Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the excess risk when the population loss is locally strongly convex. For convex problems, they obtain an upper bound of order $\tilde{O}(1/n)$ without assuming globally strong convex as in previous works, where $n$ is the number of training examples. For nonconvex problems, they obtain a bound of $\tilde{O}(1/\sqrt{n})$, which improves previous $\tilde{O}(\sqrt{d/n})$ result. Furthermore, assuming there are no spurious local minima with high probability, they can improve the bound to $\tilde{O}(1/n)$.
strengths_and_weaknesses: Strengths:
1. The theoretical results look rigorous and sound. Their results improve existing ones in several aspects.
2. The authors also clearly show how their theorems are proved with good intuition.
3. The analysis looks novel to me.

Weaknesses:
1. For convex problems, although I can see that locally strongly convex + globally convex is more general than globally strongly convex, this improvement looks a bit incremental. Also, they have a worse dependence on the local convexity parameter $\lambda$. The authors might want to clarify more why it is more challenging. But it might be fine if the focus of this paper is the nonconvex part.
2. For nonconvex problems, although the result does not depend on the dimension $d$, it depends on $K$, the number of local minima. However, if only considering Proposition 1, $K$ could be exponential in the dimension in the worst case, which means the result is better than previous ones only when $K$ is much smaller than $d$.
3. The theoretical results look a bit dense. I am fine with it but it is still better if the authors could make it more readable. For example, they could hide the constant factors. Theorem 3 also looks not necessary because it is just a direct corollary of theorem 2.
questions: My major questions and suggestions are in the weakness part, below are some additional comments:

1. The authors mentioned it is hard to improve their worse dependence on $\lambda$. Could they explain intuitively why it is hard?
2. Assumption 1 is used in previous works does not mean it is mild. I think it is kind of strong, but acceptable.
limitations: I do not think this paper has any potential negative societal impact as it is purely theoretical. Regarding the limitations of the results, please see the weakness and question parts.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes upper bounds of the expected excess risk of locally strongly convex losses, removing global growth conditions.
Specifically, this paper bounds the generalization error and the optimization error to get better risk bounds.
For convex problems, the bound proposed by this paper is of the order $\mathcal{O}(1/n)$, better than previous $\mathcal{O}(1/\sqrt{n})$ ones.
For non-convex problems, this paper shows that for each population local minimum, there is an empirical local
minimum concentrated around it with high probability, and the bound proposed by this paper is of the order $\mathcal{O}(1/\sqrt{n})$, better than previous $\mathcal{O}(\sqrt{d}/\sqrt{n})$ ones.
strengths_and_weaknesses: Merits:
1. This paper generalizes previous global growth conditions to locally strongly convexity, which extends the application scenarios.
2. Under convex condition, the result given in this paper is better than [Hardt et al., 2016; Shamir and Zhang, 2009; Zhang et al., 2017].
3. Under non-convex condition, this paper proves that with high probability, there is an empirical local
minimum concentrated around each population local minimum, and the excess risk given in this paper is better than [Shamir and Zhang, 2009].

Cons:
1. To bound the stability, a key part is to bound the gap between models derived from adjacent datasets, however, by defining the 'good events', the proofs are similar to previous ones, which reduces the novelty.
2. Some references should be added, such as [Li and Liu 2022, High Probability Guarantees for Nonconvex Stochastic Gradient Descent with Heavy Tails], in which some better results are given.
3. Comparing with PL condition, the superiority of locally strongly convexity (or the relationship between them) should be given more detailed since some of examples given in this paper also satisfy the PL condition (e.g. robust regression).
questions: Please see the weaknesses part.
limitations: As I can see, this paper has no potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper derives improved generalization and excess risk bounds for convex and non-convex problems with the local strong convexity assumption. In the convex case, previous results had the bound $O(1/\sqrt{n})$ with just convexity and $O(1/n)$ with strong convexity or global strong-convexity type conditions, where $n$ is the number of data points. This paper obtains $\tilde{O}(1/n)$ with local strong convexity. In the nonconvex case, the authors derive when the number of model parameters $d$ is in a certain range and when empirical risk has no spurious local minima, the authors show $\tilde{O}(1/n)$. Without the latter assumption in the nonconvex case, the authors show the bound $O(1/\sqrt{n})$.
strengths_and_weaknesses: Originality/significance: To my knowledge, the paper's results are capture a regime that was not done in the previous work. The authors show that local strong convexity is enough to improve the bound of excess risk from $O(1/\sqrt{n})$ to $\tilde{O}(1/n)$. The authors seem to have done a good job if citing the previous work and highlighting the differences of their result. On the other hand, I must say that the authors didn't discuss any limitations of their approach. The writing of the paper suggests that the paper gets a free lunch, which is not the case from what I understand. The analysis seems to be significantly more involved than the previous work such as [32] and the improvement in the convex case for example is not strict, the additional local strong convexity assumption is needed. The authors cite several papers in numerous places in the paper for when this assumption holds (for example line 100), however no precise application is given. Can the authors clearly describe some applications and clearly show how they satisfy their assumption?


Clarity: The paper is provided mostly clear comparisons with the related works. However, the presentation should be improved since there are many unclear parts that I included in the "Questions" section of my review.
questions: - After Assumption 2, the authors state this assumption implies the population risk is locally strongly convex, however I cannot find this rigorously proved. Please give a reference or proof. eq. (32) in the proof seems to use strong convexity directly, please show how this follows from Assumption 2 with the region $S_2(w^*, \lambda/(4L^2))$ used in eq. (32).

- line 108: Please put the definition of excess risk in a display formula, not an inline one since the paper is about bounding this quantity.

- line 12: what does dimensional insensitive mean? Line 304 seems to have an exponential term which can dominate if $d$ is too large so that $d/n\geq c_1$. What happens if $d$ is too large to make the exponent positive here?

- line 28, 29: the discussion here with the previous work seems rather single-sided. It gives the impression that the authors strictly improve the previous work under the same assumptions, which is not true. There is the additional local strong convexity assumption. Please also discuss limitations of your approach.

- line 70, 71: this sentence seems broken, please consider rewriting.

- line 87, 88: this sentence seems broken, please consider rewriting.

- line 110: what is random in $\inf_w R(w)$? Why does expectation involve this term?

- Thm 1 takes expectation over $S, S'$ instead of the supremum in previous work, in the proof of this theorem, please explain how the second inequality from the last follow?

- Isn't Theorem 2 supposed to hold with high probability? Is this statement correct?

- line 155, 176: The way that the authors talk about their "proof technique" is very vague. Can you please provide pointers to the proof or explain better what in the proof technique results in this behavior so that your readers can understand your proof technique?

- Paragraph starting with line 168: What happens when global strong convexity holds? Does this paper recover the existing best-known dependence?

- Corollary 2: How does this bound compare to [32]? It seems when $T=n$, the bound in [32] can be better. Please provide a full comparison and highlight in which regime the bound in this paper is better and why this regime is important.

- Lemma 1: How to compute the iterate $w^*_{S, k}$ since the guarantee is on this iterate? The definition on eq. (12) requires knowing $w_k^*$ which are local minima. Is there a way to get a result on a realistic iterate that does not require knowledge of local minima?

- line 232, 233: please provide clear examples and clearly show why they satisfy the assumptions made in the paper.

- Theorem 4, 5 gives the result for $w_t$ whereas  Lemma 1 required iterates as eq. (12). Is the sequence $w_t$ generated as eq. (13)? If so, why is this feasible? If not, how is it possible to remove this requirement since Lemma 1 requires iterates of the form eq. (12)?
limitations: Limitations are not discussed in the paper. The authors always talk about how the results are better than the existing work. Authors need to clarify if it really is the case that there is no limitations on this result?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the excess risk for stochastic optimization problem where the objective function is locally strongly convex. The roadmap is to decompose the excess risk as the generalization error and the optimization error. Instead of demonstrating algorithm specific generalization bounds for certain algorithms, the paper bounds the generalization error via approximation of empirical problem to the population problem.
strengths_and_weaknesses: ## Strengths

The main contribution of the paper is a new roadmap to analyze the generalization bounds for stochastic optimization. 
1. The obtained generalization bound is dimension insensitive (improving the generalization bounds derived from uniform convergence arguments).
2.  The obtained generalization bound has no restrictions on specific algorithms and particular stepsizes choices (improving over the generalization bounds derived from algorithmic specific stability arguments). 
3. The paper identifies a key issue that the generalization bound in [32] will explode when iteration number goes to infinite, which does not align with some of the numerical experiments, and provides a more precise generalization bound characterization for locally strongly convex objectives. 

## Weaknesses

See questions below.
questions: 1. In Corollary 1 and 2, why the optimization error of GD for convex problem is of $1/sqrt(t)$ and of SGD for convex problem is $1/t^4$? It contradicts with what is mentioned in Line 184 from reference [12,63]. Which ones are correct? Cor 1 & seems to be far from optimal.
 
2. Why the paper adopts a new definition for the uniformly stable (Def 2)? 

3. In equation (13), it uses an infeasible algorithm to establish the algorithmic stability bound of $w_t$ in order to get the generalization error of $w_{S,k}^*$. I would assume that in (15), the $1/n$ term comes from the stability bound of strongly convex objectives?

4. Why in Theorem 4 and Theorem 5, the generalization bounds depends linearly on the number of local solutions, $K$? Is it from the proof technique? 

5. Could the author further explains under what condition there would be only finite number of local solutions? This seems to be a key to Theorem 4 and 5 to hold.





### Minor Comments
1. Line 212, add a bracket for lambda / 4L_2.
2. Line 176, the sentence seems to be incomplete. 
3. It would be nice if the author can add some figure in the final version about the roadmap of the analysis idea. It could highlight the importance of this framework.
4. Lemma 1, Theorem 4, 5 could have been more informative if adding some discussions about where does each term come from. 
limitations: The improvements are based on the key assumption that the objective is locally strongly convex. As a result, in the nonconvex case, there is a one-to-one correspondence between the local solution of the empirical problem and the population problem. It remains unclear how to obtain dimension free bounds beyond this regime. Please add some comments if possible.
review_title: null

Meta-review: metareview: There is a consensus among reviewers that the results are strong with novel results on the rate of convergence of the excess risk of certain iterative algorithms for convex and non-convex problems, under a local strong convexity assumption. 

For the camera-ready version, the authors are encouraged to provide a more detailed discussion of the limitation of the work as emphasized in the discussion with reviewer 7m5U.
confidence: Certain
Decision: Accept