Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation
Authors: Bingbin Liu
Elan Rosenfeld
Pradeep Kumar Ravikumar
Andrej Risteski
Venue: ICLR 2022 Spotlight (2022)
Keywords: noise contrastive estimation
contrastive learning
unsupervised learning
theory

Abstract: Noise-contrastive estimation (NCE) is a statistically consistent method for learning unnormalized probabilistic models. It has been empirically observed that the choice of the noise distribution is crucial for NCE’s performance. However, such observation has never been made formal or quantitative. In fact, it is not even clear whether the difficulties arising from a poorly chosen noise distribution are statistical or algorithmic in nature.
In this work, we formally pinpoint reasons for NCE’s poor performance when an inappropriate noise distribution is used. Namely, we prove these challenges arise due to an ill-behaved (more precisely, flat) loss landscape.
To address this, we introduce a variant of NCE called \emph{eNCE} which uses an exponential loss and for which \emph{normalized gradient descent} addresses the landscape issues \emph{provably} when the target and noise distributions are in a given exponential family. 

Published as a conference paper at ICLR 2022
ANALYZING AND IMPROVING THE OPTIMIZATION LANDSCAPE OF NOISE-CONTRASTIVE ESTIMATION
Bingbin Liu, Elan Rosenfeld, Pradeep Ravikumar, Andrej Risteski Machine Learning Department Carnegie Mellon University (bingbinl, e elan, pradeepr, aristesk| (cs. cmu. edu
ABSTRACT
Moise-contrastive estimation (NCE) is a statistically consistent method for learn- ing unnormalized probabilisticc models. It has been empirically observed that the choice of the noise distribution is crucial for NCE's performance. However, such observations have never been made formal or quantitative. In fact, it is not even clear whether the difficulties arising from a poorly chosen noise distribution are statistical or algorithmic in nature. In this work, we formally pinpoint reasons for NCE's poor performance when an inappropriate noise distribution is used. Namely, we prove these challenges arise due to an ill-behaved (more precisely, flat) loss landscape. To address this, we introduce variant of NCE called eNCE which uses an exponential loss and for which normalized grudient descent ad- dresses the landscape issues provably when the target and noise distributions are in a given exponential family.
INTRODUCTION
Noise contrastive estimation (NCE) is a method for learning parameterized statistical models Cut- mann & Hyvärinen 2010 2012). To estimate distribution P., NCE trains discriminant model to distinguish between samples of P. and known distribution Q of our choice, often referred to as the "noise" distribution. If the function class for the discriminant model is representationally powerful enough, the optimal model learns the density ratio p=/g. from which we can extract the density since q is known (Menon Ong/ 2016, Sugiyama al.) 2012). Compared the well-studied maxi- mum likelihood estimation (MLE), NCE avoids calculating the (often intractable) partition function, while maintaining the asymptotic consistency of MIF (Gutmann & Hyvärinen 2012).
It is empirically well-documented that the choice of the noise distribution Q is crucial to both the statistical and algorithmic efficiency of NCE (Gutmann Hyvärinen 2010: 2012 Rhodes et al.
2020 Goodfellow et al.] 20044) Gao al. 2020). However, it has been observed in practice that even when following the standard guidelines for choosing Q. NCE can still yield parameter estimates far from the ground truth (Rhodes et al. 2020 Goodfellow et al. 2014: Gao al. 2020). Most recently, Rhodes et al.) (2020) identified phenomenon they call the "density chasm." observing empirically that NCE performs poorly when the KL divergence between P. and Q is large. One example is when P., Q are both tightly concentrated unimodal distributions with faraway modes; the region between the two modes will have a small density under both distributions, thus forming a "chasm". While it makes intuitive sense that NCE does not perform well under such settings-sine disparate Q and P. are easy to distinguish and do not require the model learn much about P. in order to do well on the classification task-thers there has not been a theoretical analysis of this phenomenon. In fact, it not even clear whether the difficulty statistical or algorithmic in nature.
In this work, we formally study the challenges for NCE with a fixed Q with focus on distribu- tions in an exponential family. We show that when the noise distribution Q is poorly chosen, the loss landscape can become extremely flat: in particular, even when p and Q are two univariate Gaussian with unit variance, the loss gradient and curvature can become exponentially small in the difference in their means. We prove that this poses challenges for standard first order and even
'The partition function is also known as the normalizing constant of an unnormalized density, such that the density after normalization will integrate 1.

---

Published as a conference paper at ICLR 2022
second-order optimization methods, forcing them take an exponential number of steps to converge to a good parameter estimate. Thus, standard approaches to minimizing convex functions such as gradient descent- or even more advanced techniques such momentum Newton's method are not suited to the NCE objective unless Q is close to P. in sense.
To remedy this issue, we study alternative method for optimizing the NCE objective. We consider instead Normalized Gradient Descent (NGD) whereby the gradient is normalized to have unit norm at each time step. Perhaps surprisingly, we prove that this small modification can overcome the problem of poor curvature in the Gaussian example. In general, we show the number of steps for NGD to converge to a good solution for the NCE loss depends on the condition number K of the Hessian of the loss at the optimum the growth of this condition number is unclear for P and Q when they belong to an exponential family.
To address this, we propose the eNCE loss, a variant to NCE that replaces the log loss in NCE with an exponential loss, and we show that the resulting condition number is polynomial in the dimension and the parameter distance between P and Q when they belong to exponential family. Our proposed change of loss and optimization algorithm together form the first solution that provides a provable polynomial rate for learning the parameters of the ground truth distribution. Theoretically, both NCE and eNCE can potentially suffer from numerical issues during optimization when P and Q are far-this is interesting direction for future work. Nonetheless, we find this to be simple and effective fix to the flatness of the loss landscape in many settings, as evidenced by experimental results on synthetic and MNIST dataset.
1.1 RELATED WORK
NCE and its variants have inspired a large volume of research in NLP (Mnih & Teh 2012 Mnih &
Kong et al. 2020) as well as computer vision (Oord et al. 2018 2018/Hoo Henafi 2020 Tian et al. 2020). It has been observed empirically that NCE with fixed noise Q is often insufficient for learning good generative models. The predominant class of approaches that have been proposed to overcome this issue aim to do so by not using a fixed Q but by iteratively solving multiple NCE problems with an updated Q, or equivalently updated discriminators. This includes the famous generative adversarial network (GAN) by [Goofelloww) al. (2014), which uses separate discriminator network updated throughout training. In a similar vein, Gao et al.] (2020) also aimed to increase the discriminative power as the density estimator improves, and parameterize Q explicitly with a flow model. More recently, [Khods et al. (2020) proposed the telescoping density ratio estimation, or TRE, which sidesteps the chasm by expanding p-/q into a series of intermediate density ratios, each of which easier to estimate, leading to strong empirical performance- though their work carries no formal guarantees.
Kavukcuoglu 2013 Dyer 2014
Hjelm et al. 2018]
With respect to a fixed Q, it remains an open question about what formally are the nature of the challenges posed by a poorly chosen Q. which could be statistical and/or algorithmic. Various pre- vious works have analyzed the asymptotic behavior of NCE and its variants (Gutmann & Hyvärinen 2012 Riou-Durand et al. 2018 Uehara et al. 2020), but these do not provide guidance on the finite step convergence of NCE or its common variants. The improvements to NCE in prior works are all borne out by the empirical observations of NCE practitioners, rather than motivated by theory, which is precisely the aim of this work.
Finally, we would like to note that prior work has proposed "generalized NCE" Piihlaja al. 2010 Gutmann & Hirayamal 2011 Uehara et al. 2020)). which relates the NCE objective to minimizing the Bregman divergence. Generalized NCE says that we can design a family of training objectives by using different convex functions to define the Bregman divergence, and the proposed eNCE is an instance of the generalized NCE objective. The difference between these prior work and ours again the different focuses on asymptotic behavior versus finite step convergence.
PRELIMINARIES
The NCE objective Let P. denote an unknown distribution in parametric family (Pa (eee for some bounded convex set O with P. Pe.- Our goal is estimate P. via Pe for some 0 E θ by solving a noise contrastive estimation task. The noise distribution Q belongs to the same parametric family with parameters 6g E O, so that Q Po.- We use po, Pa, q to denote the probability density
2

---

Published as a conference paper at ICLR 2022
functions (pdfs) of Po. P., and Q; may omit in Po. pe when it is clear from the context and write P instead. Given P. and Q. the NCE loss of P is defined as follows:
Definition 2.1 (NCE Loss), The NCE loss of Po w.r.t. data distribution P. and noise Q is:
[(Pb)
Er. log
pa
Q log
(2.1)
po +
po +
The NCE loss can be interpreted as the binary cross-entropy loss for the classification task of distin- guishing the data samples from the noise samples. Moreover, the NCE loss has unique minimizer: Lemma 2.1 (Gutmann & Hyvärinen 2012). The NCE objective Definition 2.1 uniquety mini- mized at P = P., provided that the support of Q covers that of P..
Exponential family. We focus our attention on the exponential family, where the pdf for a dis- tribution with parameter 0 is p=(x) exp ( (TT(()) - A(0)). with T(z) denoting the sufficient statistics and A(0) the log partition function. The partition function is treated parameter in NCE, so we use T to denote the extended parameter, i.e. - == [0. al where a is the estimate for the log partition function. We accordingly extend the sufficient statistics as T(x) = [T(x). -1] account for the log partition function. The pdf with the extended representation is now simply Pr (z) = exp(T T(x)). We will use the notation Pa and P. interchangeably. We will also use r()) to denote the log- partitioo extended parameterization when the log partition function a properly normalizes the distribution specified by 0.
compelling reason for focusing on the exponential family is the observation that the NCE loss convex in the parameter T:
Lemma 2.2 (NCE convexity). For exponential family pa.o (2) = l((x) exp(O (TT())(())))))))))))))))))() a), the NCE loss is convex in parameter 7 [0, a..
Lemma 2.2 has been stated under more general settings by Uehara et al. 20200; an alternative self- contained proof is included in Appendix A for completeness.
Recall that e denotes the set of parameters without the extended coordinate for the log partition function. We assume the following on distributions supported on θ:
Assumption 2.1 (Bounded parameter norm). ||0||2 S w, AO E e. Assumption 2.2 (Lipschitz log partition function). Assume the log partition function is Bz- Lipschitz. that is, 10,, 02 O, |log 2(0,) log 2(02)ls 1 02ll.
Assumption 2.3 (Bounded singular values the population Fisher matrix). There exist O. such that 44 E O, we have T (na (Fx < Amax. and Amin-
Amax, Amin
miin (Eal (T (F)) (x))(x>))))
Assumption 2.4 (Smooth change in the Fisher matrix). Assume the maximum and minimum singular values of the Fisher matrix change smoothly. Namely, there exist constants Ymaxx Ymin > s.t.
DIIS Ymaax V [T Dill Tmmi-
DIIS
Assumptions 2.2 2.4 can be viewed as smoothness assumptions on the first, second and third order derivatives the log partition function, and can be viewed as introducing structural parameters of the distributions. For example, distributions with flatter tails will have a larger Amax- which then translates to a slower rate the results; distributions closer to being singular will have a smaller Amin: etc. In particular, Assumption says the singular values of the Fisher matrix E, (Tx))TTTT (T:))()))
should be bounded from above and below. It can be shown that the Fisher matrix is proportional to the Hessian of the NCE objective when using Q P., which means Assumption 2.3 can be interpreted as saying the NCE task can be solved efficiently under the optimal choice of Q.
OVERVIEW OF RESULTS
We first provide an informal overview of our results, focusing on learning exponential families.
Another common format of the exponential family PDF is (x h(z) exp (8")(x) A())) where h(r) is a non-negative function. Such h(z) could be absorbed into T(x) and with corresponding coordinates log(h (h(z)) and 1.
3

---

Published as a conference paper at ICLR 2022
Flatness of population landscape: Our first contribution is negative result identifying a key source of difficulty for NCE optimization to be an ill-behaved population landscape. We show that due to an extremely flat landscape, gradient descent or Newton's 's method with standard choices of step sizes will need to take an exponential number of steps to find reasonable parameter estimate.
We emphasize that though Gaussian mean estimation is a trivial task, its simplicity strengthens the results above: we are proving a negative result so that failures with a simpler setup means a stronger result. Moreover, the results only apply standard choices of step sizes, such inversely proportional to the smoothness for gradient descent, or to the ratio between the smoothness and strong convexity for Newton's is method. This does not rule out the possibility that cleverly designed learning rate schedule or a different algorithm would work efficiently; the results are however still meaningful since gradient descent with standard step sizes the most common choice in practice.
Overcoming flatness using normalized gradient descent: Our second contribution is to show that the flatness problem can be solved by simple modification to gradient descent if the loss is well-conditioned. Specifically, we show that the convergence rate for normalized gradient descent is polynomial in the parameter distance and K., the condition number of the Hessian at the optimum. One immediate consequence is that in Gaussian mean estimation, for a target error of 8 E (0, $z in parameter distance, NCE optimized with NGD achieves a rate of ((+)), ), which is the same the optimal rate achieved by MLE.
The remaining question is then whether K. is polynomial in the parameters of interests. We show that K. can be related to the Bhattacharyya coefficient between P. and Q. which indeed grows polynomially in parameter distance under certain assumptions as detailed in Section 5.2
Polynomial condition number for the eNCE loss: Our third and final contribution is that if we modify the NCE objective slightly-namely, use the exponential loss in place of the log tass-then the condition number at the optimum guaranteed to be polynomial. We call this new objective eNCE. Combined with the NGD result, we get that running NGD on the eNCE objective achieves polynomial convergence guarantee.
We then provide empirical evidence synthetic and MNIST dataset that eNCE with NGD performs comparatively with NGD on the original NCE loss, and both outperform gradient descent.
FLATNESS OF THE NCE LOSS
In this section, we study the challenges posed NCE when using a badly chosen fixed Q. The main thrust of the results is to show that both algorithmic and statistical challenges can arise because the NCE loss is poorly behaved, particularly for first- and second-order optimization algorithms: when P., are far, the loss landscape is extremely flat near the optimum. In particular, the gradient has exponentially small norm and the strong convexity constant decreases exponentially fast, limiting the convergence rate of the excess risk. We further show that when moving from P= Q to P= P.. the loss drops from ((1) to a value that is exponentially small in terms of the distance between P. and Q. Consequently, common gradient-based and second order methods will take exponential number of steps to converge.
An important note is that our analysis is at the population level, implying that the hardness comes from the landscape itself regardless of the statistical estimators used.
For the negative results in this section, let's consider ceedingly simple scenario of I-dimensional, Axee-variance Gaussian mean estimation. We will demonstrate the enormous difficulty of achieving good parameter estimate, even for such a sim- ple problem-this bodes ill for NCE objectives corresponding to more complex models in practice, which certainly pose a much more difficult challenge. In particular, let P., Q, P be Gaussians with identity variance. Let 0,, By. 0 denote the respective means, with 0. being the target mean that NCE aims to estimate. When the covariance known to be 1, we can denote h(x) == exp(
Setup Gaussian mean estimation:
2 ), and
parametrize the pdf of a 1d Gaussian with mean as p(x) = h(z) (xp((r()), T()))
where the
g" parameter is 7 70)) := [0, z + log 2T) and the sufficient statistics are T(x) == [x, We will
shorthand 7 (0) when is clear from the context.
*Thus, we are setting h to be the base measure for the exponential family we are considering. *Recall that the last coordinate 1 acts sufficient statistic for the log partition function.
4

---

Published as a conference paper at ICLR 2022
0g. We will write T, == = RR 2 + log v2T]. and Tu := T(0g) = [0, log v As clarification, the results stated in this section will be in terms of R. hence the asymptotic notations 32, O never hide dominating dependency on R.
Without loss of generality, we will assume fg = 0, and 0, 0, and denote R 8. - f²
4.1 PROPERTIES OF THE NCE LOSS
We first describe several properties of the NCE loss that will be useful in the analysis of first- and second-order algorithms.
To start, we show that the dynamic range of the loss is large: that is, the optimal NCE loss is exponentially small as function of Rt on the other hand, if 0 is initialized close to 0g. the initial loss would on the order of constant. Precisely:
Proposition 4.1 (Range of NCE loss). Consider the 1d Gaussian mean estimation task with mean 0,. 0g E IR and known variance of 1. Denote R == 00 0.1 where R > 1, Then, the loss at 0 = 0g is log 2, while the minimal loss L. is (R) = c cexp(- ////////)))) /or some E 12,
The next shows we need to decrease the loss be on order comparable to the optimum value. Namely, the loss is very flat close to 6,, thus in order to recover l close to Az, we have to reach very small value for the loss. Precisely:
Proposition 4.2. Under the same setup as Proposition 4.1 for given å (0, 1), if the learned I R exp(( R2/8) 82.
parameter satisfies ||T 1---- T" 12 6, then L(T) I(T")
The way we will leverage Propositions 4.1 and 4.2 to prove lower bounds is to say that if the updates of an iterative algorithm are too small, the convergence will take an exponential number of steps.
Proposition 4.2 is proven via the Taylor expansion at 0" since the gradient is O at 0,, we just need to bound the Hessian 0,. We show:
Lemma 4.1 (Smoothness P P*), Under the same setup as Proposition 4.7 the smoothness P = Ps is upper bounded as mmax V (V*)(T=)) < R_ exp(-R2
/28
We will also need bound on the strong convexity constant (i.e. smallest singular value) at P P": Lemma 4.2 (Strong convexity at P = P*). Under the same setup as Proposition 4.1 the minimum singular value at = P, is of Tiia ((²)(T)))
exp
R2
Finally, in order to estimate the choice of the step size for standard optimization methods, we will also need a bound of the smoothness at P Q:
Lemma 4.3 (Smoothness P Q). Under the same setup as Proposition the smoothness at P = Q is lower bounded as max (V2I(T,)) 2 2
Lemma
4.2 are proved in Appendix D.4 and Lemma 4.3 is proved in Appendix D.5
4.2 LOWER BOUNDS ON FIRST- AND SECOND-ORDER METHODS
With the landscape properties at hand, and second-order methods. For first-order methods, we show that:
ready to provide lower bounds for both first-order
Theorem 4.1 (Lower bound for gradient-based methods). Let P., Q, , be Id Gaussian with vari-
ance 1. Assume 0g 0, 0, > 0 without loss of generality, and assume R == O, Og 1. Then, gradient descent with any step size n = o(1) from an initialization T = will need an exponential number of steps to reach some r' that is (11) close T..
Note, the maximum step size 1) = o(1) the theorem applies to is actually a loose bound: the standard setting of step size for gradient descent is r I 1/Ass for A& max o Fmax 2 L(r())) which is Ω (t2) by Lemma 4.3 Theorem 4.1 helps explain why NCE with far-away Q fails in practice, if we set the budget for the number of updates to be polynomial.
For example, for R > 1, RRx (eexp (R²)), but the constant in O(1) will not depend on R.
5

---

Published as a conference paper at ICLR 2022
A natural remedy to the drastically changing norms of the gradients is to methods that can properly precondition the gradient. This motivates the use of second order methods, which adapt to the geometry of the loss and hence can potentially perform more competitively.
Unfortunately, standard second-order approaches are again of no help, and the number of steps required converge remains exponential. Consider Newton's method with updates of the form ((V2L)- - L.. At first glance, this looks like it may solve the issue of a flat gradient, since the Hessian L may also be exponentially small hence canceling with the exponentially small gradient. However, the flatness of the landscape forces us to take an exponentially small step size 1) resulting in the following claim:
Theorem 4.2 (Lower bound for Newton's 's method). Let P., Q. satisfy the same conditions in theorem 4.1 Let Xp- == minsee miiu ( ((T)), AM := maXaço max (V2 Then, run- ning the Newton's method with step size O A2) from an initialization T Tq will need exponential number of steps reach some T' that ((1) close T..
Xxd
Again, the condition rj = O Ae follows the typical step size choice for Newton's 's method, i.e. the step size should be upper bounded by the ratio between the global strong convexity constant and the global smoothness of the function, which is exponentially small for this setup by Lemma 4.2
5 NORMALIZED GRADIENT DESCENT FOR WELL-CONDITIONED LOSSES
We have seen that due to an ill-behaved landscape, NCE optimized with standard gradient descent or Newton's 's method will fail to reach good parameter estimate efficiently, simple as Gaussian mean estimation, and even with access to the population gradient.
problem as
In this section, will show that close relative of gradient descent, normalized gradient descent (NGD), despite its simplicity, provides a fix to the flatness problem to exponential family distribu- tions when the Hessian of the loss is well-conditioned close the optimum.
Precisely, recall that the NGD updates for a loss function I. is T++1 = Tt 7 G We assume
(((T)
that in neighborhood around T., the change in the shape of the Hessian H is moderate:
Assumption 5.1 (Hessian in a neighborhood of T.). Under assumption 2.2 with constant Bz, assume that for any J such that ||T - T= 1, it holds that Fmax m S Su Fmax ( (T.)), and Bz T Omin (T)) 2 Bt Omin (T.)). for some constant Bus B1 > O.
The main result of this section states that NGD can find parameter estimate efficiently for expo- nential families, where the number of steps required is polynomial in the distance between the initial estimate and the optimum:
Theorem 5.1. Let L be any loss function that is convex in the exponential family parameter and satisfies Assumptions 5.7 and 2.1 2.4 Furthermore, let P., Q be exponential family distributions with parameters T., Ty and let K. be the condition number of the Hessian at P P.. Then, for any 0 < 6 Bz and parameter initialization To. with step size 1) S Buk.
8. performing NGD on
the population objective L guarantees that after T t < T such that || - T.l125 8.
Puk_ Br
11 -=ll" steps, there exists an iterate
The main technical ingredient for proving Theorem 5.1 is the following Lemma:
Lemma 5.1. Suppose Assumptions 2.2 ana
5.7 hold with constants 3z, Bu and Br. Let L be convex
function with minimizer T., and let g V L(T). For any 8 < 1.
Fg let Bu
B. 5. Then for all T
9 s.f. ||7 - --.11l1122 8, we have L(T. + 77 [ < L(T).
Lemma 5.1 explains the dependency on K. in the NGD convergence rate. The intuition of the proof is that in a small neighborhood around т., the set of parameters that have the same loss form an "ellipsoid", and by Taylor expansion, any two points in the same set will have a distance-to-7, ratio upper bounded roughly by K... The details are in Appendix C.2
As concrete example, we will show in the next section that variant of NCE satisfies both conditions.

---

Published as a conference paper at ICLR 2022
Proof sketch for Theorem 5.7 the proof leverages two observations: the convexity of NCE loss exponential family parameters, and that the Hessian neighborhood around Tx changes moder- ately as stated in Assumption 5.1] One can then show there exists global constant such that for any 7r satisfying 7/ T.ll22 6, one step of NGD update guarantees a decrease of 72 in the squared error, which means NGD must have found an ò-close estimate within || Il steps. The full proof deferred to Appendix C.T
5.1 EXAMPLE: ID GAUSSIAN MEAN ESTIMATION
It is relatively straightforward to check that NGD addresses the flatness problem faced by Gaussian mean estimation we considered in Section 4
Corollary 5.1. Let P., Q be Id Gaussian with covariance 1 and mean 0_ R where R < 1, and 0g = 0. For any given S R and initial estimate To = Tqp NGD can find an estimate such that ||T - T. 1.ll2S 6, with at most O Rt 8z steps.
Intuitively, the effectiveness of NGD comes from the crucial observation that though the magnitude for the loss and derivatives can be exponentially small, they share the same exponential factor, mak- ing normalization effective. Formally, can be shown that & 0(1) (Appendix D.6). Corollary
5.1 then follows from Theorem 5.1 and the curvature and strong convexity from Lemma 4.1
5.2
BOUNDS ON THE CONDITION NUMBER OF NCE
The convergence rate in Theorem 5.1 depends on ii, the condition number of the NCE Hessian at the optimum, and Hessian-related constants Su, 3r in Assumption 5.1 We now show that under the setup of Theorem 5.1 Ki and Bu, 3t can be related the Bhattacharyya coeffficent between P. and
Q. which similarity measure defined as BC(P,, Q) = Ja Vp. As a result, we get the following convergence guarantee:
2.3 hold with constants w, Amax. and Amin- Consider NCE task with data distribution P, and noise distribution P2, parameterized by 01, 41,02 E θ re- spectively. Then for any given <
Theorem 5.2. Suppose Assumptions
R and initial estimate To = Typ NGD NGD,finds an estimate such
that || T T-ills 8 within T S C BC(P.QQ)*
10- 6²
steps, where C' == 18 18exp
2
Amax )3
Amai
222 Xmann
2Amin *mmaax ||6||
min
Aunin "mmin 6l
In particular, when P., Q are not too far, we can further show a lower bound on BC(P., Q):
4 Lemma 5.2. For Pı, P2 parameterized by 01,02 02 E O, if [|0] 02 121335 Amnas then (C) 2
The proofs of Theorem 5.2 and Lemma 5.2 rely analyzing the geodesic on the manifold of square root densities v p equipped with the Hellinger distance as a metric; the details are deferred to Appendix C.3 C.4 It is also worth noting that Theorem (.20orrmm5.20nn... 5.2 requires ||0 02 to be smaller than constant, rather than tending to zero as usually required for analyses using Taylor expansions.
Finally, we would like to note that although analysis can be tightened, it is unlikely remove such dependency since NGD only uses first-order information. M Moreover, the condition number k. also affects the practical use of Newton-like methods, since matrix inversion is widely known to be sensitive to numerical issues when the matrix is extremely ill-conditioned. It is an interesting open question whether non-standard preconditioning approach might be amenable to this setting.
ANALYZING ENCE: NCE WITH AN EXPONENTIAL LOSS
The previous section proved that NGD can serve simple fix overcome the flatness problem of NCE for well-conditioned losses. However, though we showed K, has a polynomial growth when the distributions P. Q* are sufficiently close- -it is unclear how K, behaves beyond this threshold.
II the next section, will that the condition number is provably polynomial in ||0_ 110-00y1 for a variant of the NCE loss.
7

---

Published as a conference paper at ICLR 2022
In this section, introduce slight modification to the NCE objective, which call the eNCE objective, for which K, depends polynomially on some class-related constants. This means though eNCE may still suffer from the flatness problem, eNCE and NGD together provide solution that guarantees a polynomial convergence rate.
Towards formalizing this, the eNCE loss is defined as:
Definition 6.1 (eNCE Loss). Let sp(x)= :- log V dlay
pla) and (I, == exp(- for E {+1).
The eNCE loss of Pg w.r.f. data distribution P. and noise Q is:
q(x)
p(x) 2 f " ((x)
p(x) (6.1)
Lexp (Pa) = P. 1 (z, 1)] + 2 P. 1)]
p.
It can be checked easily that the minimizing y learns ((x) - 1 log 9 Moreover, each is associ- ated with induced distribution p. defined by p(z) (xxxp(((x))))))
Relation to NCE: Same as the original NCE loss (referred to as "NCE" below), eNCE learns to solve distinguishing task between samples from P. or Q. The difference lies only in the losses, which have analogous forms: the NCE loss described in Def. [2. can be rewritten in the same form with
((x, := log pooxpp-yy00a and (x))= == log p(z)
1
7(z)*
The main advantage of the exponential loss is that the Hessian at the optimum is now guaranteed to be well-conditioned:
Lemma 6.1 (Polynomial condition number for eNCE loss). Under Assumption 2.3 with constants Amax, Amin. the condition number of the eNCE Hessian at the optimum is bounded by K. S Ammas Amiin
We can also show that eNCE satisfies part (ii) of Assumption 5.1 Due to space considerations, the proof is deferred to Appendix B.I
Lemma 6.2. Under assumption 2.2 with constant Bz, for any unit vector and constant c [0, E I.
the maximum and minimum singular values of H( + cu) satisfy assumption 5.1 with constants Bn = 2exp(1)
Amna
B1
Amin.
Amin
2exp(I)
Amax
Lemma 6.1 and Lemma 6.2 logether imply the Hessian is well-conditioned around the optimum.
Combined with Theorem 5.1 we have the main result of this section:
Theorem 6.1. Let P. be exponential family distributions with parameters Tx Tq under Assump- 1 and pa-
tion 2./ 2.4 Let Amax: Amin be constants for Assumption 2.3 For any given 5 S By
rameter initialization To, performing NGD on the eNCE objective guarantees that when taking
T < cxx((2)
X
| steps, there exists an iterate t < T such that || Tx 8.
g
Proof. Theorem 6.1
f follows directly from Theorem 5.1 using the condition number bound from Lemma 6. and constants from 6.2
6.1 PROOF OF LEMMA 6.1
It can be checked that the Hessian P P= P. (PI( vP-qVV log p(V log Recall that 0., 0g. T denote the parameters and sufficient statistics without the partition func- tion coordinate, and Tu, Ty. T denote the extended version with the partition function, e.g. T. [0,, log (00.)], (x) [Tx), -1]. Then,
rewrite H, as:
H. = + (x))(( =
= / (T. T.)) T(x) T())T(a))
2
exp
(0. + +,, 7(x) 2
log (0.))
1
1
log 2(0,) (())T(a)
2
(6.2)
Z (u+2g
exp ((atte) T((x)
2
T(x)T(r) d== B(P..Q)
Re. TT
(Z(
(0++9g 22
B(P..Q)
The Lemma then follows from Amin I - Eo.+0,
TT 3 Amax I by Assumption 2.3
8

---

Published as a conference paper at ICLR 2022
NCE, GD
I NCE, NGO
eNCE. NGO
120
36
Figure 1: Results for estimating 1d (left) and 16d (right) Gaussians, plotting mineg T 12 (y-axis) against the number of updates T (æ-axis). In both cases, when using NCE, normalized gradient descent ("NCE, NGD", yellow) largely outperforms gradient descent ("NCE, GD", red). When using NGD, the proposed eNCE ("eNCE, NGD", blue) decays faster than the original NCE loss. The results are averaged over runs, with shaded areas showing the standard deviation.
NCE,
NCE, NGD
-NNCE GO
aNCE NGD
10-10
01
20-20
001
Figure 2: Results on MNIST, plotting loss value (g-axis, log scale) against update steps (x-axis). The left plot shows NCE optimized by GD (black) and NGD (yellow), and the right shows eNCE optimized by GD (black) and NGD (blue). It can be seen that NGD outperforms GD in both cases.
7 EMPIRICAL VERIFICATION
To corroborate our theory, we verify the effectiveness of NGD and eNCE on Gaussian mean esti- mation and the MNIST dataset. For MNIST, we use ResNet-18 to model the log density ratio log(p/9), following the setup in TRE (Rhodes et al. 2020).
Results: For Gaussian data, we run gradient descent (GD) and normalized gradient descent (NGD) on the NCE loss and eNCE loss. Figure [ compares the best runs under each setup given fixed computation budget (100 update steps), where "best" is defined to be the run with the lowest loss on fresh samples. The plots show the minimum parameter distance min, (T) l|. - -ell2 for each step T. We find that NGD indeed outperforms GD, and that the proposed eNCE sees a further improvement over NCE while additionally enjoying provable polynomial convergence guarantees. For MNIST, we can no longer compare parameter distances since т. is unknown. Instead, we compare the result of optimization directly in terms of loss achieved, again under a fixed computation budget (2K steps). The results are shown in Figure 2 with NGD converging significantly faster for both NCE and eNCE. We note that eNCE can be numerically unstable, especially when Ps, Q are well separated. We include implementation details in Appendix E.1 and additional results in Appendix E.2
8 CONCLUSION AND DISCUSSIONS
We provided a theoretical analysis of the algorithmic difficulties that arise when optimizing the NCE objective with an uninformative noise distribution, stemming from an ill-behaved loss landscape. Our theoretical results are inspired by empirical observations in prior works (Rhodes et al.) 2020
Gao et al. 2020; Goodfellow al.) 2014) and provide the first formal explanation on the nature of the optimization problems of NCE. Our negative results showed that even on the simple task of
Gaussian mean estimation, and even assuming access to the population gradient, gradient descent and Newton's 's method with standard step size choice still require an exponential number of steps to reach a good solution.
We then proposed modifications to the NCE loss and optimization algorithm, whose combination results in the first provably polynomial convergence rate for NCE. The loss we propose, eNCE, can be efficiently optimized using normalized gradient descent and empirically outperforms existing methods. We hope these theoretical results will help identify promising new directions in the search for simple, effective, and practical improvements noise-contrastive estimation.

---

Published as a conference paper at ICLR 2022
REFERENCES
Jacob Andreas, Maxim Rabinovich, Dan Klein, and Michael I Jordan. On the accuracy of self- normalized log-linear models. arXiv preprint arXiv: 04147, 2015.
Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Accurate and conservative estimates of mrf log-likelihood using reverse annealing. In Artificial Intelligence and Statistics, pp. 102-110. PMLR, 2015.
Yilun Du and Igor Mordatch. Implicit generation and generalization in energy-based models. arXiv 2019.
preprint
Chris Dyer. Notes on noise contrastive estimation and negative sampling. arXiv preprint arXiv:1410.8551 2014.
Ruiqi Gao, Erik Nijkamp, Diederik P Kingma, Zhen Xu, Andrew M Dai, and Ying Nian Wu. Flow contrastive estimation of energy-based based models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7518-7528, 2020.
Andrew Gelman and Xiao-Li Meng. Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statistical science, pp. 163-185, 1998.
Charles Geyer. On the convergence of monte carlo maximum likelihood calculations. Journal of the Royal Statistical Society: Series (Methodological), 56(1):261-274, 1994.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint arXiv: 14400.266,, 2014.
Will Grathwohl, Kuan-Chiel Chich Wang, Jörn-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky. Your classifier is secretly an energy based model and you should treat it like one. arXiv preprint arXiv: 2019.
Roger B Grosse, Chris J Maddison, and Russ R Salakhutdinov. Annealing between distributions J. C. Burges, Bottou, M. Welling, Z. Ghahramani, and Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran As- sociates, Inc., 2013. URL https: httttt::/pppccceeii.ee .pdf
by averaging moments.
neurips cc/papper/2113/ELEee
Fb60d41 1a 1a555b 2t0
Michael Gutmann and Jun-ichiro Hirayama. Bregman divergence as general framework to estimate unnormalized statistical models. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2011.
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 Statisties, pp. 297-304. JMLR Workshop and Conference Proceedings, 2010.
Michael U Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13 (2), 2012.
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high-probabilityy bounds for strongly-convex stochastic gradient descent. arXiv preprint urXiv:I909.000 2019.
Elad Hazan, Tomer Koren, and Kfr Levy. Logistic regression: Tight bounds for stochastic and online optimization. In Conference on Learning Theory, pp. 197-209, PMLR, 2014.
Elad Hazan, Kfir Y Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. arXiv preprint arXiv:1507.00330 2015.
Olivier Henaff. Dfta-efficient image recognition with contrastive predictive coding. In International Conference Machine Learning, pp. 4192-4192, PMLR, 2020.
10

---

Published as a conference paper at ICLR 2022
R Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization, arXiv preprint (10,000008000660,, 2018.
Karan Grewal, Phil Bachman, Adam
Aapo Hyvarinen and Hiroshi Morioka. Unsupervised feature extraction by time-contrastive learning and nonlinear ica. arXiv preprini 16Xv::605500336 2016.
Scott Kirkpatrick, Daniel Gelatt, and Mario Vecchi. Optimization by simulated annealing. science, 220(4598)6671-66) 680, 1983.
Lingpeng Kong, Cyprien de Masson d' d'Autume, Lei Yu, Wang Ling, Zihang Dai, and Dani Yo- gatama. A mutual information maximization perspective of language representation learning. In International Conference on Learning Representations, 2020. URL URLnEttpss//ppeeevveee net htte:/oormmldd--yyy 79eBWWI
Matthieu Labeau and Alexandre Allauzen. Learning with noise-contrastive : Easing train- ing by learning to scale. In Proceedings of the 27th International Conference on Compulational Linguistics, pp. 3090-3101. Santa Fe, New Mexico, USA, August 2018. Association for Compu- tational Linguistics. URL https:/ www. wwwwwb.bwb.......cc..........w.. org/ awtaaaattoootottaaeeee C1--
Aditya Menon and Cheng Soon Ong. Linking losses for density ratio and class paasaaitbabiiltty estima- tion. In International Conference on Machine Learning, pp. 304-313. PMLR, 2016.
Andriy Mnih and Koray Kavukcuoglu. Learning word embeddings efficiently with noise-contrastive estimation. Advances in neural information processing systems, 26:2265- 2273, 2013.
Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilistic language models. Proceedings of the 29th International Conference on Machine Learning, pp. 1751-1758, 2012.
Radford M Neal. Annealed importance sampling. Statistics and computing, 11(2):125-113 2001.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. arXiv preprint arXiv:1606.0000 00000000900 2016.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv:1807.0337444 2018
Miika Pihlaja, Michael Gutmann, and Aapo Hyvärinen. family of computationally efficient and simple estimators for unnormalized statistical models. In Proceedings of the Conference on Un- certainty in Artificial Intelligence (UAI), 2010.
Benjamin Rhodes, Kai Xu, and Michael U Gutmann. Telescoping density-ratio estimation. arXiv preprint arXiv:2006. 12204, 2020.
Lionel Riou-Durand, Nicolas Chopin, et al. Noise contrastive estimation: Asymptotic properties, formal comparison with me-mle. Electronic Journal of Statistics, 12(2)3343-33188, 2018.
Akash Srivastava, Kai Xu, Michael U, Gutmann, and Charles Sutton. Generative ratio matching networks. In International Conference Learning Representations, 2020. URL https://
openreview
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, USA, 1st edition, 2012. ISBN 0521190177.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding, 2020.
Che-Ping Tsai, Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. Heavy-tailed streaming statistical estimation. arXiv preprint arXiv:2108. 11483, 2021.
Masatoshi Uehara. Takafumi Kanamori, Takashi Takenouchi, and Takeru Matsuda. A unified statis- tically efficient estimation framework for unnormalized models. International Conference on Artificial Intelligence and Statistics, pp. 809-819. PMLR, 2020.

---

Published as a conference paper at ICLR 2022
Martin J Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and vari- ational inference. Now Publishers Inc, 2008.
Lantao Yu, Yang Song, Jiaming Song, and Stefano Ermon. Training deep energy-based models with f-divergence minimization. In International Conference Machine Learning, pp. 10957-10967. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
We will fist provide missing proofs for the eNCE results in section section Section providess proof's for NGD convergence on the NCE loss, and section [ proves the negative results NCE in section Additional notes the experiments
provided section E.I
Notation: We will use a S b to denote a = O(b) with hiding constant less than 2. Similarly, 2 b denotes
(b(b) where Ω hides constant greater than 2-
A PROOF OF CONVEXITY OF NCE (LEMMA 2.2)
As a preliminary, let's first prove that the NCE loss is convex in exponential family parameters. Recall that the NCE loss is
p+q L(P) E. log
p + Be log p+q q
(A.1)
where p(x) p(r TT:)). The gradient and Hessian of the NCE loss are:
=z((2) =p(x:) Ta))),
p
p p+q
VL(T)
V
E, log
Eq log
2
q
1
E, p
V.P + Ee
V rP
(p (x)dx, (A.2)
2
p p+99 99
Jr +
q(p - P2)
VPI(T)
7 p+q
T(x)da
2 Jz
(p q)
P. +4
/
(p. + + (2x) dz. (p q)²
pp T(x)(())) dx
2 p p+q
2
Hence the Hessian is PSD at any T.
B PROOFS FOR SECTION 6 (ENCE)
We first write down the loss, gradient and Hessian of eNCE for the exponential family:
1
P
Leep (P)
P
2
Texpp (P)
J /
Vp
V logg
VD
2 Le (P) / V
Vb
D+
>ologp + 1 / Vo VD+ Pe
Vlog pl Togg)
vp
vb)
V
+ P.
V Vlo pl V Togg))
Vp)
2 Pa
TTx))((x)
9
+
V (T(
p
(B.1)
Note that the Hessian is always PSD, which means Loxp is convex in the parameters of the expo- nential family.
13

---

Published as a conference paper at ICLR 2022
B.1 PROOF OF LEMMA 6.2
We directly calculate the Hessian at some F := Tx + cu for some expression in equation
S 8z
1 and
|| 2= 1, using the
B.1
V'L LLop(())
(5)= = f/
P- D
9 +9V (())(())
1
exp
(Tx Tq -
T(T))
eexp
( Tww) [
/ exp
Tg +T
T(x))
exp
(-
c z. T())T())
2
2
2
/ [exp
(1-
(-,u,T(x))
c
+ exp
((,,,((0)) exp
- I(w)) M())(())
21 2(0+00
exp (1 T(x))) exp (G,u exp
T())(a)
V 12(0) (00)
B(P_.Q)
(B.2)
Note that without the term in the square brackets, the integration is exactly the same as the one for H..
We would like bound the ratio Le for any unit vector v. Denote 8 == 7 o HH
0,t0. for notation convenience, and denote S = (x: TTx()) > S-1 = Tx) S
0}. We have:
2 2 Lexp (f)
JEES, exp T(x)) exp (F (TT)) (v ((=)2
1 H.v
eexp (F T ((x)) (v T(x))²
(B.3)
JEEs_ exp (8T T(x)) exp ( T(x)) (v (x))) (F (x)) (0 T(x))²
:= 7j + T-1-
1. exp (F T
Recall that > 9 means functions f,g differ only by constant factor. This equation will be used to calculate both the upper and the lower bound.
For the upper bound, let E (+1), we have
T())o Sa T exp (TTT(()) exp cxp (FTT(T) (TTT()))
Tx
J. exp (FTT(x)) (0 (o T(T)))
(18T(a))00 x0+ to (x)(v Sa te (TTT2=))
Z(x0 + 2
z ( exp(xa)
(B.4)
2xx + 4,t0,)
x0+ 0040 110 T(x))²
Z( (y exp(xa)
T(x))² En.ty
E 2
[1 T(x))
x
< exp (3
E Eo.ta
T(x))
where step (i) uses the Lipschitz property of the log partition function in assumption 2.2 For the lower bound, let x" == arg max maxx Tx. Write == [0, a) (i.e. separating out à which is the normalizing constant), let Sy (v) c Sx. denote a set s.t.
1 [ [ LeSo, (0) Px.0+2-00 (z) T(x))2 2
P Px-0 2.49 (x) T(x)))2
14

---

Published as a conference paper at ICLR 2022
Then Tx for x E {+1} can be lower bounded as:
xx Z(x + 0ot..) SaES (v) Px+0+ 8.40, (z) (z) Txx))²
Z 2) -exp(a)
Je Paoto (v Txx)2
1 x 0 + 0gt0.)
x 9. (1 T(x))²
2 ( 04 P0-0,
exp(aa
E Ee. [1 Txx)
(B.5)
0+ tha [(v (()))
(01
2 exp (-Bz |0| xxaa
2
Ee 1 [( T(x))²
T T-x+ 20
where step (i) uses the Lipschitz property of the log partition function in assumption 2.2 This means for any unit vector v, we have
v 22 Leep (F)e
-T T-1
H.v
Eg 4.4% [(0 ((x)))
E B_a 8.th [(0 - ((x)))
sexp (821181+(a))
E o [(e [2()))
Es. og [(e (xx))
(
C (1 + (22) Amax S 2xxp
Amax
Amax
exp (321011+1a1)
& 2exp(11)
Amin
Amain
Amiu
1 T 2 Lexp (F)o
(8) 1
Amax Amin 2
Amin
v H.U
=7: +
T-1
2
2
cxp
(-3211811
2 eexp(1)
Amax
(B.6)
where step (i), (ti) follow from assumption 2.3
Hence the eNCE loss satisfies assumption 5.1 with constants 3, = -exx(1))
Amax
Br = 2 2exp(1)
Anat
Amin Amaa
C PROOFS FOR SECTION (NGD AND CONDITION NUMBER AT THE OPTIMUM)
This section provides proofs for results in section 5.1 and Lemma 5.T are proved section C.I
Results for NGD convergence rate (Theorem proves the convergence rate stated in terms of the Bhattacharyya coefficient (Theorem 5.2) and the bound on Bhattcharyya
and C.2 Section C.3
coefficient (Lemma 5.2 is proved in section C.4
C.1 PROOF OF THEOREM 5.1 (NGD CONVERGENCE RATE)
Theorem C.1 (Theorem 5.1 restated). Let L be any loss function that convex the exponential
family parameter and satisfies Assumptions a.A.an22.1 2.4 Furthermore, let P., Q be exponential family distributions with parameters T., Ty and let Ks, be the condition number of the Hessian P
P.. Then, for any < 8 S 8z and parameter initialization Tú, let the step size be S
ARr. 5,
performing NGD on the population objective guarantees that after T I there exists an iterate < T such that ||T - T T=112500 6.
BaK- A.
To
82
steps,
Proof. Denote St := (T())) and R = ||_. - Tyll2 for notation convenience. Recall that the NGD
update with step size v is Tr+1 = Tt - 1)
T Then, || T.I12 can be rewritten as:
9r
| - 1=11=1177 T. --ym + 1/ + 21
gT
T. + 7
9t
(C.I)
15

---

Published as a conference paper at ICLR 2022
If set y s.t. the last term is smaller than 0 for all that not within distance d to t,, setting
7 = 7 gives:
T+ - rall I| T. -.11 --112-2y07 2yy + =7² = 1 - -2?
(C.2)
Hence the number of steps required to find a s.t. ||| - T. 8 is at most T S TT-
By Lemma 5.1 setting 7
31 & ensures L(T. + 7 11 S [(Te) for any ta that is at least ò
Bum. m.
away from T. It then follows from the convexity of L that
ge Tx
+
9t
To
Ta +
|gaell
gt.
L(Te)
S O.
(C.3)
Substituting this choice of y back to the bound for T gives T S
Ban. 84
1
C.2 PROOF OF LEMMA 5.1
Lemma C.I (Lemma 5.1 restated). Suppose Assumptions 2.2 and 5.1 hold with constant 37, B.
and Br. Let L be convex function with minimizer T., and let = VITT). For any ö s B2' let
1
V Dr 8, then for all s.t. |T T=l122 8, we have L(T, + Till s L(T).
Bux.
The proof follows from the Taylor expansion around T,: for any unit vector v and any con- stant the Taylor remainder theorem states that there exists some constant c' < c and unit vector v such that L(T. + cv) ((T.) = H ccv')v.
Proof.
For any unit vector U1, Uy and constants C1 S 8 such that L(T, -1v = L(T, + 02222) we have
oi ou H(T clv()or oa
L(T. +cve)) L(T-)
H(T. chvb)02 L(T. + c200)) L(T-)
maxx
(H(T. + c(ui)) H (T. + c(r%))
Bu B
(C.4)
This means for any two points with the same loss, the ratio between their distances will be at
most V Du k.. Therefore setting - V JaK." guarantees that for any 7 that is at least ó away from
Tu. T will have a larger loss than any point that is away from T.. In other words, L(T)) s L(72) holds for any Ti E B(T,, 7), T2 B(T.,
C.3 PROOF THEOREM 5.2 (CONVERGENCE RATE IN TERMS BHATTACHARYYA COEFFICIENT)
Recall that the Bhattacharyya coefficient of P., Q is defined as BC = Ss (p(())
Theorem C.2 (Thcorem 5.2, restated), Suppose Assumptions 2.1 2.3 hold with constants w, Amax. and Amin- Consider a NCE task with data distribution P. and noise distribution Q, parameterized by 0z, 0g E O respectively. Then for any given 6 < n and initial estimate To = Tg. NGD finds
an estimate т such that ||T Ta T=l125 within T S C
1
1 170-7-12 steps, where C =
BC(P..Q)*
82
) 18 exp Bz
(maxx)) Ammn
min
22 X Anii -Yaiin [[]]]
2Amin TImnx [|
Proof. Proving Theorem 5.2 requires bounding the condition number K, and the Hessian-related constants Bu, 3r.
We first show that H, inversely related to BC(P., Q):
Lemma C.2. Let θ be the set of parameters for exponential family satisfying assumption 2.7
Then, for any pair of Pe, Q parameterized by 0,, 0,, O the NCE problem defined with P., Q has
R. < Amaa
Zmmi BC(P..)
16

---

Published as a conference paper at ICLR 2022
The next lemma provides the Hessian-related constants in Assumption 5.1
Lemma C.3. Let ó == T Tu. Let (C(P,, Q) denote the Bhattacharyya coefficient between P.
and Qu then for any such that |ااق|ا 1 we have:
Bz'
mmxx
(2((T))
< BC(P,, Q)
.eep
3
-
1
Amax
min
2xmax
2
Tinax |81|
maxx
(22((T))
2
32
Amiu
Amiu
Amin
min
[T)(T)
BC(P..Q) 16
2
1
Amin
max
Amia Xmax
Yuuin ||8||
min
(T)((
3z
Amax
Amin
Hence Assumption
5.7 is satisfied with constants Bus B1 equal the respective right hand sides.
The factor C' in the theorem statement is then chosen such that BCPP.Q)) Theorem 5.2 is completed by applying Theorem 5.1 and the above lemmas.
C
8n
3.
and the proof of
L
C.3.1 PROOF LEMMA
For exponential family with pdf p(x) = h(x) exp (0T x 1 log Z(0)), the Hessian at the optimum is:
H. /
P.q ((x)T(x) de 3 min (=))))))))))))))<<)))))))))))))) de M. P+ +q
(C.5)
We also have H. - M by noting that p. + +9 S max g). Therefore in order bound R,, suffices to analyze the condition number of M.
For any pair of distributions parameterized by 0, 0g E θ with PDFs p, q. and for any unit vector u, we have
U (Voaao = - -(/mintv / maxt Val(o VH (())))
(
(f(max(vD T(x))²
( min min( (fw+ ao ((TT))))
(# 2Xmax f min(o (u T(x))²
(C.6)
where (i) uses Cauchy-Schward and (ii) uses assumption 2.3
Denote B = ZZ(0)
We have:
(IVC(o 7 100,
(
(Jeeee (z) (T)()))))))
Ease, (v (a)))))²
E
(10)
(C.7)
Combining equation
C.6 C.7 gives a lower bound of min(p, (u T(x))²
f min (uT))) 2 2Amax B
T(x))²
E Eato, (v T(x))22
(C.8)
On the other hand, fa min (u
(u 22 can also be upper bounded as:
[ min ((x)))) T(x))
< [
<
Eatny T T(x)))
(C.9)
B
Hence the condition number of M is bounded as:
(MM)= = max, fr min(p. (v T(x))²
Amax B
Amax
5
B. (C.10)
min, f min(n, (v T(x))2 2 min, E Eote, (v T(x))2]
2A
17

---

Published as a conference paper at ICLR 2022
It is left to determine the value of B. We claim that B BC(r.q)' where BC(P, Q) is the Bhat- tacharyya coefficient P and Q defined as BC(P.Q) == Jnr (p(z)g(z)dz. To see this, note that holds for any a that log Ze = 0 x + log h(x) log pa (z). Hence for any 2,
v Vpal Pe.
B exp log Zaton
log Za log Zo.)
(C.11)
Pa+de (z)
po(o (z) = BC(P, Therefore B-1 1 = (I₂ patel (2)) . -
C.3.2 PROOF FOR LEMMA C.3
(BOUND ON Q))
Proof. For notational convenience, write 8 = [0, a]. where ā = log ((0.) log Z the differ- ence in the coordinate for the log partition function.
Upper bounding
miax (V2 L(T)) maax (=L(T.))
We proceed by splitting T V2L(T) into two terms:
v L
(p+ + 9)
pq
(0 T()))
J -AITIODDO (p- + 9)
pq
T(=)))
TT
(p q)
(w q)
(C.12)
The first term is bounded
S (p= + +)
pq
(v T(x)))
JATT(A)CO (p+
[
1
(v TT()) ) dx
(p 9)
+
9 +2
4
p
JSTWGGEEO (p. + 1)
1
( do
( min 1TT((K)0
q p
(v '(x)))
pp'q
-f (p= + + min
q
Pa pxp(((
(0 (Tx))
p. exp (TTT(x))*
- SSTTCKKO cxp (-8TT(x)) (p. + + min
Pa cxp(28 (20()TTT())
(v (TTT(x))
Dr"
(
q g_Pal (oTT(x))2dz
exp (-8 (p. + 9) min
(TT(KK<0
P+ q
22
exp exp (i (()))
JTTT(S)O
(1)
exp (-ōT min(g.p.)( ((T))))))) < { exp (-TT)(x)) (p.q(uTT(x)) T(x))
2
7 0.40, 0) exep((-0
Pe..% (v T(x))
(Z(0.)Z(0,)
Z 0.40, cxxpp(-))
E Eester _p T(x))2
(Z(O.)Z(0g)
(186)
Z 0.+8.)
2
2
exp (3z0 - a) Ee _ g 2(x))
/ ZZ ((,))((0))
:m1/B
(10) 2
1
B exp
[+
Eo, (0 T(x))²
3z
(C.13)
where step (i) is because 8 Txx) 0; step (ii) increases the value by integrating all x; step (iit) uses Assumption 2.2 on Lipschitz log partition function; and step (iv) follows from the choice of 5 [0,a] that |8| d3
18

---

Published as a conference paper at ICLR 2022
The second term can be bounded as:
[T(())20 (p. 4) (p q)²
pd
v
T dx
P. P.tg min min 10 T(x)) 2 JTT(())20 p+q
min(p. a ( T(x))
< / VPq(o T(=)) 2( (0.+ exp(=aa
E Es. G.. (0 Txx))
(C.14)
Z 0)2(0n)
(9
2 (1ttl)
R Boo- (0 T(x))) exp 2 63210112-0
V
Eon+o+n (v T(x))²
exp
B
2
32
where step (i) uses Assumption 2.2 about Lipschitzness of the log partition function, and step (ti)
because have chosen that 2 D2
Substituting back to equation C.12
gives:
1
1
(3
1
t7 L(
S B
2 exx
1
E Eo.+a. ( T(x))) exp
E Ro.+ay (w T(x)))
3z
2 32
2 exp
3
+
3z
min /maxx Fmax ( (B.. 16 (xx) 1) + Ymaxl1l||
B
(C.15)
where the second inequality uses Assumption 2.3 and Assumption 2.4 for the first and second term respectively.
Recall that e TV2L(T.)e' 2 182 Amna BBg,zo (0 (oTT(=))))
Hence:
mmax (2I((T)
= max v ((T
F (2L(T=))
maxi 1 V2 (
Es.t2, _p( s( T(x))) + E. Eo.+o,40 (v T(x)))
1
< 8Amax B exp
3z
Ee, (6 T(x))2 2
maxo
(C.16)
Amaa exp
(3
2)max
Ymnax |8|
+
min
2
Amin
2
3z
Amin
Tmax (E s. t0g
(x))T(x)TT
Amax
3
22max
Timax
< 8
B exp
min
2+
Amin
3z
Amin
Amin
Lower bounding
amin [[T-)) Let us denote S = {e T(x) > 0} and S_1 = fx
minn (V²L(T))
TTT(r) 50. The goal is to lower bound:
v L2 /
(v- + 4)
(p+ q)² (v (TT))))>
Pq
JJES_, (p. + 4) (p+ q)2 (v T(()))
pq
JIES
+
(C.17)
Let's lower bound Tı, T_ in each of the following cases.
The first case when T-1 2 T,. Let S (v) C S_1 denote a set s.t.
1 / () ((x))
Jees).0) min(p.g) T(x))
(Tx))))))T)222222 2
19

---

Published as a conference paper at ICLR 2022
Write = ai before, then
Ti 20
T-1
[
(p. + 7)
Pq
( (0 (x)))
2
58 TT)( p p (u T(x))
pq
JTTT(K)<D
(p+ q)
1
22 TTT(()
min(p, T(x)) dr 2
min(p.g) ( 2(
2 (1)
(C.18)
(16) 1 minnto. ((x)))
(6v) exp(-a)
2( _(==001
(Borgs (v T())))))
2 8Amax
((0))
(exp(-aa
B exp(-232218 (Eortgrto (v T
8dmax
where step (i) uses p.+g < since 8 T(x) < O; step (ti), (idi) follows from the definition of
1-1; step (iv) uses equation Lipschitz.
C.8. and step (v) uses Assumption 2.2 that the log partition function is
The second case is when Ti T-1. Let Sy (v) S1 denote set s.t.
S Jes, min ( T(x))² 2 mminn(p () ( T(x))²
(t)
Then T-1; Ti can be lower bounded as:
T-1 20
(p. +
Pq
(v T(x))3dr
(p
( 2)
JESI
1
P.
p.+q
min(p.g) ( T())) dx 1 P.. min(p.g)(v T( ((())
#ES1
p+q
JeSS p
exp(a)
min Po, - (()))
2
JeS
exp(a)
explx) min Pa, (0 ((x))
Pan Pa, o) (xx))
2
(xES(()) (v)
4
z 0.+00-000
exp(a)
e ( (TTT(=))2
8Amax
((0.)2(0, 0)
exp(a)
Ba exp( 1ap(-232110))
1
(Eo. T(x))
8Amax
(C.19)
Combining both cases and using |00|5 Fz we get:
T. TV² = +
exp(-2 1z) 1
min { (Baagate (v (o Ta))))))
(B (C.20)
8Amax
B²
Recall that V
TV2 L(T)U S 3 Beege [(0 TT))) Hence
Omin (V2((T)
min LLL(T)e
minn (V2T(T+))
ming B T (2
16cxp(-2
oz
1
Amin Amax
Amin
mmin E 18.18,, TT
Omin (E,, 10 TT
max
min
B
Xmax
O E 0. TTT)
Omin Eesto, (T7)
16exp( -2
1
Amin
Amin
Ymin |
max
B
Amax
Amax
Amia
(C.21)
20

---

Published as a conference paper at ICLR 2022
C.4 PROOF OF LEMMA 5.2 (BOUND ON THE BHATTACCHARYYA COEFFICIENT)
Lemma C.4 (Lemma 5.2 restated), For P1, P2 parameterized by 01, 0,,02 E O, if [|0 - -82132 Amax'
then BC(P1,
Proof. Given 0,, E θ, define a map 6 from [0. to function vp, where p is the PDF for distribution parameterized by some 0 E θ: let 2 denote the partition function for parameter 0 E θ and let ò = 02 81 then @(t) is a function of defined as:
(z)) v h(xx) exp ((0) + 15)T x log Z(1 + 16))-
(C.22)
Denote (z(x) = (z) and 0g == 01 + tō for notation convenience. Then
8Tx x VV(((0)) /Z(0)) dt
a2(9.)
(+)(1)
0
ehe (30TTr)
VT exp
Øl
di
(0.))
Z(0.)
(C.23)
(+) Vh
1
6Tx x
Es, [oTx)) x²
(2) x- Bo, 2])
exp
v /((0)
where step (+) used
OZ(0.) θ
/ h(x) exp (0, exx (0.x) TT Z(0,) 10Tx].
(C.24)
Ot
0t
Hence
0ø:
: /
00
Sz (o. (8 x EØ, 18T x²)
01 Lg
ØL
4
(C.25)
Varg, (ŌTx)
8 Eo, [x: "J8T
Amax 1181/.
4
Using the fundamental theorem of calculus, we get
|l VDb2 1pozlli2- 122 110(1) -001)-((0)11 / 00,(z)
dl //' (z)
di Amax ||01
01
(C.26)
Hence J2 vpo, po 2 1 Amax 11811, or /Pe, P0g
for
1 Amax
8
In particular,
Amax |lll1
for any 02, O2 satisfying =| 110 02 Amoxx
i.e.
BC(P, Q) >
T. VPo
BC(P.Q)
2.
As side note, another bound get is from Lipschitzness of the log partition function:
B = V (Z(0))Z(02)) BC(P,Q)
2
(C.27)
Z(0.) exp (3z- 10--0u112
2
3 0g112
exp
2 22
110.
VZ(O.) Z(O.) exp (-3z 3/,00= 1001l
011l)
which is tighter than
if Vmmax Bz.
Amax [llll
D PROOFS FOR SECTION 4 (NEGATIVE RESULTS OF NNE)
This section provides proofs for the negative results section 4 that is, the NCE landscape is ill-behaved with exponentially flat loss, gradient, and curvature. We will first prove Theorem 4.1 and properties regarding losses and gradients, then prove results related to second-order properties
(Lemma 4.1 4.3 4.2
Theorem 4.2
21

---

Published as a conference paper at ICLR 2022
17.5
7.5
09R--)) beR b72,
5.0
b11--0), b>R BR, b>
2.5
0.0
b=R
5.5 6.0
Figure 3: The gray-shaded area is the region where equation D.7 is satisfied. The orange dot marks Tx, which is enclosed in the green-shaded area. Moreover, the red-shaded area centered at corre- sponds the width-0. 1R annulus A, within which the gradient exponentially small.
D.I PROOF OF THEBRREM 4.1 (LOWER BOUND GRADIENT-BASED METHOSS)
Theorem D.1 (Theorem 4.1 restated). Let P.. Q, Q.P. P be ld Gaussian with variance 1. Assume 0g 0, 0,0,= > O without loss of generality, and assume R == O. 0g > Then, gradient descent with any step size 1) o(1) from an initialization T Tg will need exponential number of steps to reach some T' that is (1) close to T..
Proof. The key lemma to prove Theorem is follows, which upper bounds the decrease in parameter distance from each gradient step:
Lemma D.1. Consider the annulus A := (bbcc (c 1² + (b RT)² [(0.1R)3 (0.2)))) Then, for any (b, c) E A, it satisfies that
(VL(T),
To
= 0(1) exp
c) R2 k<(b c(b,c)-
(D.1)
IT. - -
8
where x(b,c) [ [ is small constant.
Lemma D.I is proved section D.2
To prove Theorem 4.1 we will first show that Lemma D.1 serves an upper bound for the decrease
in parameter distance, that is, showing (VL(T), J. 2 || - -Tl|l-|fr++1 -r(l-- Towards
this claim, write Te+11 as:
Tt+1 T. (I(TT) = VL((T),
(D.2)
| 7ell ||,
where v v: = (L(TT) (VL(Te), -.- -ーー orthogonal to Tu - Tr. Hence
[[ - TT||= (1
17
7o )) |1 7u +////// (VL(T)), ||x - To
(D.3)
T - Tell
From this,
conclude
I Tx -=|1-||T++1 T.|l= 17 VL(T),
T- -
n| VL(T),
T.
). (D.4)
||T 7x
||,,
The next step is to show that there is path lying in A of length at 0.01 R that gradient descent has to go through. We have the following lemma (proof in appendix D.3
Lemma D.2. Let = o(1). For any T s.t. | =r,1> 0.2R. let T' denote the point after one step of gradient descent from then ||T' T.I|> 0.15R.
22

---

Published as a conference paper at ICLR 2022
From any such T', the shortest way to exit the annulus A is to project onto the inner circle defining A, i.c. the circle centered at Tu with radius 0.1R which a convex set. Denote this inner circle as B(T,,0.1R) whose projection is Il 0.) then the shortest path is the line segment r' UB (.. Further, this line segment is of length 0.05R since || -+ 0.15R by Lemma
D.2 while the decrease of the parameter distance (i.e. ||T - T. (]) is exponentially small at any point
in by Lemma D.I and equation D.4 Hence the number of steps to exit is lower bounded by
0.05R
((()) R)) exp
-xO0())exp((
D.2 PROOF OF LEMMA D.I
Recall that for Id Gaussian with known unit covariance, we can use parameter [b. cJ and sufficient statistics T(x) = [z. -11, 1]. with pdf p(z) exp (- exp ((r,T(a))).
For any such that ||_ -T|2 1, VL(T), | can be upper bounded as:
(VL(T):
T+ 2 --
p p- P. ((()) J
|T. - +||
4 2+1
R2a
p P+
(R b).
log 2 +c
(D.5)
P +1
R
/
S(R b)
p p.
2 ++1
x
+
2
log 2T
2
Pa
Let b denote a kb for constant @(). We first show the calculations with 0 for cleaner presentation; the < 0 case is analogous and deferred to D.2.2
Bounding
p-p- E+1
exp
2 2 + bo - -c) exp
(a-R)² 2
log / 2T
Po
2 +
1
exp (bee log v2T)
x²a
x² exp
<
exp
+ bx
log
2T
2< van
log
2
co vas
2
(r Rt²
x + (R b)w +
R².
exp
log v 2T
+
exp
2 -2log 2T
22 C----lg Iag Ver
x2 Colaal VIT
2
r((0)
(4)
(c
log v2 2
(c log
v 22
exp
exp
/2
Ing 22x
26
V2 e- log v/n
21d
C-
Vo
R2)²
1
collo V2T
exp
+
exp
2
lolo
2T colog V2r
(R - b)
2
b
+ b
c²
b
(c
bR)²
b
(c - bTt)²
exp
exp
exp
exp
214
c
21/
bR -
2b²
c b(R 1 b)
262
(8 O(R
A(b.c) c) R²
exp
8
(D.6)
where x(b, c) E [3
31. Step (i) uses caleulations in equation D.12 D.15 (deferred to subsection (b, c) : [b R b), b.
D.2.1 for cleaner presentation), and assumes (b, c) belongs the set
23

---

Published as a conference paper at ICLR 2022
min R)]). In particular, the annulus : ((b, c) (c- f + (b-R)² [(0.1R)? (0.2R) a subset of V when R > Step (ti) considers (b, c) E EA.
We choose b, c. s.t. b 2 2. [b(R b). min R}}, so that pick up the tails in T to
R
T4 This means:
CE [[R - b). be 1 R). C bb R), bR] b E [R,
(D.7)
Bounding
/_
x
Using similar calculations as before, we have that when c log 22T
(which is the case for
[b, cl E A),
p P+
Px
E
<
+
+
+
1
4
(D.8)
p
p.
p.
< max
+ max
x,
x
220
+11
22<0
+
1
#>0
++1
+
1
Below bound the case where > 0; the other case (i.e. 0) has an upper bound of the same order following similar calculations and is hence omitted.
x
r
a>0
+1
s>0
E +1
2
x²
<
exp
+
br C)
x
exp
logg v 2t x
xE U.
lox 2 6
2
x2
log VT
2
8
R)²
exp
log 2T
2
re(0,
colog VTF
2
T
x
R² 2
exp
(R
b).
2 log 2
c- Iog 225
T((1
(c log v 2T 2
(c log /2m)²
exp(
(-c)
exp
+ (T)
+
exp
22t
262
/2T
c-log V2T
262
R²
(c log V2mT bR)²
+ exp
exp
+ RTT,5
V 2
2
22T
21/
(c
log / 2T
bR)²
+ (R - -))
exp
252
(D.9)
where step (1) uses calculations in equation
D.16 D.19
Ignoring small constants log 2 in c
log / 2T, and denoting E, == exp
E2 = exp
(c-bR)²)
for notation convenience, we
267
2F
24

---

Published as a conference paper at ICLR 2022
can substitute equation D.6 and D.8
into equation
D.5 as:
R²
6R b)
1 +
+ log v2
c
Px
2
+ 9
R2
<(R-b) 6) (T
()) + x + +T3
(1)
11) T )
+ log V2 - -0.12 (21 (0)
+ TT + TT2 + )
2
R²²²
=O(R) exp( -c) E1 bT (0) E1 + exp
F2 RT& E2 + (R ( b)Tr(
(-2)
+ ((RR)) (T1 (0) -2200
+ +T. + 1
(0)
R²
k(b,,)R2 c)
k(bb
=O(R) exp(- (c)) exp
2 (-2
O(R²) ((RR()(R)))))))
8
ka(b, c) R²
-O(R) exp
(D.10)
where x(),c) E 13. q is the constant defined in equation D.6
Since T E R. ||T, +||= (R),, and the proof is completed by:
( exp (- <(b.c).n' R
k(b,c) ((bbcc)-P. R2
(V)())
Tx
O(1) exp
(D.11)
T
8
D.2.1 CALCULATION DETAILS FOR EQUATION D.6 AND D.8
We now calculate term T. and T.()) used in equation D.6 and
D.8
x²
6² -c)
exp (- (I
(_ (x-b)²² b)2
T
exp
+ bx
C
= exp
cologg V2E
2
2
colgg VIT
2
6
x²
exp
exp
2
x C- lag Jn
2
exp
62
lug
exp
[-2
c- log /25 - -1)
2)
c- log 2nT < 12
/c-loR 22x - b) }
cxp
62
lug v2
exp
1
c - log 2 2 8²
V2
b- colox
1
V2
exp
(c-log v 22
26
log 22 < b²
exp
62
2
c
<2
-- log wT
exp
(c-log 2nn)
262
c log V2 2 b²
(D.12)
T:
1
122
exp
2TT
2
22
(c-log v 2
(D.13)
22
VIE
exp
20
- log 2T > 0
(e-log v2+)²² 26a
exp
c log v 2 < 0
le-
log
v2nl
1
(x - R)2
x²
exp
exp
e- log 2
222T
2
Nx c- VO RR 2nn
2
V2H R
log v2r
exp
pollo log voz
R)²
c- colog V2T < bR
(D.14)
c-llg
R2)2
1
exp
c - log / 2m 2 bR
2n looo Van 12
2
25

---

Published as a conference paper at ICLR 2022
T = cxp
R 6)2
+ -
R²=
-2log 2T
/
exp
(x - (R - -6))
2
2
eologva vIT
2
(R
6)2
R²
x²
-2 -2log 2t
=ex
+ c
exp
2
2
lol
vIT
(R-b)
2
exp
(R-b)²
n1²
-2log 2TT
R- log 1og exp
(R (R-b -- --l vzr c-lagvar)
log V2* < b(R - b)
exp
(R-b)²
2
+
R
2og 2tT
ven
(R-b)
exp
(R e م 1o
c log v 2x 2 b(R - b)
s- v'T -12)
1 2t
exp
(R-b))
2
+
R²
2
22 R b-
log.2 v22
exp
c - log v2T < b(R- -b) b)
1 RR)
exp
c- log Vo 2 b( - b)
22
C- Ing
van
-RR-b)
2
(D.15)
x²
71
exp
2 2
+ bi - -c) x
2E( c-lox VI
62
(x
6)2
(a b)2
exp
exp
(x - b) +b.
exp
2
J (0. e- log /27
2
x -olog /28
2
122
x2
6I110)
exp
exp
2
loy c EEE
2
1/2
x2
log v
b
+ +bT(0))
exp
exp
2
2
62
b²
(c log V2 63)2
))
+b1,00
exp
exp
exp
2
2
24/
1
(c
log
v2T)²²
exp(-c)
exp
bTT(0)
2T
2h2
(D.16)
x²
x22
exp
x.
exp
J 12
lox VI
/2T
2
2T
2
(D.17)
1
log 2 }2
exp
/2T
21/2
(x- -1)2
T
)x x
exp
JZE/0,
loy VI
2T
5
1
exp
(- (x- - R)²
(x R) + RTT.
E0
Ver
V2
2
log VTE
1
x
RT
(0)
1
x²
RI (0)
exp
r
exp
-
colon von
R]
V2T
2
V2TT
2
R.2
1
(c
log
v 2x
bR)2
+ RT
(0)
2T
exp
2
2m
exp
2h2
3
(D.18)
26

---

Published as a conference paper at ICLR 2022
RR - b)
R²
(- (x -
(R
(R-b)) (b)))
exp
+
log 2T
exp
(x - (R - b)) (R 6)TT
2
o- log V3n
2
RR b)
R²
x
exp
+
log 2
exp
+ (R - b)T
2
2
-- log
v/
(RR-))
2
RR b)
+ c-
R²
- log 2
|exp
x² x0
(R b)T
2
2
(R-b)
(c
log
2m bR)²)
+ (R b)T
exp
22
26
(D.19)
D.2.2
CALCULATIONS FOR ò < 0
We now calculate the gradient norm bound for the case where Recall that:
V |
p
Pa
x
+
p ps
(D.20)
+
Bounding
p= 1
x+1
exp
+ bx c) exp
(x-R)² 2
log 2
p
exp (ber
log V2T)
+1
x²
x²
log V
+ bu
log 2
2
co1g VIF
T,
x
R²
(I
R2)²
exp
+ (R b)z
2 log v 2n
exp
log / 2m
log V2x
2
log
/2a
2
(0)
yr(0)
01)
(D.21)
where T.0 terms are calculated as:
x²
T:(00
exp
log 2T
c-log
2
5- log vir
cxp
(c-lug 2m))
25a
log v 2n
0
(D.22)
exp
(e-log v 24
log /2m
0
V
27

---

Published as a conference paper at ICLR 2022
x²
1b2
exp ( (x)
b)2
-2000
exp
+
br
c
=xxp
-0)
J x2
2
x2
log v2n
112
x²
exp
exp
log
2
3
exp
log V2x
eep
C- log Log./2 2
G- log 2
b < 0
12
2
exp
2
c- lng /2E
b
exp
1
log
v
> 0
cxp
2 b- ooing v
oxp
(o-log log v2x)2
242
log 2
b < 0
(c- log
v /2x)²
log /2r 6 > 0
V2n
exp
25
(D.23)
(R b)²
(Ir
(R -b))
exp
+
2 2oo V
exp
2
2
xe 2-1og Vax
2
RR
b)2
R²
2 exp
exp
+
2og 2m
2
2
lug VT
(R-B)
2
exp
(R-6)* 2)
R²
2 log 2
log exp
(R
oolog VBr
log 2
(R
exp
[R 8)
R²
2 log 22T)
exp
(R- 6-
lox 5x
log /2r (R b) >>
loy (R-
c log woz -R(
2r
exp
bR-
R²
v2n
c-log 128 (R-b)
exp
log /2r
(R- - b) > 0
12llg -R
V2r R-b- c-log vec exp
b
2n
(R - b) <0
2
(D.24)
(- (x ( R)²
1
x²
1/00
exp
exp
colog
2TT
2
c- lag VIz
2TT
2
1
12)2
R>> 0 c- log 22n
(D.25)
VIT 2m
-R
exp
V2T n
v2r
exp
22
2
R2)²
log 22m
R < 0
Bounding
P=Pa I S2
/.
p P+
P
P+
+
2 +
2
+
(D.26)
P=
P-
< mmax
max
1>0
2>0
E<D
1
As before, we will show the bound for the case where > 0; the other case (i.e. x < 0) follows similar calculation and has an upper bound on the same order.
First consider O, log 2T
p
Pa
+11 x +
+1"
1>0
x>0 7
(D.27)
(6)
R2
< px +
P
exp(
-pp(-c) c) +1
+1
exp
(- 2
= =0(1),
b +1
1
R
x>0
x>0
28

---

Published as a conference paper at ICLR 2022
where step (i) uses the following:
x
(x
bx)
exp
+
bx
exp
exp
(x b+ b)
2
2
2
0>0
#20
b²
exp
exp
+6
exp
2
2
b²
82
b²
6²
exp
exp
exp
exp(
(c)
(D.28)
2
2
62 +1
2
1 +1
(x
R)2
R
R
R²
exp
x S exp
exp
2
1
+
R
2
4.0
R
-1+
exp
1+ R
2
When b < 0, c
log v 2T
<
0.
P.
+
0>0
2 +
9
2>0
+1
P+q
q +
pr +
+
Po
(D.29)
[0 c-log VZF
x2
log v
[ c- log VI
x2 colog VIn
T
(1))
<16 max{xx [6]],
where T terms are calculated as:
c-log /2z 8
T,-- /
x² (-2)
(c - log v 22
Jz
logg / qu
exp
=1 1 exxp
exp
212
(D.30)
132
(x - b)²
p = exp
exp
JnZ e-log VaN
2
p- log
2
62
x²
x22
exp
exp
+ b x
exp
-
(D.31)
2
Lox -
x2
log
2 -b
2
1
(c
log
v 2TT)
1
cxp
C
log 2
2b2
6
(xr (x- R22
(1)
Poq
exp
bx + loo 2m
ZEJO
log 22n
P
2E e 20000 2
RR
b)2
R²
(x (R - b))2
exp
+ c -log 2
exp
2
2
ZEJO, loy VI
2
(R b)2
R2
x²
= exp
+ c - log 2
exp
(xr + R - b)
2
2
ZE|- (R-l-(Rbb).-- slog - -(l-bb]
2
R2
(o-log v2n
RT2
=exp
+ c - log 25 - eepp
+ (R - b) -
2
2
(D.32)
where (022 ((1) is:
2 R-b exp (- n²
(-1² 2 + log 2
(5-log VIF n2)²
c- log /2r > R R-1 b
exp
(11)
colog vIr (R-b)
33
(- (s lox vox vir RR}²
loy vu - (R-b)
1
exp
R-b exp
(- R² + + log v 2T
c- log 2 < R - b
(D.33)
29

---

Published as a conference paper at ICLR 2022
T(
(x - 12)2
1,-
Ps
exp
(x
R + R)
122
xx xx2 c-log
2
x²
x²²
12
c-log
VI
R
exp
2
I + R
J32
log
VI R
exp
(
(D.34)
log 2
R)2
+ R $
= exp
2
where 8 ((1) is:
1
exp
lug Vx
R1)
Ing 2
R
_
e
log
(D.35)
exp
log
RY2
log v
R
Combining equation D.21
D.27 and D.26 we have that || [LL(,, 32 max [6/ for 0.
D.3 PROOF OF LEMMA D.2
We first show the following claim, and prove Lemma D.2 at the end of this subsection:
Claim D.1. For any [b, c] IR, the gradient norm at t is [[V 32 max [R, [6]]
Proof. For parameter [b where b > 0, c
log 2TT 0.
|VL(T]l22 (
+1 I
Pa
+
p - P.
++1 q
c²
c²
RR
[[ bR)
exp(-c) -xpp cxp
( (0)
+ exp
exp
cxp
262
26
2b2
(c 2R)
+ RT3 (0)
+ exp
(R 6)(11) 00)
+ + (0)
T
(0)
+ T
(0)
T
00)
21
(8))
(b - 1)T (0) + 10)
(0)
+ (R + 1)T (0)
+ + - b+ 1)T1 00)
<4+b + max { R b, 0} $ 2 maxx b).
(D.36)
where step (i) and (ii) use equation D.16 D.19 and equation D.12
D.12 D.15 Moreover, step (ii) in-
creases the value by at most 16. Hence overall we have L 2 32 max R2 b}.
When O, log v 2T <
p
Pe
P
T
+
+
4
(D.37)
p
P-
p
P2
< max
2 +
T.
T
xx00
+1
m>0
+
Jx00
+
J<0
E +
9
30

---

Published as a conference paper at ICLR 2022
Let's bound the first term (i.e. > 0); the bound for the second term (i.e. 0) follows from similar calculations and is on the same order.
/
p
px
p.q
2
+
I
qe +
020
+1
1>0
2
9
+
820
a>0
exp
x²
T
exp
x²a
+ (R - b)æ + c
Rt2
- -log / x
2T
x>0
2
2>>
2
2
+ (R - b) exp
Rb + c log V 2T
+
(6- (b- 1) exp (-
(-2 2
R2a
+
log V2T
R - b > 0
2
1 (6- Ry++1 exp
R
+ c - log v 2T
R - 6<0
2
O1).
(D.38)
Step (i) omits a factor of 1 and uses: /2m
/
x²
R²a
exp
+
(R - b)z +
2 2log 2T
200
2
2
(R
b)2
R
(x- (R
b))2 (R-((R-))
exp
c log 22T
exp
2
2>0
(R b)2
R2
x2
x²
exp
2
c log 2
xx> (23-((1-1)
exp
2 (
x x+ (R (R) b)
JD (x3-(H-b)
exp
2
(R b) exp
(
Rb + c log v 2T)
+ (b-R)2+1 exp
(-3 + log V2T
Rt
R-b>0 0
16- RF+I exp
R²
log v /2x
R - b<b (D.39)
For b < 0, similarly have |] 0mnx (R,bb)). The calculations are similar to the b > 0 case and hence omitted.
We are now ready to prove Lemma [.2] which we restate below.
Lemma D.3 (Lemma D.2 restated). Let = o(1). For any s.t. ||-|2 0.2R, let denote the point after one step of gradient descent from then || <.I|> 0.15R.
Proof of Lemma D.3
We will prove by contradiction. First assume that we can go from 7 where ||| T, 1| 0.2 to some r' where || 7. 1|25 0.15R. Then || T. is lower bounded as:
(2) 2 1b R1-mll V
1|
T.
| - T - -
(D.40)
(i)
R
>
b
R|
32mb
32m
b
b
where step (i) uses ||7- -+
|| [r[]]
11|2 ||/|-
|r
16 R). and step (ii) is by Claim D.I
On the other hand, we have
|| Tx | 0.15 by assumption, which when combined with equation 0.15R or b = O This means ||7 - T- -- 7-115 n/l VL(T)]= o(1) D.40 gives b < 1 # -3nn"
m R, [b])
o (R). However, we also have ||| 1-1 T. 1.112 0.05R e(R) by assumption. This is a contradiction, which means the assumption must be false, i.c. T' cannot
satisfy || T. 1 0.15R.
D.4 PROOF OF LEMMA AND LEMMA
We prove Lemmas 4.1 and 4.2 in this section. First recall the lemma statements:
31

---

Published as a conference paper at ICLR 2022
Lemma D.4 (Smoothness P Pt, Lemma 4. restated), Consider the 1d Gaussian mean timation task with R := 10x - -8y1> 1. Then the smoothness at P = P. upper bounded as:
o maa :- max
(V2((T))) < -1p(--1/88
(D.41)
V2T
We will also need bound the strong convexity constant (i.e. smallest singular value) at P P":
Lemma D.5 (Strong convexity P P", Lemma
4.2 restated).
Under the same setup as lemma
4.1 the minimum singular value at P P. is o LLL(T=)) = θ exp (- R² 8 )
D.4.1 PROOF OF LEMMA 4.1 (SMOOTHNESS AT P = P.)
We will show the smoothness constant (i.e. max (2)))) is exponentially small the optimum, i.e. when P P.. The Hessian at the optimum is:
P.q T(x)T(x) do 1 / P-g Pa +q
L'
[xr, -1] [xc,
dr.
(D.42)
2 Px +
Recall that 0g = w.l.og, and assume 0 = >> 1. Then
L() 2
2SR/22 P. + (z))
P-d
T dx + 1
/
P.q T(x)T(z) dz
R/2 P. +
(D.43)
25
p.T(T))(z) dx R/2
1
(T)))((x) da.
#SR/2
Let S C 2R2 denote the circle centered as the origin with radius 1, The maximum singular value is upper bounded by
1/D.9 P.q
(aiæ u2)² dx
T max
max [01:
1 Pa +
Ps (a1x - (z) dx + JD2R/2
ala13 az)² dr
max [01.02]ESt
2
U2RR/2
1
[/
D" (afa²
2a a2æ + a dx
q (aq=0"
2a 20ia + a²) dx
max (01.82JES!
JzSn/2
1//2
1
(
max
Pax +
qr²
P+x
20102
2
[0: aaJEES
xc
7
xx
Pa +
x>
To
0
To (i)
2
1
R²
- +
+
+
+
+
2
2
R
R
2
8
R
3
R²
R
R22
+ 2
exp
<
2
R
V
2m
2T
8
(D.44)
32

---

Published as a conference paper at ICLR 2022
where (i) substitutes in 1 or -1 1 for 01, 02 and uses the fact that the upper bounds for To. T1. T2 positive. (iz) uses the calculations on To to T2 shown below. We note that these calculations rely on properties of Gaussian and do not extend to general exponential families.
4
R²2
To
-2
q
exp
R
V2T
8
1>11/2
1
( - 0)
x² (
Ti
exp
xdr +
exp
vdæ
V/SR/2 2
R/2 2
(D.45)
(1')2
x²
exp
(R x²) x')dr +
exp
rdæ
2R/2
2
2
1/> 22T
2
2
R²
=R
gile S
exp
2T
Jx2R//2
Pe((2
2 3))
For T2, denote PR/2 =
Gaussian tail bound gives
exp (-16)
n22)
PR/2
Then calculate each term in T2 as:
v2k
/ P+ p+(x)=d
(x- - R)
exp
2dxx
15
V2T
2
(x - R)2
exp (-
(x R)²
exp
(x
Rt) xdx +
xdæ
454
V2T
2
2 2n
2
4
(ar R22
(x- 172 exp
exp
T
2
(x: R)dr
2T
V2T
1
R2
R
R-
Pn/2
exp
V2TT
R²
1
R22
+1)
cxp
R
R.
PR/2
exp
22T
8
22T
8
3R
1
R²
+ R2 PR/2
exp
2
2T
8
3R
R2
exp
+ R²
Pn/2
2
2
8
(D.46)
1
x
exp(
x2
2 )x
00
g(x)x²
dr
exp
x² dx
Pn/2
42
JoZ
2
v /2T
(D.47)
1 R
R22
exp
PR/22
v 2T 2
8
Hence T2 < R.
exp
+ (R²
+1)PR/2 < (R+ 2)
exp (-
/2=
33

---

Published as a conference paper at ICLR 2022
D.4.2 PROOF OF LEMMA 4.2 (STRONG CONVEXITY AT P P.)
Lower bounding a min follows a similar calculation as for upper bounding a max"
min 1 /. p-q (a.x -a2)=aa)²au dr 2 min 4 /. max(p-, o) (ar.eg]e
min
2 n P. +
[ur.wg]est
P.g
(a12- az) dr
Mren Pe (a10 02)² dr q ( az)² dx
min [a1.ag|eS]
U/gR/2
R2
201 + a²)) do [f VESR/ D. (aix²
min (11-
9 (aro?
-201 + ag) dr
min [2i.0
1 Paot
q
.ai
Patt +
qu
20102
x2
2
1/ 4
Po
02
To
(81
1
R
R 1 2 +
2
mm
exp
min
R
40102 +
2m
1
exp
R²
8
min 0.11
R 1
2 R
a²
1av / 1 a²
R - aa²)
1
R
R 2 40 v1
1
V
2m
exp
8
min [
2
a²
R
1
R
RR 1
exp
min 0,
d²
+ R
V 2m
exp
1R 2/m
(D.48)
where (i) uses the calculations on To to T2 stated in equation D.45 and D.46
Step (ii) replaces
0 to remove the ( term.
D.5 PROOF OF LEMMA 4.3 (CURVATURE AT P= QQ)
Lemma D.6 (Smoothness at P = Q. Lemma 4.3 restated). Under the same setup as Lemma 4.1
the smoothness at P = Q is lower bounded as T 2 ((Tg) 2
n² 2.
Proof. The result follows from direct calculation of the Hessian at P Q:
1
P. + q
V (ZT(T)
T(x)
(a)) dx
2
+ IEQ ([=) [x, -11 )
x
1
E.
+ Egx²
0
E
[r, -1l
2 (D.49)
8
-1
8
R2 +
2
0
8
2
Hence Fmax (.L. 2 e, (IL(T)e 2 n² 2.
D.6 PROOF OF THEOREM (LOWER BOUND FOR SECOND-ORDER METHODS)
The proof of Theorem 4.2 is similar to that of Theorem 4.1 where show that there is ring of width (RR) in which the amount of progress at each step is exponentially small, hence the number of steps required to cross this ring is exponential.
34

---

Published as a conference paper at ICLR 2022
We show that starting from To Tq. the optimization path will necessarily steps into A:
Lemma D.7. Let == O ( where Xp = mingge miin ((2)()))) AM =
maxéee max (V2 L(Ta)) defined in Section f For any s.t. ||T +. 0.2R, let r' denote
the point after one step of gradient descent from т, then || Tell2> 0.15R.
Proof. First note that Vr, the next point after one step of Newton update is: To
= -
TV' = - = =
T T.
+
|| To 112
|| Tx
(D.50)
where v ( | T--1-112
is orthogonal
To.
Hence
||T - Tall - /< (--)(())-~199
-- To
)
- -
|| Ta 11
(V((T),
|
--
71 VL
32m max RR, [6]
min (V2L(T))
To
minn (22((T)
min (PL(TT)
(D.51)
(44)
max R. [6|} 32 max R. [6}
64 max R. |b
32
min [T))
AM
Am
R²
where step (i) uses Claim D.I and step (ii) follows from the choice of n)
Suppose || - 12. 0.15R, then
64 max ( (R, [b]
0.05R > T -117' -xlLS
R² b S(R*).
(D.52)
However, ||'' entails b ((R), which is contradiction. Hence it must be that |/ - 0.15R.
- -x
Proof of Theorem 4.2 By Lemma D.7 the optimization path will go point 7' E A s.t. ||' T>l12> 0.15R. From any such r', the shortest way to exit the annulus A is to project onto the inner convex set. Denote
circle defining A, i.e. the circle centered T. with radius 0.1R which this inner circle as B(T,, 0.1R) whose projection is IB 0. R), then the shortest path is the line segment r' 11 (L. (T'). Further, this line segment is of length 0.05 since -r--,,||> 0.15R by Lemma D.7
However, the decrease of the parameter distance (i.e. || Tx (1) is exponentially small at any point in A::
T - T.|| -|]l-||Te+1
T.lls
7 o m (())
Tt - To (VL(TT))
1 - T. 112
(D.53)
VL((T))
T.-T.
x(b.c) n2?
(8))
TTe-T.
(186)
exp
8
AM
R3
where step (i) uses the caleulations in equation D.51
step (ii) use the choice of my. and step (idi)
uses Lemma D.1
Hence the number of steps to exit A is lower bounded by
0.05R 2 exp
n² 2 an2 exp
52))
E ADDITIONAL NOTES ON EXPERIMENTS
E. IMPLEMENTATION DETAILS
Parameterization: For the 1-dimensional Gaussian, we take P., Q to have mean μ., 16, My = 0, and unit variance o2 o² 1; Figure 4a for an illustration of the flat loss landscape. We
35

---

Published as a conference paper at ICLR 2022
144
4,0
1.0
35
25
2.0
02
1.0
20
(a) Id Gaussian mean estimation with o² = 1 and
means Hy 0, 16. The and axis cor- respond the estimated mean μ and the NCE loss. The left and right vertical lines show Pe and p.,, and the red and green curves show the pdfs of Q and P..
(b) 2d Caussian mean estimation with o² and means μ4 0, 8. The blue surface shows the NCE loss surface, and the orange and green sur- faces show the pdfs of Q and P..
Figure 4:
An illustration of the flat landscape caused by the "density chasm" NCE loss quickly flattens out for 1d and 2d Gaussian mean estimation.
use h(x) == - ). 16-dimensional Gaussian, P., Q share the same mean μ. = 0 but have different covariance with Cov, = Ia and Cov, =
T(x) = [x, -1] be consistent with the notation in Section For the
sa)), where 8, = Uniform [8 x 0.75, 8 x 1.5).
For MNIST, adapt the TRE implementation by Rhodes al. (2020). We model the log density [(z
ratio log(p/4) by quadratic of the form g(z) == -f(x)
where f is ResNet-188 18, and W, b, are trainable parameters with W constrained to be positive definite.
b f(x)
Implementation notes: We include some tricks we found useful for implementation:
Calculation in log space: instead of dividing two pdfs, found it more numerically stable to subtraction between the log pdfs and then exponentiate.
Removing common additive factors: the empirical loss is the average loss over a batch of samples where overflow can happen. We found more stable calculate the mean by first subtract the largest value of the batch, calculate the mean of the remaining values, then add back the large value- akin to the usual log-sum-exp trick. For example, mean ((a b)) max(a, b) mean max b),6 max(a, b)]).
Per-sample gradient clipping: is sometimes helpful to limit the amount of gradient contributed by any data point in batch. We ensure this by limiting the norm of the gradient, that is. the gradient from a sample x is now min(1, [[((())]]
V[(x) for some prespecified constant (saai
ct al. 2021).
Per-sample log ratio clipping: an alternative to per-sample gradient clipping is to upper threshold the absolute value of the log density ratio each sample, before passing it to the loss function. Setting a proper threshold prevents the loss from growing too large, and consequently prevents a large gradient update.
E.2 ADDITIONAL RESULTS
Results for training with a larger computation budget: We provide additional results on Gaussian mean estimation and MNIST, both trained with a larger computation budget.
Figure 5 shows results similar to those of Figure I except that we now run the optimization process for 5 times longer than in Figure L and additionally show results on eNCE optimized with gradient descent (GD). The conclusion is the same as that of Figure I for both NCE and eNCE, normalized
'Generally, for d-dimensional Gaussian with mean μ and diagonal = diag([of.....o2)) o2)). the exponential parametrization is r = (2m)( det(")))
covariance matrix
"This is hecause the mean function is internally implemented as the sum of all entries divided by the batch size, and the sum of large hatch size where each value also large lead overflow.
36

---

Published as a conference paper at ICLR 2022
NCE, GD
NCE,NGD
oNCE. CD
oNCE, NGD
120
15
90
10
100 200 300 400 500
300 200 330 400
500
Figure 5: Results for estimating 1d (left) and 16d (right) Gaussians, plotting min] - 12 (y- axis) against the number of updates T' (x-axis). Normalized gradient descent (NGD) significantly outperforms vanilla gradient descent (GD) for both NCE and eNCE In addition, eNCE decays faster than NCE when optimized with NGD. The results are averaged over 5 runs, with shaded areas showing the standard deviation.
NGD
oNCE,
1e-10
0.01
10:20
00001
2k 4t
24
Figure 6: Results on MNIST, plotting loss value (U-axis, log scale) against the number of update steps (z-axis). The left plot shows NCE optimized by GD (black) and NGD (yellow), and the right shows eNCE optimized by GD (black) and NGD (blue). The setup is the same as that for Figure except that we now let training run 4 times longer. NGD outperforms GD in both cases, consistent with the results in Figure 2
gradient descent (NGD) significantly outperforms GD. Moreover, eNCE performs competitively compared to NCE when optimized with NGD.
Similarly, we train with a large computation budget on MNIST, whose results are shown in Figure
6 The results are again consistent with those Figure
MNIST samples We run annealed importance sampling (AIS) Neal (001 following Rhodes et al. (2220) on the models trained on NCE and eNCE optimized with GD or NGD. Figure 7 8 show samples generated with 4k 10k sampling steps. from different random initialization. We can see that eNCE gives much sharper results than NCE, and eNCE with NGD results in more diverse samples. A downside though is that eNCE samples seem to show signs of mode collapse. However, it is unclear whether this is a problem with the model or due to the sampling procedure.
Results for training with other normalized optimization method: One interesting question to ask is, whether the results of NGD generalize to other optimizers that perform some form of nor- malization. One example that is commonly used in practice is the RMSprop, which performs per- coordinate normalization on the gradient. Specifically, at the lh step with gradient gt. R R.Spprpp [0, 1] hyperparameter
first updates a cumulative term V. = av + (1 =ag?, where a
E
6
5
9
P
5
5
5
2
6
Z
9 9
9
4
7
9
9 5
6
9
g
22
4
2
U
9
9
(a) NCE, GD
(b) NCE, NGD
(c) eNCE GD
(d) eNCE, .NDD
Figure 7: MNIST samples from 4000 sampling steps
37

---

Published as a conference paper at ICLR 2022
Z
9
5
5
2
5
2 9
9
5
3
AF
(a) NCE, GD
(b) NCE, NGD
(c) eNCE GD
(d) eNCE NGD
Figure 8: MNIST samples from 10000 sampling steps
NCE, GD
NCE, NGD
NCE, RMSprop
eNCE. GD
oNCE, NGD
oNCE, RMSonop
120
120
100
40
100 200 300 400 500
100 200
300 400
500
Figure 9: Results for estimating 1d Gaussian with NCE (left) or eNCE (right), using GD (gray), NGD (yellow for NCE, blue for eNCE ) or RMSprop (green). The effectiveness of RMSprop seems to depend on the task: RMSprop performs the best for NCE, but falls short than NGD for eNCE.
controlling how much to "damp" the current gradient, and the square 9i is applied entrywise. It then normalizes the gradient as 9r := g./ve, with division applied entry-wise.
Figure 9 compares RMSprop with GD or NGD 1d Gaussian estimation task. The results suggest that how well RMSprop performs may be task-specific: R.Spprpp performs the best when optimiz- ing for NCE, but only slightly better than GD when optimizing for eNCE. Moreover, NCE favors higher value of a where the best performance is achieved by 0.99, whereas eNCE prefers a to be small with a 0.01 performing the best.
is not yet clear what the theoretical answer should be for normalized methods in general: though methods like RMSprop perform certain form of normalization (e.g. per-coordinate normalization), so does Newton's 's method, and Theorem 4.2 has shown that it still suffers from an exponentially bad convergence rate (at least with standard choices of step size). It is unclear what quantity replaces the condition number of the Hessian for RMSProp, which governs the convergence of NGD. Theoretical guarantees for these optimization methods is an interesting open question.
38


Reviews:
[{"review_id": "sJjQ18zjJz6", "reviewer": "Reviewer_6syu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Pros:\nThe author constructs a bad case, and improves the NCE by fixing problems in the bad case. The improvement is theoretically guaranteed.\n\nQuestions:\n1. The Proposition 4.2 is confusing. It states that $||\\tau - \\tau^*|| \\leq \\delta \\Rightarrow L(\\tau) - L(\\tau^*) = R \\exp(-R^2 / 8) \\delta^2$. However, according to it, we can also derive $||\\tau - \\tau^*|| \\leq \\delta \\Rightarrow  ||\\tau - \\tau^*|| \\leq (\\delta+1) / 2 \\Rightarrow L(\\tau) - L(\\tau^*) = R \\exp(-R^2 / 8) ( (\\delta+1) / 2)^2$. Thereby, we have $||\\tau - \\tau^*|| \\leq \\delta \\Rightarrow R \\exp(-R^2 / 8) \\delta^2 = R \\exp(-R^2 / 8) ( (\\delta+1) / 2)^2 \\Rightarrow \\delta = (\\delta+1) / 2 \\Rightarrow \\delta = 1$, which is a contradiction. The author can use quantifiers like $\\exists$, $\\forall$ to make Proposition 4.2 more clear.\n\n2. In Section 4, the  $R$ appears before it is first defined. Besides, above Section 4.1, the author defines $\\tau(\\theta) = [\\theta, \\frac{\\theta^2}{2}+\\log \\sqrt{2\\pi}]$, but then says \"In particlular, $\\tau(\\theta_*) = [R, -\\frac{R^2}{2}-\\log \\sqrt{2\\pi}]$\". It seems that there is a contradiction between $\\tau(\\theta)$ and $\\tau(\\theta_*)$.\n\n3. Although the improvement can solve problems in the Gaussian case, it is not guaranteed that the improvement generalizes well on more complex data sets. I notice that the author provides results on MNIST and the loss curve becomes better. It would be better if more experimental results on more complex data sets are provides. For example, the author can show some generated samples of MNIST or try on datasets like CIFAR10 and provides FID[1*] results.\n\n4. The author can plot a figure of the landscape of loss in the 1-d Gaussian example. It helps readers understand the illness of the landscape better.\n\n5. The uniqueness in Lemma 2.1 needs $p_*(x) \\neq 0 \\rightarrow q(x) \\neq 0$ to hold.\n\n[1*] https://github.com/bioinf-jku/TTUR", "summary_of_the_paper": "This paper constructs a Gaussian case to illustrate why NCE doesn't work. The failure in this case is due to the flat loss landscape. The traditional GD or Newton's methods don't work on such a flat landscape. To overcome this problem, the author proposes a normalized GD, which improves the convergence rate. The author also introduces a modification of the NCE loss.", "summary_of_the_review": "This paper is generally solid, although there is some confusion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VdP6l-FtTV", "reviewer": "Reviewer_VmJ3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "**Caveats:**\n- I am not so familiar with the literature in this area, so cannot determine the novelty of the results or whether there are missing citations.\n- I did not read the proofs in detail, so cannot vouch for the correctness of the mathematical results.\n\n\n**Summary:**\n\nI think this is a good paper and I am in favour of its acceptance. I do have a few points of concern / thoughts on how the paper can be improved, but I hope the authors will take these into account. \n\nI think it is great when theoreticians analyse settings that are motivated by empiricists, as I believe that this synergy can lead to improvements in understanding of things that matter. This is an interesting and seemingly poorly-studied area. NCE and the related GANs are very widely used, and so improving understanding of them is important. \n\nThe paper is well written and explains the problem and their solution clearly. I didn't spot any technical issues, and I believe they make a solid contribution. By exploring the simplest possible empirical setting (1D Gaussians) they clearly highlight the issues with existing methods, but prove results that are much more general. \n\nTherefore, although there are some areas where things could be improved -- a sober explanation of the downsides of their assumptions, and where the connection to the empirical world might break down, as well as the experimental validation -- I am overall happy with the paper. \n\nPlease see the detailed comments below for all questions / wishes for the authors. Here I would like to highlight the main points of concern:\n\n- Discussion of the assumptions made -- under what conditions they hold and do not hold, perhaps with examples to give an intuition as to whether they are strong or weak assumptions. \n- Discussion of the gap between the theoretical setting they study, and the ones encountered in the 'real world'. For example: dimension, families of distributions, mini-batching vs full gradient descent. \n- Experiments: please provide code to make things easier for future researchers to build on your work. \n\n\nI am giving the paper a \"6: marginally above the acceptance threshold\", but would be willing to raise my score if the authors can address my concerns. \n\n\n\n\n**Detailed comments:**\n\n\nPage 3: \n- Exponential family: could you define the partition function and add a short comment on why this (or the log-partition-fn) is so important? \n- Assumptions 2.1 -> 2.4. Could you give examples of distributions that satisfy and violate these assumptions, to give an intuition of how strong/weak the assumptions are? \n\n\nPage 7: \n- Definition of eNCE. This is perhaps more of a philosophical question, and is also a stretch outside of my area of expertise, so it is possible that I am confused and talking rubbish, if so please ignore me (though I would appreciate an explanation of where I am wrong!) \n\n  As I understand it, the NCE loss can be viewed as an upper bound on the Jensen-Shannon divergence between P* and Q, i.e. if you minimise the loss wrt \\theta, the resulting minimum is exactly JS(P*, Q) [possibly with some sign flips and min <-> max].\n\n  Jensen-Shannon is an instance of an f-divergence. It looks to me like the same as the above could be said of the eNCE loss, but just with a different choice of f-divergence. Do you think that could be the case?\n\n  If so, that would be interesting connection to draw because there has been work in the generative modelling (GANs, VAEs etc) community on using different choices of f-divergences other than JS to overcome some limitations of JS. Of the top of my head I remember this 'canonical' paper, but I'm sure there are many other works, also probably some more theory oriented ones: https://arxiv.org/abs/1606.00709 (f-GAN, by Nowozin et al 2016) \n\n\n- Lemmas 6.1-2 and Theorem 6.1. There are no free lunches, so I guess there must be some downside of using the eNCE objective. I would suspect that the exponential (rather than log) loss would lead to numerical instability, or very large gradient variances when using mini-batch optimisation methods. Could you comment on this? Also, what is the impact of dimension on your results? It doesn't appear explicitly, but perhaps comes into play via \\lambda_min ? \n\n\nPage 9:\nExperiments: \n- Figure 1: what is meant by \"best parameter distance\"? I didn't quite understand the explanation in the Results paragraph. \n- Figure 1: Perhaps you could consider extending the plots beyond 100 steps, to see how the worse methods perform after a larger number of steps? (You could consider making the x-axis be log-scale.)\n\nFigure 2: \n- Qn1: Are you doing full gradient descent on MNIST? (i.e. without minibatching?) \n- Qn2: Rather than comparing to the baseline of a fixed 2k budget, why not let all the methods run for a long time and see where they converge, and use that as the baseline? [It doesn't say how long a run of 2k steps takes, but I imagine not so long?]\n\n- Could you comment on the full gradient descent assumed in the paper/experiments, vs the mini-batch based methods commonly used by practitioners?\n- I'd also be interested to see how the experiments behave if you repeat them just naively using mini-batches of different sizes.  \n- Please make code for the experiments/methods available -- this is the best way for readers to check if they are not sure that they understand something with the implementation. \n\n\nMinor: \n- Page 3: the spacing seems to be a little messed up here, e.g. in lines 2 and 3 of assumption 2.3 the equations intersect a little bit.\n\n\n\n\n", "summary_of_the_paper": "TLDR: The authors theoretically study convergence properties of the Noise Contrastive Estimation (NCE) loss, identify issues that make its optimisation difficult in some practical scenarios, propose a method to resolve this and provide theoretical guarantees that their proposal works. \n\nLonger version: \n\nThe authors point out that although NCE in theory should work regardless of the choice of noise distribution Q (assuming population distributions and ignoring optimisation etc), practitioners have empirically found that the choice of Q is crucial to methods working well.\n\nThere is not a great deal of work theoretically analysing the NCE objective, and so the reasons for why choice of Q is so important is not rigorously understood. \n\nIn this paper they study the setting in which all distributions are in the exponential family of distributions. \n\n- They first show that in the very simple case of 1d Gaussian distributions, if the means are far apart then the number of gradient updates required to make the distributions close grows exponentially in the initial distance (because the norm of the update steps decay exponentially in this distance) \n- They next show that, provided the distributions are 'sufficiently close', using *normalised* gradient descent results in requiring only polynomially many steps.\n- Next, they show that modifying the NCE loss (exponential-NCE) results in such polynomial guarantees even without the distributions being 'sufficiently close'\n- Finally they validate their theory with basic experiments.\n\n", "summary_of_the_review": "\nI think this is a good paper and I am in favour of its acceptance. I do have a few points of concern / thoughts on how the paper can be improved, but I hope the authors will take these into account.\n\nAs such I have set my recommendation to \"6: marginally above the acceptance threshold\", but will increase my rating if the authors are able to satisfactorily address my comments.\n\n[Edit: updated my score to \"8: accept, good paper\" after author response] ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QIohDD8XVjI", "reviewer": "Reviewer_rZGo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strength\n-\tTheoretically understanding of NCE method is an important direction and I believe this paper gives some interesting results in this direction. \n-\tThis paper gives a concrete reason and example to explain why NCE can fail in practice in certain situation. Authors further give several ways to provably overcome the issue, which is quite interesting.\n-\tThe paper is overall clearly written and easy to follow.\n\nWeakness:\n-\tThe paper only studies the NCE method for the exponential family of probability distribution, which does not include the more complicated distributions that might be used in practice. However, I would not view this as a major weakness, as the current results already seems to be interesting to me.\n\nSome minor comments:\n-\tAt the beginning of page 4 (Overcoming flatness using normalized gradient descent): use delta without explanation (which I believe is the distance to ground truth according to Theorem 5.1)\n-\tProposition 4.2: missing an O(1) factor in front of R exp(R^2/8)\\delta^2 ?\n", "summary_of_the_paper": "This paper studies the noise-contrastive estimation (NCE) method for the exponential family of probability distribution, which is usually used to learn probabilistic models. The authors first give a negative result in the setting of Gaussian mean estimation, which shows that NCE suffers from the ill-behaved population landscape when the proposed distribution is far away from the target distribution. As a consequence, standard gradient descent and Newton’s method need to run exponential time for convergence. To overcome this issue, authors first show that normalize gradient descent (NGD) can have polynomial convergence guarantee under certain condition. Furthermore, a variant of NCE called eNCE was proposed so that NGD can converge to optima within polynomial time. Experiments are also provided to show that using eNCE with NGD can have comparable performance with NCE.", "summary_of_the_review": "Based on the above comment, I believe this paper gives interesting theoretical results on NCE and would vote for accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2tcvTY-nVuk", "reviewer": "Reviewer_yXSX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper has many strengths. It takes a step back to ask a fundamental question in the Contrastive Learning (what happens when the discrimination task is too easy) and Generative Modelling literature (what happens when the data and noise are too far from each other - this is a motivation behind current advances in diffusion models). \n\nIt deals with it effectively while proving an analytical characterisation on a simple yet generic use-case (exponential family distributions). For another, related Contrastive Loss (InfoNCE), intuitions that the gradient norm is related to the hardness of the task are explored in Khosla et al 2021, yet a complete formalization is not provided. Furthermore, Pihlaja et al 2012 consider modifications around the NCE loss and comment on the effect (e.g. stable gradients) on the corresponding estimation tasks, yet a conclusive recommendation is not reached. This paper makes a convincing case on how to modify the loss with algorithmic considerations in mind. \n\nOut of curiosity:\n\n1. Is it possible to empirically compare NGD with other normalized-gradient methods?\nBecause a central contribution is \"normalizing the gradient\", would it be worth comparing the authors' Normalized Gradient Descent (NGD) with other normalized-gradient methods (Adagrad, Rmsprop, Adam) from recent years in the Stochastic Optimization literature? Or with other such methods?\n\n2. What is the impact of the proportion of noise samples hyperparameter on this paper's analysis?\nThe NCE task in this paper has fixed the proportion of noise samples at 50%, as is common in the literature. Do the authors know how this hyperparameter might impact the loss landscape and their results?\n", "summary_of_the_paper": "This paper examines Noise-Contrastive Estimation (NCE) from an optimization perspective. \n\nThe NCE task consists in training a Discriminator to distinguish between data and noise samples. Prior works observe that this task is \"too easy\" when data and noise distributions are \"very distinguishable\", which leads to poor estimation. This paper provides a formal explanation for this - the loss landscape becomes flat - along with an analytical formula for a simple model (1D mean-parameterized Gaussians). \n\nTo remedy this problem, previous literature has sought to modify the task itself, by breaking it down into a sequence of harder subtasks (GANs, Flow-Contrastive Estimation, Telescoped Density Ratio). This paper proposes to keep the task at hand, but enable the optimization to cope with the difficulties of a flatter landscape. It does so by:\n\n1. Modifying the optimization algorithm: normalize the gradient at every step\n2. Modifying the loss: still density-ratio based, but replace the sigmoid-log with a square root\n\nThese two contributions are supported theoretically, using the exponential distribution as a study case. Respectively,\n1. Provides a polynomial convergence rate in the parameter distance (i.e. how different the data and noise are) and Hessian conditioning number (i.e. local curvature near optimum)\n2. Expresses the Hessian conditioning number as polynomial in the parameter distance and dimension, to complete the convergence rate characterization\n\nThe effect of either modification is empirically verified on the MNIST dataset. ", "summary_of_the_review": "I have not read the proofs in detail. This optimization angle on NCE seems rather new and the overall expose seems convincing and beneficial to the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This contribution investigates and takes a step back on an important problem in recent ML, namely the impact of the noise distribution in density estimation using Noise Contrastive Estimation. The work offers both theoretical insights and convincing experiments.

For these reasons, this work should be endorsed for publication at ICLR 2022.
Decision: Accept (Spotlight)