Near-Optimality of Contrastive Divergence Algorithms
Authors: Pierre Glaser
Kevin Han Huang
Arthur Gretton
Venue: NeurIPS 2024 poster (2024)
Keywords: Statistical Estimation
Learning Theory
Stochastic Optimization
Exponential Families
Unnormalized Models
Primary area: learning_theory
TL;DR: We show that contrastive divergence (CD) algorithms can converge at a parametric rate with near optimal asymptotic variance to the true data distribution.

Abstract: We provide 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 that CD can achieve the parametric rate $O(n^{-1 / 2})$. Our analysis provides results for various data batching schemes, including fully online and minibatch. We additionally show that CD is near-optimal, in the sense that its asymptotic variance is close to the Cramér-Rao lower bound.

Near-Optimality of Contrastive Divergence Algorithms
Pierre Glaser Gatsby Computational Neuroscience Unit, University College London pierreglaserrgmail. com, han. huang. 200uc1 ac.uk, uk, arthur. gretton@gmail.comm com
Kevin Han Huang Arthur Gretton
Abstract
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 Onn-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 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, the sense that its asymptotic variance is close to the Cramér-Rao lower bound.
Introduction
Describing data using probability distributions is central task in multiple scientific and industrial disciplines [ [ Since the true distribution of the data is generally unknown, such a task requires finding an estimator of the true distribution among model class that best describes the available data. An estimator can be characterized at multiple levels of granularity: at the highest level lies consistency [4) a property which states that as the number of available data points increases, a given estimator will converge to the one best describing the data distribution. At a lower level, a consistent estimator can be further characterized by its convergence rate, a quantity upper-bounding its distance to the true distribution as function of the number of samples. A convergence rate can be either asymptotic, e.g. hold only in the limit of an infinite sample size, or non-as aommasyyp,,,ic, in which case the rate also holds for finite sample sizes. In their simplest form, convergence rates are provided in big-O O notation, discarding finer grained information such asymptotically dominated quantities as well as multiplicative constants. These constants play role in the so co-called asymptotic variance of the estimator, which is a precise descriptor of an estimator's statistical efficiency. Convergence rates and asymptotic variances have been the subject of extensive research in the statistical literature; in particular, well-known lower bounds exists regarding both the best possible (asymptotic) convergence rate of an estimator and its best possible asymptotic variance. These results set a clear frame of reference to interpret individual convergence rates, and are routinely present in the analysis of modern statistical algorithms such as noise-contrastive estimation [5 6 or score matching 7 8 9
In this work, we focus on cases where (1) the true data distribution admits density with respect to some known base measure, and (2) the model class is parametrized by finiteddimensional parameter. In this setting, provided that the true distribution belongs to the model class, a celebrated result in statistical estimation states that the model maximizing the average log-likelihood both achieves the best possible asymptotic convergence rate (called the parametric rate) and the best possible asymptotic variance, called the Cramér-Rao bound (see, e.g. [10). While this result shows that Maximum Likelihood Estimators (MLE) are asymptotically optimal, fitting them complicated by computational hurdles when using models with intractable normalizing constants. Such unnormalized models are common the Machine Learning literature due to their high flexibility [2] their weakness however lies in the fact that expectations under these models have unbiased approximation. For this reason, popular approximation algorithms such as unbiased gradient- based
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

stochastic optimization of the empirical log- likelikoi cannot priori be used, as the gradient of the normalizing constant given by an expectation under the model distribution.
The Contrastive Divergence (CD) algorithm [3] is a popular approach that circumvents this issue by using a Markov Chain Monte Carlo (MCMC) algorithm to approximate the gradient of the log- likelihood. Unnormalized models trained with Contrastive Divergence have been shown to reach competitive performance in high-dimensional tasks such as image [14 15 [6], text [17, and protein modeling 18 19,, or neuroscience 100 A consistency analysis of the Contrastive Divergence algorithm delicate, however: indeed, the optimization error e.g. the difference between the estimate returned by CD and the MLE, is likely to be non-nege negligible as compared with statistical error - the distance between the MLE and the true distribution and thus cannot be discarded, as often done when analyzing estimators that minimize tractable objectives 8 5 Recent work [2] elegantly established asymptotic families when using only a finite number of MCMC steps. Key to their argument the fact that the bias of the CD gradient estimate decreases as iterates approach the data distribution. However, as noted by the authors, their work left open the question of whether and under what conditions CD might achieve ((==1/2)-consistenc)
- of the CD estimator for unnormalized exponential
Contributions In this work, we answer this question by providing a non-asympiotic analysis of the CD algorithm for unnormalized exponential families. While existing convergence bounds [21] were derived for the "full batch" setting, where the CD gradient is estimated using the full dataset at each iteration, our analysis covers both the online setting (where data points are processed one at a time without replacement). and the offline setting with multiple data reuse strategies (including full batch).
In the online case (Section 3), we show, under a restricted set of assumptions compared to Jiang et al. (21] that the CD iterates can converge the true distribution the parametric (n-1//2 rate. Our analysis reveals that CD contains two sources of approximation: a bias term, and variance term. These sources are almost independent of each other, in the sense that decreasing the bias by increasing the number of MCMC steps will not decrease the variance. The impact of these two sources of approximation transparently propagates in our resulting bounds: in particular, as the bias of the CD algorithm goes to O, our bounds recover well-knoww results in online stochastic optimization [22]. Finally, we study the asymptotic variance of an estimator obtained by averaging the CD iterates, a classic acceleration technique in stochastic optimization (3). We show that provided that the number of steps m is sufficiently large, the asymptotic variance of this estimator matches (up to a factor 4) the Cramér-Rao bound.
Next, we study the offline setting (Section 4 where the CD gradient is estimated by reusing (potentially random) subsets of a finite dataset. We show that a similar result to the online setup holds, up to an additional correlation term that arises from data reuse, and present several approaches to control this term. We improve over the results of [2] by showing non-asymptotic and near- parametric rate at ((logn)1/2 -12/) under their conditions, and also illustrate how different rates can be obtained under variety of conditions. Our results also show an interesting tradeoff between the effect of initialization and the statistical error as a function of batch size.
In summary, we establish the near-optimality of a variety of Contrastive Divergence algorithms for unnormalized exponential families in the so called "long-run" " regime, where the number of MCMC steps is high enough to ensure that the CD gradient bias is sufficiently offset by the convexity of the negative likeeiiddoood.
Contrastive Divergence in Unnormalized Exponential Families
Unnormalized Exponential Families Exponential families (EF) of probability distributions, given by
24 25
form a well-studied class
(drd)) == e ((z) Z(0) c(dx), 7(5)= = Jx ev o())
(1)
Here, X 3 x is the data or sample space, which we set to be a subset of Rdd for some E N although our results are readily extendable to more general measurable spaces. c measure on X' called the base or carrier measure. When X C Rdd, e is often set to be the corresponding Lebesgue measure. b E V C RP is finite-dimensional parameter called the natural parameter, and Φ Rd - RPP a function called the sufficient statistics, which, alongside with the base measure, fully describes an exponential family. Finally, log ( the log-normalizing (or cumulant) function, is quantity
2

---

ensuring that Pe integrates to 1 over X. Crucially, we will not assume that log (1b) admits a closed form expression for all ạ.. The latter fact provides the practitioner with a great deal of flexibility in designing the model class: indeed, the only requirement that should be satisfied prior to performing statistical estimation to have ( < +o0 for all 4/, something that can be readily verified and is often the case in practice. The drawback of unnormalized EFs is the fact that sampling (and thus approximating expectations under the model) cannot usually be performed in an unbiased manner. Instead, inference in unnormalized EFs is often performed using tools from the Bayesian Inference literature, such as MCMC [26]. Unnormalized EFs belong to the larger class of unnormalized models
7 G. of the form e e- (x) ( c(dr), Z( = f - (((xx))) for some parametrized function Egg 1Rd + IR referred to as the energy. Unnormalized models thus take the flexibility of unnormalized EFs one step further by allowing the (negative) unnormalized log-density to be an arbitrary function Eg of x and vi instead of requiring a linear dependence on 1b as in Equation [ We focus in this work on unnormalized EFs due to the multiple computational benefits they provide, as explained the next section, but we believe that extending our analysis to more general unnormalized models is an interesting avenue for future work.
27
28
Statistical Estimation in Unnormalized Exponential Families using Contrastive Divergence We now review the Contrastive Divergence algorithm, an algorithm used to fit unnormalized models, and our main object of study in this work. The general setting is the following: we assume access i..d. samples (X,,... Xn)) drawn from some unknown distribution p". which we assume belongs to Pg. e.g. p* = Pv. for some v E V. Given these samples, we aim to perform statistical estimation, e.g. find a parameter vi, within V that should approach ui* as n grows.
The starting point of the Contrastive Divergence algorithm is the unfortunate realization that Maximum Likelihood Estimation, which corresponds to minimizing the tross-entropy ((1) = -Ep.. log dp between the model p. and the empirical data distribution P.. 1/n > 6x.- cannot be performed using exact (possibly stochastic) gradient- based optimization, as the gradient (vb( of L with respect to the parameter vi contains an expectation under the model distribution Py- Indeed, the cross entropy and its gradient are given by
(1bb) ((v) - Σ (X,) + E,
= 1 E
= ( & + log (11)
The second line follows from the well known identity V log Z(v) = E,, o; refer to 25 Proposition 3.1] for a proof. The Contrastive Divergence algorithm circumvents this issue by running approximate stochastic gradient descent (SGD) L, where the intractable expectation in V. log Z is estimated using an MCMC algorithm initialized at the empirical data distribution. In more details, given a number of epochs T, a sequence of data batches Brg of size B (c.g. Brr E [1, n] S T, S j S N[n [nnBB)) and a family of Markov kernels {kip, v/ V each with invariant distribution Pv, the jth minibatch of epoch I, V log Z 1) is approximated by 1 ExEB,, (({:),, where XT is produced by running the recursion X. ~ k2, (X, (X 1.), X = =x,
1
up to k = m. Throughout the paper, we will refer to the conditional distribution of X:" given X, as kW (X,,.) .. The resulting gradient estimate arising from combining this approximation with the other (tractable) sum over the data samples present in V ((b). which we refer to as the CD gradient and denote as h, is thus
haj B Eieb., (X,) 1
1B EiEB, ((x')) - E,EE, (0(x)))((3)
(3)
B
Key to the behavior and analysis of the CD algorithm is the strategy employed to generate minibatches Bej- The case where T 1, B = and BI, {i} will be referred to online CD, while the variant where T > 1, and each batch Br, draws B indices (with or without replacement) from [1,n] will be referred as offline CD. In online CD, each data point is present in one and one batch only, while in offline CD, data points are reused across batches. From a statistical perspective, we will see that online CD can be analyzed in a remarkably simple way, while offline CD introduces additional correlations that require care to be controlled. Both settings come with their advantages and drawbacks, as we will see in the next section. The CD algorithms we study will employ decreasing
step size schedules (ne ) of the form 1/: = Ct where C' > 0 is the initial leaning rate and E [0, 1). We lay out online CD and offline CD in Algorithms and 2 Note that our algorithms include a projection step on the parameter space Vi to account for the case where V is compact. In the case V RP, this step can be omitted. Next we depart from the setting of (1] and start by analyzing online CD.
3

---

Algorithm Online CD
Algorithm 2 Offline CD
Input: (X1,.... ......... .1,)..,,,)))) ltd.
Pa-
Input: (X1...., .x,) Ltd. Pe-
Parameters: Model class {pp, sb E v), Markov kernels (kip, v E W). number of MCMC steps learning rate schedule Y = Ct B E 1].
Parameters: Same as Algorithm I plus number of epochs T, batch size B, batching schedule Br.j. initial parameter 40.0
0, initial
for /. = ,,..., do do
parameter 1/0
for j = =....._mmm/
for = I,..., 71 do
[X ~ k (Xi,) for i in Br,jl
//Approx. sample from Po--1
X k (X,,
hr.j 3 BiEB, (o(x)) o ((()i,))
he (xx) d( (
Vt.j f- Wr.j-1 Thhies
Vt.j + (roje(11r.)
the + 1t- 1hlt
end for end for
the Proje (1ht) end for return U'n
return e²r
3 Non-asymptotic analysis of Online CD 3.1 Preliminaries and Assumptions
Recall that the chi-squared divergence between two probability measures and is defined as: (p( q) == S( (z) (dd)) if p < and +oo otherwise. Here, p < denotes that is absolutely continuous with respect and dp/dq is the Radon-Nikodym derivative [29] of p with respect to q. Let (px) be the space of equare-integrabl functions with respect to pa. For function f E (p(),, we define
a(S, v) = (SS Ep. (XW) k dy)) (d
(4)
- (2))p (dx)) (d)))
which is a measure of how quick a Markov chain with kernel by mixes, relative to the function f 33). With these definitions in hand, we state the assumptions required by our analysis of online
CD. These assumptions form a striet subset of the assumptions considered in prior work [1], which required additional regularity and tail conditions on the Markov kernels ky-
Assumption A1. Pv is subset of a regular and minimal (25] Section 3.2] exponential family with natural parameter domain D C RP, V is convex and compact subset of D, and 1p lies in the interior
of V.
Assumption A2. There exists a constant Cx > such that x2 (p Pv) S CRlly 1
Assumption A3. = supfa v), f E for U ( & v 1, where di is the i-th component of the function @ and of the i-th component of the function x -> d(r)².
A well known property of EFs 25 Proposition 3.1] is that their negative cross-entropy (against any other measure) is C convex, and strictly so if the exponential family is minimal (meaning that the set of sufficient statistic functions d; are not linearly dependent). Leaving aside the issue of intractable expectations, this convexity suggests that L can be efficiently minimized using stochastic The compactness of v provided by Assumption A thus ensures, by the extreme value theorem 32 the existence of finite positive constants ja and L defined as:
approximation algorithms [3 22
14 == mingev Amin (V))()) L == max Amax (V (()),
(5)
where V3.C is the Hessian of L with respect th Jr (called the strong convexity constant) and L, (a bound controlling the smoothness of the problem) play critical role in the analysis of convex optimization algorithms [3I]. While it is possible to obtain convergence rates in non-smooth or non-strongly-comee settings, analysis follows the spirit of (2I) by leveraging the strong convexity of the problem to compensate for the bias introduced by using CD gradients instead unbiased stochastic gradients.
Assumption A2 allows link variations in distribution space to variations in parameter space, and will be instrumental to control the bias of the CD gradient. Note that since (2 Po).

---

provided that 2 - 1 E D (see [33 Lemma 1J), we expect Assumption A2 to hold in many cases of interests. On the other hand, the possible exponential scaling of Cx w.r.t log Z suggests that this constant may be large in some instances.
elog ((2 (²) (2 (()) (ogg ((*))
Assumption A3 is a restricted spectral gap condition: it guarantees that the time required by the MCMC algorithm to estimate expectations of 6 and x² under pa will be uniformly bounded. This assumption is weaker than the (unrestricted) uniform spectral gap condition of [21]. which requires that a controls the convergence rate of all functions in L (p Note that standard results in stochastic analysis
34 guarantee that a S 1: thus, it only remains to ensure that a is strictly less than 1. Spectral gaps are strongly dependent on two properties of distribution: their tail behavior and their multimodality. While multimodality poses the risk of pushing the constant close to very heavy tails distributions may not verify the spectral gap condition at all.
3.2 Results
3.2.1 Parametric convergence of online CD
In this section, we show that under the assumptions stated Section 3.1, the iterates ih produced by the online CD algorithm described in Algorithm will converge to the true parameter v at the parametric rate 0n2/) To do so, we follow well known paradigm in convex optimization [22 by deriving recursion on the quantity 6, := E ||v *01 which will allow, after unrolling, to obtain convergence rates for the iterates a/c. We aim to characterize precisely the impact of performing
CD as opposed performing online SGD on L, which would consist of replacing the CD gradient h4 of Algorithm|] by the unbiased (stochastic) gradient, given by:
(v(b) == -(()) + V log ((v)
(6)
which satisfies gx)) = (v The only stochasticity in comes from the sampling of a single data point di from the true distribution, which is unavoidable in the online setting, and
have IE] ( )11 = Tr(Cov の) =: o². of plays a key role in the analysis of Stochastic Gradient Descent [22] We expect that replacing 9r by h, will introduce
sources of approximation: bias term coming from using finite number of MCMC steps m, and an additional variance term, coming from using a single sample z estimate v log (vx)) With that in mind, we derive a recursion on 8, in the following lemma.
Lemma 3.1. Let (We)osisn be the iterates from Algorithm 1 Denote ó; = E 1e 1
o.
(E |1 Ep.. // and oe = (Epv. 11 Epv. )1 Then, under Al
A2
and
A3
for all
t t21 L.
m 6, S (1 21 + 1,20 + 2n 1 + 4a m2 |log 7 211,,00 G25L/2
(7)
where |log 7 000 is constant, imm == / at 0x and ām, == (0? + of 20fa 2m)/22
Lemma 3.1 is proved in Appendix D.2 which details the form of |log _| constant that expect to scale roughly as dL. Loosely speaking, this recursion suggests that as the learning rate 17t goes to O, the two terms scaling in nz will be negligible, in which case we will have: ò; S (1 201 < 8t-1. yielding convergence of 8, to We make these arguments formal in the next theorem. The reader familiar with the convex optimization literature will note the similarities between this recursion and the one derived in (22), which would apply as online SGD on L using 9t- The difference between the two recursions is that the roles of the strong convexity constant μ and the noise a, are now played respectively by
Pm,t-1 11 m 0x and
0 o 0f +
of
20 a
These two modifications respectively characterize the impact of the bias and the additional variance introduced by the CD gradient. The last term in Equation 7 scaling in =²2 Vo,, is residual higher order mixed term coming from relating the variance of the Markov chain sample a:" to of This term can be easily controlled as done next, and disappears as m - oc. Investigating the impact of m in the recursion, we notice that as m > 00, Pmm. + μ.. As we will see later, this ensures that CD will converge for a sufficiently high m. On the other hand, in that same regime, om, does 1/2,
not converge to a., but rather to (oî + = showing the irreducible impact of the variance term.
5

---

While we precisely investigate the impact of the residual variance term in the next section, we now unify o, and or by introducing
σ = Dew 1l Ey, 0/2
(8)
a is an upper bound on the noise induced both by the CD gradient and by the online setup, and was used in prior work [21] Note that by the properties of log Z. o² also equals su tr(V (())),
where tr(A) is the trace of A E Rexp, and thus finite by the extreme value theorem. The following theorem is obtained by invoking standard unrolling arguments in the convex optimization literature.
In the next result, we use the function sp, (t), defined as spy (t) = - if & O, and log t if = O.
Theorem 3.2. Fix n 2 1. Let (We)osisn be the iterates produced by Algorithm ! and define 1xgioCy/u)
5. == E 11v- 1 11. Moreover, assume that m >
log |al L.e. Pim = μ a=O'Ca 0 > 0. Then
under Assumptions Al A2 and
A3
for Ct with C > 0, we have:
2 exx 4IC (I-3R1--2(n)) exp 8n 5
C. 1
(50 + 82
La
+
1C0 Amn 3
if0 $ B <1
exp(2L c*)
500
+
02
27
C
F/m (()) adm C72
if
m
where 7m = 02 +222222mm 2m
+ m/ |log Z Z112,0 Ox and L. = -1.2 m2/221/22 Consequently, if
Th with an initial learning rate C > 2mmm we have Von S 25 CV PaC C-2C-2v + o (1))
Theorem 3.2 is proved in Appendix D.3 It shows that the iterates produced by online CD will converge to the true parameter u0" at the rate O(n provided that the number of steps m is sufficiently large, improving over the asymptotic (13) rate of [2I]. while imposing slightly weaker conditions on the number of steps m (see 22 Theorem 2.1]). This proves that online CD can be asymptotically competitive with other methods for training unnormalized models, such as Noise Contrastive Estimation (6) or Score Matching (7]. However, the asymptotic variance of the
(e.g. the multiplicative factor in front of the On 1/2) term) likely to be suboptimal, e.g. much larger than the Crámer-Rao bound, given by the trace of the inverse of the Fisher information matrix [25. Given the statistical optimality of MLE, and the fact that CD in an approximate MLE method, this motivates the further goal or obtaining a CD estimator with near-optimal statistical properties. In the next section, we achieve this goal by showing that averaging the iterates tht will produce near matistically-optiime estimator, in sense that we will make precise.
3.2.2 Towards statistical optimality with averaging
Dolyak-Ruppers averaging 23 is simple yet surprisingly effective way to construct an asymptotically optimal estimator Vin standard online SGD algorithm [22]. As shown (22). when the objective is the cross-entropy of a
ns - vh from sequence of iterates (v), Joseon obtained by running
model, and assuming the unbiased stochastic gradients available, averaging yields an estimator T with the asymptotic variance tr tr(I(N**))) )/n, where I(bb) = Cov o is the Fisher information
matrix of the data distribution Pa. I(ab+)- being the Cramér Rao lower bound asymptotic variances of statistical estimators [10], this estimator Uh is asymptotically optimal. The following theorem shows conditions under which averaging CD iterates can give rise to near-optimal estimator.
Theorem 3.3 (Contrastive Divergence with Polyak-Ruppert averaging). Let (1/))20 the sequence of iterates obtained by running the CD algorithm with learning rate 17 Ct-3 for B E (2,1). Define
2n = Σn= L/. Then, under the same assumptions as Theorem 3.2 and assuming additionally that m(n)=
(1-8) 8) log n we have, for all 2 1,
2 log al
(E V. -na--1112 0111)1122 s $2 tr(I((+)-t
+ o(n 11/2)
Consequently, we have that lim o0 nB - - 113 4(((I()))-)
Theorem 3.3] alongside with statement which includes the asymptotic order of the residual term, proved Appendix [D.4] It shows that the cost of an increase computational complexity of the entire algorithm from O(n) to Orr log n),, 3n will be a near-optimal statistical estimator of s

---

While this increase in complexity emerges from the bias of CD, the additional variance of CD results an asymptotic variance inflated by factor of compared to the Cramér-Rao bound.
Theorem 3.3 concludes our analysis of online CD. Despite their asymptotic near-optimality, the bounds provided for online CD and its averaged version have weaknesses: the online CD iterates not robust to choices of C. On the other hand, as shown in Appendix DD44, the bound of the averaged iterates contain higher-order terms that could be large in intermediate sample regimes. Next, we show that offline CD, which processes data points multiple times, can alleviate these issues.
4 Non-asymptotic analysis of offline CD
In practice, CD gradient approximation schemes commonly used within offline stochastic gradient descent (SGD) algorithm, where one is given the full size-n dataset upfront and each update uses some stochastic subset of the data. We study CD under offline SGD with replacement (SGDw), i.e. Algorithm 2
with batches BrG being i.i.d. uniform draws of size-B subsets of [n]] and include SGD without replacement in Appendix B3.2 To do so, follow the setting of prior work on offline CD 21, which established its asymptotic O(n -)) consistency. We show that by slightly strengthening a moment assumption used in [21]. the offline CD iterates converge to the true parameter at near-parametric O n rate. Our proof proceeds by controlling "tail strength of the correlations
probability" term specific to the offline setting which characterizes show, the assumptions of [21]
between the offline CD iterates and the training data. While, provide a tail control sufficient to obtain a near- near-parametric rate, other strategies are possible to obtain convergence guarantees. In particular, cither (I) relaxing assumptions on the Markov kernel required by prior work, or (2) making a specific mixing assumption the Markov chain.
show that non-asymptotic convergence can be obtained by
4.1 Background: Asymptotic consistency of offline CD in subexponential settings
Prior work [21] has established asymptotic Onn=$) consistency of the (averaged) offline CD iterates the full-batch case. We summarize their results and assumptions below.
Assumption A4. There exists s.t. for all E N, there Kumm < s.t.
SuPRex supwev (E| (x)) Blo(KT
((o(KT(<))])"" (+)))))))
S Kurm
Assumption A5. There exists some Cm 0 such that, for all 1/ 1/2 E V, supeeex [|[[((K]] (x))]-
Blo(K 02 (=))]l Cm 4/2ll-
Assumption A6. There exist some am, Sm > O such that, for any E R with ||||| < Gm. Ele² (o(KT) (x.)) (xxi)ll) I 1
Theorem 4.1 (Theorem 2.1 of (21). Assume assumptions AZ A3 A4
(for 2), 2) annd Let
Pe, be the 1-th iterate of offline CD with full-batch gradient descent and constant stepsize T = C.
ie the iterates produced by Algorithm 2
Jusing Br, = =[1, [I. Then for any learning rate C and
O. we have, for number of Markov kernel steps satisfying μ a amoox G (L+ some Am > O,
Amn Amn )
lim I lim sup 10000
limsup T-400
SGDW Vi1
This result shows convergence of the averaged full-batch CD iterates to the true parameter in the large n and T' limit. As discussed, this result is asymptotic both in n and T: the probability of the error exceeding A, goes to as n + oo and T + oo, but at an unknown rate. Moreover, the O(n" 1) does not match the optimal O(n rate.
4.2
Sharpening offline CD bounds in subexponential settings
4.2.1
Non-asymptotic Ö(n -
As first result, show that under the assumptions of (1 (except for slightly stronger moment assumption in A4D, SGDD in fact achieves a near- peramparaeetric rate. The most general version of our result holds for any learning rate schedule of the form Ct- 3 [0, 1], and for offline SGD
7

---

with arbitrary batch sizes B. with data drawn either with or without replacement across batches. For simplicity, we first present our result assuming full batch (B n,
1, v/.. Si
vi,1 JSGDD for
t 2 1) SGD with constant step sizes 1/t- C, which is the setting of [21]. Analogue bounds holding for the other mentioned batching and step sizes schedules can be found in Appendix B
Theorem 4.2. Assume the setup of Theorem 4.1 except that Assumption A4 holds for some v >
and that P.
5SCDw = El a a² 4CT.2 Let 01,)
Then, we have:
imc
BSGDW
SSDD 0,0
+ C' m, 4)
Vlogn vn
+
(9)
Cm
L2C
where E Eg are functions decreasing exponentially in T, and C"(p, U, n,m, V) is a constani in n, T. Consequently,
E
CD,, V v. Vlogg 1 vn
lim
SSGDW T.1
BanC
vn
The precise values of all the constants can be found in Theorem B.1 (for ETT E and Lemma B.3 (for C"(p, V, m, V 3),, including their expressions for N > and 3 E [0, 1]. We comment on the main differences between our result and the one of [2]]. First our bound holds for any epoch T and number of samples n. Second, fixing n but taking T + co, the final bound matches the parametric O(vn) up to a /log(n) factor, significant improvement over the O(n rate of (2T). Finally, we control an T.2 error, which a stronger control than high probability bound by Markov's inequality; we hypothesize this is the reason why slightly stronger moment assumption is required for our setup, compared to the one used for the high probability bound 21
Inspecting Equation 9 we notice the presence of two transient terms, and a stationary term, reminis- cent of the structure of upper bound of Theorem 3.2 The transient terms (i.e. the ones containing Ex and E " vanish exponentially fast in the total number of CD updates T. However, unlike in online CD where the number of updates and the number of samples are tied (e.g. T = n), these two values are now decoupled, and these terms can be made arbitrarily small by increasing the number of gradient steps T without having to collect more samples n. The stationary term, which is the only one remaining in the limit of T + oo, decreases with n at a rate that is independent of hyperparameters like the step size C' or the learning rate schedule 3 (see Lemma B.3). In that sense, offline CD compares favorably to online CD, whose rate is sensitive to B and C, and averaged online CD, whose bound contains higher-order (in n)) terms which can be large in the moderate n regime. On the other hand, the stationary term in offline CD is asymptotically suboptimal: its rate is larger (while only up to log factor) than the best-case O( (Vn) one achieved by online CD algorithms, and the leading constant does not match the optimal one.
4.2.2 Proof of Theorem
The high-level proof of Theorem 4.2 follows a similar strategy as the online one: first, derive a recursion for the quantity DS El
112 then unroll it explicitly to obtain a final
bound on 85.1 8SGDw The main difference to online CD the presence of an additional offline-specific correlation between the iterates and the data. We thus break down the proof into three steps: (1) deriving a controllable, uniform-in-time upper bound of the data-iterate correlations, (2) deriving and unrolling a recursion on 01 final bound on 67,1 8SGDw.
8SGDw containing this new term, and (3) controlling that term to obtain
Step I:characterizing the data-iterate correlations in offline CD In offline CD, at each epoch t > 1. the iterate wSGDD and the data samples X, are correlated: this is because these samples may have been used in previous epochs L'
1 to obtain the v.s which themselves influenced 4/1-,11- With such correlations, we now have (P, (SSCP)) * PPX)),, preventing us from obtain- ing an unrollable recursion on dSGDw by first marginalizing X; out to obtain upper bound of SGDW .0 [[oSCDW] that only depends on ||DD - - and then marginalizing over w 1-111 to obtain recursion as in Lemma 3.1 As this problem would not have occurred had we used "fresh samples" (e.g. i.dd copies of X; not present in the training data) to perform our update, the
E Pt.l
SGDw
8

---

core of the proof lies in controlling the following quantity:
A(e = Eiss (E
K Berio (X.))
42,1 SGDW x.] - 18 B[ K kegeoa (X1))
where X is an i.idd. copy of X1. A ( is the expected (over the data and iterates) emror between a quantity that allows to obtain a recursion (the rightmost term) and the one actually used by offline CD (the leftmost term). To control it, we upper-bound it using a tail decomposition:
SGDW )31 $ 2 +sup E|A 11,1 B[A (v/7.1
SGDW) (SSDDwy y1)2// sup (A (1,1
>
c)
SGDW Cn.m T: (c)²
(10)
We invoke an additional assumption to ensure that (E A 1 21]. this is automatically implied by assumptions A4 bounding constant Kigqm-
SSDDSGDW))) (T) is finite; in the results of
and A6
For simplicity assume the same
Assumption A7. There exists 2 2 s.t. for all E N, Kumm from A4 moreover verifies
supeew (Bl (X1)) (K (x (XI)III
S &kpmm
Note the similarity of this assumption with assumption A4 the only difference is that X1 is now random training point instead of an deterministic (arbitrary) one. Ensuring assumption [7 in addition
to assumption A4 thus requires controlling w-th order moment, instead of all moments as implied by assumption A6
Deriving and unrolling the recursion on oi The right-hand side of Equation (10) does not depend on t, allowing for the derivation of an "unrollable" recursion on D and its subsequent unrolling, which is performed in the following theorem. For simplicity, we again assume and N = and defer the general case to Theorem B.I appendix.
Step 2:
Theorem 4.3 (Convergence up to a tail control), Assume A7
A2
A4 and A7 Then for any >0,
A3
Let 1nt = C.for
some C > 0, and assume thut Pmm = p - amaaCox >> 4CT."
DSGD
SE. SE..
BSGD V00,0
+ C
SSDD ( (=n +
5a + 5mam
Aay
ET.
vn
PmC
I2C2
where T.., (c) is defined in Equation d0
Note that the general, non-full batch B S n case,
30 is replaced by 50 vn
(see
vB
Theorem B.I. Under our bounds, obtaining consistency thus requires setting B = B(n) +o0.
Step 3: Controlling the tail probability term Theorem 4.3 is just one step away from the final
bound of Theorem 4.2 remains to control the tail term x,,, (c). Under the assumptions of 21 minimizing gSGDw "n,m,T: (E) over e yields the following result:
Lemma 4.4. Assume the setup of Theorem 4.2 Let n E N be sufficiently large s.I. log
o
Denote T as the radius of the smallest sphere in IR that contains V, which is finite under Al
Then
inf i e>0 v..,rr I
30m Dolvpl(e 2)p + 2v) + Kygm 2 2x
(rw)
(v 2hx 20
(1
20m 2/
2)y
Vlog /n
VV-
0mpl/2((v 2)p 2/)3/2
To obtain this result, control the moment term (sup, (UA(UDDDW))) using A7 and control the tail probability term sup, (AA(( (GGD)) > e) as in 21 Lemma 3.1] using an union bound, covering argument and A6 Theorem 4.2 then follows by plugging Lemma 4.4 into Theorem 4.3
4.3 Consistency of offfine CD: beyond subexponential tails.
As discussed above, the general unrolling result of Theorem 4.3 holds without the subexponentiality assumption A6; this assumption was only used Lemma 4.4 to control sSGDw (e). 7. (e). We now discuss two alternative ways to control this quantity without requiring subexponential tails. The first generalizes the idea of Jiang et al. (21), while the second exploits mixing of the Markov chain KT (x)
as m - co. As before we only state partial results (full batch, = and defer the full explicit bounds to Appendix B.3

---

Control via Markov Inequality Our first alternative uses Markov Inequality to yield the following. Theorem 4.5. Assume the setup Theorem 4.3 and additionally that A5
holds. Then
(2-2)p
inf e00
vym.m, (c) S &C,, V)
2 +
(r 21n +10
lim T
SSGDW T.1
S (p, (n
where Ö and Ò' are functions whose explicit expressions are given Lemma B.4 in the appendix.
In the case p 1 and 3, the sub-optimal error from Theorem 4.5 reads On 3/20). Theorems 4.2 and 4.3 reveal that, depending on the tail condition imposed on the noise introduced by the Markov kernel, the convergence rate of offiine CD varies: A subexponential tail, assumed in prior work, in fact leads to near pear-parametric rate. Meanwhile, consistency can be obtained without assuming subexponentiality albeit at sub-optimal rate.
Control via Markov chain mixing. Alternatively, notice that IE| A (1 (WGDDW)) involves an average
( [e When m - oc, the effect of initialization vanishes, and one may expect the difference to converge to zero. We defer to Lemma B.5 in the appendix to show that, under d-discrepancy mixing condition (35) with a mixing coefficient E [0, 1).
of E ( Wa (X X,,, (t, wifiii] - E [o Kysgow (X1))
We,
inf e SGDw <>0
vmnm,r O (or- 20m 30-2
and
lim T-
ESCD T,1
0 Kygm 10-2
(o 2)m
As oc, this recovers the parametric rate O/n-1/2). This alternative convergence guarantee comes at the cost of requiring m, the number of Markov chain steps, to grow with the sample size n.
Remark (Examples). In main results (Theorems 3.2 and 4.3) and the tail condition for offline SGD (Theorem(42) we employed a weaker set of assumptions than those [2] (except for the mild moment assumption in (A4) Consequently, our results apply to all three examples studied in [11]: A bivariate Gaussian model with unknown mean and random-scan Gibbs sampler, a fully visible Boltzmann machine with random-scan Gibbs sampler, and an exponential-family random graph model with a Setropolis-Hastingg sampler.
5 Related Work
Central to this paper is the prior work of Jiang et al. [21, which provided a rigorous theoretical foun- dation to analyze the convergence of full-batch CD, and which we refine. The study of optimization with biased gradient descent has attracted lot of attention in recent years [36 37
38 39 These
works, while closely connected ours, analyze algorithms with different implementation choices than the CD algorithm: i.i.d. noise setup [36. or setup where a persistent Markov chain is maintained
through the iterations [36. 37
38, 39 The latter is akin to a variant of the CD algorithm, called the persistent CD 44).. In contrast, our analysis focus on the CD algorithm that restarts a batch of Markov chains from the data distribution at every iteration. Finally, there is a rich body work on 46). A notable difference of our analysis is that we are primarily concerned with statistical errors associated with convergence to the true parameter 2 in number of samples n, and not the commonly studied convergence rate in number of epochs T. Consequently, most of our work for the offline setup goes into handling the correlations that accumulate by reusing data across epochs.
convergence guarantees for offline multi-par pass SGD [4] 42 43
44 45
Discussion
In this work, we provide a non-as non-asymptotic analysis of the Contrastive Divergence algorithms, showing, in the online setting. their potential to converge the parametric rate and to have near-optimal asymptotic variance, and proving a parammeeit rates in the offline setting, significantly extending prior results. Our results apply to unnormalized exponential families: despite their flexibility, these models only cover log-densities with linear relationships on the model parameters. We believe that extending our results to more general forms of unnormalized models an important direction for future work.
10

---

Acknowledgments and Disclosure of Funding
All authors acknowledge support from the Gatsby Charitable Foundation.

---

References
[1] Kyle Cranmer, Johann Brehmer, and Gilles Louppe. The frontier of simulation-based inference. Proceedings the National Academy of Sciences, 117(48)33055533000 2020.
[2] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning. pages 8748 8763. PMLR, 2021.
[3] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[4] Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
[5] Holden Lee, Chirag Pabbaraju, Anish Prasad Sevekari, and Andrej Risteski. Pitfalls of gaus- sians as noise distribution nee. In The Eleventh International Conference on Learning Representations, 2023.
[6] Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, 2010.
[7] Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 2005.
[8] Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical efficiency of score matching: The view from isoperimetry. In The Eleventh International Conference Learning Representations, 2022.
[9] Chirag Pabbaraju. Dhruv Rohatgi, Anish Prasad Sevekari, Holden Lee, Ankur Moitra, and An- drej Risteski. Provable benefits of score matching. Advances in Neural Information Processing Systems, 36, 2024.
[10] George Casella and Roger L Berger. Statistical inference. Cengage Learning, 2021.
[11] Nicolas Le Roux and Yoshua Bengio. Representational power of restricted boltzmann machines and deep belief networks. Neural computation, 20(6): 2008.
[12] Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. Advances Neural Information Processing Systems, 32, 2019.
[13] Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 2002.
[14] Erik Nijkamp, Mitch Hill, Tian Han, Song-Chun Zhu, and Ying Nian Wu. On the anatomy of meme-based maximum likelihood learning of energy-based models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
[15] Erik Nijkamp, Mitch Hill, Song-Chun Zhu, and Ying Nian Wu. Learning non-convergent non-persistent short-run meme toward energy-based model. Advances in Neural Information Processing Systems, 2019.
[16] Yilun Du, Shuang Li, Joshua Tenenbaum, and Igor Mordatch. Improved contrastive divergence training of energy- based models. arXiv preprint arXiv:2021.01316. 2021.
[17] Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. Cold decoding: Energy-based constrained text generation with langevin dynamics. Advances in Neural Information Processing Systems, 35:9538 9551, 2022.
[18] Deqian Kong. Bo Pang, Tian Han, and Ying Nian Wu. Molecule design by latent space energy- based modeling and gradual distribution shifting. Uncertainty in Artificial Intelligence, pages 1109-1120. PMLR, 2023.
12

---

[19] Csilla Varnai, Nikolas S Burkoff, and David L Wild. Efficient parameter estimation of general- izable grasse-rained protein force fields using contrastive divergence: a maximum likelihood approach. Journal of chemical theory and computation, 912): 18-5778 2013.
[20] Pierre Glaser, Michael Arbel, Arnaud Doucet, and Arthur Gretton. Maximum likelihood learning of energy-based models for simulation-based inference. 2022.
[21] Bai Jiang, Tung-Yu Yu Wu, Yifan Jin, and Wing H Wong. Convergence of contrastive divergence algorithm in exponential family. The Annals of Statistics, 4666A):3067-3098, 2018.
[22] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems, 24, 2011.
[23] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal control and optimization, 30(4):838-8555 1992.
[24] Lawrence Brown. Fundamentals of statistical exponential families: with applications in statistical decision theory. Ims, 1986.
[25] Martin J Wainwright, Michael Jordan, al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008
[26] Charles J Geyer. Introduction to markov chain monte carlo. Handbook of markov chain monte carlo, 201 1602::45, 2011.
[27] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and Fujie Huang. A tutorial on energy- based learning. Predicting structured data, 1(0), 2006.
[28] Yang Song and Diederik Kingma. How to train your energy- bassed models. arXiv preprint arXiv:2101.03288 2021.
[29] Joseph L Doob. Measure theory, volume 143. Springer Science & Business Media, 2012.
[30] David Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[31] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[32] Gary Harris and Clyde Martin. Shorter notes: The roots of polynomial vary continuously as a function of the coefficients. Proceedings of the American Mathematical Society, pages 390-392, 1987.
[33] Frank Nielsen and Richard Nock. On the chi square and higher-order chi distances for approxi- mating f-divergences. IEEE Signal Processing Letters, 21(1):10-13, 13, 2013.
[34] Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
[35] Maxim Rabinovich, Aaditya Ramdas, Michael I Jordan, and Martin J Wainwright. Function- specific mixing times and concentration away from equilibrium. 2020.
[36] Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi- To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference Learning Theory, pages 1944-19744 PMLR, 2019.
[37] Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. Advances in neural information processing systems, 31, 2018
[38] Thinh Doan. Finite-time analysis of markov gradient descent. JEEE Transactions on Automatic Control, 68(4):2140-215: 2022.
[39] Yves Atchadé, Gersende Fort, and Eric Moulines. On perturbed proximal gradient algorithms. Journal of Machine Learning Research, 18(10):1-33, 2017.
13

---

[40] Tijmen Tieleman. Training restricted boltzmann machines using approximations to the like- lihood gradient. In Proceedings of the 25th international conference on Machine learning. 2008.
[41] Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
[42] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference machine learning, pages 1225-1234. PMLR, 2016.
[43] Junhong Lin and Lorenzo Rosasco. Optimal rates for multi- pass stochastic gradient methods. Journal of Machine Learning Research, 18(97):1-47, 2017.
[44] Loucas Pillaud- Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. Advances in Neural Information Processing Systems, 31, 2018.
[45] Nicole Mücke, Gergely Neu, and Lorenzo Rosasco. Beating sgd saturation with tail- allerreggg and minibatching. Advances in Neural Information Processing Systems, 32, 2019.
[46] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Risk bounds of multi-pass sgd for least squares in the interpolation regime. Advances in Neural Information Processing Systems, 35:12909-12920 2022.
[47] Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703 4711. PMLR, 2019.
[48] Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of sgd without replacement. In International Conference Machine Learning, pages 7964-7973. PMLR, 2020.
[49] Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009.
[50] Martin J Wainwright. High-dimensionul statistics: non-asymptotic viewpoint, volume 48.
Cambridge university press, 2019.
[51] W. Dharmadhikari, Fabian, and K. Jogdeo. Bounds on the moments of martingales. Ann. Math. Statist., pages 1719-1722 1723, 1968.
14

---

Supplementary Material for "Near-Optinality of Contrastive Divergence Algorithms"
The supplementary material provides the proofs of the main results of the paper:
Section
B
states full explicit bounds the offline CD algorithm.
Section collects a list of useful tools for our proofs. These include the properties of by introduced before heorem 3.2 in the main text, as well several contraction and integrability results.
Section D provides the proofs for the online CD algorithm.
Sections and
G contain the proofs about the offline CD algorithm and the tail control.
A
Notations
Throughout the proofs, we will denote by p the following operator from (p²))) to itself:
(1 PT f()) = (' ('(e)))
(11)
Here, kTT x²) is the m-iterated version of some Markov transition kernel ky, e.g.:
Ke (2,,²))=
xm-1) k. (2m-11 x' )dæı dmm-1
(12)
Proje: : :R >> denotes the projection operator onto the convex set V e.g.
Proje (v) argmin
|/ v/
NeW
We also frequently the following function, used in standard convex optimization results 22
C-1
i 0
(t) =
logt
if 0
which is defined on IR,, (0).
Additional results for offline SGD
In this section, we provide the full statements on error bounds for SGD with replacement (SGDw), SGD with reshuffling (SGDo) and tail moment bounds, which complement the results in Section 4 Proofs are deferred to Appendix F which make use of L2 approximation by auxiliary gradient updates derived in Appendix
Denote the SGDw iterates by (v) JINNEEN and let X be an i.i.d. copy of X1. Throughout the remaining of the appendix, define given >> 0 and E NN
Notations
E (B(el (oapp (x.) Xx, v
SGDW]
B Blol
Km "SsD (Xi) w 1)Il
SSDD (c):
sup P LE[T]
1-11
> g.
JEIN]
sup P (AA (b
SGDw) > E)
and n.m.T T
SGDw (c) analogously. Using these notations, we can redefine the quantity Enm,
(c) in the
SGDw (e) Ve2 2 + 22.m (USGDar main as (ar
15

---

B.1
An explicit simite-sample bound for SGDw
In the result below, write DSGDw = E |
0,3
w011 and, for fixed > O, the quantity
SGDW O n.T
SGDW -n,m,T:: (c) +
5a + 5km
Ve
e + 12n
+
5a + 5tmm
VB
vB
Theorem B.1. Assume A1 (where V may be non-compact),
A2
A3
A4
and
A7
Let tJs Ct- for
some 3
[0,
1] and C > O, and assume that m
log(aC log
s.1.
pmm
1
a o00 > 0 as in
Theorem 3.2
Then for any e > 0,
/
/SGDD is upper bounded by
PMCN (e 13
E
SSGDw
Co
+ +NN + 1m. - (I+ E
())
0,0
for B 2
E T.N
SSDD 0,0
+ CC
4
3N(1
1223 N-1 22 log(T 11)
for B = 1
PmC
(T 12
EN,N
Co
(228+1
ane 200- (211))
31 Pm M 2) ET,N) otherwise
0,0
AmC
L2C
where E T.N and Fny T.N are two decreasing functions in T defined by
91 29 + 1)) Nim + 1)+ NE²C²
E ET, = exp
E = exp
(-
Nem C + 1) - +
2 91-0
We emphasize that the full result above holds for any 3 E [0, 1], which in particular includes the constant step size / = 0 regime considered by [2I]. When 3 = 0, for E Ef"'" and E to decay to zero as T + oo, additionally need the condition
im
am oCx > 4CL
This is almost identical to the condition used in [21 Equation 2.5, Theorem 2.1], except that 4L gets replaced by 1 (L + a" oCx)². Notably this says that an additional step size condition needed for our results to hold in the constant step size regime, but not necessary for decreasing step size.
B.2 Results for SGDo
SGD with reshuffling (SGDo, also called SGD without replacement) an optimization scheme that also widely used in practice compared to SGDo and online SGD. In the context of CD, it corresponds to Algorithm 2 with batches chosen as
(B,,,.. Br,N) TT -(I,...,
where n is uniform draw of the permutation group elements. We denote the iterates of SGDo (WSGDo) (te JoeN, JE[N]- Analogously to gSGDy, we define, for X1 an i.i.d. copy of X1, and E N, n.m.?'
the tail probability term
E (ι[σ(x
km scpp (X.) N1, X.. w.ppa
Km popp. (x1) (
spapy
(c) sup P
n.m.
TE[T]
JE
Also denote SGDo (c)
SGDw 2 R2 (DSGDo (c)) and o n.
SGDo 6nm, T. (c) + 5mm
B
The following result says that y SSD enjoys exactly the same convergence guarantee as v SGDo in Theorem 3 The statement is identical to that of Theorem B.I and is stated in full for completeness; see Appendix F2 for the proof, which is slight adaptation of the proof for Theorem B.I As before
write SSDo = E SSDD =b+
16

---

Theorem B.2 (Convergence of CD-SGDo). Assume A7 (where Vi may be non-compact),
A2 A3
A4 and
A7
Let ?e Ct for some 3 E 1] and C O, and assume that
log C / log ca
s.l. Jim
a xxx > 0 as in Theorem 3.2
Then for any 0, V ( is upper bounded by YT,N
17777377
E
NN
(SGDo 0,00
+ So
21 + Pm C) P + E
Rm
for 3 =
3N(1+ 2 N-1 22 log(T'+ + +1)
E ET.
SSGDo 0,0
+ Co
SCDo
4
+
for 3 = 1,
Am
(T 1
ET.N
0,0
DSGDo
+ Co
226+1
20
(3+1)3
+ 39 Pm (T + 2)
Fig F..
otherwise.
CmC
I?C²
where E
ENN and E ET.N are two decreasing functions in T defined by
E = exp
NL 1P
(T + 1))
E. = exp
(- Npm C
91 1)) 2NL + +1)
Remark. We also remark that existing works 47 48 show that the standard SGDo typically gives
faster convergence rate in T than SGDw. An analogous result for the CD setup would involve additional technical hurdles of jointly controlling the correlations across minibatches and from reusing data samples, and we defer this to future work.
B.3 Explicit tail control
We now provide the full explicit tail control bounds. All results in this section hold directly for 2SGDo (c) (c) Cun.m,
SCDDo and we omit them here. In the result below, we denote as the radius of and TNN the smallest sphere in R' that contains V, which is finite underA]
Lemma B.3. Assume A5 and A6
Let N be sufficiently large s.f. log <
22 p4o-2
Then
inf SGD <20 umm.m,
7(c) S
30 v plVv - 2)p 2v)
20 (rv) (v-2h 2ly (1 (1+ pmp
20m(u 2)1/2
(v-2) 2v
v Mlg
+ Kugm
Vv
ampl/2((
2)p + 2/
Vn
In particular, if we additionally assume the conditions of Theorem B.
we have
lim T
SSGD
& C²,, n.m, v 4)
Vlog n vn
T.N
VB
where
8(1 + 50 + 5kim)
C,,, V
30 v Dolu 2)p 20
1v-2ip 20 (r
(1+
20 2)
(v-2)p 2)e
2
//ppt/(((v 2)p + 20)
Lemma B.4. Assume the conditions of Theorem 4.3 and additionally that A3 holds. Then
inf SGD e>0 (p)m, < (3Cm + 2/2 (ra)
(v-2)p
Cm
2-2
(0-22p
n
20
2
lim (GGW 1/2 T-000
< Ō' u, M. ()
20
(w- 2)v
+ 112))
where
C'(,,u,,,V)
8(1 + + 58mm
(3Cm + 2/22 (rw)
C.
um2 (w-21
Pm
17

---

The next result considers a o-discrepancy mixing condition ((35), which is mixing assumption on K but with respect a specific test function @, and we impose it uniformly over & E V. We also recall that X1 Pip
Lemma B.5. Assume that there exist ā E [0, and CK > such that, for all vb E and x E X, [ (x)) - E[o(X)))| I Cxâ Then
inf.>o m.
(1+2 Kyom (ŌK)
30-2
In particular, if we additionally assume the conditions of Theorem 4.3 we have
lim T-000
T,N
DSGDW
S
8
(1+
v=2 Kymm (Cx)
4-2
(2-m)mm 30-2
+
/B
C Auxiliary Tools
C.1 Properties of ipy
The following lemma collects some identities used in [22].
Lemma C.I. ipy satisfies the following properties:
(i) Py is increasing on R4 for all y
(ii) (t) s - for y O, and (t)(t) S - for y < 0
for
(ii) (1-a(1) 2 11 for 3 E (0, 1];
(iv) (t) (g) 2 1 for 7 (0,
The next lemma provides some additional results on (P- Lemma C.2. iyy satisfies the following properties:
(i) Py is positive on > O and increasing for every 7 E IR;
(ii) For 1 S 11 S l2 and 2 O, we have
f1- 1) -1 ((t)(tt) S Et.,, t- s 2 ( + 1) -
If instead B < 0, we have
2 (P1- + 1) - (t1) S 2ihh t-8 s 91-0(11 1 9 -
(ii)) For 151 S l/ and 7 + 0, we have
f $ (t) (t1) s f
1f 1, i1
53 (1-1) (1) (ti) 1- (111)
(iv) Let St < 22 and k, 2 0. If + 1 and a > 0, we have
En (t + 1) 3 exp (a 1t 1)) <
(t2 1)
exp (ap1-x(tz + +))
and if + and < 0, we have
(t2 + 1) 8,0)
Σ 1/ (t (1+1)) exp (a)1-a((t)
<
exp (ap(aap1o))) (I
(-a)
Proof of Lemma C.2 (i) follows from checking v > 0, = and y < 0 respectively. The first set
of bounds in (ii) follow by noting that + - is decreasing for 3 > 0:
E9,, 3 2
l2
1--1 - p1-0(tz + - (0--11ts(tt)...
4
B < 2 2/ 1=
11+ < $2 2 11-
(l (1+1) 1 - = 2(p1-1((12 + +1) (11-((11))
18

---

The second set of bounds follows from noting that t + tー is increasing for _ < 0:
E ti 8-
f2
1 22
(t+ 11+
$ > 1/2
(t+ Adt [ +1 (1-0((1))
2
2 4-
Els 1-8 1 J
12
Pd p1-1(12 + 1) - 9111((1))
For (iii, we note that for y + 0,
1/ -1
- (((6))-9yl))
7
so by the mean value theorem,
inf t Sesta 8711 S (12) - (1) S suPrseet, 1711
The desired bounds then follow from an explicit computation of the infimum and the maximum in each of the two cases y 2 and y I 1.
For (iv), we first consider the case k # 1 and a >> 0. Then
l2 Eiee (1+1)- exp (1 - 1)) = e T Ete,, (1 (1+1)- exp
l2
(att~a (
(1++1)²)
>/ >i=e, (t+ 1) exp aat 1- - (t + exp aat-~>
S e - maxt, SiSts
(1+1)/
S (12 + 1) m)max((-880 3,0}
exp
Since, for x 2 0, + (x + 1) 1)-* is decreasing and x + exp(ar 1 - /(1 - x)) is increasing, we have
that for 1 S S 22 and x E [t, 1).
(++ S x x
and
exp(att>x/(1 k)) S exp(act~* 111 ki)
This implies that
Exn, (t + 1)- exp (a (t- 1])
[+]
(az!-M)
S (tz + 1) B,00 e - _
x x=
exp
dx
1-
= (12 + 1) jjmxxf -8,00 0.00 - 1ttp
(axt~x
x cxp
1- dc
(12 1) m)
alta+112
E e
(l2 m) 2.0)
exp (a + 1))
The main difference in the case + and < is that we now use x + exp(a(x + 1)2- 11) decreasing to obtain, for 1 S 1 S L2 and x E (1,++1) 1].
/(1 k))
exp(a(t + 11) /1 ((1-)(1))))))))))))))))(()))
k)) k)) s
xi)
A similar argument then yields
Ei., (1 1)+ exp (x)))x(())
< (tg + 1) m)x (x- 3.0) e 1 Eie (t (1+1 1) exp
(a(t (a(++1) 1)1-1
1-
S (12 + 1) max - { platz x exp exp
aax aaxt
dx
(12 + 1)maxfa-8.01
(exp (a:1-x + 1)) - exp
(a<11xx(t1))
(t2 1) ( 2,01
exp (a (11xx(11) (11))
0)
19

---

We also need the following lemma, which is useful for controlling the accumulation of errors from the noise terms over iterations.
Lemma C.3. For any a, b 2 O, E NN and K, B 2 0 such that bt -8 -at S 1or all St we have that
bt bt (1- IT (1 -1---6
+ at a) S exp ( (- (I aN -I (T++)
Moreover, for any Ç 2 0, we have thut
N Σx 1- Eymm (1 bt + at at=*))
II T -1, (1 bs 8 + as "M
- bN
I Q1 + exp
P1-3(T + +1) + 4a (T Q2
where
(T 3)
bN
exp
2(1 ()( 1)8)
f8
Q1 =
b
2 2N exp
bN
91 (T P1=
If = lorb = 0,
and
36 a0 N1 (T - 2) 2))xax(x-
ifk + and >> 0,
Q2 =
2a
2N + a)N- P1-c-2aN(TT
ifx a
In the special case ( ( B 1 < k. have
T Eta1+ 5- |2/=11 (1 b + agj-1)
II -1 - as x
N- 4uN
3N(1
log(T 11)
<
(1+1)
Proof of Lemma C3
By assumption, bz- at- < for all 1 <t T. Since S - x 66 for all x < we have that for any 1 1.t 52 ST
IT' (1 - bt + at RRN z exp
(- 6N E'e, 8 + aN Ete, (-))
(13)
Applying this to the first quantity of interest followed by noting that a, 2 0 and using Lemma C.2 ii), obtain the first bound that
II_ (1 -t- B + at NON s exp
- bN -N 1- 8- +
T aN ET tー 21=1
< exp
bb و (T aN PI
For the second bound, we define
l0 = sup
f1 ST
b < al (x-10)
2
20

---

Then by noting that 1 - bt + at 2 0 for all 1 S t S T again,we can bound the quantity of interest as
En,,
T
[Emn (1 bt + at at=-)
N
II T II (1 - bs + as "
E t-c
r
(E)=11 (1 - bt by + at - II= (1 bs + as a
N
(II
r
(1
bs 3 + aas
(Ee1 1-
2=j=1 (1 - bt 8 + at a
Σ N
L0 I1 bs + aaa x)))
x
T
N
(1-
b
3-11
IT
g=t+1 (1- b 11-281 ) N
t=t++1
-=1=1 j=1
2
[
I
(1 8 5-
N
E
to
5
Σ N Σ (1 + at x II I1 (1+ + as )
t=1
N x
1= 1- IIT I (1
(1-2
))
N
2
=11
+ +N(1+))N-1 x (II
(1-2--0) No
x EE t- to [ (1 as (1+
=13
=12
In the last line, we have used that 0 < 1
br- < 1 for t 2 to + 1 and 1 + at S 1 + a. To
control the three quantities, we first note that by [3 we have
6N 2 s=1 87
S3
exp
exp
s=l
bN Σ a=1
T
5 exp o.V E/e === sJx)
exp
bN
41 91 (T + 1) + 2a.N 40 f- (T 1))
exp
2
In (a) above, we have noted that y S as (k- for < to: in (b). we have used to S T and
Lemma C.2 ii) with a, b 2 0. In the special case 3 = 1 < K. the above yields
exp 2aN (T+ 1) (n-1)
S3 $ (T 1)
< TT e--T.
NaN
We now control S2. By
13 again, we have
S2 5 Ete 1 exp
aN Σ fo 0=1+1
$ ET tt eep
(NN) ET T Exe0H1
(2) exp (2aN + 1)) x
EEr 5 exp ( 1-2aNN + 1))
(4)
/ 3 exp ConN (T+1)) ΣT, (1+2) eepp ( 2aN + 1))
T
In (c) above, we have applied Lemma C.2 ii); in (d), we have noted that suPtEn (t + 2)8 /t8 - 33.
x + 1 and a > O, we can apply Lemma C.2 iv) to get that
3 2aN (T + 2) max
S₂ S
exp (2aNę1-x(TT+ + 1))
Q2
N(1+a+oN-- cxp (2aN (1)
21

---

If = 1 or = 0, the bound from (c) above reads
S2 < exp (T' + 1)) Σ t-1 1t) 2aN
I exp P1- (T +)) E 5-22N
Q2
2 (T + 1) exp (2aN pp (T 1))
+( exp (2aNV1 1))
where we have used Lemma the bound from (d) becomes
ii) in the last line. Now consider the special case with Ç = 1 < K,
S₂ v 3 exp (2aNV1- 1 (T + 1))
T [i=((+ (t+ (-200a2gg 22aaVinnn 1))
I 3xx 2aNN (T 17
T (t+
x-1
2ux I 3- T log(1 + 1).
We are left with controlling S1, which follows from a similar strategy as controlling S2:
S
1 eep
(- bN Σ
878)
+=
2
t- eexp
bN
T
1=1
==1+11
bN
Pi a1 (T + 1) Et. to exp (22 f1- (t+
T
exp
(14)
4 exp
bN
G1 G1-B(T + 1)) T (t + 3) exp (tr 91 (t st-
2
In (a) above, we used Lemma
C.2 For B * and b * O. we can apply Lemma C.2 iv) with
> 0 to obtain
S1 S 46 cxp
bN P (T + +) (T 13)=mxxx00-22
bN 2 91 + 3))
exp
bN/2
2 22x+1(7 ((T 3)
bN
(T 3)1- (T + 1) 1))
exp
bN
2(1 - (3)
( 22c+ (T ()-
6n
Q1
bN
2(1 - (T - 1)8 iii) with - 3 < 1. Meanwhile, if 8 = 1 or b = 0, we have
exp
N
In (b), we have used Lemma
S S cxp
bN
2 11 (T + +1)
E ( (t+ 1)
T
2 PT- (T + 1)) Σ _ C
b
< exp
bN
91 s(T + 1)) = Q1
< 201-c-bN/2( + 1) exp
2
N
For the special case with
( = 3 = 1, the bound in
14)
becomes
S < exp
bN
50 (T + 1) Σ
exp
6N
coll +1)
2
2
(T +1)
- 1 + 1)
5 (T++))
IN
(1-
t=]
2 2(T 1) P (T + 1) 2(T + +1) 1)- 2 (T 1joN/2
-1
bN/2
6N
In (c), we have used Lemma C.2 ti) for both the case
6N 2
< 0 and
1
AN
2 0.
2
Combining the bounds for the general cases, obtain the first desired inequality that
Σ
T 1- (E (1 (1- 1l bt + aa- IT (1 bs + aas "M)N
S Q1 + +exp
2 41 (T + 1) + u4p1 - e (T + 3) + 4a (T +1)) Q2
22

---

For the special case Ç = = 11 < ni 7/ combining the earlier bounds gives
Ei= t- E |Σح= (1 b + at -t=))=-) II II (1 - + as ">)"
3N(1 a)N -1 AuN
log(T
(T
C.2
Contraction and integrability results
The next result is standard result in convex analysis, needed to handle projections performed in Algorithms/ D [
Lemma C.4. Ler v a be convex subser of R'. Let sh* v. Then, for all IR, we have: [|rrojo (1)) 1 S 1 1
Proof. We have:
|| 112 || Proje (v) + Proje (b)) 112
1 Proje (b)] + 2 Proje (v), Proje (v)) v² [|Projo &12
Since by (49 Proposition 1.1.9], we have:
( Proju (1b), v/ Proje (16)
for all v/ E V, we can use this inequality at v/ = 1/* E to obtain:
|| - 11 2 || - Projy (v))l
and the result follows by taking the square root.
We now state two lemmas that guarantee an amount of integrability sufficient to our analysis. Lemma C.5. Let p.g E P(X) such that de exists, and such that (2 q) < +00 Assume that E (g) Then Epfl +00.
de Proof. By assumption, f L²) Moreover, (2 < too, and thus we have Thus, the inner product is finite, and
L²(g).
dg
/ / dp dg
)dgl = =1rrpp sdp
sdp-pp - sdal
PR - Eyll = M < t00
- EEgl < Eppf M + Eggl
Lemma C.6. For all a E W for all m 2 1, and for all k 2 1, we have:
E
Im ob|
+00
Proof. By analycity of the log partition function u! + log Z(b)), we have ʃ [|øl]* dpy(x) < too for all vi E v, and thus, the function - || (x) E (2(p)) for all v.. Consequently, Pn |
I, (p.).. We can apply Lemma C.5 to P || obtain Egg- pm * +oo for all and for all m 0. As a by-product, we obtain pm || E (P and thus ||
L
The following lemma is used multiple time in our analysis.
Lemma C.7. Assume A3 Let be positive integer. Let I = (J1,..., such that Su E
(o.) 12 U ( 1 for [g]. Then, for all V. we have
| [PT -UU--Pp./ Ep S an Cx (Epe [||. Ep. 119) 1/2 11 1011
23

---

Proof. Let us note first that
|p PV (f
-p-Ep 11
P (fr BBp (2) (pe- (2) Pv do
Pi (S: Bip (x)
dp
(x) -1) Pes (xx)dr)
dps
dp dpw.
(z:) (x)-
Pot po: (2:)d2x
pe (S: Bis Dx)
S x (p Pv
p (f; -Ep Eegli
(0)
S a
2m x (pp:
|| Epp
1=1
0 || 11 Epp ||f 1
Here, we used the fact that P admits Pvp as an invariant measure in (a) 34 Eq. (1.2.2)), the Cauchy-Schwarz inequality in (b)
C.3 Miscellaneous
Lemma C.8. Let f: V - RR be differentiable function in the interior of v R For V.
define min (+) == infaew. ||e||=1 0 ( and 6 max (1²) = supooe.loll 0 V f with respect to the Jacobian matrix V f(().. Then for any 11, 1/2 E V, we have that
infgev mmin (+) I (v/1 )22 (f(v1) f((2)) I suppew maxx (v)
Proof of Lemma
C.8
By the mean value theorem, there exists some a (0, 1) such that
(vi 10--- v22)
(ti - v/2) (J(1 th +0 1/2) f(0 +/ + v/2)
= (wi - (22) VV) (ar' + (1 - 2)) - 2222)
|/ 2/2 (41 Φ2) T
V f (ath1 + (1 a)v2)
1 w2ll
1
Plugging in the definition of maax gives the desired upper bound and similarly amin implies the lower bound.
D Proofs for Online CD
D.1 Auxiliary Lemmas for Online CD
We recall the following notations used in the next lemmas, namely os = Ep 11 Ep, 0112.
0. = og- and σ == suppew Op-
We now provide two intermediary lemmas necessary to analyze the impact of variance in the CD gradient. The strategy similar in both of them: we change the integration from P to Pv: to obtain contraction, the cost of an additional term scaling with Cx || v/² [|. We obtain exact constants that we choose to describe in terms of the smoothness parameters of the problem, e.g. the th derivatives of the log partition function log 7, which, for k 2 2, equals the 1tth derivative of the negative cross-entropy model w.r.t p
Second Moment convergence
The following lemmas guarantee the second moment of sample from km pa- approaches the second moment of a sample from the target distribution pa- and
Lemma D.1. Under
A7
A2
A3
for all 1b V. we have:
Bpg
Pm ||
Ep, ||
< Ca"Cx 11 - w11l log 7 1,
24

---

where
|log 1, == sup BEE
(40 log 03 log Z(v) + 20 log ( + 40, log Z(1)0 log (
0 log ((b)) to0
Proof. Applying Lemma
C.7 each fi = of. have
T Cx 114s -b² (By (of p. o5g o
Epg.
Epg oi
Caa"C a Cx 11 1 (E (E 09)))) 1/2
We map the two moments to derivatives of log (v²), since the hthh derivative of log (1b) is the 1 cumulant. It can be shown, using the multivariate moment cumulant mapping, that
Eø log Z+ 4 + 6 Olog Z 8 log Z
8 log Z
2
alog Z 0 log Z
0 log Z
+3 3
4
+
dvi
Ov?
OU7
Oup
Ous
0f log ((b)² + 60; log Oz log ((b) + 30; log Z(1)² + 40 log 2 10 log Z(0)
o log (1b)
where 0. log ( denotes the :t derivative of log Z with respect to v/. On the other hand, Eoτ = 0. log Z (1b) + of log ((v) (Ed?)² = 0 log ( + 20 log Z ( log (v)) + 05 log Z(
implying Ep, of (E2g 07)² = 40 log Z 20 log Z(b) 20 log Z 48 log Z log (
of log (vb)
The result follows by summing over i, since:
Epg P 0l Epp | S Ei_ Ep.. P Pro - Epp 0?
Note that |log 211,, is finite since v is compact and log Z is analytic.
Squared First Moment convergence The next lemma provides convergence (in squared absolute value) of the first moment of the m-iterated Markov kernel k
Lemma D.2. Under A7
A2
and
A3 for all 1/ E V we have
|
v 21 - | a||
S ax o + C/am/4 allog Z112,00 1 - -
where
|llog Z112,00 == sup
E i= (F(1))0 log Z(b)) 1/4 + 2 0y log 2(v) log 112)
+ew
and
F(b)= == -150 log Z(0)) + 100 log 2(b)2 + 1507 log Z(W)0t log Z(v) + 8 log 2(
Proof. We have:
E pas pm 6.) (Epgr e P 00 Ep. 0: Ep 02)²
=(Epor pm 0: pmm
Ep 0z)² 21E Φi (Epg- pm 0; -Ep, R.)
+ (z))
= Epg. 6:)2 (Epp oi) << (Kpg. pm (Ø: Epp sbz)) 3
+ Ep, di Ep.. pm (Ør Epp 0i)
25

---

where
A = Epp (0r - Bxddi)? + Bpp ((PT)) b: - Ep 0i)²
(dpe-
dpp
An,2
A12
2m E Eo: 21) + +C 11v 10 (Epo (p: -Epo bxp 02)²)(/2
(6)
2 a 2 Ey (0: Expp,) Cx -10 - 1 (Epg Pm (0: Ep (2) 1/4 (Epg pm pm( - -Bp 610 1/4
(6) a
2 Es - E + a am2 Cx | - +0 (Ep, (o: - Ep, 01)9) 1/4 (B (d, - Epy 01) 1/4
In (a), we used the restricted spectral gap Assumption A3 for 11,1, and the Cauchy- Cauchy-Schward Schwarz inequality combined with Assumption A2 for 41.2. In (b), we used the Cauchy-Schwarz once again, and in (c) we used the fact that P is a contraction in (pp) and another invocation of the spectral gap assumption A3 As an aside, note that a simpler result can be obtained by making regularity assumption on the mapping &0 + p Assuming that d + PT is uniformly Lm -i--ssichitz across x E X for instance (as done in 21 Assumption 5)), the second term 41,2 of A could have been handled using
1 S pp, | 6- - Ey of 1 + 11 0 pp 01
< (Im 1| 101l + a²aa2 2m + Ex 1 - Ep. 13)
S 4( || 20
|| + oaa² 2m + 222 1 I1
Although this result does not require possibly large constants related to sixth-order moments, it is less tight the sense that it does not go to 0 as m + co. Back to the main proof, and A₂ in particular. Applying Lemma C.7 to f = Φ. we have
A2 S a E 6s Cx 1100 11 (Eps (Ø. Epp oi))) 1/2
Sa" log Z()) log ((b) 1/2 1 10'l
Putting everything together, we have:
Pp (P 0,)2 Epp 0371 S a 2m m (0: Ppp 22,)
+ Cx || - 101l (Tpp (p): - log )b)) )0) 1/4 (E (Ø: - log )2//
+ 2a m of log (11))222200 log Z 2(3)
< a 2m Tm (0: Ey, 012²
+ Cgam// 1 11 (Eps (Ø: log d:) ////4 (Ep., (Ø: log 2)
+ 0 log OV log 222)2/22 )
Summing over i, we obtain
Bppe || pm 2| - (Ep,. 2
$ p 1=1 Epp. (pm))) 02,2 -PEps 21
< 2m DS1 == (p: - Ep, 0² + C2am/ |log 21 11 - *1
< 2m
oz + m/2 |log
m/2
211,,00 1/ - -
where
|log 2112,00 supeev Σ
p (Bpo (d: Ep 1// (Epa (b.. 1 Eps 21)2
+ 2 00 log Z O log 2 1/2
26

---

Similarly to the previous lemma, one can upper bound [(Ø; - Epp,, 6.) using the centered moment cumulant formula:
Epp. (d: E 6 150g log Z())* + 100 log Z(1))+ 1504 log log Z ((6) 0 log (
(())
To get a full description of |loo 7 12,,00
|log 2, suppev Σ i=
(F(#) log Z(t))" +2 ot log log
Lemma D.3. Under Al A2 and A3 for all 1b V. we have
Bppp PT - || w/| S a + Cyan//4 |log 2112,00 1 - -1
where
|log 2112,00 == sup +E
E. i-1 log 1/4 + +2 log (( log Z
and
F(L) = 150t log 2( + 100 log 2()) + 150t log Z(v) log ((b) + 0. log Z(6)
Proof. We have:
E pag (P 6.)² (PT)
Epp. (P di Epp 0: E., 01)²
-ppg (Pmh ob: Ep x2)) 2 Ds Bop pm (0: Ey Φ.)
+ (Ibr)))
Epg. (P 0.)² ((Ep, 0:) - Epg (pm (Ø: Epp 0.))
+ E di Epp pm (Øs Epp Di)
where
A = Ep (P 2 + Epp ((P. o: 0:)
(dpo -1
dpp
A1,2
A
(a)
S a 2T (0: E.) + +C /| - w'll (Epg (Pm - -Ep (2)))))
(1)
E (b:: - 22 2 + Cx 1/ - 1b" (Epg pmt(de - Bx, 1/4 (Eep pm((b: - (1pp-Epp di )2) 1011/
1/4
< a
(0)
E0 2 n 1 Cx || - w1 (Epp (6:, Epp 21)2) 1/4 (B (di - Ep, )o) 1/4
In (a), we used the restricted spectral gap Assumption A3 for Λ1,1, and the Cauchy-Schwar Schwarz inequality combined with Assumption A2 for A (b), we used the Cauchy-Schwarz once again, and in (c) we used the fact that PM contraction in L (p(x) and another invocation of the spectral gap assumption A3 As aside, note that simpler result can be obtained by making regularity assumption on the mapping &i + pm Assuming that &i + Pm (x) is uniformly I. - across z E for instance (as done in 21 Assumption 5)), the second term A1,2 of A₁ could have been handled using
1 S 2E,.,
pm 0 Eg o 1 2 Epp. ø1 10
5 4(4m |b +1 o. a
2m + Ep.. Φ Epp ol
< 4 (m
|| - w0 a²22m 2m 2L || *1)
27

---

Although this result does not require possibly large constants related to sixth-ordes moments, it is less tight the sense that it does not go to 0 as m co. Back to the main proof, and A₂ in particular. Applying Lemma C.7 to f == Φ we have
2 S a R Ss Cx 11 10 (Bp (d:: Bp,d))))) 1/2
Sa 0 log (1)) log (1b)) 1/2 11 1/-11
Putting everything together, we have:
Bpp. (P 0:)² - Epp 081 S a Ep,
p (0: Ep, 2.)²
+ Cx 11 1/'1 (Tpp) / (Ø: - log )o))))))))))) )1/ (TE (6: log 3)/4
+ 2a m 0f log Z(v)) log 222)
S a 2 (0: Ep, Ø,)2
+ C2am/2 110 - 10 (Ppp (ch log 0i) )0) (R (6: log obe
+ 2 0 log (1)) log 2
Summing over i, we obtain
Epp- || P 211 ( 21
$ 1=1 Epp. (P
p
(PT')) 0.)² ) (Epo 0=
1 0 2m p
m/2 -i=1 Epp - Ep, di)² + Cxam/2 |log 212,00 11 - 111l
s a
2m
og + Cxam/ m/2 |loo Z112,00 1/0 - -
where
||log 01 Su E (Epp (d: Epp 0:4
(Epo (0:- 18--a 1xp 0:)3
+ 2 0 log Zl O log 1/2
Similarly the previous lemma, one can upper bound [( Ep, 60) using the centered moment to cumulant formula:
Epp (d: - )6 6 = -50g log Z( + 100 log Z(b)² + 150 log Z()) log Z(b)) + o log 2
=: F(b)
To get a full description of |loog Z 30
|log 01 = supsev E (F(*)af log 7(0)) 1/4 +2 0t log o6
We can now the previous lemmas to obtain an expression on the second moment of the contrastive divergence gradient estimator, relating it to the one of the stochastic log- likelikel gradient estimator.
Lemma D.4. Under A7 A2 and A3 we have:
E Il (v. x.)I < 2 + 2 + 2L |/ - - 12 + +40 ma |log Z113,00 Cx 11 *
where |log Z Z1la,00 = 2 max (Illo 211, ||log 2112.00)
Proof. We rely on the following decomposition:
h (1b,,, X.) (.(X,) Bpp. Φ) + (Bpa. 1b - Epp Φ)) + (R
km (X..))) -0(p (Xe, x))
A (Eps Φb Enn (X))))))
AL2
42
28

---

A1,1 + 112 form the differentiable stochastic gradient 9r of Equation 6 Note that 1 is mean- zero, and 22 mean-zero conditionally on X, Consequently, E (A,,AA)
(Az. AI,1)
E 1 112) = E (A1,1, Ae) O, and the only mixed-terms that remain to be controlled are I A3) and R (A As). We first control the unmixed terms, and the simple ones first: we have E | I| = of as well as E 2 < 1|
10 1 For 22, we have:
(x,) ||2 Eay (l0(( (2, ))1 (a, ( (z, ))1
Pe -1
We can invoke Lemmas
D.3 and D.I which guarantee
E Pp. P
ol - || ob 1/
S a 2m oz + Cxam/2 ||log 21 11 - 1=
Ep.. P 1101 - 11b|1
S a ax'C' Illog 21 11/0 -00 10'1
to obtain
Ep.. Bay (u.-) /a>>111111 |
Epp |1oll || 2 + a 2m o + +xxa Cxam/ (Ilog 110, -Illog Z112,00) 1 - -
E ll Enil + 2m o + m/ |log Z 21111,,, 11,,00 Cx 11 -1/1-11711 1/
where |log a1 = 2 max (|log 2 1,000 ||lo Z Z11 1.2000)
For Ag. notice that Ag is precisely the term A in Lemma D.3 and we can thus bound it by
E p | o 2m + m/2 |log 2112,00 Cx l|b 11"
2m
Finally, we simply bound 2E (A1,1 1, As) by E || 1, 11 +E | 12 and 2E (1 Az) by E |1, E Aall". Putting everything together, we have:
E [[ = 1 B| + + 2 + E | 2 2 (A 4s) + 2F (A12. A3)
S 11,1 2 1 + A2 2 3E A |
$ 20 + 21 || - w- + o3. + 4 4(0 2m + a m/2 |loo Z113,00 Cx 11 - *1)
$ 20 + 20 + +22
| 11 1 2m + m/2 llog Z 3,,00 Cx 1| 2/5
D.2 Proof of the SGD recursion (Lemma
3.
We are now ready to provide an SGD-style recursion for the expected squared distance to the optimum
|
11
Lemma (Restatement of Lemma
3.1 Let t/2 be the iterates produced by Algorithm Denote 1/2 Then,
6, = E [lkv 1 a. (E
$ Epy, 2/ and o, = (Eye, 1 Ep,,
under Assumptions
and for all
have:
8, 5 (1 21.0m, + 2n/ 12) + 1/: 02 m + 4a m/2 |log Z112,00 Cx5L12
where |llog ol is constant, Pm,t == p a Cx and om,t == (o? + of 20
2m
Proof. In this proof, we note (Fi)ro, the increasing family of o-algebras generated by the random variables (X.) ~ Pe- and the Markov chain samples X X,, the ~ km (X,, We decompose the integrand & as follows:
1/ 1= = [|Proj - - 25 1
-
S |/ (n//((///1)) 1/211 (By Lemma C.4
= ||6k-1 w²2 - 2n (1r(())-)) sh--1 - vt) + me h (vx-1))
29

---

The first term is (up to an averaging operation) the previous iterate. The middle term will ensure (provided is large enough) contraction of the expected distance the optimum. Finally, the third term can be described by Lemma D44 and essentially behaves like the second moment of log-likelihood stochastic gradient. Indeed, noting g(b) == -Rp @ + Epp ø the expectation of ge w.r. 2y (which is the gradient of the negative cross-entropy between Pe and P we have:
(ho(Wn,e-)), P v (g(V P -.5) + ((he(Wn,t-1) - -(Vn.t-11 1)), 2 - 30
and applying Lemma C.7 we get that
(1/22-11 - 9( = "(k"'(('''00 (X,, -)) Bpg の
pp. Engy (Xer) (M6( g(vi-1) F( = P3 Φ - Exp o,
meaning
[ 111 S Bppp P -mpo e|/l ||/--1 -1-11
Sa Cx( (Epre-1 ||5 Eppers f 11 1/112 1|/0 11
aa σ - Cx |1 - 1121
On the other hand, by applying Lemma C.8 to g. we have:
1), wh-1 か³ = (g(1/ g(bb)(())))))))))))) th-1 -w0) 2 1111/1111 --0-1
Combining the above results, obtain:
Epg. Eay (x.)) |1eee - 1/ [F-1]
< (1 - 2n (p am 01 01- 02-112))) 11111
+ 1/2 (20 + 20,-1 + 22 | - 111 + 1(002-1a20 2m "a" |log 110,000 Ox 11/1 (D)
And the result follows by integrating over Fi-1.
D.3 Proof of Online CD convergence
We now prove Theorem 3.2
The recursion of Lemma 3.1 is almost identifiable, up to a cross-term
of second order, with the one of an SGD algorithm presented in the setting of [22] Theorem 1]. To make the identification exact, we use the bound /2 |log 211 C, < 2a m2 m
1/2
2a m/2 |log 2 1 Ox yielding the following recursion:
6, S (1 2m, (+ am xCx) 2n (L²+aa/)))) + (2 ) m/2 |log 2 212
where we used the fact that mm.t S a. This recursion is of the same form as the one studied in 222 Equation 6, Theorem 1] given by:
6, < - (1-2pm + +2L?7/) 8,-1 + 20²??
by identifying:
o² + (2 2a 2m) + m/2 |llog Z 112000 =0
2 + (L2 + a m/2 = i
μ - p am o0x x = pm
7 T
We can use the same unrolling strategy as theirs (the only condition required to proceed is that Jim > L, which automatically holds since μ < L), and we obtain
2 exp (4iC((1222(m)) exp exp(2
anC n 1-3
50
82
4C82 Pm
if < B < 1
f2
8n <
(80 + 1.
82 + 282 2 Pam (n)
1
m
mim C72
30

---

D.4 Proof of online CD with averaging (Theorem 3.3
We first restate the theorem its complete form.
Theorem (Contrastive Divergence with Polyak-Ruppe averaging). Let (1)))20 the sequence of iterates obtained by running the CD algorithom with learning rate 7/e Ct- for B E (3: 1). Define we have, for all n 2 1,
nn Di= vr. Then, under the same assumptions as Theorem 3.2
B T 2011
S 2/
(((I(W)))) T1
0 (.) (1- +m Box
Where I(1b*) Covpo [0] the Fisher information matrix of the data distribution. Additionally, if
(1-8) log have E 1 ao
101
21
(r(I(v)) (n=
Throughout the proof, we will denote by hn the standard online CD gradient defined in Equation
(n(-n-1) -((x)) + <(k (:, Xn)); Xn por, Vn E N {0},
as well
h(vn-1) E (h(2)- v Ep.. o(X,m) + Epg. Egm pn-1 o(k :)..
We start by establishing some intermediate lemmas. Lemma D.5. Under Assumptions A7
A2
A3 the online CD iterates produced by Algorithm 7 ussin
Ne Ct for 3 E ( (5.1) verify
V
E
|| - v-(1() (ot=v+11')
On On -3-
Proof. Let us note 8n EE ||
Summing the r.h.s of Theorem 3.2
we have
Σm 8; S E
4082
+
80 +
am
i=1 1
1
1=1
43
1 V n 1=1 8; S n
AC (1))(n) + //
22 -O (
)Aa)
12
where Ag is finite if 3 < L, and Ag (n) otherwise (22)
Lemma D.6. Under Assumptions CL-9 for 3 E (2, 1) verify
A3 the online CD iterates produced by Algorithm 7 using
|1 0=112) 1/2 = O( -3-
V E
E
Proof. Let note on
E
||
Applying x 1Ttv S V v the r.h.s of Theorem
3.2
we have
8//2
201/2 am
8/112
82 2/ 60 +
2l' (1-20(0)) AmC
1=
2pm
1/2
i=1
12
i=1
1/2
1=1
8
1/2
n
1
20
1/2
(1-282(())
+
1
do +
02
7,2
Aa
=0 (n
where A₂ is finite if 3 < 1, and AA O(n) otherwise 122
31

---

Lemma D.7. Under Assumptions ?i Ct for 3 (3. (111) 1) verify
A7
A2
A3
the online CD iterates produced by Algorithm 7 Assig
|
En h
= =0 (n =0(
Proof. The result follows from the fact that he verifies
he( = - fje
(1i-1- -1))
A similar quantity was handled in the case of standard SGD 12 Theorem 3], and the only condition
needed reuse their steps that (gbe)esn satisfies an upper bound of the same form as the one [2
Theorem 1] derived. This is precisely the nature of our bound of s/, estblished in Theorem 3.2 with
Jom om L. Borrowing on their result, we have:
45 9
43
1/2
E
PP222(n)
+
80 +
A2
22/2npm
Cruu
1/2
L
- +
60 1/2
+
25. 201/2 7m
P1 91-8(n)2/2
C
1/2
pm
41
2 1.2
1/2
+
60
+
Ag
n
where Mmm om and L are defined 3.2 and
A2
Σ
Am
k=1
Lemma D.8. Under Assumptions Ne Ct-B for 3 (2.1) verify
A7
A2
A3
the online CD iterates produced by Algorithm 7
using
1-11]] = O(n (n)
E
Proof. We proceed as in the proof of 22 Theorem 3], first establishing recurrence for | w011") [1]]
and then unrolling it. We have
E
Ilvin 16"11 Fn-1] & || 111 + 6n/ 11 11-1 E [1/bn (1/n-
1) Fn-1]
+ nal |l/inn (vn-1))l [Fn-1]
4m 11 w/ 11 (win-1 - 26 ; E [hm]]
+ 11v w E |lhn (+hn=1)l [Fa1]]
The second and fourth terms will be controlled using results from our previous sections. For simplicity, we don't attempt to relate the moments of ||A,,!I* as precisely as before. Instead we use:
Epp-
< -h
Epm p
[ -111 Epp- [[l{(Xx)]l*]]
And let us note = (supyew Epg [101(() 1/8
We have, for k 2 4.
Epg Egm
P 11o(k,) (Xn, + < Ep,. |l + +Cx Cx(e,, (11111 Ep.., 1/ - +1
S 7 + 20x | - 1111
32

---

Where we used the fact that P.m. on- is a contraction, and (IE) )/ is an increasing function of k. On the other hand, we simply have Bp-- (l )]| S rh Plugging this into the previous equation, we obtain
I1 - 10*11 Fn-i]
11 - 111
+ +nn || - 112 (4T² + x4x 1
+ (167* + 16Cx=* || x011))
41jn I| - "1² (Wi-1 //= ,E [n-
+ 4n || - w0 (8T + 80x=* || - 2/5
To simplify the recursion, we use the four following inequalities:
73 || 1 311 - /
1
( m -11 721700 11 -11)²))
1 - 4 |1 *)()()))
7 4 |10 - 10 s (r +
7 || - 10 < 2
|| 7²
- 1b211=+ + 16
7 |1n-1 10 - 1m + 1110--1 -62 (/:))²+))
Injecting them in our recursion, we obtain:
E [1 1011²1 1=
< 1n--1 16-112
+ 12n |1 - 11
+ 12C 7 72122 1/2ll1in || 1/
+ 120x 2 | 11
+ 16
+ 16Cx
+ 40x || 11
4mpmm || - 11
+ 16 2 11 - 11
+ 16
16n C2
+ 16n CxT² || 3/112
33

---

which, after further simplifications, yields
E 1lvn - 311 Fn
1 1| 15 1 (1 4m 12C + 4C21"1)
+ nh 11in-1 - w0 112 (28(1 +
< 11 11 (1 4mpmm + +
+ 28n 11 - 11 ((1+ +217)+327
& 11 - 65 1² (1 - 4m + +[ + (()7))))
+ 28 11/--1 11 ((1 (2)
$ 11 - 60 11 (1 4m + -
+ 4(2(1 (x)r)* + 2017 || (2L
C2)r)*
< 11 - 10 11 (1 4 -1000 Cx)T + L)²
+ 4(2(1 + Cx)T + =)) + 20m 1 - -01 (2))- 16 (2(1 Cx)r)*
< 11 - 161 |1 (1 4/ P. 12 [ 16// 1, +4i(mh)
+ 20n 1| - 1/" 7? 16
where we defined 71 == 2(1 + Cx)T and Ê, = 2(1 + +xx]T + L. This recursion is of the form of the one studied in [22 Equation 32] (note that by design, L 2 jmm.) The steps performed to bound | e- [|] thus follow from their derivations, and we obtain:
1
- 1,1/2 (39/2(1)) + jim p1
n
Ci
2n
/20
Al exp (241 (60 + BmbBl00 - 00
+ 2:90 Am + +277 1/2
+
2n
20C77
= (n
where
A1 = 4-Ex
k=1 e 10
-BC a 0110 (x)
and we have A(1) < to0 8 < 1, and A(1) = (n) otherwise.
Lemma D.9. For all v. we have:
Coov
- Cov [x(x))]]]
Sa Ca (F2/2 + 2/| log Z Z114,x00)lv - 56 1| + a 2m Oz20 1 - + 1
where F = sup Epp |1000T -Ep, 100 T1 < +o0 and || log 211,,00 sup || s
sup#ew Σd= 8? log 2
Proof. We have
Cov [ (Xn,))) })]] = Ep,,, pm [ - (Bpgr (PT (Epg- (P T)
Looking at the second moment first, we have
Epg.
pP ΦΦ - Ep sbo Epp.. Pan (do Enn Engchoo T)
Ai
Applying lemma C.7 to the of -valudd function f given by fiz = =0:00 - Ep, BI00
|| |الم S 1 w0 "1 Cx
Epp [100T - Ep, 220 T
< F1/2 "///2a""C"""
Cx 111b - -1
34

---

We now investigate the first moment. We have
Epg-
P Φ
Eps- p Φ - Epg [(]] + Epon Φ
A2,1
(Bpo. P (B Py pT Epp Epp Bpp ot 2211 A2, + Exp $1
and thus, applying Lemma
C.7 on 2 we have:
| < A A 2,1 12,1 66 + Epg [Ø] 42 llr
- 2, 2 |1l + ||2 Epp [Ø] l|
S 2m x² 0² 1/4- 1
loo 2114,00 a
Cxa 11 4
where we used that 11 //1 1| We can now combine two matrix moment bounds to obtain
||Cov [o(k (Xm; })] Cov [x(()))]lr = ||41 + D2llr
aa Cx 12 2| log 20 *1 + a 2m O2oO 2 1| 16=112
Lemma D.10. Under Assumptions
Al
A2
A3 it holds that
("(()t)- hss (1h: 1/)1
ir(I((0)11)
E
22
[(0-)~
(M + a= + 211 log Z 2112200))2222
(Ein 6/ 1/2
2m C22 (Ei= 0i-1) 1/2
where M =
<3 ((x)) (ap(l--ll- 1p((1111p:.111pp) 400.
Proof. (1b (n(3n-11) = - (0(Xn) - Epp. + (oCkT,,(XX,) - Epn- Exy
6(kmh_ (Xns 1))
Ar,
42,
= A + f"(
Noting A the I.h.s of Lemma D.10 have, summing over [m]. and using Minkowski's inequality,
A
<
E
Σ x f"((*)- A1,
E
Σ
Note that this step was made possible because we are looking at the square-root of the variance, which unlike the recursion Lemma 3.T This allows to separate the terms and use fewer intermediaries than in the proof of Lemma 3.1
35

---

Since both 1m, and 2n, are martingale differences with respect to the filtration F the covariance terms vanish, and we have
E -11"
+ n += - E =1
(n((""("")) [A
tr( tr(f" 22, (
tr
Σ 1= tr (ff"((*))) Cov (olay (0:)) (1((t))-1)
n
tr(I(1b)))
- (x() -1 'Coo o+ (Cov po; Φ Cov pur の)
12
+ (Cov ((1:7) (aa)) - CoNpo, o)) (1))((())))) 1/2
tr([((b))-1) + ((r(I((+)-3)
E/= IICCovvon_1
Pon-1 8- - Cov
n
1/2
+ ||Cov (K: (x:)) - CoV )}[[F)
(2)
(r(((ab+)-1) Vir(I(e')
S 2/
(M + Caa 211 log 2 /1/22)
V Σn == |1 - wb-ll - + a an C2 Ein Ei=ilbi- 15-113
(8)
(M a 2/| log log =1 1/2 /E 67/2 tr([(1+)-1)) 2
2
Fa"Cxo Σ. " de
In (a) we used Lemma D.10 the cyclicity of the trace, tr(A B) S ||AB|| S ||l|p B p. and the fact that since Cov _ [o(z))] ((b by analycity of L, there exists constant M = supse || log 2 [pp)1))1)))))) such that
[V - - SM 11 MM 1
In (b) we used Jensen's 's inequality to get E [||v/-1 - w01l S v [1 [1165-1 - 15-1]]]
-1/22
We are now ready to prove Theorem 3.3
Proof of Theorem 3.3 It holds that:
f" ((/nn)))nnn)))) )² f'(hn-1) - + (("'""))-- 1((n-1)+ f(+*))
-h,(vhn1)- + (f"))"))))~11 15a - ((n-1)++((0
+ (f(( - (())n-1)) + (1((vn-1) - hn (vn-1))
36

---

Applying on both sides: (a) summation over i E [n], (b) multiplication by f (c)
and using Minkowski's inequality on the r.h.s, we obtain
Σ のx --1 -
(8)
E
- th
(f -60)) - (((b)-1)
(4))
| Σn
E
(116)
E
| En th
h. (((0)-1))
(iv)
(i) and (ii) have direct analogues in the proofs of prior work [22 the convergence of (unbiased)
SGD with Suppert averaging, and will be bounded similarly. (iii) captures the bias of the CD algorithm, while (iv) captures the variance.
Bounding (t)
Using Lemma
D.7, we have (1) = 00
Bounding
i1
Since log ((b) is analytic, there exists some constant M' such that
- -b² - s M M/ 16" 1
Thus, we have:
M' n
Σ ||: - 1111)
M'
(ii)
E
E I1v
O(n
where the second-to-last inequality used Minkowski's inequality, and the last applied Lemma D.8
Bounding
(dii)
By Minkowski's inequality, we have:
(it < Σ E [1((()))) - 1(
Moreover, using lemma C.7 we have:
E Epen_, O- Eppr En off
([ h( 1)|l
- --ppan of 11 1011
a " V Bpwa-
S a m OCx || -1'11
We thus obtain a
(iii) S
ax
12
E 111/5-11
1/11/11/22
Ox
Σ" 1=
12 81/2
1=1
Recalling that & satisfies Theorem 3.2 we have that 8 O(n -8/2), and we thus have Σ 6!/2
Onn'-5). -). By squaring the result of Lemma D.6 we have Σnz 5./2 -1- and thus, we obtain that (iii) Ola"' -B2) Onn
4
Logal
log
37

---

Bounding (iv)
We have
(iv)
tr (I(())))-
( (M Cx 211 log Z 4,00 //,- 6//
2V
ta="Caa E 0i-1
(6)
ir (I(}²)=1) x 2
+ O(n - +)-
n
Where in (a), we used Lemma D.10 and (b), we used Lemma D.6 and D.5
Final bound Putting everything together, have that:
V. 1b 112 21
(r(I(1b)-t O(n max
O(nmaax( (-(+ n. 1, (.-(4+ Nor
If, furthermore, m
11-8) we have
2] lopt
max (- 3
3 +
log a:
))
8
-, 1,
< <ー
log
which concludes the proof.
E L2 approximation by auxiliary gradient updates
In this section, we consider different gradient update schemes starting from some random initialization Onnis and control the L2 distance between the different updates and the deterministic target sp* E w.
Notation. Recall the notation that X II...., Xn iid. Per, n//N and for E V, (x)))
(z, ). We also write, for E N {oc).
Th (ar),
Km (x) lid (xr
Let ginit be some V-valued random initialization that is possibly correlated with XJ...., Xn. We capture the effect of correlation through the following quantities: For and 2, let
ginit (c) = DE Z[o(km ginis (x,)) x,, Ginit] - R[O( (x)) ginit) n.m
> c)
Smmma (c) = V + mm.m (Dinit (e))
and
We also consider the i.i.d. samples, drawn independently of X1, ".....,,,, X2, and on given v E V as
XY. X Lid.
Pe-
For notational clarity, shall use 6m,B denote parameters arising from one-step update, where the subscripts m, B represent performing the one-step update with length-m Markov chains and with batch size B. This is to be distinguished from th, elsewhere in the text, which denotes the parameter from the actual multi-step CD algorithm and the subscript denotes the 1-th CD iterate.
Gradient update schemes. We consider five different updates. Let X be an i.i.d. copy of X, drawn independently of all other random variables. The SGD--withrrppacemmen update is given by
FSGD (ginit).
where SS (xb) == 1b
7 Eieso (Ø((.)) of k B
(K (X:)
m,
38

---

and S is uniformly drawn size- B subset of [n). The SGDD-wihhut-rrplaeemee update, after renormalizing the learning rate, is given by the N-fold function composition
F...B (Binit)
m,
m.B:N
where
NB EiEST (X(,,))) for each j E [N]
and SJ are disjoint size- B random subsets of [m], defined by ( ((nl) for uniformly drawn element π of the permutation group n objects. The full-batch gradient update is given by
GD
FGD (flnit).
where
FGD (+))
Eign ign ( (K (X:))
The full-batch gradient update with an infinite-length Markov chain is given by
gGD
FGD (finit).
where
FGD
Σ isn -(xx)))(xx)))
The population gradient update with an infinite-length Markov chain is given by
(PoP = ppop (Oinit)) where fPop (1b) = = -
where we use the lowercase f to emphasize that frop is deterministic function. The forthcoming results are summarized below:
gSGDw m,
Lemina
BGD
Leunaa
JGD
Lenuna
gpop
Lemmaa E.4
Rd
m
OC
Lemma E.1. Let Fn be the sigma algebra generated by {X;, Kigiuu (x,) sis n). Then
E
BGD
ginit
Fr] 0
almost surely
Moreover, under Al and A7
we have
(0² krrm) I [[BEn)
SGDW
BGD11 <
Proof of Lemma E.1 Write A = (A1.... An), where
A: (ó(X.) Φ6 Kigini (X.))) [[(((1) o(K (X1))
Since 5 uniformly drawn from all size-B subsets of [n]] and independently of other variables, we have that almost surely
SGD m.B
GGD m
ginit Fr]
E
A 4-2
A A = 0. in n
To prove the remaining bound, we note that the above relation implies (SGDD By the law of total variance, we have
RGD zero-mean.
m.
SGDW
0GD12 Cov [OSGDW
OGDJ
Tr E Cov
[OSGDW
GGD Oinit Fr]]
17 TrE
E ( Eies A, ( Eiss Ar)
A
-
( inn A.
A) Enin A.) A
To compute the covariance, recall that S is uniformly drawn size-B B subset of [n] with B = n/N. Let ([]] be the collection of all partitions of [ni] into N size-B subsets. We can generate S by the following two-step process:
(i) Uniformly draw a partition P' = (P,,..., Pb)) from Px ([x)))
iii Uniformly sample index K from [N] and set S k.
39

---

Then we have, almost surely
E Eiesu im Al) ( Eies A1) 1 A (H A:)
(
(-)
Lign As)
"
PN((n)) Σ EPIEPN((N))
(+ B²
EnsEp, A,A]
1 Eissh A14))
n2²
(Pw([n)) Σ EPERN(HD
NB Ense Ensery A1A
1 ERIEN Die A14)]
N²
(Py(li)) EPERM((M)
N2B² EKSN EnSEP AAA
N
1 N2
ExØt EnErtJeRy A:4))
By noting that A;'s are exchangeable, we obtain
E m.
Tr
--1 AIAI +
(N 1X 1)
AIA
N-1
A
NB
NB
N
Tr
N 1
A
N-1
A
NB
NB
(N 1)
(EIIA,)) 1|2 E(A,, A2))
NB
(a)
2n7a
1112
2/²²
B
(0(x)) - E[o(x)I) - (o( (X1) - E ( K
Eoins (x1))
B
4r²
(TrCOv(o(X1)) + Tr ToV (6 Km sigmmr (X1))
B
3 4n + m
B
In (a), we have used a Gauuch-SScwward inequality; in (b), we have used A1 and A7 that if B n, 0SGDw GCD almost surely, which implies the desired bound.
Finally we note
Lemma E.2. Denote An as the sigma algebra generated by ginit X1, ................................ Nu- Under Al and we have that for any c >> O and v > 2,
A2
A3
E E m
DGD| AA. I| S 17 (2(amoOx V Elliinnt 112
cini (e)
(e))
E 1l
GGD1 12 S (0(0000xx VEliuuit 11
init mmmp
x2 + t
Proof of Lemma E.2 The main challenge arises from the possible correlation between ginit and X1,..., Xn. First note that for any >> and real-valued random variable Y, by Hölder's inequality, we have
E[ = E[ T(r + T2T [y>
S < + E [(r I 2 ( c)(u-2)/v
(15)
Also note the useful inequality that for two real-valued random vectors (possibly correlated) V1, V/2 we have
V + [3]l < B[[IV]] + [[6])) < E + 2 (E + [F])
(VEI + v 12)
(16)
Now to control the first quantity of interest, by using triangle inequality, we have
E DDD @CD A.]]l = E E Σ Sn (o(K)) (Xx)) o(x, |4.]] ||
E
13 (VEIAR) + B[A3]
40

---

where
4 E > is (0l
K
Epgion (Xi)) [[[(KK
E:dini (Xi)) (init)) Anl]
Σ isn (E (6 K 1:ginir (X:)) |0inie, Xx]] EB(5( ([ spgiii (Xi)) )
2
Eiso
isn (E (K (K iiginit (X1)) @init] ((xx )) An
B[ (X1)) @ (XPtt)) giuit]
and X is an i.i.d. copy of X1 and in particular independent of Oimit, A is controlled via 15
B[A < e + (B[A)))** P(A1 e)
(a)
Kin 1:0inu (X1)) 0init )l")aro
2/v
2 + [E
Φ5 Km
1sgiur (X1)) E (K(
Eisn (E[ km
siginse (Xi)) ginte, x.] B[o(K Rigimis (X))) [
x P
n
I 2 + maym (Dinia (t))
= (e))
(17)
In (a), we have plugged in the definition of A and applied Jensen's inequality with respect to the empirical average; in (b), we have used A7 to bound the y-th moment term as
1,0ini: (X1)) R @b( I:oiii (x))) gimit] [11)) 1/v
K
1,0 (X1)) [amt]]] 11" [ |
1)ur
3/v
E
E
(
Km
1:0rnre (X1)) (o(KT) mm
E (6 m (X1) [(']) 1/2
S
supwev
E
(K) (x,)
('1) 1/2
sup
E
[K
1:00
(X1))
E ( (KT) (x1))
S
and recalled the definitions of n.m. and innt
On the other hand,
n.may
E
B
/ Lid
((x) (K Tigma Pv- (z)dz B[O(xpi))) > |
(a)
iigini (x) p (x)dx - Bpoina |0]l
EE
(KT..
R
(b)
T.gmii (Ø- - Epamir (+])) x Pv- (z)dx ?
E
Rd
(c)
E
(K (o (0- EEggina ④ ())) (xx (p (x) - Poim (x))
Rd
[f Ra (IFFF (Ø- Epginn [01) Tea eq Painn (x) Pe: (2r) Poinn (x) Points
2
Σ
dx)
Ei1 1=1 EE [ʃ
(IKT)) (0- -E (x)) et) Painu dx
Ra
ʃ Bd
Pe- (2)) Pormit (x) 2
Poioi (x)dd) 2
Pognts(())
Ein E(a2"' 2m Tr (ov ) @init]] >2(D"-,
(
- 2mh o² Eljoinks 111
In (a), we have used that (x) I K(x, in (b), we have used that the Markov operator leaves the constant function invariant; in (c), we used that Ki leaves Pointe invariant; in
41

---

(d), we denoted (et) as the standard basis vectors of IR" and multiplied and divided by Painis (z); in (e), we have used Cauchy-Schward Schwarz inequality; in (f), we have used the definition of the spectral gap in A3 in (g), we have used Al and A2 Combining the bounds gives the first inequality that
E
C
BGD
Anlll
S n² p²(a" xx
Bl 1/1 + cm.m:((e) (c))
2
Now we handle the second quantity by conditioning on Oimit and perform a bias-variance decomposi- tion:
E
0 = =1 11 E isn
o(X,"mm) ))
) [A.]]]]]
= (QB + +vv).
where
QB = E
E isn
(0( Eigiei (Xi) - x(x:
An 1|:
Qv = E Tr Cov
} Eisn (6 K spgini (Xi)) Cov
[ Eish of (f
ginit
sloini D]
Note that the covariance terms separate because X is independent of Km Cifinns (X;) conditioning on ginit 2/²0B exactly the quantity controlled above, so it suffices to bound the variance term Qv. By explicitly computing the second covariance term while noting that Xf ......,, . are
conditionally iid. given ginit and Kmn (igius (X,)'s conditionally independent across 1 S i S given An, we have
Eign B Cov o siginn (X;)) ginit xill
Cov [ginit]]
Qy
n²
F[TrCov(d Iiginit (x1)) XII.
E Tr Cov(o( [innie]]
Kivee +
n
where we have used A4 A7 and Al in the last line. Combining the bounds, we obtain that
B1 - 00D 1|2 = (12 + Qv)
S 122 ( a 00x
E finit 1 + (e)t) (e)² 22mm + a²
Lemma E.3. Under Al
E 110 - 0|
2n2 n
Proof of Lemma E.3 Since both FGD and frop involve infinite-lnngth Markov chains, the initializa- tions do not matter and
decouple the stochasticity of X; and Kg In particular,
E | 2 = 2 D E iign (Ø(X.) - =(xx""))) - E[((x.) - (xx |||
s (Q' 2/Q/ + Q22
where
Q E 2 Σ isn (6(x;) - Bl((
TrCov(o(X1)
V log Z(1)*)
G²
Q/2 E Σ isn (o(xp"")))
B [x )1)
Tr Cov (i ][ginit]]
E[Tr v log Z ((ginit)
7²
n In the computations above, have used the relation V3 log (0) Covx [x(X] and the assumption supsem tr tr(V? log Z(0)) o² from Al This implies the desired bound. D
42

---

Lemma E.4. Under Al E 1pop 101 =
2nm + L2r)²) B 1l0init 11.
Proof of Lemma E.4
Recall that
frod --
(V log Z(0*) V log Z(6))
By construction, foop is deterministic and from (xb*) v.* By plugging in the recursions and expanding the square, we get that
E ppop 211 E frop - (bb)(
E @(oiuii - -5-" - v log ((ginit) - V log 2)
|linit 1011² 1 - 2n { 10", V log ?(Qinit) V log ((b²)))
11² E V log Z(Oinit) V Φ log 211
E oinit 20- 1|2 2pm E | "01 112 + L322² E ginit 001
In the last line,
we have recalled infwew Amin V log ((b))
and
suPsey Amax (V3 log 7())) L by A1 and applied Lemma C.8 Combining the coefficients gives the desired statement.
F Proofs for offline SGD
We prove Theorem B.1 (which directly implies Theorem 4.3 and Theorem B.2 in this section. The key ingredient of both proofs is Lemma F.1 below, which provides an iterative error bound for the SGD-witb-replaccmmen scheme by combining different approximation bounds in Appendix t Throughout this section, we denote 3SGDw
E E x0
Lemma F.1. Under A/
A2
A3
A4 and A7 have that for S SiSM N
SGD 1.
< (1 178 (N - a n
a=oxx
I.² m))
SGD L.j-
+ n1 (eSCDruc
+
50 3m%ppmm
BB
where
m/ (11 am axxOx 1.2 m² > 0.
Proof of Lemma F.I We first remark that in view of Lemma the projection step Algorithm
does not increase 22g so suffices to bound & 8SGDw as if projection is not performed on dlrGDw
To apply the results from Appendix E we identify ginit = SGDw and r7 = 7h- which allows us to
(,j-1
write SGDw gSGDw, This also implies Ellitnnt 1 o and _init
En,mp (E) < Evmn., (e).
43

---

By adding and subtracting the auxiliary gradient updates followed by expanding the square, we obtain
Ot.
SGDw
E
DGD
+ 0D
0& + 00 0POP
0POP 1/11
E
+ E 6 CD
|GD
2 + E B 00 |
+ E goop
11
2E
( (O
0GD
GD
DDD) + 2 D
GDD
00D
0POP)
2 {E m3
GDD
ginit F fooP - 36 + 2 E (0
G
BGD goop)
m
+ 22E (E(OmD
0
An foop
) + 2 k0 goop
goop
4
(6)
4n2 (a² + mm
2 I [(BCa) n/! ( oC v DSCDW m. (c)
+ 0²
VB
4n
(1 2pm 1221 (21))000000 1tr111
2111 02 + m22m
1m 0²
2
[[Ben)1( Ox v JSGDW nmm.t (e)
/B
/n
2771 VO2
21/ [[Ben]
+2
+0 vn
VB
1m +
2Th
a oCx
(SGDw
amm.to + 6--1
2n10
v
21/(
00
8SGDD
(mm.te(e)) (6))
SGDW
2pm V(1 (1p2 + 1221))050D7
+
+22
2n1
V(L
-umm + )2n)))800D 1850
Va
(0)
2 1 2pm
Lnk n/a0 O² + 2m oCx / C
2pm I2 x 6t.j-1
2nd 2n 02 + m2 + () oaxx
+ 2
th m o0x
(e)
SGDW (e) +
VB
2 /
2pm + LL
+ 11 (imm. (c) -pup + T2n +
x
FSGDD
vn
A(0²2 + mm)
(e (e))²
5N
2
4 4/02 + 22
SGD (ip
+ 17/
B
B
v BB
80 o0 + x2mm
40g SCDw n.mm
(c)
B
VB
=: (Ai) x SGDD i-j-1
+ (A2) x v
JSCDD + (Aa)
In (a), we have expanded the square, used F., defined in Lemma E. and An defined in Lemma E.2 and noted that grop z/" is almost surely constant given ginit in (b), we have applied Lemmas
A4 and A7 and used Va / < va + vb for a, 6 > 0; in (c), we have grouped the terms by powers of SGDW bounded the indicator function from above by and used B < n to replace n in the denominator by B. While the computation above is complicated, we remark that the key steps are taking the conditional expectations for the cross- terms in (b). which gives us a tighter bound than directly applying triangle inequality of the form E| 1² < (v E | + (F))Y To further simplify the bounds, seek to bound each
E.1 E.2 E.3 and E.4 under Al A2 A3
44

---

coefficient by square, which yields
(A1) (naa + V1 2pr + TaTe
(A2) s 0x + /1 2pm + Lin )
SGDW
(e)+
+ 40 2Kuaa
x 1/s
@n.m,tte
VB
(As) s n/ (E (e)) + _02 + 4x2.m nmmttee
21o² 1772
vB
50 + Srieem 2
S m
SGDW (u. +
vB
This implies
SSGW
$ (A1) x o.j-1 + (Az) x V 156 + (As)
SGDW
((nam Ox + V 2pm + Lni
5SCDD + T) (, (c) + 50 + 5mierm
/B
Now note that since 1 I L by the definitions in Al 2pme L' S 2Lm, LL s 1. By using vI S for all x S L, we get that
12 pr +
2pm + LAT I
2 ne
Substituting this into the earlier bound and taking a square-root, we obtain the desired bound that mT
V (SGD I (1 (1- 17t (M- a=,
(SSDD + 7e = /
SSDD (E) +
5 + 5Kugm
VB
Moreover, since T, 2 1 by definition from A1 we have
1 1- 1-n (u a a0x 2 m1
L2 =
(/2 - 1) + (V2L u)m + a aaaaaCCCp oCxie 0,
which finishes the proof.
F. Proof of Theorem B.1
Under Al
A2
A3
A4
and
A7 Lemma implies
DSGDD Gg
I
im Ct 8 L²C²
SGDw 20) v 655mn + Ct-8
onT
2
for
S1S and S S N, where we have used j'm 1 am dm 1/t Ct-8 and
enm,,te (<)
50 5kmmm
SGD n.m.T. (t) +
50 5kumm
SGDw
VB
VB
n.
By an induction on I,...,,, .....,, N, we have
JSGDW < (1 iim B +
12c2 -20))
N
SSGD 1.0
+ Co
SGDW 8
Ex (1- ium Ct B
N
L²C²2 22 j-1
j=1
By noting that 0,0
I-N, almost surely for 1. 2 2 and using another induction on L I,...,T.
JSSDD T.N
I Qo /
/SSDDw + SGDW 0,0
T Σ'= Q,4
(18)
where
Q II (1
L²
228)
N and A, 2===1 (1 (1-
L2C² f-1
2
2
we also have that 1 C1-B 8 L² 122 > This allows us to apply
Note that by Lemma
F.I
Lemma
C.3 to obtain
No < exp 11 Nom CiP1-
NL202
(T +1)) (T)) = ET
99
2
45

---

To control Σi= Q.A,I recall that 3 E [0, Pm > 0, 12c²
2 > 0, and that
..N
exp
Npm
2 P1 P1-a(I + +1) 2
We now apply Lemma
C.3
B & 2 1), then
E Qe A.
2 C
all 23 Tripp + (1 + jim 1 +2)
E2 E..
12C²
If 3 2. i.. 23 = we have
T En Qi A,1
4
c e1144)1/2 + +N + C) 9 - (T+ (+1) E.N.N
EmCN
Ein C.N.
E
3 1, we get that
3V(1 + 4202 2 N-1 2212 log(T + 1)
T Σn
Q.
4
pm
(7 + 1)(mm
Substituting the bounds into
18
get the desired bound that
/
/SCDD is upper bounded by T.N
AMCN 4e
ET.
SS + n.
+ 2N(1 + Pm. (T + E .T.N
0,0
C
1 2
for B
3N(1 + 1202 1 N-1 22 1og(T+11)
TNN /SDD + Co
00.0
4
3 (T 1++1(Am
for B =
Pmc
ET.N
SSDD 0,0
+ Co
2201
Aae ((1-) (2+1)
3 + Pm Cy N1 (I'+ 2)
E
otherwise
Cm
L2
F.2 Proof of Theorem B.2
E to LSGDo we Piu condition on S which in particular fixes S the last size- B subset of [m|] chosen. We then identify ginit diSCDo 1) 1)2 and the dataset used Di, == (X; i ST,)), which allows "t.j-1*
Recall that 8SGDo = E SGD. - 10 To apply the results from Appendix [g
identify Vi.j AGD the full-batch gradient descent update using Di,j- Meanwhile, we note that almost. surely 0GD = m.B the SGDD-with-replacmmen iterate that uses the full dataset Do Observe that the proof of Lemma F11 holds with 55 replaced by any random initialization ginit possibly correlated with XI,..., Xn. which allows us to obtain
SCDo
SSGDo Lg
< (1- ( a oC,
La
m)
(8SCL + 1) (
S (e) + 5a 5maam
/B
Since the recursion for & is identical to that of 8SGDW in Lemma F.1 the proof of Theorem 4.3 follows directly, thereby yielding an identical result for oT,N as with @SGD in Theorem
G Proofs for tail probability bounds in offline SGD
We present the proofs for results Appendix B.3 that control the tail probability terms @SGDw and .SGDw T
Proof of Lemma B.3 For > 0, let N₂ be the 8-covering number of V, which satisfies No S (1 + 2/5)) (Example 5.8, [50). Note also that by the Jensen's ''s incquality applied to [X]]
and Assumption A6 there exist some oms Sm > 0 such that, for any R with ||2||| S &m.
Ele² (Blo(Kg) (X.)) (x.i)1) < Ele² (0(K7 (X (X,)))) < 1=111/2
46

---

Meanwhile under A5
recycling the proof of Lemma 3.1 of [2]] shows that if 0m5/ VD <
om
P sup NEV
Σ c-1
[[((Kg (X))
[x.] B[o(K]] (X.)) > 3Cmd) I 2Nopexpp
nC
2po
I 2(rw) ) exp (p (ogg(1 28-
nC 82
2po
Since the probability above an upper bound SS
n.m.T (3Cm5), we get that if Cm vD < o Sm
T (3Cm 90 6² + mim
Cm
vp
S 99 8² + miym 2
21v 2) (rw)
2
(v [v- 2)p
log(1 + 2---)-
n/V 2) 82 2upo t.
exp
Recall that by assumption, log
Sa
We now choose
ptu
8
Cm
Om
2v ppt
v-
log n
n
Fm Cn
Vp*
x
(v 2)p + 2v
2
log n
which implies
inf 600
Evm.m.
SGDW
(t) 2 x
SGDW Eun.mm, (0C (3Cmd))
90 20 2)p 1 2v/) log
kyom 2 - (rwv)
(w=21p 21p
(1+ + 28-1)
(m-20p 20p
exp
(v
2)p 2v
2
log m
(v
2)n
9 p(u - 2)p + 20) log
22m
2 2 (rv) 10=2)2 212 1 Gmp (2 2)p 20) Vlogn
2C 2)
V
(u-21x
+
900 - 2/p + 20)logn
(v 22m
+ N 2 2 (rv) (u-2)e 11+
20m (v- -2)1/2
(v-21e 21p
(u-2)p
2n
omp
(2((1 2)p 201
10mmp(le 22p + 20)
(w-2)
(rv)
(u-2)0
2Cm (v 2/1/2
(w-22)
log n
2-2 2
1/2 pmpl/2((
amp
2)p 2//
Taking a squareroot across and using Va + b S va+ for a, b> 0 gives the desired bound. The limiting result follows by substituting this bound into Theorem B.I
Proof of Lemma B.4 Let 8 and Ns be defined as in the proof of Lemma B.3 with No < (rw + 2/0))* Let (v7) [ be the centers of the covering d-balls. The covering-bai argument of the proof of Lemma 3.1 of [2l] shows that
BSGD (3Cm
s IP
sup
Σn 1=1
[.] - B[O(K (x.))] 3Cn,))
new
.Na IP
E"_
E B[ x.] E [[ (x.)) 2 C..))
By a Markov's inequality followed by the Burkholder's inequality applied to an average of i.i.d. sum- mands (see e.g. [5 for v > 2), there exists a constant C, > 0 depending only on such that
E E. BI [x.] E E(O(KT (x.)i
D <
n2 8%
E||E[A(KT] (X)) [x]] F[O (XIIIl
1=1
Namy
(rw)p(1 + 28 1yp
ne 12 8
n2/20% 8"
47

---

where we have used assumption A4 in the last line. This implies
(3C. = 00 + memm (nnmir((C.n (V-2)/e
(r 21v
S 90 6² ki (rv)
"r 218 (-((-2)
(1 + 26
n
60-2
10--
Choosing 8 = 2(u24(u-21p)
< 1, get that
inf <>0
SGDW
(e)
S
E Eva,m, (3C
SGDW
S 90 m n
+1 + meg (rv) (u-210
20v
C.- C-(v-2)g
(u-21p
(v- 21v
72
(90 Kwym (re)
(0-2)2 C (M- (V-2)) 2)3 12-2)2
[o- 23
219
Taking squareroot across and using vo b S va + vb for a, b gives the desired bound. The limiting result follows by substituting this bound into Theorem B.T
Proof of Lemma B.5 average, we have
By Markov's inequality and a Jensen's 's inequality with respect to the empirical
En B|le|o 1 peann (xx)) Xs, M
E
(o(K
Km
sSaD
(X1)
S
sup JE[N]
ne
Azys
sup JEME
78C
Mcanwhile by triangle incquality and the ergodicity assumption, have
Arjo S Vsopy
B <B||E[e
m
(X:)
Xi,
vi-11
SGDW]
E BB0b x
E R
1t-11
E
Φb K Kapp (x1)
(t-1
20xāām
This implies g (c) s 20xām and therefore
SGDW (t)) 2 S 22+2" u= kuim (Ōx)
u-2 (r 21m
Choosing â (f(v-)mm/3vv- gives
inf
(=))),,((e)) - 21+2-=²
2(r 2)m 2 )
Taking squareroot across and using Va + S Vu+ + vb for b> 0 gives the desired bound. The limiting result follows by substituting this bound into Theorem B.I
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract summarizes the theoretical results of our paper. We cleary mention that while CD can achieve these rates, assumptions are needed to guarantee this. We also mention the model class studied in this paper, namely (unnormalized) exponential family distributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mention limitations multiple times in the main body of our work: after introducing the assumptions in Section 3.1 we mention that spectral gaps may be verified for heavy tail distributions, or act numerically unfavorably for multimodal distributions, and that constants may large in practice. In the discussion (Section O we reflect back on these limitations, and we mention the limitations of our considered model class (unnormalized exponential families).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
49

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All of our theoretical results are formally proved in the supplementary material. In the main paper, we provide some proof sketches (discussion of the tail term in Section 4 paragraphs after theorems in section 3) to provide high level intuitions behind the proots. All of the theoretical results provided by our work are proved the supplementary material, usually by invoking (and referencing) more atomic lemmas, also proved in the supplementary material. All of our theorems and lemmas are stated with the assumptions they require.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
50

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments, and thus no code or data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
cablic/guidess (egaal//uuides/oooeebbbssssssss peeiionPoccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ctips.cc/public//eee sewpaidddde//o/eubmlmim /wtp///ooeeSeseeeeeeeeeeee wetpimiissioooooiiiocco
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
51

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/s//eerrips..cpppbb/////ta
Answer: [Yes]
Justification: As a theory paper, we believe that our work does not breach the code of conduct. With this work, we aim to advance the understanding of statistically efficient algorithms, domain which has the potential to improve the overall compulational efficiency of machine learning algorithms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
52

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We believe that our work will not have the negative impacts mentioned (e.g., disinformation, surveillance, faireess, privacy, security considerations). We believe that advancing the domain statistical effiency has the potential improve the overall computational efficiency of machine learning algorithms, which, all else left equal, could constitute a positive societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Since our work does not include experiments nor data, and only analyzes existing models, we do not believe that our work requires any specific guidelines.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
53

---

Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's ' creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
54

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
55


Reviews:
[{"review_id": "cbbCXKJGny", "reviewer": "Reviewer_Hdtk", "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.\n\nThe paper proves:\n* 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\n* Thm 3.3: Online CD with Polyak-Ruppert averaging achieves (up to a constant factor of <= 2), an asymptotically optimal rate.\n* 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.", "questions": "* What is $\\\\tilde{\\\\mu}$ in Theorem 3.2? Do you mean $\\\\tilde{\\\\mu}_m$?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "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 \nresults 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.\n\nVery minor:\n* 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].\n* 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.\n* On line 95, the idiom “silver lining” is used incorrectly. It should indicate something positive, rather than something negative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and in particular for challenging us regarding the significance of our work and its relevance to the NeurIPS community, which will help better position our contributions. We explain further the relevance and significance of our results below. We will make these points clearer in the camera-ready version of the paper.\n\n**On the relevance of our work to the NeurIPS community** \n\n- The broader question our work addresses is the following: *What are the statistical estimation methods that are **sample efficient**, e.g. that require as few samples as possible to reach a good accuracy*? We believe that this question resonates which a sizeable part of the NeurIPS community, especially in fields where samples are expensive to acquire (making sample efficiency crucial). An example of such fields is **Simulation-Based Inference** (SBI), a set of methods performing parameter inference in scientific models with intractable likelihoods. SBI is popular in multiple scientific disciplines such as particle physics and neuroscience, and has attracted significant attention in the NeurIPS community. The data space is challenging, yet often lower-dimensional than domains like images (which are now indeed dominated by other estimation methods like diffusion models), and acquiring samples often requires running expensive simulations, making sample-efficient methods particularly important. Interestingly, [20] designed an SBI method using CD which achieves state-of-the-art sample efficiency for multiple problems. Given such facts, we believe that the results established in our work work are relevant to inform modern machine learning applications and to the NeurIPS community in general.\n- Moreover, we believe that the sample-efficiency properties of CD established in our work yield an important conclusion: in exponential families, CD is near-asympotically **statistically** efficient, which shows the potential of CD in statistical estimation. In order for CD to be **computationally** efficient and thus usable in practice, the number of MCMC steps $m$ should not be too large: this calls for the design of fast-mixing, model-dependent Markov kernels, thanks to which CD may be shown to be an end-to-end efficient estimation technique.\n\n\n**On the significance of the theoretical improvements**\n\n- With the improvement from the $O(n^{-1/3})$-consistency shown in [21] to the optimal $O(n^{-1/2})$ rate established in our work, we place CD at the same level as other well-known statistical estimation methods for unnormalized models like Noise-Contrastive estimation and score matching, which both enjoy $O(n^{-1/2})$ consistency. Thanks to this new bound, CD is now proved to be asymptotically competitive with such methods, making CD a theoretically valid alternative in large data regimes. This conclusion is only possible because of our new bounds, and could not have been reached from the results of [21]. We thus believe that this rate improvement is important.\n- In addition to improving the **rate** of convergence of CD, we also show that the asymptotic variance of averaged online CD (e.g the multiplicative constant associated with the leading $n^{-1/2}$ term) is optimal up to a factor 4. This result improves over the asymptotic variance of score-matching (which includes other problem-dependent smoothness factors and a suboptimal Fisher information exponent [8]) , and over the  Noise-Contrastive Estimation result (which requires knowing the unknown data density to reach similar results [6], and otherwise can scale exponentially poorly with dimension [5]). Analyses of asymptotic variances are common in the machine learning literature, have important empirical implications regarding the sample-efficiency of the associated methods. We believe that our results complement other known results in an informative manner. We are happy to make these points clearer in the camera-ready version of the paper.\n    \n**Regarding assumption A4:** The reviewer is correct. We we provide some additional comments regarding cases where A4 is satisfied for $\\nu = 2$ (which is needed to obtain the asymptotic consistency of [21]) but not for any $\\nu > 2$ (which is needed for our results to hold). In such cases, the Markov kernel is such that $\\phi(K^m_\\psi(x))$ has only finite second moment and unbounded higher moments, which has a much heavier tail than most typical practical regimes (for example, this implies infinite kurtosis). In particular, violation of A4 is a known pathological regime in the Central Limit Theorem literature, where the empirical average of these random variables converges to a normal distribution, but obtaining finite-sample bounds is difficult (see e.g. [57]). Since, unlike [21],  our results involve finite-sample controls on sample averages of gradients in a much more complicated optimization regime, we do not expect to be able to circumvent such known difficulties. One may indeed try to relax the bounded $\\nu$-th moment assumption by a more involved analysis of the dependence, but we believe that our assumption  suffices for many practical applications: Indeed, A4 for any $\\nu > 2$  will be satisfied for Markov kernels with subexponential tails. Moreover, the tail of a Markov kernel can often be checked based on its specific form.\n\nWe apologize that these points were not made sufficiently clear in the submission, and will add these comments in the camera-ready version  for contextualizing A4.\n\n[57] Friedman, N., Katz et. al Convergence rates for the central limit theorem. PNAS\n\n**Minor** We also thank the reviewer for pointing out some minor inaccuracies. In theorem 4.2, we $\\tilde{\\mu}$ was indeed supposed to be $\\tilde{\\mu}_m$. We will correct the use of \"silver-lining\".\n\n---\n\nWe have done our best to address your questions, and we would be happy to address further questions in the discussion. If we have done so, we would be grateful if you would consider increasing your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vvsgOpnzWF", "reviewer": "Reviewer_yRNH", "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.", "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})$?\n\nAre there plans to complement the theoretical findings with empirical validations?", "limitations": "The authors listed the limitations and future directions in their discussion section", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n- 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.\n- 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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments. We address their concerns below.\n    \n**Regarding the regularity conditions required to achieve the $O(n^{-1/2})$ rate** One of the assumptions made in our theorems regarding online CD  is that the parameter space $\\Psi$ is compact. Under this assumption, the log-partition function is smooth (e.g. $C^\\infty$) and with bounded derivatives. This boundedness is what we mean by \"regularity conditions\", and is critical to obtain our upper bound on the variance of the averaged online CD iterates (see Lemma D.1 and D.2 of the appendix).\n    \n**Regarding empirical validation** We thank the reviewer for their suggestions. We agree that experimental validation of the theory is helpful and will add a synthetic experiment where the ground truth is known in order to exemplify the claims made in our theory.\nWe follow the setup of [21, Section 4.1] and consider the following model:\n\\begin{align}\n    p(x; \\psi) = \\mathcal  N(\\psi, \\Sigma), \\quad \\quad \\Sigma = \\begin{bmatrix} 1 & 0.5 \\\\\\\\ 0.5 & 1 \\end{bmatrix}\n\\end{align}\n\nfor $\\Psi = \\left \\lbrack -0.5, 0.5 \\right \\rbrack^2$, which is an exponential family for $\\phi(x) = \\Sigma^{-1} x$, $\\log Z(\\psi) = \\frac{1}{2} \\psi^T \\Sigma^{-1} \\psi$,  implying $\\nabla_{  }^2 \\log Z(\\psi) = \\Sigma^{-1}$. It can be shown (see discussion below) that assumptions A1-A6 are verified for this model. While other, more complicated models could be shown to verify our assumptions, for this specific model, the quantities involved in the bounds can be computed explicitly (or upper bounded) explicitly, which allows us to validate our bounds.\n\n**Experimental setup** We run 500 different experiments with different seeds to compute an empirical estimate of $\\delta_n = \\mathbb{ E } \\| \\widehat{ \\psi }_n - {\\psi}^{\\star} \\|^2$ up to $n = 2000$ samples, where $\\widehat{ \\psi }_n$  is the estimate of $\\psi^{\\star}$ obtained by the online CD, online CD with averaging, and offline CD estimators, respectively. We then plot this empirical estimate as a function of the number of samples $n$ , and compare it to both our upper bounds of our paper obtained in each setting, as well the Cramer-Rao lower bound. Our learning rate schedule is $C n^{-\\beta}$, with $C = 0.1$ and $\\beta = 0.6$. For offline CD, we make $5000$ gradient steps using the full dataset, and run the experiments for 10 evenly log-spaced values of $ n $ between $ 100 $ and $2000$. We use $m =20$ MCMC steps.\n\n\n**Plotting lower and upper bounds** In the pdf included in the general comment, we plot:\n- The full non-asymptotic upper bound related to the last-iterate online CD estimator\n- The leading term of the non-asymptotic upper bound related to the averaged online CD estimator (for simplicity, due to the complexity of the higher-order terms)\n- The non-asymptotic in $n$, but asymptotic in $T$ upper bound related to the offline CD estimator (for similar reasons).\n    \nIn this example, we see that the bounds for online CD are tight. While the rate of offline CD is near-optimal (and thus tight), the bounds are looser than in the online case, which is due to the multiplicative constant in front of the leading term. However, our bounds for offline CD are still able to provably explain how offline CD is more robust to transient effects related to bad initialization and smoothness, as mentioned in the rebuttal to reviewer ouZy. Moreover, we see that offline CD performs competitively compared to online CD, which calls for more investigations of the offline setting. Further work will investigate how to tighten these bounds by, in particular, attempting to improve the constants.\n    \n \n**Additional details for the model**\nIt can be shown [21] that $\\sigma^2 = 2.67$, $\\mu = 0.67$, and $C_{\\chi} \\approx 1.84$, and that $\\alpha \\leq 1 - \\lambda_{\\min_{  }}(\\Sigma^{-1} / 2) = 0.67$. For $m \\geq  \\lceil 3.5 \\rceil = 4$, Theorem 3.2 will hold. Using the formulas present in the proofs, and the formulas for the cumulants of a Gaussian random variable, we can show that $||\\log Z||_{3, \\infty} \\approx 10.9$. \nFor online CD with averaging, we also need $m(n) > \\frac{(1 - \\beta) \\log n}{2\\lvert \\log \\alpha \\rvert }$. Assuming $n = 2000$ and $\\beta =0.6$, we need $m(n) > 3.8$, which will hold for $m(n) \\geq 4$. Finally, for offline CD, Assumption A4 to A6 will be satisfied [21].\n\nIt can be shown that $k_{\\psi}^{m}(X)$ is a Gaussian random variable with mean $\\psi ( 1 - \\rho^{2m}) + {\\psi}^{\\star}$ and (component-wise) variances $1$, yielding (using formulas for the centered moments of Gaussian random variables and $(a^2 + b^2)^3 \\leq 4 (a^{6} +  b^{6})$), we obtain $\\kappa_{m, 6} \\leq \\lambda_{\\max_{  }}(\\Sigma ^{-1}) (\\mathbb{ E } \\| k_{\\psi}^{m}(X) - \\mathbb{ E } k_{\\psi}^{m}(X) \\|^{6})^{1 / 6} \\leq 4 \\cdot 12^{1 / 6} \\approx 4.6$. Finally, it can also be shown that $\\mathbb E [ k_{\\psi}^{m}(X) | X]$ is Gaussian with mean $\\psi ( 1 - \\rho^{2m}) + \\rho^{2m}X$ and component-wise variances $1 - \\rho^{4m}$. Straightforward derivations can show that assumption A6 is verified for $\\sigma_m = 2$.\n\n---\n\nWe have done our best to address your questions, and we would be happy to address further questions in the discussion. If we have done so, we would be grateful if you would consider increasing your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TVEZLhClsw", "reviewer": "Reviewer_ouZy", "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.", "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.\n- 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.\nMinor comments:\n- Eq (5). Definition of $\\mu$ is incorrect. Strong convexity parameter should be the minimum eigenvalue, instead of the operator norm.", "limitations": "The paper addressed limitations of the results adequately.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n\nI'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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review. We address the reviewer's concerns below.\n    \n**Regarding the benefits of offline CD** We agree that the analysis of offline CD is more delicate than the one of online CD. On the other hand, we stress that while online CD is asymptotically optimal, *offline CD can perform better than online CD in the nonasymptotic regime*: indeed,\n- Online CD **without averaging** (Theorem 3.2) is sensitive to the choice of the initial step size: below $2 \\tilde{\\mu}_m$, the convergence rate is smaller than $O(n^{-1/2})$. Above $2 \\tilde{\\mu}_m$, the bound contains a transient higher-order term which scales exponentially with the smoothness $L$ of the log-likelihood gradient and linearily with the initialization $\\sqrt \\delta_0$. This higher-order term can affect the performance of the estimator in the non-asymptotic regime.\n- Similarly, for online CD **with averaging**, the $o(1/n^{-1/2})$ term in Theorem 3.3 contains multiple higher-order terms (See Lemma D4, D.5, D.6) that scale exponentially with $L$ and other smoothness parameters of the problem, and linearily with $\\sqrt \\delta_0$.\n- Offline CD (Theorem 4.2) also contains similar transient terms as in the online case. However, in contrast to online CD, these terms vanish for a *fixed* number of samples $n$ by making the number of gradient steps $T \\to \\infty$. In Lemma 4.3, for instance, the only remaining term is $C'(\\kappa_m, p, \\nu, m, \\Psi, \\beta)(\\sqrt{\\log(n) / n} + 1 / \\sqrt{n})$ (assuming $B=n$), with  (see Lemma B.3, full statement)\n    \\begin{align*}\n    C'(p,\\nu,m,\\Psi,\\beta) = \\frac{8(1+ 5 \\sigma + 5\\kappa_m)}{\\tilde \\mu_m} \\times\n    \\Big( 3 \\sigma_m \\sqrt{p(p+\\nu-2)} +  \\kappa_m\n    (2 r_\\Psi^p )^{\\frac{1}{\\nu-2}} \\Big( 1 + \\frac{2 C}{\\sigma_m (p^2 + (\\nu-2)p)^{1/2}} \\Big)^{\\frac{p}{\\nu-2}} \n    \\Big)\n\\end{align*}\nFor Markov kernels with light enough tails, we can set $\\nu - 2 = 2 p$. Considering the worst-case initialization scenario  $\\delta_0 = r_{\\Psi}^2$, we obtain\n\\begin{align*}\n    C'(p,\\nu,m,\\Psi,\\beta)= \\frac{8(1+ 5 \\sigma + 5\\kappa_m)}{\\tilde \\mu_m} \\times \\Big( 3 \\sigma_m \\sqrt{p(p+2p)} +  \\kappa_m 2^{\\frac{1}{2p}}\\delta_0^{\\frac{1}{4}} \\Big( 1 + \\frac{2 C}{\\sigma_m (p^2 + 2pp)^{1/2}} \\Big)^{1/2} \\Big).\n\\end{align*}\n    \nCompared with the online CD bounds we see multiple benefits:\n- This bound depends only sub-linearily on $\\sqrt{\\delta_0}$, unlike some of the constants of the online CD bounds, which depend linearily on it. Moreover, for subexponential $k_\\psi^m$, the dependence can be arbitrarily weakened to $\\delta_0^{1/2a}$ by setting $\\nu - 2 = a p$ for some $a > 2$. Offline CD can thus be provably less sensitive to the effect of initialization than online CD, in moderate sample size regimes where $\\sqrt{\\log n / n} \\simeq 1/\\sqrt{n}$ and higher-order terms still matter.\n- Moreover, with such choices, $C'$ only depends polynomialy on the parameters of the problem and is independent of L. This is in contrast with the constants of online CD, which contain terms that exponentially grow with the initial learning rate $C$ and $L$, translating the fact that a too large $C$ can lead to a transient exponential blowup of the loss. By allowing $T \\to \\infty$, offline CD thus prevents this possible exponential blowup.\n    \n    \nIn summary, in subexponential tail scenarios, offline CD allows to control smoothness and initialization related transient terms of the online CD bounds at the cost of increasing compute ($T \\gg n$, compared to $T=n$ for online CD), and asymptotic suboptimality. This is one reason why we believe this result is a valuable addition to the paper, despite the technicality of the proof. While alluded to in the end of Section 3, we agree that this argument is not presented with sufficient clarity the paper, and we thank the reviewer for challenging us in that regard. To address this, we will highlight the dependency of the higher-order term of Theorem 3.3 in the parameters of the problem, and will make a thorough comparison between the online and offline CD bounds in Section 4, as done above. We welcome further discussion with the reviewer on this topic.\n    \n\n**Regarding the clarity of section 4**: We agree that Section 4 is technical, and that it is crucial to increase its accessbility to a broad readership. To this end, we will take the following actions:\n- Introduce Lemma 4.3 (which is our strongest final result for offline CD) as the main result (Theorem) of Section 4. Consequently, the tail probability terms and Theorem 4.2 will only appear as part of a proof sketch for this Lemma.\n- Delegate Lemma 4.4 to the appendix, with a mention in the main paper.\n- Rely on the extra page for camera-ready papers to add proof sketches for section 3 and 4  and summary tables for rates (provided to reviewer Fohj).\n    \n    \n**Other questions**\n- We thank the reviewer for spotting the incorrect definition of $\\mu$, and will fix this in the updated version of the paper. The extreme-value theorem argument justifying its existence still applies, thanks to [56].\n- The reviewer is correct on the origin of the inflated factor of 4 in our bound. We will add a discussion about it in the paper.\n    \n[56] G. Harris and C. Martin. The roots of a polynomial vary continuously as a function of the coefficients. Proc. Amer. Math. Soc. 100 (1987), no. 2, 390–392.\n\n--- \n\nWe have done our best to address your questions, and we would be happy to address further questions in the discussion. If we have done so, we would be grateful if you would consider increasing your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sjRseljD48", "reviewer": "Reviewer_Fohj", "summary": "This paper analyzes the contrastive divergence algorithm for learning exponential family distributions.\nBoth 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})$.", "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.", "limitations": "There is no specific limitation noted in the paper.\nIt'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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Efficiently learning unnormalized model, especially exponential family distributions, is an important problem. \nAnalyzing 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.\nI 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.\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We address their concerns below.\n\n**On the technicality of the paper** We agree that the paper in its current form is technical, and agree that increasing the accessibility of our work to a broad readership is important. The main message is the following: under suitable assumptions,\n- Online CD can converge at a speed $O(n^{-1/2})$ (optimal rate), and the asymptotic variance of averaged online CD is $4$ times the CRLB. However, both variants contain transient higher order terms scaling exponentially badly with the smoothness parameters of the problem and linearly with the initialization $\\sqrt \\delta_0$.\n- Offline CD, on the other hand, converges at a near-optimal $O(\\sqrt{\\log n} / \\sqrt{n})$ rate, but, for a fixed sample size $n$, the higher-order terms vanish as the number of gradient steps $T \\to \\infty$. Consequently, offline CD can be provably more robust than online CD to smoothness and initialization (see the rebuttal to reviewer ouZy for a detailed discussion).\n\nIn conclusion, online CD is asymptotically near-optimal, and asymptotically better than offline CD, while offline CD may perform better in the non-asymptotic regime, where higher-order terms due to initialization and smoothness play a non-negligible role. This matches the expectation that multiple passes through the  data can improve statistical efficiency for CD. This discussion is summarized in the following table (which we thank the reviewer for suggesting)\n    \n| Algorithm   | Rate | Leading term constant | Higher order terms | \n| -------- | ------- | --------------------- | --------------------- |\n| Online CD ($\\beta=1$, Last iterate, A1 to A3 ours)  | $1/\\sqrt{n}$ if $\\tilde{\\mu}_m C>2$, $1/n^{-\\tilde{\\mu}_m C / 4}$ otherwise   | $2\\tilde{\\sigma}_m C \\frac{\\tilde{\\mu}_m C}{\\tilde{\\mu}_m C - 2}$ |  Exponential in $L$, linear in $\\delta_0$\n| Online CD (Averaged iterates, A1 to A3, ours) | $1/\\sqrt{n}$                                           | $2\\sqrt{\\text{tr}(\\mathcal I(\\psi^\\star)^{-1})}$ | Exponential in $L$, linear in $\\delta_0$\n| Offline CD (Last iterate, $B=n$, $\\nu - 2 = 2p$, A1 to A6, ours)   | $\\sqrt{\\log(n)}/\\sqrt{n}$  | Indep. of $L$, sublinear in $\\delta_0$  | $o_{T}(1)$\n| Offline CD ($B=n$, Averaged iterates, [21] A1 to A6 with A4 only for $\\nu = 2$)  | $n^{-1/3}$ (Asymptotic)  | $?$ | $?$\n\nWe will improve the accessibility of the paper by taking the steps outlined in the general comment.\n    \n    \n**On the term near-optimality**: We use \"near-optimality\" to describe online CD because the factor of 4 scaling the CRLB is a universal constant, (independent of the parameters of the problems like smoothness or dimension).\n\n**Comparison with NCE** We thank the reviewer for suggesting to compare our results with other estimation methods for unnormalized models. The asymptotic variance of NCE is provided in [6, Theorem 3]. Its expression depends on the noise distribution used. More explicit formulas can be obtained for specific choices of the noise distribution:\n- If the noise distribution is  Gaussian, then it can be shown that for specific choices of data distributions, the asymptotic variance of NCE grows exponentially with the dimension of the data [5]. This is in contrast with our obtained bounds which do not contain any explicit exponential scaling with the dimension.\n- If the noise distribution is the unknown data distribution, then as the number of noise samples grows to $+\\infty$,  the asymptotic variance of NCE approaches 2 times the CRLB [6, Corollary 7]. However, attaining that limit requires knowing the data distribution, which defeats the purpose of estimation.\n\n(We additionally compare with score matching in the next comment)\n\nWe can thus see that both NCE can significantly depart from optimality (not just by a universal constant), which is unlike (averaged online) CD. On the other hand, CD requires assumptions for its bounds to hold, and in particular a lower bound on the number of MCMC steps, which can be large in some instances. CD can thus be more computationally expensive than these methods. Our point is thus not to argue that CD is uniformly better than NCE, but is able to trade-off computational power for statistical efficiency, which is useful when acquiring samples is costly.\n    \n**On examples satisfying the assumptions:** We discuss the assumptions in m\n- Assumption A1 and A2 describe the exponential family. A1 will hold by putting a hard limit on the parameter norm. A2 will hold as soon as the domain (not $\\Psi$) of the exponential family is the whole of $\\mathbb R^d$.\n- Assumption A3 to A6 describe the Markov kernel, with A4, A6 focusing on its tails. A4 and A6 will hold for subexponential ones, such as MALA or Random Walk Metropolis Hasting. A5 is a smoothness constraint which should hold in most cases for compact $\\Psi$. As discussed to reviewer yRNH, a Gaussian model with an unknown mean lying in a bounded subset, but known covariance matrix. This model satisfies all required assumptions, as discussed in the rebuttal to reviewer yRHN. The other examples of [21] also satisfy all assumptions.\n\n  \nOn the other hand, A Gaussian model with arbitrary precision matrix will not satisfy Assumption 1 (or Assumption A5), as the parameter set is not compact, and the log-likelihood function is not smooth. Heavy-tailed proposals (like a Student-t distribtution) are likely to not satisfy A6. Regarding Assumption A3, we expect that this assumption will often be verified. However, in some instances, $\\alpha$ may be very close to 1, requiring many MCMC steps ($|\\log \\alpha |$)  for our bounds to hold. Instances where spectral gaps a very close to 1 include multi modal distributions with unknown mode proportions ([8, Example 2]).\n\n---\n\nWe have done our best to address your questions, and we would be happy to address further questions in the discussion. If we have done so, we would be grateful if you would consider increasing your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PuzmYhpu62", "reviewer": "Reviewer_b7nK", "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. \nThe analysis also covers various data batching schemes, including fully online and minibatch methods.\nThe 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.", "questions": "See the weaknesses part.", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n**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.\n\n**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.\n\n**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.\n\nOverall, 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:\n\n**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.\n\n**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.\nConsider 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.\n\n**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.\n\nI welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments. We address their concerns below.\n\n**Regarding the techincality of the paper**  We agree that Section 4 is technical, and that it is crucial to increase its accessbility to a broad readership. We will take multiple actions to improve the accessibility of Section 4, as discussed in the general comment.\n    \n\n**Regarding Assumption 4**\nAssumption A4 is a moment assumption on the MCMC sample $\\phi(K^m_\\psi(x))$. This assumption will hold as soon as the tails of this random variable are light enough. For example, if $\\phi(K^m_\\psi(x))$ has a sub-Gaussian tail, A4 automatically holds for any positive $\\nu$ with $\\kappa_{\\nu;m} = O(\\sqrt{\\nu})$; if $\\phi(K^m_\\psi(x))$ has a sub-exponential tail, A4 holds for any positive $\\nu$ with $\\kappa_{\\nu;m} = O(\\nu)$. In fact, we just require A4 to hold for some fixed $\\nu > 2$. Characterizing the tail of this random variable can often be done by inspecting the Markov kernel used. We will add this discussion in the camera-ready version of the paper.\n   \n**Regarding empirical validation** We thank the reviewer for their suggestions. We agree that experimental validation of the theory is helpful and will add a synthetic experiment where the ground truth is known in order to exemplify the claims made in our theory.\nWe follow the setup of [21, Section 4.1] and consider the following model:\n\\begin{equation*} \\label{}\n\\begin{aligned}\n    p(x; \\psi) = \\mathcal  N(\\psi, \\Sigma), \\quad \\quad \\Sigma = \\begin{bmatrix} 1 & 0.5 \\\\\\\\ 0.5 & 1 \\end{bmatrix}\n\\end{aligned}\n\\end{equation*}\nfor $\\Psi = \\left \\lbrack -0.5, 0.5 \\right \\rbrack^2$, which we make an unnormalized exponential family for $\\phi(x) = \\Sigma^{-1} x$, $\\log Z(\\psi) = \\frac{1}{2} \\psi^T \\Sigma^{-1} \\psi$, implying $\\nabla_{  }^2 \\log Z(\\psi) = \\Sigma^{-1}$. It can be shown (see discussion below) that assumptions A1-A6 are verified for this model. Moreover, the quantities involved in the bounds can be computed explicitly (or upper bounded) explicitly, which allows us to validate our bounds on this simple example.\n\n**Experimental setup** We run 500 different experiments with different seeds to compute an empirical estimate of $\\delta_n = \\mathbb{ E } \\| \\widehat{ \\psi }_n - {\\psi}^{\\star} \\|^2$ up to $n = 2000$ samples, where $\\widehat{ \\psi }_n$  is the estimate of $\\psi^{\\star}$ obtained by the online CD, online CD with averaging, and offline CD estimators, respectively. We then plot this empirical estimate as a function of the number of samples $n$ , and compare it to both our upper bounds of our paper obtained in each setting, as well the Cramer-Rao lower bound. Our learning rate schedule is $C n^{-\\beta}$, with $C = 0.1$ and $\\beta = 0.6$. For offline CD, we make $5000$ gradient steps using the full dataset, and run the experiments for 10 evenly log-spaced values of $ n $ between $ 100 $ and $2000$. We use $m =20$ MCMC steps.\n\n\n**Plotting lower and upper bounds** In the pdf included in the general comment, we plot:\n- The full non-asymptotic upper bound related to the last-iterate online CD estimator\n- The leading term of the non-asymptotic upper bound related to the averaged online CD estimator (for simplicity, due to the complexity of the higher-order terms)\n- The non-asymptotic in $n$, but asymptotic in $T$ upper bound related to the offline CD estimator (for similar reasons).\n    \nWe see that the bounds for online CD are tight, while the bounds for offline CD are looser, which is due to the large multiplicative constant in front of the leading term. However, our bounds for offline CD are still able to provably explain how offline CD is more robust to transient effects related to bad initialization and smoothness, as mentioned in the rebuttal to reviewer ouZy. Moreover, we see that offline CD performs competitively compared to online CD, which calls for more investigations of the offline setting. Further work will investigate how to tighten these bounds by, in particular, attempting to improve the constants.\n    \n**Additional details for the model**\nIt can be shown [21] that $\\sigma^2 = 2.67$, $\\mu = 0.67$, and $C_{\\chi} \\approx 1.84$, and that $\\alpha \\leq 1 - \\lambda_{\\min_{  }}(\\Sigma^{-1} / 2) = 0.67$. For $m \\geq  \\lceil 3.5 \\rceil = 4$, Theorem 3.2 will hold. Using the formulas present in the proofs, and the formulas for the cumulants of a Gaussain variable, we can show that $||\\log Z||_{3, \\infty} \\approx 5.95$. \nFor online CD with averaging, we also need $m(n) > \\frac{(1 - \\beta) \\log n}{2\\lvert \\log \\alpha \\rvert }$. Assuming $n = 2000$ and $\\beta =0.6$, we need $m(n) > 3.8$, which will hold for $m(n) \\geq 5$. Finally, for offline CD, Assumption A4 to A6 will be satisfied [21]. \n\nMoreover, it can be shown that $k_{\\psi}^{m}(X)$ is a Gaussian random variable with mean $\\psi ( 1 - \\rho^{2m}) + {\\psi}^{\\star}$ and (component-wise) variances $1$, yielding (using formulas for the centered moments of Gaussian random variables and $(a^2 + b^2)^3 \\leq 4 (a^{6} +  b^{6})$), we obtain $\\kappa_{m, 6} \\leq \\lambda_{\\max_{  }}(\\Sigma ^{-1}) (\\mathbb{ E } \\| k_{\\psi}^{m}(X) - \\mathbb{ E } k_{\\psi}^{m}(X) \\|^{6})^{1 / 6} \\leq 4 \\cdot 12^{1 / 6} \\approx 4.6$. Finally, it can also be shown that $\\mathbb E [ k_{\\psi}^{m}(X) | X]$ is Gaussian with mean $\\psi ( 1 - \\rho^{2m}) + \\rho^{2m}X$ and component-wise variances $1 - \\rho^{4m}$. Straightforward derivations can show that assumption A6 is verified for $\\sigma_m = 2$.\n\n---\n\nWe have done our best to address your questions, and we would be happy to address further questions in the discussion. If we have done so, we would be grateful if you would consider increasing your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their comments, which were very helpful to improving the current manuscript. We have addressed the concerns of each reviewer in their respective threads. We provide below a summary of the most common reviewer's comments, and of our actions taken to address them.


**Regarding offline CD and Section 4** Multiple reviewers (ouzY, Fohj, Hdtk) found Section 4 (which contains the bounds for offline CD) difficult to follow because of the technicality of the theorems. To address this issue, we will simplify Section 4 by taking the following steps:
- We will cast lemma 4.3 (The strongest bound we achieved in this section) as the main result of the section, making it a Theorem. Theorem 4.2 and the introduction of the tail probability term preceding it will be discussed as part of the proof sketch of Lemma (Theorem to-be) 4.3. We will also delegate Lemma 4.4 (which achieves worst upper bounds, but requires fewer assumptions) to the appendix.
- We will provide an extended comparison between the rates achieved in the online case and those achieved in the offline case. The main takeaway, as presented in detail in the response to Reviewer ouzY, is that while the bounds of (averaged) online CD are asymptotically near optimal, and asymptotically surpass those of offline CD, the bounds of offline CD can be tighter than the online ones in the non-asymptotic regime, where transient terms present in the online CD bounds that scale with the smoothness and initialization parameters can be dominant. In contrast, the transient terms present in the offline CD bounds can be made arbitrarily small by increasing the number of gradient steps $T$, while the dominant term remains robust to smoothness and initialization.
- Finally, we will rely on the extra page for camera-ready papers to add proof discussions for section 3 and 4, and a summary table for rates. We provided both proof discussion and tables to reviewer Fohj.

**Regarding empirical validation** Multiple reviewers (yRNH, b7nK) have suggested to add an experimental validation of the bounds, which is currently absent in the paper. To address this, we have added an experiment showing the behavior of online and offline CD for a Gaussian model (described in detail to reviewer yRNH) which we show satisfies all our assumptions. While other (more complicated) models and samplers would satisfy our assumptions, all constants involved in the assumptions can be explicitly computed (or upper bounded) for this model. In each setting (online, online averaged, and offline), we plot the behavior the empirical version of $\mathbb E \| \hat{\psi}_n - \psi^\star \|^2$ compared to our upper bounds and the lower bounds. A more thorough discussion and comparison of the methods is made in the rebuttal to reviewer yRNH.

We have done our best to address the reviewer's concerns, and welcome further discussion with the reviewers if needed.

Meta-review: This paper studies the maximum-likelihood estimator for an exponential family. It provides guarantees for the Contrastive Divergence algorithm, which uses stochastic gradient descent on the cross-entropy loss between the model estimate and empirical data.
The reviewers found the presentation clear and the contribution valuable for the NeurIPS community. I recommend accepting this paper
Decision: Accept (poster)