Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper examines Noise-Contrastive Estimation (NCE) from an optimization perspective. 

The 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). 

To 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:

1. Modifying the optimization algorithm: normalize the gradient at every step
2. Modifying the loss: still density-ratio based, but replace the sigmoid-log with a square root

These two contributions are supported theoretically, using the exponential distribution as a study case. Respectively,
1. 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)
2. Expresses the Hessian conditioning number as polynomial in the parameter distance and dimension, to complete the convergence rate characterization

The effect of either modification is empirically verified on the MNIST dataset. 
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). 

It 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. 

Out of curiosity:

1. Is it possible to empirically compare NGD with other normalized-gradient methods?
Because 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?

2. What is the impact of the proportion of noise samples hyperparameter on this paper's analysis?
The 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?

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Strength
-	Theoretically understanding of NCE method is an important direction and I believe this paper gives some interesting results in this direction. 
-	This 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.
-	The paper is overall clearly written and easy to follow.

Weakness:
-	The 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.

Some minor comments:
-	At 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)
-	Proposition 4.2: missing an O(1) factor in front of R exp(R^2/8)\delta^2 ?

summary_of_the_review: Based on the above comment, I believe this paper gives interesting theoretical results on NCE and would vote for accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

Longer version: 

The 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.

There 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. 

In this paper they study the setting in which all distributions are in the exponential family of distributions. 

- 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) 
- They next show that, provided the distributions are 'sufficiently close', using *normalised* gradient descent results in requiring only polynomially many steps.
- Next, they show that modifying the NCE loss (exponential-NCE) results in such polynomial guarantees even without the distributions being 'sufficiently close'
- Finally they validate their theory with basic experiments.


main_review: **Caveats:**
- 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.
- I did not read the proofs in detail, so cannot vouch for the correctness of the mathematical results.


**Summary:**

I 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. 

I 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. 

The 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. 

Therefore, 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. 

Please see the detailed comments below for all questions / wishes for the authors. Here I would like to highlight the main points of concern:

- 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. 
- 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. 
- Experiments: please provide code to make things easier for future researchers to build on your work. 


I 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. 




**Detailed comments:**


Page 3: 
- Exponential family: could you define the partition function and add a short comment on why this (or the log-partition-fn) is so important? 
- 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? 


Page 7: 
- 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!) 

  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].

  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?

  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) 


- 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 ? 


Page 9:
Experiments: 
- Figure 1: what is meant by "best parameter distance"? I didn't quite understand the explanation in the Results paragraph. 
- 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.)

Figure 2: 
- Qn1: Are you doing full gradient descent on MNIST? (i.e. without minibatching?) 
- 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?]

- Could you comment on the full gradient descent assumed in the paper/experiments, vs the mini-batch based methods commonly used by practitioners?
- I'd also be interested to see how the experiments behave if you repeat them just naively using mini-batches of different sizes.  
- 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. 


Minor: 
- 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.





summary_of_the_review: 
I 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.

As 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.

[Edit: updated my score to "8: accept, good paper" after author response]
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Pros:
The author constructs a bad case, and improves the NCE by fixing problems in the bad case. The improvement is theoretically guaranteed.

Questions:
1. 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.

2. 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_*)$.

3. 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.

4. 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.

5. The uniqueness in Lemma 2.1 needs $p_*(x) \neq 0 \rightarrow q(x) \neq 0$ to hold.

[1*] https://github.com/bioinf-jku/TTUR
summary_of_the_review: This paper is generally solid, although there is some confusion.
review_title: null

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)