Pith. sign in

REVIEW 2 major objections 3 minor 2 cited by

Better Models and Algorithms for Learning Ising Models from Dynamics

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Learning Ising models from observed flips alone, with no access to failed update attempts, is possible in near-optimal time.

desk verdict First real resolution of flip-only observation for learning Ising models from dynamics; main structure-learning theorem is solid, with a fillable gap in the claimed external-field recovery and a broader-generality condition that is verified only for two chains. read the letter →

arxiv 2507.15173 v1 pith:HPCAG6O3 submitted 2025-07-21 cs.LG cs.DSstat.ML

Jason Gaitonde , Ankur Moitra , Elchanan Mossel This is my paper
classification cs.LGcs.DSstat.ML MSC 62H3060J2068W27
keywords Isingmodellearningfromdynamicsflip-onlyobservationGlauberMetropolisstructureparameterestimation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that an Ising model can be learned from the bare trajectory of its Glauber dynamics, observing only the times when a spin actually flips, without any record of update attempts that left the configuration unchanged. Prior algorithms for learning from dynamics all relied on knowing every update attempt, including non-flips; this paper removes that requirement, which is the natural observation model for most real processes. It recovers the dependence graph in time $\mathrm{poly}(d)\cdot n^2\log n$ and the parameters in additional $\tilde{O}(2^d n)$ time, matching the qualitative complexity of state-of-the-art i.i.d. algorithms. The results extend to any reversible single-site chain satisfying a stability condition, including Metropolis dynamics.

What carries the argument

The central object is the flip-cycle statistic $Z^{i,j}_t = \mathbf{1}_{iijjiijj} - 2\mathbf{1}_{iijjjiij} + \mathbf{1}_{jiijjiij}$, evaluated on short windows of length $8\varepsilon$. Its conditional expectation is approximately a squared difference of products of transition rates of the form $g_i(\pi(X^{t,i\to+1})/\pi(X^{t,i\to-1})) - g_i(\pi(X^{t,\oplus j,i\to+1})/\pi(X^{t,\oplus j,i\to-1}))$, where $g_i$ encodes the reversible transition kernel. A small-window expansion (Proposition 5.1) shows the probability of any bounded flip sequence factorizes into a product of flip rates up to $O(d\varepsilon)$ error, and a dynamical anticoncentration result guarantees that linear forms in the dynamics deviate noticeably from any fixed value with constant probability. Together these force the statistic to separate edges from non-edges except for isolated matching edges.

What would settle it

Take a reversible single-site chain on a 2-site Ising model that is consistent but not stable, check whether the difference $g_i(z) - g_i(\exp(\alpha)z)$ stays below the stated threshold for $z$ near $z^*$ while $|z - z^*|$ is large; if so, the cycle statistic's separation bound fails.

Watch

Extended reading notes

Core claim

The paper claims that the structure and parameters of an Ising model of maximum degree $d$ can be learned with high probability from the flip-only trajectory $(X_t)_{t=0}^T$, provided the model satisfies standard non-degeneracy bounds (degree $d$, width $\lambda$, edge magnitude at least $\alpha$). Structure learning runs in time $\mathrm{poly}(d)\,n^2\log n$ and parameter learning in additional $\tilde{O}(2^d n)$ time. The key mechanism is a degree-8 flip-cycle statistic $Z^{i,j}_t$ built from short alternating flip sequences; conditional on the past history, its expectation is provably separated between edges that lie in a connected component of average degree greater than 1 and non-edges. The remaining edges form a matching, which is recovered by estimating spin-spin correlations in the resulting product chain. Parameters are then recovered from estimated single-site flip rates along a small subcube, using reversibility to convert ratios of flip rates into edge weights.

Load-bearing premise

For the general class of chains beyond Glauber and Metropolis, the abstract stability condition in Assumption 2 is a postulate rather than a verified property; if a natural reversible single-site chain violates it, the cycle statistic can no longer separate edges from non-edges.

Editorial extensions

If this is right

  • Observing only configuration changes is sufficient for learning, so physical or network processes can be used as data without tracking hidden update attempts.
  • The runtime and sample complexity match the state-of-the-art i.i.d. learning results, despite the far weaker observation model.
  • The approach succeeds for a general class of reversible single-site chains, not just Glauber dynamics, whenever the stability condition holds.
  • Parameter recovery inherits the same $\tilde{O}(2^d n)$ dependence, suggesting that the exponential-in-degree factor is intrinsic to subcube-based rate estimation rather than to the observation model.
  • Once the graph is known, the algorithm's parameter estimates achieve $\varepsilon$-accuracy in $\tilde{O}(2^d n \,\mathrm{poly}(1/\varepsilon))$ time with high probability.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The flip-cycle statistic likely tests a more general principle: local correlations in a trajectory are detectable from transition events alone even when the underlying update attempts are hidden, provided the observation window is short enough that the dominant path is the intended one.
  • The abstract stability condition in Assumption 2 may be verified for additional chains such as Barker dynamics or other reversible single-site kernels with monotone transition functions, expanding the algorithmic reach beyond the two examples given.
  • A natural testable extension is to ask whether the matching-recovery step can be replaced by a flip-only statistic as well, avoiding the need for time-averaged spin-spin correlation estimates.
  • The parameter learning guarantee should degrade gracefully when edge magnitudes are only lower bounded by $\alpha$; one could test empirically whether the $\tilde{O}(2^d)$ factor is actually necessary in practice on sparse graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies the problem of learning an Ising model from a continuous-time Glauber dynamics trajectory in which only actual spin flips are observed, and failed update attempts are not. The main advertised contributions are: (i) a structure-learning algorithm that recovers the dependence graph with O(poly(d) n^2 log n) runtime under Assumption 1, (ii) a parameter-learning algorithm that recovers the interaction matrix A to epsilon accuracy in O~(2^d n) time once the graph is known, (iii) the same guarantees for a broader class of reversible single-site chains, notably Metropolis dynamics, under Assumption 2. The technical machinery includes a degree-8 short-window flip-cycle statistic, anticoncentration estimates for linear forms under the dynamics, a matching-recovery step using spin-spin correlations, and local flip-rate estimation based on reversibility. The paper is self-contained for most of the Glauber structure-learning and interaction-matrix parameter estimation, but two load-bearing parts need attention: the proof of Corollary 5.5 contains an algebraic reduction that appears incorrect, and the recovery of the external fields h is only sketched in a remark.

Significance. If the results are correct, this is a substantial advance over a line of work dating back to Bresler, Gamarnik, and Shah: it removes the strong observability assumption that all site-update attempts are known, which has been considered essential in prior dynamical learning algorithms. The claimed n-dependence matches state-of-the-art guarantees in the i.i.d. setting, and the extension to Metropolis dynamics is a useful robustness property. The paper also contains a careful and largely self-contained development of the short-window flip expansion (Proposition 5.1), the anticoncentration lemma (Corollary 4.5), and the interaction-matrix estimation theorem (Theorem 6.5). The significance is therefore high, but it is conditional on repairing the proof of the dense-edge detection step and on supplying a real proof for the h-recovery claim, since both are advertised as main results.

major comments (2)
  1. [Section 5.2, Corollary 5.5 (Eqs. (26)-(27))] The reduction to the stability condition is algebraically incorrect, and as written the lower bound (24) does not follow. Let r0 = exp(2*Aik*X^t_k summed over k not equal to i, plus 2*h_i) and r1 = exp(2*Aik*X^t_k summed over k not equal to i,j, minus 2*Aij*X^t_j, plus 2*h_i) be the two ratios in Proposition 5.3. Their product is r0*r1 = exp(4 times the sum over k not equal to i,j of Aik*X^t_k plus 4*h_i), so the j-th term cancels. For Glauber-type g, the near-equality |g(r0) - g(r1)| <= delta is therefore the condition that the sum over k not equal to i,j of Aik*X^t_k is close to -h_i. It is not equivalent to the claimed statement that z := exp(2 times the sum over k not equal to i of Aik*X^t_k plus 2*h_i minus 2*|Aij|) is close to z*(4*|Aij|). Consequently Eq. (27) has the wrong center: it contains plus 2*|Aij|, while the correct center is -h_i. The subsequent anticoncentration event E_a with a = -2*h_i + 2*|Aij| does not rule out the dangerous near-equality; the dangerous event can occur on E_a, so Corollary 5.5 is not established as written. Since Theorem 5.6 and the main structure-learning claim depend on Corollary 5.5, this is a load-bearing gap. The claim appears repairable by taking a = -h_i and applying stability to y = min(r0, r1), but the current proof needs a corrected derivation.
  2. [Section 6.2, Theorem 1.2 and Remark 1] The abstract and Theorem 1.2 advertise recovery of both A and h to epsilon accuracy, but the formal parameter-learning theorem (Theorem 6.5) only controls the interaction matrix A. The recovery of h is delegated to Remark 1, which contains a one-line sketch and closes with "We leave the details to the interested reader." This is not a proof of the advertised h-recovery claim, and no runtime or high-probability guarantee is given for the fields. Since the external-field recovery is explicitly part of the main results, this gap must be fixed either by supplying a complete proof with the same level of detail as Theorem 6.5 or by explicitly rescoping the main claims to interaction-matrix recovery.
minor comments (3)
  1. [Section 3.3, Assumption 2 and Definition 3.10] The advertised generality to a broader class of reversible, single-site chains is entirely conditional on the (lambda, alpha0, delta0, eta)-stability condition, which is verified only for Glauber dynamics and site-homogeneous Metropolis dynamics in Propositions 3.14 and 3.16. This is not a flaw in the conditional theorems, but the introduction and abstract should state more precisely that the algorithms are designed for chains satisfying Assumption 2 and that the condition is verified for two specific families; otherwise the reader may infer a broader verified theory.
  2. [Section 5.2, Corollary 5.5] The definition of the linear form in the proof of Corollary 5.5, written as the sum over ell not equal to i,j of A_{i,ell} x_k, uses ell both as a summation index and as the name of the function while also introducing k as an apparently free index; this should be rewritten with a single clear dummy variable, such as the sum over r not equal to i,j of A_{i,r} x_r.
  3. [Throughout] The notation O-tilde and e-O is used without a unified definition; the abstract states O-tilde(2^d n) for parameter learning while Theorem 6.5 states e-O(exp(O(gamma lambda)) 2^d log(1/beta) / delta^4 kappa^8), and the relationship between the two expressions is not explained. The authors should define both notations once and use them consistently.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main structure- and parameter-learning claims are derived from new propositions, with self-citations only for auxiliary techniques.

full rationale

The derivation chain is self-contained for its central claims. Theorem 1.1 (structure learning) rests on Propositions 5.1, 5.3 and Corollaries 5.4-5.5, all proved in this paper from the explicit flip-window expansion; the edge/non-edge separation is obtained by Proposition 5.3's expectation formula plus the anticoncentration of Corollary 4.5, not by fitting. Theorem 1.2 (parameter learning) uses Lemma 6.1 and Corollary 6.4 to estimate transition probabilities, then the reversibility ratio (37) to recover A_ij; no parameter is fitted to the target output. Assumption 2, including the stability condition of Definition 3.10, is an explicit hypothesis rather than a conclusion; the paper verifies it for Glauber (Prop 3.14) and Metropolis (Prop 3.16), and the stated generalization is conditional on it. Self-citations to [GM24] and [GMM25] supply a boundedness Fact B.2 and the 'squaring trick' construction, but the load-bearing analysis is re-proved here (Propositions 5.1 and 5.3). Thus there is no equation that reduces to its own input and no fitted quantity is renamed as a prediction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on Assumption 1 (bounded degree, width, separation) and Assumption 2 (an abstract class of single-site chains). The free parameters are algorithm hyperparameters, not fitted to data. No new unverified physical or mathematical entities are introduced.

free parameters (2)
  • epsilon (window length) = c_ALG * kappa^8 * delta^2 * exp(-O(gamma lambda)) / d
    Hyperparameter of the flip-cycle statistics and flip-rate estimator. Chosen to make error terms O(d epsilon) negligible. Not fitted to data, but the sample complexity depends polynomially on it.
  • delta (stability threshold) = min{eta^{-1}(c exp(-O(lambda))/alpha), delta0}
    Threshold used in the cycle-statistic separation (Corollary 5.5). Chosen to satisfy the stability condition and determines epsilon and the trajectory length T.
assumptions (4)
  • domain assumption Bounded degree d, bounded width lambda, and neighbor nondegeneracy |A_ij| >= alpha (Assumption 1).
    All theorems condition on these model parameters being known and satisfied.
  • domain assumption Assumption 2: site-consistency, (lambda, alpha0, delta0, eta)-stability, gamma-boundedness, and kappa lower bound on transition probabilities.
    The analysis applies to chains satisfying this abstract condition. It is verified for Glauber (Prop 3.14) and Metropolis (Prop 3.16), but is not verified for arbitrary single-site chains.
  • domain assumption The observed process is an exact continuous-time reversible single-site Markov chain with unit-rate Poisson clocks.
    The algorithms assume noise-free continuous-time observations of flip times.
  • standard math Standard probability tools: Azuma-Hoeffding, Freedman's martingale inequality (Prop A.4), Lezaud's Chernoff bound for Markov chains (Thm 3.5), and the canonical paths spectral gap (Fact 3.7).
    Used without proof in the analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Better Models and Algorithms for Learning Ising Models from Dynamics." pith.science (2026). https://pith.science/paper/HPCAG6O3

@misc{pith2026250715173,
  author       = {Pith},
  title        = {Pith review of: Better Models and Algorithms for Learning Ising Models from Dynamics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HPCAG6O3}},
  note         = {Machine review of arXiv:2507.15173}
}
abstract

We study the problem of learning the structure and parameters of the Ising model, a fundamental model of high-dimensional data, when observing the evolution of an associated Markov chain. A recent line of work has studied the natural problem of learning when observing an evolution of the well-known Glauber dynamics [Bresler, Gamarnik, Shah, IEEE Trans. Inf. Theory 2018, Gaitonde, Mossel STOC 2024], which provides an arguably more realistic generative model than the classical i.i.d. setting. However, this prior work crucially assumes that all site update attempts are observed, \emph{even when this attempt does not change the configuration}: this strong observation model is seemingly essential for these approaches. While perhaps possible in restrictive contexts, this precludes applicability to most realistic settings where we can observe \emph{only} the stochastic evolution itself, a minimal and natural assumption for any process we might hope to learn from. However, designing algorithms that succeed in this more realistic setting has remained an open problem [Bresler, Gamarnik, Shah, IEEE Trans. Inf. Theory 2018, Gaitonde, Moitra, Mossel, STOC 2025]. In this work, we give the first algorithms that efficiently learn the Ising model in this much more natural observation model that only observes when the configuration changes. For Ising models with maximum degree $d$, our algorithm recovers the underlying dependency graph in time $\mathsf{poly}(d)\cdot n^2\log n$ and then the actual parameters in additional $\widetilde{O}(2^d n)$ time, which qualitatively matches the state-of-the-art even in the i.i.d. setting in a much weaker observation model. Our analysis holds more generally for a broader class of reversible, single-site Markov chains that also includes the popular Metropolis chain by leveraging more robust properties of reversible Markov chains.

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics

    stat.ML 2026-07 accept novelty 7.0 of 10

    Exact graph recovery from one Glauber trajectory is provably achievable at the information-theoretic κ^{-2} sample rate without mixing or stationarity assumptions, via a dueling-neighborhood search with two local traj...

  2. Interpreting learning dynamics of autoencoders: Transient scaling and emerging concepts of the Ising model

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Unsupervised autoencoders on Ising configurations form magnetization then energy representations in two dynamical regimes, with recursive error flow fields sharing topology across layers.

Reference graph

Works this paper leans on

55 extracted references · 52 canonical work pages · cited by 2 Pith papers

  1. [1]

    Abrahao, Flavio Chierichetti, Robert Kleinberg, and Alessandro Panconesi

    Bruno D. Abrahao, Flavio Chierichetti, Robert Kleinberg, and Alessandro Panconesi. Trace complexity of network inference. In The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD , pages 491--499. ACM , 2013

    work page 2013

  2. [2]

    Chow- L iu++: O ptimal P rediction- C entric L earning of T ree I sing M odels

    Enric Boix - Adser \` a , Guy Bresler, and Frederic Koehler. Chow- L iu++: O ptimal P rediction- C entric L earning of T ree I sing M odels. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 , pages 417--426. IEEE , 2021

    work page 2021

  3. [3]

    Bartlett, Varsha Dani, Thomas P

    Peter L. Bartlett, Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Rocco A. Servedio and Tong Zhang, editors, 21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008 , pages 335--342. Omnipress, 2008

    work page 2008

  4. [4]

    Bovier and F

    A. Bovier and F. den Hollander. Metastability: A Potential-Theoretic Approach . Grundlehren der mathematischen Wissenschaften. Springer International Publishing, 2016

    work page 2016

  5. [5]

    Bartlett, Paul Fischer, and Klaus - Uwe H \" o ffgen

    Peter L. Bartlett, Paul Fischer, and Klaus - Uwe H \" o ffgen. Exploiting random walks for learning. Inf. Comput. , 176(2):121--135, 2002

    work page 2002

  6. [6]

    Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, and N. V. Vinodchandran. Near-optimal learning of tree-structured distributions by chow and liu. SIAM J. Comput. , 52(3):761--793, 2023

    work page 2023

  7. [7]

    Learning G raphical M odels from the G lauber D ynamics

    Guy Bresler, David Gamarnik, and Devavrat Shah. Learning G raphical M odels from the G lauber D ynamics. IEEE Trans. Inf. Theory , 64(6):4072--4080, 2018

    work page 2018

  8. [8]

    Learning a tree-structured Ising model in order to make predictions

    Guy Bresler and Mina Karzand. Learning a tree-structured Ising model in order to make predictions . The Annals of Statistics , 48(2):713 -- 737, 2020

    work page 2020

Show all 55 references
  1. [9]

    Learning restricted B oltzmann machines via influence maximization

    Guy Bresler, Frederic Koehler, and Ankur Moitra. Learning restricted B oltzmann machines via influence maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 , pages 828--839. ACM , 2019

    2019

  2. [10]

    A new approach to learning linear dynamical systems

    Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau. A new approach to learning linear dynamical systems. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 , pages 335--348. ACM , 2023

    2023

  3. [11]

    Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior , 5(3):387--424, 1993

    1993

  4. [12]

    Bshouty, Elchanan Mossel, Ryan O'Donnell, and Rocco A

    Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning DNF from random walks. J. Comput. Syst. Sci. , 71(3):250--265, 2005

    2005

  5. [13]

    Reconstruction of M arkov R andom F ields from S amples: S ome O bservations and A lgorithms

    Guy Bresler, Elchanan Mossel, and Allan Sly. Reconstruction of M arkov R andom F ields from S amples: S ome O bservations and A lgorithms. SIAM J. Comput. , 42(2):563--578, 2013

    2013

  6. [14]

    Andrej Bogdanov, Elchanan Mossel, and Salil P. Vadhan. The C omplexity of D istinguishing M arkov R andom F ields. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Worksh...

    2008

  7. [15]

    Efficiently L earning I sing M odels on A rbitrary G raphs

    Guy Bresler. Efficiently L earning I sing M odels on A rbitrary G raphs. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , pages 771--782. ACM , 2015

    2015

  8. [16]

    Localization S chemes: A F ramework for P roving M ixing B ounds for M arkov C hains

    Yuansi Chen and Ronen Eldan. Localization S chemes: A F ramework for P roving M ixing B ounds for M arkov C hains. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 , pages 110--122. IEEE , 2022

    2022

  9. [17]

    Gautam Chandrasekaran and Adam R. Klivans. Learning the Sherrington-Kirkpatrick Model Even at Low Temperature . In Michal Kouck \' y and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 , ...

    2025

  10. [18]

    Approximating discrete probability distributions with dependence trees

    Chao-Kong Chow and Chao-Ning Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory , 14(3):462--467, 1968

    1968

  11. [19]

    Learning I sing models from one or multiple samples

    Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros. Learning I sing models from one or multiple samples. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 161--168. ACM , 2021

    2021

  12. [20]

    Kane, Alistair Stewart, and Yuxin Sun

    Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. Outlier-Robust Learning of Ising Models Under Dobrushin's Condition . In Conference on Learning Theory, COLT 2021 , volume 134 of Proceedings of Machine Learning Research , pages 1645--1682. PMLR , 2021

    2021

  13. [21]

    Lokhov, Marc Vuffray, and Sidhant Misra

    Arkopal Dutt, Andrey Y. Lokhov, Marc Vuffray, and Sidhant Misra. Exponential R eduction in S ample C omplexity with L earning of I sing M odel D ynamics. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021 , volume 139 of Proceedings of Machine L...

    2021

  14. [22]

    The minimax learning rates of normal and I sing undirected graphical models

    Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The minimax learning rates of normal and I sing undirected graphical models. Electronic Journal of Statistics , 14:2338--2361, 2020

    2020

  15. [23]

    A S pectral C ondition for S pectral G ap: F ast M ixing in H igh- T emperature I sing M odels

    Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. A S pectral C ondition for S pectral G ap: F ast M ixing in H igh- T emperature I sing M odels. Probability T heory and R elated F ields , 182(3-4):1035--1051, 2022

    2022

  16. [24]

    Kane, and Adam R

    Surbhi Goel, Daniel M. Kane, and Adam R. Klivans. Learning I sing M odels with I ndependent F ailures. In Conference on Learning Theory, COLT 2019 , volume 99 of Proceedings of Machine Learning Research , pages 1449--1469. PMLR , 2019

    2019

  17. [25]

    Klivans, and Frederic Koehler

    Surbhi Goel, Adam R. Klivans, and Frederic Koehler. From B oltzmann M achines to N eural N etworks and B ack A gain. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020 , 2020

    2020

  18. [26]

    Time-dependent statistics of the Ising model

    Roy J Glauber. Time-dependent statistics of the Ising model . Journal of mathematical physics , 4(2):294--307, 1963

    1963

  19. [27]

    A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width

    Jason Gaitonde and Elchanan Mossel. A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width . In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024 , pages 503--514. ACM , 2024

    2024

  20. [28]

    Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics

    Jason Gaitonde, Ankur Moitra, and Elchanan Mossel. Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics . In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025 , pages 348--359. ACM , 2025

    2025

  21. [29]

    Low-temperature Ising dynamics with random initializations

    Reza Gheissari and Alistair Sinclair. Low-temperature Ising dynamics with random initializations . In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1445--1458. ACM , 2022

    2022

  22. [30]

    Rapid phase ordering for Ising and Potts dynamics on random regular graphs

    Reza Gheissari, Allan Sly, and Youngtak Sohn. Rapid phase ordering for Ising and Potts dynamics on random regular graphs . arXiv preprint arXiv:2505.15783 , 2025

    2025 arXiv

  23. [31]

    W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications . Biometrika , 57(1):97--109, 04 1970

    1970

  24. [32]

    Learning graphs from noisy epidemic cascades

    Jessica Hoffmann and Constantine Caramanis. Learning graphs from noisy epidemic cascades. Proc. ACM Meas. Anal. Comput. Syst. , 3(2):40:1--40:34, 2019

    2019

  25. [33]

    Information T heoretic P roperties of M arkov R andom F ields, and their A lgorithmic A pplications

    Linus Hamilton, Frederic Koehler, and Ankur Moitra. Information T heoretic P roperties of M arkov R andom F ields, and their A lgorithmic A pplications. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , p...

    2017

  26. [34]

    Lokhov, Sidhant Misra, and Marc Vuffray

    Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra, and Marc Vuffray. Discrete distributions are learnable from metastable samples. CoRR , abs/2410.13800, 2024

    2024 arXiv

  27. [35]

    R. E. Kalman. A New Approach to Linear Filtering and Prediction Problems . Journal of Basic Engineering , 82(1):35--45, 03 1960

    1960

  28. [36]

    Learning and T esting L atent- T ree I sing M odels E fficiently

    Anthimos Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, and Davin Choo. Learning and T esting L atent- T ree I sing M odels E fficiently. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023 , volume 195 of Proceedings of Machine Learning Research , page...

    2023

  29. [37]

    Statistical E fficiency of S core M atching: T he V iew from I soperimetry

    Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical E fficiency of S core M atching: T he V iew from I soperimetry. In The Eleventh International Conference on Learning Representations, ICLR 2023 , 2023

    2023

  30. [38]

    Efficiently learning and sampling multimodal distributions with data-based initialization

    Frederic Koehler, Holden Lee, and Thuy - Duong Vuong. Efficiently learning and sampling multimodal distributions with data-based initialization. CoRR , abs/2411.09117, 2024

    2024 arXiv

  31. [39]

    Klivans and Raghu Meka

    Adam R. Klivans and Raghu Meka. Learning G raphical M odels U sing M ultiplicative W eights. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , pages 343--354. IEEE Computer Society, 2017

    2017

  32. [40]

    Mailath, and Rafael Rob

    Michihiro Kandori, George J. Mailath, and Rafael Rob. Learning, mutation, and long run equilibria in games. Econometrica , 61(1):29--56, 1993

    1993

  33. [41]

    Chernoff and Berry--Ess \'e en inequalities for Markov processes

    Pascal Lezaud. Chernoff and Berry--Ess \'e en inequalities for Markov processes . ESAIM: Probability and Statistics , 5:183--201, 2001

    2001

  34. [42]

    Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, and David X. Wu. Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains . In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024 , pages 203--215. IEEE , 2024

    2024

  35. [43]

    Levin and Yuval Peres

    David A. Levin and Yuval Peres. Markov C hains and M ixing T imes , volume 107. American Mathematical Soc., 2017

    2017

  36. [44]

    Rosenbluth, Marshall N

    Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics , 21(6):1087--1092, 1953

    1953

  37. [45]

    Convergence to E quilibrium in L ocal I nteraction G ames

    Andrea Montanari and Amin Saberi. Convergence to E quilibrium in L ocal I nteraction G ames. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009 , pages 303--312. IEEE Computer Society, 2009

    2009

  38. [46]

    Learning the graph of epidemic cascades

    Praneeth Netrapalli and Sujay Sanghavi. Learning the graph of epidemic cascades. In ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '12 , pages 211--222. ACM , 2012

    2012

  39. [47]

    On L earning I sing M odels under H uber's C ontamination M odel

    Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar. On L earning I sing M odels under H uber's C ontamination M odel. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS...

    2020

  40. [48]

    High- D imensional I sing M odel S election U sing _1 - R egularized L ogistic R egression

    Pradeep Ravikumar, Martin J Wainwright, and John D Lafferty. High- D imensional I sing M odel S election U sing _1 - R egularized L ogistic R egression. The Annals of Statistics , pages 1287--1319, 2010

    2010

  41. [49]

    Learning linear dynamical systems with semi-parametric least squares

    Max Simchowitz, Ross Boczar, and Benjamin Recht. Learning linear dynamical systems with semi-parametric least squares. In Conference on Learning Theory, COLT 2019 , volume 99 of Proceedings of Machine Learning Research , pages 2714--2802. PMLR , 2019

    2019

  42. [50]

    Computational transition at the uniqueness threshold

    Allan Sly. Computational transition at the uniqueness threshold. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages 287--296. IEEE, 2010

    2010

  43. [51]

    The C omputational H ardness of C ounting in T wo- S pin M odels on d - R egular G raphs

    Allan Sly and Nike Sun. The C omputational H ardness of C ounting in T wo- S pin M odels on d - R egular G raphs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 , pages 361--369. IEEE Computer Society, 2012

    2012

  44. [52]

    Santhanam and Martin J

    Narayana P. Santhanam and Martin J. Wainwright. Information-theoretic limits of selecting binary graphical models in high dimensions. IEEE Trans. Inf. Theory , 58(7):4117--4134, 2012

    2012

  45. [53]

    Lokhov, and Michael Chertkov

    Marc Vuffray, Sidhant Misra, Andrey Y. Lokhov, and Michael Chertkov. Interaction S creening: E fficient and S ample- O ptimal L earning of I sing M odels. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016 ,...

    2016

  46. [54]

    Shanshan Wu, Sujay Sanghavi, and Alexandros G. Dimakis. Sparse L ogistic R egression L earns A ll D iscrete P airwise G raphical M odels. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019 , pa...

    2019

  47. [55]

    Peyton Young

    H. Peyton Young. The dynamics of social innovation. Proceedings of the National Academy of Sciences , 108:21285--21291, 2011

    2011

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.