Exponential Generalization Bounds with Near-Optimal Rates for $L_q$-Stable Algorithms
Authors: Xiaotong Yuan
Ping Li
Venue: ICLR 2023 poster (2023)
Keywords: $L_q$-stability
Uniform stability
Moments inequality
Exponential generalization bound
Excess risk
Sparsity

Abstract: The \emph{stability} of learning algorithms to changes in the training sample has been actively studied as a powerful proxy for reasoning about generalization. Recently, exponential  generalization and excess risk bounds with near-optimal rates have been obtained under the stringent and distribution-free notion of uniform stability~\citep{bousquet2020sharper,klochkov2021stability}. In the meanwhile, under the notion of $L_q$-stability, which is weaker and distribution dependent, exponential generalization bounds are also available yet so far only with sub-optimal rates. Therefore, a fundamental question we would like to address in this paper is whether it is possible to derive near-optimal exponential generalization bounds for $L_q$-stable learning algorithms. As the core contribution of the present work, we give an affirmative answer to this question by developing strict analogues of the near-optimal generalization and risk bounds of uniformly stable algorithms for $L_q$-stable algorithms. Further, we demonstrate the power of our improved $L_q$-stability and generalization theory by applying it to derive strong sparse excess risk bounds, under mild conditions, for computationally tractable sparsity estimation algorithms such as Iterative Hard Thresholding (IHT).

Published as a conference paper at ICLR 2023
EXPONENTIAL GENERALIZATION BOUNDS WITH NEAR-OPTIMAL RATES FOR - -TABLE ALGORITHMS
Xiao-Tong Yuan
Ping Li Linkedln Ads 700 Bellevue Way NE, Bellevue, WA 98004, USA pinlis minl@iinkedin...
School of Intelligence Science and Technology Nanjing University, Suzhou, 215163, China xtyuan1 980 com
ABSTRACT
The stability of learning algorithms to changes in the training sample has been actively studied as a powerful proxy for reasoning about generalization. Recently, exponential generalization and excess risk bounds with near-optimal rates have been obtained under the stringent and distribution-free notion of uniform stabil- ity (Bousquet et al., 2020; Klochkov & Zhivotovskiy, 2021). In the meanwhile, under the notion of -,t-abbilyty, which is weaker and distribution dependent, ex- ponential generalization bounds are also available yet so far only with sub-optimal rates. Therefore, a fundamental question we would like address in this paper is whether it is possible to derive near-optimal exponential generalization bounds for sty-le learning algorithms. As the core contribution of the present work, we give an affirmative answer to this question by developing strict analogues of the near-optimal generalization and risk bounds of uniformly stable algorithms for -table algorithms. Further, we demonstrate the power of our improved Ly- stability and generalization theory by applying it to derive strong sparse excess risk bounds, under mild conditions, for computationally tractable sparsity estima- tion algorithms such as Iterative Hard Thresholding (IHT).
INTRODUCTION
A fundamental issue in statistical learning is to bound the generalization error of a learning algorithm for understanding its prediction performance on unseen data. has long been recognized in literature that one of the key characteristics that permits learning algorithms to generalize is the stability of estimated model to perturbations in training data. The idea of using algorithmic stability as a proxy for generalization performance analysis dates back to the seventies (Rogers & Wagner, 1978; Devroye & Wagner, 1979). Since the seminal work of Bousquet & Elisseeff (2002), the search for generalization bounds under various notions of algorithmic stability has been flourishing area of learning theory (Zhang, 2003; Mukherjee et al., 2006; Shwartz et al., 2010; Kale et al., 2011; I; Hardt et al., 2016; Celisse & Guedj, 2016; Bousquet et al., 2020).
As one may expect, the stronger an algorithmic stability criterion is, the sharper the resulting gen- eralization bound will be. On one end, exponential generalization bounds can be guaranteed by approaches under the most stringent notion of uniform stability (Bousquet & Elisseeff, 2002: Bous- quet et al., 2020), which requires the change in the prediction loss to uniformly small regardless data distribution. Despite the strength of generalization, the distribution-fre nature makes uni- form stability too restrictive be fulfilled, e.g., by learning rules with unbounded losses (Celisse & Guedj, 2016). On the other end, based on some weaker and distribution dependent notions of sta- bility such as hypothesis stability and mean-square stability, only polynomial generalization bounds seem possible in general cases, although the corresponding stability criteria are more amenable to verification (Bousquet & Elisseeff, 2002). These observations have prompted the development of sta-sbbillty,, as an in-between state, to achieve the best of two worlds (Celisse & Guedj, 2016; Abou- MooutMaa & Szepesvári, 2019): it generalizes the notion of hypothesis stability from -orm criterion to norm criterion for q 2 2 but remains distribution dependent and thus is weaker than uniform stability; in the meanwhile it can still achieve similar exponential generalization bounds to those of uniformly stable algorithms (Bousquet & Elisseeff, 2002).

---

Published as a conference paper at ICLR 2023
By far, the best known (and near-optimal) rates about exponential generalization bounds offered by approaches based on uniform stability and certain fine-grained concentration inequalities for sum of functions of independent random variables (Feldman & Vondrák, 2019; Bousquet et al., 2020).
These rates are substantially sharper than those of Bousquet & Elisseeff (2002), which are implied by naive application of McDiarmid's inequality, in terms of the overhead factors stability co- efficients. While it has long been known that the low probability of failure (over sample) can be handled via developing modified bounded-difference inequalities (Rakhlin al., 2005), it still re- mains less clear how to simply adapt these existing techniques to the more sophisticated frameworks of Feldman & Vondrák (2019); Bousquet et al. (2020) to obtain sharper exponential bounds. Partic- ularly for -table learning algorithms, the state-of-the-art exponential generalization bounds are derived based on the moments or exponential extensions of the Efron-Stein inequality (Celisse & Guedj, 2016; Abou-Moustafa & Szepesvári, 2019), which yield similar rates of convergence to those of Bousquet & Elissceff (2002) and thus are suspected to be sub-optimal.
Given the above observed gap in rates of convergence between the generalization bounds under uniform stability and Ly stabiiliy, the following question naturally raised:
Is it possible to derive sharper exponential generalization bounds for Stable learning algo- rithms that match those recent breakthrough results for uniformly stable algorithms?
As the core contribution of the present work, we give an affirmative answer to this open question by developing strict analogues of the near-optimal generalization bounds of uniformly stable algo- rithms for Ly Stable algorithms. The main results of our work confirm that the notion of Lt-sbability serves as neat yet powerful tool for extending those best-known generalization bounds broad class of non-uniformly stable algorithms. To illustrate the importance of our theory, we have applied the improved analysis of -tt-be algorithms to derive sharper exponential risk bounds for com- putationally tractable sparsity recovery estimators, such as the Iterative Hard Thresholding (IHT) algorithms widely used in high dimensional sparse learning (Blumensath & Davies, 2009; Foucart, 2011; Jain et al., 2014). This application also serves main motivation of our study.
Notation. Here we provide some notation that will be frequently used throughout the paper. Let S = {Z1, 2,...., ZN} } be set of independent random data samples valued in some measurable set 2. For any indices set I C [N] == (1...., N}. we denote by S = (Z, i E 1} and S7 = S 5)- 7 Tz 3 another i.i.d. sample from the same distribution
that of S and we write 5K3) [Z,,.., Zi-1, Zi Zi-1; ...y ZN}. For a real-valued random variable Y. its -orm for g 2 1 is defined by || = (1E (9)) By definition it can be verified that V/g 2 2.
We denote by S
|M (E| 2/4 = (E1))")//2) 2/9 = ||| 9/2
(1)
Let 9- NN R be some measurable function and consider the random variable g(S) ZN). For g(S) and any index set I S [N], we define the following abbreviations:
g(S,) = (S) St), (S))), = (B[ S/
We say a real-valued function f is G- Lipschittz continuous over the domain W
[f(ww f(w') s G/|l w'll. Vw, w e W.
For pair of functions f,g 0, we use f S g (or g 2 f) denote f S cg for some constant e 0. We denote by supp(w) the support of a vector us which is the index set of non-zero entries of w.
1.1 SETUP AND PRIOR RESULTS
Problem setup. We consider a statistical learning algorithm N + W that maps a training data set S to model A(S) in closed subset W of an Euclidean space. The population risk and corresponding empirical risk evaluated at A(S) are respectively given by
1 N
E ((((S)) R(A(S)) = Ez (=(((((();; 2)] and Rs(A(S)) = N
where é W x Z + R is neg-negative and potentially unbounded loss function whose value f(w;; 2) measures the loss evaluated at a with parameter w. As a classic fundamental issue in statis- tical learning, we are interested in deriving the upper bounds on the difference between population
2

---

Published as a conference paper at ICLR 2023
and empirical risks, i.., -s((()) which quantifies the generalization error of A. Let R := min R(w) be the optimal value of the population risk. We will also study how to upper bound R ((((S)) R (a.k.a. excess risk) which is of particular interest for understanding the population risk minimization performance of A.
We first introduce the concept of uniform stability (Bousquet & Elisseeff, 2002) which requires the change in the prediction loss to be uniformly small regardless the distribution of data.
Definition 1 (Uniform stability). learning algorithm A is said to have uniform stability with parameter % > 0 if it satisfies the following uniform bound:
sup
I((A(S); 2) ((A(((())))))))) 2)
Yuu ViE You
[N].
S,5t0,
Given that the loss function is almost surely bound by M, Bousquet & Elisseeff (2002) showed that a large class of regularized empirical risk minimization (ERM) algorithms has uniform stability, and using McDiarmid's inequality yields the following exponential tail generalization bound that holds with probability at least 1 å over the draw of S for any 5 E (0, 1):
1
log (1/6) +
(R(A(S) - Rs (A(S)) Tu
N log
MV
(2)
N
Recently, equipped with a strong concentration inequality for sums of random functions, Bousquet al. (2020) established the following moments bound of uniformly stable algorithms for all q 2:
[R(A(S)) - (s(A())) S oy (N + M
(3)
N
In view of the equivalence between tails and moments (see, e.g., Bousquet et al., 2020, Lemma 1), the above -n-no bound implies that for any 8 (0, 1), the following tail bound holds with probability at least 1 ö over the draw of S
2 + M
log (1/8)
R(A(S)) (s(())) & Ta (og(())og log
N
This bound substantially improves the classic result in Eq. (2) by reducing the overhead factor on sta- bility coefficient from O ((V N log(H)) (logg(N) (o) For example, in regimes such as reg- ularized ERM where 7o & VN usually the case, the convergence rate in Eq. (2) becomes vacuous as it is not vanishing in sample size, while the bound in Eq. (4) still guarantees O log(N)) log()) rate vN of convergence. Indeed, up logarithmic factors on sample size and tail bounds, the rate in Eq. (4) is nearly optimal in the sense of a lower bound on sums of random functions by Bousquet et al. (2020). The bound Eq. (4) can be extended to stochastic learning algorithms when the uniform stability (over data) holds with high probability over the internal randomness of algorithm (Feldman & Vondrák, 2019; Bassily et al., 2020). Under the generalized Bernstein condition (Koltchinskii, 2006) and based the sharp concentration inequality for sums of random functions by Bousquet al. (2020), Klochkov Zhivotovskiy (2021) alternatively established the following deviation op- timal excess risk bound that holds with probability at least 1 - over the draw of S:
(t)
(M + B) log(1/0)
R(A(S)) R S opp + E[A.p]] + Yu log(N) log
(5)
where Aapt = Rs(A(S)) min Rs(w) represents the empirical risk sub-optimality of the algorithm on training data, and B the Bernstein condition constant as defined in Assumption
While implying strong generalization guarantees, the uniform stability is also most stringent in the sense that is distribution independent and hard to be fulfilled, e.g., by learning rules with unbounded losses. To address such an unpleasant restrictiveness, the notion of -ta-biiillty was alternatively introduced by Celisse & Guedj (2016) relaxation of uniform stability.
Definition 2 (LaaStabilltty). For > 1, a learning algorithm A is said to have Ly -tasbiiiyyty with parameter 7/4 > if it satisfies the following moment bound:
((A(S); Z) ((A(S()) ) 7gg Vie [N].
3

---

Published as a conference paper at ICLR 2023
In the above definition, the expectation associated with Lg- is taken over S,S Z, and the internal random bits of A, if any (such as in the case of stochastic learning algorithms). Note that slightly different from that of Celisse & Guedj (2016), the random variable Z in the above definition is not necessarily required to be independent of S and S By definition, -saabilly is distribution dependent and thus is weaker than uniform stability which can be regarded as a special case of Ly- stability with 74 = Y for some y > O. Particularly for 9 1 and q 2, the Sta-bibillty reduces to the notions of hypothesis stability (Bousquet & Elisseeff, 2002) and mean-square stability (Kale al., 2011), respectively. For an instance, it has been shown that the classical ridge regression model with unbounded responses has -ttabiiiyy for all q 2 1 rather than uniform stability (Celisse will see shortly in Section 3 that Sta-sbbbyy
& Guedj. 2016). As novel and concrete example, plays a crucial role for deriving strong sparse excess risk bounds for sparsity estimation algorithms such as IHT (Jain et al., 2014; Yuan et al., 2018). Alternatively, the dcfinition of -tasbiily can be extended to the Ln-argument--sabiile concept of uniform argument stability (Bassily et al., 2020) to the I.g-norm criterion. Obviously Ly arauumee---tabbliit not at all relying on the random argument Z and it implies Stabbiiy for Lipschitz losses.
as [[])(S) - A(S())]ll,, I 7/. which generalizes the
The following is by far the best known moments generalization bound under Ltasbiiil that holds for all q 2 2 and potentially unbounded losses (Celisse & Guedj, 2016; Abou-Moustafa & Szepesvári, 2019):
[R(A())) (s(A())),,, & 74 N Q
(6)
As one can see that the stabiilty generalization bound in Eq. (6) is significantly inferior to the near-optimal uniform stability generalization bound in Eq. (3) in terms of the overhead on stability coefficient. Such a gap in rate of convergence is indeed unsurprising: the bound in Eq. (6) was de- rived via more or less directly applying moments or exponential extensions of Efron-Stein inequality to generalization error (Celisse & Guedj, 2016; Abou-Moustafa & Szepesvári, 2019), and thus yields about the same overhead factor on stability coefficient as that of the sub-optimal exponential bound in Eq. (2) for uniformly stable algorithms. In light of these observations, we are naturally motivated to derive sharper exponential generalization bounds for L, stable algorithms hopefully to match the near-optimal bound in Eq. (3) achievable by uniformly stable algorithms.
1.2 OUR CONTRIBUTION
The core contribution of the present work is a set of substantially improved exponential generaliza- tion bounds for Ltabbe algorithms. The key ingredient of our analysis is a sharper concentration bound on sums of functions of independent random variables under the Ly-norm bounded difference conditions, which generalizes previous counterpart under the uniform bounded difference condi- tions (Bousquet et al., 2020). With this generic concentration bound in hand, we are able to derive sharper generalization and excess risk bounds for Ttt-tt learning algorithms that match those best known for uniform stable algorithms. The power of our results is demonstrated through de- riving more appealing exponential sparse excess risk bounds for computationally tractable sparsity estimation algorithms (such as IHT). The main results obtained in this work are sketched below:
In Section 2, we first establish in Theorem 1 of random variables with Ly-norm bounded difference. Then equipped with such a general- purpose concentration inequality, we prove in Theorem the following nn-norm generaliza- tion bound for Lg -stable learning algorithms for all 2 2:
norm inequality for sums of functions
[[((AS)) - Rs (A()))) S 97g log N + M
N'
where M, is an upper bound of moments [I((A(S); 1) Compared to Eq. (6), the preceding bound improves the overhead factor on 7, from VN to log(N). As another consequence of our Ly-norm concentration inequality, we further derive in Theorem 3 the following excess risk bound for Ly stable algorithms under B -Brnstein-condittoon with M- losses (where
C M + B), or u-quadratic-gret growth condition with G-Lipschitz losses (where C' G²
[R(A(S)) - R² Appill l1g S app + 97g log(N) + Cq
N
4

---

Published as a conference paper at ICLR 2023
Based the equivalence between moments and tails, this above result implies identical deviation optimal risk bound in Eq. (5) for uniformly stable algorithms.
In Section 3, based on our StaSbiiiyyty generalization theory, we show in Theorem 4 novel exponential sparse excess risk bound for inexact Lo-estimators, A key insight here is that Lo- estimators are in many cases "almost always" stable over any fixed supporting set, and thus can be shown to have -ttsbibily over the same supporting set, which consequently makes our analysis techniques developed for Sttbbll algorithms applicable there. This novel appli- cation answers call by Celisse & Guedj (2016) for extending the range of applicability of the -ta-biibyl theory beyond the unbounded ridge regression problem, and complements other existing applications of the -tasbiiiy theory including k-nearest neighbor classification and k-folds cross-validation (Celisse & Mary-Huard, 2018; Abou-Moustafa Szepesvári, 2019). Last but not least, improved Lgg-tabiliiyy theory also be readily applied the above mentioned prior applications to obtain sharper generalization bounds.
SHARPER EXPONENTIAL BOUNDS FOR L -TTSBBBL ALGORITTM
2.1 A MOMENT INEQUALITY FOR SUMS OF RANDOM FUNCTIONS
We start by presenting in the following theorem moment inequality for sums of random functions of N independent random variables that satisfy the norn bounded difference condition. See Appendix B.I for its proof.
Theorem 1. Let S {Z,, Z2,..., ZN} ) be a set of independent random variables valued in Z. Let M1: ............................... 9N be a set of measurable functions gi ZN + IR that satisfy the following conditions for any E [N]:
E [g.(S)) S Z = O, almost surely;
(i( has the following Ly norm bounded difference property with respect to all variables in S exceptt Zr, ie., Vj for all q 2 1:
|(:(S) 2:(5(1))1 S Spp
Then there exists universal constant 1.271 such that for all q 2 2.
Σ (:) E(g((S) Zj]
4ng. [log N79g.
Additionally, if (S) 2ill, s Ma. then all 2 2
N
Σ (() s 22/2KNgM, + V N1...
Remark 1. Theorem 1 extends the moment inequality of Bousquet et al. (2020, Theorem 4) from under the distribution-free uniform bounded difference property to under the Lg-norm bounded difference property which is distribution dependent. Specially if 9i(S) have uniformly bounded difference property, then Theorem reduces to the result of Bousquet et al. (2020, Theorem 4).
Remark 2. The Lo-norm boundedness condition [[[]((() Zi]1, < Ma in our theorem allows gi to be potentially unbounded over domain of interest, which is weaker than the corresponding almost sure boundedness condition [B]g Z,]l as imposed by Bousquet et al. (2020, Theorem 4).
2.2
GENERALIZATION BOUNDS FOR - STABLE ALGORITHMS
As an important consequence of Theorem 1, we can derive er the following main result on the generalization bound of -table learning algorithms. See Appendix B.2 for proof of this result.
Theorem 2. Let A N + W be learning algorithm that has Lg -tabiilty by 74 f q 2 1. Suppose that [[(AA(S); 2)1,, & Mg for any Z E Z. Then for all 2 2,
(R(A(S)) - Rs Rs(A(S))11 S 97 log N + May N
5

---

Published as a conference paper at ICLR 2023
Remark 3.
The Lorm boundedness condition [[e(A(S); 2)1g Mg allows for learning with unbounded losses over, e.g., data distribution with Gaussian or sub-exponential tail bounds.
To compare with the best-known moments generalization bound in Eq. (6) under the notion of Lg- stability, our bound Theorem substantially improves the overhead factor on Yo from /N to lNg Specially when reduced to regime of uniform stability where % Yu for all q 2 1, our result revisits the moments generalization bound in Eq. (3) which nearly tight, up to logarithmic factors sample size, in the sense of lower bound
of random functions from Bousquet et al. (2020). More broadly, for any 8 E (0, 1), suppose that the following exponential stability bound holds with probability at least - with mixture of sub-Gaussian and sub-exponential tails over S,0(), Z:
(A(S)) ((A(()))))(( - a log (7) by log (g)
Then according to the equivalence of tails and moments, as summarized in Lemma 4 (see Ap- pendix A). we must have that A is -table by "g aq b.q. Assume that the loss is bounded in (0, M] almost surely over data. Then the Lg norm generalization bound in Theorem 2 combined with Lemma immediately implies the following generalization bound:
(7)+ + log (1/8) N
IR(A(S)) Rs(A(S))) S (o)g(o))oogg log?
blog(N)) log"
Compared with the uniform stability implied tail bound in Eq. (4), the preceding Lg -ttsaibility bound nearly identical up slightly worse confidence tail terms which are caused by the uncertainty of T.y Tyg-stability with respect to data distribution. We conjecture that such slight deterioration in tail bounds might possibly be remedied by using the exponential versions of Efron-Stein inequal- & Szepesvári, 2019) instead of the currently used vari- ant moments. We leave the improvement over poly-logarithmic terms for future investigation.
ity (Boucheron et al., 2003;
2.3 EXCESS RISK BOUNDS FOR L2g-TABBLE ALGORITHMS
In addition the generalization bounds, we further apply Theorem study the excess risk bounds of an -tablle learning algorithm which are of particular interest for understanding its population risk minimization performance. Let denote W Argmin R(w) as the optimal solution set of the population risk. In order to get sharper risk bounds, we need to impose some struc- tural conditions on risk functions. Particularly, the following defined generalized Bernstein condi- tion (Koltchinskii, 2006) is conventionally used with multiple global risk minimizers allowed.
Assumption (Generalized Bernstein condition). For some B > 0 aor any w E W, there exists w" W* such that the following holds:
E [[((w; 2) - E(w"; ;(w";2)) < B(R(w) R(w")).
We will also consider the quadratic growth condition which widely used as an alternative condition for establishing fast rates of convergence in learning theory.
Assumption 2 (Quadratic growth condition). For some μ > O and for any E W, there exists w" E W such that the following holds:
R(w) 2 R -lw f w w²112.
Remark 4. Clearly, when the loss is G-Lipschitz, the quadratic growth condition with parameter μ implies the Bernstein condition with parameter
The following theorem is our main result on the excess risk bound of stt-be algorithms, which extends the near-optimal exponential risk bounds of Klochkov & Zhivotovskiy (2021) from uniform stable algorithms to L. -table algorithms. A proof of this result can be found in Appendix B.3.
In exponential tail bound, the terms associated with v log (t) and log (+) are respectively referred sub-Gaussian and sub-exponential tails.

---

Published as a conference paper at ICLR 2023
Theorem 3. Ler A: I" H W be learning algorithm that has Ltasbiiil with parameter No for q 2
(a) If Assumption holds and (((;-) S M, then Vq 2,
[R(A(S)) Rd Appelly S SE ElAopi + 47a log(N) (M B)q
N
(b) If Assumption 2 holds and ((::)) is G-Lipschitz with respect to its first argument, then 4q 2 2,
G24
|| [R(A(S)) R - Dapele S o[Aop] + 97g log(N) + p.
Remark 5. Suppose that satisfies the exponential stability bound in Eq. (7), and thus has Lg stability by Yr aq by/q. Then combined with Lemma 4, the norn risk bounds Theorem suggest that the following exponential tail bound holds:
(t) + booo(()))))))))o
) log (1/6)
R(A(S)) - R - A opr + E [pp) + log(N))oo log?
Nog
N
In part (a), the M M--boundedllos condition is not essential and it can be relaxed to a sub- exponential (or sub-Gaussian) variant by alternatively using the general Bernstein-type inequalities for sums of independent sub-exponential random variables (Vershynin, 2018). Concerning part (b), under the quadratic growth condition, the loss allowed be unbounded Lipschitz continuous.
Remark
APPLICATION TO INEXACT LO-ERM
In this section, we demonstrate an application of our -tatbiiiy and generalization theory to the following problem of high nigh-dimensional stochastic risk minimization under hard sparsity constraint:
min R(w) == Ez (f(;; 2)] subject to ||w]|o S k, WEW
where W C Rdd the cardinality constraint |]w||| s for < is imposed for enhancing the interpretability and learnability of model situations where there clear favourite explanatory variables, or the model is over-parameterized. We consider the following Lo-ERM problem over training set S {Z, be(]]:
N l(w; Zi)
w arg min
= Rs(w):
(8)
N
Since the problem is known to be NP-hard (Natarajan, 1995) in general, it is computationally in- tractable to solve it exactly in general cases. Alternatively, we consider the incxact Lo-ERM oracle meta-algorithm outlined in Algorithm 1. In order to avoid assuming unrealistic conditions like restricted isometry property (RIP), it is typically needed to allow sparsity level relaxation for ap- proximate algorithms like IHT to achieve favorable converge behavior (Jain et al., 2014; Shen & Li, 2017; Yuan et al., 2018; Murata & Suzuki, 2018). Therefore, we are particularly interested in
Algorithm 1: Inexact Lo ERM Oracle
Input : A training data set S {Ziheen) and the desired sparsity level
Output: ü.Sk-
Compute an inexact k-sparse -R- estimation Ts.k such that
s..k is optimal over its support j supp(us..)). i.c., ūs, = arg min www.ww....www))) Rs(w);
ws.k attains certain le-paase sub-optimality level Ai.opt 2 for some Te such that Rs(W5,)) Rs(w5x) S Ar.

---

Published as a conference paper at ICLR 2023
the inexact Ly ERM oracle with h-sparse sub-optimality Kkopt 2 for some h I A such that the output & of Algorithm satisfies
(s(ūss)) - Rs(w3, S Koppr
typical that opt is a random value over the training set S. For example, the sub-optimality guarantees of IHT for empirical risk usually hold with high probability over training data (Jain et al., 2014). Let t == arg fil R(()) be the k-sparse minimizer of population risk for some k < k. We are interested in deriving exponential upper bounds for the k-sparse excess risk given by R(,s,,) R(we))
Our analysis also relies on the conditions of Restricted Strong Convexity (RSC) which extends the concept of strong convexity to the analysis of sparsity recovery methods (Bahmani al., 2013; Blumensath & Davies, 2009; Jain et al., 2014; Yuan et al., 2020).
Definition 3 (Restricted Strong Convexity). For any sparsity level 1 S d, we say function is restricted [ug-strongly convex if there exists some 24s > 0 such that
(ww) - (w') (V w') 2 ||w w'll,, A/[w w'llo S
2
Specially when we say f is p-strongly convex if is fa--trongly convex.
The following basic assumptions will be used in our theoretical analysis.
Assumption 3.
The loss function ((::-) is convex and G-Lipschitz with respect to its first argument.
Assumption 4. The population risk R is p-strongly convex and the empirical risk Rş is pa st--stongly convex with probability least by over sample S for some 6N E (0, 1).
Assumption 5. The domain of interest uniformly bounded such that |!l|| S D. V. E W.
Remark 7. Assumption 3 is common in the study of algorithmic stability and generalization theory. Assumption 4 is conventional in the sparsity recovery analysis of Lo-ERM. Assumption is needed for establishing the Lg staaiiiyyyty of Lo-ERM in Lemma I to follow. Similar conditions have also been assumed the prior work of Yuan & Li (2022).
Let w² == arg wew R(w) ) be the global minimizer which is unique due to the strong convexity of R. For a given index set J S [d]. let us consider the following restrictive estimator over J: arg min (g(w)- (up(()))(
"SJ.
We first present the following lemma that guarantees the T.g-stability of w'y for any fixed J with W|= hi. See Appendix C. for its proof.
Lemma 1. Assume that Assumptions 3, and hold and log( 2 2. Let S [d],]J] k log set of indices of cardinality k. Then for any 2 2, the oracle estimator Wly has L Typ-stability with parameter
14 N
1 /442
-+2GD
4G2
+2GD)
2GDlog(N)y
log(1/öx)
Remark 8. For sparse linear regression models, it can be verifted based on the result by Agarwal et al. (2012, Lemma 6) that Assumptions 4 holds with 8N = for some universal positive constant Cg. Then we have log(1/8x)
<o.N 2 2 for sufficiently large N, and Lemma implies log(N) Tog(N)
that 74 S ( (oDlgg(N) for all q 2
Go
The following theorem is our main result on the sparse excess risk of the inexact Lo-ERM oracle as defined in Algorithm 1. See Appendix C.2 for its proof which is stimulated by that of Theorem 3.
Theorem 4. Suppose that Assumptions 3, 4, 5 hold. Assume that log(1/8x)
log(N) > 2. Then for any 6 E (0, e I)), the following k-sparse excess risk bound holds with probability at least 1 - over the random draw of S:
R(Ws,) R(w()
GD log (# log 2 (NV) + (1og(A))
(G² G² + +GD +
G2 & log (ed) log (g)
log(1/ōN)
N
(klog (4)) log (4)) (R(wt)- R((w*))
+ GG
+ Kpp + E Akoopl
Nu
8

---

Published as a conference paper at ICLR 2023
Remark 9. For the IHT-sttyle algorithms, the sparse optimization sub-optimality Dk.opt can be bitrarily small (with high probability) after sufficient rounds of iteration (Jain et al., 2014).
Specially for sparse linear regression models in which Assumptions holds with dN e- (Agarwal et al., 2012), we have that log(1/8x)
co
2 can always be fulfilled for
log(N) [o
sufficiently large sample size N, and the sparse excess risk bound in Theorem 4 roughly scales
R(ös,u) R(wj) x (A: log (d) + log (1/6)) (og)
N
log (d) log (1/8)) (R(wE) R(w*)) + oopp + E [A k..pp
Generally for misspecified sparsity models, the dominant rate in the above bound matches the O (N sparse excess risk bound of Yuan & Li (2022, Theorem 1) for IHT under similar conditions.
Compared to the )++) bound available in that paper (Yuan & Li, 2022, Theorem 3), the preceding bound is generally slower in rate but more broadly applicable without imposing any strong-signal or bounded-loss conditions as required in the analysis of Yuan & Li (2022).
For well-specified k-sparse models such that R(wE) = R(w"), i.c., the population minimizer is truly k-sparse, the preceding bound improves to
R(ws,t) R(w S (k log (d) + log
(N) + Ak. + E [p
N
Therefore, our bound more appealing in the sense that it naturally adapts to well-specified models to attain an improved ) rate. In contrast, the regularization technique used by Yuan & Li (2022, Theorem 1) needs optimal choice of penalty strength of scale O( (()x) which leads an overall
slow rate of convergence, though the analysis is relatively simpler.
We further comment on the role of Lta-bibbyytyy played in deriving the improved bound of The- orem 4. The 0 fast-rate component of the bound is indeed rooted from the L,y-tability co- efficient as established in Lemma and application of Lemma 6. The relatively slow O ( component, which is controlled by the oracle factor A(wā) - R(w"), ). is mainly due to a careful anal- ysis customized for handling the combinatorial optimization nature of Lo-ERM. Such slow-rate term would be vanished if the global minimizer w" is truly k-sparse. Therefore, we confirm that the fast-rate component attributes our -tabbiiiyy theory, while the slow but adaptive rate component mainly attributes to the optimization property of Lo-ERM, Finally, we comment in passing that our improved stabiilty theory can also be applied to some prior applications such unbounded ridge regression and k-folds cross-validation to obtain sharper generalization bounds.
CONCLUSION
In this paper, we presented an improved generalization theory for L,tstable learning algorithms. There exits a clear discrepancy between the recently developed near-optimal generalization bounds for uniformly stable algorithmss and the best known yet sub-optimal bounds for Ly algorithms. Aiming at closing such theoretical gap, we for the first time derived a set of near-optimal exponen- tial generalization bounds for -tt-bt algorithms that match those of uniformly stable algorithms. As concrete application of our -ta-biibyy theory, we have applied the developed analysis tools to derive strong exponential risk bounds for inexact sparsity-constrained ERM estimators under milder conditions. To conclude, Lttble algorithms generalize almost fast as uniformly stable algo- rithms, though the distributioon-deeeddee notion of -tabbiiiyyty is weaker than uniform stability.
ACKNOWLEDGMENTE AND DISCLOSURE OF FUNDING
The authors would like to thank the anonymous Reviewers and Area Chairs for their insightful com- ments which are truly helpful for improving this paper. Siao-Tong Yuan funded in part by the Na- tional Key Research and Development Program of China under Grant No.2018AAAO0 2018AAA0100400,, and in part by the Natural Science Foundation of China (NSFC) under Grant No. No. U21B244, No.61936005 and No.61 1166009..

---

Published as a conference paper at ICLR 2023
REFERENCES
Karim Abou-Moustafa and Csaba Szepesvári. An exponential Efron-Stein inequality for l.q stable learning rules. In Proceedings of the Conference on Algorithmic Learning Theory (ALT), pp. 31-63, Chicago, II. 2019.
Alckh Agarwal, Sahand Negahban, Martin J Wainwright, et al. Fast global convergence of gradient methods for high-dimensional statistical recovery. The Annals of Statistics, 40(5):2452-2482, 2012.
Sohail Bahmani, Bhiksha Raj, and Petros T. Boufounos. Greedy sparsity-constrained optimization. J. Mach. Learn. Res., 14(1):807-83) 2013..
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1279--12288, Vancouver, Canada, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Ap- plied and Computational Harmonic Analysis, 27(3):265 2009.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities using the en- tropy method. The Annals of Probability, 31 3133) 2003.
Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi, and Pascal Massart. Moment inequalities for functions of independent random variables. The Annals of Probability, 33(2):514-560, 2005.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Proceedings of the Conference on Learning Theory (COLT), pp. 610-626, Virtual Event [Graz, Austria], 2020.
Alain Celisse and Benjamin Guedj. Stability revisited: new generalisation bounds for the leave-one- out. arXiv preprint arXiv:1608.06// 2016.
Alain Celisse and Tristan Mary-Huard, Theoretical analysis cross- validaaaii for estimating the neighbor classifier. J. Mach. Learn. Res., 19:58:1 2018.
risk of the
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 144-753, Stockholmsmässan. Stockholm, Sweden, 2018
Le- Yu Chen and Sokbae Lee. Best subset binary prediction. Journal of Econometrics, 206())33--66, 2018.
Le- Yu Chen and Sokbae Lee. Binary classification with covariate selection through to- fo-penalized empirical risk minimization. The Econometrics Journal, pp. 1-16, 2020.
Yuan Shih Chow and Henry Teicher. Probability theory: independence, interchangeability, martin- gales. Springer Science & Business Media, 2003.
Richard Combes. An extension of McDiarmid's inequality. arXiv preprint arXiv: 1511:,5400 2015.
Qi Deng and Wenzhi Gao. Minibatch and momentum model-based methods for stochastic weakly convex optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp- 23115-23127, virtual, 2021.
10

---

Published as a conference paper at ICLR 2023
Lue Devroye and Terry J. Wagner. Distribution-fre free inequalities for the deleted and holdout error estimates. IEEE Trans. Inf. Theory, 25(2):2(2222))2 1979.
Vitaly Feldman and Jan Vondrák. Generalization bounds for uniformly stable algorithms. In Ad- vances Neural Information Processing Systems (NeurIPS), pp. 9770-9780, Montréal, Canada, 2018.
Vitaly Feldman and Jan Vondrák. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Proceedings of the Conference Learning Theory (COLT), pp. 1270-1279, Phoenix, A7, 2019.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 439 439,449, Chicago, II., 2020.
Dylan J. Foster and Vasilis Syrgkanis. Statistical learning with a nuisance component. In Proceed- ings of the Conference on Learning Theory (COLTT), pp. 1346-1348, Phoenix, 2019.
Simon Foucart. Hard thresholding pursuit: An algorithm for compressive sensing. SIAM J. Numer. Anal. 49(6))2543-2563, 2011.
Rahul Garg and Rohit Khandekar. Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property. In Proceedings of 26th Annual International Conference on Machine Learning (ICML), pp. 337-344, Montreal, Canada, 2009.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pp. 1225-1234, New York City, NY, 2016.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high- dimensional m-estimation. Advances Neural Information Processing Systems (NIPS), pp- 685-693, Montreal, Canada, 2014.
Satyen Kale, Ravi Kumar, and Sergei Vassilvitskii. Cross-validation and mean-squan stability. In Proceedings of the Conference on Innovations in Computer Science (ICS), pp. 487-495, Beijing, China, 2011.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with con- vergence rate o(1/n). In Advances Neural Information Processing Systems (NeurIPS), pp- 5065-5076, virtual, 2021.
Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2593-2656 2006.
Aryeh Kontorovich. Concentration unbounded metric spaces and algorithmic stability. In Pro- ceedings of the 31th International Conference on Machine Learning (ICML), pp. 28-36, Beijing, China, 2014.
Samuel Kutin. Extensions to McDiarmid's inequality when differences are bounded with high prob- ability. Dept. Comput. Sci., Univ. Chicago, Chicago, IL, USA, Tech. Rep. TR-2002-04, 2002.
Samuel Kutin and Partha Niyogi. Almost-everywhere algorithmic stability and generalization emror. In Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence (UAI), pp. 275- 282. Edmonton, Canada, 2002.
Iija Kuzborskij and Christoph H. Lampert. Data-dependent stability of stochastic gradient descent. In Proceedings of the 35th International Conference Machine Learning (ICML), pp. 2820- 2829, Stockholmsmässan, Stockholm, Sweden, 2018.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 5809-5819, Virtual Event, 2020.

---

Published as a conference paper at ICLR 2023
Xingguo Li, Tuo Zhao, Raman Arora, Han Liu, and Jarvis D. Haupt. Stochastic variance reduced optimization for nonconvex sparse learning. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pp. 917-925, New York City, NY, 2016.
Andreas Maurer and Massimiliano Pontil. Concentration inequalities under sub-gaussian and sub- exponential conditions. In Advances in Neural Information Processing Systems (NeurIPS), pp.
7588-7597, virtual, 2021.
Sayan Mukherjee, Partha Niyogi, Tomaso A. Poggio, and Ryan M. Rifkin. Learning theory: stabil- ity is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math. 25(1-3): 2006.
Tomoya Murata and Taiji Suzuki. Sample efficient stochastic gradient iterative hard thresholding method for stochastic sparse linear regression with limited attribute observation. In Advances in Neural Information Processing Systems (NeurIPS), pp. 5317-5326, Montréal, Canada, 2018.
Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM J. Comput., 24(2):
227-234, 1995.
Alexander Rakhlin, Sayan Mukherjee, and Tomaso Poggio. Stability results in learning theory. Analysis and Applications, 3(04):397-417, 2005.
William H Rogers and Terry J Wagner. A finite sample distribution -frere performance bound for local discrimination rules. The Annals of Statistics, pp. 506-514, 1978.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. J. Mach. Learn. Res., 11:2635 2--26-26777,, 2010.
Jie Shen and Ping Li. A tight bound of hard thresholding. J. Mach. Learn. Res., 102208:--208:2, 2017.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Jialci Wang, Mladen Kolar, Nathan Srebro, and Tong Zhang. Efficient distributed learning with sparsity. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 3636-3645, Sydney, Australia, 2017.
Lutz Warnke. On the method of typical bounded differences. Combinatorics, Probubility and Computing, 25(2):269-299, 2016.
Xiao-Tong Yuan and Ping Li. Stability and risk bounds of iterative hard thresholding. IEEE Trans. Inf. Theory, 68(10):6663-666) 2022.
Xiao-Tong Yuan, Ping Li, and Tong Zhang. Gradient hard thresholding pursuit. Mach. Learn. Res., 18: 18:166:11166::44 2018.
Xiao-Tong Yuan, Bo Liu, Lezi Wang, Qingshan Liu, and Dimitris N. Metaxas. Dual iterative hard thresholding. J. Mach. Learn Res., 21:152:1-152:50, 2020.
Tong Zhang. Leave-one-out bounds for kernel methods. Neural Comput., 15(6):1397-1437, 2003.
Pan Zhou, Xiao-Tong Yuan, Huan Xu, Shuicheng Yan, and Jiashi Feng. Efficient meta learning via minibatch proximal update. In Advances in Neural Information Processing Systems (2019), pp. 1532-1542, Vancouver, Canada, 2019.
12

---

Published as a conference paper at ICLR 2023
A PRELIMINARIES
In this section, we collect some preliminary results that will be used in our analysis. We start by introducing the following -orm generalization of the celebrated Efron-Stein inequality, which is a corollary of Boucheron et al. (2005, Theorem 2).
Proposition (Generalized Efron-Stein inequality (Celisse & Guedj, 2016)). Let [Z Zx) be set of independent random variables valued in Z and 2 R be some measurable function. Then there exists a universal constant K < 1.271 such that for all 2 2,
N
(lx(S) - Big(S)Il,, S /2kg,
Σ
(a(S) - 9(S()))
9/2
The following result is an immediate consequence of Proposition when applied sum of inde- pendent random variables, which revisits version of Marcinkiewice-Zyygmmmn inequality (Chow & Teicher, 2003).
Proposition Let Z...... En be a set of independent centered random variables. 2 2,
Then for all
N
N Σ 1=1
Σ
Z
S 2
2Rq
Z
7/2
The following lemma is simple yet useful in our analysis.
Lemma 2. Let S (Z,,... Zn) } be a of independent random variables valued in some measure
space 2 and ZN + IR be some measurable function. Then for all S [N] and q 2 1, we have
[g(S)))l I [19())]l, = -1llsll,
Proof.
Recall g(S)) = (S)(S) Sr]. Then using Jensen's inequality we can show that
[l)( (EE (S] 17 1/9 < (E (()) SAD /1 (Ello())))) /s == (19(())
By definition we can also express [Ig(S) 11 (E (B)) S,]1) (1I L
As direct consequence of Lemma 2, the following result indicates that conditional expectation does not expand the differences in norm.
Lemma 3. Let {Z..... Zn} } be a set of independent random variables valued in some measure space 2 and N + R be some measurable function. Let I C [N] be index set. Then for all i EE and 2 1,
((())) s - 9((()))
Proof. For each E 1, by applying Lemma 2 to g(S) g(S(i)) we can show that (1g(S)) g(S )l, < ([g(S) - (( which gives the desired result.
We also need the following lemma about the equivalence between tails and moments (see, e.g.. Bousquet al., 2020).
Lemma 4. Let Y be real-valued random variable.
Suppose that Y satisfies the following inequality for some a, b 2 0 with probability at least 8 for any (0, 1),
Y alg (5) + by log e
Then, for any q it holds that
|| 5 3aq 9b
13

---

Published as a conference paper at ICLR 2023
Suppose that Y satisfies ||Y|l, f(g) for any 1 qi 9 qu and some non-negative real function J. Then the following holds with probability at least 1 - 8 for any å E (e! - {)
| of (l0g )
Proof. We only prove the second part which slightly generalizes the corresponding result of Bous- quet et al. (2020, Lemma 1). For any ò E (e--ux - el-#:,. we choose log(e/ò) E [qt, qu). Using the condition ||l f(g) and Markov's inequality yields
PP (v) ey|> es (1og E (7)) = P((M > el|Y1la)
8
YI
This proves the desired bound in the second part.
Remark 10. Suppose that for any E (0, 1), the following inequality holds with probability at least 1- over S, 5 Z:
(AAS)) Z) ((A(S()) 2) a log (3) + B log (3)
Then according the first part of Lemma 4 we have that A is -table by "i 3aq + 9b. Remark 11. Specially if qi 1 and qu = oc is allowed, then the second bound in Lemma 4 holds with an arbitrary tail bound 6 E (0, 1).
Finally, we present the following technical lemma about self-bounding inequalities to be used for showing fast rates of excess risk bounds under Bernstein quadratic growth conditions.
Lemma 5. Let x, a, c. be a set of non-negenn non-negative quantities satisfying x S a /blz + c). Then must hold that x S 30+2b-c
2
Proof. If x a, then the claim holds trivially. In the complementary case of x a, by condition we must have (x - -a)² < b(x + c). which then implies
x - 2a + + 2//bb b(a + c)
3a + 2b +
< 2
2
where we have used the basic fact 2 bla + cc abaa+c
B PROOFS FOR SECTION
B. PROOF OF THEOREM 1
The proof is generalization of the sample-splitingg arguments of Feldman & Vondrák (2019);
Bousquet et al. (2020) under the considered property of Lo-morm bounded difference. For the sake of completeness, we reproduce below the relatively simpler arguments of Bousquet al. (2020, Theorem 4), with proper modifications made to adapt to our setting via using the generalized Efron- Stein incquality in places of McDiarmid's inequality.
Proof of Theorem I. Consider & such that 2 < N < 2 If N < 2* we pad the training set S with extra zero-fune fero-functions so that = 25 Consider the partition Io, I1. .... In of [N] given by
Io ((1) (2*)), I ([1,2), (3, 4)... (2 2), I, {{1, ((1,...,*%)) 2*),
For any i E [N] and O,..,, denote by (() Ii the only set from Iz that contains and consider the following random variables
of
E 9i
Z, S ((())
In particular, of = 9: and ot E[gs
Z: Clearly we have the following telescope sum:
k-1
Σ
(gf gi
++1 - Ejg: Zz].
9: =
1=0
14

---

Published as a conference paper at ICLR 2023
It follows that
Σ 9
E
Zil
Σ
Σ
9
(10)
We need to upper bound the right hand side of the above inequality. To this end, it can be verified that
g. +1
E gi Zi S E g Zi S Sp+1())
Since Ii has a bounded Lg Loffffeere by By with respect to all variables except the i-th variable, known from Lemma 3 that so is of for each 0, ..., Conditioned on Zi, Sarpy invoking Proposition I to of yields
llo o (Z,, SptTo) S 2mg22 Bg
as there are 2 indices in (1) (i). It follows from Lemma 2 that
11 9 1+1 11 = llot - g: 11 (Zi, S ST-TT) S 2
Now consider any I' E I, Since each E I, of of ++ depends only on Zi, Sp. these terms are independent and centered conditioned on S7r. Therefore, applying Proposition 2 yields
Σ ot gtt1 iE
(sp) 2/ 2ng22 x 2ng22 Bg 4xq92' Bay
which according to Lemma 2 implies that
Σ
gi
[+]
I 4mg2t Bg.
iET!
Then based on the triangle inequality we get
Σ ot
g.
Σ
9
g
1+1
<
2
Anq2' Bg 4kg22* Bg < NAq
KE[N]
ien
Finally, the right hand side of Eq. (10) can be bounded as
Σ 9: Elgs
2,]
1+1
< 4xqN [logz N 19,
(11)
i=1
9
1=0
which gives the first desired bound. In view of Eq. (11) and the triangle inequality have
N
Σ
E[ga
2,]
+ 4xgN [logz N 1
(12)
2 0, it follows from Proposition that the first term the right hand side of Eq. (12) can be bounded as
Since [S] Zill,, S M, and Elg. (S) S
N
E
Z,]
2kNgN.
(13)
The second desired bound is obtained by plugging Eq. (13) into Eq. (12).
n
15

---

Published as a conference paper at ICLR 2023
B.2 PROOF OF THEOREM 2
The proof technique follows that of Bousquet et al. (2020, Lemma 7) developed for uniformly stable algorithmss with natural adaptation the distribution-deeenddnn notion of -taabiii.
Proof. Let us consider
h2( == R(A(S)) ((A(S); Z,), (x(S) = Ez: - zi)
Then the norm of the generalization gap can be bounded as
N
N Σ (S)
N
1 [R((((S) - (s(A = N
Σ (S)
S N
+
Σ
(h.(S) - (((s))
B
(14)
We respectively upper bound the two terms A and B in Eq. (14). To bound the term A, by definition holds that (S) S Z = O. Based on the triangle inequality we can show that
[[) 1,,, (S))
= |><(AA((A(SS)))) Z) - Bzg ((AA(()): 2))]l
<IIE(A(S(0) 2)1,, + (I((A(()); 2:)1l, S 2M4.
where in the first and second inequalities we have twice used Lemma 2. Next we further show that gi has bounded -o-morm difference by 27 with respect to all variables in S except Zú. Indeed, for each j A it can be verified that
(() - 21(6)))
< B2: R(((S()))) R(A((S(())))))) (((0)) E2z ((AA(S)) -()((((()))(()))))) 2.)
B2, B2: ); ((A(((()))))) 2)] + +1E2:((A(((()) Z,) ((A((S(()))) 2,)
< ((A((())): -())))())))(((((((()))((( ((((((()))))) 1),1, + ((A(S(O): (EAD-E(((((SS)))) E(A((S())))) 2:) < 2T
where in the last but one inequality have used Lemma while in the last equality we have used the stabiiiyyy assumption on the algorithm A. Therefore, {gi} satisfy the conditions of Theorem and thus
A
Σ
(S)
S S4/2kNgM,, + 8nggN Nh7
(15)
9
Now we proceed to bound the term B. It can be verified that
B <
Ezi [R(A(S)) R(A(S()))
Σ Bzj [((A();; Z,) ((A(S()): 2i0 2:1
N
Σ Ez (((A(S):)) -(A(S))))((((((()))) 2)]
Σ
Ezg ((AA()) 2,) E(A(S()); -(CA(S(()));)) 2:)
+
-(A(S))))(((((S()))
E(A(S(0): 1)11 + +Σ [| 2,) - 23)1 S 22N
(16)
where in the last but inequality have used Lemma 2, and in the last equality we have used the L. stabiityyy assumption. Plugging bounds Eq. (15) and Eq. (16) into Eq. (14) and preserving leading terms yields the desired result.
16

---

Published as a conference paper at ICLR 2023
B.3 PROOF OF THEOREM 3
We need the following lemma which plays a fundamental role in proving the main result.
Let A : NN + W be a learning algorithm that has stabiiliy by Ng for q 2 1. Suppose that [[E(A(S); l) < Mg for any Z E 2. Let S' be independent copy of S. Then the following bound holds for all 2 2:
Lemma 6.
N Σ
R(A(S)) - Rs(A(S)) - ([(((())) +
B(((A(S)): 2,) Z
S My log(N).
N
Proof. Let us again consider (s( = Ez! [((A((()) - ((A(S()); 2.] Then using similar proof
arguments to those of Theorem 2 we can show that
N
N(R(A(S)) (s(S)))))
Σ 9s(
Ez R(A(S)) ((A(S)))((((
Σ Ezy ((A(S): - ((A(S()))) 2n]]
Ez [((A(S); 2) E(A(S())) - 22)
Σ Ezj (((A();; 7,) E(A(S())) Zii
- 1:11 + Σ
| ((A(S)))) 2)) -((A(S)))) 2i)1 S 22N
which implies
1 N
R(A(S)) ((A(S))-Rs(AAA Rs(A(S))
Σ (S)
s 27
N
==1
Also, (S) satisfies the conditions of Theorem 1 with 3g 27g and follows from the second bound of Theorem 1 that for all g 2,
Σ
8Nary [oga N7. (g)( (Sg zI)
N
Combining the above two yields
N Σ
R(A(S)) Rs(A(S)) N (S) zi|
The desired result follows by noting that
(Sg Z = E[R(A(S')) E[E(A(S"): Z.) Z = E[](( - BI((A(S)) Z,) ZZ].
This completes the proof.
With Lemma 6 in place, we are ready to prove the main result of Theorem 3.
Proof of Theorem 3. Consider any w" E W*, is standard to decompose and bound the excess risk
as
R(A(S)) R
= RR(A(S)) Rs(A(S)) + Rs(A(S)) Rs(w") + Rs(w") R²
Sppp + R(A(S)) Rs(A(S)) - -(R- Rs(ww))
(17)
N
- + +(S) + E[R(A(S)) - N B(((A(S"); 2,) Z - (R" Rs(w")), Σ
17

---

Published as a conference paper at ICLR 2023
where
T(S) R(A(S)) Rs(A(S)) B[((A(()))) 1 N Σ E(((A((");;) 2)) Zi)-
Since we have the freedom to choose w", let specify it in the above as w (S") E W which is the minimizer that satisfies the Bernstein condition in Assumption associated with A(S'). Then, it follows from Eq. (17) that
R(A(S)) R²" App
<T(S) + B[R(A(S))] B(((A(S)) Z (R" - [E[ (S')) S)).
Consequently,
[[((A(S)) R² - Appilla
N
< (1((5))1, +
E [[(w (5'); (S'(
((A(S)))) Z.) 2.] (R' (ER(A(S))) E [l((w" (5");
(18)
N
Soy log(N)+
Σ (('( 2 E(A(S') Z,) z (R" (((-E((((SS)))
N
974 log(N), and the fact where in "G1" we have applied Lemma to obtain [[T()) S E[R(A(S))) = E[R(A(()))
Part (a): bound the term T. using Bernstein's inequality for sum independent bounded vari- ables together with the generalized Bernstein condition we can show (see the proof arguments of Klochkov Zhivotovskiy (2021, Theorem 1.1) for the details) that
9 (BE(R(A(S)) R*
gM N
((A(ER(((S)) R
A opt
+ E
App
qM
TS
N
N
N
(B())(((SS) - R
App 1g + E opp)))
qM
N
N
where the last inequality is due to Jensen's inequality. Therefore, combining the above and Eq. (18) yields that for some universal constant C::
(1 log(N)) ((((R)((S)) - R Appella + E opp))))
([((A())--R"-1 sC (%,
q.
+
N
N
By invoking Lemma 5 to the above self-bounding inequality with [(((S))) R Appulla-
a C(g7, log(N) + gM N ),
and c [p[ we immediately obtain that N
((A(S)) R opulla S E opd + 47 log(N) + (M + B)q
This gives the desired bound in part (a).
Part (b): Under the given conditions in part (b), we can bound the term T in Eq. (18) as follows for q 2 2:
Pit possible to relax the ad-boundedness condition on the loss function its sub-Gau Gaussian or sub- exponential counterparts by alternatively applying general Bernstein-tye type inequalities for sums of independent sub- Gab-Gaussian eub-exponential random variables (Vershynin, 2018) in this part of proof. For the sake of simplicity and transparency of exposition, here choose to work on the bounded loss while keeping in mind that the requirement not essential.
18

---

Published as a conference paper at ICLR 2023
N
Z - - -E(R(A(S)))
=
G 22K
[B (()))))))) 2)) Z.] - - E[R(A(S))))
N
9/2
4 1Rg
E (S') ((A(5))) 2)) 2 + -R" -ER((ASS3))1
N
9/2
4 Rq
TRa (S': - ((A(s)) Z.) Z 9/2 + NE R(A(S)))
N
Rq
E
[ [G (S') A(5 2,I1 + NE' (G)[()) - A(S
N
4G 2
2K5g
E (S)) [(
/Fg
8G nq
B((((((S)) R.
[(R(A(S)) R Dopel + E Appt
VN
VNu
8G /R (((A(S)) R Applll R[[
VNu
where in "GI" we have used Proposition in "Ce" we have used the Lipschitz-loss condi- tion, in "C3" we have used || [G'll= ((") A(S') Zi]l 9/2 = E² [G'] A(S")ll < Ge (S") A(5)) in "Ca" we have used Assumption 2, and the last inequality is due to Jensen's 's inequality. Then, plugging the above bound of term T into Eq. (18) yields that for some universal constant C::
[[(A(S)) - R - Aupilg S (nr logg + +G |IR(A(S)) R Applll + E Aupi)
Nμ
Invoking Lemma 5 to the above inequality with [(((A()) R² Dopellor a C97 log(N), gG2 b PN
and E[Aop] yields
[I((A(S)) - R² Appill S B[Aop] 47n log(N) 9G2
PN
This gives the desired bound in part (b). The proof is completed.
19

---

Published as a conference paper at ICLR 2023
C PROOFS FOR SECTION 3
C.I PROOF OF LEMMA 1
Proof. Let consider the following event about the restricted strong convexity of Rs:
a: Rg is pu--trongly convex.
Let Y =1g be the indication random variable associated with E. Then by Assumption 4 we have
P(Y = 1) 2 1- - ōN. Suppose that & occurs such that Y = 1. Then,
Rs( (s(wggo)p)) - Rs(w(sj)
1
Σ ((Wgro)ii 2z) - P(ws Z3))
1 N (e(w)ro)si Zi) E(W3)Ji Zi))
N
-gg (1zgo)1) (w5)s) (elwgroppi Zi) - {(W3) Zi))
(Rwwsunnp Zi) - ((w Zi))
N
1 N [(Wroo)i Z() E(W3) Z?)
$ ((wjoppi Z,) - e(wssjii Zi) +
2G N
where we have used the optimality of lasoe with respect to Rgm (w) and the Lipschitz continuity of loss. Since occurs by assumption, Rs is st--tnoggly convex. Since "SJ is optimal for (s(w)) over the supporting set J, we have
Rs(w (s(w)(opp) Rs(wšjp) 2
M*
w w ||
Combing the preceding two incqualities yields w s w
S
4G M
Consequently from the
Lipschitz continuity of we have that for any 2 E 2, the following holds conditioned on Y = 1:
4G
[(wSroj Z) - (( ; 2) - G 15
(19)
M
In the complementary case of Y = 0, in view of Assumption 5, it always holds that
[ 7) f(wsjJ u Z) s G | " 2GD.
(20)
(xx)
Let us consider Ja == log(N)) By assumption 9a 2 2. Then for 2 2 q S Ja. it can be verified that
E [wwsoopi 2) - ((w5) 2) []
=P(Y = 1) |[wssooppi 2) {(W$jji 2)) 9 Y V=1
+ PPY = O)E
[(w3coopi 2) - -((w3 2)
Y =0
4G2 9
5N (2GD)) ( [4G 9
1
4G2 9
1
+ Naw
(2GD)* <
+
(2GD)
M
M
No
It follows that for all 2 2 q Ju
[(Bsooppi Z) f(53) Z)
1G2
1
(2GD)²)
1/9
1
/G2
+ 2GD)
1
N
pk
where we have used a² b < for a, b > and q 2 2. For the complementary case > qu- it is trivial to show that
[( Z)
l( ;: Z) |1, 2GD <
2GD
q.
qu
Assembling the preceding two bounds yields the desired Tsa-staiyliyy bound.
20

---

Published as a conference paper at ICLR 2023
C.2 PROOF OF THEOREM 4
Let us denote a+ maxfa fa 0}. We need the following key result in our analysis, whose proof idea draws large inspiration from that of Theorem with proper modifications for handing the challenges imposed by the combinatorial optimization nature of Lg-ERM.
Lemma 7. Suppose that Assumptions 3, 4, 5 hold. Assume that log(1/ōx) [g([N 2 2.
Then for any
d e (0, e)), it holds with probability at least that
R(W'sju) - I((w()
sup |
GD log (x)) + log (x)) (og))
log?(N)) (N)
+ (1oS(N) ( ( +++00 + GD) + G²
k log
log (g)
log(1/ŌN)
Me
N
lo k) log (5)) (R(w)) R(w-)) + (Rs(WŠiJ) Rs(w0s,))
+ G
N₁
+ E ( (RS(W(j)) Rs (s(w5s,)) )
Proof. Given fixed index set J C [d] with |J| = k, we can show that the following holds for any
q 2
R(wg.) Rs Rs(wg))) u + Rs(w") R(ww)
N
sls + E(((ws)))) ()
Bi Zi) 2s] + Rs(w") - R(w")
N
1=1
(21)
N
< sp +
E[R(wS))]
Billws Z.) Z.J R(ww) + Ro(w*)
N
T
where
s= R( Rs(wS)s [[[((w))))
Σ
Billwgg y Z.) Zz).
In view of Lemmal we have that w has stabiitty by
1 442 + +2GD)
2GD log(
24
+
log(1 (og(1/)))
Then invoking Lemma over the supporting set J yields
s S mh log(N) = 9 glog(N)
4G2
+ 2GD)
+ 2GD log 2 (N)g²
(22)
N
μí
log(1/5x)
21

---

Published as a conference paper at ICLR 2023
We now bound the term T in Eq. (21) as follows:
N
T
E w"; Zi)
((13r)Ji 2i) [n] (R((w")
9 2
2
E [(wu= Zi) 1133 Z,) [.] (R(w*) ((R((3))))l))
N
9/2
E2 [((w>: 2,) - f(w3g) jr Zi) Z,] (R(w*) - B[ ( 2
Σ
N
9/2
kp
E2 [(ww; Zi) f(wsy) 1 Z,)
Z:
+ +NE? [((w)) R(w3)))))
(23)
N
1/2
kp
Σ
E2 G |
w ا
2
NE? [
w w3y
N
9/2
Co 4G 2xp
w w5/1s 11²
E
VN
51
8G /Kg
V
E
[(w0g1))= M(w)))
8G 8G
VNH V E
[[w3sp)) - R((w))
VN
where in "G" we have used Proposition 2, in "C2" we have used the Lipschitz-loss sumption, in "Ca" we have used ||E
Gillw"
1 2, 9/2 E² Gl| Wا S
G ||0 - w [|3] in "Ca" we have used the strong convexity condition in Assumption 4. Plug- ging Eq. (22) and Eq. (23) into Eq. (21) yields that for any g 2 2.
[(w3sp)) - R(w*) - Rs(w)))) + Res Rs(w")
(24)
(log(NN)
/ 4G2
+ 2q GD (NV)
EqR R(wg))) R(wc))
+ 2GD)
log(1/6N) + +8G
N
bk
Nu.
Next we need to upper bound the factor E [R(w)))) R(w*)) ((()) in the second term of the above bound. To do so, let consider 9 2 in Eq. (24). It follows from the optimality of w" and S'y that
E R(ws))) - R(w") - Rs(wğg)) + Rs(w")
[(WSjj) R(w")) - Rs(w + Rs(w=))
Eq. (og))))(N)
1862
log (N)
2xE R(wsjs) R(wx+)
+ 4GG
+
SG
N
log(1/Ön)
Nu
lNg(N)
(8G2
8GD (oN)
(N)
E R(wāju) R((w))
64kG²
+ 4GD
P4k
log(1/5x)
Nu
where in the first inequality have used Cauchy-Schwarz inequality, and in the last inequality have used the fact Vab < 2 + bt for any a, b, > Rearranging both sides of the above inequality
22

---

Published as a conference paper at ICLR 2023
with simple algebra leads to
E
R(ws(J) R(w))]
Rs (s(W())) Rs(w")] + log(N)
(16G2
16GD log (N)
128nG²
22
+ +GGD
+
N
log(1/6N)
Nu
-2E
[s(W()))) Rs( + Rs(w Rs(w"))
log(N)
16G
16GD 16G (N)
128xG²
+ 8GDD
N
log(1/ŌN)
Np
-2E
[s((w()))) Rs(w))
+(((w - R(w"))
log(N)
16G2
16GD BuGDlog"1 [
log(1/ōN) + 128nG
+ 8GD
N
1ik
Np
(25)
22E
[s((W)))) Rs(w"g.))
+ +((((())) -R(w"))
log(NN)
[16G2 + 8GD)
16GD log²(N)
+ 128kG²
N
uk
log(1/dx)
Nu
< 2E
(R Rs(w
+ (R(wE) R(w"))
T2
log(N)
16G
16GD (N))
128xG²
+ 8GD
+ Np
N
jkk
log(1/ÓN)
T3
Plugging Eq. (25) into Eq. (24) yields that for any q 2 2
|| [R(WSj)) R(w²)
Rs((ws))) Rs(ww)
① (log(N)
1402
+ 2GD2² log (og)(N) + 1
(T + Ta Ta)
+2GD
N
14
log(1/8g (/((1/))
Nu
9 (log(N)
4G2
2G log (N)
Rq + Ta) Np
+ 2GD
+ + + 8G
+ 8G
N
log(1/ōN)
Nu
(26)
6 q (N)
1GG
2GDq² log log
RqTT2
16RqG²
+ 2GD
+ Ti + T3 +
N
P4
log(1/àn)
Nu
Nu
7 (log(N)
G2
GDq² log?(N) (N)
+ 902
[Rs(w()u) Rs(w
GD
+
+ E
N
14
log log(1/(N)
(R(w)) R(w*))
+ G
where in "Si" we have again used the fact Vab < a + for a, b, 0. Now we are in the position to finally upper bound the desired sparse excess risk with respect wi. which can be decomposed
2r
23

---

Published as a conference paper at ICLR 2023
in the following way:
R(wssj)) R(we)) = R(ws(j) R(w=) (s(w()s) Rs(w") + Rs(wš5p) Rs(wg)
+ Rs(w Rs(w") )+ + R(w") - R(wE)
< < R(wx*) (s((((s)= Rs(w") + Rs("(Sp)) Rs(w((,))
+ Rs(wf) Rs(w") )+ + R(w") - R(wf)
s R(wssp) - R(w") - Rs(w((s) + Rs(w") + (Rs(WSg)) Rs(w(sk)
Tj
+ Rs(wE) Rs (ww" + R(w") - R(wE).
T2
(27)
where in the first inequality we have used the fact Rs(w5s 5,)) S Rs(w() We are going to bound the
above two terms Ti and Tý respectively with high probability. Concerning Ti, since Eq. (26) holds for all q 2 2. in view of the second part of Lemma (with qi 2 and qu 0o) we can show that the following holds with probability at least 2 for any 8 E (0,e-
T R(wssjs) R(ww) Rs(ws) + Rs(w=)
< R(w's ,) R(w")- - Rs(ws(p)) + Rs(w*)
GD log² (5) log?(N)
(log(N)
[++ +GD)
G²
G²
log (5)
(28)
log( (1 (1/8))
1
log (9) (A(wg) - R(w*))
+ GV
+
+E
(Rs(w))u) - Rs Rs(w (
Nμ
Regarding the term Ty, similar to the argument of Eq. (23), we can bound its -nom for any 2 2 follows:
1
Tell
(l(wi) Zi) - E(w=; Z:)) - (R(w)) - R(w-))
N
N
2 2kg
(elwi;; 7.) e(ww; 7z) (R(w)) - R))²
N
9/2
4 A/Rg Rq
Σ
(e(uf: 2,) f(w=; Zi)) (R(wt) R) )²11
N
4/2
4 ARgg
(B(ut: Z,) flwi; Z.)) 4/2
+N (R(wf) - R(w=))²
N
4 2kg
NG | - w' 11
N
8G Kq
V [(ww]) R(ww).
VNp
By invoking the second part of Lemma 4 with @i 2 and Qu = we can translate the above moment bound into the following exponential tail bound that holds with probability at least for any å E (0, 11):
log (9) (R(wE) - R(w*))
Ty S G
(29)
Np.
24

---

Published as a conference paper at ICLR 2023
By plugging Eq. (28) and Eq. (29) into Eq. (27) and applying union probability argument obtain that the following holds with probability at least 1 for any 5 (0,
R(WS(j) R(w
GD log² (9) log + (IOR(N) ( (G
+GD) (
G
log (9)
log (5)
(R(w)) R(w=)) Ní
+
+ G
log(1/öx)
14k
N
+ (Rs(W))u) - Rs(w5gk) + E
(Rs(W))J)) - (s(
This proves the desired sparse excess risk bound over the supporting set J.
As the final step, since there are at most (3) - (ed) different J with |J| k, by union probability we can show that the following holds with probability 8 for any E (0, e0:
sup R(w3}J) R(wF)
JEld
GD log (x) + log (5)) log"(N)) + (Dog(N) (G² Pk
G² +GD)
G²
k log (#))
+ log (g)
()g()/
1
N
log # log (f)) (R(we) R(w=)) + (Rs(wŠ)u) Rs(w(sk))
+ G
Ny
(Rs(wšjp) Rs(ws) )
+ E
This completes the proof.
Now we are in the position to prove the main result in Theorem 4.
Proof of Theorem 4. Let consider J = supp (,),)) By definition we have WS.e "6s.." Then invoking Lemma yields that for any 5 E (0, e0,e-)), the following holds with probability at least
1 8:
R(wg,)) - R(w()= = R(w R((w))
GD log ad) log (5)) log" log)(N) + (10g(N)) ( G2 +GDD) +
G ie log
log (9)
log(1/ŌN)
N
(k log (ed)
log (5)) (R(wf)) R(w=)) + (Rs(w'))) Rs(wzg
+ G
Nu
(Rs(W)))) Roswss ( )}]
+ E
GD log ( (4)) + log (4))² 2 log (N)
+ (Log(N) (
G2 GD)
G²
add A log
+ log (4)
k
log(1/ŌN))
Mkk
1
N
GGV (ko (ad) log (+)) (R(w)) R(ww))
+
+ D Kpp + E
[kspp]
Nu
This proves the desired sparse excess risk bound.
25

---

Published as a conference paper at ICLR 2023
D OTHER RELATED WORK
Uniform stability and exponential generalization. Stimulated by a recent landmark work of Hardt et al. (2016), there is a renewed interest in the use of uniform stability for deriving generaliza- tion bounds for various learning algorithms and paradigms including stochastic gradient descent (SGD) (Kuzborskij & Lampert, 2018; Charles & Papailiopoulos, 2018; Lei & Ying, 2020), stochas- tic model based optimization (Wang et al., 2017; Deng & Gao, 2021). optimization based meta learning (Zhou et al., 2019), and differential privacy stochastic optimization (Bassily et al., 2019; Feldman et al., 2020). Compared to other stability arguments, uniform stability is notorious for im- plying high-probabiliity generalization bounds in addition to the traditional in-expectation bounds. Until very recently, the basic result of Bousquet & Elisseeff (2002), as expressed in Eq. (2), remains the best known exponential generalization bound for uniformly stable algorithms. Using some ele- gant proof techniques from adaptive data analysis, Feldman & Vondrák (2018) managed to replace
the first term in Eq. (2) by /%u (,)()), which leads to improvement whenever "/u 2 N- Soon after, a series of breakthrough results were obtained (Feldman & Vondrák, 2019; Bousquet et al., 2020) using tighter concentration bounds for sum of random functions, which eventually improve the stability dependent rate to a near-optimal one "/u log(N) log (t) as shown in Eq. (4). Addition- ally under the generalized Bernstein condition, these state-of- oftte-of-the-rt thethheeatttt art results lead to O ) excess risk bounds for uniformly stable algorithms (Klochkov & Zhivotovskiy, 2021).
stability and exponential generalization. More broadly for non-uniformly stable algorithms, exponential generalization bounds have also been shown to be possible under various weaker and cetrributiio-dependdde notions of stability. As an early work in this line, Kutin & Niyogi (2002) showed that under the so called "almost eeerroereeeryheere"" stability, which is a high-probability counterpart of uniform stability, generalization bounds that hold with overwhelming probability are still possible in view of certain modified McDiarmid's s inequality (Kutin, 2002). Later, Rakhlin et al. results of Kutin & Niyogi (2002) in more straightforward manner by using a powerful moment extension of Efron-Stein incquality (Boucheron et al., 2005). Recently for general T. algorithms, the exponential leave-one-out generalization bounds were derived using moment or exponential extensions of Efron-Stein inequality, with applications found in ridge regression, k-nearest neighbor classification and k-folds cross- validation (Celisse & Guedj, 2016; Celisse & Mary-Huard, 2018; 8; Abou-Moustafa & Szepesvári, 2019). However, when it comes to the recent break-through bounds of Feldman & Vondrák (2019); Bousquet et al. (2020), it is much less obvious how to easily extend these optimal bounds under the almost-every stability via simply incorporating the low probability failure events into concentration inequality. This is actually in sharp contrast to what have been done by Feldman & Vondrák (2019, Theorem 4.5) and Bassily et al. (2020, Theorem 2.1) for stochastic learning algorithms with uniform stability (over the randomness of data) holding with high probability over the internal randomness of algorithm. We refer the interested readers to Boucheron et al. 22013;; Kontorovich (2014); Combes (2015); Warnke (2016); Maurer & Pontil (2021) for more results on concentration inequalities beyond bounded- difference conditions, which are fundamental for deriving exponential bounds for non-uniformly stable algorithms.
(2005) revisited the
Generalization analysis of fn-estimators. We further briefly review some prior results on the generalization guarantees for statistical learning under cardinality constraints, which is the theme of the application part of our work. For the 4o-ERM estimator as expressed in Eq. (8), provided that the solution exactly known, a series of uniform excess risk bounds were derived over binary prediction classes (Chen & Lee, 2018; 2020) and bounded liner prediction classes (Foster & Syrgkanis, 2019). The exact solutions of EREERM, however, is computationally intractable in general high- nigh-diimnsional cases due to the NP-hardness of problem. Therefore, it is more realistic and desirable to establish generalization bounds for approximate fn-estimators such as the IHTT-ttlle algorithms (Yuan et al., 2018; Garg & Khandekar, 2009; Li et al., 2016). Particularly for misspecified sparsity models, set of sparse excess risk bounds with slow and fast rates were established through the lens of uniform stability theory under proper regularity conditions (Yuan & Li, 2022).
26


Reviews:
[{"review_id": "mMK2cC94fR", "reviewer": "Reviewer_dfYo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper derives near-optimal generalization bound under the notion of $L_q$-stability, extending previous work on distribution free uniform stability. The authors then apply their results to derive excess risk bounds to inexact $L_0$-ERM.", "summary_of_the_review": "The problem the paper studied is well related and the authors made substantial contribution for $L_q$-generalization bounds, significantly improving previous results by removing the overhead $\\sqrt{N}$ factor. I think the paper is a good contribution to the community and would like to recommend accept.", "strength_and_weaknesses": "The paper significantly improves the previous result under the notion of $L_q$ stability, which is a novel and substantial contribution. The paper lacks numerical experiments to support sharpness of their bounds, but this is not a big deal for a theory paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "f2C2Yj-Y9ct", "reviewer": "Reviewer_Ryqw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper shows that Lq stable algorithms also generalize well with the “correct” rates. Specifically, recent analysis of uniformly stable algorithms has shown that uniform stability implies generalization at a $\\tilde O(\\gamma + 1/\\sqrt{N})$ rate where $\\gamma$ is the uniform stability parameter and $N$ is the sample size, improving prior results of $\\tilde O(\\gamma \\sqrt{N} +  1/\\sqrt{N})$. The current paper shows analogous improvement in results for Lq stable algorithms, where Lq stability indicates that the qth moment of difference of the losses on neighboring datasets is bounded. Since Lq stability is weaker than uniform stability, this applies to a wider variety of algorithms.\n\n", "summary_of_the_review": "This result seems to fill an important gap in the literature on stability. The contribution appears strong and worthy of acceptance.", "strength_and_weaknesses": "The proposed results appear to both fill a natural hole in the literature and have reasonable applications. The exposition of prior work is well presented as well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "VAQLwLMw5S", "reviewer": "Reviewer_LaZo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This papers studies the generalization properties of $L_q$-stable algorithms. This notion of stability is distribution-dependent, and thus less stringent analogue of uniform stability. The authors first derive a general inequality for the sum of functions of random variables with bounded difference (Theorem 1), and use the result to show generalization bounds improving the best known bounds for $L_q$-stable algorithms, going from a $\\sqrt{N}$ to a $\\log(N)$ factor in one of the terms, where $N$ is the sample size, which is important to avoid vacuous convergence rates in regimes where the uniform stability parameter is $\\approx 1/\\sqrt{N}$. They then use their result to show excess risk bounds for $L_0$-estimators. ", "summary_of_the_review": "I believe this is a solid contribution to the study of stable learning algorithms, and that the paper would be of general interest to the learning theory community. ", "strength_and_weaknesses": "**Strength and Weaknesses**\n\nThe paper's technical and conceptual contributions are solid, clearly stated, and well-explained. The techniques seem sounds and the application to approximate $L_0$-ERM interesting.  \n\n**Questions/Feedback**\n\n- Could you comment on the technical novelty of Theorem 1? I understand this is a generalization of another result, but where the bounded difference is distribution-dependent, so this question is more about the mechanics of the proof. In particular, in Appendix B.1, you state \"*The proof is a generalization of that of Bousquet et al. (2020, Theorem 4) [...] We reproduce the proof here for the sake of completeness.*\". Where and how does the proof differ from that of Bousquet et al. (2020, Theorem 4), and what is the main technical addition to the proof?\n- In the statement of Theorem 1, the difference between the random variables $g_i(S)$ and $g_i(S^{(j)})$ is studied. On p.2, $S^{(j)}$ is defined as S but with the $j$-th sample point replaced by another sample point $Z_j'$. However the sample $S'=Z_1',\\dots,Z_N'$ doesn't appear in the theorem statement. Is it simply that $S'$ is missing from the theorem statement? In that case, are S and S' sampled independently from the same distribution, as stated earlier on p.2?\n- On p.3, it would be a good idea to at least explain in words what $R^*$ and $\\Delta_{\\text{opt}}$ are, instead of just referring to Eqn 8.\n- Typo p.5: \"substantially proves the overhead factor\" -> \"substantially improves the overhead factor\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TER7ltslQm", "reviewer": "Reviewer_Hu4j", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper continues the recent line of work on high-probability generalization and excess risk bounds for stable algorithms. In this regard the paper:\n\n* Extends the nearly-optimal generalization bounds for uniformly stable algorithms to $L_q$-stable algorithms.\n* Similarly, it extends the excess risk bounds for uniformly stable algorithms under the Bernstein condition to $L_q$-stable algorithms under either the Bernstein or quadratic growth conditions.\n* It considers the inexact empirical risk minimization (ERM) with sparsity constraints problem. Under Lipschitzness, (high probability) strong convexity, and bounded domain conditions, it shows it is $L_q$-stable and it proves a new excess risk bound for that problem. The bounds are comparable to others in the literature with different assumptions.", "summary_of_the_review": "This paper extends and builds upon the current best rate bounds on the generalization and excess risk bounds under the uniform-stability assumption to the milder $L_q$-stability assumption. \n\n* For the generalization bounds, instead of further needing a bounded loss, it needs bounded moments. \n* For the excess risk bounds, it either maintains the requirement of a bounded loss and the Bernstein condition or requires Lipschitness and the quadratic growth condition. These rates under the latter assumptions are novel as far as I know.\n\nThe paper needs to make clearer, though, the influences of the previous literature in their proofs, since some of them follow these papers closely. Similarly, it needs to further clarify some of the assumptions in the introductory text.\n\nThen, the paper finds bounds for the excess risk of inexact ERM with sparsity constraints (which are applicable to IHT). First, they prove these algorithms are $L_q$-stable and then they find specialized bounds that are comparable to those in the literature.\n\nThe paper needs to make clearer the comparison of their bounds and assumptions to those in the literature as well as the reason for Section 3, which does not use directly their bounds for generic $L_q$-stable algorithms. \n\nOverall, I believe the paper is well written and is a good contribution, so I recommend acceptance. Nonetheless, I still believe the comments in the weaknesses part should be addressed. \n\n**Minor comments and nitpicks that did not impact the score of the review**\n\n* Please, introduce the notation $\\lesssim$.\n\n* In the first paragraph of page 2, \"the Efron-Stein inequality\".\n\n* In the paragraph before Definition 1, \"introduce the ~~following~~ concept of uniform stability*.\n\n* In Remark 1, use either \"uniformly bounded\" or \"uniform boundedness\".\n\n* Before (7), please mention explicitly that this holds with probability $1-\\delta$.\n\n* Before the acronym HTP, give the name \"Hard Threshold Pursuit\".\n\n* For completeness, in page 7, after the displayed equation before Definition 3 mentioned that $\\tilde{w}_{S,k}$ is the output of Algorithm 1.\n\n* In Section 3, describe what you mean by support to disambiguate with the support of distributions since you are also working with random objects in this work.\n\n* In the last paragraph in Section 4, either \"a cardinality constraint\" or \"cardinality constraints\".\n\n* In the Conclusion you don't mention anything about your results on inexact ERM with sparsity constraints. Maybe you want to write a little about that.\n\n* Throughout the text you are using $a$ for the constant on the sub-exponential term and $b$ for the constant on the sub-Gaussian term. However, in the first bullet point of Lemma 4, you reversed them.\n\n* Maybe you want to separate Remark 11 into two remarks. \n\n* At the beginning of Theorem 1 you say \"we pad the set with extra...\", please write explicitly which set you mean.\n\n* In the last paragraph of page 15: \"Based on the triangle and Jensen's inequalities we can show that\"\n\n* In (16) I think it should be $4 \\sqrt{2 \\kappa Nq} M_q$ instead of $2 \\sqrt{2 \\kappa Nq} M_q$.\n\n* The first inequality of part (a) of Theorem 3 on page 18 and the last inequality of part (b) on page 18 are not due to Hölder's inequality since it only holds for exponents $1 < r < s < \\infty$ where the first inequalities are strict. However, it does hold due to Jensen's inequality.\n\n* There is a typo in the first equation in the proof of Lemma 1. In the $\\ell(w^* w_{S|J};Z_j)$ it should be $\\ell(w^*_{S|J};Z_j)$.\n\n* In (23) instead of inequality $\\leq$ it should be $\\lesssim$.\n\n* In the array of equations and inequalities after (29) in the second inequality I believe you forgot a factor of $\\sqrt{2}$ (it should be a 4 instead of $2 \\sqrt{2}$) and it carries over that part.", "strength_and_weaknesses": "**Strengths**\n\n* The generalization error bounds under $L_q$-stability are near-optimal, improving upon the current bounds, and matching the rate of their uniform-stability counterparts.\n* The excess risk bounds under $L_q$-stability match the rate of the uniform-stability counterparts under the Bernstein condition and add a new form under the quadratic growth condition.\n* The bounds on inexact ERM with sparsity constraints include algorithms like iterative hard thresholding (IHT) and match the rate of current bounds under potentially milder conditions. \n\n**Weaknesses**\n\n* There are some parts in the text and the proofs where the contributions and influence of previous work are not clear. It would be good to clarify these parts.\n\n  * The bound in Proposition 1 is *[Celisse and Guedj 2016, Corollary D1]*, which is a Corollary of *[Boucheron et al 2005, Theorem 2]*. Although the text preceding the proposition mentions the references, the wording is slightly confusing.\n  * The proof of Theorem 1 essentially follows *[Bousquet et al 2020, proof of Theorem 4]* with little variation to adapt it to $L_q$ stability. The same happens with the proof of Theorem 2 which follows essentially the combination of Lemma 7 and Theorem 4 of *[Bousquet et al 2020]*. Also with the proof of Lemma 5 which follows *[Klochkov and Zhivotovskiy 2021, proof of Lemma 3.1]* and the subsequent beginning and part (a) of the proof of Theorem 3 which follows *[Klochkov and Zhivotovskiy 2021, proof of Theorem 1.1]*.\n\n* In the exposition of the results, sometimes the assumptions are unclear, usually due to the notation $\\lesssim$ (which needs to be introduced in the notation section).\n\n  * The standard results from the uniform-stability literature usually require the loss is bounded by some constant, say $L$. This usually appears in (2), (3), (4), and (5), even under the use of $\\lesssim$ to make this assumption explicit. Having these constants would help understand better the improvement of using $L_q$-stability. If they are not there, it would be good to explicitly mention these bounds hold under this assumption prior to their introduction.\n  * Similarly, in (5) the Bernstein condition constant is usually present to make sure this dependence is clear.\n  * The same happens when presenting the contributions in Section 1.2. \n  \n    * The generalization bound should have the constant $M_q$ demanding a finite moment $\\lVert \\ell(A(S);Z) \\rVert_q \\leq M_q$ or at least an explicit mention that this is required. \n\n    * The excess risk bound should either have the Bernstein constant $B$ and a bounded constant, or an explicit mention that these assumptions are required. Moreover, it should include the Lipschitz constant $G$ and the strong-convexity constant $\\mu$  or an explicit mention that these assumptions are required. \n\n* Algorithm 1 seems self-referential. Namely, note that $\\tilde{w}_{S,k} := \\argmin_{w \\in \\mathcal{W}, \\textnormal{supp}(w) \\subseteq \\tilde{J}} R_S(w)$ and $\\tilde{J} = \\textnormal{supp}(\\tilde{w}_{S,k})$. This made understanding the section a little more difficult.\n\n* Remark 10 seems a little unfair. It is comparing a bound for misspecified models *[Yuan and Li 2022, Theorem 3]* with a rate $\\mathcal{O}(1/N)$ with further assumptions with their $\\mathcal{O}(1/\\sqrt{N})$ bound on Theorem 4 with weaker assumptions. However, it does not consider the $\\mathcal{O}(1/\\sqrt{N})$ bound of the same paper *[Yuan and Li 2022, Theorem 1]* which has very similar assumptions (i.e. does not need a bounded parameter space nor a strongly convex population risk as this paper does but requires smoothness of the empirical risk) that can be similarly applicable.\n\n* The paper claims that it uses the developed theory to bound the excess risk of inexact ERM with sparsity constraints. This is not the case, the excess risk bounds are based on $L_q$-stability, yes, but don't use the theorems in Section 2. First, the assumptions are larger in that setting, and second, only some ideas of the proof of Theorem 3 are employed to prove Lemma 6 in the Appendix. \\\nI believe this should be clarified in the Abstract and the Introduction. Section 3 serves as a motivation for the importance of studying $L_q$-stability, but not for the usage of their generic bounds for $L_q$-stable algorithms, since they are not used there.\n\n* Could you please clarify or write explicitly in the text the final step in the proof of Theorem 3, part (a) and part (b)? That is, the step that follows the \"which implies that\" and \"which then implies\".\n\n* The exposition would be clearer if the excess risk bounds and concepts were also introduced in the problem setup instead of that later in Section 2.3. \n\n**References**\n\n*[Boucheron et al 2005]* Moment inequalities for functions of independent random variables. \\\n*[Celisse and Guedj 2016]* Stability revisited: new generalisation bounds for the leave-one-out. \\\n*[Bousquet et al 2020]* Sharper bounds for uniformly stable\nalgorithms. \\\n*[Klochkov and Zhivotovskiy 2021]* Stability and deviation optimal risk bounds with convergence rate o(1/n). \\\n*[Yuan and Li 2022]* Stability and risk bounds of iterative hard thresholding.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "O3ipLTDUOR", "reviewer": "Reviewer_6gau", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper derives near-optimal exponential generalization bounds for $L_q$-stable algorithms. Compared to uniformly stability, $L_q$-stability is weaker and distribution dependent. To establish sharper generalization bounds, they first present the moment inequality for sum of random functions that satisfy the $L_q$-norm bounded difference condition, which is an extension of theorem 4 in (Bousquet et al., 2022). With this concentration inequality, they derive generalization bound and excess risk bound for $L_q$-stable algorithms. Moreover, they derive exponential risk bounds for computationally tractable sparsity estimation algorithms.", "summary_of_the_review": "The paper derives some new exponential generalization bounds for $L_q$-stable algorithm. However, it is confusing for me to make bounded assumptions in the analysis of $L_q$-stable algorithms.", "strength_and_weaknesses": "Strengths:\n1. This paper derives near-optimal exponential generalization bounds for $L_q$-stable algorithms, which match the existing bounds of the uniformly stable algorithms. \n2. Based on the notion of $L_q$-stability, they derive exponential risk bounds for computationally tractable sparsity estimation algorithms under mild assumptions. \n3. To establish exponential generalization bounds for $L_q$-stable algorithms, they first extend the moment inequality in (Bousquet et al., 2022, Theorem 4) from under uniform bounded condition to $L_q$-norm bounded condition. The obtained concentration inequality can be applied to unbounded losses. \n\nWeaknesses:\n1. Theorem 2 is derived under $L_q$-norm boundness condition, which allows for learning with unbounded losses. Theorem 2 and Theorem 3 are both derived by applying the new moment inequality (Theorem 1). However, part (a) of theorem 3 requires the losses to be uniformly bounded. Compared to uniformly stability, $L_q$-stability is weaker since $L_q$-norm allows the losses to be unbounded. I am concerned about the incompatibility between the uniformly bounded assumption and the motivation of analysis of $L_q$-stability algorithm. Part (b) of theorem 3 assumes the loss to be Lipschitz with respect to the first argument. It is necessary to discuss the relationship between this Lipschitz assumption and bounded loss assumption.\n2. Theorem 3 extends the near-optimal exponential risk bounds from uniform stable algorithms to $L_q$-stable algorithms. Theorem 4 presents the theoretical results on the sparse excess risk of the inexact $L_0$-ERM problems. It seems that Theorem 4 is an isolated application of $L_q$-stability, which is not related to previous theorems in the paper. I would recommend including an explanation of the relationship between Theorem 4 and previous theorems.\n3. As pointed out in Remark 10, for misspecified sparsity models, their derived bound in Theorem 4 is slower than the existing results in (Yuan & Li, 2022, Theorem 3). They argue that their result is more broadly applicable. Besides the strong-signal condition, are there other assumptions that limit the application of results in (Yuan & Li, 2022, Theorem 3)? I would recommend including more discussions on differences of assumptions between Theorem 4 and results of (Yuan & Li, 2022, Theorem 3).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster