# Learning Graphical Models Using Multiplicative Weights

arXiv: https://arxiv.org/abs/1706.06274 · HTML: https://mlsanity.com/paper/1706.06274/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2017.

## Built on by (most cited first, 30 of 43)

- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Optimal learning of quantum Hamiltonians from high-temperature Gibbs states](https://mlsanity.com/paper/2108.04842/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Learning to Sample from Censored Markov Random Fields](https://mlsanity.com/paper/2101.06178/) (2021)
- [Learning Continuous Exponential Families Beyond Gaussian](https://mlsanity.com/paper/2102.09198/) (2021)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry](https://mlsanity.com/paper/2206.04663/) (2022)
- [Provable learning of quantum states with graphical models](https://mlsanity.com/paper/2309.09235/) (2023)
- [Stein's method for marginals on large graphical models](https://mlsanity.com/paper/2410.11771/) (2024)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Discrete distributions are learnable from metastable samples](https://mlsanity.com/paper/2410.13800/) (2024)
- [Efficient Hamiltonian, structure and trace distance learning of Gaussian states](https://mlsanity.com/paper/2411.03163/) (2024)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)

## Abstract (arXiv)

We give a simple, multiplicative-weight update algorithm for learning undirected graphical models or Markov random fields (MRFs). The approach is new, and for the well-studied case of Ising models or Boltzmann machines, we obtain an algorithm that uses a nearly optimal number of samples and has quadratic running time (up to logarithmic factors), subsuming and improving on all prior work. Additionally, we give the first efficient algorithm for learning Ising models over general alphabets. Our main application is an algorithm for learning the structure of t-wise MRFs with nearly-optimal sample complexity (up to polynomial losses in necessary terms that depend on the weights) and running time that is nO(t). In addition, given nO(t) samples, we can also learn the parameters of the model and generate a hypothesis that is close in statistical distance to the true MRF. All prior work runs in time nOmega(d) for graphs of bounded degree d and does not generate a hypothesis close in statistical distance even for t=3. We observe that our runtime has the correct dependence on n and t assuming the hardness of learning sparse parities with noise. Our algorithm--the Sparsitron-- is easy to implement (has only one parameter) and holds in the on-line setting. Its analysis applies a regret bound from Freund and Schapire's classic Hedge algorithm. It also gives the first solution to the problem of learning sparse Generalized Linear Models (GLMs).