Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper provides a theoretical analysis of the average version of SGD iterates, and shows that the averaged version of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution, under a generalized condition of dissipativity. 
main_review: This paper generalizes the DDB19 to a more generalized condition than the PL condition. Though the authors claim the non-convex regime, the main contribution falls in the use of PL condition and the analysis is analogous to DDB19. 
limitations_and_societal_impact: From my perspective, the main limitation is the novelty. The analysis is analogous to the DDB19, but just extends the analysis to some generalization of the PL condition. The experiments also did not justify the nonconvex settings, nor surprising.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper provides CLT and bias control for constant step-size stochastic gradient descent in the non-convex case. The general theory is applied to several specific examples.
main_review: The paper presents an interesting results on SGD algorithm with constant stepsizes. Under reasonable assumptions, the authors study the limiting behaviour of SGD output. It is well known, that constant stepsize SGD produces a biased stationary measure. The author quantifies this phenomenon. First, they show CLT for biased sequence and next provide bounds on the bias. The main result is applied to several examples. In my opinion, the paper provides an important and interesting contribution to the theory of SGD with constant stepsize.
limitations_and_societal_impact: not applicable
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In the paper, the authors establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD) algorithm under the dissipative settings of non-convex and non-smooth objective functions. 
main_review: 
In my opinion, the asymptotic results of the constant step size SGD presented in the paper under non-smooth and non-convex objective settings are of interest. Here are my comments on the paper:

(1) The dissipativity assumptions in Assumptions 2.2 or 3.2 are satisfied by also symmetric two components Gaussian mixtures, non-linear regression models, and informative non-response model (See references [1] and [2] that I mentioned below for more details).

(2) In Proposition 1, since $L$ and $L_{\xi}$ are not known in practice, what is the practical way to choose $\eta$ to satisfy the constraint in that proposition? Furthermore, do we have some explicit forms for the stationary distribution or simply just some approximation?

(3) In Theorem 3.1, I also have the same comment on the learning rate as the previous comment. We usually do not know $\alpha, \beta$, and the growth of function $g$ in localized dissipativity assumption. Furthermore, it seems that the upper bound of the expectation of $\|theta^{(\eta)} - \theta^{*}\|$ is not tight when $g(x) = x^{p}$ for $p > 2$. Can the authors clarify more this result?

(4) The results of Theorem 3.2 are not readable. I do not understand the meanings of constants $M$ and $m$ in that theorem. Furthermore, what is the implication of the results of Theorem 3.2 apart from the complicated constants?

(5) I think that in the localized dissipativity setting where $g(x) = x^{p}$ with $p > 2$, the CLT of constant step size SGD is not a normal distribution. In fact, it seems to be a Gaussian process. Can the authors provide more insight into this setting?

(6) There are a few relevant papers around the context of the paper that the authors may consider adding to the work:

(6.1) For the literature for the computational complexity and statistical accuracy of estimators in general non-convex settings (need not be locally strongly convex), the current work of [1] established the trade-off between the instability of general optimization algorithms and their statistical accuracy and computational efficiency.

(6.2) The dissipativity and local dissipativity also recently have been used to study the posterior convergence rates of parameters under Bayesian models [2].

--- References:

[1] N. Ho, R. Dwivedi,  K. Khamaru, M. J. Wainwright, M. I. Jordan, B. Yu. Instability, computational efficiency, and statistical accuracy. Arxiv preprint Arxiv 2005.11411, 2020.

[2] W. Mou, N. Ho, M. J. Wainwright, P. Bartlett, M. I. Jordan. A diffusion process perspective on the posterior contraction rates for parameters. Arxiv preprint Arxiv 1909.00966, 2019.
limitations_and_societal_impact: I do not see any foreseeable limitations and negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the asymptotic normality and the bias for non-convex optimization problem with constant stepsize SGD algorithm. Relaxing previous strongly convex assumption, adopting techniques from Markov chains, they show that under some mild conditions, SGD with constant stepsize will quickly converge to a stationary distribution that is uniquely determined by the stepsize $\eta$. Also, they analyze the bias under various conditions, basically showing that the bias is also (positively) dependent of the stepsize $\eta$. Last, they provide thorough experiments in Regularized MLE and Regularized Blake-Zisserman MLE settings, showing that the numerical results match their theoretical prediction.
main_review: Overall, this is a good and well-written paper. It studies a very important problem: how to quantify the uncertainty of SGD in the realistic non-convex and non-smooth setting. Also, its proof techniques may have independent interest. Different from previous work, this paper uses $V$-uniform ergodicity to show the existence and uniqueness of the stationary distribution (Proposition 2.1). Some detailed suggestions and comments are listed below and I would be happy if you can answer this questions.

1. In the application part, you list the Regularized MLE and Regularized Blake-Zisserman MLE. I am interesting that whether we can show that neural network also satisfies the conditions required to have the asymptotic normality. To me, with some regularizer or weight decay, at least shallow networks is hopeful to satisfy your conditions. 

2. As you already mentioned, there is an interplay between the convergence to the stationary distribution and the bias term. If $\eta$ is large, then the convergence is quick. On the other hand, the bias will become large if $\eta$ is large. Could you provide a quantitive analysis to provide some suggestions on how to choose a good stepsize.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper studies the asymptotic normality and the bias for constant step size stochastic gradient descent (SGD) algorithm in the non-convex and non-smooth setting. It shows that if the non-convex and non-smooth objective function satisfies a dissipativity property, the average of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution. It also characterizes the bias between this expected value and the critical points of the objective function under different local regularity conditions. The paper is well-written and studies an important problem. The authors are encouraged to incorporate the feedback from the reviewers in the revision.
Decision: Accept (Poster)