We perform a non-asymptotic analysis of the contrastive divergence (CD) algorithm, a training method for unnormalized models. While prior work has established that (for exponential family distributions) the CD iterates asymptotically converge at an $O(n^{-1 / 3})$ rate to the true parameter of the data distribution, we show, under some regularity assumptions, that CD can achieve the parametric rate $O(n^{-1 / 2})$. Our analysis provides results for various data batching schemes, including the fully online and minibatch ones. We additionally show that CD can be near-optimal, in the sense that its asymptotic variance is close to the Cram\'er-Rao lower bound.
Paper
Similar papers
Peer review
Summary
The paper provides a non-asymptotic analysis of the Contrastive Divergence (CD) algorithms, demonstrating their ability to achieve parametric convergence rates and near-optimal asymptotic variance in the online setting. It also shows near-parametric rates in the offline setting, extending previous results. The analysis is applicable to unnormalized exponential families, which, despite their flexibility, cover only log-densities with linear relationships on the model parameters. The analysis also covers various data batching schemes, including fully online and minibatch methods. The study highlights the importance of extending these results to more general models in future work. Additionally, the assumption of $\chi^2$-regularity of the exponential family model is crucial for mapping Markov contractions back to the parameter space. Future research could consider alternative conditions on the Markov Chain Monte Carlo (MCMC) chains, such as geometric ergodicity, to avoid the presence of potentially large regularity constants.
Strengths
**Originality**: The paper provides a novel non-asymptotic analysis of the Contrastive Divergence (CD) algorithm, significantly extending the understanding of its convergence properties. Unlike prior work that focused on asymptotic convergence rates, this study shows that CD can achieve the parametric rate $O(n^{-1/2})$, which is a substantial improvement over the previously established rate of $O(n^{-1/3})$. This originality is further enhanced by applying the analysis to various data batching schemes, including online and minibatch settings. **Quality**: The theoretical contributions are robust and well-supported by rigorous mathematical analysis. The paper meticulously outlines the assumptions required for their results, such as $\chi^2$-regularity, and provides clear justifications for these choices. The comprehensive approach to evaluating the performance of CD in different batching schemes adds depth to the quality of the research. **Clarity**: The paper is clearly written and well-structured, making it accessible to a broad audience, including those who may not be deeply familiar with the nuances of CD or unnormalized models. The authors effectively explain complex concepts and provide a logical flow from the introduction to the conclusion. The distinction between the contributions of this work and previous research is clearly articulated, enhancing the reader's understanding of the paper's significance. **Significance**: The findings have significant implications for the field of machine learning, particularly in the training of unnormalized models. By demonstrating that CD can achieve near-optimal asymptotic variance and parametric convergence rates, the paper provides valuable insights that can influence future research and practical applications. The potential to extend these results to more general models opens up new avenues for exploration and underscores the broader impact of this work. Overall, the paper makes a substantial contribution to the theoretical understanding of the CD algorithm, providing new insights that are both original and significant. The high quality of the analysis and the clarity of the presentation further enhance the impact of the research.
Weaknesses
While I acknowledge that I am not an expert in this specific area, I have some suggestions that could improve the paper towards its stated goals. Although I did not thoroughly check the proofs due to the extensive 30-page appendix, here are my detailed comments: **Experimental Validation**: While the primary focus of this paper is theoretical, it would be beneficial to include an intuitive demonstration of the $O(n^{-1/2})$ rate, if possible. This could help bridge the gap between theory and practical understanding, making the results more accessible and relatable to a broader audience. **Clarity and Structure**: The paper currently presents a substantial amount of theoretical content, which can be overwhelming, especially for readers who may not be deeply familiar with the notation and concepts used. Highlighting the new techniques that significantly improve upon previous work would make the contributions clearer. Consider focusing on one main theorem with detailed lemmas and techniques that build towards it. This approach could provide a more structured and digestible presentation, making it easier for readers to follow the logical progression of the work. **Assumptions and Practicality**: The paper requires a slightly stronger moment assumption (Assumption A4) to achieve better results. Providing more detailed examples and explanations that demonstrate the practical acceptability of this assumption would be valuable. This could help convince readers that the stronger assumption is reasonable and applicable in real-world scenarios. I welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!
Questions
See the weaknesses part.
Rating
6
Confidence
2
Soundness
3
Presentation
3
Contribution
3
Limitations
Yes, the authors adequately addressed the limitations in conclusion part. The paper is theoretical, and I believe there is no need to confirm societal impact.
Summary
This paper analyzes the contrastive divergence algorithm for learning exponential family distributions. Both online and offline versions are studied. The main contribution of this paper is to establish the parametric convergence rate $O(n^{-1/2})$ of the estimator, which improves the previously best result of $O(n^{-1/3})$.
Strengths
Efficiently learning unnormalized model, especially exponential family distributions, is an important problem. Analyzing the CD algorithm is known to be difficult, and this paper seems to establish the best result, proving the parametric rate both in online and offline settings. I like the gentle introduction of the CD in the first three pages.
Weaknesses
- That said, the paper is extremely technical, loaded with heavy notation. Though I am aware of some related works on learning unnormalized models, this paper is hard to appreciate. It is hard to penetrate without extreme familiarity with the previous analysis in the literature and all the optimization analysis tools. I guess this paper could be certainly of some audience, but it'd be great if the authors can provide some more high-level explanations, pointing out some difficulties in the analysis, required techniques, and so on. - In particular, assumptions are not with concrete examples. Can you provide a few examples of exponential family distributions that satisfy and don't satisfy each assumption?
Questions
- Is it proper to say "near-optimality", if this refers to the parametric rate $O(n^{-1/2})$, and it indeed achieves CRLB up to a factor of 4? It's still not efficient due to the multiplicative factor. Is this dependence usually called "nearly optimal"? For example, compared to the NCE estimators, can you argue that what's guaranteed with the CD estimator is provably better in a certain regime? This kind of insights would be very useful.
Rating
6
Confidence
3
Soundness
3
Presentation
2
Contribution
4
Limitations
There is no specific limitation noted in the paper. It'd be very helpful if the authors can provide a comparison of assumptions and attained rates from previous papers to the ones in the paper, side-by-side.
Discussion of proofs, comparision with score matching
In the following comment, we compare our bounds with existing ones for score matching, and provide a high level discussion of the proofs of the theoretical results in the manuscript. **Regarding score matching** The asymptotic variance of score-matching was analyzed in [8], where it is shown that: - Under a Poincaré Inequality, the asymptotic variance of score matching scales as the square of CRLB (times a smoothness term) (See [8, Theorem 2]). - For some specific exponential families, the asymptotic variance of score matching can scale exponentially badly with the parameters of the problem (see [8, Corollary 1]). **Regarding high-level explanation of the proofs** As suggested by the reviewer, to further improve the accessibility of the paper, we provide below a high-level discussion of each result of the main body, and the main proof ingredients used. The overall approach leading the online and offline bounds consists in using non-asymptotic arguments from the convex optimization literature, combined with a control of the bias (and the correlations in the offline setting) introduced by using the CD gradients. While the online setting was not studied in prior analyses of CD, the offline setting was studied in [21]. Our approach significantly departs from [21], which obtained its results by considering constant step sizes $\eta_t = \eta$, thanks to which the sequence of iterates $\psi_t$ becomes a Markov Chain. [21] then obtain convergence by showing the recurrence of this Markov chain in a ball containing the MLE. We now discuss the online and the offline results in more detail. **High level discussion of the online result proofs** In the online setting, the fact that every sample $x_t$ is only used once makes $\psi_{t}$ and $x_{t}$ conditionally independent given past information. Thanks to this conditional independence, the final recursion is free of correlation terms, and we only need to control the bias and variance induced by using CD instead of standard SGD. The lack of correlations allows to obtain an optimal rate of convergence. A fine control of the bias and the variance, as done in Theorem 3.3, allows to show the that the averaged CD iterates are near-optimal estimators. This correlation-free setting also allows to get rid of multiple assumptions compared the offline analysis of [21]. - Lemma 3.1 is a recursion on the iterates describing the distance of of the estimated parameter to the true parameter during optimization. This recursion is obtained by combining standard arguments in the convex optimization litterature (See [22, Equation 16]) with a control of the approximation error due to using the CD gradient instead of the true likelihood gradient. This control uses arguments similar in spirit to [21, Lemma 3.2] although with considerable simplification thanks to the online setup. - Theorem 3.2 provides a bound on the distance of the n-th iterate of the previous sequence, by "unrolling" the recursion. The form of the recursion allows to directly invoke [20] to unroll the recursion, allowing for a very short argument. - Theorem 3.3 provides a bound on $\mathbb E ||1/n \sum_{t=1}^{n} \psi_t - \psi^\star ||^2$, the distance of the averaged CD iterates to the true parameter. The proof consists in adapting the argument of [20, Theorem 3], with multiple modifications to account for the fact that - The CD gradient is an unbiased estimate of a *biased* gradient. Consequently, a different decomposition to the one in the proof of [20, Theorem 3] must be used (l. 1133 to l. 1139 of our manuscript) - The CD gradient contains an additional source of noise coming from from using one MCMC sample to approximate $\mathbb E_{p_{\psi^\star}} \phi$. However (and this is key to our final result), we relate this additional noise to the Fisher Information of the model at the true parameter, which is why the CRLB is multiplied by factor of 4. - While averaging the CD iterates yields an estimator with smaller variance, it induces the accumulation of a bias term, which we can control by scaling the number of MCMC steps with $\log n$. **High-level discussion of the offline results proof** In the offline setting, already studied in [21], the conditional independence structure of the online setting disappears. Instead, the iterates $\psi_t$ are correlated with the data points $x_t$, and these correlations need to be controlled to obtain our final bounds. From a technical point of view, the control of these correlations constitutes the main difference between the online and the offline setting (see Lemma E.2), and requires arguments that are specific to our setting, and not standard in the SGD literature. The rest of the arguments used to obtain our bounds (Lemma E.1, E.3 and E.4) are either adaptations from classical results in the SGD literature, or similar in spirit to the one developed in the online section (with adaptations to the offline setting).
I really appreciate the authors' detailed response. As most of the reviewers raised concerns of its extreme technicality, the paper will be better appreciated by a larger audience, after a through revision as explained and promised by the authors. I'd like to say that the added simulation is also nice, in that it confirms the theory by a simple example. I believe that the authors will do the best in revising the manuscript. I will keep the score as is.
Summary
The paper studies parameter estimation problem in naturally-parametrized exponential families using the contrastive divergence methods, i.e., SGD where the stochastic gradients are estimated via MCMC. Both online and offline variants of the algorithms are considered. Building upon existing works on stochastic approximation, the paper establishes upper bounds on the last iterate and averaged iterate for online algorithms. In the offline setting, the paper establishes a near-parametric rate under certain tail assumptions.
Strengths
Contrastive divergence algorithms have been used in practice, and it is interesting to provide some theoretical guarantees. The paper made solid contribution by proving sharp rate of convergence under various settings. The results provide methodological guidance on the choice of tuning parameters such as stepsizes and Monte Carlo trajectory length. The analysis in the online setting is clean and conceptually straightforward, while the results are strong.
Weaknesses
On the technical side, the results are mostly applying existing techniques directly. The online results are mostly from Bach and Moulines (2011), with a careful analysis of the biases. I'm not totally convinced by the usefulness of the offline algorithm. It seems that the analysis is much more involved and requries additional technical assumptions. On the other hand, the results are weaker than the online setting.
Questions
- Unlike Bach and Moulines (2011), the claim of matching Cram\'{e}r--Rao lower bound in Theorem 3.3 involves an additional factor of 2. I think this is unavoidable because of the additional variance from the Monte Carlo sample. This needs to be discussed more thoroughly. - The writing of Section 4 needs some improvement. The notations are extremely heavy, making the main message difficult to follow. I would suggest simplifying the expression under optimal choice of parameters, and present the main result clearly. The heavy notations can be introduced in the proof sections. Minor comments: - Eq (5). Definition of $\mu$ is incorrect. Strong convexity parameter should be the minimum eigenvalue, instead of the operator norm.
Rating
6
Confidence
4
Soundness
3
Presentation
2
Contribution
3
Limitations
The paper addressed limitations of the results adequately.
Summary
The paper delivers a detailed non-asymptotic analysis of the Contrastive Divergence (CD) algorithm applied to unnormalized exponential family distributions. It significantly advances the understanding of CD by showing that, under certain regularity conditions, the algorithm can achieve the parametric convergence rate of \(O(n^{-1/2})\). This finding represents a notable improvement over the previously established convergence rate of \(O(n^{-1/3})\). The paper's analysis is rooted in a meticulous exploration of how CD's bias and variance components affect its convergence behavior, providing deeper insights into the algorithm's performance under various conditions.
Strengths
- The paper offers a thorough theoretical analysis, providing new insights into the convergence behaviors of CD, particularly highlighting how CD approaches the true data distribution parameters under different data batching schemes, including fully online and minibatch settings. - By establishing that CD's asymptotic variance is close to the Cramér-Rao lower bound, the paper positions CD as a near-optimal method for training unnormalized models, which are prevalent in fields such as image and text processing, protein modeling, and neuroscience. - The introduction of new primal-dual treeplex norms and a novel regret lower bound specifically tailored for sequence-form strategy spaces in online learning scenarios represent significant theoretical advancements.
Weaknesses
The paper focuses heavily on theoretical analysis with less emphasis on empirical validation. Including comprehensive experiments that benchmark CD against other estimation techniques across various real-world datasets could strengthen the claims. The paper focuses heavily on theoretical analysis with less emphasis on empirical validation. Including comprehensive experiments that benchmark CD against other estimation techniques across various real-world datasets could strengthen the claims.
Questions
Could you provide more detailed explanations or examples of the "specific regularity conditions" under which CD achieves the improved convergence rate of $O(n^{-1/2})$? Are there plans to complement the theoretical findings with empirical validations?
Rating
6
Confidence
2
Soundness
3
Presentation
3
Contribution
2
Limitations
The authors listed the limitations and future directions in their discussion section
Thank you for the response. I have read the rebuttal and decide to keep my score.
Summary
This paper studies the problem of finding a maximum-likelihood estimator for an exponential family. The paper proves guarantees for the Contrastive Divergence (CD) algorithm, which iteratively performs stochastic gradient descent on the cross-entropy loss between the estimated model and empirical data distribution. However, each step of gradient descent is performed by estimating the gradient with an MCMC algorithm. The paper proves: * Thm 3.2: Online CD (i.e., using a fresh sample on each step), with enough MCMC steps, leads to $O(n^{-1/2})$ error rate with $n$ samples * Thm 3.3: Online CD with Polyak-Ruppert averaging achieves (up to a constant factor of <= 2), an asymptotically optimal rate. * Thm 4.2: Offline CD (i.e., using a batch of samples at each step) leads to $O((\log(n) / n)^{1/2} + 1/\sqrt{B})$ error rate with batch size B.
Strengths
This paper improves on the results of Jiang et al. [21], which had previously shown a weaker rate under stronger assumptions. The math that I checked appears correct, and the paper is very well written and presented. Many variations of CD (online, online with averaging, and offline) are analyzed. The best rates possible are also proved.
Weaknesses
My main concern is on whether the subject of this paper will be of sufficient interest to a large enough portion of the NeurIPS audience, or whether a different venue/journal with a more statistical audience might be more appropriate. The results of this paper are technical bounds on how CD converges for maximum-likelihood estimation in exponential families; and the CD algorithm is not (currently) a focus of the machine learning community. Furthermore, the rate improvement proved is relatively modest -- from the previously known $O(n^{-1/3})$ rate in Jiang et al. [21] to the current best possible $O(n^{-1/2})$ rate, so to some extent the qualitative nature of the result was previously known. Very minor: * Assumption A.4, which is needed for Theorem 4.2 is stronger than what Jiang et al. [21] assumes (see Remark 4.1). But Theorem 4.2 is stronger than what is proved in Jiang et al. [21]. * The bound in Line 23 of Theorem 3.2 is quite elaborate and difficult to check/use. However, the most important case of $\\beta = 1$ is conveniently solved. * On line 95, the idiom “silver lining” is used incorrectly. It should indicate something positive, rather than something negative.
Questions
* What is $\\tilde{\\mu}$ in Theorem 3.2? Do you mean $\\tilde{\\mu}_m$?
Rating
5
Confidence
3
Soundness
4
Presentation
4
Contribution
2
Limitations
Yes
Thank you for the response. I maintain my current evaluation of the paper, as it is highly technical and covers areas I am unfamiliar with. I believe the paper could be improved based on the current modifications shown in the rebuttal. Good luck to you.
Response
Thanks for addressing my concerns. I appreciate the authors's efforts on improving the presentation of Section 4. I have the following questions: - The drawbacks of online CD (dependence on initial distance, exponential high-order terms) can be overcome by more careful choice of stepsize and tail averaging techniques. These are not discussed and the comparison to offline CD is unfair. - For offline CD, it would be helpful to make it clear what the rate, leading-order term, and high-order terms are, and whether they're optimal. I think there could be a publishable paper here, but the current version looks unclear. So I'll keep my score.
Response to reviewer's questions
We thank the reviewer for their response. We answer their questions below. **Regarding our comparison between online and offline CD, and its fairness**: - First, the bounds provided in our paper are **the only currently existing nonasymptotic bounds for the CD algorithm** (and the contribution of our work). We do not believe that comparing these two bounds (and stating when offline CD is likely to be more efficient than online CD) as done in the paper and in the rebuttal is unfair to online CD. Note that we take into account all step size schedules of the form $Ct^{-\beta}$ in our comparison. - Second, while adapting the guarantees of **other** online unbiased SGD algorithms to the CD setting is an interesting avenue for future work (and we are happy to mention that in the paper), the bounds are **not** expected to transfer without fundamental modifications from unbiased SGD to CD: for instance, the tail-averaging algorithm of [58] (Equation 6a) contains averaging **in its update rule**, which may introduce CD-specific correlations that are precisely the ones requiring a tail control as done in Section 4, and that lead to the additional $\log (n)$ factor in the rate. The rate of such variants may thus be **worse** than (averaged) online CD. Offline CD, as we show, provides a simple optimization algorithm with an optimal (up to a log factor) convergence rate (sharply improving over [21]) and that is robust to multiple hyper-parameters of the problem, unlike averaged online CD. Trying to extend the guarantees of other online SGD algorithms to the CD setting would be interesting for future work, but the absence of such results in our paper does not take away the value of our analysis of offline CD, and its benefits compared to online CD. **Regarding the rates, leading order terms, and high-order terms of offline CD**: all such quantities are given in the current manuscript. The rates (depending on the setting) are given in Lemma 4.3 and Lemma 4.4 of the main body. The leading order terms are made explicit (to keep the main body simple) in Lemma B.3 and B.4 of the appendix. The higher order terms are given in Theorem B.2 of the appendix, but importantly vanish for fixed $n$ as $T \to \infty$. The rate is optimal up to a $\log(n)$ factor, while the multiplicative constant may be improvable. We will mention these points and will make clearer references to these results in the main body. We thank the reviewer for engaging with us and our manuscript. We are happy to answer any remaining questions they may have. [58] ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm, Li et. Al
Decision
Accept (poster)