Characterization of Excess Risk for Locally Strongly Convex Population Risk
Authors: Mingyang Yi
Ruoyu Wang
Zhi-Ming Ma
Venue: NeurIPS 2022 Accept (2022)
Keywords: Excess risk
Algorithmic stability
Loss Landscape

Abstract: We establish upper bounds for the expected excess risk of models trained by proper iterative algorithms which approximate the local minima. Unlike the results built upon the strong globally strongly convexity or global growth conditions e.g., PL-inequality, we only require the population risk to be \emph{locally} strongly convex around its local minima. Concretely, our bound under convex problems is of order $\tilde{\mathcal{O}}(1/n)$. For non-convex problems with $d$ model parameters such that $d/n$ is smaller than a threshold independent of $n$, the order of $\tilde{\mathcal{O}}(1/n)$ can be maintained if the empirical risk has no spurious local minima with high probability. Moreover, the bound for non-convex problem becomes $\tilde{\mathcal{O}}(1/\sqrt{n})$ without such assumption. Our results are derived via algorithmic stability and characterization of the empirical risk's landscape. Compared with the existing algorithmic stability based results, our bounds are dimensional insensitive and without restrictions on the algorithm's implementation, learning rate, and the number of iterations. Our bounds underscore that with locally strongly convex population risk, the models trained by any proper iterative algorithm can generalize well, even for non-convex problems, and $d$ is large.

Characterization of Excess Risk for Locally Strongly Convex Population Risk
Mingyang 12,.2,3, Ruoyu Wang" .2, Zhi-Ming Ma 1.2
University of Chinese Academy of Sciences
Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Huawei Noah's Ark L.b (yimingyang17, wangruoyu17)Smatll wwuucas.... .dda..edu... cn mazm@amt ac. en
Abstract
We establish upper bounds for the expected excess risk of models trained by proper iterative algorithms which approximate the local minima. Unlike the results built upon the strong globally strongly convexity or global growth conditions e.g., Pl-inequality, we only require the population risk to be locally strongly convex around its local minima. Concretely, our bound under convex problems is order (1/n). For non-convex problems with model parameters such that d/n is smaller than a threshold independent n, the order of (1/nn) can be maintained if the empirical risk has no spurious local minima with high probability. Moreover, the bound for non-convex problem becomes (1)/Vn) without such assumption. Our results are derived via algorithmic stability and characterization of the empirical risk's landscape. Compared with the existing algorithmic stability based results, our bounds are dimensional insensitive and without restrictions on the algorithm's 's implementation, learning rate, and the number of iterations. Our bounds underscore that with locally strongly convex population risk, the models trained by any proper iterative algorithm can generalize well, even for non-convex problems, and d is large.
Introduction
The core problem in machine learning is obtaining model that generalizes well unseen test data. The excess risk decides the model's performance on these unseen data, and it can be decomposed into optimization and generalization errors. The tool of algorithmic stability [9] [0] has been proven to be a suitable tool for exploring the excess risk. Roughly speaking, the output a stable algorithm robust a slight change in the algorithm's input, i.e., training
The output of stable algorithm has been proved to have controlled excess risk in [9], and the result has been further developed under some specific algorithms However, these results have some limitations. The results in [79] 14 50 47 are obtained under the
332 79
14
T6
50 20 e.g., stochastic gradient descent [6]] (SGD).
assumption of either global strong convexity or global growth conditions (PL-inequality (42)). On the other hand, the results in [32] 20 are only applicable to specific algorithm, i.c., SGD, and their
bounds of generalization error diverge across training which is inconsistent with the observation that
"train longer, generalize better" [4
To improve these, provide unified analysis of the expected excess risk for generic class of iterative algorithms without any strong global conditions, i.e., global strong convexity or global
growth conditions in (79 14 50 Concretely, substitute the strong global conditions with weaker
equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

local strong convexity (see Section of population risk around its local minima. The substitution is based on the fact that the nice strong convexity property can be locally (though not globally) satisfied by many important problems, e.g., PCA 30 ICA 27 and matrix completion [28]. We derive our results via algorithmic stability and characterize the empirical risk's landscape. For both convex and non-convex problems, our results can be applied to any proper algorithms that approximate local minima. Moreover, our generalization upper bounds do not diverge with the number of training steps.
Technically, we upper bound both generalization and optimization errors to control the excess risk. We first show a fact that the locally strongly convexity around the local minima of population risk (population local minima) can be generalized to the local minima of empirical risk (empirical local minima), and the empirical local minima would concentrate around population local minima. Then for convex problems, we establish the generalization upper bound of the iterates of any proper algorithm via algorithmic stability by leveraging the facts of iterates will converge to empirical local minima, which concentrate around population local minima. For non-convex problems, our generalization error analysis includes three steps. 1) By applying similar arguments under the convex problem, we upper bound the generalization error of those empirical local minima around population local minima. 2) Then, we prove that, with high probability, there are no extra empirical local minima except for those concentrated around population local minima with guaranteed generalization capability. 3) Finally, we extrapolate the upper bound of the generalization error to the iterates obtained by the proper algorithm as they converge empirical local minima.
After controlling the generalization error, the excess risk is directly implied by characterizing the optimization error. By the proved local strong convexity of empirical risk and the convergence results
of proper algorithms, the optimization error can be controlled as in [2 29 27 37].
Concretely, establish upper bound of order ((1/n) (Ö(+) defined in Section 2 for the expected excess risk of iterates obtained by any proper algorithm under convex problems. Here ni is the number of training samples. For non-convex problems with parameters of model, we establish an upper bound of order Ó(1/vn + exp(-n(c2 - d/n)) where c1 is a constant independent of and d. Noticeably, the exponential term in the bound can be ignored when d/n S C1, then our bound becomes ((1 The bound can be applied to high-dimension in the same order of n. The result significantly improves the classical one of order ((vd/n) (63) which has polynomial dependence on d. Moreover, our bound of order ((1/VT) can be improved to (1/n)) if the empirical risk has no spurious local minima with high probability, which can be satisfied for many important non-convex problems 33 28 D.
problems such that d is
Our upper bounds to the excess risk underscore that, for both convex and non-convex problems satisfying our regularity conditions, the model trained by an algorithm can generalize on test data even when d is large. Our improvements over existing classical results are summarized follows.
For convex problems, our bound improves the standard upper bound of the expected excess risk in the order of (VIIn)) 32) to ((1nn), under an extra locally strongly convex assumption.
For non-convex problems, we relax the dimensioonalldependenncc in the standard excess risk bound of order ((vd/n) 63), under local strong convexity assumption.
In contrast to the existing algorithmic stability based works 32 79 14,
our results can be applied
to any algorithms that approximate local minima without restrictions on the implementation of algorithms, learning rate, and the number of iterations.
2 Preliminaries
2.1 Notations and Assumptions
In this subsection, we collect our (mostly standard) notations and assumptions. We use || to denote fz-norm for vectors and spectral norm for matrices. (, is ball with radius around w RdC. Let dataset { znn 21, 2zn} be 2n iid samples from unknown distribution, and S {21,'.. ... _n) ) is the training set, S (21,... Z;-1, 2/2, 2i+1, ... .,, and S' = ! Throughout this paper, we assume without further mention that the loss function f(w, is differentiable w.r.t. to parameter w for any 2, 0 < f(w, x) < M, and the parameter space W C R

---

is convex compact set. Thus 1| W2 < D for w1, w2 E W and some positive constant D. The population risk is R(w) (f =)] and its empirical counterpart on the training set S is (s) = n- E ===1/ [(w, 2.). Let w's E arg min Rs(w) and w* E arg min R(wr), The projection operator (w(()) is defined as Pwr = arg wiw {ller - -=]]]- During our analysis, the order of sample size can go to infinity, and d can diverge to infinity with n. But we assume the other quantities are universal constant independent of n. The symbol (--) is the order of a number, factor in the number of model parameters d. The following two assumptions on loss function f(w, x) are imposed on the population risk.
while (.) hides a
Assumption 1 (Smoothness). For 0 S j S 2, each z and any w1. w2 E W. V f(w1,z)) - V f(w2, z) f(w2,)) L, - wzll,,
(1)
where V fi, 2) are respectively loss function, gradient, and Hessian at w for j = 0, 1,2. Assumption 2 (Non-Degenerate Local Minima). For wfcaa the set of local minima of population risk R(w),, V (R = x > 0, i.e. V ()((io)))) XL is
definite matrix.
Assumption T says that the loss function should be smooth enough, which a mild assumption and has been adopted in 32 81 (30. Assumption aad together imply that the population risk is locally strongly convex around its local minima. The rationale behind the imposed local strong convexity is as
follows. Though the strong global conditions (e.g.. global strong convexity) in 33 79
14
16 50 20)
do not hold in many problems, the weaker locally strongly convex condition can be satisfied by
many important problems, e.g., generalized linear regression [49], robust regression [4]. PCA [30),
ICA (27]. and matrix completion (28]. The detailed examples of import problems that satisfy the assumptions imposed in this paper in Appendix F
2.2 Stability and Generalization
Definition 1 (Proper Algorithm). The algorithm is proper if it approximates local minima of empirical risk (s
This is rough definition of the discussed proper algorithm. The sense in which algorithms approxi- mate local minima will be made clear in our formal theoretical results. Let A(S) be the parameters obtained by an algorithm A, e.g. SGD, on the training set S. The performance data is determined by the excess risk R(A(S)) between the current model and the optimal one. In this paper, we explore the expected excess risk EA.s|R(A(ST)) inf R( [[w)] where EA means the expectation is taken over the randomized algorithm A and the training set S. We may neglect the subscript if there is no obfuscation. Since Rs(w3s) S Rs(w"). we have the following decomposition.
model on unseen inf R(w).. which is the gap of population risk
(A.s(R(A(S)) R(w"" }] = a. (R(A(S)) Rs [] S EAS (R((S))(((S)) Rs(w's)]
T.A. (A(() Rs(ws)] + EA.s[R((A(S Rs(A(S))
(2)
< EAs (A(S)) Rs(w))) EA.s (((((S) - (s()))
Eapt
Egen
The expected excess risk is upper bounded by the sum of optimization error Eapt and generalization error Egen. Eopt decided by the convergence rate of the algorithm A eтror Egen can be controlled by algorithmic stability [9] as follows.
I2
29 The generalization
Definition 2. An algorithm AA is c-uniformly stable, if
Estab
E.s.s sup (Alf(((S)) x) f(A(S")) =)] Se,
(3)
where S and S' are defined at the beginning of Section 2.1
The e-uniformly stable is different from the one in (32, which does not take expectation over training
sets S and S The next theorem shows that the uniform stability implies the expected generalization of the model, i.e., Egen S Cstab- The idea of Theorem is similar the ones in 9 14. and its proof is in Appendix
2 Pleease notice that local minima all global minima for convex problem.
3

---

Theorem 1. If A is e-uniformly stable, then
Egn |EA.s [R(A(S)) Hs(A(S)) S.
(4)
Please note that all the analysis in this paper is applicable to the practically infeasible empirical risk minimization "algorithm" such that A(S) w's. However, to make our results more practical, we suppose A as iterative algorithms in the sequel. For any given iterative algorithm A, let wi and w/ denote the output of the algorithm when A is iterated t steps on the training set S and S' respectively.
3 Excess Risk under Convex Problems
In this section, propose upper bounds of the expected excess risk for convex problems. We impose the following convexity assumption throughout this section.
Assumption 3 (Convexity). For each z and any w1, W2 W, [(w, z) satisfies
( x) S (Wi, x), w1 W2).
(5)
3.1 Generalization Error under Convex Problems
As we have discussed, in the existing literature 32 79
16
50 20,, researchers have explored the
excess risk via the algorithmic stability to control the error generalization. However, the obtained generalization upper bounds of order ((1/n) 32
14 50) are built upon the strong assumptions of either global strong convexity or global growth conditions, e.g., Pl.-inequality [42]. On the other hand, the generalization upper bounds in [32 20 are only applied to SGD, and they diverge as the number of iterations grows. For example, Theorem 3.8 in [22 establishes an upper bound 2L3 =k T to the algorithmic stability of SGD with learning rate 7kk which diverges when t + c0, as the convergence of SGD requires kk= 1h = oo [ Thus the bound can not explain the
79
observation that the generalization error of SGD trained model converges to a constant [8 34].
To mitigate the drawbacks in the existing literature, we propose the following new upper bound of algorithmic stability (Theorem 2 Our bound can applied on the top of any proper algo- rithm defined in Definition [ and it remains small for an arbitrary number of iterations as long as the sample size n is large. Under convexity Assumption 3 the proper algorithm means that E [Rs (s(w"s) - 0 as + cc. Our theorem is based on the following intuition. Due to the locally strongly convex property discussed after Assumption 2 there exists (with high probability) the unique global minimum w'g of Rs(()) and w's. of Rsy (-) that concentrate around the unique (the uniqueness from Assumption
[ population global minimum w². Then, the provable convergence results of w, w's and w/ s. imply the algorithmic stability (see Lemma in Appendix).
Theorem 2. Under Assumption
3
(t) 4V2Lo(A 4DL2)
Ve(t)=
8Lu
Lo
GALELED 23
128Lo nd2
(5
4e 4e df Vn
nd
= =O(ve(() + 1/n).
(6)
where (stab(t) = Es,s' |sup_ () x]]l| the stability of wa and e(t)
E. [Rg(w.)) Rs(w's), w's is the global minimum of Rs(().
The proof of this theorem is in Appendix B. The expected generalization error of w, is upper bounded by the right hand side of (6) due to Theorem I Compared with the existing result (32), the extra term related to ve(() in our bound originates from our proof technique, and it seems to be unavoidable according (63). Since for proper algorithms, e.g., GD and SGD, e(t) + 0 as oo the leading term of the upper bound (6) is C* log d/n Ō(1n) with C* 32
In summary, the local strong convexity (Assumption 2 enables us to establish an algorithmic stability based generalization bound (6. The bound improves the classical result of SGD 2L3 Ei=1 na/n n in 32 as it can be applied to any proper algorithm with any learning rate and number of iterations.
3.2
Excess Risk Under Convex Problems
According to (2) we can upper bound the expected excess risk by combining the generalization upper bound (6) with the convergence results in convex optimization.

---

Theorem 3. For w's E min Rs(w), and w E arg min,, R(w), under Assumption 7
[[((w:) - R((w")))))))))) S <0)) + 4V2Lo(A 4DL2)
8L0
ne (Lo
G4L0L3D
Ve(l) +
A
23
128LoLiD
(5/logd+ +
4e log
(7)
+
nd²
Vn
o(ve((t)+ + 1/m),
where <(t) = [Rs(w)) Rs(w")))
This theorem provides an upper bound the expected excess risk. The bound decreases with the number training steps t, and is of order (1//n) if is sufficiently large.
Comparison. Under the extra local strong convexity assumption, our result significantly improves the bound of order ((1/v/) ) in [32]. On the other hand, our bound matches (in order) the result under strongly convex problem [63 81]. It seems our result has a worse dependence on the strong convex parameter X, i.e., from //A to 1/A4. The worse dependence is acceptable as local strong convexity weaker than strong convexity. Moreover, our bound is not necessarily weaker compared to the current results [63 81 under global strongly convex problem. This is because À in our bound the local strongly convex parameter restricted around the minimum point, which is larger than the global one over the whole parameter space appears in [81]. Improving the dependence on À without sacrificing the order of seems to be infeasible based on our technique might be a meaningful topic to be explored in the future. Finally, our result has no conflict with the lower bound for general convex problem in the order of O(v O(yd/n) [25] This is because Assumption | and 2
restrict our result to smaller class distributions and functions, which rules out the counter-examples [25].
To make our results concrete, we apply them to GD and SGD as examples. Note that Rs(w) Di= f(w,z( 2;), the GD and SGD respectively start from wy follow the update rules of
We41 = Pw (wi - n V Rs(w:)),
(8)
and
Wi+1 = Pw (w: ff., #.)))
(9)
where is is randomly sampled from Note the convergence of w; updated by GD and SGD respectively ((1/t) [12] and ( /F) [64], we have the following two corollaries declare the
converged expected excess risks whose proofs appear in Appendix
Corollary 1. Under Assumption if w: is updated by GD in
8 with = L/L,, then
R ((w)) R(w")= =O 1 + 1
(10)
n
Corollary 2. Under Assumption
with Tu DD(LIv(+1) then if ww is updated by SGD in 9
E (((m)) R(w")) δ
(11)
ti
Excess Risk Under Non-Convex Problems
In this section, we present the upper bounds of the expected excess risk of iterates obtained by proper algorithms that approximate local minima under non-convex problems.
4.1 Generalization Error Under Non-Convex Problems
In this subsection, we study the generalization error under non-convex problems. Unfortunately. the analysis in Section B can not be directly generalized here due to the following reason. The generalization error under convex problems relies on the fact that there exists the unique empirical local minima w's of Rs(-) and w of (.)(.) that concentrate around the unique population local minimum un of R(.). Under non-convex problems, there can be many empirical and population
The dependence can be improved 1/x² with worse order of (from 1/n 1/y1).
5

---

local minima. The iterates obtained on S and S' may converge to different empirical local minima away from each other, which invalidates our methods used in convex problems.
Fortunately, we can prove that for each population local minimum, there is an empirical local minimum concentrated around it with high probability. If the generalization upper bound for these local minima is established, and there are no extra empirical local minima, the convergence results of the iterates obtained by proper algorithms imply their generalization ability. Next, we prove our results following this road map.
First, we establish the generalization upper bound for the empirical local minima around the popula- tion local minima. According to Proposition] in the Appendix [.I] there are only finite population local minima, thus the non-convex problems with local minima consists of manifold [48] is not considered in this paper. Let M = [wi
uik] } be the set of population local minima. The number of local minima K may depend the problem of interest. In many important non-convex problems, K can be quite small, e.g., K = 2 for PCA 30) and = 1 for robust regression 449
Then, we notice that the population risk is strongly convex in B2 2/(42))) Similar to the scenario under convex problems, we can verify that the empirical risk is locally strongly convex in B2 By (A/4L)) with high probability. Next, we consider the following points
arg mig Rs(w),
(12)
WEB2(Wi 1in
is a local minimum of Rs(-) with high probability and present for 1: = 1..., K. We show that w & the generalization bound of it. Note that in Theorem D A can be infeasible. We construct an auxiliary sequence w, via an infeasible algorithm.
1 ( L1
w++1 = P P
w0
(13)
Then, as w, locates in Bg (w 2/L22) in which (s(-) is strongly convex with high probability, we can establish the algorithmic stability bound of the wp. Combining this with the convergence result of w, wss, implies the generalization ability of w The following lemma states our result rigorously.
Lemma 1. Under Assumption aaadd 4 for k = =I...., ".....,,, K, with probability at least
512L
128L2
5 1ool +
4e delogo d
(14)
nx4
na2
Vn
w's s.s a local minimum of R.).). Moreover, for such w's we have
8Lo
64 x
3A
[ss [Hs(ws,ss) - H(W3s,))] S
Lo +
min
3D,
nd
2L2
(15)
128 nx²
log d' vn
3A
15vlog d
min
3D,
2Lg
The lemma is proved Appendix C.I.I and guarantees the generalization ability of those empirical local minima located around population local minima. The expected generalization error on these local minima is of order (1/n)) as in convex problems. In the sequel, we show that there are no extra empirical local minima expected for these w's, with high probability, under the following mild assumption, which also appears in (49 30
Assumption 4 (Strict saddle). There exists a, A > O such that [[V > a on the boundary of W, and
[R(w)]] |I o Tmii (V (V"((w)) 2 A, where miin 2 (((ww) is R2 's smallest eigenvalue.
(16)
The Assumption 4 is generalized version of local strong convexity Assumption 2 (can be implied by Assumption 4p. vast vary of machine learning problems satisfy this assumption, e.g., generalized linear regression, robust regression, normal mixture model, tensor decomposition, matrix completion,
PCA, and ICA 30 49 8TI.
We refer readers to 30 27 49 for more details of this assumption.
Let Mg = {w w is local minimum of Rs(+)) be the set consists of all the local minima of empirical risk (.).). Then we establish the following non-asymptotic probability bound.
'Please note the definition of u in 12 which is not necessary be local minimum.

---

Lemma 2. Under Assumption
and for
min
8122
16ba f
a²
with probability least
3D
na
3D
nd²
1 1
exp
"128L8
4d
exp
128
(17)
512LBL3
128L2
4e log d'
2 }
K
5y log d
nd4
vna
we have
i: Ms = (w......... w.s.k
i:: for any w E W, if [Rs(w)Il < (2/() and Rs((w > -X/2, then 1|
PMs(w)) < AlVRs(w)ll
where V (w)) > 2/2 means V Rs((w) a/2I is positive definite matrix.
The first conclusion in this lemma states that there no extra empirical local minima except for those W's.& concentrate around population local minima, which have guaranteed generalization ability (by Theorem
D The second result is that the empirical risk is "error bound" (see 42 for its definition) around its local minima, with high probability. The "error bound" is a nice property in optimization [42]. Proof of the lemma is in Appendix C.2.1] The probability bound (17) will appear in the generalization bound of iterates obtained by proper algorithms accounting for the existence of those empirical local minima away from population local minima. We defer the discussion to the bound after providing our generalization upper bound in Theorem
We move forward to derive the generalization upper bound of those iterates obtained by the proper algorithm that approximates the local minima under non-convex problems. Under strict saddle Assumption// 4 the proper algorithm A approximates the second-order stationary point (SOSP) that says with probability least 1 (& is constant that can be arbitrary small),
[V & (()), Rss)) ž -p(t)
(18)
where w; is updated by the algorithm A, and p(t).p(t) - (which may have poly-logarithmic dependence on 5 (37]) as - cc.
To instantiate such proper algorithms, construct algorithm that satisfies 18) in Appendix D
The following theorem establishes a generalization upper bound of we obtained by such A.
Theorem 4. Under Assumption 7 andd 4 ifw; satisfies
(18) and defined in Lemma 2 by choosing
t such that ((t) < a² (2La) and p(t) x we have
SLo
2KM
8KL3
|BA.s [R(w:)- Rs(w)))
<(t) DL Vn
X
nd
Lo min 3D, 2L2
2M
En11 2M
(19)
(c(t)+ +
1
(d/n S O(1)),
vn
where
1,,1 K
512L
128L nd²
5 dd
logo d' vn
(20)
nd4
and
(3D exp
na
3D d
nd²
En,
128L1
+4d
exp
1281;
(21)
If with probability at least then
8' (8' can be arbitrary small), Rs(.))
has no spurious local minimum,
8Lp
8(K 4)L8
[ASS [R(w.)) Rs(wr))
((t) + 2T
-6M8' +
A
nd
(K + Lo
3A
+
min
3D,
+ 6M
En,1 + 6M
(22)
K
2La
δ (c(1) 1)
(d/n < 0()))
" is (e, sccon-orrd stationary point (SOSP) if ([))) and v Rsssw 2 -7
7

---

This theorem is proved in Appendix C3
and it provides upper bounds of the expected generalization error of iterates obtained by any proper algorithm that approximates SOSP. We present an explanation of each term in it follows. The T. is of order (11 n)) ( (m) as we take the corresponded 5 = 1/vn or 1/n, and (Lo((t) / can be arbitrary small we take sufficiently large Since E,,1 of order (11/n), we next explore En.2- The leading term in En,2 is
4d
3D
exp
12813
Td²
= exp log 4d d doo
3D
128L.
RA
(23)
If d is large enough to make log 4d I d dlog(3D/r), then En.2 S exp(-c2n(e - =)),, where Thus En,2 Õ(1 provided by d/n e1- In this case, the 2KM/ v appears in bound (19) implies it is of order O(1/Vn), even under nigh-dimensional problems such that d is in the same order of n. The K can be small here for many non-convex problems, as previously discussed. Moreover, the bound (22) improves the result in (19) to (1/m)), under the condition of empirical risk has no spurious local minima with high probability (i.e. 8' - Ó(1/n)). The condition has been proven to be satisfied by many important non-convex optimization problems e.g., PCA 30 matrix completion 28 and over-parameterized neural network 43 21
c X2 X2/(256T, log(3//r) and 02 2
Comparison. Under the extra strictly saddle Assumption 4 our bounds (no matter whether im-
posing the no spurious local minima assumption) improve the classical results of order O d/n)
based on the uniform convergence theory [63] or the one of order O( /n) for positive e [32 79
based on algorithmic stability. (30) get the result of order Ö'd/n n)) under the same Assumptions
[ imposed in this paper. However, their bound has linear dependence on d, thus can not be non-vacuous like ours when is in the same order of n.
we can extrapolate Theorem f to sitrahigh-dimensione problem such that > n. For example, suppose the parameter space W is contained in a 4 i.c., ||w W2ll S D' for some positive D'. Note that the covering number (defined in (72) of polytopes (Corollary 0.0.4 in (7T) is much smaller than that of bzlbll.. Then, applying the similar proof of Theorem establishes the same upper bound of generalization error w.r.t. up with En, in Theorem replaced by
Specifically, if the parameter space satisfies some sparsity conditions 6 80 35
36
++++1 (2 exp (-
na (-12813) 2(2d) /n (2
nda 12813
< Ô <.))))
2(2
exp
(24)
where the much smaller relationship is valid as long as log(d)/ - + 0.
4.2 Excess Risk Under Non-Convex Problems
In this subsection, we establish upper bounds for the expected excess risk of iterates obtained by proper algorithms under non-convex problems. In contrast to convex optimization, the proper algorithm under non-convex problems is not guaranteed to find the global minimum, as it only approximates SOSP. Hence the optimization error may not vanish in Theorem The following theorem proved in Appendix C.4 establishes an upper bound of the expected excess risk.
Theorem 5. Under Assumption 7 and 4 if ww satisfies 18 by choosing <(I) < (22(())) and p(t) < X/2, we have
18 such that
EAss [R(w.) R(w")) < 1Lo <(t) + L.D8 2KM
A
Vni
8KL
Lo min { 3D, 2L2
3\
+ 2M
En,1 + +2MEn.2
nd
+ EAss (P (w:))
His (wss)
((1) (((()) 1)
RAs (w.)) Rs(mn))]
(d/n s 0(1))
(25)
8

---

where w" is the global minimum of the population risk. If with probability at least 1 8' (8' can be arbitrary small), Rs(()) has no spurious local minimum, then
4L0 c(1) + L8 + 8M8' + 8(K + +4)L
EA [R(w.)- I((ww))) -
nd
(K L)To
31
K min 3D, 2L2 /
+ 8M
Eu,3 + 8M
(26)
Ô (c(1) h)
(d/n S 0(1))
where Su.1 and En,2 are defined in Theorem 4 and w's is the global minimum of Rs(-).
From the discussions in the last section, the bound (25) and (26) become ((1/v)) and Ó(1/n). respectively, when d is in the same order of n and L - Do. Besides that, in (25). expected for the order of convergence rate (c((t) and the generalization bound order Õ(1 (1/// n ho1/vn+tnn
-iii-d//na d)))) there is an extra AA, S R& (PMs (we) - Rs w3s)] in the bound (25) compared with the result of convex problems in Theorem 3 This is the gap between the empirical global minimum and the algorithmic approximated empirical local minimum. The gap seems necessary the proper algorithm is not guaranteed to find the global minima, and if so, the gap becomes zero.
The bound (26) of order (1/nn) is obtained under empirical risk without spurious local minima, which is proven to be hold on many important non-convex problems c.g., PCA [30), matrix completion 28). and over aver-parameterized neural network 43
85
Related Works
Generalization The generalization error is the gap between the model's performance training and unseen test data. One the central tools to bound the generalization error in statistical learning uniform convergence theory. However, this method is unavoidably related to the capacity of hypothesis space e.g., ., VC dimension [7 [59 31], Rademacher complexity [1) covering
number 73
82 65,, or entropy integral (72). Thus, these results not well suited for high-
dimensional hypothesis spaces, which makes the mentioned measures to be large.
The generalization eиror of the iterates obtained by some algorithms, c.g., GD SGD, is often of more interest. There are plenty of papers working on this topic via the tool of algorithmic stability 22
30 63], differential privacy [18 41, robustness of model [75] 66 [77), and information However, these tools either depend heavily on algorithm implementation (algorithmic stability and information theory) require unverifiable conditions (robustness and differential privacy). This paper combines the technique of characterizing empirical loss landscape and algorithmic stability to explore the generalization under both convex and non-convex problems. Our methods develop a new way to use algorithmic stability, which can be applied without restrictions on the algorithm, learning rate, and the number of iterations.
10,
theory
74
67 11.
Optimization Results in this paper are related to both convex and non-convex problems.
For convex problems, 12 summarizes most of the classical algorithms in convex optimization. Some (6) with lower computational complexity have also been extensively explored. Recently, the non-convex optimization has attracted quite a lot attentions owing to the development of deep learning 33 [70]. But most of the existing algorithms 29
other novel methods 40 62,
57
15
23 78
approximate the first-order stationary point instead of local minima.
Under non-convex problem, the algorithm that approximates SOSP is proper (approximate local minima) in this paper. We refer readers for recent progress in the topic of developing algorithms approximating SOSP to [27] [19 37 39 76 52 84 (3). The discussed proper algorithms in this
paper have constrained parameter space which is different from the ones in [5] 13 [52 To resolve
this, we also develop an algorithm that approximates SOSP under our constraints in Appendix
'The difference in the coefficients of the convergence rate term ((t) between the bounds in Theorem and due to technique issue and not essential.

---

Excess Risk A straightforward way to characterize the excess risk is by controlling the general- ization and optimization errors, respectively, as we did in this paper. Thus, for this problem, the used tools are similar to the ones in analyzing generalization, e.g., uniform convergence theory
20), information theory [53] [4]. However, the discussed drawbacks of these tools also appeared. Our results are built upon the combination of
[69] 88 25 algorithmic stability [32
14
16
79
characterizing empirical risk's s landscape and algorithmic stability, Moreover, they are dimensional insensitive, independent of algorithm's 's implementation, and they improve the order of existing results under both convex and non-convex problems.
Conclusion
This paper provides a unified analysis of the expected excess risk of models trained by proper algorithms under convex and non-convex problems. Our primary techniques are algorithmic stability and the non-asymptotic characterization of the empirical risk's landscape.
Under the conditions of local strong convexity around population local minima and some other mild regularity conditions, we establish the upper bounds of the expected excess risk in the order of O (1/n) and O(1/Vn) (can be improved to ((L/n) when empirical risk has spurious local minima with high probability) under convex and non-convex problems respectively.
The presented results improve the existing results in many aspects. For convex problems, our results improve the standard excess risk bound of order O ((/1/n) 332 to (11/n) under locally convex assumption. For non-convex problems, our results significantly improve the standard uniform convergence bound in the order of ((vd/n) [63 when d/n is smaller than universal constant. Moreover, our results can be generally applied to algorithms that approximate local minima, and they have no restrictions on the algorithm, learning rate, and number of iterations.
10

---

References
[1] Z. Allen-Zhu, Y. Li. and Z. Song. A convergence theory for deep learning via over- parameterization. In International Conference Machine Learning. 2019.
[2] S. Arora, Z. Li, and K. Lyu. Theoretical analysis of auto rate-tuning by batch normalization. In International Conference on Learning Representations, 2018.
[3] L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results, Journal of Machine Learning Research, 3(11))463-422, 2002.
[4] P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: a statistical viewpoint. Preprint arXiv:2103.09177 2021.
[5] W. Bian, X. Chen, and Y. Ye. Complexity analysis of interior point algorithms for non-lipschitz and nonconvex minimization. Mathematical Programming. 149(1-2):3013327,
[6] P. J. Bickel, Y. Ritov, A. B. Tsybakov, et al. Simultaneous analysis of lasso and dantzig selector. The Annuls of Statistics,
2009.
[7] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension, Journal of the ACM, 36(4):929-965, 1989.
[8] L.. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311 2018.
[9] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Muchine Learning Research, 2(3):499-526, 2002.
[10] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, 2020.
[11] Y. Bu, S. Zou, and V. Veeravalli. Tightening mutual information- bounds on generaliza- tion error. IEEE Journal on Selected Areas in Information Theory, 1(1):121-130, 2020.
[12] S. Bubeck. Convex optimization: Algorithms and complexity. Preprint arXiv: 1405.4980, 2014.
[13] C. Cartis, N. I. Gould, and P. I.. Toint. Second-order optimality and beyond: Characterization and evaluation complexity in convexly constrained nonlinear optimization. Foundations of Computational Mathematics, 18(3):103311077, 2018.
[14] 7. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, 2018
[15] X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of class adam-type algorithms for non-convex optimization. In International Conference Learning Representations, 201 8.
[16] Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms. Preprint arXiv: 1804.01619, 2018
[17] V. Cherkassky, X. Shao, F. M. Mulier, and N. Vapnik. Model complexity control for regression using VC generalization bounds. IEEE Transactions on Neural Networks, 1075) 1999.
[18) D. Cynthia, Vitaly, H. Moritz, P. Toniann, R. Omer, and R. Aaron. A new analysis of differential privacy's 's generalization guarantees. In ACM Symposium on Theory of Computing, 2015.
[19] H. Daneshmand, Kohler, A. Lucchi, and T. Hofmann. Escaping saddles with stochastic gradients. In International Conference Machine Learning, 2018.
[20] Z. Deng, H. He, and W. Su. Toward better generalization bounds with locally elastic stability. Preprint arXiv:2010.11 13988, 2020.
[21] S. Du, D. Lee, Li, I.. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, 2019.

---

[22] J. Fan, Q. Li, and Y. Wang. Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions. Journal of the Royal Statistical Society. Series B, Statistical methodology, 79(1):247, 2017.
[23] C. Fang, J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic aatt-interrated differential estimator. estimaato Advances in Neural Information Processing Systems, 2018.
[24] C. Fang, Z. Lin, and T. Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, 2019.
[25] V. Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, 2016.
[26] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference Learning Theory, 2019.
[27] R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points-onling stochastic gradient for tensor decomposition. In Conference on Learning Theory, 2015.
[28] R. Ge, J. D. Lee, and T. Ma. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems, 2016.
[29] S. Ghadimi and G. Lan. Stochastic first-and programming. SIAM Journal on Optimization, 23(4):2341 22368, 2013.
methods for nonconvex stochastic
[30] A. Gonen and S. Shalev-Shwartz. Fast rates for empirical risk minimization of strict saddle problems. In Conference on Learning Theory, 2017. 2017.
[31] I. Guyon, B. E. Boser, and V. Vapnik. Automatic capacity tuning of very large ve-dimension classifiers. In Advances in Neural Information Processing Systems, 1993.
[32] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, 2016.
[33] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition, 2016.
[34] E. Hoffer, I. Hubara, and D. Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Advances in Neural Information Processing Systems, 2017.
[35] A. Javanmard and A. Montanari. Confidence intervals and hypothesis testing for high- dimensional regression. Journal of Machine Learning Research, 15(1):2869-2099 2014.
[36] A. Javanmard, A. Montanari, et al. Debiasing the lasso: Optimal sample size for gaussian designs. The Annals of Statistics, 46(6A):2593-2622 2018.
[37] C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, 2017.
[38] C. Jin, L. T. Liu, R. Ge, and M. I. Jordan. On the local minima of the empirical risk. In Advances in Neural Information Processing Systems, 2018.
[39] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. Stochastic gradient descent escapes saddle points efficiently. Preprint arXiv: 1902.0490..048) 1902.04811 2019.
[40] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, 2013.
[41] C. Jung and K. Ligett. A new analysis of differential privacy's generalization guarantees. In Innovations in Theoretical Computer Science, 2020.
[42] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the and Knowledge Discovery in Databases, 2016.
condition. In European Conference on Machine Learning
12

---

[43] K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, 2016.
[44] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[45] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.
[46] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1 (0(11)):27823333 1998.
[47] S. Li and Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. International Conference on Machine Learning, 2022.
[48] C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
[49] S. Mei, Y. Bai, and A. Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statisties, 46(6A):2747-2774, 2018.
[50] Q. Meng. Y. Wang, W. Chen, T. Wang, Z.-M. Ma, and T.-Y. Liu. Generalization error bounds for optimization algorithms via stability. In Association for the Advancement of Artificial Intelligence, 2017.
[51] M. Mohri and Rostamizadeh. Rademacher complexity bounds for non-iid processes. In Advances in Neural Information Processing Systems, 2009.
[52] A. Mokhtari, A. Ozdaglar, and A. Jadbabaie. Escaping saddle points in constrained optimization. In Advances in Neural Information Processing Systems, 2018.
[53] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. Information -theoretccc generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 2019.
[54] G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theorrtic generalization bounds for stochastic gradient descent. In Conference on Learning Theory, 2021.
[55] B. Neyshabur, Z. Li, S. Bhojanapalli, Y. LeCun, and N. Srebro. The role of vvrrparraettiizatoon in generalization of neural networks. In International Conference on Learning Representations, 2018.
[56) I.. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáë. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, 2017.
[57] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. Stochastic recursive gradient algorithm for nonconvex optimization. Preprint
2017.
[58] Nocedal and Wright. Numerical optimization. Springer Science & Business Media, 2006.
[59] M. Opper. Learning and generalization in a two-layer neural network: The role of the vapnik- chervonvenkis dimension. Physical Review Letters, 72(13):2113, 1994.
[60] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al. Scikit-learn Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[61] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[62] N. L. Roux, M. Schmidt, and F. Bach. A stochastic gradient method with exponential convergence _rate for finite training sets. Advances Neural Information Processing Systems, 2012.
13

---

[63] S. Shwtar-S O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In Conference on Learning Theory, 2009.
[64] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning. 2013.
[65] Shawe-Taylor and R. C. Williamson. Generalization performance of classifiers in terms of observed covering numbers. In European Conference on Computational Learning Theory, 1999.
[66] A. Sinha, H. Namkoong, J.d Duchi, Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
[67] T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual informa- tion. In Conference on Learning Theory, 2020.
[68] T. Tieleman and G. Hinton. Lecture 6.S-rmpprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31 31, 2012.
[69] V. Vapnik. The nature of statistical learning theory. Springer science business media, 1999.
[70] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
[71] R. Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[72] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[73] R. C. Williamson, A. J. Smola, and B. Scholkopf. Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators. IEEE Transactions on Information Theory, 47(6):2516-2533 2001.
[74] A. Xu and M. Raginsky. Information cheeorttion-thooretii analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 2017.
[75] H. Xu and S. Mannor. Robustness and generalization. Machine learning, 86(3):391-423, 2012.
[76] Y. Xu, R. Jin, and T. Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. In Advances in Neural Information Processing Systems, 2018.
[77] M. Yi, L. Hou, J. Sun, L. Shang, X. Jiang, Q. Liu, and Z.-M. Ma. Improved ood generalization via adversarial training and pre-training In International Conference on Machine Learning. 2021.
[78] M. Yi, Q. Meng, W. Chen, and Z.-M. Ma. Towards accelerating training of batch normalization: manifold perspective. Preprint arXiv:2101 102916, 2021.
[79] Z. Yuan, Y. Yan, R. Jin, and T. Yang. Stagewise training accelerates convergence of testing error over sgd. In Advances in Neural Information Processing Systems, 2019.
[80] C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statisties, 38(2):894 942, 2010.
[81] L. Zhang. T. Yang, and R. Jin. Empirical risk minimization for stochastic convex optimization: (11n))-and O(t/n")-type of risk bounds. In Conference Learning Theory, 2017.
[82] Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(3):527-550, 2002.
14

---

[83] Y. Zhang, J. C. Duchi, and M. J. Wainwright. Communication eefficientteiitniiteeee algorithms for statistical optimization. The Journal of Machine Learning Research, 14(1):3321 2013.
[84] Y. Zhang, P. Liang, and M. Charikar, hitting time analysis stochastic gradient langevin dynamics, In Conference on Learning Theory, 2017.
[85] D. Zou, Y. Cao, D. Zhou, and Q. Gu. Gradient descent optimizes wer-paramettrizze deep relu networks. Machine Learning, 109())4467-49) 2020.
15

---

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? [Yes] There is no potential negative societal impacts of this paper.
(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] See Appendix.
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 as URL)? [Yes]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/]]
16


Reviews:
[{"review_id": "oY0aOkMBEvv", "reviewer": "Reviewer_7m5U", "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})$.", "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).\n\n- 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.\n\n- 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?\n\n- 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.\n\n- line 70, 71: this sentence seems broken, please consider rewriting.\n\n- line 87, 88: this sentence seems broken, please consider rewriting.\n\n- line 110: what is random in $\\inf_w R(w)$? Why does expectation involve this term?\n\n- 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?\n\n- Isn't Theorem 2 supposed to hold with high probability? Is this statement correct?\n\n- 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?\n\n- Paragraph starting with line 168: What happens when global strong convexity holds? Does this paper recover the existing best-known dependence?\n\n- 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.\n\n- 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?\n\n- line 232, 233: please provide clear examples and clearly show why they satisfy the assumptions made in the paper.\n\n- 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?", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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?\n\n\nClarity: 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.", "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": "Weu27XQIGT", "reviewer": "Reviewer_HJpT", "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)$.", "questions": "My major questions and suggestions are in the weakness part, below are some additional comments:\n\n1. The authors mentioned it is hard to improve their worse dependence on $\\lambda$. Could they explain intuitively why it is hard?\n2. 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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The theoretical results look rigorous and sound. Their results improve existing ones in several aspects.\n2. The authors also clearly show how their theorems are proved with good intuition.\n3. The analysis looks novel to me.\n\nWeaknesses:\n1. 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.\n2. 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$.\n3. 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.", "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": "D0dTOGuw4VJ", "reviewer": "Reviewer_MRcT", "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.", "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.\n \n2. Why the paper adopts a new definition for the uniformly stable (Def 2)? \n\n3. 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?\n\n4. 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? \n\n5. 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.\n\n\n\n\n\n### Minor Comments\n1. Line 212, add a bracket for lambda / 4L_2.\n2. Line 176, the sentence seems to be incomplete. \n3. 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.\n4. 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. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe main contribution of the paper is a new roadmap to analyze the generalization bounds for stochastic optimization. \n1. The obtained generalization bound is dimension insensitive (improving the generalization bounds derived from uniform convergence arguments).\n2.  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). \n3. 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. \n\n## Weaknesses\n\nSee questions below.", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "4iZiyc2OND", "reviewer": "Reviewer_GY9U", "summary": "This paper proposes upper bounds of the expected excess risk of locally strongly convex losses, removing global growth conditions.\nSpecifically, this paper bounds the generalization error and the optimization error to get better risk bounds.\nFor 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.\nFor non-convex problems, this paper shows that for each population local minimum, there is an empirical local\nminimum 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.", "questions": "Please see the weaknesses part.", "limitations": "As I can see, this paper has no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Merits:\n1. This paper generalizes previous global growth conditions to locally strongly convexity, which extends the application scenarios.\n2. Under convex condition, the result given in this paper is better than [Hardt et al., 2016; Shamir and Zhang, 2009; Zhang et al., 2017].\n3. Under non-convex condition, this paper proves that with high probability, there is an empirical local\nminimum concentrated around each population local minimum, and the excess risk given in this paper is better than [Shamir and Zhang, 2009].\n\nCons:\n1. 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.\n2. 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.\n3. 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).", "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