Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers
Authors: Sejun Park
Umut Simsekli
Murat A Erdogdu
Venue: NeurIPS 2022 Accept (2022)

Abstract: In this paper, we propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific complexity measured by the covering number, which can have dimension-independent cardinality in contrast to standard uniform covering arguments that result in exponential dimension dependency. Based on this localized construction, we show that if the objective function is a finite perturbation of a piecewise strongly convex and smooth function with $P$ pieces, i.e., non-convex and non-smooth in general, the generalization error can be upper bounded by $O(\sqrt{(\log n\log(nP))/n})$, where $n$ is the number of data samples. In particular, this rate is independent of dimension and does not require early stopping and decaying step size. Finally, we employ these results in various contexts and derive generalization bounds for multi-index linear models, multi-class support vector machines, and $K$-means clustering for both hard and soft label setups, improving the previously known state-of-the-art rates.

Generalization Bounds for Stochastic Gradient Descent via Localized E-Covers
Sejun Park
Korea University
sejun, www.wo00gmaia..cooommm com
Umut Şimşekli
DI ENS, Ecole Normale Supérieure, Université PSL, CNRS, INRIA umut. Sammskkl@@nniiaa fr
Murat A. Erdogdu
University of Toronto & Vector Institute erdogduucs toronto.... edu
Abstract
In this paper, we propose new covering technique localized for the trajectories of SGD. This localization provides an algorithm--peccfic complexity measured by the covering number, which have dimennion-indeeeeddnn cardinality in con- trast to standard uniform covering arguments that result in exponential dimension dependency. Based on this localized construction, we show that if the objective function is a finite perturbation of piecewise strongly convex and smooth function with P pieces, i.e. non-convex and non-smooth in general, the generalization error can be upper bounded by O( ( (log log(nP))/m)) where n the number of data samples. In particular, this rate is independent of dimension and does not require early stopping and decaying step size. Finally, we employ these results various contexts and derive generalization bounds for multi-index linear models, multi-class support vector machines, and K-means clustering for both hard and soft label setups, improving the known state-of-the-arr rates.
Introduction
We consider the following stochastic optimization problem F()) = Fz (0(; 2)
min #E0
(1.1)
where 9 represents the optimization parameter, θ Rd is convex parameter domain, f(:;2) is possibly non-convex loss incurred by a single data point 2 E Z, and Z is a random variable on Z following the data distribution. Since the distribution of Z is unknown in general, the following proxy based on independent and identically distributed (i.i.d.) samples 21,..., on of Z is optimized instead
1
min Oee
[(()
f(0;z)) z)) = 71
(1.2)
Given a learning algorithm A(-) mapping samples .I,..., on to an approximate solution of (1.2), bounding the generalization error! ((A(2),..... 2n)) )) F(A(21, 2n)) is a fundamental problem
'This quantity is also referred to as the generalization gap or the estimation enror in the literature.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

in learning theory. Classical gegorifum-independder results rely on uniform convergence over the entire domain θ R thus. they apply to any learning algorithm. However, these bounds often increase with the dimension d [SSSSS09, SSBD14, Fel16], becoming vacuous in the modern over- parameterized regime [ZBH+21]. To derive crreessoon-inependden bounds, researchers have been investigating algorithm-dependee generalization properties, especially for commonly used training methods such as stochastic gradient descent (SGD) [HRSI5, SHN+ 18, YKM21J.
Notably, algorithmic stability is technique for deriving generalization bounds based on the properties of a specific learning algorithm, which leverages that if a parameter learned by an algorithm is robust under a perturbation of samples 21...., Zn. then the generalization error at that parameter must be small [BE02]. Based on this principle, several works proposed generalization bounds for SGD and its variants under various setups [HRS15, Lon FV LLQ20, BFGT20, L,20, FO21, LLY21, KWS22]. Bounds derived using algorithmic stability is optimal for strongly convex and smooth functions [SSSSS09] and convex and non-smooth functions [BFGT20, AKI.21]. Nevertheless, without global (strong) convexity, early stopping, and/or decaying step size, generalization bounds based on algorithmic stability often diverge with the number of SGD iterations [HRS15, LLQ20], failing to explain the empirical observations.
To obtain (ambient) dimension-innependden bounds that do not diverge with the number of iterations, recent works proposed to utilize the low-dimensional fractal structures generated by the SGD iterates whose complexity can be measured by a notion called the Hausdorff dimension [Fal14]. In this context, [SSDE20] showed that, under a continuous- time surrogate for SGD, the generalization error can be bounded by Ö(v dh/ /n), where dæ denotes the Hausdorff dimension of the optimization trajectory. This result was later extended to discrete-time iterated function systems by [CDE* 21]. Here, the Hausdorff dimension can be smaller than the ambient dimension [CDE*2] 21]. ultimately providing improved generalization bounds. However, both of these results are inherently asymptotic, and rely on opaque assumptions that are hard to verify in practice.
In this paper, we propose a new framework for deriving generalization bounds for the projected SGD with a constant step size and without requiring carly stopping. Inspired by the works I$SDE20, CDE+21], our framework is based on complexity measure of the trajectory of SGD, which can be quantified under standard verifiable conditions. Our contributions are as follows.
Localized e-covers for SGD. Our first principle contribution is a covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific complexity measured by the covering number, which can have dimension inniiioonnddeeedeent cardinality in contrast to standard covering arguments that result in exponential dimension dependency.
Generalization bounds for SGD. Based on this localized covering, we establish dimension- independent generalization bounds for SGD, for a rich class of non-convex loss functions whose gradients can be approximated by that of piecewise strongly convex and smooth function h, i.e. [V: 2) Vh(B; 2) I & for some Ç. In particular, with high probability, we prove the bound
(v log log(nP)
F(0(0)) - F(O(0)) (F(()))(((0) =0
+ &
(1.3)
where g(t) denotes the parameter generated by SGD iterations for a sufficiently large f, and P denotes the number of strongly convex pieces needed to approximate f. We further show that the gradient of any (piecewise) smooth function can be approximated with that of a piecewise strongly convex and smooth function, demonstrating the wide applicability of the bound (1.3). Finally in the special case P = 1 and & = O, our result reduces a non-asymptotic bound where the complexity is captured by the Hausdorff dimension of the invariant measure of SGD.
Improved bounds in specific models. We employ the above result to derive generalization bounds in several statistical models trained by SGD, including multi- support vector machines, and K K-means clustering with both hard and soft label setups, improving the previously known state-of-the-an art generalization error bounds in this context.
linear models. multi-class
Notation and problem setup. For k E N, we denote [k] == [1....,k} the lz- norm. For > 0 and A E IR4, we use (0) to denote the d-dimensional closed ball of radius& E, centered at 0. Given a set S C IRd and > O, we say C. S RRd is an "e-cover" of S S C UPEC. (0).
}} We use || ||| to denote

---

Given a step size 17 > 0, an initial parameter ((0) E O and randomly sampled index in E [n], the t-th iteration of the projected SGD performs the following update on the parameters
( 9s. (B (0(--1) 1) := Ill (g ((((t)) 2n)) for t = 1,2, ...,
(1.4)
where [Tx(0) == arg mingre ge | 0|| denotes the Euclidean projection. The domain θ is convex; thus, the projection operation unique. We note that the projection is not needed under the presence of an fg-regularizer and Lipschitz continuity; see Section 4 for more details. Throughout the paper, we use ((0) := 91, .... o 9t, (0(o) for possibly random indices .4.
Lastly, we recall few standard notions. f θ - IR is called "a-strongly convex" and "p-smooth" respectively if for all 0, 0' +. the following conditions are satisfied
f(0) - f(0') - V f(0) (0 0') 2 2
a 10 0'11? and [I - v)((0) = B|10 - 0'
The function f is called "convex" if it is O-strongly convex.
2 Main results
We demonstrate covering construction in Section 2.1 in the classical strongly convex and smooth case in which the localization argument can be simplified by the contractivity of SGD, We present our main generalization result on non-convex losses in Section 2.2, and its implications in Section 3.
2.1 A localized covering construction: Strongly convex and smooth case
To motivate our approach, let us first briefly discuss the limitations of prior methods that are based on uniform convergence of empirical processes. Given a set of parameters @ C 88 (0). let C. be an E-cover of θ, i.e. θ S Usec. (Ø). Uniform convergence over θ can be established with high probability by simply applying the union bound over C,, which yields generalization error bound depending on the cardinality of the cover Vlog [Ce However, C2 is typically independent of the algorithm being used, and standard e-covers for θ yield [Ce| = (R/e) ((1)) thus, bounds based on covering numbers often grow with vd. which can be loose if d is large. To overcome this issue, we use the contractive properties of SGD in the strongly convex and smooth case and localize the s-cover. Namely, instead of covering the entire feasible set θ we construct a cover that contains only the points that can be reached by SGD trajectories, resulting in a covering number that independent of the ambient dimension d. We introduce the following sets produced by SGD trajectories.
Definition 1. We define the following two subsets of Q.
The set of points that can be reached by T SGD iterations initialized at ((0) E O
gs, (8(0) ii,.... ir E [n]]] "The set of points that can be reached by any 1 T SGD iterations initialized at (00) E O
(f())))) == {gin
Vz (0())
(.()%))
12T
For 7 (0. 1). a function 9 θ - O is called "ry-contractive" if for all 0, 0' E O, it satisfies [l - (00)) S 01 0'1l. the constant step-size case, SGD iterates converge to a distribution instead of single point [DDB20], but their contractivity can still provide the following localization: all possible SGD iterates after sufficiently many iterations can be e-covered by n (log((/))) points.
Lemma 2.1. Suppose that 91, I2.... are c-cottractivee for some y (0, 1). Then, for any initializa-
tion ((0) E O C (0) and for any fo T = Te max log(1/e) .0.. we have
(00)) S (e)
6EVT(()
ogi, (0(0) for some i it,..., in [n]] Let Φ- := 9i, o .... Ii. 1 (0) and notice that & E (0) by construction. Then for T' == Tg and g(t-T) I
Proof. Fort > T, let ((1) E (0(() such that ((0) = gr, o...
Fi, have
[ Φ1 7 (1 Oll R c,
since each gi is -onntractive and ||o(t-T)|| < R by (1.4). This implies g(t) E U0e (o)))
3

---

o...... (0)
0 0e0,,200.10 [1,2]]
T. SCD updates
91 g2
T. SGI updates
S1s
91 (1)
91 ga o 9t, o...o 9t, (8) 8, 0, 0, E (1,
9km
Left: illustration of T. coupled projected SGD updates from two distinct points. Right: illustration of our localized cover Vr covering 2rr with T = 2 and n = 2 and Wr n =4.
Figure I:
For strongly convex and smooth f(;;2), an SGD update with a sufficiently small step size is contractive [DDB20]; that is, applying 9i to any two points decreases the distance between them (see Appendix A.1 for formal derivation). Therefore, for any e > 0, there exists T == Tg such that applying T synchronously coupled SGD updates that the same sample each iteration can make the distance between the initial points smaller than E; see Figure 1 (left). This observation implies that the set (0) of all parameters that can be generated by T SGD updates when initialized the origin s-covers the set v (0())) of all parameters that can be generated by any 2 SGD updates for an arbitrary initialization 810); see Figure (right). In contrast to & that scale with [C.| (R/s) = e ed(d), we obtain [0) S n² = O(1) which is independent of the dimension d and only polynomial in the number of samples n.
independent covers of
We make the following additional assumptions on the loss function f- Assumption 1 (Weak Lipschitz continuity). For >>> there exists h θ TR such that for all 0, 0' E θ and E Z, If z) h(0) - (f(0'= - h(0')) S L| 0'|l-
Notice that h 0 reduces to the classical Lipshitz continuity, but the above condition is more general. Assumption 2 2Bounded deviation). For B B>0 for all @ sup [(0; =) inf [(0;=)] B.
We note that Assumptions & 2 (or their variants) both appear in several algorithmic stability-baas -bseed results; see e.g. [HRS15, Thm 3.10]. We also highlight that these conditions are invariant to adding regularizers (e.g. consider /(0; 2) + [(; 2) + 2 [[01()) which will be useful in Section 3. 2
Theorem 2.1. Suppose that Assumptions 1 & hold and there exist a, B > O such that f(:;2)
is a-strrogly convex and 3-smooth Q C ( (0) for all E Z. For any r) E (0,2/8), let
.). Then, with probability at least - 6, for any ((0) E A, T, and i1, , is E [n]. SGD iterate g(t) satisfies
7 = V1- -2ann + aBr22, T := max
(2L(2 log(1/7)
((B())) (
BT +1
+ BV
T log n 1og(2/5)
(2.1)
72
2n
Remark. A few remarks are in order. For stochastic convex optimization, the best achievable bound via uniform convergence over θ is worse than the algorithmic stability-based bounds for SGD by factor of Vd [SSSSS09, Fel16, FV19]; however, by localizing the uniform convergence argument, we are able to obtain dimension -iwinsiiooniddeeddeene bound. We note that this high-probability result still not directly comparable to most stablity-based bounds which are given in expectation. exception is [FV19, Thm 4.5] which obtains near-optimal bounds for SGD in the convex case by tuning the number of iterations to be taken, obtaining a rate of Olog(nn/5) log(n)/ ( /n). ) In contrast, our bound reads O ( (logm)) log (1/8)//) which is better by a logarithmic factor and holds for any sufficiently large number of SGD iterations. We emphasize that the bound (2.1) holds for the union of all trajectories of SGD generated by > T iterations, whereas the stability- consider single parameter generated by SGD. A similar setup is considered in Corollary 2.1 where we establish improved bounds on the generalization error removing the logarithmic factor. Lastly, we note that localized covering can also be used for deriving bounds in expectation; see Appendix D.
results often
The proof of Theorem 2.1 follows from three steps. i) Lemma 2.1 implies that any g(t) for t > T can be approximated by some parameter g(T) generated by T SGD updates initialized at O. ii) ((O(T))

---

concentrates around F(o(T) since ((7) is almost independent of the samples, i.e. it depends on at most T (n)) of n samples. iiz) The empirical process (F(O(T)) F(O(T)) uniformly converges over the set (0) which has a dimension-fiee cardinality. See Appendix B.2 for details.
While the bound in Theorem 2.1 holds uniformly over all possible initializations, it can be tightened by considering a single realization of (10) in the following corollary.
Corollary 2.1. Assume the setup in Theorem 2.1. Then, for any (0)) E e,,t2,, and ii...., [n]]
with probability at least we have
((o0))-F((()))
BT
BV
log(2/0))
n1
2n
For sufficiently large n, the bound in Corollary 2.1 coincides with the tight concentration bound at fixed 8 E Ô; however, has the limitation that at least 2 SGD updates are required. This is remedied in the next result which does not require strong convexity and smoothness.
Corollary 2.2. Suppose that Assumption 2 holds. Then, for any (00) 2 with probability at least we have
I 2 0, and in......., is [x]]
Bt + BV 2m
log (2/6)
F(0 (((0))))(())))
F(O())
n
The bound in Corollary 2.2 requires early stopping since it diverges as t + co. However, since Corollary 2.2 only requires Assumption 2, it can be easily combined with other results, e.g. Corol- lary 2. to provide generalization bound that holds for any number of SGD iterations. The proofs of Corollaries 2.1 and 2.2 are presented in Appendices B.3 and B.4, respectively.
Relation to fractal dimension. There is an interesting connection to be made between Theorem 2.1 and the Hausdorff dimension of the support μ of the stationary distribution of (projected) SGD. For example, suppose that E (0, 1). è = B (0). f(0: 2) 1 0- I| for some 8 E [ and ||0%, - 07, ll 2 2 R for all * j. Here, the last assumption can be satisfied with high probability if dd, r are large enough and 0 ~ N(0, (F.),.. i.e. zero-mean Gaussian with covariance a² /; see e.g. [PLYS21, Appendix CJ. Under these assumptions, the bound in Theorem 2.1 can be reformulated as
BT+1 + +B
[H +
log 2LR (og(1/7)
log n + log(2/6)
F((()) - F(O()))
(2.2)
2n
where dæ denotes the Hausdorff dimension of ja. The precise definition of dæ and the derivation of (2.2) are presented Appendix B.5. In (2.2), dæ replaces the ambient dimension that appear in algorithn-indeeenden bounds [SSBD14]. We note that such connection between the fractal dimension and generalization bounds has been also studied ($SDE20, CDE+21]: however, their bounds asymptotic and require non-trivial assumptions that not easy to verify in practice.
Generalization due contractivity. Contractivity of SGD has also been used to derive general- ization bounds in the concurrent work [KWS22]. Although the localized covering construction in Lemma 2.1 relies on the same principle, our results differ from those in [K [KS2 on two key aspects. First and foremost, as we shall see in Section 2.2, the localized covering argument used in Lemma 2.1 can also be applied to the non-convex case which the uniform stability- based argument used in [KWS22] provably breaks down (Appendix F); thus, extending the results of [KWS22] to cover non- convex objectives is highly non-trivial. Further, the generalization bounds in [KWS22] are provided in expectation, i.c. (o(()) - F( ie. [(((t)) F((( < ((1/vn). When translated to bounds in expectation, our results read (LF((())) - F(O())) < ((1/n) and (()()) F(O())]] Õ(1/ /T); see Appendices D & E.
< (L1n)), whereas we provide high- probbbbbbayilityy bounds,
2.2 Non-convex case: Perturbations of piecewise strongly convex and smooth functions
Algorithmic stability technique yields (near) optimal rates for strongly convex objectives; however, when applied to non-convex functions, the resulting bounds often diverge with the number of SGD iterations [HRS15, L.QQ20.. The localized covering construction introduced the previous section remedies this issue, providing more stable generalization bounds. Specifically, we establish
5

---

dimension dimension-independdee independent generalization bound for functions that are finite perturbations of piecewise strongly convex and smooth functions. We further prove an approximation result and show that any smooth non-convex function can be approximated with a piecewise strongly convex function. Since piecewise strongly convex and smooth functions may not be differentiable on the entire O we will use the auxiliary gradient in Definition 2 as surrogate for the SGD update (1.4).
Definition 2. f is "piecewise o-strongly convex and 3-smooth with P pieces on Q if there exists a partition (P1, 1...... Pp) of A and o-strongly convex and B-smooth functions h1,-... hp on O such that f= = hp on Pp for all E [P]. We also define V f(0) == Vh₂(0) if E Pp.
Piecewise strongly convex and smooth objectives are widely used in machine learning applications. For example, the objective of learning single layer of ReLU network with ég-regularization is piecewise strongly convex and smooth. Furthermore, the objective of learning an entire ReLU network is also piecewise strongly convex and smooth on small loss regions [Mil19]. Such observations easily extend to more general settings, e.g. an objective function defined as the summation of a piecewise linear loss (e.g. hinge loss) and é2 eg-regularization. However, if we further allow for finite perturbations, any piecewise smooth non-convex function can be covered within this framework.
Proposition 2.1. For any piecewise 3'-smooth with Q pieces θ C B (0), and for any & > 0 and O < a S B, there exists a piecewise o-stroogly convex and 3-smooth h with at most Q(3(3 + R/EE" pieces such that [[V [ for all E O.
For this general class of non-convex functions, we derive the following generalization bound.
Theorem 2.2. Suppose that Assumptions
hold and θ S (0). Suppose further that there exists h: x x Z - R such that for any E Z, h(:;z) is piecewise u-strongly convex and B-smooth with P pieces on O satisfying
[V 2) - Vh(0: =)1l Σ
(2.3)
for all 0 E O. For any 1, E (0,2/3), let 7 := VI- 2am + aB72. Then given T E N, with probability at least - for any ((0) E t, T, and i .1,...,44 E [m], we have
( - F(OO))
BT -mmm- + BV n
Tlog(nP) + log (2/5) 2L
7 T
1 7T
1 7 m
2n
Remark. The bound above is stated in full generality and holds for any SGD iterate f 2 T and any choice of T > 1. However, obtain meaningful generalization bound, one may choose, for example T = (log((IR)/ log(>~1)), I). In the case that y, B, L = O(1), the bound simplifies to
Iog((nR) <V(v ( log(nP) + log(1/0) + +6) +5)
F(010) F(B(0)
(2.4)
n
Here, the first term in the bound is logarithmic in the number of pieces P and the last term scales linearly with the approximation error Ş. Thus, the generalization bound depends on the trade-off between the complexity of h through P, and how well Vh approximates Vf through ç. In this regime, in contrast to algorithmic stability-baad based bounds, the above result does not grow with the number of SGD iterations, i.e. early stopping is not required for generalization in Theorem 2.2. We finally note that Theorem 2.2 holds for any f with an auxiliary gradient V satisfying (2.3).
In light of Proposition 2. any piecewise smooth function can be approximated by piecewise strongly convex and smooth function; the worse case, the number of pieces is at most e (d)) Therefore in this pessimistic case, Theorem 2.2 recovers the classical gesorithm-independeen covering ((1((LV))) and T' @llog( LRm)). However, any value
bound Ö(B /d/n) by choosing of that is sub-exponential in dimension yields improved generalization bounds. In particular in the next section, we consider certain (non-convex) statistical models and carefully design h so that Theorem 2.2 improves the existing generalization error bounds. In contrast, uniform stability-based bounds for piecewise strongly convex and smooth functions are in general (2(1) after sufficiently many SGD iterations; see Appendix F. That is, the contractivity- based bounds in [KWS22] cannot be directly extended to piecewise contractivity (2.3).
The proof of Theorem 2.2 relies on a modified version of the covering construction presented in Section 1. First, we define the auxiliary parameter update gt.p (0) := 0- D- 2:) where hp (0())))) 24)

---

denotes the strongly convex and smooth function satisfying Vf( = (2)(+ on the p-th piece. We show that (0) (grr.pr
9b (0) f.....: .T E [m].P] ..... PT E [P]] covers V>t for any g(o) E θ as Lemma 2.1. Since |4 _ (nP)², applying a concentration
inequality and the union bound over the localized cover yields Theorem 2.2. Formal proofs of
Proposition 2.1 and Theorem 2.2 are provided in Appendices B.6 and B.7, respectively.
Applications
In this section, use localized covering to prove generalization bounds for multi-index linear models, multi-class support vector machines, and K -means clustering for both hard and soft label setups, trained by SGD, improving the state-of-the-art results known for these models.
3.1 Multi-index linear models
Given a sample = (v, .)) E y Bi (0), consider the fz-regularized loss in a multi-index model with K indices parameterized by 0 = (0,) E R
f(0:2) = [(0 x..., 0 0kzyy) + Σ 10,
(3.1)
Characterizing the generalization properties multi-index models is an important problem with many applications including regression, classification, dimension reduction, and learning single-layer of a neural network. In the following theorem, we derive a generalization bound for multi-index models by approximating each f();)) with piecewise strongly convex and smooth function, and then applying Theorem 2.2. The proof is given in Appendix C.I.
Theorem 3.1. Let 0 (0 and θ IT θ₁ for some convex O S. B (0). Suppose that satisfies (3.1), Assumptions
hold, and ((...... :;g) is piecewise 3-smooth with Q pieces on θ for all y y. For any 17 (0, 2/),, let y == [1 nd), T = max
[og[3L Rn)
.0. and
Tog(1/>)
P := :o-oyy (3, 17, K, L, R. Ra, n.).. Then, with probability least 5, for any g(0) and i1.....4; it E [n], we have
any
((((()) - F(((O)) BT+1 + BV
Tlog(n PKQ) Q) + log(2/0)
2n
Generalization behavior of multi-index models has received considerable attention; subset of notable results include [Gue02, Zha04, JKZ+12, CMR13, LDZK19). Under the same conditions of Theorem 1, existing state-of-the-an bounds scale at least linearly v or K, while our result dimension-free and scales with vK. Specifically, the result [LDZKI9) 19] translated to our setting reads (& is L-Lipschitz, and f(0; z) E [0, B] which are stronger conditions than Assumptions I & 2)
((0) - F(O) S [KRRR, + B
(3.2)
Vn
for all 0 E O, which is obtained via [LDZK19, 19, Cor 3 & 9] with A <- R and p < cc. While the bound in (3.2) is linear in KLRRg, our bound is linear in VK and logarithmic L, R, Rg. The significance of this improvement can be better seen, for example, when learning the first layer of neural networks, for which L can be very large. Moreover, æ (O, then ||~||| ②(vd) with high probability; that is, (3.2) is linear in R2 2 2(vd) but ours only scales with vlog which can make significant difference especially in the overparameterrzed regime. We should note that compared to our bound, (3.2) does not require the smoothness
For specific application of Theorem 3.1, consider the multi-class support vector machines, i.e. for y = [K] and p : [-RR,, RRR] - [0, B] L-Lipschitz and ( 8-smooth, the objective given as
K |10 1|2.
f(0: 2) max p (00 -0.x0 + v'
j=1
7

---

Theorem 3.1 provides a generalization bound of ((VK/n) that improves the existing bounds which scale at least linearly with K and/or vd [Zha04, DSBDSSI5, LDBK15, LDZK19]; see e.g. [LDZK19, Sec 2.1] for similar related results.
3.2 K-means clustering
We can also provide generalization error bounds for the problem of K K-mmans clustering in both hard and soft label setups. As before, we consider SGD an optimizer which has been the focus of many works in this context [BB94, Scu10, TM17J. We assume throughout this section that the samples are supported on a bounded domain, and the SGD iterations are applied without projection.
Generalization properties of K-means clustering has been studied for decades [Ant05, Lev 13, TTJCI5, TM16]. While most existing bounds are at least linear in K, [LL21] recently provided an improved bound in the hard label setup, which is of order (K log" n/n)) m//n1// 1/2 for bounded inputs. However, state-of-the-art bounds in the soft label setup were still linear in K. Below, we establish a bound of order / K log n/n in the soft label setup, which is the first bound that is sublinear in K. We further improve the bounds of [LL21] in the hard label setup, but by logarithmic factor.
Soft K- means clustering. While the hard K-means clustering assigns exactly one cluster to each point using one-hot encoding, the soft K K-means clustering allows soft labels within the probability simplex. Specifically, given Ç >> 0 and the samples 2i..... 2n. the soft K -means clustering algorithm alternates between updating the soft labels (w, (2;; ()); of 2, for all i [rd], and estimating the cluster centers
(0,) (B) K using the classical update rule [Mac03]
exp(-<110; z: 12)
> - Wy (z;(
wy (2c 0)
(3.3)
E exp( - z4 12))
Σ (y((2;))
Here, this procedure is equivalent special case of expectation-maxxiizallln algorithm, which converges to a local minimum of the following objective (see Appendix C.2 for details)
K
-()== F()) =
- Σ [(0:z)= = log Σ exp ( <110; - 2: 13))]
(3.4)
j=1
Instead of running the standard alternating procedure (3.3), we directly minimize (3.4) using SGD and derive generalization bounds for the soft K-means clustering by approximating the objective (3.4) with piecewise strongly convex and smooth functions. The proof is presented in Appendix C.3.
Theorem 3.2. For B = 4(R + 1)2 and for any E (0, Ke- let V1
Ane-CB An²
K
L:= 4R CB T == max VK
Log (3L
... and P == poly(1, S, B, K, R, n, B) Then, with
(1/(1
probability at least for any ((0)
E 10,12 1 T. and i,,..., it [n], have
BT +1 + B ' Tlog(nPK) PK) + log(2/5)
F(O())) - F(B(t))
<
2n
The above generalization bound scales with VK, which improves the previously known bound Ō(K/ for clustering with soft labels [LL21]. Theorem 3.2 also implies ((vK/ K/n) bound under R. O and 17 = ((K), which coincides with the best known rate in the hard label setup. Here, the choice of 17 ((K) may look odd; however,
indeed practical since the derivative of the objective function scales with 1/K, i.e. [10f(0; =)/00,1| < 4Re /K.
Hard K-means clustering. Under the same setup as before, we minimize the objective function
1 Σ [(0:)) min 10, jE(K] ==11²]
F()) =
(3.5)
Note that (3.5) coincides with the soft K -mmans objective (3.4) as Ç oa if 0, 241l * 10, 2; for all j. A. Since [0; 2) = min |0, - 21| may not be differentiable, we use an auxiliary gradient at a non-differeetiable 0, i.e. for a randomly or deterministically chosen S S arg minje[k] 110, =|12,
00, 2(022) = 0
i 22 =) ifj
8

---

For example, one may choose single cluster index (|S]=1) The following result characterizes the generalization of hard K K-means clustering trained by SGD using this auxiliary gradient. Its proof is deferred to Appendix C.4.
= 1) and compute the corresponding gradient.
Theorem 3.3. For any n E (0, let 4R², 7 == |1 2n/. T= max {
log(16 (tn))) log(I/>)
.0
Then, given (10) E O the following bound holds with probability at least - for any t 2 0 and ",..,,, 2 [n]] we have
F(O())) - F(B(t)) BKT +1 + BV
KT (oTlo2(2) + log(2/0)
2n
We note that under 77, R= and (n), Theorem 3.3 provides O (K log² n. (22 general- ization bound which improves the bound given by [LL21], but this time by a logarithmic factor.
Discussions
Beyond (piecewise) strong convexity and smoothness. The localized covering construction utilized is essentially based on the (piecewise) contractivity of SGD updates for (piecewise) strongly convex and smooth functions. However, local strong convexity is by no means necessary and this analysis can be extended to a broader class of objective functions.
Consider, for example, objective function f that is uniformly convex [DN21] and has Hölder continuous gradient [5e Then, for any & > O, there exists a step size 1) > 0 and T = Te such that applying 7' synchronously coupled SGD updates on any two points makes the distance between them smaller than E. Consequently, an analog of Lemma 2.1 can be established under this setup as well, for properly chosen 7. T' We highlight that this class of functions is already covered in our framework via Proposition 2.1; however, an analysis based on the actual curvature (as opposed to a piecewise approximation) of the objective may provide tighter generalization bounds.
Extension to SGD without projection. Projection operation is only needed to ensure that the SGD iterates stay bounded. Indeed, the projection is not needed in the presence of explicit regularization, or under a dissipativity--ype condition on the objective [RRT17, EMS18, YBVE21, EH21J. J. For example, if f();2) is Lipschitz continuous, it is straightforward exercise to show that SGD iterations are bounded the presence of Ez-regularization and bounded initialization.
Extension to mini-batch setup and different sampling schemes. The results we presented can be easily extended to the mini-batch setting. To see this, note that the localization is based on the (piecewise) contractivity of single iteration of the algorithm, and we have that if all 91..... are contractive, then an average of their subset is also contractive. Moreover, our generalization bounds hold for any sampling scheme, e.g. sampling without replacement, random shuffling, data- dependent sampling, since the covering construction is based on an E-cover the union of all possible trajectories of SGD, which is independent of the underlying sampling scheme.
Extension to contractive stochastic optimization methods. In this paper, our main focus was the SGD algorithm and its generalization properties. However, it is straightforward to adapt our framework general stochastic optimization setup. For example, the next result follows from the identical steps leading to Theorem 2.2; hence, its proof is omitted.
Definition 3. An "iterative stochastic algorithm" " using g O Z O performs the update 0(0) 9t, (0(t-1)) == g(0(t-1); 21,) at ileration I, for a random sample in E [n]]
Definition 4. - θ is "piecewise 7-contractive with P pieces O" if there exists partition , Pp of O and --contractivv hi....,ll .pp on O such that = ltp on for all p E [P]. c (0), and an iterative stochastic
Theorem 4.1. Suppose that Assumptions I & hold, algorithu g is given. Suppose further that there exists h e x 2 - θ such that for any E Z, h( +()) (22+ is piecewise cycontraeetvve with P pieces on θ satisfying
[gg(0; 2) h((0; x)ll S
for all 0 E O. Choose T E N. Then with probability at least 1 5, for any ((0) 2 T, and
21, E [m], we have
BT
T Tlog(nP) + 12g()
1 1- 1-17 7T
(((00)) F(0(0)) <
+ B
+ 2L
7 TR+
1 1- 5)
2n

---

We note that concurrent work by [KWS22] requires global contractivity and their bounds are in expectation, whereas Theorem 4.1 is a high-probie segh-rrbbbbiityy statement which only requires piecewise contractivity as stated in Definition 4.
Linitation of results. We outline few limitations of our current analysis. In this paper, we only considered the generalization error (also referred to as the generalization gap), and our main result in the non-convex regime cannot be easily translated step would require a bound on the optimization error: nevertheless, establishing such bounds in the non-convex regime highly non-trivial. is worth highlighting that without assuming convexity, algorithmic stability-based bounds also suffer from this limitation [HRS15, FV19, BKZ20J.
bound on the excess risk. This additional
Because of the shared contractivity parameter y across different iterations and pieces, method cannot be easily extended to varying step size. This is indeed a limitation of our analysis as varying step size schedules oftentimes used in practice. We leave this extension a future work.
Acknowledgments
SP was supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2019-0-00079, Artificial Intelligence Grad- uate School Program, Korea University) and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2022R F1 A A00761 (0).. US was funded part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' d'avenir" program, reference ANR- ANR-19-P3IA 19--199-31A-001 (PRAIRIE 31A Institute), and the European Research Council Starting Grant DYNASTY 101039676. MAE was supported by NSERC Grant [2019-06167], CIFAR AI Chairs program, and CIFAR AI Catalyst grant.
References
[AKL21]
Idan Amir, Tomer Koren, and Roi Livni, SGD Generalizes Better Than GD (And Regularization Doesn't Help), Conference on Learning Theory, 2021.
[Ant05]
András Antos, Improved Minimax Bounds on the Test and Training Distortion of Empirically Designed Vector Quantizers, IEEE Transactions Information Theory (2005).
[BB94]
Leon Bottou and Yoshua Bengio, Convergence Properties of the K-Means Algorithms, Advances in Neural Information Processing Systems, 1994.
[BE02]
Olivier Bousquet and André Elisseeff, Stability and Generalization, Journal of Machine Learning Research (2002).
[BFGT20]
Racf Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar, Stability of stochastic gradient descent on nonsmooth convex losses, Advances in Neural Information Processing Systems, 2020.
[BK720]
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy, Sharper Bounds for Uniformly Stable Algorithms, Conference Learning Theory, 2020.
[CDE*21] Alexander Camuto, George Deligiannidis, Murat A. Erdogdu, Mert Gürhüzhalaban, Umut Simşekli, and Lingjiong Zhu, Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms, Advances in Neural Information Processing Systems, 2021.
[CMR13]
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh, Multi-Class Classification with Maximum Margin Multiple Kernel, International Conference on Machine Learning, 2013.
[DDB20]
Aymeric Dieuleveut, Alain Durmus, and Francis Bach, Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains, The Annals of Statistics (2020).
[DN21]
Nikita Doikov and Yurii Nesterov, Minimizing uniformly convex functions cubic regularization of newton method, Journal Optimization Theory and Applications (2021).
[DSBDSSI5] Amit Daniely, Sivan Sabato. Shai Ben-David, and Shai Shalev-Shwartz, Multiclass Learnability and the ERM Principle, Journal of Machine Leamingg Research (2015).
[EH21]
Murat A Erdogdu and Rasa Hosseinzadeh, On the convergence of langevin monte carlo: The interplay between tail growth and smoothness, Conference on Learning Theory, PMLR, 2021, pp. 1776-1822 1822.
10

---

[EMS18]
Murat A Erdogdu. Lester Mackey, and Ohad Shamir, Global non-convex optimization with discretized diffusions, Advances in Neural Information Processing Systems 31 (2018).
[Fal14]
Kenneth Falconer, Fractal geometry: mathematical foundations and applications, Wiley, 2014.
[Fel16]
Vitaly Feldman, Generulization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back, Advances in Neural Information Processing Systems (2016).
[FO21]
Farzan Farnia and Asuman Ozdaglar, Train simultaneously, generalize better: Stability of gradient- pradient-bused minimax learners, International Conference on Machine Learning. 2021.
[FV19]
Vitaly Feldman and Jan Vondrak, High probability generalization bounds for uniformly stable algorithms with nearly optimal rate, Conference on Learning Theory, 2019.
[Gue02]
Yann Guermeur, Combining Discriminant Models with New Multi-Clat SVMs, Pattern Analysis & Applications (2002).
[Hoe63]
Wassily Hoeffding, Probubility Inequalities for Sums of Bounded Random Variables, Journal of American Statistical Association (1963).
[HRS15]
Moritz Hardt, Benjamin Recht, and Yoram Singer, Train faster, generalize better: Stability of (2015).
stochastic gradient descent, arXiv preprint arXiv:1509.0
[JKZ 12]
Robert Jenssen, Marius Kloft, Alexander Zien, Sören Sonnenburg, and Klaus-Rober Müller, Scatter-Bass Prototype Framework and Multi Class Extension Support Vector Machines, PloS one (2012).
[KWS22]
Leo Kozachkov, Patrick M. Wensing, and Jean-Jacques Slotine, Generulization in Supervised Learning Through Riemannian Contraction, arXiv preprint arXiv:2201 ,06656 (2022).
[LDBK15]
Yunwen Lei, Urän Dogan, Alexander Binder, and Marius Kloft, Multi-class SVMs: From Tighter Data- DetenDepnndent Gemeralization Bounds to Novel Algorithms, Advances in Neural Information Processing Systems, 2015.
[LDZK19]
Yunwen Lei, Urün Dogan, Ding-Xuan Zhou, and Marius Kloft, Data--ependent generalization bounds for multi-class classification, IEEE Transactions on Information Theory (2019).
[Lev13]
Clément Levrard, Fast rates for empirical vector quantization, Electronic Journal of Statistics (2013).
[LL21]
Shaojie Li and Yong Liu, Sharper Generalization Bounds for Clustering, International Conference on Machine Learning, 2021.
[LLQ20]
Jian Li, Xuanyuan Luo, and Mingda Qiao, On Generalization Error Bounds Noixy Grudient Methods for Con-Coovex Learning, International Conference on Learning Representations, 2020.
[LLY21]
Yunwen Lei, Mingrui Liu, and Yiming Ying, Generalization Guarantee of SGD for Pairwise Learning, International Conference on Artificial Intelligence and Statistics, 2021.
[Lon17]
Ben London, A PAC-Bayesian analysis of rundomized learning with application to stochastic gradient descent, Advances Neural Information Processing Systems (2017).
[LY20]
Yunwen and Yiming Ying, Fine-Grained Analysis of Stability and Generalization for Stochas- tic Gradient Descent, International Conference on Machine Learning, 2020.
[Mac03]
David J.C. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge Univer- sity Press, 2003.
[Mil19]
Tristan Milne, Piecewise Strong Convexity of Neural Networks, Advances in Neural Information Processing Systems, 2019.
[Nes15]
Yu Nesterov, Universal gradient methods for corvex optimization problems, Mathematical Programming (2015).
[PLYS21]
Sejun Park, Jacho Lec, Chulhee Yun, and Jinwoo Shin, Provable Memorization via Deep Neural Networks using Sub-lineur Parameters, Conference on Learning Theory, 2021.
[Pri12]
Simon J.D. Prince, Computer vision: models, learning, and inference, Cambridge University Press, 2012.

---

[RRTI7]
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky, Non-convex learning via Stochastic Grudient Langevin Dynamics: nonaxymptotic analysis, Conference Learning Theory. 2017.
[Scu10]
David Sculley, Web-Scale K-Means Clustering, International Conference World Wide Web, 2010.
[SHN' 18]
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro, The Implicit Biax of Gradient Descent on Separable Data, The Journal of Machine Learning Research (2018).
[SSBD14] Shai Shalev-Shwarzz and Shai Ben-David, Understanding Machine Learning: From Theory Algorithms. Cambridge university press, 2014.
[$SDE20] Umut Şimşekli, Oran Sener, George Deligiannidis, and Murat A. Erdogdu, Hausdorff Dimension, Heavy Tails, and Generalization Neural Networks, Advances Neural Information Processing Systems, 2020.
[SSSSS09]
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan, Stochastic Convex Optimization, Conference on Learning Theory, 2009.
[TM16]
Cheng Tang and Claire Monteleoni, Lloyd's Algoritim:: New Theoretical Insights for Cluster- ing in Practice, Interaatoonal Conference on Artificial Intelligence and Statistics, 2016.
[TM17]
Convergence Rate of Stochastic k-means, International Conference on Artificial Intelli- gence and Statistics, 2017.
[TICCIS]
Matthew Thorpe, Florian Theil, Adam M Johansen, and Neil Cade, Convergence the k-Means Minimization Problem using I-Convergence, SIAM Journal on Applied Mathematics (2015).
[Ver18]
Roman Vershynin, High-dimensional probability: An introduction with applications in data science, Cambridge University Press, 2018.
[YBVE21]
Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A. Erdogdu, Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias, Advances in Neural Information Processing Systems, 2021.
[YKM21]
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi, A Unifying View on Implicit Bias in Training Linear Neural Networks, International Conference on Learning Representations, 2021.
21]
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals, Understanding deep learning (still) requires rethinking gemeralization, Communications of the ACM (2021).
[Zha04]
Tong Zhang, Statistical Analysis of Some Multi- Multi-Category Large Margin Classification Methods, Journal of Machine Learning Research (2004).
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This paper
only contains theoretical results on the generalization properties of SGD.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "tnPY6bQ9aqN", "reviewer": "Reviewer_PjwR", "summary": "The paper studies the generalization gap for objectives that are optimized\nvia stochastic gradient descent (SGD). By leveraging the fact that SGD\nupdates are contractive when all component objective functions are strongly\nconvex, the authors are able to apply an $\\epsilon$-covering argument that\nremoves the dependence of d in the generalization gap for many\nsituations. Moreover, by arguing that any smooth, bounded non-convex\nfunction is within an $\\epsilon$ (in the $L^{\\infty}$ norm) of piecewise strongly\nconvex functions, they are able to generalize their argument to a larger\nshare of non-convex objectives. Namely, they are able to demonstrate an\nimprovement in the generalization gap in the class of multi-index models and\nK-means with hard label assignment.", "questions": "[Q1] Are the best known bounds stated for K-means (soft and hard) and\nmulti-index models that were beat in this paper for the tail probabilities\nor for the average SGD iterates?\n\n[Q2] Is there any general theory describing when a smooth function can be\nrepresented in the form of described in Proposition 2.1 with very few\npiecewise components?", "limitations": "No, the authors have not addressed the societal impact if their work is misconstrued or incorrect.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I found this to be a well-written and well thought out paper.\n\n[Originality]\n\nStrengths:\nThe core of the paper seems to rely on two different insights:\n+ The set of all possible SGD iterates at step T form an $\\epsilon$-covering for\n  all future SGD iterates with an appropriately chosen T\n+ Any smooth, bounded non-convex function can be arbitrarily close to a set of\n  piecewise smooth strongly convex functions (with the number of required\n  functions possibly but not always growing exponentially in the ambient dimension d).\n\nArmed with these two observations, the authors are able to argue an upper\nbound on the generalization gap that does not necessarily rely on the\ndimension. The combination of these two ideas permits the authors to\ndemonstrate an improvement in some common ML models (K-means and\nmulti-index models).\n\nWeaknesses:\nThe paper mentioned that there was some previous inspiration based on\nunderstanding the Hausdorff dimension of an SGD iterate chain, so in that\nsense, the paper had some previous related ideas. However, I found this\nconnection to build more understanding rather than diminish the work done in\nthis paper.\n\n[Quality]\n\nStrengths:\nWhile the theoretical framework in Theorem 2.1 and 2.2 are of independently\nof interest, the application of these theorems to some real models is\npowerful. This demonstrates that this perspective of using an\nalgorithmic-dependent stability can provide some benefit on top of general\nmethods that only consider the objective function and not the optimization\nroutine.\n\nWeaknesses:\nI do not have any notable complaints with the work presented.\n\n\n[Clarity]\n\nStrengths:\nThe paper was very clear and easy to follow (with a couple exceptions, see\ndetailed comments below).\n\nWeaknesses:\nNA\n\n[Significance]\n\nStrengths:\nThe generalization gap is a widely studied object in modern day ML. The\ntechniques used here could spark other ideas on how to use computational\ngeometry to better understand the nature of SGD in deep learning.\n\nWeaknesses:\nI could not tell from reading the paper whether the fact that these results\nwere upper bounds on the tail probabilities made this easier than the\nexpectation bounds mentioned in paper. I am not certain if this could be\ndrawn out a bit more, but it would be helpful for the reader to understand.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cLuvYvb5Nl", "reviewer": "Reviewer_pTmX", "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.  ", "questions": "--> Assumption 2: I do find the bounded deviation assumption to be quite strong. Is it possible to remove this assumption?\n\n--> 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?\n\n--> Line 213: \"multi-index linear models\" why is this type of models fundamentally different from \"single-index models\"?\n--> Equation (1.4): have authors considered the SGD with minibatch?\n\n--> In lemma 2.1, the authors have implicitly assumed the boundedness of the iteration sequence $\\theta^{(t)}$. Is this assumption reasonable?\n\n--> 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. \n\n--> Main concern: I am also surprised that there is no expectation involved in the statement of lemma 2.1.\n\n--> 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.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strength: the narrative in general flowing well and the paper has a clear structure\n\n- Weakness:\n\n--> Assumptions made in the paper are strong.\n\n--> Key lemma needs further explanation. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Yf3q8Mylv1o", "reviewer": "Reviewer_FYvm", "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.", "questions": "See above.", "limitations": "Limitations and possible extensions are sufficiently assessed in the discussion section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wxhtb5qqlj", "reviewer": "Reviewer_2vrF", "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$. \nUnder 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.\nThe 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).\nYet they showcase on several learning paradigms that they can improve this worst case bound and surpass state-of-the-art bounds.", "questions": "See Weaknesses. \n", "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)$. ", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea of studying only the parameter space under the action of SGD is super natural and elegant. \n- 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.\n- 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).\n- In Section 3, the authors do a good job at convincing that their results can improve generalization bounds in many ML settings.\n- 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].\n\nWeaknesses:\n- 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). \n- (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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-U9oCj9MVRR", "reviewer": "Reviewer_4jdi", "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.\n", "questions": "I think it would be great to expand the derivation of the second term in the second line of Equation (B.3)\n", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept