PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Graphical Models Using Multiplicative Weights

Adam Klivans, Raghu Meka

arXiv:1706.06274v1cs.LGcs.DSmath.STstat.TH

TL;DR

Learning MRF structure and parameters has required efficient algorithms with favorable sample and runtime guarantees, while prior higher-order methods have limitations in runtime and hypothesis output. The paper introduces multiplicative-weight Sparsitron and applies it to Ising models, sparse GLMs, and t-wise MRFs, obtaining learning and reconstruction results with nearly optimal sample complexity in the stated settings.

  • Problem

    Learning graphical-model structure from random samples is a central problem, while prior general t-wise MRF methods run in n^Ω(d) time and do not output a statistically close hypothesis even for t=3.

    Source: §1 · p. 2

  • Method

    The paper uses Sparsitron, a multiplicative-weight update algorithm, and extends it to higher-order MRFs by applying it to degree-t multilinear polynomials.

    Source: §1.1 · p. 2, §1.2 · p. 4

  • Results

    The approach learns Ising models with nearly optimal sample complexity and ˜O(n^2) time per example, and learns binary t-wise MRF structure in n^O(t) time with parameter recovery and point-wise approximation given roughly n^O(t) samples.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    Sparsitron also provides an online algorithm for sparse GLMs with sample complexity O(λ^2 log n) under the stated model conditions.

    Source: §3 · p. 6

    The t-wise MRF argument imposes a non-degeneracy condition to address the possibility that distinct graphs and factorizations yield the same factorization polynomial.

    Source: §7 · p. 16

Abstract

from arXiv · show

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 $n^{O(t)}$. In addition, given $n^{O(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 $n^{\Omega(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).

1 Introduction

The paper introduces a multiplicative-weight algorithm for learning MRFs and applies it to Ising models, sparse GLMs, and higher-order MRFs. Its approach uses online updates and δ-unbiasedness to obtain learning and recovery guarantees.

1.1 Our Results

  • The algorithm learns Ising models on arbitrary graphs with nearly optimal sample complexity and ˜O(n^2) running time per example, including unbounded-degree graphs when each neighborhood's weight vector has bounded ℓ1 norm.For bounded-degree graphs, the paper says this subsumes and improves prior work.Source: §1.1 · p. 2
  • For binary t-wise MRFs, the algorithm learns the dependency graph in n^O(t) time and, with roughly n^O(t) samples, reconstructs parameters and outputs a point-wise approximation to the distribution.The sample statement suppresses necessary terms depending on the weights.Source: §1.1 · p. 2
  • The paper motivates its n^O(t) runtime by a reduction from sparse parity with noise, and notes that prior general t-wise MRF algorithms run in n^Ω(d) time and do not produce a hypothesis close in statistical distance, even for t=3.The reduction is attributed to Bresler, Gamarnik, and Shah.Source: §1.1 · p. 3
  • Sparsitron also learns sparse GLMs online, using one parameter and sample complexity O(λ^2 log n) under the stated bounded-ℓ1-weight and monotone Lipschitz transfer-function conditions.It outputs a predictor close in squared loss to the true conditional mean function.Source: §1.1 · p. 3

1.2 Our Approach

  • The method replaces additive updates with multiplicative-weight updates, whose analysis uses the Hedge regret bound; it targets ℓ1-dependent sample complexity and recovery of the weight vector itself.The GLMtron's dependence on the ℓ2 norm and its prediction-error guarantee do not meet those goals in this setting.Source: §1.2 · p. 4

1.3 Best-Experts Interpretation of Our Algorithm

  • For Ising models, the algorithm can be viewed as weighted voting among candidate neighbors; non-neighbor weights rapidly decay, while the weights converge to those of the underlying model.For higher-order MRFs, the approach extends to degree-t multilinear polynomials, with small prediction error implying close polynomials under δ-unbiased distributions.Source: §1.2 · p. 4, §1.3 · p. 5

2 Preliminaries

The preliminaries establish notation for vectors and multilinear polynomials used in the later analysis.

2 Preliminaries

  • For a vector x, x−i denotes the vector of coordinates other than i; a multilinear polynomial is represented by its monomial coefficients.The coefficient ˆp(I) denotes the coefficient of the monomial indexed by I.Source: §2 · p. 6
  • The partial derivative notation ∂ip and ∂Ip denotes differentiation with respect to one variable or a set of variables, respectively.These derivatives are expressed using the polynomial's monomial coefficients.Source: §2 · p. 6
  • A maximal monomial is a nonzero monomial whose index set is not strictly contained in any other nonzero monomial's index set.Source: §2 · p. 6

3 Learning Sparse Generalized Linear Models

This section presents Sparsitron for sparse generalized linear models and establishes its prediction-risk guarantee. The algorithm uses a Hedge regret bound, has sample complexity depending on the ℓ1 weight bound, and can run online.

3 Learning Sparse Generalized Linear Models

  • The algorithm runs in O(nT) time and can be run online, where T is its number of update iterations.Source: §3 · p. 6
  • The analysis applies the Hedge regret bound to expert-associated losses and uses empirical risk estimates to obtain the stated guarantee.The algorithm's inputs consist of independent examples used for updates and risk estimation.Source: §3 · p. 7
  • With O(λ^2 log(n/(εδ))/ε^2) samples, Sparsitron produces a predictor with squared-loss risk at most ε with probability at least 1−2δ.The theorem assumes examples in [−1,1]^n × {0,1}, conditional mean u(w·x), nondecreasing 1-Lipschitz u, and known ∥w∥1 ≤ λ.Source: §3 · pp. 6, 8

4 Recovering affine functions from ℓ2 minimization

This section shows that sufficiently accurate sigmoid ℓ2 approximation yields an ℓ∞ approximation to an unknown affine weight vector. The analysis uses δ-unbiased inputs and a lower bound on sigmoid sensitivity.

4 Recovering affine functions from ℓ2 minimization

  • Sufficiently low error in sigmoid ℓ2 minimization yields an ℓ∞ approximation to the unknown weight vector.The paper uses this approximation to reconstruct Ising-model dependency graphs and edge weights.Source: §4 · p. 9
  • The proof uses sigmoid monotonicity and a derivative lower bound to relate prediction differences to differences between affine inputs.The derivative bound stated is σ′(t) = 1/(2 + e^t + e^−t) ≥ e^−|t|/4.Source: §4 · p. 9
  • For a δ-unbiased distribution D on {−1,1}ⁿ, Lemma 4.3 assumes Eₓ∼D[(σ(w·x+α)−σ(v·x+β))²] ≤ ε, with ε < δ·exp(−2∥w∥₁−2|α|−6).Source: §4 · p. 9

5 Learning Ising Models

The paper applies Sparsitron to conditional probabilities in Ising models to estimate parameters and recover dependency graphs. The resulting algorithms have quadratic-in-n runtime and near-optimal sample complexity under the stated width and weight conditions.

5 Learning Ising Models

  • The model's width is λ(A, θ) = maxi(Pj |Aij| + |θi|), which controls the parameter bounds used in the analysis.The algorithm applies Sparsitron to estimate the coordinate-specific weight vectors.Source: §5 · pp. 10–11
  • The parameter-estimation algorithm uses N = O(λ2 exp(O(λ))/ε4)·(log(n/ρε)) samples and runs in O(n2N) time.It produces an estimate  satisfying the theorem's stated guarantee with probability at least 1−ρ, and can run online.Source: §5 · p. 10
  • The method learns conditional probabilities as sigmoid generalized linear models, with coefficients determined by the Ising interaction weights.For coordinate i, the conditional probability is expressed as σ(w(i) · x + θi), where w(i)j = −2Aij.Source: §5 · p. 10
  • N = O(exp(O(λ))/η4) · (log(n/ρη)) samples suffice to recover the dependency graph with probability at least 1−ρ, in O(n2N) runtime.This corollary assumes width at most λ and every nonzero entry of A has absolute value at least η; it is online-capable.Source: §5 · p. 11
  • The graph-recovery sample complexity is near the best-known information-theoretic lower bound for learning Ising-model structure.The comparison is to the lower bound of Santhanam and Wainwright.Source: §5 · p. 12

6 Recovering polynomials from ℓ2 minimization

This section establishes that, under δ-unbiased inputs, closeness between sigmoid outputs of low-degree polynomials can support recovery of polynomial structure and coefficients. Its proof uses anti-concentration and bounds on maximal monomials.

6 Recovering polynomials from ℓ2 minimization

  • The section uses anti-concentration: a maximal monomial I in s has |s(X)| at least |b_s(I)| with probability at least δ^|I|.The proof derives this by induction on |I| under δ-unbiasedness.Source: §6 · pp. 12–13
  • Small sigmoid ℓ2 error can constrain maximal monomials of p and q, including those of p−q, under the stated conditions.The section states that highest-degree monomials of p and q are close and gives Lemma 6.3 for maximal monomials of p−q.Source: §6 · pp. 13–14
  • Even under the lemma's hypothesis, the coefficients of p and q can nevertheless be far apart.The section's coefficient-recovery claims concern maximal monomials rather than unrestricted closeness of all coefficients.Source: §6 · pp. 12–13
  • For degree-t polynomials, sufficiently small sigmoid ℓ2 error implies that ∥p −q∥1 is small under the stated δ-unbiasedness and error condition.The condition in Lemma 6.4 is ε < e−2∥p∥1−6δt.Source: §6 · p. 14

7 Learning Markov Random Fields

This section develops Sparsitron-based methods for learning binary t-wise MRF structure and parameters, including log-polynomial densities. Under the stated weight and identifiability conditions, the methods recover dependency structure with nearly optimal sample complexity and can produce polynomial or distributional approximations.

7 Learning Markov Random Fields

  • For η-identifiable binary t-wise MRFs, structure recovery has nearly optimal sample complexity and runs in O(N n^t) time.The algorithm succeeds with probability at least 1−ρ and can run online.Source: §7 · p. 16
  • With additional samples, the method can produce a t-wise MRF that pointwise approximates the original density.The theorem states an O(N n^t) runtime and online operation.Source: §7 · pp. 16–17

7.2 Learning log-polynomial densities and parameters of MRFs

  • For degree-at-most-t log-polynomial densities, the algorithm finds a polynomial and estimates every maximal-monomial coefficient within ε with probability at least 1−ρ.The algorithm runs in O(N n^t) time and can run online.Source: §7 · p. 17

7.1 Learning the structure of MRFs

  • Feature expansion lets Sparsitron estimate partial derivatives; fresh-sample medians of maximal-monomial coefficients then identify neighbors and recover the graph.The procedure repeats neighbor recovery across vertices and applies a union bound.Source: §7.1 · pp. 18–19

7.2 Learning log-polynomial densities and parameters of MRFs

  • To form an MRF hypothesis, the construction connects variables appearing together in nonzero monomials of the approximating polynomial.The resulting factorization polynomial is used to define a t-wise MRF.Source: §7 · p. 16, §7.2 · p. 20

8 Extension of the Ising Model to general alphabet

This section extends the Ising-model learning approach to general alphabets and describes recovery of dependency graphs and model parameters. Its graph-recovery guarantee applies to non-binary Ising models under width and identifiability conditions.

8 Extension of the Ising Model to general alphabet

  • The extension targets learning both the dependency graph and parameters of general-alphabet models, with nearly optimal sample complexity.For k = 2, the model description coincides with the binary Ising model discussed earlier.Source: §8 · p. 21
  • The model assumes centered interaction matrices, and η-identifiability requires every dependency-graph edge to have an interaction of magnitude at least η.The matrices can be centered without loss of generality.Source: §8 · pp. 21–22
  • Given an η-identifiable model of width λ, N = O(exp(O(λ))/η^4) log(n/(ρη)) k^3 samples suffice for graph recovery with probability at least 1 − ρ; runtime is O(k^2 n^2 N), and the algorithm is online.The guarantee is for an n-variable non-binary Ising model with alphabet size k.Source: §8 · p. 22
  • The proof uses a non-binary analogue of unbiasedness: every symbol's conditional probability given the other variables is bounded below by δ, with δ depending on model width.This condition supports the extension of the earlier Ising-model argument.Source: §8 · p. 22
  • For each vertex pair, the method estimates interaction contrasts across alphabet symbols and declares a neighbor when the estimated contrast exceeds η/2.It repeats this procedure across symbol pairs and vertices; the threshold relies on η-identifiability.Source: §8 · pp. 23–24

A Hardness of Learning t-wise Markov random fields

The section reduces learning sparse parities with noise to learning the structure of a higher-order MRF. It concludes that, assuming sparse-parity-with-noise hardness, the paper's n^O(t) runtime matches a conditional n^Ω(t) lower bound for learning t-wise MRFs.

A Hardness of Learning t-wise Markov random fields

  • Assuming sparse parities with noise are hard to learn, learning t-wise MRFs for t < d on degree-d graphs requires time n^Ω(t), matching the paper's positive runtime dependence.The lower bound follows from embedding parity learning as an MRF.Source: A Hardness of Learning t-wise Markov… · pp. 27–28
  • The reduction encodes a k-sparse parity as a clique involving its k input variables and an additional vertex in a (k + 1)-wise MRF.Recovering the clique would reveal the underlying sparse parity.Source: A Hardness of Learning t-wise Markov… · pp. 27–28
  • The current best algorithm for k-LSPN is reported to run in time n^Ω(0.8k), and a sub-n^k algorithm would be a major breakthrough.The passage presents this as context for the reduction's significance.Source: A Hardness of Learning t-wise Markov… · p. 28
Loading 1706.06274v1…