Pitfalls of Gaussians as a noise distribution in NCE
Authors: Holden Lee
Chirag Pabbaraju
Anish Prasad Sevekari
Andrej Risteski
Venue: ICLR 2023 poster (2023)
Keywords: NCE
Noise Contrastive Estimation
Generative Models
statistical efficiency
theory

Abstract: Noise Contrastive Estimation (NCE) is a popular approach for learning probability density functions parameterized up to a constant of proportionality. The main idea is to design a classification problem for distinguishing training data from samples from an (easy-to-sample) noise distribution $q$, in a manner that avoids having to calculate a partition function. It is well-known that the choice of $q$ can severely impact the computational and statistical efficiency of NCE. In practice, a common choice for $q$ is a Gaussian which matches the mean and covariance of the data.

In this paper, we show that such a choice can result in an exponentially bad (in the ambient dimension) conditioning of the Hessian of the loss - even for very simple data distributions. As a consequence, both the statistical and algorithmic complexity for such a choice of $q$ will be problematic in practice - suggesting that more complex noise distributions are essential to the success of NCE.

Published as a conference paper at ICLR 2023
PITFALLS OF GAUSSIANS AS A NOISE DISTRIBUTION IN NCE
Holden Lee"
Chirag Pabbaraju"
Johns Hopkins University hlee2838 fhu. edu
Stanford University
cpabbara@cs sta.ecsdssaaarrrreed...
Anish Sevekari"
Andrej Risteski
Carnegie Mellon University asevekar andrew. cmu. edu
Carnegie Mellon University aristeske andree.. cmu. edu
ABSTRACT
Noise Contrastive Estimation (NCE) is a popular approach for learning probability density functions parameterized up to constant of proportionality. The main idea is to design a classification problem for distinguishing training data from samples from an easy-to-sample noise distribution g. in manner that avoids having calculate a partition function. It is well-known that the choice of q can severely impact the computational and statistical efficiency of NCE. In practice, common choice for q is a Gaussian which matches the mean and covariance of the data. In this paper, the ambient dimension) conditioning of the Hessian of the loss, even for very simple data distributions. As consequence, both the statistical and algorithmic complexity for such choice of will be problematic in practice, suggesting that more complex and tailored noise distributions are essential the success of NCE.
show that such choice can result in exponentially bad (in
INTRODUCTION
Noise contrastive estimation (NCE), introduced in (Gutmann & Hyvärinen, 2010; 2012), is one of several popular approaches for learning probability density functions parameterized up constant of proportionality, i.c. p(z) xx exp(Ee(z)) for some parametric family {Ee A recent incarnation of this paradigm is, for example, energy-based models (EBMs), which have achieved near-state-of- the-art results many image generation tasks (Du & Mordatch, 2019; Song & Ermon, 2019). The main idea in NCE to set up a self-supervised learning (SSL) task, which we train a classifier to distinguish between samples from the data distribution P. and known, casy-to-sample distribution Q, often called the "noise" or "contrast" distribution. can be shown that for a large choice of losses for the classification problem, the optimal classifier model is (simple) function of the density ratio p=/q. so an estimate for p. can be extracted from good classifier. Moreover, this strategy can be implemented while avoiding calculation of the partition function, which necessary when using maximum likelihood to learn p".
The noise distribution q is the most significant "hyperparameter" in NCE training, with both strong empirical (Rhodes et al., 2020) and theoretical (Liu et al., 2021) evidence that a poor choice of can result in poor algorithmic behavior. (Chehab et al., 2022) show that even the optimal q for finite number of samples can have unexpected form (e.g., it is not equal to the true data distribution p.). Since q needs to be distribution that one can efficiently draw samples from, as well as write an expression for the probability density function, the choices are somewhat limited.
particularly common way to pick g is as a Gaussian that matches the mean and covariance of the input data (Gutmann & Hyvärinen, 2012; Rhodes et al., 2020). Our main contribution in this paper formally show that such choice can result in an objective that statistically poorly behaved, even for relatively simple data distributions. We show that even if p* is product distribution and member very simple exponentaal family, the Hessian of the NCE loss, when using a Gaussian
Alphahetical ordering.

---

Published as a conference paper at ICLR 2023
noise distribution q with matching mean and covariance has exponentially small (in the ambient dimension) spectral norm, As a consequence, the optimization landscape around the optimum will be exponentially flat, making gradient-based optimization challenging. As the main result of the paper, we show the asymptotic sample efficiency of the NCE objective will be exponentially bad in the ambient dimension.
OVERVIEW OF RESULTS
Let P. be distribution in parametric family {Po) Dee). We wish to estimate P. via Po for some 0, by solving a noise contrastive estimation task. To set up the task, we also need to choose a noise distribution Q. with the constraint that we can draw samples from it efficiently, and we can evaluate the probability density function efficiently. We will use po. Ps. 9 to denote the probability density functions (pdfs) of Pa. Ps, and Q. For data distribution P. and noise distribution Q, the NCE loss of a distribution Pa is defined as follows:
Definition (NCE Loss). The NCE loss of Po w.r.t. data distribution P. and noise is
L(Pp)
1 - log
Pe
Eq
log Po q
Po + q 2
P. and Moreover, the empirical version of the NCE loss when given i.i.d. samples (zi....,, (n) (y1,..., Un) ~ Q" is given by
(0) 1 Σ
po
Σ
n
2 log
log
(2)
po( + ((x2))
(v() ((1))
i=1
By slight abuse of notation, we will L((), L(po) and L(Pa) interchangeably.
The NCE loss can be interpreted as the binary cross-entropy loss for the classification task of distinguishing the data samples from the noise samples. To avoid calculating the partition function, one considers it as an additional parameter, namely we consider an augmented vector of parameters
(0, c) and let Pa(x) exp (xpr - c). The crucial property of the NCE loss is that it has unique minimizer:
Lemma (Gutmann & Hyvärinen 2012). The NCE objective in Definition I is uniquely minimized 6, and log(J, exp( Eg- (x))dx) provided that the support of Q contains that of P..
We will be focusing on the Hessian of the loss L., as the crucial object governing both the algorithmic and statistical difficulty of the resulting objective. We will show the following two main results:
Theorem 3 (Exponentially flat Hessian). For d > 0 large enough, there exists a distribution P. Po. over Rd such that
E [x]] = 0 and P, [xx La-
Pa a product distribution, namely p. (I .2..... ..) -I- (xx).
The NCE loss when using = NO, Ia) as the noise distribution has the property that
L(--)l)) S exp (2)))
We remark the above example of problematic distribution P is extremely simple. Namely, P is a product distribution, with 0 mean and identity covariance. actually is also the case that P* is log-con oog-concave-oo concave-whicl which is typically thought of as an "easy" class of distributions to learn due to the fact that log-concave distributions are unimodal.
The fact that the Hessian is exponentially flat near the optimum means that gradient-descent based optimization without additional tricks (e.g., gradient normalization, second order methods like Newton's 's method) will fail. (See, c.g., Theorem 4.1 and 4.2 in Liu et al. (2021).) For this will be merely an intermediate result. We will address a more fundamental issue the sample complexity of NCE, which is independent of the optimization algorithm used. Namely, large number of samples, the best minimizer of the empirical NCE might not be close to the target distribution. Proving this will require the development of some technical machinery.
will show that without
More precisely, we use the result above to show that the asymptotic statistical complexity, using the above choice of P Q. is exponentially bad in the dimension. This substantially clarifies results in
2

---

Published as a conference paper at ICLR 2023
Gutmann & Hyvärinen (2012), who provide an expression for the asymptotic statistical complexity in terms of P", Q (Theorem 3, Gutmann & Hyvärinen (2012)), but from which it's very difficult to glean quantitatively how bad the dependence Unlike the landscape issues that (Liu et al., 2021) point out, the statistical issues are impossible to fix with better optimization algorithm: they are fundamental limitations of the NCE loss.
dimension can be for particular choice of P Q.
Theorem (Asymptotic Statistical Complexity). Let d > be sufficiently large and Q = NO, Ia).
Let on be the optimizer for the empirical NCE loss L (0) with the data distribution P. given by Theorem 3 above and noise distribution Q. Then, as n + 00, the mean seean-squrrdd error satisfies
0.1 1:
exp(S(())
E
0n
EXPONENTIALLY FLAT HESSIAN: PROOF OF THEOREM 3
The proof of Theorem 3 consists of three ingredients. First, in Section 3.1, we will compute an algebraically convenient upper bound for the spectral norm of the Hessian of the loss (eq. (1)). We will restrict our attention the case when {Po} belongs to an exponential family. The upper bound will be in terms of the total variation distance TV,.., Q) and the Fisher information matrix of the sufficient statistics at Oz. Here, P. denotes the true data distribution and Q denotes the noise distribution.
Then, in Section 3.2, we construct distribution P for which the TV distance between P and Q is large. We do this by "tensorizing" a univariate distribution. Namely, we construct a univariate distribution with mean 0 and variance 1 that is at a constant TV distance from standard univariate Gaussian. Then, we use the fact that the Hellinger distance tensorizes, along with the relationship between TV and Hellinger distance, to show that TV ,Q) 2 1 - 8d for some constant å < 1. (See Wasserman (2020) for detailed review of distance measures.) Section 3.3 bounds the Fisher information matrix term, completing all the components required to establish Theorem 3.
3.1 BOUNDING THE HESSIAN IN TERMS OF TV DISTANCE
Suppose } } is exponential family of distributions, that is po(x) = Tz))), where T(x) is a known function. Then, a straightforward calculation (see e.g., Appendix A Liu et al. (2021))
shows that the gradient and the Hessian of the NCE loss (eq. (1)) with respect @ have the following forms:
Voro(=) po(x) T(x),
(3)
1
/
VoL(Do)
(po P. (.))d,,
(4)
2 Po +
1
(p. + q)pog (xx) dæ.
ViL(P))=
(5)
2
(po + q)²
For 02 and po = Pa, we have
V.L( l P- q
P-q T(x) dx = min(p=, (z) dr
(6)
2
The second line holds since p.q min(p.. 9). max(p..g) poty
S min(p=, 4) Applying the matrix version
p-+y
of the Cauchy-Schwee inequality (Lemma 9, Appendix A) to eq. (6) with two parts min(p-(x) Vp.
and [x)) T / (x), we obtain
( min(p.,0)) 1)2 S
1 2
(V |
Pa
1
(/. min((p. 9)xz)
((lIraai(()) (I) (x))x
1/4
$ 2
=1 >|188((P))] $
1
IV(P..Q)
3

---

Published as a conference paper at ICLR 2023
We bound the two terms in the product above separately. The first term is small when P. and Q significantly different. The second term is an upper bound of the Frobenius norm of the Fisher matrix at P.. We will construct P. such that the first term dominates, giving the upper bound required.
3.2 CONSTRUCTING THE HARD DISTRIBUTION P.
The hard distribution P. over Rd will have the property that Ep, [x]] = O. [p,[ la. but will still have large TV distance from the standard Gaussian Q (0, Ia). This distribution will simply be product distribution the following lemma formalizes our main trick of tensorization to construct a distribution having large TV distance with the Gaussian.
Lemma 5. Let d > O be given. = -0, Ia) be the standard Gaussian in R Then, for some 1, there exists a log-concave distribution P (also over IRd) with mean O and covariance Ia satisfying (V(P,Q) 2 1 - 84.
Proof. Let denote the standard normal distribution over R. Let P be any other distribution over with mean and variance that satisfies p(P. Q) = 8 < 1, where p(P, Q) S. vpq dx is the Bhattacharya coefficient. Since tensorizes (Wasserman, 2020), we have that p(pd Q²4) = p(P, Q) for any > We can then write the Hellinger distance between P, Q as
(P)P.Q) = Vpq dx 2(1 p(p, ())
(8)
Further, we also know that
1 II (Pd Qt) S TV(Pa, - p() S TVV(P (9) - 1 - 8d S TV(Pa, Q*). 2
Setting P pd and noting that Q² = Q -N(0, Ia), have TV
8d. Finally, if the chosen P a log-concave distribution, then so is pd since the product of log-concave distributions is log-concave, which completes the proof.
We will now explicitly define the distribution P& that we will work with for rest of the paper. Definition 6. Consider the exponential family (po(s) exp(0"T(x)) PER given by the suffi- cient statistics T(x) function á given by
x/ 1). Let P. pd where f is the distribution on I with density
p(x) x exp
We will set the constant of proportionality and a appropriately to ensure that P has mean 0 and variance 1. Note that P. Po. for 0.
- , log C).
0, is log-concave. Further, symmetry of around the origin gives E[ = 0, and the choice of a ensures that Var = The normalizing constant satisfies
Since d' logg - dzd
2 /
e dx = 2
l e dx.
C
Substituting
x² gt. dt do
3
4011 dx gives
C C= σ /-
= (
5
3-3
2 4
201'
2
where l(2) is the gamma function defined as I(z) Jox x=- c x dr. The variance is given by
Var []
1 c
Jo 2 + dx C %/100
2
/0 +
The same substitution as above gives
Var( P) 2C /- //2 3/1 -
03 1
o3
(3 o² T(3/4)
11/1
2C
2C 4 T(5/4)
4

---

Published as a conference paper at ICLR 2023
Thus, setting = TT(54)) T(3/4)
results in Var = 1. Correspondingly, we have C' TT(5/1)8/2
vT(3/4)
For this choice of P. the Bhattacharya coefficient p(P, Q) is given by:
p(P, Q) Q)= Vp(z)[(z)d== VCV2T
1
exp
x²
dx = 0.9905 Σ 0.991 < 1.
20
Thus, in the proof of Lemma 5, we can use this choice of P, and we have that for 5 = 0.991 and
P. = Pd, TV(P., Q) 2 1 8%, as required.
3.3 BOUNDING THE FISHER INFORMATION MATRIX
In this subsection, bound the second factor in eq. (7), which is an upper bound on the Frobenius norm of the Fisher information matrix at 0,. Lemma 7. For some constant M > O, we have
( s d
(9)
Proof. Recall that T(x) = (.f...., 24 1). Then,
||< Σ of + Σ +1
oi
(10)
iØj
Therefore, by linearity of expectation, and using the fact that P. product distribution,
[[<"))())]]]]{><>>>>>>> = d Ep[= + d(d - 1) (EI[=01)² + E + +1 dl M, x
for appropriate choice of constant M. This constant exists since all the expectations above are bounded owing to fact that the exponential density ý dominates the integrals.
3.4 PUTTING THINGS TOGETHIER
For P. defined as above, and Q NN Ia), Lemma 5 ensures that 1 TV(P., Q) I 8d, for
5 = 0.991. From Lemma 7, we have that
/ (T (x)de s d2 M.
Substituting these bounds in eq. (7), get that
VOL(P.) 1 J exp(- -xxp(()))
By construction, p. a product distribution with Ep. [x] and Ry, [xxx T] = La, which completes the proof of the theorem.
4 PROOF OF THEOREM 4
We will bound the error of the optimizer ô,, of the empirical NCE loss (eq. (2)) using the bias varianer decomposition of MSE. To do this, will reason about the random variable vn(0,, 0.); let Σ be its covariance matrix. Since 0, is unbiased estimate of 0., the MSE decomposes
E 0
0.
Tr(E).
(11)
2
The proof of Theorem 4 proceeds as follows. In Section 4.1, we show that the random variable vn(A, 0.) asymptotically normal with mean and covariance matrix Σ given by
Σ = (VL100))""(((VVVo00000)11111
(12)
5

---

Published as a conference paper at ICLR 2023
We prove that the Hessian (8.) is invertible in Appendix C, so that the above expression is well-defined. Since Σ = 0 (it is a covariance matrix), to get a lower bound on Tr(E), it suffices to get lower bound on the largest cigenvalue of Σ. Looking at the factors the right hand side of eq. (12), we note first that Theorem 3 ensures an exponential lower bound on all eigenvalues of V ) The bulk of the proof towards lower bounding the largest eigenvalue of E consists of lower bounding VnV e (0+))) the directional variance of Vn VnVeL"(O,, (0+) along suitably chosen direction
Var (o"
in terms of (O0())) )v. In Section 4.2 and Section 4.3, we use anti-concentration bounds to prove such variance lower bounds.
4.1 GAUSSTAN LIMIT OF vn(On, -0)
To begin, we will show that vn((0, 0-) behaves Gaussian random variable as n - co. Recall that the empirical NCE loss is given by eq. (2):
(O( (o( + ((;;)
(():)
L (0) =
Σ
2
pa (3A) + ((v))
==1
where F; ~ P. and yi ~ Q are i.i.d. Let On be the optimizer for L Then, by the Taylor expansion of VoL" around fz, we have
Va (n - 0.) -V2L"00))- - - vn. (
(10.-0.
0.
(13)
by Gutmann & Hyvärinen (2012), who also show in their Theorem 2 that 0n is consistent estimator
of 0.: hence, as + xo. 0, (00-0,1 0. + O. Gutmann & Hyvärinen (2012, Lemma 12) also assert! that the Hessian of the empirical NCE loss (eq. (2)) at 6, converges in probability to the Hessian
Es VaI(O.)-1. On the other hand, by the Central Limit Theorem, V I (0.) converges to a Gaussian with mean E(vnV a (#.)) Ln O, and covariance Var v (0.)). With these considerations, we conclude that the random variable (T( - 0. in eq. (13) is asymptotically Gaussian with mean O and covariance (O.. - Var V, (B.)) ((..)) ((..)).-....0 as defined eq. (12).
of the true NCE loss (definition 1) at 6., i.e., V2I."
(0_))
Next, we introduce some quantities which will be useful in the subsequent calculations. As we already have a handle on the spectrum of (2. from Theorem 3, the main object of our focus in eq. (12) is the term VarlvnVV LO..)) In particular, since we concerned with the directional variance of Σ, we will reason about Var [ VnVoL"
for a fixed vector of ones, i.e., = 1d+1 This vector has the property that for all x, TT(x) > 1, as all non-constant coordinates of T are non-negative, and the remaining coordinate is 1. Note that
1 a
(Tx)) P. (x,) ((x,)
1 n
P.( 1=1 (M.) ) (())
VOL"(0.) = 2n
2n
where x; ~ P. and yi ~ Q. Writing out the variance term explicitly, we have
[g(x) v T(x)
1 Var 4n
(v) v IT())) Po(y) + g(v)
Var Var|uT (oVoLL = n
Var
+ n
4n
(.( + q(x)
(using linearity and independence)
g(x)) . T. T(x:)
1
(a) . TT())
Varzwp.
Var y
(14)
Po (x(x) + ((x))
4
(v(y) + (V))
A(x)
B(v)
Define A(x) = <(x)-v TT(z)
Rz) v T(x) where (1 = g(z)
p=(x) and B(y) = z- TT())
(()+
I+ (w)
(v)+g(()
1+ v T(y) where R2(y) = p=(2)
Ra(v)
v(5) To show that Var [A(x)] and Var [B()] are large, we
will need anti-concentration bounds on R (x)) and R2(v).
Translating notation: Ta n, Jr, (0) 27. (T) and setting gives 2V2 in eq. (6).

---

Published as a conference paper at ICLR 2023
4.2 ANTI-CONCENTRATION OF R1 (v))
Next, we show that Rí and R2 satisfy (quantitative) anti-concentration. We show this by a relatively straightforward application of the Berry-Esseen Theorem, and the proof is given in Appendix B. Precisely, we show:
Lemma 8. Let be sufficiently large. Let p fo and q - d be any product distributions, and
define R(x)= p(a)' Suppose we have the following third moment bound: Bx-p (1053) /
g(z)
c0.
Then, for any there exist constants a = =a(p. c), Pe (, < 0 such that
1 P Popp M(x) eep( ind - ova) 2 2 and P. Pamp R(xx) exp( (nd + avva 2225
Instantiating Lemma 8 for the pair (p-,g) 1) gives us the anti-concentration result for R1. while instantiating it for the reversed pair (g. gives us the amti-concentration result for Rg. We can verify that the third moment condition holds in both instantiations, since in both the cases, log(ū/p) a polynomial. Crucially, we will also utilize the fact that the constant μ is negative (as it equals (LL(pl@)) We now ready to bound the variance of A(r) and Byy).
4.3 BOUNDING THE VARIANCE OF A(x). B(y)
Recall that A(x) = R((a)x and Byy) = Ba(y)-n Let μr, be the constants given by (+)
1+H2(y)
Lemma 8 for c. c. Further, let L, = exp (nd - avd) and L2 = exp exp(nut (nd + avd). Since the
mapping + T+a is monotonically increasing in x.
(1)
Tn
P Pamp. [R((x) S L1] = Pawp.
5
2
(15)
1+ R(()
1 + L1
2
R1(x)
L2
1
Pa~p. (Z] 2 L2] = PP Pamp.
2
c,
(16)
1+ (1(
1 1 L
2
Let Tup be such that
7
P Pamp-
|[T()||| S Tup 2 8
and Pawg
|(<م]]
S Tup
(17)
8
In Appendix D, we show that some Tup we have
Vd)2v suffices for this to hold. Then, from eq. (15),
(x)
1 2 -
Pawp.
R1
1 L1
RI(r)- o T((x)
Livd+ IIT()
1
P Prup.
2タ
(Cauchy-Schware
1+ (1(z)
11
[1(x)) . (T(())
Li Livd+ I|T(())))))))
((IZ())
3
Pa-p.
R+R)(
1 Lii
8
(union bound with eq. (17))
[i(D) T(x))
vd+ IL
3
Pa-p.
1+ (I(
1+
>
-
A(z) < Vd + 1L Tup
1
1+L1
for E < 8. On the other hand, recall also that satisfies v T(()) 2 1 for all z. Therefore, we have
(x) 2 1+ L2
L2
P Pamp,
2 2 -c
1+
R1(x) v. T(xx)
1
Lz PANp, A(x) 2 + Lz
1
P Z.pp
1+ R1(x)
1 L
2
4"
7

---

Published as a conference paper at ICLR 2023
Now, consider the event A1 {A(x) BBapp [A(x)], Ezupp [A(x)]]}_ If this event were to intersect both the events A2 {A(x) S have
Va+ILiTop and A3 (A(x) 2 I+L2 J. then would 1+h1
Lo
1
Vd 1I. Tup and E Ezup, [A(x)] 2 1+ L2
La
E s.p.
[A(x)] $
2
1+ L1
L2
L1 +111- L2+1 33
L1
TupVd+1
We will show that this cannot be the case. Recall that μ < 0, which means that L2 explud + dyd) < 1 for sufficiently large d. This means that for sufficiently large d we have:
explud + avd) <1
explud+avid 2 expludd avd) <1
+ explud + avd) 2 2 eexpppuuddaaa avd)
+ exp(pd - av d)
+ exp(ud + av
L1+1 1 2
I2+1
Further, since ta exp d) and Tup (("2//)) we get that
L2
L1 +1 exp(2avd) 1
>3
L I
L O(o2d)
where the last inequality follows for large enough since the numerator grows faster than the denominator. Hence for large enough d, Ai cannot intersect both A₂ and Ag. If the event A is disjoint from A2, then
P Pawp.
[AI U2] P x~pp [Ai] + P. Pawp. [A2] 51
P Propp
[A1] < 1
Pamp.l [A2]
P Paup.
A(x) E
Exwp. [A(x)] bz Bamp.. [A(x)] -
4
1
Pamp. AA - Ep, Al > 2 Ep. A
This finally lower-bounds the variance of as
1
1
1
Varp. [A] = [[(AAAAA4 Ey. A)
EE,, A)2 P (A Ey, A)2 1 (Epp A)2
2 (Ey A)2.
4
and thus T.p. (A2) (R.p. A)2 = Varp. [A] 2 16 (Fp A)2, so that (R.p. A)2 <
16
F.p (A2).
17
Altogether, we get Varp, [A] 2 1 (A?). An analogous argument in the case when A₁ is disjoint with As yields the same bound on the variance. Using an identical argument for R3 and B, we get that for large enough d, Var, [ 2 1 F,,(B,.)
4.4 PUTTING THINGS TOGETHER
Putting together the lower bounds Varp. [A] > 17 Ep. (A2) and Var, [B] 2 (B²) showed in
the previous subsection, and recalling eq. (14), we get
1
1
1
Var l VVnVoL" (0-)
4 Varp, [A]
Varp. [B]
(Ep [A + Eg BB1))
4
68
1
(
(x)
+ (z)
[T((T)((x) T Ju
68
(px +(x))²
1
(z)
T(x T(x)T(x) dr. 34
V(L((0))
68
(x)) + ((x)
(from eq. (6).
8

---

Published as a conference paper at ICLR 2023
Finally, since (0,( is invertible claimed earlier (Lemma 10, Appendix C), let be such that v (O,( w. Then, recalling the expression for Σ in eq. (12), we can conclude that
T Ew Var[vTVoLL" w
Var Varlu' [u
1 w V2L(0.) (18)
2 V/L((0)u - 34
34
which gives us the desired bound on the MSE, namely
E 6, 0, 1
1 Tr(=)
x =
2 sup
||=11
2
1 w
Ew
ViL(O.)
w
1 34n
inf 2 VgL(0,)-
exp(si(d))
" |
34n
|
||
7
where the last inequality follows from Theorem 3 and the fact that Amax (ViL(0.)) Amin
L (()))=)-+
This concludes the proof of Theorem 4.
5 SIMULATIONS
We also verify our results with simulations. Precisely, we study the MSE for the empirical NCE loss as a function of the ambient dimension, and recover the dependence from Theorem 4. For di- mension d 72, 72,..... 120), we generate n = 500 samples from the distribution P. we construct in the theorem. We generate an equal number of samples from the noise distribution Q = (0, La), and run gradient descent to minimize the empirical NCE loss obtain 8,, Since explicitly know what 0, is,
compute the squared error 0, 0. 2| We run 100 trials of this, where obtain fresh samples each time from P. and Q, and average the squared errors over the trials obtain an estimate of the MSE.
Figure 1: Log MSE versus Dimension Theorem sug- gests this plot should be linear, as observed.
Figure shows the plot of log MSE versus dimension we can see
that the graph is nearly linear. This corroborates the bound Theorem 4, which tells us that as + oo, the MSE scales exponentially with d. This behavior is robust even when the proportion of noise samples true data samples is changed 70:30 (though our theory only addresses the 50:50 case). Finally, we note that optimizing the empirical NCE loss becomes numerically unstable with increasing d (due very large ratios in the loss), which why we used comparatively moderate values of d.
CONCLUSION
Despite significant interest in alternatives to maximum likelihood example NCE (considered in this paper). score matching, etc. etc.-there is little understanding what there is to "sacrifice" with these losses, either algorithmically statistically. In this paper, provided formal lower bounds on the asymptotic sample complexity of NCE, when using common choice for the noise distribution Q Gaussian with matching mean and covariance. Thus, is likely that even for moderately complex distributions in practice, more involved techniques like Gao et al. (2020); Rhodes et al. (2020) will have to be used, in which one learns noise distribution Q simultaneously with the NCE minimization or "anneals" the NCE objective. There is very little theoretical understanding of such techniques, and this seems like a very fruitful direction for future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Andrej is supported in part by NSF award IIS-2211907
REFERENCES
Omar Chehab, Alexandre Gramfort, and Aapo Hyvärinen. The optimal noise in noise-contrastive learning is not what you think. In Uncertainty in Artificial Intelligence, pp. 307-316. PMLR, 2022.
Yilun Du and Igor Mordatch. Implicit generation and generalization in energy-hased models. arXiv preprint arXiv:1903. 08689, 2019.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019. 11
Ruiqi Gao, Erik Nijkamp, Diederik P Kingma, Zhen Xu, Andrew M Dai, and Ying Nian Wu. Flow contrastive estimation of energy-based models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7518-7528, 2020. 9
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 297-304. JMLR Workshop and Conference Proceedings, 2010. 1
Michael U Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications natural image statistics. Journal machine learning research, 13(2), 2012. 1, 2, 3,6 6
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5), oct 2000. doi: 10. 121114/400111155533555 URL https: /wwi. org/ 10. 1214 $2Faos $2Fooss2F100 $F11G39571111995 12
Bingbin Liu, Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. Analyzing and improving the optimization landscape of noise-contrastive estimation. arXiv preprint arXiv:2110.11271,, oct 2021. URL http: aww.iiiiiivv....io
wttpwwiwww....aaaaaa/oo//aa/aaaa wwtp://///a/aaatatoooo.oooae 121....1111.....11....11 2,
Benjamin Rhodes, Kai Xu, and Michael U Gutmann. Telescoping density-ratio estimation. Advances in Neural Information Processing Systems, 33:4905-4916, 2020. 1,
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
Paul van Beek. An application of fourier methods to the problem sharpening the Berry-Esseen inequality. Zeitschrift für Wabusscheimniickkettthhherr und verwandte Gebiete, 23(3):187-196, 1972.
11
Larry Wasserman. Lecture Notes 27. https://wwet http:////.tttttt.ttt/....../t staat. cmu. wwt..eda//larrr/sstttttt/ Lecture27 fddf, 2020. [Online; accessed 5 May 2022], 3,4
10

---

Published as a conference paper at ICLR 2023
A BOUNDING THE MATRIX INTEGRAL IN EQUATION 6
We prove a variant of the Cauchy-Schwarz inequality that gives us a handle on norms of matrix integrals.
Lemma 9. Let f Rd + R and A : Rd + I be integrable functions, with M Ja ((x)) Then we have
| |1, f())A(z)ds | ((((c)) (
(19)
Similarly, A Rdd + RRax is matrix valued function then
| [())) (f(rGo) de ((IACOBBB)))
(20)
Proof. The proof follows from the Sauchy-Schwarz inequality, Since integrate component-wisse for eq. (19) we have that
M3 (( s (fslo)de)) (f (/
Summing over i, we get the result. The matrix variant eq. (20) follows by looking at the matrix M as vector in "
B PROOF OF LEMMA
We restate the lemma for convenience:
Lemma 8. Let > be sufficiently large. Let p = fr and q= be any product distributions, and
a(x)) define R(x) p(a)' Suppose we have the following third moment bound: Exzi (10g) ( <0.
3
Then, for any 6, there exist constants a(p, c). / u
q, c) 0 such that
P PaNp R(x) S exp(ud - ava) Σ c and P Pawp R(x) 2 exp (ud + ava) 2
Proof. We will analyze the behaviour of R(x) using the Besre-Esscen theorem. Given that p. pd
and = q²t are product distributions, let r(x) be the random variable defined by r(x) M x P. Let (x) logr(z) rxx) for < i I d be d independent copies of the random variable r(z). Let
((x)
E[ya] = Mr. E [ly. - m= = o² and || /r (4-11]]] = Yr. all of which are well defined by the
hypothesis of the lemma. Let Y Ed Ei=1 Mi, and be the standard Gaussian in R. Then, by the Berry-Esseen Theorem (Durrett, 2019, Theorem 3.4.17),
Y n s-c 2 p|Z -c] P
OBE 7r vdvd
v,vd
where CBE < 1 (van Beek, 1972) is an absolute constant. We can now choose = e(c) such that Piz < c) _ Further, we can choose d large enough so that Cue. oavd
ş. Then for μ H, and
Co,, we have
P Pawp R(x) S exp(ni (ap(pddvvil ava) 2
Since Z is symmetric around 0, Berry-EEseent Esseen gives us the other inequality for the same choice of and a,
Y p Vd
Plz c) CEE 7t vdvd
1 2
2
Note that the constants and a are independent of d. Further, note that μ = 14. = -KL(p1I)) <
11

---

Published as a conference paper at ICLR 2023
C INVERTIBILITY OF THE HESSIAN
We prove that the Hessian of NCE loss for the exponential family given by T(x) = (a1,....,47) 1) is invertible. In particular, have the following lemma:
Lemma 10. Let Q = (O, Ia) be the standard Gaussian R Let P be the log concave distribution defined in definition 6. Let P = pa. Let and denote the density finctiinn of Q and P respectively. Observe that is in the exponential family given by T(x) (si...., ... 1), and equals Pe. for some 0,, Then the hessian of the NCE loss with respect to distribution P and noise Q given by
= VZ =
p-q
Ta))
P. +
is invertible.
Proof. For any subset A C Rd, define
HA HA JEE P. +
1
p-q T(x)T(x)
Observe that the density functions p- and g of P. and respectively are strictly positive over all of Rd Therefore, for any subset A S Rd and any E IR++1 we have
H 2
/
p-q
TT)) 0= C HA HAV.
P. +q
Given a vector v E Rd+1 we will pick A such that [(x) ol > for all E A. Note that the set B {el + ea+t...., Ed Ed+1, ea+1) is basis. Therefore, if bT 0 for all b E B, then e= = O. Hence, there exists some x E (ei,..., eat such that [Txx] Jul > 0. Since x + T(x) v is continuous function, we can find an open set A around such that
[T() 0/
E
follows that
0 HAU
1
/
P.q - (()) 2 2 P. +
p.q
T(x) T 0 > 0.
2 P. +
Let B Rd A. Since v T HAV > 0 and T for any arbitrary non-zero vector v, the matrix H must be full rank. Since H is integral of PSD matrices, it is a full rank PSD matrix and hence invertible.
HB 2 0. we have that T He >> 0. Since this holds
D TAIL BOUNDS FOR EQUATION 17
We prove that some Tup ((o2 suffices to obtain the bounds in eq. (17). Concretely, prove tail bounds for [T(']] using tail bounds for P. and Q. We will use Lemma from Laurent & Massart (2000) which proves bound for x2 distributions:
Lemma (Lemma 1, Laurent & Massart (2000)). If X is x² random variable with d degrees of freedom, then for any positive
d2 2v 2t s exp(-t).
Then, for Q, ||0|| 2 is x² random variable with d degrees of freedom. Observe that for t, d 2 4. have d + 2t + tt < 2td. In particular, have the weaker bound
Panq ||==|] 2dtt s exp(-t9)
implying that
82
P PanQ
| 2 S exp
2d
12

---

Published as a conference paper at ICLR 2023
Further, if ||>|||| 2 o2vd, 2 (x), implying that for t 2 od
Pa~P. ||||| 2 of S exp
t2
2d
In partieular, for any such that (0/(1 2 o², we have
|||||| P
2 (2d1og(1/0)
5 and
PoWP ||0||| 2
\2d
(21)
13


Reviews:
[{"review_id": "c2rPC2cTbu", "reviewer": "Reviewer_cCKs", "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": "", "summary_of_the_paper": "This paper\nconsiders estimating the parameters of an exponential family using the NCE\nloss.  The NCE loss is a particularly popular method because it avoids\ncomputing the partition function of the exponential family which is required by\nother methods such as maximum likelihood.  A popular choice for the noise\ndistribution is to use a Gaussian that matches the mean and covariance of the\nobservations.  This work shows that there exist simple exponential families for\nwhich such a choice makes the NCE exponentially flat around the optimal\nparameter.  This fact also results in exponentially large sample complexity for\nthe NCE loss.  More precicely, the first result shows that for this exponential\nfamily the $\\ell_2$-norm of the Hessian of the NCE loss with Gaussian noise\ndistribution is at most $e^{-\\Omega(d)}$, where $d$ is the dimension of the\nobservations.  They then use this result to show that the empirical optimizer\nof the NCE loss needs exponentially many samples ($e^{\\Omega(d)}$) in order to\nconverge to the true parameter (be in constant $\\ell_2$ distance from the true\nparameter). \n", "summary_of_the_review": "This paper considers an interesting problem and provides a simple\n\"counter-example\" for a common choice for the noise distribution in the NCE\nloss.  Overall, I found the paper to be somewhat \"light\" in technical content\nbut I liked the fact that it provides a clean counter-example to popular method\nand fills a gap in the literature on the NCE loss. Therefore, I am inclined\ntowards acception.\n", "strength_and_weaknesses": "Strengths\n\n1. The NCE objective is a popular method and investigating its behavior under\ndifferent noise distribution is an important and well-motivated problem.  The\nresults of this work provide a concrete \"counter-example\" to a commonly used\nnoise distribution.\n\n2. The paper is well-written and the proof details are easy to follow.\n\nWeaknesses\n\n1. Since the contribution of this work is theoretical, I think a minor weak\npoint of this work is that the proofs and technical results are not\nparticularly challenging.\n\n\nQuestions\n\nI think for the parametric family constructed to make the NCE loss\nexponentially flat, the maximum likelihood objective is strongly convex (for\nsome dimension-independent constant).  If this is true the authors could\nperhaps add this small observation so that it is more clear that for the family\nconstructed the maximum objective would be efficiently optimizable.\n\nMinor Typos\n\npage 4, \"the gamma function defined as $\\Gamma(z) \\int_0^\\infty x^{z-1} e^{-x} d x$.\n\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "YPvhxnrvUXX", "reviewer": "Reviewer_mHes", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper analyzes Noise Contrastive Estimation (NCE): a popular algorithm for approximating distributions given iid samples from it, and whose effectiveness crucially depends on the user's choice of a \"noise distribution\" to compare the given samples to. Often, this noise distribution is chosen to just be an isotropic Gaussian.\n\nThis paper shows that even if the given samples are drawn iid from a extremely well behaved distribution, then NCE with the isotropic Gaussian as its noise distribution has a mean squared error that grows exponentially in the dimension of the data. In other words, for NCE to low mean squared error, the number of samples required must be exponential in the dimension of the data.\n\nThis \"well behaved\" distribution is a $d$-dimensional vector with $iid$ log-concave entries from an exponential distribution. It's basically a mild generalization of the isotropic gaussian, where the pdf depends on $e^{t^4}$ instead of $e^{t^2}$.\n\nThe paper emphasizes an intermediate result, showing that the NCE loss metric is exponentially flat near it's optimum. Critically, this result is for the population loss (which the algorithm doesn't optimize over), as opposed to the sample loss (which the population does optimize over). This distinction isn't made clear in the introduction or abstract.", "summary_of_the_review": "I like this paper, and unless other reviewers have concerns around it's novelty and/or significance, I'd like to see it published.\n\nShort an sweet. Interpretable results. I'm happy.\n\n", "strength_and_weaknesses": "_Note that I'm not an expert on NCE. I understand the math in the paper, and I'm good with statistical and machine learning lower bounds, but I can't really speak to how this paper fits into the broader NCE literature._\n\nThe paper is short and compelling. The math is short. The language is clear. The claim is somewhat interesting, though I suspect the authors may be underselling the underlying intuition that implies this exponential dependence. I'll elaborate on these points below.\n\nFirst, the paper is short and the math is clean. I read almost the entire thing, and verified virtually every line of the math. I've got a couple minor questions, but more than almost any other theory paper, I can really claim this paper is mathematically correct.\n\nSecond, the paper is well written. The language is short. It doesn't waste your time. It quickly gets to the core ideas, has a nice logical flow, and the authors give nice intuitions preceding each step of the proof, so you never loose the big picture between the equations.\n\nThe claims and proofs feels significant and novel, though this is hard for me to judge as an outsider to the NCE literature.\n\n\nThat said, the first major claim of the paper (what I referred to as the \"intermediate result\" in my summary), is somewhat hard to interpret. First, keep in mind two facts:\n1. NCE means minimizing a specific loss function (the _empirical NCE loss_; equation (2) on page 2 of the paper)\n2. NCE is not tied to a specific optimization algorithm.\n\nThis first major claim says that the _population_ NCE loss function, which is impossible to compute since it requires knowing the distribution we're trying to approximate, is very flat near it's optimum. Near the bottom of page 2 of the paper, the authors claim this suffices to show that typical first-order methods would take exponentially long time to converge unless they make a mitigating factor like normalizing their gradients. Putting aside the fact that it is it pretty easy to normalize a gradient, the authors don't even prove that the empirical loss is flat near the optimum. So, it's not clear that this claim carries much weight on its own as an independent contribution.\n\nThat said, this is an important intermediate result for the final claim of the paper, which uses an anti-concentration argument to say that the mean squared error of NCE is bounded by the flatness of the _population_ NCE loss function. So it's important for the final result about NCE sample complexity, but I think those claims should be either better explained or toned down or just removed.\n\nThe final exponential sample complexity ends up relying on the exponential flatness (exponentially small spectral norm of the Hessian) of the population loss function. So, if we want to learn a broader lesson about when picking a bad noise distribution can make NCE require a huge sample complexity, we should look inside the proof of the exponentially small spectral norm, specifically at equation (8) on page 3:\n$$\\|\\| \\nabla_\\theta^2 L(p_\\theta) \\|\\| \\leq \\frac12 (1-TV(P,Q))^{1/2} \\ \\cdot \\  (\\textstyle{\\int} \\|\\|T(x)T(x)\\|\\|_F^2 p(x) dx)^{1/2}$$\nThis right hand side has two terms:\n1. A total variation that measure how far the true distribution is from the noise distribution. This term is exponentially close to zero.\n2. Something akin to a norm on the Fisher Information Matrix, which is a known measure for the flatness of optima. This term is polynomially large.\n\nThis upper bound on the norm of the Hessian crucially assumes the true distribution is an exponential distribution, but that's all. The total variation is going to be exponentially small in the dimension any time both the noise and true distributions have $iid$ entries and when the noise distribution isn't exactly equal to the true distribution. The second term should be polynomially large in all reasonable circumstances. So, from my intuition at least, we expect to have this exponential flatness for a much much wider choice of noise distributions and true distributions. At least, we should carry this intuition around and have to argue why some other setting won't fall into this pitfall.\n\nBasically, I suspect there's another interesting result that can be found by generalizing this paper's current results to a much larger family of distributions, showing that the exponential dependence on dimension is much more general than just the Gaussian noise distribution. I don't know how interesting that would be to the broader NCE community though.", "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": {}}, {"review_id": "UXTr7PRkntu", "reviewer": "Reviewer_9KJi", "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": "", "summary_of_the_paper": "The paper analyzes the Noise Contrastive Estimation (NCE) algorithm under the choice of a gaussian sampling distribution with mean and covariance estimated from the data.\nThe paper shows that such a choice can lead to both poor statistical and computation efficiency by constructing an exponential distribution that leads to ill-conditioned Hessian with a spectral norm exponentially decaying in the ambient dimension. Such a choice also leads to exponentially bad statistical efficiency.", "summary_of_the_review": "The paper is well-written and provides novel theoretical contributions to the analysis of the widely used algorithm NCE. The paper's novelty is however limited and the additional contributions of the paper compared to Liu et al. [1] should be discussed. The paper can also be improved through a discussion of suitable alternatives to gaussian noise and algorithms that are not significantly affected by the poor conditioning of the Hessian.\n\n[1]: Liu, B., Rosenfeld, E., Ravikumar, P. and Risteski, A., 2021. Analyzing and improving the optimization landscape of noise-contrastive estimation. arXiv preprint arXiv:2110.11271.\n\n____________\n\nPost rebuttal: I thank the reviewers for clarifying my doubts and incorporating the suggestions into the paper. I've raised my rating to 8.", "strength_and_weaknesses": "### Strengths:\n\n- The paper highlights the limitations of a common practical choice of gaussian distribution while using NCE.\n- The paper is well-written.\n- The proof technique of utilizing the tensorization of the Hellinger distance is interesting and non-trivial. \n- The proofs are easy to follow.\n- The results are supported by simulations.\n\n### Weaknesses:\n\n- The paper doesn't contain adequate discussion of related work. Including a related work section with a more detailed comparison against works such as Liu et al. [1] would improve the presentation of the paper. \n- The poor algorithmic efficiency of optimization algorithms for NCE due to an exponentially flat Hessian of the loss was discussed in Liu et al. [1]. Therefore, the novelty of the paper appears to be limited.\n- The relevance of the novel results for the use of eNCE and normalized gradient method in Liu et al. [1] is not discussed.\n- A discussion of the relationship with related generative models such as Generative Adversarial Networks is absent.\n- The effect of utilizing sample mean and covariance instead of the population mean, and covariance is not discussed.\n- Possible approaches for mitigating the pitfalls of gaussian noise are not presented.\n\n[1]: Liu, B., Rosenfeld, E., Ravikumar, P. and Risteski, A., 2021. Analyzing and improving the optimization landscape of noise-contrastive estimation. arXiv preprint arXiv:2110.11271.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6cqqsSjKzg", "reviewer": "Reviewer_mqhY", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies the noise contrastive estimation (NCE). NCE aims to learn probability density functions by first choosing a simple \"noise\" distribution and then training the parameters by minimizing the NCE loss, where the NCE loss measures the difference between the target distribution and the \"noise\" distribution. The authors show that when the target distribution is in a product form and the chosen \"noise\" distribution is Gaussian, the Hessian of the loss function decreases exponentially fast when the input dimension increases. In this situation, the authors also show that when the number of training samples goes to infinity, the mean-squared error is on the order of $\\exp(d)/n$.", "summary_of_the_review": "The setup and the results of this paper are stated clearly. However, I am skeptical about the message that this paper is trying to convey.", "strength_and_weaknesses": "Strength: The results and the proof seem solid.\nWeakness: The explanation of the results is not enough. The main message of this paper is questionable. See my comments below.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4I5rYkml6Bt", "reviewer": "Reviewer_ZzEv", "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": "", "summary_of_the_paper": "This paper shows that using the Gaussian distribution with mean and covariance of the data as the noise distribution in Noise Contrastive Estimation might be bad in terms of both statistical and computational efficiency.", "summary_of_the_review": "Overall I like the paper and think it should be accepted", "strength_and_weaknesses": "**Strengths**\n- The paper is globally clear and well written\n- It tackles an interesting problem and gives an elegant solution\n\n**Weaknesses**\n- After proving the negative result about the Gaussian distribution, I would have liked the authors to elaborate a bit more on which distribution should be used instead. In particular, the authors mentioned two works in the conclusion, that learn $Q$ simultaneously as solving the NCE, but would any fixed distribution suffer from the same problem as the Gaussian?\n- Some aspects of the writing might be improved, see below", "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": "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": {}}]

Author rebuttal:

Decision: Accept: poster