Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides theoretical results for the asymptotic convergence of SGD algorithm under an over-parameterized setting. It shows a set of assumptions that can guarantee the global convergence of SGD almost surely in some non-convex setting. 
strength_and_weaknesses: The strengths of this paper are the theoretical results for the global convergence of SGD almost surely. The authors consider the regular sampling scheme and propose a new scheme (sampling noise with global stable guarantee). They prove the asymptotic convergence for SGD under a set of assumptions. 

The weaknesses of this paper are: 
- This paper did not explain the intuition why SGD converge globally very well. The assumptions are not clearly motivated. The authors should explain why they have two set of assumptions on the gradient/ sample gradient of g. One is Assumption 2.1 part 4, line 2 where there is a lower bound on the liminf of gradient, the other is Assumption 2.2 where we put an upper bound on the sample gradient. Please add a discussion why the theory needs these assumptions and make sure they do not contradict each other. In addition, Assumption 2.3 is not natural when it asks that the constants $c_\theta, \hat{c}_\theta$ are bounded away from 0 and by a constant of $\theta$. 
- The presentation of this paper is poor. There are many notations and variables that were mentioned before the authors define them in the draft. For example: $M_0$ and $a$ were referred in Assumption 2.1 but only defined until 2.2, $\tilde{\nabla} g$ has no definition, 'global stable guarantee' was referred before the explanation,... Most of the time, the sketch proofs are confusing and they did not help to understand the thought process to prove the theorems. 

Question: In Theorem 3.4, what is 'the variant of Assumption 2.3 described immediately preceding this statement'?
clarity,_quality,_novelty_and_reproducibility: The results of this paper seem to be new and the approach is different from prior work. However, its clarity and presentation is not good. 
summary_of_the_review: Although this paper show interesting results, I am not fully convinced by the assumptions and the intuition/reasoning behind the proofs.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper utilizes a method based on Clarke subdifferential and Lyapunov stability to show that SGD for an over-parametrized model converges to the global optimum almost surely under arbitrary initial value and some mild assumptions on the loss function. In addition, it is also shown that if the learning rate is larger than a value depending on the structure of a global minimum, the probability of converging to this global optimum is zero.
strength_and_weaknesses: Strength:
This paper considers two fundamental problems in learning, i.e., does SGD provably find the global optimum with an over-parametrized model, and why SGD prefers a flat global minimum? If all the claims (Thm 3.1, 3.2, 3.3) in this paper are correct, it is indeed a breakthrough in this field.  

Weaknesses:
However, it is hard for me to judge the correctness of the draft due to the following writing issue. 

1. There are so many notations used without definition. For example, $\tilde{\nabla}$ in assumption 2.1 (it means subdifferential?), $N_0$ in the proof of Claim 2.2 (number of samples in a batch?), $K_0$ in equation (5) and $\zeta_n$ in equation (9).

2. I did not see the importance of Claims 2.1 and 2.2, but they took up much space in the paper. Moreover, the sketch of Thm 3.1 seems to be disconnected from the preliminaries in section 2. 

I would recommend the authors add more insights and intuitions of the proof instead of the proof details and provide some high-level comparisons on why the proposed techniques could show such strong results. This paper considers two fundamental problems in learning, i.e., does SGD provably find the global optimum with an over-parametrized model, and why SGD prefers a flat global minimum? If all the claims (Thm 3.1, 3.2, 3.3) in this paper are correct, it is a breakthrough in this field.  

Some related references are missing. I would like the authors to address how their approach and results differ from these papers. 

Vaswani, Sharan, Francis Bach, and Mark Schmidt. "Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron." In The 22nd international conference on artificial intelligence and statistics, pp. 1195-1204. PMLR, 2019.

Chizat, Lenaic, and Francis Bach. "On the global convergence of gradient descent for over-parameterized models using optimal transport." Advances in neural information processing systems 31 (2018).

clarity,_quality,_novelty_and_reproducibility: See the above comments.
summary_of_the_review: This paper considers a fundamental problem in the convergence guarantee of SGD in an over-parametrized model. However, the paper is not well-written in its current form, which makes the reviewer hard to verify its correctness.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence property of SGD under the over-parameter setting. Under some regular assumptions of the loss and subdifferential gradient noise, this paper gives some novel results: (1) SGD must converge to a global optimum with probability 1. (2) SGD converges to a sharper global optimum not as easy as a flat one. (3) SGD achieves an arbitrary accuracy in polynomial time.
strength_and_weaknesses: Strength:
The paper is technically sound. 
The paper studies an interesting question related to the over-parameterized problem and provides more understanding of the optimization landscape.
The theoretical results are important to the machine learning community.

Weakness；
More discussion should be added after each Theorem.

clarity,_quality,_novelty_and_reproducibility: Paper is written well, well-organized, and has nice reproducibility.
summary_of_the_review: The paper provides some novel insights on SGD’s optimization landscape. For example, the authors show interesting and important findings that SGD could indeed obtain a global optimum even in the non-smooth non-convex over-parameter setting.
I have some concerns.
(1) This paper studies square loss. Can these results be generalized to general losses?
(2) What’s the difference between $\tilde{\nabla}$ and $\nabla$. subdifferential?
(3) Can the authors provide some numerical experiments to support the theory in this paper?
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper claims that SGD converges to global minimum almost surely, under some assumptions.
strength_and_weaknesses: I have a few technical concerns on different aspects of the theoretical results in this paper.

Problematic assumptions:

Assumption 1: $g(\theta)$ is already non-negative by definition, and there is no need for repitition. The actual meaning of smoothness needs to be made clear here ($C^1$ or $C^{\infty}$ ?)

Assumption 3: the set of roots itself is already a closed set, as long as $g(\theta)$ is continuous which is implicit: one only needs to prove any limit point $x$ of roots $\{x_i\}$ is still a root. Suppose for contradiction $g(x)>0$, then by its continuity there exists an open neighborhood $S$ containing $x$, such that for any $x'\in S$ we have that $g(x')>g(x)/2>0$. However, some root $x_N$ will fall into $S$ which finishes the proof.

Assumption 4: this is a rather strong assumption in my opinion. The simple example $f(\theta,x)=(\theta-x)^2$ fails to satisfy the assumption, let alone neural networks. Even if the domain is restricted to be a compact set of $\mathbb{R}^d$, the constant $c$ is likely to be a large poly factor in the dimension $d$. 

Assumption 2.3: can you give any example included in the large family of functions as claimed? 

$\tilde{\nabla}g(\theta)$ is not defined. Is it an unbiased estimator of $\nabla g(\theta)$ or what? The model of SGD isn't explained either.

Main results:

I will only take Theorem 3.1 as an example. The argument in step 3 is doubtful: $\theta_n$ might not converge at all with positive probability. Suppose I am the adversary that generates the stochastic estimator $\tilde{\nabla}g(\theta)$, then at any root I'm allowed to generate $\pm a v$ by Assumption 2.2 where $v$ is randomly drawn from the unit sphere. Then such sequence of $\{\theta_n\}$ doesn't converge, and one can only talk about limit points. Unfortunately, even a non-root point can be a limit point if $\tilde{\nabla}g(\theta)$ is an unbiased estimator.

I suspect that the proof goes through when $\tilde{\nabla}g(\theta)$ is exact and the randomness of SGD decreases with function value, as in equation (5). However, this is a very strong and non-standard assumption and I feel it's not what the authors mean.

clarity,_quality,_novelty_and_reproducibility: The writing can be improved, some sentences are hard to parse.
summary_of_the_review: Based on the mathematical issues I found, I doubt the correctness of this theoretical paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper provides theoretical results for the asymptotic convergence of SGD algorithm under an over-parameterized setting. It shows a set of assumptions that can guarantee the global convergence of SGD almost surely in some non-convex setting.

Most of the reviewers do not support its publication at ICLR and I also agree with the reviewers. The main concern from the reviewers is that the results rely on the strong assumptions, which are quite restrictive. There is no empirical evidence to show that these assumptions could potentially hold in practice. 

Please take the comments and suggestions from the reviewers in their detail reviews to improve the manuscript for the future submission. I would suggest the authors to consider some optimization journal venues for this paper. 

justification_for_why_not_higher_score: - The main concern from the reviewers is that the results rely on the strong assumptions, which are quite restrictive. 
- There is no empirical evidence to show that these assumptions could potentially hold in practice.
Decision: Reject