On the Generalization Error of Stochastic Mirror Descent for Quadratically-Bounded Losses: an Improved Analysis
Authors: Ta Duy Nguyen
Alina Ene
Huy Nguyen
Venue: NeurIPS 2023 poster (2023)
Keywords: high probability
generalization
convex optimization
nonconvex optimization
TL;DR: We propose a novel approach to show high probability generalization bounds of stochastic mirror descent for quadratically bounded losses

Abstract: In this work, we revisit the generalization error of stochastic mirror descent for quadratically bounded losses studied in Telgarsky (2022). Quadratically bounded losses is a broad class of loss functions, capturing both Lipschitz and smooth functions, for both regression and classification problems. We study the high probability generalization for this class of losses on linear predictors in both realizable and non-realizable cases when the data are sampled IID or from a Markov chain. The prior work relies on an intricate coupling argument between the iterates of the original problem and those projected onto a bounded domain. This approach enables blackbox application of concentration inequalities, but also leads to suboptimal guarantees due in part to the use of a union bound across all iterations. In this work, we depart significantly from the prior work of Telgarsky (2022), and introduce a novel approach for establishing high probability generalization guarantees. In contrast to the prior work, our work directly analyzes the moment generating function of a novel supermartingale sequence and leverages the structure of stochastic mirror descent. As a result, we obtain improved bounds in all aforementioned settings. Specifically, in the realizable case and non-realizable case with light-tailed sub-Gaussian data, we improve the bounds by a $\log T$ factor, matching the correct rates of $1/T$ and $1/\sqrt{T}$, respectively. In the more challenging case of heavy-tailed polynomial data, we improve the existing bound by a $\mathrm{poly}\ T$ factor.

On the Generalization Error of Stochastic Mirror Descent for Quadratically-Bouddee Losses: an Improved Analysis
Ta Duy Nguyen
Alina Ene Department of Computer Science Boston University aene@bu.c edu
Department of Computer Science Boston University edu
taduy@bu. edu
Huy Le Nguyen
Khoury College of Computer Sciences
Northeastern University
hu hu.aguyen@@nrttheateem edu
Abstract
In this work, we revisit the generalization eтrоr of stochastic mirror descent for quadratically bounded losses studied in Telgarsky (2022). Quadratically bounded losses is a broad class of loss functions, capturing both Lipschitz and smooth functions, for both regression and classification problems. We study the high probability generalization for this class of losses on linear predictors in both realizable and non-realizable cases when the data are sampled IID or from a Markov chain. The prior work relies
intricate coupling argument between the iterates of the original problem and those projected onto a bounded domain. This approach enables blackbox application of concentration inequalities, but also leads to suboptimal guarantees due in part to the use a union bound across all iterations. In this work, we depart significantly from the prior work of Telgarsky (2022), and introduce a novel approach for establishing high probability generalization guarantees. In contrast the prior work, work directly analyzes the moment generating function a novel supermartingale sequence and leverages the structure of stochastic mirror descent. As a result, obtain improved bounds in all aforementioned settings. Specifically, in the realizable case and non realizaae case with light-tailed sub-Gaussian data, improve the bounds by log T factor, matching the correct rates of 1/T and 1/ 1/VT, respectively. In the more challenging case of haavy- polynomial data, we improve the existing bound by a poly factor.
Introduction
Along with convergence analysis of optimization methods, understanding the generalization of models trained by these methods on unseen data is an important question in machine learning. However, despite the number of works attempting answer it, the problem has not been fully understood, in the simplest setting of linear predictors constructed with the standard stochastic gradient/mirror descent. A great part of prior works 33
31 32 focus only the generalization linearly separable data and/or models trained with specific losses with exponentially decaying tails such as logistic loss. The question of what
15 30
guarantee beyond these settings remains open.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

proposes new approach to analyze the generalization error with high probability of stochastic mirror descent for broad class of quadratically bounded losses, beyond the realizable setting. This class of losses encapsulates both Lipschitz and smooth functions, for both regression and classification problems. The obtained bounds complement existing in-expectation bounds [T2] and nearly match the counterpart of convergence rates in optimization. While this result pushes forward the state of the art, the obtained guarantees do not completely resolve the problem. The central piece of the proposed approach is "coupling" technique between the iterates of the original problem and those projected onto a bounded domain. In this technique, one first constrains the problem in bounded domain with well chosen diameter. The bounded domain diameter allows to apply concentration inequalities as a blackbox and obtain bounds in high probability. Then using an inductive argument and union bound across all iterations, one can show that the iterates in the original problem coincide with the ones in the constrained problem. Due to the union bound, the success probability decreases from algorithm. This loss translates to a milder log T factor loss in the guarantee in the case of realizable data and more significant poly T factor loss in the non-realizable setting when the data has polynomial tails. Thus a natural question arises of whether we can obtain a stronger analysis that closes these remaining gaps.
Recently, B35
5 to T5, where T is the number of iterations in the
In this paper, we revisit these generalization bounds for quadratically bounded losses by [35] We introduce novel approach to analyze the generalization errors of stochastic mirror descent in both realizable and non non-realizable cases when the data are sampled IID or from a Markov chain. In all these cases, remove the need to use the union bound argument, thus preventing the loss in the success probability. This translates to the following improvements:
In the realizable, and the non-realizable cases with uub-gaussian tailed data and Markovian data, we improve the bounds by a log factor. This improvement comes from analyzing the moment generating function of a martingale difference sequence with well-chosen coefficients. In these cases, we also remove the necessity of using the coupling-bass argument used in the same work by (35]. Instead, by solely making use of the problem structure, we arrive at the same conclusion that with high probability, the iterates of stochastic mirror descent for quadratically bounded losses behave as if the problem domain is bounded.
In the non-realizable case with polynomial tailed data, we improve the existing bound by poly T factor. Due to the polynomial dependency on 8. being able to maintain the same success probability through all iterations crucial in this case. Unlike the previous work, we rely on a truncation technique. Using a more refined analysis of the truncated random variables, in combination with suitable concentration inequalities and the coupling technique, we improve the existing bounds significantly.
1.1 Related Work
Broadly speaking, there is a rich body of works in optimization and generalization that provide convergence guarantees and generalization bounds for stochastic methods. Earlier works often focus
on in-expectation bounds [8] 24, 26, 18
12 3 and bounds in high probability [16]
28
14
[3] for
problems with bounded domains or under various additional assumptions such strong convexity,
noise with light tails. Recent developments for optimization [25] 10, 20 23 [1 17
[9] 19 29 22
able to handle unconstrained problems and relax these assumptions, but also require changes to the algorithm such as gradient clipping.
In generalization error analysis, specifically, number of prior works, including 33 15 30 31 (2)
focus only on linearly separable data. Among these, [33] 15] 32) only deal with exponentially tailed losses while (30 31 show generalization bounds for general smooth convex losses. Our work,
similarly to (35,, goes beyond the realizable setting and specific losses. We show high probability generalization bounds in both realizable and non-realizable settings for the broad class of quadratically bounded losses, for both regression and classification problems.
Other related works include the line of works that examine generalization errors via algorithmic stability. The works by [12 5 I show the generalization error of an arbitrary algorithm via a quantity called uniform stability. By bounding this quantity for specific algorithms on a fixed training dataset, they derive generalization bounds. Our work focuses on different setting where we assume the algorithm has access to fresh data sample in each iteration. In this regard, the setting in our work.

---

as well as the prior work by [351. stays closer to the world of optimization. However, in contrast to the optimization world in which we commonly impose assumptions on the stochastic gradients (such as having bounded variance or sub-gaussian noise), we make assumptions on the data (such as sub-gaussian or polynomial tailed data). This difference introduces several challenges which we overcome in our work.
The main point of reference for this paper the work by 33 This work develops a "coupling" technique to bound the generalization error of stochastic mirror descent for quadratically bounded losses. This technique has been employed in prior works [O probability convergence bounds of stochastic methods in optimization. Our work improves their results by using different approach that takes closer look at the mechanism of the concentration inequalities and leverages the problem structure. When the data are bounded or have sub-gaussian tails, analyzing the moment generating function of novel martingale difference sequence allows us to maintain the same success probability, without using either the coupling technique or the union bound. This new analysis, however, does not change the observation by [55 that the iterates of the unconstrained and the constrained problems coincide with high probability. When the data have polynomial tail, we rely on a truncation technique. In this case, the coupling technique is necessary but not the union bound, and we are still able significantly improve the success rate.
22 to obtain high
In terms of techniques, the work by 21 for optimization is the closest ours. In this work, the authors develop the whitebox approach to analyzing stochastic methods for optimization with light- tailed noise. In this work, we study generalization errors. Moreover, in all settings, our choice of martingale difference sequences and coefficients are significant departure from the prior work. In particular, in (1 the choice of coefficients only depends on the problem parameters whereas in the realizable case, our coefficients depend also on the historical data. Our approach also allows for flexible use of an induction argument without decreasing the success probability, while in [21] the bounds are simpler and can be easily achieved in a single step.
2 Preliminaries
In this section, we provide the general set up and necessary notations before analyzing stochastic mirror descent in the subsequent sections. Overall, we closely follow notations used in [35..
Domain and norms. In this work, we consider Xhe domain of the problem to be a closed convex set or Rdd We will use ||-|| to denote arbitrary norm X' and let I1-11. be its dual norm. We define the Bregman divergence D (w: v) ri(w - (/()) (V)(()), w v) where Rd RR a differentiable function that is --strongly convex with respect to the norm |1-1|-
Loss functions. Each loss function é R R Rz0 in our consideration can be written using a convex scalar function ? in one of the two following forms: 1) Ely. ;) = (ssign(y)0) where sign(y) = 1 if y 2 0 and = -1 otherwise; and 2) Ely, 7) = E(y D) The first form captures classification losses and the second regression losses. We will assume that subgradients de of in the second argument always exist, and let E' denote a subgradient in de. For a function f. we also use [[](w))] == sup [l|g|] g (f()).
). We further make the following assumptions, introduced in 351 as quadratic boundedness and self-boundedness.
Assumption 1. We assume that e is (C1, C2) (eJ--uuddraiically-bbunde for some constants C₁, C2 2 0, i.., for all y, 9
1r D S Ci
+ (7)
This condition captures both classes of Lipschitz and smooth functions. Indeed, Lemma 1.2 from 35 shows that a-Lipschitz functions are (a, O)--quadratically-boonde while 3-smooth functions
are [a((0) ( -quudratiicall--boudee..
Assumption 2.
In the realizable setting, we assume that E is p-self-bounding. i.e., ? satisfies (x))² < 22((2) for all R.
The second assumption is a generalization of smoothness. This assumption is satisfied by smooth losses but also certain non-smooth losses such as the exponential loss. This condition is necessary in the current analysis to prove T/T rates in the realizable setting. The readers can refer to 34 35 for more detailed discussion on this assumption.
3

---

Algorithm Stochastic Mirror Descent
Input wp. step size 7
For in 1 1...I 9i E dee (l(
Wy = arg min (ngg, w) + Da (w; wx-1))
Assumptions and 2 are satisfied by commonly used loss functions in machine learning. These include the logistic loss E(y. D) In(1 + exp(-yÿ) and the squared loss Eyy 77) - [ - 7)² (see Lemma 1.4 in (35).
For the loss function and the configuration w, and sample (z. y) where x denotes the attribute and the label, we will write ε2,y E(y, w" x)). We state the following crucial lemma which is the same as Lemma A.I in (35], whose proof will be omitted.
Lemma 1 (Lemma A.I in (35))). Suppose is (C1, (G)--uaddaaically-ooneeee and Bg 2 is given. Given (z, y) such that max {| [y] & Bg and any u, U,
10l (u)ll. (u)ll - B2 (C1 + C2 (1 + [m]l)) (1x (x)( S B2 ||u all (C1 + Bz (1 [[l])))
Risk, IID and Markovian data. When sample (æt,, Ui) arrives in iteration i of algorithm, we will use the notation ((w) = E(y,, w zz). For an algorithm of T iterations, we use F, = ((x1, .i..... (Iz, 3t)) denote the natural filtration up to and including time t. When the data are IID and generated from a distribution म,, we define the risk
R(w)= = ((),))~ [[ wT))]:
In contrast to IID data, Markovian data come from a stochastic process. This setting has also been considered in (4. We let P be the distribution of (Iz, y)) at iteration t conditioned on F... We make the following assumption regarding the uniform mixing time of the stochastic process. Note that
similar assumptions have also appeared in [35 4
Assumption We assume that for some 7, 2 0 of our choice, there is a distribution n such that
sup sup TV (P!+T T) S. E2
refer to the triple (T, T, an approximate stationarity witness. We then define the risk according to the approximate stationary distribution m: R(w) = (a,y)>< [f(y, w" w²':))
Algorithm. Stochastic Mirror Descent is given in Algorithm [ In this algorithm, for the simplicity of the analysis, we consider a fixed step size In each iteration, we pick subgradient ge E de, (wr-1) and perform the update step.
We finally introduce a standard lemma used in the analysis of Stochastic Mirror Descent. Lemma 2. For and Wret E X, we have
n72 11 11.
Dy (Wreti Wx+1) D (Weeti w:) S (le+1 (Weet) le+1 (w,))
Other notations. We will Whet refer to comparator of interest. For the simplicity of the exposition, we let Do = De (wref: Wg), and R inf R(v). For a loss function that is (C1, C2) couudrraticlly-bbundte we let C4 C C - [[.l))))
3 Generalization bounds of SMD for IID data
In this section, we distinguish between two cases: the realizable case and the non-realizable case. In the realizable case, there exists an optimal solution w= E X' such that R(w*) = 0. We will show that under mild assumptions, the risks of the solutions output by Algorithm I are bounded by (1ITT). In the non-realizable case, we will show, on the other hand, weaker statement that the excess risks of the solutions are bounded by O(I/VT).

---

3.1 Realizable case
In the realizable case, the comparator Wref not necessarily the global minimizer. To show the 1/T rate, we will assume Wref satisfies R (Wreet) S pD (Wref: Wo)/ IT and that the loss at Wref is bounded. The guarantee for the iterates of Algorithm is provided in Theorem 3
and p-self-boundigg Given T, ((21,3)) UET are IID samples with max { < 1..1] S almost surely, Wxet satisfies R(Wret) S (Wooff; Wo)/T, and maxter le+1 (Wret) I C3 almost surely. Then S 1. with probability at least - for every 0 S k S -1
Theorem 3. Suppose i is convex, (C1, C2) l-gguudratialll-bbnnndee
2p.
16D (Wrefi Wk+1)
C
R(mr)= +
I
+ +R(we)))
k+1 t=0
5(k + 1)m
k+1
where C' = 16Ca log 8 V 4 + 4m + (oDo+ + 2 FFC)) with y max { log }
5
The analysis of Theorem 3 relies on the use of concentration inequalities. In contrast to existing blackbox, we will make use of the mechanism for
works that utilize concentration inequalities proving concentration inequalities in order to obtain stronger guarantees. The type of concentration inequalities we consider are shown by analyzing the moment generating function of suitably chosen martingale sequences. We will use Lemma [4| (Appendix) which gives basic incquality that bounds the moment generating function of bounded random variable. To start the analysis, we use Lemma
2 and Assumption 2 to obtain
Lemma 4, For all t 2 0, we have
D (Wref; W++1) Day (Weef; Wx) S mlet1 (Wret)
? 2
fett (wee;
and hence, Du (Wref; wx) S Dy (Wref; Wo) +n Σ la (Wret) Do 17 Σ Es (Wret)
First, let us pay attention to the term Ei= l (Wret). Recall that the terms E (Wret) are non-negative and bounded by a constant C3 almost surely. We can analyze the term Σ & (Wret) which upper bounds all sums Ei=1 &s (Wret) by studying its moment generating function (or via concentration inequality). We state this bound in the next lemma and defer the proof to the appendix.
Lemma 5. With probability al least 5, Ei=
1 ls (Wret) S [R)(w)))) + C3 log g-
Lemma and 1 and the assumption that R(wret) = O (1/T) imply that with probability at least 1 8, D. (Wiett W.) is bounded. In other words, with probability at least - 8, the iterates w, all lie in a bounded region. One could therefore proceed to assume that the problem domain is simply this bounded ball around Wref. This is the basic idea behind the "coupling" technique demonstrated in [35]. However, the important question is how to obtain a bound for the risk of all iterates even when are working with problem with unbounded domain. Here, not paying close attention to the structure of the problem and the blackbox use of concentration inequalities lead to suboptimal bounds. On the other hand, discussed above, erucial novelty in analysis is the choice of supermartingale difference sequence, defined in the proof below. By working from first principles using moment generating function of this sequence, derive two conclusions: 1) an improved risk bound can be obtained, and 2) the coupling technique is not necessary.
Proof Sketch. Towards bounding the risk Ek R(wx), we define random variables
1
Z. an (R(w:)- - R(wser) - l (Wret) + 2z (Do) (Wrefi Wc+1) - D (Wreti w))
2
3
2 (R(weet) R(we)),
4A 1LST-
16
= 1, 1,00g 1
where 2,
= max
n04h 217 2Do + 2n Ei_ 1 & (Weet
5

---

and we let St = Σ ==0
Z
0A s 1. The reason to define these variables is because from
Lemma we can bound
E exp (Z)) Fil x exp
16 26 (R(wret) R(wx)))
207 (R(w;) R(wrer) le+1 (Wrer)) + 2a (nlet2 (wzet) !
<B
exp
=E
exp
2+) (R(w:) R(wret) le+1 (Wret) (u+)( Fe
where now inside the expectation, have the term R(w))) R(Wret) ) + le+1 (Wret) l++1 (we) which has expectation 0. Let C4 = C1 + C2 + [|Wret))) we can bound
7 (R(ws)- - R(Wret) + L (Wrer) le+ l (wx)) & n/as || wa
and 2,
Now we can apply Lemma 14 (Appendix) bound
well
3 2n (R + R((w)))
exx (Ze)
Fi]
exp
16
I cxp
31
44 =
(R(ws) R(Wret) leta (Wret) le+1(we)) [
3 21
(fe41(Wret)) let1 - (we)) Fi]
exp
16
3
I cxp
ca Wree
well well (le+1 (Wret) le ( Fil
16
3
2t7 (R(wret) R(we))
exp
16
Therefore E (exp (2x) Fi] < and hence (exp (8.) is supermartingale. By Ville's inequality, have with probability at least 1 5, for all 0 < k <
Ze S log
Expanding this inequality, in combination with Lemma obtain the conclusion.
Remark 6. The new analysis does not change the conclusion observed in 35 probability, the iterate sequence (w=) behaves as if the domain of the problem is bounded. We improve the probability that this event happens.
that is, with high
3.2
Non-realizable
In the non-realizable case, we do not aim for 1/T but only 1/v rates. Hence we do not assume that the comparator Whet satisfies R(wret) pD (Wref; wo)/T but rather the following assumption the excess risk:
Assumption 4. Ret = infoex R(v), assume that R(wrer) R (w(werring))
/T
We also relax the assumption the data samples. In the previous case, the data are bounded, i.c [||=|] |y] < 1 a.s. We will consider in this section two settings, one when the data come from Lub-Gaussian distribution and one when the data distribution has a polynomial tail.
Remark on Theorem 10 in 35 There seems to be an issue with the proof of Theorem 10 in [35]
The proof uses a variant of Azuma's inequality (337) Problem 3.11) which allows the ranges of the random variables to not be specified up front. However, when bounding the range of relevant random variables, the proof uses Z++1. which is correlated with the data | ll. and Jt+11 Thus the condition of Azuma's 's inequality not satisfied. We do see an immediate way to resolve this problem. In the following, consider separately the two cases of sub- Gaussian and polynomial

---

tailed data for which we use different proof techniques to show the error bounds. In the first case of IID data with sub-Gaussian tails, we proceed by bounding the moment generating function of well-chosen martingale sequence. In the second case of IID data with polynomial tails, we introduce a truncation technique. In both cases, we are able to obtained better bounds compared with [35].
3.2.1 IID data with sub-Gaussian tails
We will show the following guarantee:
Theorem 7. Suppose & is convex, (C1, 1aa,-CC)-quuaa quadratically--ouudee Given T, ((01, Bil)es are IID samples with Qt = max 1, | and there exists a 2 0 such that for all X
vell))
max E [exp (A (Q²
- E [Q,]))] [oxp (A (Q: - -E S exp (X20²)
Let μn E EQd and μ2 [Qi]. Suppose that Wret satisfies Assumption 4. Then for nj S
with probability at least 28, for every 0 S S
102 T22t0 /
/T
(R(w)) RR) + Do (Wrefi Wk+1) 17 (k 1)
Ri2
+
17 (1: +
where R² = 16C2 (o² 4nf) log " + (1
(Tw2 + 20 TTog } 0(1).
Remark For zero-mean sub- Gabssiann variable X, the definition E lxxp (AX)) S exp (X²x²) for all À is equivalent to E [exp [A²x²)] I exp (X²o²) for all S X S 1 (see (38). The lemma below shows property of sub-Gaussian variables under scaling and translating. First let consider
Σ Ot Similar to Lemma 5 by bounding the moment generating function of this term, have
the following (see also Section B4 in (35))
Lemma 9, With probability at least - 8, Et= Oi S TTp2 + 20 T 3-
The proof of this Theorem uses the technique developed in 21 We will also analyze the moment generating function of suitable martingale sequence. However, the choice of the coefficients will differ significantly from the previous proof. In this case the structure of the problem is deeply integrated into the analysis of the martingale. We define
Proof of Theorem 7
2: = 2 (R(w:) R R(Wret) )) + ze (D (Weefi We+1) Day (Wrofi We))
1
2 20 119.+111 42,27 (o² + 444) De (Wyer; wr)
VO St
where 2, 4n2C3 (02 + 417) (1+++1)
V V-1SIST-1
and let S: = Et= Zú: 4A S - 1. By Lemma we have
Z, + 42 C2 (02 4p² D v (Weeti wx) zen (R(w)) R(wret) + let1 (Weet) - L (w:)
where we have E [R(ww) we) - R( (Wret) l (Wret) l (we)) 0, and using the same notation C₁ = C1 + C2 (1 + ||lred|] (l), by Lemma !
(R(w)) R(Wret) +e41 (Weet) 1 (w:))
< 4++1 (Weet) - l441 (wa)) + R(ww) R( ((Wwer))
1641 (Wret) l (w:)) + E [Ien, (w:) l Lx. (Wror)]]
< (Q: + m1) || well C4 = ((Q: u1) + 2 || - well C4
Hence applying Lemma 15 we have
E (exp (7x) exp 1 (o² + 4p²) D& (Wref; W:))
= (exp (zm (R(w;) R(wiet) + let1 (Wret) l.t1 (wx)) Fil
7

---

sexp C2 Wret will 11 112 4uf)
eexp (42 C (o² + 4n²) D (Wret; W))
Therefore E lexp (Z,) Fi] I and hence (exp (St)) is supermartingale By Ville's inequality, we have with probability at least 1 6, for all 0 2 k 1 T
Σ t=
Z S log
Expanding this inequality we have
R(w)) + 2n Do (Wrefi Wk++1)
1=0 0
1
log
+ 2-1 Do + -7R(Weee Σ
2x +
Σ 1=
20 119c+1ll 11
0
2
1=0
k Σ> (=0
(2t + 42,11 (0² + 4p1)
22-1)
D (1 wi))
50
(a)
1
1
S
log + z- Do + 1/R((rret)
Σ
2t
+ 2
z 2 |
where for (a), by the choice of 2t = (P we have 2--1 - 2t 2
C2 (o² + 4pf). We highlight that this where the structure of the problem comes into play. That is, by setting appropriate coefficients, we can leverage gain in the distance in the martingale difference sequence ((2, - -11 Dy (Wrefi wx)) to cancel out the loss from bounding the moment generating function (4 (o² + 4uf) D (Wref; w:)). Another important property of the sequence (z+) is that it is decreasing sequence and & s 2 for all t, k. Hence have
1
((w,)) R²) + Dy (Wrefs Wk+1)
1 S407 (o² + 41²²) log " (T +++ (+) 2Do + 2 (R(wee)) - -R') R²) + 1) + n
1| 1t 11:
Combined with Lemma with probability at least - 25, for all 0 S k S
(R(w)) - R²) + De (Wref; Wx+1)
<4C? (o² + 4nf) log ~" (T +1+++10 k) + 2Du + 2 - R²) + 1) + 17²
11 11:
t=0
and Σ Qt < Tu2 20 v Tlog 1 8
Conditioned on this event, we will prove by induction that
Do (Wref; Wi)
R = 16C2 (0² + 4nf) log T + 4D. + 4DoTVT + 4r207 Tue + 20 T log 1 x
For the base case lo = 0. is trivial. Suppose for all S k we have D (Wref: we) S R². now we prove for + By Lemma I
k Lin (C) + (1 || 11) s n?
19++ 1 < n Σ
Σ
Pup (C4 + C2 I - wretl) )
t=0
8

---

A+1
- 22 Σ oi + 2nj 2r Σ
22+1 11,0 - wrerl
1=1
1=
S 1n² (20 + 2C3R3)
T Tlog THe + 20
Therefore
D& (Wrefi Wk+1) S 8C9 (o² 4111) log T +22 + 2 (R(Wsot) n())(k + 1)
t1p (20) + 123
(Twa + 20 Tlog
R²
$ 2
4n Tu2 20 Tlog R² R²
Finally we obtain, 77 Ex (R(w;) R*) + De (Wrefi Wk+1) R2, needed.
3.2.2 IID data with polynomial tails
Theorem 10. Suppose f is convex, (C1, C2) quadraticalll bounded. Given T, ((1), W)ser are IID samples with Qt max (1, || [ (2) and some 2 there exists M 2 E such that for all
{B - - [ S M
maxx sup 2SrS22p
[|Q, E (QJIT), sup 25rSp
Let #1 = E [Qq] and p2 E [Q:]. Suppose that Wret satisfies Assumption 4. Then for S
with probability at least 1 - 36, for every 0 < TT-1
(716
(R(w:) - -R*) + Dv (wrof;
R²
Σ - 1 =
(k 1)
21 (k 1)
where R = max 6 (000(1++VV (1+7VT) + +,² (T22 + 22M (2)) ()))))))=))))) (7
(MT) 1/20
2/1) + v log TTT (annCaaa 01) - max {1, log 3)
Remark 11. Since p 2 2, the rate O - log 1
(t)+))
29
This rate improves over
the o ((7tz t f) log $ rate by 35 by a polynomial factor T log in the high
probability regime where pTly(T)
We will give a proof sketch for this theorem. The full proof is deferred the appendix.
Proof Sketch. The heavy tailed distribution of the data does not allow to analyze the moment generating function. this case, we rely on the coupling technique as in [35]. Since it is not possible to apply Azuma's inequality due to the bounds the variables being not measurable, and the variables are heavy tailed, we use truncation technique. We define,
Ut = arg
min {mnge (V: (v:-1), w) + Do (wi v+-1))
where we use ge (1;-)) to denote the gradient at U using the same data point (xt, y1) when computing wa and define
U, (R(v)) R(wier) + let1 (Weet) l (vt)

---

Ut Pt =
| E (A+ 2p1) RCa
(A + 2p1) ssin (U))
otherwise
MT
1/2p
where A
and B, U. Pr-
8
We can write
Σ
U,
Σ t=
(P.
E E Fi.)
Σ B B [A] B
1=
We bound Σ Di= (Pr E [P. Fel) by applying Freedman's inequality. The terms Ei E[P Fil and Σi= Bg are both the bias terms can be bounded by analyzing the tail of the distribution and Markov's s inequality. We also use Lemma 12 to bound Σ I19t+1 (vx))l Finally, using the induction technique, we can prove that w = U2 with high probability and obtain the desired result.
With probability 2 21-8, 8, E Qi - T22 + 2MVT (2)²
Lemma 12 (Lemma A.5 from 35
Generalization bounds of SMD for Markovian data
The final result we present in this paper is the following theorem for the case when the data are sampled from a Markov chain.
Theorem 13. Suppose is convex, (O1, -uaadratai bounded. Given T, ((I,, B()ssT are sampled from a Markov chain with max || 11: bullt S and (T,,,== +/) is an approximate
with stationarity witness. Suppose that Wset satisfies Assumption 4. Then for S 20 T(1+2)) probability least for every 0 T
k (R(w) R²) + D& (Whet; Wk+1)
R²
11 (k: +1 2n (k + 1)
where R = max {
{V (2Do + 2n + 161 3 2TT ) .
2n/4 + 4npTCa) =0 and C4 = C1 + C2 + Wrerl). |/lthhlll
We will give proof sketch for this theorem.
Proof Sketch. The proof of this Theorem follow similarly to that of Theorem 7 is we need to bound different martingale difference sequences in the form of
The difference here
E [e+(++)+ (Wret) Fri+s] -E [C<(+1)+5 (Wri+s) Frits] +(o-)))1) (woret) (Writs)
0 S j T 1, < T-1-1 We also need the assumption on the approximate stationarity
witness to see that
RRw,.) R R(wort) - E [letr (Wrot) | Fi. + E (C+tr (wx) Fi]] <CaRe.
Now we only need the union bound over 7 sequences, instead all iterations. The success probability will decrease from 1 - 8 to - 1-8
5
Conclusion
In this paper, we show a new approach analyze the generalization error of SMD for quadratically bounded losses. Our approach improves logarithmic factor for the realizable setting and non- realizable setting with light tailed data and poly T factor for the non-realizable setting with polynomial tailed data from the prior work by [3]. An inherent limitation of the current approach is the assumption that we can obtain a fresh sample in each iteration, whereas training data is still not well understood. In the realizable setting, we require that the data is bounded, as opposed to more relaxed assumptions in the non-realizable settings. We leave the question of resolving these issues for future works.
setting with finite
10

---

Acknowledgement
TDN and AE were supported in part by NSF CAREER grant CCF-1750333, NSF grant III-1905100 10, and an Alfred P. Sloan Research Fellowship. HN was supported by NSF CAREER grant CCF. 1750716 and NSF grant 2611
References
[1] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses, Advances in Neural Information Processing Systems, 33:4381-4444 1-191,, 2020.
[2] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-6200666006 PMLR, 2020.
[3] Radu Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx. Fast stochastic bregman gradient methods: Sharp analysis and variance reduction. In International Conference on Machine Learning, pages 2815-2825. PMLR, 2021.
[4] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4): 1578, 2012.
[5] Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. Advances Neural Information Processing Systems, 31, 2018.
[6] Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
[7] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[8] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4): 1469-14411 2012.
[9] Eduard Gorbunov, Marina Danilova, David Dobre, Pavel Dvurechenskii, Alexander Gasnikov, and Gauthier Gidel. Clipped stochastic methods for variational inequalities with heavy-tailed noise. Advances Neural Information Processing Systems, 1231119931333 2022.
[10] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with
heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042-15053 2020.
[11] Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexander Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint 21X.::2106.05558, 2021.
[12] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[13] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579-1613. PMLR, 2019.
[14] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1):2489-2512 2014.
[15] Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 1803.0000 2018.

---

[16] Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. Advances in Neural Information Processing Systems. 21, 2008.
[17] Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. In International Conference Learning Representations, 2021.
[18] Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.033329 2020.
[19] Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In International Conference on Machine Learning, pages 12931-12963. PMLR, 2022.
[20] Xiaoyu Li and Francesco Orabona. high probability analysis of adaptive sgd with momentum. arXiv preprint arXiv:2007.14294, 2020.
[21] Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Le Nguyen. High probability convergence of stochastic gradient methods. arXiv preprint arXiv:2302.1484. 2023.
[22] Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2302.06763, 2023.
[23] Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent. arXiv preprint vrXiv:2006.06614 2020.
[24] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
[25] Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 8019):1607-1627, 2019.
[26] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[27] Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Le Nguyen. High probability convergence of clipped-sgd under heavy-tailed noise. arXiv preprint vnXiv:2302.05433 2023.
[28] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprini arXiv: /tt:://00.00 109.5647, 2011.
[29] Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High- high-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. arXiv 2023.
preprint
[30] Matan Schliserman and Tomer Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In Conference on Learning Theory, pages 3380-3394 PMLR, 2022.
[31] Matan Schliserman and Tomer Koren. Tight risk bounds for gradient descent on separable data. arXiv preprint a:Xiv:2303.01/35, 2023.
[32] Ohad Shamir. Gradient methods never overfit on separable data. The Journal of Machine Learning Research, 22(1)33847-3866 2021.
[33] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-288 28788 2018
12

---

[34] Matus Telgarsky. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pages 307-315. PMLR, 2013.
[35] Matus Telgarsky. Stochastic linear optimization never overfits with quadraticaly--ooundedd losses general data. In Conference on Learning Theory, pages 5453-5488. PMLR, 2022.
[36] Joel Tropp. Freedman's inequality for matrix martingales. 2011.
[37] van Handel. Ape 550: Probability in high dimension. Lecture Notes. Princeton University. Retrieved from https:/wweb. math. princeton. edu/vaa/AAPC550. pdf on December, 21:2016 6 2016.
[38] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
13

---

A
Concentration Inequalities
Lemma 14. Let X be random variable such that IE [X] and |X| S R almost surely. Then for
0 OSAS 1 R
E exxp (AX) exp
4 X
(xTE(x2)) [x3]
The following lemma is similar to Lemma 2.2 in 21
Lemma 15. Suppose that Q satisfies for all 0 S S J. eexp (X²Q²) I exp (X²a²).
Then for
variable such that E [X] = and [X] S a (Q + b) for some a 2 0 then for all X 2
E exp (AX)) - exp (2x² (o² + +b)))
In particular, if O we can have lighter constant: E (exp (AX)I S exp (AZu2o2).
Proof. We consider E [exp (AX)]
If SAS V2ao
then using exp (x) S + exp (x²)
E Texp (AX))
< exp (A2x²)]
- exp (x²a² (Q+
< E2 eep (2X² + 2x))
< exp (2x²a²63) E [exp (2X²
exp
(2X²a² (o² (1))
Otherwise S >/22a
X²
E (exp (AX)] SE exp (X2'002
4a202
(Q (Q + 6)²
Sexp (X² (2²a²00) E
exp
4g²
Q² + b2
sexp (1' E
exp
20
6²
s (XP2202 exp
20
exp
2
S eexp(1222 exp (X2a²t²) exp (X²a²02)
S exp (2X2 (o² + +b)))
Theorem 16 (Freedman's inequality 77 361). Let (Xt)121 be martingale difference sequence.
Assume that there exists a constant e such that Xel S c almost surely for all t 2 and define
of
E X2
X, X. X1).
Then for all > F > and T 2
T
T
62
Pr
TT TTI1
1:
X
b and
of oo
Σ 1=1
< F
< 2exp 2F + 2ch
B Missing Proofs
Proof of Lemma 2
Using the optimality condition
(19:4) + Veb(we1)) - Veb(w,), Whet Wx41) 2 0
14

---

we have
(19++1, Wref)
(19++1, We+1 Wret) + (199+11, Wi w/++1
(Vi((u++1) Vib(we), Wree 10 + (199++1, Wlt - w(++1
Do (Weef w/) - D (Wief: w(+1) - Dy. (Wi+1; w/) + (199+11 w6+1)
1
D e (Wref; Wt) Dey (Wref; We+ 1) - |wu, - we++lll 112 + (119+11, wi wx41)
2
7/2
< Do (Wrof; Wt) Di (Wroff We+
+ 2
|1 11
Hence
Du (Wreti (141)- - Dw (Wrefi wx) S (119--1 Wrot - we) + .12
2 119.+112
S 1y (le+1 (Wret) - Let1 (wi)) + n/²
119++a112
needed.
Proof of Lemma
We have
112
Do (Wrefi Wx+1) - D (Wreti wx) S n (l++1 (Wret) - le41 (wx)) + 19 ll:
2
11²
< (le+1 (Wret) - le+1 (wx))
l
t+1 (wr)²
2
S 1) (c++1 (Wrot) - l1+1 (w:)) 11² p (
n (Wret) (4r)(wr) ml241 (Wret)-
Summing up, we have, for any S
Dy (Weeft wp)= < D (Wret' wo) + Σ 4 (Wret) = Do + 17 > & (Wret)
i=1
Proof of Lemma
We have 1es (wret) - R(Wret)) s
max (Es (Wret), R(Weet)) S C3s thus by
lemma 14 for
Cs
E (exp (A (4, (Wret) - R(Wrer)))]
x (e, (Wret) R R( ))
I cxp
(a)
x ( (w)rer)])
exp
- 4 Xx²CxR(wror)
3
S exp ( (XAR(wnrt):
exp
where for (a) we use E independent random variables, have
(x
E X2| and for (b) we use ls (Wret) S Cz. Since & (Wret)
T
]]
E
exp
A
Σ
(& (Wrer) - R(wrer))
E
II exp (A (es (Wret) R R(wret)))
T
T
(3 (xR(uret) - exp (XTR(Wte))
E lexp (A (E, (Weet) - R((rre)))
< II
=exp
15

---

Hence by Markov's inequality
T
Pr
(Ee (Wret) - R(Wret)) 2 XTR(wuret) + log
4
8
==1
Pr
exp
(ls (Wret) R(wret))
2 exp
1
AXTR (
(3
]
I8
exp
(6, (Wret) R(wree))))
Σ 8
exp
(EXTR(Weel)
Choose A
we have with probability least
8
C3
(le (Wret) - R(Waet)) - TR((wat)) + C3 Czlog 1
Proof of Theorem
Towards bounding the risk Σ R(w.), we define random variables
1
Z, 2 . (R(w)) R(weet) - let1 (Wret) + (D (Wrefi wc+1) Dei (Wret' wc))
u1ll (R(wret) + R(w+));
vo StsT-1
16
max 1, 1, 1
where 2
n/Ca n/Ca// 2 2Do + 2n Ei= & (Wret)
and S.
Σ Z,:
VOSIST-1
i=0
The reason define these variables is because from Lemma 4 we can bound
E
(exp (Z.) [F] x cxp
16 2n (R(wret) + R(wx))
<E
exp
2077 (R(w;)
R(wrer) - le+1 (Wret)) + zạ (nle+1 (wret) - 2 2
((na(ui)) Fr
=E
exp
2,77 (R(w:)
R((ret) + ( - (w)() Fe
where now inside the expectation, we have the term R(w)) - R(w,et) + le+1 (Weet) - let1 (we)
which has expectation This reminds us of Lemma I4 To use this lemma, we notice that, by the assumption that the samples are IID with max {1|=]], Tel } < 1 and Lemma
(x..y(err))
(wx)] S ||WYor - we || (Ci C2(1 + [[wrrll)))
C4
We also have
R(w)) R(wrer)) Ila (Wret) (we)l S C4 W|wref - well
Therefore
1 (R(w)) R((wrt) let1 (Wret) leta(1ot)) nnas ||Wret wall
2
By the choice of we have
24 <
nC1N 200'2n0s + 2D. 2n Ei= ls (weet
m/C'v 22'//2Dy (Wreti wt)
14C4 Weee w/
16

---

Now we can apply Lemma 14 to bound
3 (6 2m (R(wret) + R(wr))
eexp
(Zx)
Fil
exp
expp
331 44 "6""
PE
(R(ws) R(Weet) + let1 (Wret) ((o))))))) |F(]
3
(1141(Wret) let1 (we)) Fii
S exp
16
3
2 Wret well LE [let1 (Wrett + ( Fil
S exp
16
st
3
2n (R(w)et) + R(we))
S exp
16
Therefore E lexp (Z+) Fi] < and hence (exp (8e) 1>0 is supermartingale. By Ville's inequality, we have with probability at least 1 5, for all 0 < k ST -1
Σ Ze S log g
Expanding this inequality, we obtain
5 20)RR (w;) + zg Di (Wref; WK++1
16
k
1 + 20 Dr (Wref; wo) + (Wret)
11
< log g
Σ A=
Zt
+
z0lle (
16
2 0=0
+
(zt
2t-1
Du (Wref; we)
(I)
1=1
20
(a)
1
11
nle+1 (Wret)
log 8
+ 20 Do +
1jR (((eet)) +120 +
16
t= Consss v 2n + 2Do + 2n Eim ls (wrot)
(b)
1
11
k
nl2+1 1 (Wret)
< log 8
+ 20 Do +
R ((wer)) 1)20 +
(2)
16
2nC4 t=0
2Do + 2n S++1 Es (Wrer)
For (a) the fact that (ze) is a decreasing sequence and R(Wret) S eDa For (b)
use the assumption le+1 (Weet) C3- Now notice that we can write
/2Do Eizl (e(weer)
2D 2n Σ i=1
(Wret)
2D 2n Ei (weet) and over t obtain
k
5
R(wx) + 2x Da (Wrefi Wk+1)
2kl
16
1=
11 + 1))(w)))(rrr))
A++
< <log
Do + 17 Σ & (Wret)
16Cav2017C3 2D2
V2nCa \
Hence
16 Dy (Weet) wk+1)
Σ R(we) +
5n
16Ca
log + 11 + (wr(w
T Σ i=1
+
Dn + 1
e (wret)
5
16C,//2mCss +DD
V2ncCa \
17

---

T
x 207 + 2Do + 2n Σ & (Weer)
1=1
By Lemma with probability least 1- we have
r
Σ
4 (Wret) S 7 [I((w)t)))) + C3 Cglog 5 C37
Therefore with probability at least 1 25
16 5n
R(wr) +
D (Wref) wk+1)
t=0
16C4 log 8
11 + 1)
8
15
15
+
R(wret) +
5n V
Do + 2
1 4
Do + 407C3
5//n//33 2Do
16Ca log 8 V 4
15
32
Do + 4m +
- Do
,03
+ 3(k: + 1)R(wrr))
5
which gives us the conclusion.
Proof of Theorem 10 First we consider the bounded domain case. Let
Ut arg
min
(nege (vt-1), w) D (w; vt-1))
where we use gr (8=-1 to denote the gradient at Ut-1 using the same data point (Ie, Mr) when computing we and we choose
(2 (7)
R max
Do + 12C
Tu2 2MVT
2 7
7 (7
MT
1/2p
+ + Vylloy log 2
2
g u2
nCs
We have
(R(()) - R(Wset) + L441 (Wret) - l (et)
1e41 (Wret) ll11 (vx) + [R(vr) R (Wrre))
x (Q: 11) Wree vell C. S (Qi + u1) RCs
(3)
Let us define the following variables
U. = (R(ve) R(Wrer) + let1 (Wret) l+1 (vt)) if lU S (A + 2nr) RCa
[U:
P. (AA + 2pr) RCssign (Ut)
otherwise
(MT)
1/2p
where A
and B. U. Pt.
In words, U, is the variable of our interest and P, is the truncated version of U, and B, is the bias. We would want control these terms in order bound >k Ur. We start with the following decomposition
k Σ
Σ
U
(P
E
FF) + Σ E
F
Σ B 1=0
t=0
1=0
First, we consider the term Elz E [P Fi).
18

---

E
[P Fil B [P: - U. A U Fil
E
P U.l (1 - (A+
+ Σ 1 1[kk- 1)ARC, + 2p1 S |02| S KARC, + 2p (p,RRCa))
k=
E
Pt U,| 1 [[k: 1)ARCa 201 & |U|| S kARCA + 2p1
(kARC4 + RCs - (A + 2/1) RCA) RC [1 U 2 (A: 10ARCA + 2/11 RC,]]
kARC [[Q: + m1) RC4 2 kARCs + 2/0 RCa]]
(due to
20
KARC, Pr [Q: 2 KA + m1 - ARC Σ
kPr 11:--1) 111 z ( 2p
k=1
Mk
SARCA
A'
RC Σ 11 2A
RC
2 A2p
where the last inequality is because 2 2. We obtain
Σ
E P. Fi S 24'
RO
The term Ei= B₁ above deduction,
S Ei BB
S
|Bg will be bounded by Markov inequality, From the
t=
T-1
T
E
Σ
Brl
Σ
E
B
B
B
Pal F.]] S 2A 28 RC4
1=0
With probability at least 1 - 6,
MT
BBl S 2T RC,M 2RC,A7-2
8
Finally, we will use Freedman's 's inequality to bound the remaining term Et (P. - [ Fi)). First, notice that
E - E F,ll 2 Fi <E [P? Fi]
$ E [U3 F.] E E (Ceta (Wret) let1 (wt))² Fi]
I R² R'CE [Q < C2
We have (P. - E [P& Fi)) is martingale difference sequence with PP [P: Fi] s
2 (A + 2/11) RCs. We can apply Freedman's 's inequality.
b
A
Pr
3k 2 0:
Σ
PR-EPP Fi > a and
E
Pt E(P. F F F
-2a²
<2exp
2F + 4 (A + 2/1) RCqa/3
If we select
F F= TuyR2e R2O
19

---

2 2
log (A + 2pm) RC4 + RCt/ /188
2 /105 8 T
and
3 8
we obtain with probability at least 1 - ò, for all k 20
&
2
2
Pt-
Fil _ 3 σ
log
(A 2nr1 RC4 + RCA log T
t=0
Therefore with probability at least 1 3 we have the following event E for all k: 2 0
k
2
2 Tp2 + 4RC1A!
MT
Σ
U
-
log (A + 2n1) RCs + RC, log 8
3
5
8
1=0
MT
1/2p
2 RC + RC1 log / Tu2
- 7
+ 2u1
8
k+1
( #
and
oi - Twp + 2M
1=1
where we denote y = max {1, log } Furthermore
17
11 (ve)1 S
7
Σ
&
(C+ + C2 (1ele))))
2
1=0
E=0
1/2
Ue+1 (Cs + C2 | wl)
2 1=0
k+1
k
Σ
Of + 17 C/ Σ Qi+i 104--00 ||rrll"
S +
(Tp 2MVT
(2)
Now we will proceed by induction to show that conditioned on the event E, We = 2t2 For the base case, we have Wh Fo. Suppose that we have ua Ut for all k. We will show that wk+1 Uk+1 From Lemma])
2
we have
7 (R(w)) - RR*) + D Ww+11)
k
<Du
+
n (R(wret) - R*)
1=0
k
17 &
+
(R(we)= - R((ire)) ) + let1 (Wret) - let1 (we)) +
Σ
1 11?
2
1=0
1=0
112 k
<Dn + n + 1) Σ
U₂ +
10++1(12))1
2
t=0
0=
<Do
1 +
(
2
MT
1/2p
2 log x
7
2pm
+ v
Tu2
n/Css
3
8
(2)
+1²
(C) C2R22)
(Tu (Tu2+ + 2M VT
122
2
20

---

Thus || Wret|] I R. And thus wh+1 = Me+1 Finally, we can conclude that with probability
least 1 33, for all 0 < k < T
(R(w)) - R(wher)) + De (Wrefi Wk+1)
R. 2n (k: + 1)
(k: +1
Proof of Theorem 13 For SIST 1, we define
z 2 1) (E (6(0+1)+5 (wror) Fritz] E [CT(++14+5 (wri+s) Fritts)
+ Z (L (((++))+ (Wret) (((++)+ (wos+s)) - 8 (2+1+57) CDD (Wref: Wrsts),
T j-j
44 5
7
T T-1-j z4, < k.
S Σ
i=0
where
2 &n (T +1+
A --ISIST-1
We bound
(((i (Wrot) [Fitss] - E [C70+1)445 (Wri+s) Frits]
+ L7(641)45 (Weet) - (r(++))+s (wrets)
200 W[ Wri+5ll
By Lemma 15
exp ZZ) Frits
(-8 (1r D2D (weeti wrsts)
exp
x exp 2 [ea(++1) (Wret) Frits]] (e (wa++)) | Frits]]
+ E (wret) - b7(41)+ (wis)s) )) |Fritt
<exp (-8 (2 C2D' (Wret: wrsts) exp (4 (ETE+57)? C2 [|wret - wrstsl?) $
Therefore E
eex (
Frits] < 1 and hence (exp (8%)
is supermartingale. By Ville's
120
inequality, have with probability least 1 8, for all S
Σ 2 < log
k=0
By union bound over = O,...,T 1, and with probability at least 1 - 78 we have for all k k
Σ 2m (E (le+r (Wrer) Fi] [leer (wi) | Fe] + leer (Wrer) - leer (we))
21

---

k (2m1)² DDD,, (Wreti we) + T log g
1=0
We will proceed to prove by induction that Dy (Wrert we) S 1 R22
For the base case / = 0, this holds trivially. Suppose that this is true for all 0 S t S k, we now show for t +
11
1 (R(w)) - RR) + Da Whoffi 1)
<Do
1) (R(wret) - RR)
1=0
k
& 2
+
(R(we) - R(weet) + let1 (Wrer) - lut1 (we)) +
l1 l
2
t=
t=
We have
k
17 (((w)) - R(Wrer) + le+1 (Weet) - l++1 (w:)
t=0
k
<
2n || - well S 2nC & 2n
t=
and
112 k
1 & <
loo+
Σ
(G1 +2 (1 1|wx1)))²
2
2 1=)
n
Σ
(C4 + C2 ||w
Wror 11)
2 [=)
11)
7m7 +0++
Therefore
R
Do (Weefi wk+1) & Do + nDvTT 2n 2n + Tr² (C2 + C²R2) -
2
If k 2 7,
Σ t=0
2:77 (R(w;) - RR") + D. (Wreti Wk-1) =- Di (Wref' wo)
<
207 (R(wset)= -R") + Σ 2177 (R(w:) - R(wiet))
1=0
2012
2677 (le+1 (Weet) - l411 (w:)) + Σ
1g +
(2t - 20-1 Do (Wreti wy)
2
1=0
1=0
t=0
k
2 - RR)) +
2n77 (R(w)) - R R(wret))
t=0
t=
m (R(we) R(Wrer)
E [leer (Wror) | [F]] + E (leer (wx) Fil)
22

---

Eell (IE (letr (Weet) Fil - IE [li+r (wa) [ + letr (Wrer) - lets (wx))
2x7l (le+r (wi) - leto (Weer) +
Σ
20 (le+1 (w0ret) Let1 (wot)
t=
(zt 21-1 Do (Wreti we) +
Σ
2
1
2
1=0
t=
k
Σ
207 (R(weet)- -R²)
Σ
2n7 (R(w)) R ((Weet))
t=k-
Ftll (R(w)) R(wee) - E Bletr (Weet Fi] + E Elle+ (wi) Fel)
t=0
K-t
k-T
T =ooog
8 (am))² Σ
DgDos (Wrefi wi) +
Σ
(zt 2 Di (Wreti we)
t=
K-T
2,11
19++1 11: + Σ
20 (le++ (we) - lett (W+++-1))
2
1=
k-1
Σ
277 (le+1 (wx) let1 (Wrot)) - Σ
20l (let1 (Wret) - let1 (w,)
1=7-1
0=
20l (R(wrot) RR) + Σ
2ell (R(we) - R. (Wrro))
t=k-
21l7 (R(wi) R((ree) - E (letr (Wret) Fi] + E Blet+ (w)) Fil) + log
t=
2012
k-T
119+2111 Σ
20 (le++ (wi) - lett (W1++-1))
17 (2t-+41 24) (le+1 (we) - let1 (Weet)
znn (le+1 (Wret) - le+1 (we)) + zun (Ca+1 (Wret) Lx+1 (wk))
where in the last inequality we use 24 = 8, to see that &t + 8 (207)) 03 S 2111 Notice
that, < 2, and (R(weet) R²) = Du we have
VT
&
Σ (R(w))= - -R") + D (Wref; Wh+1)
1=
1 <DD, 2n + 16n CI log 5 + 2m
RR(w:) - R(wiet)
+ 2m
R((we) R(Wiet) E [letr (Wiet) | Fe] E lletr (wi) Fill
t=0
23

---

+ 17
19++1 1 + +2n
Σ
lets (we) letr (Wi++-1))
1=0
1=0
2(T 1)n
k-1
T-2
+
Σ
lle+1 (wi)
l4t1 (Wret) + 2ny
Σ
1e+11 (wret) -4+1 (wo1) + 21) (lx+1 (Wrett Ex+1 (wrk)
T
t=--1
E
Now we bound each term. For A
&
k
A 2n
Σ
R((w)) - R(Wrer)) $ 2n
Σ
Ca WWzzet - will S 2n
t=
t=k-r+1
For B, by Assumption 3, suPieZgo supy, TV (Pf+T, , E,
2n (R(w)) R(wrot) E [le+r (Wret) Fi] + E [l++ (we) Fill S2nC4
Thus
R-T ((())) - R. (WFrot) (letr (Wref) Fi] + E [letr (w)) [Fi] S ReT
= 2n
t=
For C, similarly before
C= n² 1=0
1941111 11. s 22T2 (0) + C
For D, we have
let (wi) - letr (wo++-1)1
b
lletr (wi) - letr (wi-1)l
bir-1
Σ [mo - |w--w;1ll (C1 + C2 (1++ [w;, (Io)lllll)
Σ n
VV, (w;-1))l (C4 C2 l|w; Wrelll
1++1
(C4 + C2R)
Σ
(C4 + C2 ||: - wrelll
(=H+1
(n + C2R)² का (2C + R2)
We obtain
R-T
2m Σ
letr (we) letr = (20 + R²)
t=0
For E, since
1le+1 (w)) - let1 (Wret) < C.R
Hence
2(T - 1)m
k-1
E
Σ 1=7-1
1let1 (we) - let1 (Weet)
T
2-2
+ 211
lea1 (Wret) leti (we) + 21/ 16+41 (Wret) - Ex (wx))
1=0
24

---

(T- (k: T 1) +T) S ,
S2nC,R
Sum up we have
Σ 17 (R(we) -R") + Di (Wiefi wk+1)
2DD + DoDoVT + CTT log 1
+ C2 2n RcT + 12 (C² + R
+ TT (2C² + 202 R²) + C
R²
2
as needed. Finally we have
(R(w)) - R²) + Do (Wieti wk+1)
R²a 21 (k + +)
k
" (k + 1)
25


Reviews:
[{"review_id": "9QDfgVzkfG", "reviewer": "Reviewer_H14F", "summary": "This paper revisits the generalization error of stochastic mirror descent for quadratically bounded losses studied in Telgarsky (2022). The authors depart significantly from the prior work of Telgarsky (2022), and introduce a novel approach for establishing high probability generalization guarantees. In contrast to the prior work, this work directly analyzes the moment generating function of a novel supermartingale sequence and leverages the structure of stochastic mirror descent. As a result, this paper obtains improved bounds.", "questions": "In the proof of  Lemma 4, line391-line392,  the last inequality uses assumption 2. \nHowever, Assumption assumes that $\\ell'(z)^2 \\le 2 \\ell(z)$ for $z\\in \\R$ but $w_t$ in the proof is a vector. \nCould you fix it?", "limitations": "No.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper revisits the generalization error of stochastic mirror descent for quadratically bounded losses studied in Telgarsky (2022). The authors depart significantly from the prior work of Telgarsky (2022), and introduce a novel approach for establishing high probability generalization guarantees. In contrast to the prior work, this work directly analyzes the moment generating function of a novel supermartingale sequence and leverages the structure of stochastic mirror descent. As a result, this paper obtains improved bounds.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and the endorsement of our novel approaches.\n\nRegarding the question: We believe that line 391-line 392 are correct and consistent with our notations. We recall some notations to clarify the assumptions. We use $\\ell_{t}(w)$ as the short form for $\\ell(y_{t},w^{T}x_{t})$ and $\\ell(y,\\widehat{y})$ is either $\\widetilde{\\ell}(sign(y)\\widehat{y})$ or $ \\widetilde{\\ell}(y-\\widehat{y})$. In assumption 2, we use the scalar form $\\widetilde{\\ell}$ of $\\ell$, which says, $\\widetilde{\\ell}'(z)^{2}\\le2\\rho\\widetilde{\\ell}(z)$ for $z\\in R$. Regarding line 391-line 392, let us take the first case $\\ell(y,\\widehat{y})=\\widetilde{\\ell}(sign(y)\\widehat{y})$ as an example (same steps hold for the other case), we have\n\n$||g_{t+1}||\\_{*}^2 $ \n\n$= || \\ell' (y_{t+1},w_{t}^{T}x\\_{t+1} )||\\_{*}^{2}   $\n\n$\\overset{(a)}{=} || x_{t+1} ||\\_{*}^2 \\widetilde{\\ell}' (sign(y_{t+1}) w_{t}^{T} x_{t+1})^2 $\n\n$\n\t\\overset{(b)}{\\le} 2\\rho\\widetilde{\\ell}(sign(y_{t+1})w_{t}^{T}x_{t+1})$\n\n$=2\\rho\\ell(y_{t+1},w_{t}^{T}x_{t+1}) $\n\n$=2\\rho\\ell_{t+1}(w_{t})$\n\nwhere $\\ell'$ denotes a subgradient in $\\partial\\ell$ wrt the second argument, (a) uses chain rule and (b) uses the assumption $\\left\\Vert x_{t+1}\\right\\Vert _{*}\\le1$."}, {"review_id": "pwVVzAUV3N", "reviewer": "Reviewer_TJAZ", "summary": "The authors propose a novel approach to analyze the generalization error of Stochastic Mirror Descent (SMD) for quadratically bounded losses. Compared to previous methods, their approach demonstrates improved accuracy by a logarithmic factor when the data is realizable. Additionally, in scenarios where the data is not realizable and has a polynomial tail, their method achieves enhanced accuracy by a polynomial factor of T.", "questions": "See weaknesses.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a clear and well-explained improvement over previous work.\n2. The approach presented in the paper, which involves analyzing the moment generating function of a martingale difference sequence with well-chosen coefficients is interesting as it avoids the need for the coupling technique used in previous works and might be used also in future works.", "weaknesses": "1.A potential weakness of the paper is that the improvement over previous work in the realizable case is relatively modest, as it is limited to logarithmic factors in the bound. \n2. Although the paper suggests improvements in the bound, these may not result in entirely new conclusions or fundamentally alter our understanding of the generalization behavior of Stochastic Mirror Descent (SMD) with quadratically bounded losses. The incremental nature of the improvement might not have a significant impact on the practical performance or broader understanding of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We answer the concerns of the reviewer below.\n\n1. The main contribution in the realizable case is not only an improvement in the log factors, but also a new approach to analyze generalization bounds in high probability of stochastic gradient methods. As noted by Reviewer H14F, our work “depart[s] significantly from the prior work of Telgarsky (2022), and introduce[s] a novel approach for establishing high probability generalization guarantees”. We think our new approaches can be applicable in broader scenarios.\n\n2. To our knowledge, closing the gap between the upper bounds and lower bounds is an important question in the literature of optimization and generalization. even to $\\log$ factors. Although a $\\log$ factor improvement may seem small, there is a line of works studying the log factors that reveal fascinating phenomena of SGD. For example, [1] shows that the lower bound for the convergence of last iterate of SGD differs from that of the suffix averaging iterate by a $\\log$ factor. This theoretical question does not fundamentally change the performance of the algorithm we use in practice, but strengthens our understanding. In the non-realizable case with polynomial tailed data, where the improvement by our approach is significant, we also have a much better understanding of the behavior of the algorithm.\n\nReference\n\n[1] Harvey, Nicholas JA, et al. \"Tight analyses for non-smooth stochastic gradient descent.\" Conference on Learning Theory. PMLR, 2019."}, {"review_id": "ukzTqspqTH", "reviewer": "Reviewer_p99H", "summary": "The authors study Stochastic Mirror Descent, and analysis its generalization error under a quadratic loss assumptions, self boundedness of the loss (a relaxation of smoothness), iid or Markovian data, and realizable or non-realizable cases, which amount to assume that the error of the reference point is of different orders.\nThe approach taken consists in deriving concentration bounds taylored to the problem.\nThe results improve previous ones by some log(T) (resp. polylog(T) ) factor in the realizatble (resp. non-realizable) setting.", "questions": "See above. \n\nI suggest acceptance for this paper for the reasons noted above. I suggest adding references such as [A,B] in order to add discussions for readers who are more familiar with such works.", "limitations": "No such limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Disclaimer.** I acknowledge not being familiar with the generalization error literature cited in the paper (excpet the Hardt et al. paper on algorithmic stability), although I am quite familiar with the SGD literature and especially Mirror descent and its stochastic counterparts.  \n\nStochastic Mirror Descent is a widely used and studied algorithm in many domains of optimization. Since existing generalization error analyses (the SOTA rates being Telgarsky [30]), as cited in the paper) appear to be suboptimal in light of the rates obtained in the present submission, I think this is a contribution worth acceptance at Neurips. The whole paper being organized around the generalization bounds for SMD under the various data assumptions (realizable or not cases, Markovian or iid), it is quite technical, but the authors make an effort to put as much detail as possible of the analysis in the main part of the paper ", "weaknesses": "I think that the results should be put in light of optimization error analyses of SMD, the current best rates being in the following paper [A]:\n\n**[A]** *Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction*, Dragomir et al., Icml 2021.\n\nThe following work also studies SMD convergence rates.\n\n**[B]** *Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize*, Loizou et al. 2022.\n\n\nIn particular, the rates in [A] being for SMD with iid data and fresh samples at each iteration (and thus the loss being optimized in the generalization error), can these rates be considered, in the context of the present submission, as in-expectation gen error ?\n\nAlso, in many applications, MD or SMD is used when (S)GD cannot converge (or is too slow) due to non-smoothness and degenerate frontiers (e.g, minimization of KL distances). It seems to me that the assumptions on the loss in the present submission are too restrictive to allow this. This, in addition to some strong assumptions on the data lead to somewhat quite restrictive assumptions; this is however fine as it appears that previous works also make similar assumptions. To what extent the gap in the theory between SMD convergence rates in expectation (as in [A]) and the high probability generalization error of this submission seems hard to fill ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and for pointing out the references that we missed in our submission. We will include them in the revision.\n\n**Regarding [A]**: We agree that this paper can be seen in part as giving an in-expectation generalization error bound for a setting that corresponds to the non-realizable setting with  iid data. However, one important distinction between these two settings is \n\n- in [A] and other optimization papers, we commonly impose assumptions on the stochastic gradients (such as bounded variance, sub-gaussian noise, etc) \n\n- in our paper and other generalization papers, we make assumptions on the data instead of the stochastic gradients. \n\n**Regarding the assumptions**: Convergence analysis for SMD even in expectation does not immediately translate to generalization error bounds. One reason for that is because we do not have {\\em a priori} bounds on the magnitude of the gradients. A challenging question is how we can translate the assumptions on the data to guarantees on the gradients. It turns out, we can make such guarantees only for certain loss functions, such as logistic loss or exponential tailed losses or the broader class of quadratically bounded losses introduced by Telgarsky [30]. For this class of losses, Lemma 1 can be viewed as an attempt to bound the gradients. Another challenge that arises from Lemma 1 is that these bounds depend on the magnitude of the data and therefore convergence analysis for SMD still does not apply. Our paper fills in the gap by introducing a novel analysis.\n\nAdditionally, our paper also shows that in the realizable case, for potentially non-smooth losses, the generalization bound can be better than what is shown by the convergence guarantee ($O(1/T)$ vs $O(1/\\sqrt{T})$). We also include bounds for the non-iid case (markovian data)."}, {"review_id": "LARYhK3h6O", "reviewer": "Reviewer_sY4Q", "summary": "This paper analyzes the generalization bound for stochastic mirror descent applied to linear models and a general class of quadratically-bounded losses. In addition to the more common IID sampled data, this paper also considers where the data is sampled from a Markov chain. This paper follows up from the work of [Telgarsky 2022] and improved the bounds, particularly in the case of non-realizable setting. The improvements in this paper come from a more clever application of concentration inequalities.", "questions": "I would like to hear from the author on how this paper presents a significant delta over [T22] and in what ways their improved bounds can be useful. Given what I currently gathered from the paper, I am inclined to say that the contribution is insufficient, but I would love to be proven wrong.", "limitations": "N/A. This paper is purely theoretical and I do not believe there would be any negative society impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Since this paper is mainly a follow up to [Telgarsky, 2022], I would refer that paper as [T22] for simplicity.\n\nOne major strength of this paper compare to [T22] is that the content are better organized and the notations are also slightly better. I found this paper to be generally easy to follow.\n\nAlso, the theoretical analysis seem to be in good shape. While I did not have the time to read through the proofs line-by-line, I have reasonable faith that there are not major technical issues buried in the proof.", "weaknesses": "While the overall quality of this paper is good, I feel that the contribution over [T22] is not sufficient to warrant a new paper. In particular, compare to [T22]: Theorems 3 and 13 in this paper have the same guarantee as Theorems 5 and 8 in [T22], respectively. While Theorem 7 of this paper is an improvement over Theorem 10 of [T22], a log factor is not particularly interesting. Also, the problem setting of this paper is almost entirely the same as [T22] and I would love to see more novelty on this front.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. \n\n**Regarding the comparison between our results and [T22]**: Both theorems 3 and 13 in our paper improve the guarantee of theorems 5 and 8 in [T22] by a $\\log T$ factor. This is also the case of Theorem 7 compared with Theorem 10 part 1 for sub-gaussian data in [T22]. Our Theorem 10 significantly improves Theorem 10 (part 2 for polynomial tailed data) in [T22], i.e, by a $poly\\ T$ factor. As in our response to reviewer TJAZ, the significance of this improvement lies in two aspects: \n\n1. in our opinion, closing the gap between the upper bounds and lower bounds is an important question in the literature of optimization and generalization, even to $\\log$ factors. Although a $\\log$ factor improvement may seem small, there is a line of works studying the $\\log$ factors that reveal fascinating phenomena of SGD. For example, [3] shows that the lower bound for the convergence of last iterate of SGD differs from that of the suffix averaging iterate by a $\\log$ factor. This theoretical improvement strengthens our understanding of the behavior of SMD. In the non-realizable case with polynomial tailed data, where the improvement by our approach is significant, we also have a much better understanding of the behavior of the algorithm.\n\n2. we offer new approaches that look into to how obtain a tighter high probability bound, instead of just applying concentration inequalities as a blackbox (which is suboptimal). As noted by Reviewer H14F, our work “depart[s] significantly from the prior work of Telgarsky (2022), and introduce[s] a novel approach for establishing high probability generalization guarantees”. We think our new approaches can be applicable in broader scenarios.\n\nWe would also like to point out an issue in the analysis of [T22], which is unclear to us during our study of the paper. The application of Azuma's inequality (mentioned in the last paragraph of page 12 - page 13 in [T22]) in proving Theorem 10 [T22] is not correct (or at least not immediate to us) as the variables' ranges do not satisfy the measurability condition of the inequality. Our analysis fixed this issue in this paper, having to rely on a different approach, while also achieving significant improvements.\n\n**Regarding the problem setting**: As detailed in [T22], the setting studied in this paper captures and significantly extends many prior works in a unified way. Due to its generality, it remains interesting to provide a tight bound for the generalization error in this broad class. There is also large body of work on obtaining generalization bounds via Rademacher complexity. For example, the recent work [1] considers the setting of separable data and smooth losses with bounded tails. We think it is a very challenging and interesting direction for future works to unify these two settings.\n\nAnother broad direction for future works is to show generalization bounds for a more general class of algorithms. For example, algorithmic stability was used by [2] to show high probability bounds for Lipschitz losses for several variants of SGD in a unified way. Going beyond SMD, it would be interesting to combine our techniques with [2] to obtain tight high probability generalization bounds for both a more general class of algorithms and all quadratically bounded losses.\n\nReference:\n\n[1] Schliserman, Matan, and Tomer Koren. \"Tight Risk Bounds for Gradient Descent on Separable Data.\" arXiv:2303.01135 (2023).\n\n[2] Bassily, Raef, et al. \"Stability of stochastic gradient descent on nonsmooth convex losses.\" Advances in Neural Information Processing Systems 33 (2020)."}]

Author rebuttal:

Meta-review: While the final results of the paper might seem incremental given the prior work (removing poly(T) factors), all the reviewers (and myself) appreciated the introduction of the new proof technique and the fact that the state of the art bounds have improved. Besides the authors have adequately addressed the reviewers' concerns, which resulted in an increase in the overall score. After the discussion with the SAC, we believe that the paper is borderline and we recommend a weak acceptance.
Decision: Accept (poster)