Venue: ICLR 2018 conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: In this paper, the authors present an analysis of SGD within an SDE framework. The ideas and the presented results are interesting and are clearly of interest to the deep learning community. The paper is well-written overall.

However, the paper has important problems. 

1) The analysis is widely based on the recent paper by Mandt et al. While being an interesting work on its own, the assumptions made in that paper are very strict and not very realistic. For instance, the assumption that the stochastic gradient noise being Gaussian is very restrictive and trying to justify it just by the usual CLT is not convincing especially when the parameter space is extremely large, the setting that is considered in the paper.

2) There is a mistake in the proof Theorem 1. Even with the assumption that the gradient of sigma is bounded, eq 20 cannot be justified and the equality can only be "approximately equal to". The result will only hold if sigma does not depend on theta. However, letting sigma depend on theta is the only difference from Mandt et al. On the other hand, with constant sigma the result is very trivial and can be found in any text book on SDEs (showing the Gibbs distribution). Therefore, presenting it as a new result is misleading.  

3) Even if the sigma is taken constant and theorem 1 is corrected, I don't think theorem 2 is conclusive. Theorem 2 basically assumes that the distribution is locally a proper Gaussian (it is stated as locally convex, however it is taken as quadratic) and the result just boils down to computing some probability under a Gaussian distribution, which is still quite trivial. Apart from this assumption not being very realistic, the result does not justify the claims on "the probability of ending in a certain minimum" -- which is on the other hand a vague statement. First of all "ending in" a certain area depends on many different factors, such as the structure of the distribution, the initial point, the distance between the modes etc. Also it is not very surprising that the inverse image of a wider Gaussian density is larger than of a pointy one. This again does not justify the claims. For instance consider a GMM with two components, where the means of the individual components are close to each other, but one component having a very large variance and a smaller weight, and the other one having a lower variance and higher weight. With authors' claim, the algorithm should spend more time on the wider one, however it is evident that this will not be the case. 

4) There is a conceptual mistake that the authors assume that SGD will attain the exact stationary distribution even when the SDE is simulated by the fixed step-size Euler integrator. As soon as one uses eta>0 the algorithm will never attain the stationary distribution of the continuous-time process, but will attain a stationary distribution that is close to the ideal one (of course with several smoothness, growth assumptions). The error between the ideal distribution and the empirical distribution will be usually O(eta) depending on the assumption and therefore changing eta will result in a different distribution than the ideal one. With this in mind the stationary distributions for (eta/S) and (2eta/2S) will be clearly different. 


The experiments are very interesting and I do not underestimate their value. However, the current analysis unfortunately does not properly explain the rather strong claims of the authors, which is supposed to be the main contribution of this paper. 

review_title: Interesting paper, however not convincing theoretical results

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors study SGD as a stochastic differential equation and use the Fokker planck equation from statistical physics to derive the stationary distribution under standard assumptions. Under a (somewhat strong) local convexity assumption, they derive the probability of arriving at a local minimum, in terms of the batchsize, learning rate and determinant of the hessian.

The theory in section 3 is described clearly, although it is largely known. The use of the Fokker Planck equation for stationary distributions of stochastic SDEs has seen wide use in the machine learning literature over the last few years, and this paper does not add any novel insights to that. For example, the proof of Theorem 1 in Appendix C is boilerplate. Also, though it may be relatively new to the deep learning/ML community, I don't see the need to derive the F-P equation in Appendix A.

Theorem 2 uses a fairly strong locally convex assumption, and uses a straightforward taylor expansion at a local minimum. It should be noted that the proof in Appendix D assumes that the covariance of the noise is constant in some interval around the minimum; I think this is again a strong assumption and should be included in the statement of Theorem 2.

There are some detailed experiments showing the effect of the learning rate and batchsize on the noise and therefore performance of SGD, but the only real insight that the authors provide is that the ratio of learning rate to batchsize controls the noise, as opposed to the that of l.r. to sqrt(batchsize). I wish this were analyzed in more detail.

Overall I think the paper is borderline; the lack of real novelty makes it marginally below threshold in my view.
review_title: Theory not particularly novel, experiments okay.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper investigates how the learning rate and mini-batch size in SGD impacts the optima that the SGD algorithm finds.
Empirically, the authors argue that it was observed that larger learning rates converge to minima which are more wide,
and that smaller learning rates more often lead to convergence to minima which are narrower, i.e. where the Hessian has large Eigenvalues. In this paper, the authors derive an analytical theory that aims at explaining this phenomenon.

Point of departure is an analytical theory proposed by Mandt et al., where SGD is analyzed in a continuous-time stochastic
formalism. In more detail, a stochastic differential equation is derived which mimicks the behavior of SGD. The advantage of
this theory is that under specific assumptions, analytic stationary distributions can be derived. While Mandt et al. focused
on the vicinity of a local optima, the authors of the present paper assumed white diagonal gradient noise, which allows to
derive an analytic, *global* stationary distribution (this is similar as in Langevin dynamics).

Then, the authors focus again on individual local optima and "integrate out" the stationary distribution around a local optimum, using again a Gaussian assumption. As a result, the authors obtain un-normalized probabilities of getting trapped in a given local optimum. This un-normalized probability depends on the strength of the value of the loss function in the vicinity of the optimum, the gradient noise, and the width of the optima. In the end, these un-normalized probabilities are taken as
probabilities that the SGD algorithm will be trapped around the given optimum in finite time.


Overall assessment:
I find the analytical results of the paper very original and interesting. The experimental part has some weaknesses. The paper could be drastically improved when focusing on the experimental part.

Detailed comments:

Regarding the analytical part, I think this is all very nice and original. However, I have some comments/requests:

1. Since the authors focus around Gaussian regions around the local minima, perhaps the diagonal white noise assumption could be weakened. This is again the multivariate Ornstein-Uhlenbeck setup examined in Mandt et al., and probably possesses an analytical solution for the un-normalized probabilities (even if the noise is multivariate Gaussian). Would the authors to consider generalizing the proof for the camera-ready version perhaps?

2. It would be nice to sketch the proof of theorem 2 in the main paper, rather than to just refer to the appendix. In my opinion, the theorem results from a beautiful and instructive calculation that should provide the reader with some intuition.

3. Would the authors comment on the underlying theoretical assumptions a bit more? In particular, the stationary distribution predicted by the Ornstein-Uhlenbeck formalism is never reached in practice. When using SGD in practice, one is in the initial mode-seeking phase. So, why is it a reasonable assumption to still use results obtained from the stationary (equilibrated) distribution which is never reached?


Regarding the experiments: here I see a few problems. First, the writing style drops in quality. Second, figures 2 and 3 are cryptic. Why do the authors focus on two manually selected optima? In which sense is this statistically significant? How often were the experiments repeated? The figures are furthermore hard to read. I would recommend overhauling the entire experiments section.

Details:

- Typo in Figure 2: ”with different with different”.
- “the endpoint of SGD with a learning rate schedule η → η/a, for some a > 0, and a constant batch size S, should be the same
  as the endpoint of SGD with a constant learning rate and a batch size schedule S → aS.” This is clearly wrong as there are many local minima, and running teh algorithm twice results in different local optima.  Maybe add something that this only true on average, like “the characteristics of these minima ... should be the same”.
review_title: A stability analysis of local optima in constant-rate SGD

Meta-review: Dear authors,

The reviewers agreed that the theoretical part lacked novelty and that the paper should focus on its experimental part which at the moment is not strong enough to warrant publication.

Regarding the theoretical part, here are the main concerns:
- Even though it is used in previous works, the continuous time approximation of stochastic gradient overlooks its practical behaviour, especially since a good rule of thumb is to use as large as stepsize as possible (without reaching divergence), as for instance mentioned in The Marginal Value of Adaptive Gradient Methods in Machine Learning by Wilson et al.
- The isotropic approximation is very strong and I don't know settings where this would hold. Since it seems central to your statements, I wonder what can be deduced from the obtained results.
- I do not think the Gaussian assumption is unreasonable and I am fine with it. Though there are clearly cases where this will not be true, it will probably be OK most of the time.

I encourage the authors to focus on the experimental part in a resubmission.
Decision: Reject