Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies generalization gap for stochastic gradient descent. Since the generalization gap can be expressed in terms of the number of fixed-radius balls required to cover the domain on the function, it suffices to bound the number of balls covering the SGD trajectory. For strongly convex functions, the bound is derived based on the fact that the gradient descent step is a contractor, i.e. it decreases the distance between points by a constant factor. For a non-convex function, the paper uses the fact that its gradients can be approximated by gradients of a piecewise strongly convex function. While the number of pieces can depend exponentially on the dimension, providing no improvement in the worst case, the paper presents a number of applications that have non-trivial number of pieces, improving state-of-the-art for the respective problems and sometimes significantly improving dependence on dimension.

strengths_and_weaknesses: The paper is easy to read and it clearly conveys its ideas. While I’m not sure that all mentioned applications are of great importance (in particular, single-layer neural networks), I believe that the presented applications shows the potential of this approach, especially in presence of regularization, as outlined in Discussion.

questions: I think it would be great to expand the derivation of the second term in the second line of Equation (B.3)

limitations: Yes
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: The paper proposes a new covering technique localized for SGD trajectories. For objectives that are perturbations of piecewise strongly convex and smooth functions, the proposed approach provides a dimension-independent upper bound on the generalization error. The authors further show that the approach gives rise to improved rates for several important applications, including multi-class SVMs and k-means clustering.
strengths_and_weaknesses: The paper is very well written; theoretical results are clearly presented and motivated. The proof sketches are instructive and give a good preview of the full arguments in the supplemental. The part of the theoretical results that I checked seems correct. It might be helpful for the reader to provide a table with the best-known rates and assumptions/ requirements in the previous and concurrent literature -- in the current version this is provided only in-text (e.g., Remark on page 4 and Discussion section), which is harder to read.

The paper is not in my direct area of research, so it is difficult to judge novelty and strength. Based on the background given in the paper, the results improve over the SOTA for several instances of the problem class considered, which would be a strong contribution.
questions: See above.
limitations: Limitations and possible extensions are sufficiently assessed in the discussion section.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This submission considers a localized covering technique to analyze the generalization bounds of SGD. The technique claims to construct an $\epsilon$-net which is spanned by the points on the trajectory reachable by SGD iterations, which leads to the dimension-independent bounds with constant step size and without using early stopping.  
strengths_and_weaknesses: - Strength: the narrative in general flowing well and the paper has a clear structure

- Weakness:

--> Assumptions made in the paper are strong.

--> Key lemma needs further explanation. 
questions: --> Assumption 2: I do find the bounded deviation assumption to be quite strong. Is it possible to remove this assumption?

--> Equation (1.3): I am a little surprised that the generalization bound is independent from the iteration count $t$. What is the rationale behind this claim?

--> Line 213: "multi-index linear models" why is this type of models fundamentally different from "single-index models"?
--> Equation (1.4): have authors considered the SGD with minibatch?

--> In lemma 2.1, the authors have implicitly assumed the boundedness of the iteration sequence $\theta^{(t)}$. Is this assumption reasonable?

--> Main concern: I find the proof to lemma 2.1 to be dubious. In particular, the claim $\|\theta^{(t)} - \phi\|\le \gamma^T R:= \varepsilon$ does not seem correct. 

--> Main concern: I am also surprised that there is no expectation involved in the statement of lemma 2.1.

--> Line 272: I doubt about the correctness of applying results with respect to differentiable functions on non-differential objective functions.
limitations: Strong assumptions made in the paper and unclear proof makes this submission require much more careful scrutiny.
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: The paper studies the generalization gap for objectives that are optimized
via stochastic gradient descent (SGD). By leveraging the fact that SGD
updates are contractive when all component objective functions are strongly
convex, the authors are able to apply an $\epsilon$-covering argument that
removes the dependence of d in the generalization gap for many
situations. Moreover, by arguing that any smooth, bounded non-convex
function is within an $\epsilon$ (in the $L^{\infty}$ norm) of piecewise strongly
convex functions, they are able to generalize their argument to a larger
share of non-convex objectives. Namely, they are able to demonstrate an
improvement in the generalization gap in the class of multi-index models and
K-means with hard label assignment.
strengths_and_weaknesses: Overall, I found this to be a well-written and well thought out paper.

[Originality]

Strengths:
The core of the paper seems to rely on two different insights:
+ The set of all possible SGD iterates at step T form an $\epsilon$-covering for
  all future SGD iterates with an appropriately chosen T
+ Any smooth, bounded non-convex function can be arbitrarily close to a set of
  piecewise smooth strongly convex functions (with the number of required
  functions possibly but not always growing exponentially in the ambient dimension d).

Armed with these two observations, the authors are able to argue an upper
bound on the generalization gap that does not necessarily rely on the
dimension. The combination of these two ideas permits the authors to
demonstrate an improvement in some common ML models (K-means and
multi-index models).

Weaknesses:
The paper mentioned that there was some previous inspiration based on
understanding the Hausdorff dimension of an SGD iterate chain, so in that
sense, the paper had some previous related ideas. However, I found this
connection to build more understanding rather than diminish the work done in
this paper.

[Quality]

Strengths:
While the theoretical framework in Theorem 2.1 and 2.2 are of independently
of interest, the application of these theorems to some real models is
powerful. This demonstrates that this perspective of using an
algorithmic-dependent stability can provide some benefit on top of general
methods that only consider the objective function and not the optimization
routine.

Weaknesses:
I do not have any notable complaints with the work presented.


[Clarity]

Strengths:
The paper was very clear and easy to follow (with a couple exceptions, see
detailed comments below).

Weaknesses:
NA

[Significance]

Strengths:
The generalization gap is a widely studied object in modern day ML. The
techniques used here could spark other ideas on how to use computational
geometry to better understand the nature of SGD in deep learning.

Weaknesses:
I could not tell from reading the paper whether the fact that these results
were upper bounds on the tail probabilities made this easier than the
expectation bounds mentioned in paper. I am not certain if this could be
drawn out a bit more, but it would be helpful for the reader to understand.
questions: [Q1] Are the best known bounds stated for K-means (soft and hard) and
multi-index models that were beat in this paper for the tail probabilities
or for the average SGD iterates?

[Q2] Is there any general theory describing when a smooth function can be
represented in the form of described in Proposition 2.1 with very few
piecewise components?
limitations: No, the authors have not addressed the societal impact if their work is misconstrued or incorrect.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study the generalization properties of parametric models trained with SGD. While classical statistical analysis of the generalization error $F(\hat{\theta}) - \hat{F}(\hat{\theta})$ rely on uniform bounding on the parameter space $\Theta$, thus ignoring the nature of the optimization process and leading to rates of the form $\sqrt{d/n}$ where $d$ is the dimension of $\Theta$ and $n$ is the number of samples, the authors propose to bound instead the process $F(\hat{\theta}) - \hat{F}(\hat{\theta})$ over points that are reached under the action of the SGD on the parameter space $\Theta$. 
Under a contraction hypothesis of the updates, two different points with synchronous SGD updates will eventually be close. In particular, the action of the SGD on $\Theta$ can be reduced to the action of the SGD starting from the point 0 (see Lemma 2.1) with $T$ iterations. Since the number of SGD trajectories starting from 0 with $T$ iterations does not depend on the dimension of the parameter space (coarsely upper-bounded by $n^T$), the dependency in $d$ in the generalization bound is removed.
The authors prove these results in the strongly convex and smooth case and in the more general case of perturbated piecewise smooth strongly convex functions. In particular, they highlight the fact that the latter can encompass standard generalization bound as any piecewise smooth function can be approximated by a piecewise smooth strongly convex function at the cost of increasing the number of pieces thus recovering the standard dimension dependent generalization bounds (see Remark, l. 196- 201).
Yet they showcase on several learning paradigms that they can improve this worst case bound and surpass state-of-the-art bounds.
strengths_and_weaknesses: Strengths:
- The idea of studying only the parameter space under the action of SGD is super natural and elegant. 
- The paper is well-written and easy to follow even for non-experts, arguments can be easily understood: indeed, under the contraction property, it suffices to study the trajectories starting from 0 with a finite number of iterations T.
- The framework is broad and as shown in their remark, it covers almost all cases of standard ML problems (even though it does not improve known results).
- In Section 3, the authors do a good job at convincing that their results can improve generalization bounds in many ML settings.
- The comparison to other works in related fields seems to be correctly made and from the samples I've read, the approach of the authors do seem quite different from other cited works yet it seems some results were already covered by [KSW22].

Weaknesses:
- Novelty of the results?  Even though the approach seems different and more intuitive, I believe the work of the authors is somehow a less general version [KWS22]. Indeed, the results are with high probability instead of in expectation and only piecewise contraction is required (instead of global contraction) yet it seems like a marginal improvement. In particular, their whole paragraph 2.1 is readily covered by [KSW22] and it should have been highlighted more clearly right in this section (instead of simply being mentioned in the Discussion section at the end of the paper). 
- (Minor) A more intuitive proof than the one provided in the Appendix would have been to use a standard metric entropy reasoning: Lemma 2.1 provides an \epsilon covering of $\psi_{\geq T}(\theta_0)$ of cardinality $| \psi_T( 0 ) | \leq n^{T(\epsilon)}$, hence we can upper bound with a chaining argument $E |F(\hat{\theta}) - \hat{F}(\hat{\theta})| \leq \sqrt{\log(n) / n} \int_{0}^{O(1)}  T(\epsilon)^{0.5} d \epsilon$ and recover a result with high probability using a Bousquet concentration bound. Is it because of the suboptimal $1/\sqrt{n}$ dependance that this reasoning was not used? If it is the case, I believe it should have been quickly mentioned as it would have been the natural argument for a statistician.
questions: See Weaknesses. 

limitations: The authors clearly show that their result is only a part of the equation when it comes to the question of the risk excess bound. Indeed, they claim they do not control the term $\hat{F}( \hat{\theta}) - \hat{F}( \theta^*)$ where $\theta^*$ is the true minimum $\inf_\theta F(\theta)$.
review_title: null

Meta-review: metareview: This paper introduces a new framework for proving generalization bounds for SGD that is based on covering the space of trajectories. When the underlying function is smooth and strongly convex, the fact that gradient descent contracts the distance between points by a constant factor, can be used to construct a good cover. More interestingly, their framework can be applied to nonconvex functions too, by approximating them by a piecewise strongly convex function. In general, the number of pieces will grow exponentially with the dimension, but in some important applications, like multiclass SVMs and k-means clustering, they are able to use their framework to derive interesting new generalization bounds. The paper is well-written and there was almost uniform consensus that it ought to be accepted. 
confidence: Certain
Decision: Accept