Research map / Learning theory and algorithms / Sample complexity
Near-Optimality of Contrastive Divergence Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives non-asymptotic analysis of contrastive divergence for unnormalized exponential families, showing parametric O(n^{-1/2}) rates for online CD (near-optimal asymptotic variance with averaging) and near-parametric rates for offline CD.
Problem
Prior analyses showed only asymptotic O(n^{-1/3}) consistency of contrastive divergence (CD) for unnormalized exponential families; it was open whether CD achieves the parametric rate and near-optimal variance.
Approach
Treat CD as biased SGD on the cross-entropy, derive a recursion on the squared parameter error that separates a bias term (decaying in MCMC steps m) and an extra variance term, obtaining O(n^{-1/2}) for online CD and, with Polyak-Ruppert averaging, asymptotic variance within factor 4 of the Cramér-Rao bound; offline analysis controls data-iterate correlations via tail/mixing arguments.
Key results
- Online CD with decreasing step size achieves O(n^{-1/2}) parametric rate for unnormalized exponential families when MCMC steps m are large enough.
- Polyak-Ruppert averaged online CD has limsup n E||avg psi - psi*||^2 <= 4 tr(I(psi*)^{-1}), i.e., within factor 4 of the Cramér-Rao bound.
- Offline CD (SGD with replacement) achieves near-parametric O((log n)^{1/2} n^{-1/2}) rate under the assumptions of Jiang et al., improving on O(n^{-1/3}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a sufficiently large number of MCMC steps in online CD | Online CD · Unnormalized exponential families, online | parameter error rate: O(n^{-1 / 3}) -> O(n^{-1/2}) | Helped |
| Average the online CD iterates | Online CD · Unnormalized exponential families, online | asymptotic variance: up to a factor 4 the Cramér-Rao bound | Helped |
| Increase the MCMC-step count with sample size under the averaging theorem's condition | Averaged online CD · Unnormalized exponential families, online | computational complexity: O(n) -> O(n log n) | Hurt |
| Strengthen the moment assumption to ν > 2 | Offline CD (SGDw) · Unnormalized exponential families, offline full-batch | parameter error rate: O(n^{-1/3}) -> O((log n)^{1/2} n^{-1/2}) | Helped |
| Use a Markov-inequality tail control instead of the subexponential-tail assumption | Offline CD (SGDw) · Unnormalized exponential families, offline | parameter error rate: n^{ - ((ν-2)ν)/(2(ν²+(ν-2)p)) } + 1/√n | Hurt |
Surprising findings
- Averaged CD incurs O(n log n) total computational cost but still achieves a near-optimal estimator.
Limitations
- Results restricted to unnormalized exponential families with linear dependence on parameters; extension to general unnormalized models left open.
- Requires restricted spectral gap and chi-squared Lipschitz assumptions; constants may scale exponentially in log Z.
- Offline stationary term is only near-parametric (log factor) and its leading constant is not optimal.
Experimental setup
Metrics: convergence rate in n asymptotic variance relative to Cramér-Rao bound
Baselines: Jiang et al. full-batch CD asymptotic analysis Noise contrastive estimation Score matching
Builds on: Jiang et al. CD consistency analysis Polyak-Ruppert averaging stochastic gradient descent convergence theory
Closest papers by meaning
- On the difficulty of unbiased alpha divergence minimization (ICML 2021 · similarity 0.88)
- A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation (ICML 2025 · similarity 0.87)
- Asymptotics of Alpha-Divergence Variational Inference Algorithms with Exponential Families (NeurIPS 2024 · similarity 0.86)
- Demystifying SGD with Doubly Stochastic Gradients (ICML 2024 · similarity 0.86)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.85)
- Robust Diffusion Models via Divergence-Induced Weighted Denoising (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.