Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD
Authors: Aniket Das
Dheeraj Mysore Nagaraj
Soumyabrata Pal
Arun Suggala
Prateek Varshney
Venue: NeurIPS 2024 poster (2024)
Keywords: Streaming estimation
heavy tailed estimation
clipped SGD
Primary area: optimization
TL;DR: near-Subgaussian convergence rates for streaming statistical estimation for clipped SGD in the presence of heavy-tailed data.

Abstract: $\newcommand{\Tr}{\mathsf{Tr}}$
We consider the problem of high-dimensional heavy-tailed statistical estimation in the streaming setting, which is much harder than the traditional batch setting due to memory constraints. We cast this problem as stochastic convex optimization with heavy tailed stochastic gradients, and prove that the widely used Clipped-SGD algorithm attains near-optimal sub-Gaussian statistical rates whenever the second moment of the stochastic gradient noise is finite. More precisely, with $T$ samples, we show that Clipped-SGD, for smooth and strongly convex objectives, achieves an error of $\sqrt{\frac{\Tr(\Sigma)+\sqrt{\Tr(\Sigma)\\|\Sigma\\|_2}\ln(\tfrac{\ln(T)}{\delta})}{T}}$ with probability $1-\delta$, where $\Sigma$ is the covariance of the clipped gradient. Note that the fluctuations (depending on $\tfrac{1}{\delta}$) are of lower order than the term $\Tr(\Sigma)$.
This improves upon the current best rate of
$\sqrt{\frac{\Tr(\Sigma)\ln(\tfrac{1}{\delta})}{T}}$ for Clipped-SGD, known \emph{only} for smooth and strongly convex objectives. Our results also extend to smooth convex and lipschitz convex objectives. Key to our result is a novel iterative refinement strategy for martingale concentration, improving upon the PAC-Bayes approach of \citet{catoni2018dimension}.

Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD
Aniket Das
Dheeraj Nagaraj Google DeepMind dheerajnagaraj Ggoogle.
Stanford University aniketd@cs stanf ord. edu
Soumyabrata Pal Adobe Research sounyabratapladdbe.. com
Arun Sai Suggala Google DeepMind
Prateek Varshney"
Stanford University
arunss@google. com
wprrateek@stanforddcco
Abstract
We consider the problem of high-dimensional heavy-tailed statistical estimation in the streaming setting, which is much harder than the traditional batch setting due memory constraints. We cast this problem as stochastic convex optimization with heavy tailed stochastic gradients, and prove that the widely used Clipped- SGD algorithm attains near-optimal sub-Gaussian statistical rates whenever the second moment of the stochastic gradient noise is finite. More precisely, with T samples, we show that Clipped-SGID for smooth and strongly convex objectives,
T achieves error of y (r(=)=/(((())))))))) (n()((( with probability ō. where
Σ is the covariance of the clipped gradient. Note that the fluctuations (depending on 1/6) are of lower order than the term Tr(E). This improves upon the current
best rate of TT(E))((1/)) for Clipped-SGID, known only for smooth and strongly convex objectives. Our results also extend to smooth convex and lipschitz convex objectives. Key to our result is novel iterative refinement strategy for martingale concentration, improving upon the PAC-Bayes approach of Catoni and Giulini [
T
Introduction
A fundamental problem in machine learning and statistics the estimation of an unknown parameter of a probability distribution, given samples from that distribution. This can be expressed as the minimization of the expected loss: ming F(x) = E E)]. where x represents the parameter estimated, P is the underlying probability distribution which can only be accessed through samples, and f(x; {) is function which quantifies the loss incurred at a point ç by parameter x. In this paper, we focus on the setting where a heavy-tailed distribution for which the extreme values are more likely than in distributions like the Gaussian, (:: .) is convex and the learner only has access to (d) memory.
The heavy-tailed statistical estimation problem has received increased attention of late because of the prevalence of heavy-tailed distributions many statistical applications dealing with real world data [19 49 (3) The presence of such heavy-tailed distributions can significantly degrade the per- formance of statistical estimation and testing procedures designed under Gaussian (or sub- lub-Gaussian) tail assumptions [30] (24 53 24 This has spurred recent research efforts towards developing estima- tors specifically tailored for heavy-tailed settings (c.g.. [10 44 16 36] see Section [.2 for a more detailed literature review). Despite substantial progress on this problem in recent years, much of the
Work done while Google
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

existing work has concentrated on batch learning, where the entire dataset is available upfront, and the learner can revisit data points multiple times, without memory constraints. However, the streaming setting, where data arrives sequentially and must be processed with limited memory, is increasingly pertinent in the era of large-scale models. Consequently, in this work, we focus on understanding estimators for statistical estimation under heavy-tailed distributions, in the streaming setting.
A popular approach to study heavy-tailed streaming statistical estimation casts it as stochastic convex optimization (SCO) problem with heavy-tailed gradients [7
with Clipped-SGD as the favored solution due to its simplicity [42]. Indeed, clipping has become a standard component
52 48)
in the training of modern deep neural networks and thus, the properties of Clipped-SGD have been [52] in various contexts. Specifically, several works have shown that Clipped-SGD has sub- satb-Exooential or sub- tails despite the presence of
studied widely in the literature [1] [56
38 48
heavy tailed noise in the gradient [45 21
52 49, Despite this progress, the best known rates for
Clipped-SGD with smooth and strongly convex losses, under bounded 2nd moment assumption on
gradient distribution, are of the order Tx(2) (n())) where 5 is the failure probability [22 Note that
this is still far from the optimal sub-Gaussian rates of v Tr( [|2]] In(1/4) In this work, we bridge
this gap with a sharper analysis of Clipped-SGD for SCO problems, achieving nearly sub-Gaussian rates (see Section I.Ip. Our approach leverages novel technique obtained by bootstrapping the Donsker-Varadie Varadhan Variational Principle to Freedman's inequality, yielding tighter concentration inequalities for vector martingales compared those in [8]. This enables to derive more refined rates for a variety of settings than a direct application of Freedman's 's inequality as in [2
1.1 Sub-Gaussian Error Guarantees for Statistical Estimation
Mean Estimation We motivate our style of results with the case of mean estimation. The Central Limit Theorem (CLT) posits that that the empirical mean of T'' independent and identically distributed (i.id) random variables with a finite covariance, behaves roughly like the empirical mean of Gaussian random variables with the same covariance, as T + co. That is, the empirical mcan p. the true mean
j and the covariance D are such that 1imy IP (VTili- ulll > TT((2) + ||Di|2 log(()))))) S 8.
However, these asymptotic rates need not hold with practical number of samples. Therefore, recent works on heavy-tailed high dimensional mean estimation consider algorithms and non-asymptotic guarantees which move beyond the empirical mean (see [36, 10
9 27 28 (5)). Estimators such as the clipped mean estimator 8 55 trimmed mean estimator [45, and the geometric median-of-means
estimator 39 29 achieve an error of at-most V Tr(z)) () with probability 1 6 6 with a finite 28 36 further improve upon these re-
covariance assumption. Recent ground breaking works 37
sults to construct estimators which can achieve the CLT convergence rates of CVy TT(E)++ lok( #3// for every T and 8. Some of these estimators work under just the assumption that the second moment and some even provide nearly linear time algorithm [5]
is bounded 37 28
General Statistical Estimation In this work, we are interested in the general statistical estimation problem. Among the various approaches, framing this problem as SCO with heavy-tailed gradients has gained traction recently (see [52) and references there in). While one obvious candidate is to use SGD with state-of-the-an optimal mean estimators for robust gradient estimation, such methods can face significant challenges. First, most optimal mean estimators aren't 't designed for the streaming data setting with batch-size being 1. Second, these estimators can be complex, frequently relying on cemi-definite programming or other demanding techniques. Third, and perhaps most importantly, they don't typically provide guarantees on the bias of their estimates. This lack of bias control is problematic because SGD-style algorithms, even when equipped with accurate gradient estimates, can perform poorly if those estimates are systematically biased (See 3 Theorem 4], where bias does not cancel across iterations). Given these challenges. the clipped mean estimator of (8] has emerged as a popular choice for gradient estimation in SCO, due mainly to is simplicity. Several recent works analyze the performance of SGD with clipped mean estimator for the gradients (i.e. Clipped SGD). However, as previously mentioned, the best known analysis for clipped SGD achieves sub-optimal rate of /Tr(E) [)) In()/)/TT, under bounded 2nd moment assumption. In this work, we improve upon these rates and show that with T samples, clipped obtains a sharper rate of Tr(E)+ 100tt/T((220 Tr(2))]]]] In( (n(2)
with probability 1 - 6, which is closer to the truly sub-Gaussian rates.
T

---

Table 1: Sample complexity bounds (for converging algorithms for SCO under heavy tailed stochastic gradients. Results are instantiated for smooth and strongly convex losses, and for the case where the gradient noise has bounded covariance equal to the Identity matrix. Dj is the distance of the initial iterate from the optimal solution. For readability, we ignore the dependence of rates on the condition number. Observe all prior works have d log 8-1 dependence in the sample complexity.
approximate solution) of various
Method
Sample Complexity
Batchsize
Domain
Clipped SGD 21
log
log 6 1 + log log
log
log
log
Unhounded
R-Clipped SGD
log
log 6 + log log
o
log
log
"i
Unbounded
R-Clipped SSTM
21
log
Di
log 11 + log log
of
0
y log
log
Di
Unhounded
RobustGD 45
0 det log
with
log
Di
0
d log 2
Unbounded
proxBoost 14
log
Di log 6
log
Unbounded
restartedRRSMP 40
( log
Di
log 6
+ log log
Di
o dl log d
log log
2i
Bounded
Clipped SGD
52
D1
log 0
1
Unbounded
Clipped SGD (Ours)
dividlin 5-1
Di log (6 log
1
Unbounded
1.2 Related Work
Clipped SGD Clipped SGD and it's variants have been studied under variety of settings including convex, strongly-convex, non-convex losses, with various assumptions on the moments of stochastic gradients. The estimators of 21 45 40
work under the assumption of bounded 2nd moments, but require (11/c) batch size, to converge to an c-approximate solution. Consequently, they are not suitable for streaming setting. The recent work of [52], which closest to our work, addresses this issue by analysing Clipped-SGD for batch size 1 for smooth, strongly convex losses. But they achieve sub-optimal rate of / Tr(E) In(s))(()))/ These rates are improved in our work (see Table 1 for a detailed comparison). Additionally, our work provides convergence rates for convex objectives that are not strongly convex. Recent works 44]] 46, 41 34 [33 have studied Clipped-SGD with the assumption that the stochastic gradient has finite p-th moment for some p E (1,2). They derive near optimal results in terms of dependence of T and p (but their dependence on log 8-1 is sub-optimal). In contrast, our work specifically the case considers p = 2 with a focus on improving the sub-Gaussie Gaussian dependence in the high probability bounds in these works from Tr( log (1)6) and approaching the truly sub-Gaussian rates for estimation
Heavy-tailed Estimation Heavy-tailed estimation has rich history in statistics and we only review some of the recent advances. Several recent works have studied the problem of heavy-tailed mean estimation, and have derived estimators that achieve aub-Gaussian rates under the bounded 2nd
moment assumption [36] 10 9 27
28
15 45) Among these, the works of [15] 32) are particularly
relevant to work. The algorithm of DS runs in linear time while requiring O(d log ò memory. But it is not immediately clear how to use their estimator in the framework of SGD. [3 study the trimmed mean estimator (an estimator that is closely related to clipped mean estimator, where outliers are removed instead of being clipped) and show that when T= w wlog' 5 8-1), d = w(log?(8-)) the estimator achieves the optimal rates. We not that our analysis of clipped SGD, when instantiated for mean estimation, leads to similar rates. But unlike [32 which primarily focused mean estimation, we focus on the more general SCO problem.
Heavy-tailed linear regression has been widely studied, with classical estimators based on Huber regression [30 [50] 33) known to provide optimal rates when the response variables are heavy-tailed, but the covariates are light-tailed. Recently, there has been surge of interest in developing estimators
43 However, most of these works are in the batch setting. Another line of work has considered streaming algorithms in the couten-contanination model, which much harder contamination model than heavy-tails [18] However, these algorithms when adapted to heavy-tailed setting, do not provide optimal rates.
when both covariates and response variables are heavy tailed [ 44
3

---

1.3 Contributions
Iteratively Refined Martingale Concentration via PAC Bayes Our key technical result obtains fine-grained concentration guarantees for vector-valued martingales by using the Donsker- -araddhan Variational Principle to iteratively refine baseline concentration inequalities. This allows us to sharpen the PAC Bayes bounds of Catoni and Giulini [8] (and its martingale based extensions like (T]) which were used to analyze the clipped mean estimator. We believe these iterative refinement arguments could be of independent interest for developing fine- ane-grained concentration bounds.
Sharp Analysis of Clipped SGD Leveraging these fine-grained concentration results, We perform a fine-grained analysis of clipped SGD for heavy-tailed SCO problem obtain nearly subgaussian perfor- mance guarantees in the streaming setting with a batchsize of and (d)) space complexity. In particu-
lar, we demonstrate that the sub-optimality gap after I" steps scales as Tr(>*) + (023)+([Z]] 2 Tr(2)) log()/))
improving upon the best known scaling of Tr(E) log(1/) obtained by prior works [52] only for smooth strongly convex problems. To the best of our knowledge, we derive the first such guarantees
for smooth convex and lipschitz convex problems in the streaming setting.
Streaming Heavy Tailed Statistical Estimation We use the above results to develop streaming estimators for various heavy-tailed statistical estimation problems including heavy-tailed mean estimation as well as linear, logistic and Least Absolute Deviation (L.AD) regression with heavy tailed covariates, all of which exhibit nearly subgaussian performance. Our mean estimation results improve upon the previous best known guarantees for trimmed mean based estimators 88 52 32 (either in performance or in generality) For heavy-tailed linear regression under the assumption of bounded 4th moments for the covariates and bounded 2nd moments for the response, our rates significantly improve upon that of the previous best known streaming estimator [52]. To the best of our knowledge, we develop the first known streaming estimators for heavy-tailed logistic regression and LAD regression which attain nearly subgaussian rates
Notation and Organization
We work with Euclidean spaces IR equipped with the standard inner product (-.-) and the induced l2 norm -|- For any matrix A RRxx,, we use || to denote its Euclidean operator norm ||||| SUPxx0 ||Axl//|x]] For A E Raxd, denote its trace as Tr( (A). For any random vector x, denote its covariance matrix Cov[x]. We use S. and to denote S, 2 and respectively, upto universal multiplicative constants. We use V (x) to denote the gradient of a differentiable function For any convex function f, we use (x) to denote an arbitrary subgradient of
3 Background and Problem Formulation
Our work studies the Stochastic Convex Optimization (SCO) problem, described as follows: Let denote closed convex subset of Rd and let F C -> IR be convex function. We aim to solve:
min F(x): ECC
(SCO)
assuming access to convex projection oracle II and stochustic gradient oracle, which we define as follows: Let P denote a probability measure supported on an arbitrary domain E from which we can draw samples. A stochastic gradient oracle for F is function y C x C, which, given a point x E C and a sample { ~ P returns an unbiased estimate g(x: E) of F i.c., Eg-P [g(x: {)] = F If F is nondiffcrentiable, Eg-x [9(x; E)] = (x).. Note that we do not assume direct access to Fx()., which may be expensive or intractable to compute. Our objective is to (approximately) solve SCO subject to constraint on the number of samples we can draw from P.
This is an alternative formulation of the statistical estimation problem by recognizing P as the data distribution, C as the parameter space and defining the population risk Fxx) := Of E)), where denotes the sample-level loss function. The associated stochastic gradient oracle g { == Vs(x; E), & ~ P. which is usually easy to compute. As we shall discuss in Section 5 several statistical estimation problems such as mean estimation, linear regression, logistic regression and least absolute deviation regression naturally fit into the SCO framework.

---

We use nx; {) {x; - (x) to denote the stochastic gradient noise and assume it has finite second moment, i.e., Σ(x) = E [n(x: { ( [x: exists for every x E C. Our results make use of either of the following assumptions on {-
Assumption (Bounded Second Moment). The exists positive semidefinite matrix Σ such that:
2(x)33 VXEC
(Bdd. 2nd Moment)
Similar assumption has been made by several prior works (2 following generalized assumption, which is refinement of the one made in Tsai et al. (52).
40 14 45
We also consider the
Assumption 2 (Second Moment with Quadratic Growth), There exist constants a, B 2 and 1 S dend such that the following holds for every x E
[[(x)]l2 S alxx x=11 3:
Tr(I(x)) S del (a|xx~x'11+ 3) (QG 2nd Moment)
where x" denotes any arbitrary minimizer of F.
Since we consider streaming statistical estimators that are robust to heavy tailed data, we only assume the existence of the second moment of the stochastic gradient noise and allow its higher moments be infinite. That is, our results hold even when Ex-rl (n(x; E), v) [2+t] = oo for every > O, v E Rd
Our work analyzes SCOJunder either of the following structural assumptions assumptions F
Assumption 3 (Convexity). F Rd R is a convex function if the following holds for any E [0, 1]
F(tx + (1 - f)y) S (x) + (1- -t)F(y) Vx,
(Convexity)
Assumption 4 (μ-Strong Convexity). F; d + R is p-stroogly convex function for μ 2 0 if the following holds for every t [0,1]
F(ix + (1- < (F(x) + (1 (1- () - (1-1) 1) - y11 Vx,
(u-Strong Convexity)
In addition, we also consider either of the two regularity assumptions on
Assumption 5 (L-smoothness), differentiable and satisfies the following:
Rd + IR is L-smooth for some 2 O if F is continuously
FF(x F S T||x - yll Vx.
(T-smoothness)
Assumption 6 (G-Lipschitznesss. F: IR.d + R. G-Lipschitz for some G 0, ie., is continuous and satisfies the following:
[F(x) - F(y)ll Gl|x- yll Vx,e
(G-Lipschitzness)
Results
Under the Bdd, 2nd Moment and QG 2nd Moment assuumtionssm streaming algorithms for SCr such as Stochastic Gradient Descent (SGD) typically convergence bounds guarantees that hold in expectation
[56 26 22). However, high probability guarantees require strong assumptions on the tail behavior of the stochastic gradients (e.g. boundedness or subgaussianity) 25 47 31). Our work analyzes
SCO heavy tailed stochastic gradients, which typically exhibit large fluctuations from their expected value due its higher order moments being potentially infinite. Clipped SGD mitigates the
large fluctuations typically observed in the heavy tailed stochastic gradient (x; {) by thresholding
its norm as follows. The full algorithm is described in Algorithm
g(x; E) [1g(x; E)ll
(g)p
min(1', (l((x)
We now present our performance guarantees for clipped SGD for streaming heavy tailed SCO wherein Algorithm|| is subject to an O(d) memory constraint and can access only one stochastic gradient sample per iteration. For the remainder, of this section, we use x* E C to denote an arbitrary minimizer of F, which is assumed to always exist, and guaranteed be unique
satisfies fu-Strong
satisfieszuSSrrnng
Convexity We use x; to denote the initialization of Algorithm| ] and let D |x x'|].
5

---

Algorithm 1 Clipped Stochastic Gradient Descent
Input: Initialization X1, Horizon T', Step Sizes (Ne)et)y) Clipping Level 1'
1: for E [T] do
2: gr gxx Et), & ~~1
3: X1+1 < Ic(( - Tr clipr(g:))
4: end for
5: Last Iterate: Output XT+1
6: Average Iterate: Output Xr + EE=
4.1 Smooth Strongly Convex Objectives
Theorems
I and 2 proved in, Appendix B and respectively, derive high probability convergence bounds for smooth and strongly convex objectives with second moment assumption.
Theorem 1 (Smooth Strongly Convex Objectives). Let the [-smoothness) I--Strong Convexity and Bdd. 2nd Moment assumptions be satisfied. Then, for any 5 E (0, 1/2), the last iterate of Algorithm run for T Z In(In(d) iterations with stepsize Ti = m(t+t) and clipping level
[ (7 + 1)2D9 (7+g) (Tr(E) + VT(E) /1( (aat the following with
probability at least - 8
x 7D1
Tr(E) + Tr(E) El ln(lu(7)8))
XT+1 x
(1)
T T+
where 7 x m
2 (2( Tr(E)
2/2 (I(((())/)) K In((m(T)/6)²
We use Theorem to derive sharp rates for streaming heavy tailed mean estimation in Section 5.1 and the following result to derive sharp rates for streaming heavy tailed linear regression in section Theorem 2 (Smooth Strongly Convex Objectives with Quadratic Growth Noise Model). Let Assump- tions] u-SStron Convexity L-smoothness and QG 2nd Moment be satisfied and let K. 4/n. For any 6 E (0, 1/2), the last iterate of Algorithm run for T Z In(In(d)) iterations with step-size 1); (e
n (T + (dett + ddet In(ln(T)/))) satisfies the and clipping level In(miryaa V (7 + 1)2
following with probability at least -
7Di
1
B(der + ddn In((ner)//))
||x++-- - x
+
(2)
1
T+y
adea avder In(In(T//)) Ava In((m(7//s)
VRadee In(I(T)/s),
where y x max
112
412
P
* d//3//
x²
In(In(T)/s), 22 (n())())))) In(1n(7)66) den
In(1n(1/6))
1/13
Comparison to Prior Works To the best of our knowledge, the result closest Theorem 2 is 52
Theorem 1] which analyzes streaming strongly convex SCO and obtains a 7
<D + /
Bdwr (n(1/) T+C rate
for Ç x audan (o/( We note that Theorem 2 obtains significantly better confidence bound which
n² is closer to the optimal subgaussian rate compared [22 Theorem 1].
Extra log log T term: Our bounds for the statistical error is of the form 1 which has extra log log 7 factor in the lower order term. This is still sharper than prior works with bounds of the form
i V B(der + ddd (n((oC))/))
T4y
1 Bd In(1/4)
as long as log log v derr log( (
T47
4.2 Beyond Strongly Convex Objectives
Moving beyond strong convexity, we present Theorems for smooth convex functions and for Lipschitz convex function, proved in Appendix D and respectively. To the best of our knowledge,

---

these are the first results for streaming heavy-tailed convex SCO that exhibits near- near- subgaussiann concentration without strong convexity.
Theorem (Smooth Convex Objectives). Let Ler Convexity L-smoothness and Bdd. 2nd Moment be satisfied. Then, for any 8 E (0. 1/2) and T [m[n[d]), there exists an E (U. such that the averuge iterute of Algorithm run for T iterations with step-size T/ = and clipping level
Tv 2 LLD)
satisfies the following with probability at least
In mL (7))))
Tr(E) VIEEI22 (VT(()) + LDi) In(")(T//a)
LDJ F(XT) F(x')
T + DIV
or (I., D1.
T
where oT (L, D1, Σ) represents terms that are of lower order in T (explicated in Appendix D
Theorem (Lipschitz Convex Objectives). Let Assumptions Convexity G-Lipschirzness and and Bdd
2nd Moment be satisfied. Then, for any 5 E (0, 1/2) and T > In(In(d), there exists an 1 E (0, G/
such that the average iterate of Algorithm T ruun for T iterations with step-size qp = 17 and clipping
T [Ellaay Gr(
level T=
satisfies the following with probability at least -
(/(6)))))))
Tr(E) + VIEila
V Tr()) + G) In(InCT1/8)
DIG
F(KT) - F
VT + D
+ or (G, D1,2)
T
where or (G, D1. Σ) represents terms that lower order in T (explicated in Appendix
E
Remark: We use Theorem B to design the first known streaming estimator for logistic regression with heavy-tailed covariates in Section [5.3 and Theorem 4 to design the first known streaming estimator for LAD regression with heavy-tailed covariates in Section 5.4
Remark: In Theorems and 4 the leading order term in the error is of the form: Diy
THS++VISTT (IITETI((((())))) (T)()++ (n(1)())/)))) where E (G, Assuming G, D1, v Tr(2)= Vd.
T
we note that the term dependent on the confidence level log(1/0) is lower order compared to Tr(2). To the best of our knowledge, this is the first work which establishes strong confidence bounds in the setting of SCO without strong convexity. Interestingly, our results also improve the best known rates for nab-Gaussian gradient noise. To be precise, [35 Theorem 3.1] shows a weaker bound of
V DD(GG"+ +T())) logt 3 M/r in the setting of Theorem but when the noise is sub-Gaussian
5
Applications to Streaming Heavy Tailed Statistical Estimation
5.1 Streaming Heavy- Heavy-Tailed Tailed Mean Estimation
Consider streaming heavy tailed mean estimation with clipped SGD with access N i.i.d samples from the distribution P. Let E\t C, [[ = m C. We further assume Covl Σ and allow the higher moments to be infinite. As described in Appendix G.I] this is an |COOSpoolleee problem with the
sample loss Ex = ||I e The population loss and stochastic gradient are given by:
F(x) = =|lxx ml| P((C)
g(x: {) x
The following result, proved Appendix G.I via an application of Theorem I shows that the last iterate of clipped SGD attains pear-subgaussian rates for the heavy tailed mean estimation problem
Corollary 1 (Heavy Tailed Mean Estimation), Under the stochastic gradient oracle described above, implemented using N Z In(Ind)) ii.d samples Ei....,EN ~ P. the last iterate of Algorithm 7 when run under the parameter setlings of Theorem satissies the following with probubility at least 1 8
7|1x1 ml|
Tr(E)) + [ 12 Tr((5) (5.) (1(ln())/))
|xx+1 ml|
N N
N +
where 7 x 2
7

---

Comparison to Prior Works The clipped mean estimator of [8 and the clipped-SCC SGD based estimator
with probability 6. Our result in Corollary [obtains a sharper rate of convergence. In a recent work, Lee and Valiant [2] showed that the trimmed mean estimator achieves the optimal rate of /Tr(E)/N when wloog" 8 8-1), d = (1 Our result matches this optimal rate in those settings, but is considerably more general, it holds for any N, d.
in come with a guarantee of the form ||m m S V ToR))
5.2
Streaming Heavy Tailed Linear Regression
In the current and subsequent sections, we use 0 denote the parameter of F. Let R2 x R. Given a target parameter 8" E C, P defines the following linear model:
X Q, [ = 0, B[xx"] > > 0;
[x, (7) + +, B[dx] = 0, E|e S o²
In addition, we make the following bounded 4th moment asumption on the covariates x
(x v) (xx((xx)))))
some numerical constant C4 2 1. Note that we allow both the covariate x and target y to be heavy tailed, assuming only finite moments of upto order 4 for x and order 2 for y. The assumption E|x] = 0 is only made for ease of presentation and our arguments easily adapt to E[x] * 0. Our task to estimate 8 in streaming fashion with access to N i.i.d samples from P. As described in
Appendix G.2 we reframe this problem as SCO under the sample loss f00 x, y) = I (xx, 8) - -
The associated population loss F(0) and the stochastic gradient oracle g x, y) are given by:
F(0) 10 0')0-''''(000 0"); g(0:x.y) = ((x, y)x
Corollary 2 (Heavy Tailed Linear Regression). Under the stochastic gradient oracle described above, implemented using N 2 In (n(n(()) (d) ii.d samples from P. the last iterate of Algorithm when under the parameter settings of Theorem satisfies the following with probability at least 1 6:
10N+1-87
10
7110, 0'
σ
Tr(E)
|1 Tr(E) In(ln(N1/s)
N 7
Amin (E)
N N+
where y x max
C2K²2
TrEx) 1
In (ln(N)66) i [I((((()))) and x
| Amiia (3:)
To the best of our knowledge, 52 Corollary 4] is the only other streaming estimator for this problem with subgaussian-style concentration. Our result above significantly improves upon their rates of
|6,-8"1| N+C Amin (2)
In//s) with < C4dx² In(2/). Furthermore, our result is much closer to
N+C
the optimal subgaussian rate and gracefully adapts to the stable rank or effective dimension [32] i.e.,
deff Tr(E)/1>)) therefore implying significant speedups over 52 in settings where deff d.
5.3 Streaming Heavy Tailed Logistic Regression
Let E Rdd {0, 1} and given target parameter 6* E C, P denote the following linear-logistic model:
Q, Ex x 0, E[xx²] E;
y Bernoulli(@ (0*, x)))
where o(t)= (1 - The covariates are heavy tailed, with only bounded second moments. The negative log likelihood y/x given by [00: x, x) In(1 exp((x, 0))) - y (x, 0). The objective of the logistic regression problem is to estimate 4* by minimizing the population-level negative log likelihood:
F(0) = Ex.g~P [In(1 + exp( (x, 0)) - (x,0)
which is minimized at 0" Here, the stochastic gradient oracle is y(0; x) ) = of (x, 0))x yx. The following result applies Theorem too show that the output of clipped SGD attains near-subgaussian rates for heavy tailed logistic regression. We refer to Appendix G.3 for the proof.

---

Corollary 3 (Heavy Tailed Logistic Regression), Under the stochastic subgradient oracle described above, realized using N 2 (n([n(d)) i.i.d samples from P. the average iterate of Algoritium 7 when run under the parameter settings of Theorem A satisfies the following with probability at least
Tr(E) + V|Ella Tr(E)) + 112122))) In(1n(N1/)) + ON (1)
F(ØN) - ((O)) N
N
where ON (2, D1) represents terms that are lower order in N (explicated in Appendix G.3
Note that the standard analysis SGD, with the assumption that ||x S R almost surely leads to bound of the form 44 Proposition 5]: F(Ox)= - F(0)) S RDd /Dg(/
VN
5.4 Streaming Heavy Tailed LAD Regression
Let = = Rd x R. Given a target parameter 0* E C, P defines the following linear model:
x Q E[x] = O, E[xx"]
y y= (x, 0*) + c. Median(e(x)) = 0
We allow both the covariate and target y to be heavy tailed, assuming only bounded second moments for x. We do not assume any moment bounds on e e|x. The assumption [E[x] of clarity and can be straightforwardly relaxed. The Least Absolute Deviation (LAD) Regression problem involves estimating / by solving SCO with the sample loss f(; x, y) = (x, 03 - y). The stochastic subgradient oracle and population risk is given by:
is made for the sake
g(0; x, y) = sgn(( (0, x) - y)x,
F(0) - B (0 x) - -|]
where sgn(t) E| for + and s0) The following result, whose full statement and proof
presented in Appendix G.4] applies Theorem 4 to show that the average iterate of clipped SGD attains suaauuuuaassian rates for heavy tailed LAD regression. To the best of our knowledge, this is the first known streaming estimator for this problem.
Corollary 4 (Heavy Tailed LAD Regression), Under the stochastic subgradient oracle described above, realized using N ([Indd) i.dd samples from P, the average iterate of Algorithm 7 when run under the parameter settings of Theorem satisfies the following with probability at least 8:
Tr(E) V/EE (r()) In (((((N)/)))
F(ON) ((w))F(O''S F(O' DIV
+ (E,
N
where oN denotes terms that are lower order in N (explicated in Appendix G.4
6 Improved Martingale Concentration via Iterative Refinement
Our results are based on the following concentration result for Rd valued martingales. The proof appears in Appendix F Suppose M, for 0, . is an I2 valued martingale such that Mo = 0 almost surely, the difference sequence V, == M, M,-1 is such that [|v.]| S and E(v.v [[ = Σ, almost surely for every t ,,..., T for some r >> 0. Assume that there exist deterministic
sequences PI....,Pr and 91,.... ... qr such that Tr(E.) S and |E || I Pt almost surely.
Theorem 5. Let q = 1 Σt a and = + ET= Pt. Then, for any 8 E (0, ():
P(sup ||ai]| 2 eST
5
Where g(T, CM V +
PVT r
log (5) and = In [n( / +11 log(d (Id++1)))))) 1)) + Cs for V
+
some universal constan! CM
To prove this result, we first use Freedman's inequality 20 to obtain a coarse-grained go such that P(sup; || M > go /o)T)= < 5. We then iteratively refine this inequality via a PAC Bayesian [8] 1T
argument to show that (sup, || > I++IVT B₂) < ó, where By = (sup, ||MM]|| < VT) and
D < Tr(Σ)= + S& / [ (og)) This iterative refinement strategy, proved in Theorem 14 is one
of the main technical contributions of our work, which could be of independent interest. We arrive at Theorem 5 after K z log log(T log d) refinement steps.

---

Remark Theorem 5 is used to control the influence of the fluctuations introduced by clipped SGD. To this end, let v, be the centered version of clipr g.). ensuring lvvell - 2T almost surely. Suppose
Σ = Σ for some fixed Σ and let I
/ogt K Then, with probability 1 - 8: supigT || X
(T)(E) + T|| log( ). This is sharper than the supişT |l & y (TT((E) log( ( guarantee
implied by the Matrix Freedman inequality [51] Corollary 1.6].
7 Proof Sketch
We sketch our proof technique for the case of smooth convex functions considered in 3 We consider the SGD iterations X1...... X. with clipped stochastic gradient at time denoted by clip- F(x,) + Va + by Here, V; is the zero mean 'variance' such that E [V,] 0 and ||vel - 2r almost surely. b, is the non-zero mean 'bias' which arises due to clipping. Using the usual analysis of SGD for convex functions (see for instance (31), we consider:
||x++1 1 < X x' 11= (F((x) ((sss))FF(x))) - (v, b,, -x-xx))=aa VVFx) b.ll
Considering constant step-sizes, we sum the incqualities for each to conclude:
Σ F F(x)) -
1
|x|
11
1 T
Vz + b Xt x*)
T
21/T
Σ 2T
311
+ l|v. |b,l
(3)
The 'random' terms to bound compared to gradient descent here are E. + b X, - xx) and E. /vvll2 + ||b,|| Lemma 13 shows that ||x; x'1 S 2/|x1 - x"1 with high probability. Under this event, we bound E, (Ve. X; x²) using the standard Freeman's ss inequality and [[V((x)) by using smoothness and the fact that V FF(x*) = O. The bias of the estimator |lb, || is bound using arguments similar to [8] (see Lemma 4. The main improvement of our method given by our method of bounding 1 E, |vall" We show by application of Theorem that } E,Ilv x
Tr(E) + Tr(E)) [ Ei log( Tog with probability at-least whenever the clipping factor I' is
appropriately chosen. Choosing the step size 17 appropriately gives us the result in Theorem
8 Conclusion and Limitations
Our work obtained nearly subgaussian rates for heavy-tailed SCO using clipped SGD by devel- oping fine-grained iterative refinement strategy for martingale concentration. As corollaries, obtained state-of-the-art streaming estimators for various heavy tailed statistical problems. We note Clipped-SGD widely used optimize neural networks with highly nonconvex landscapes, which is currently outside the scope of our work. Nevertheless, we believe our techniques could be useful for providing sharp high-probabilit, guarantees for non-convex losses. Our bounds are currently of the
form T
which is suboptimal compared to the tight subgaussian rate of dn(1((/)) T
Further research is required to understand if it is possible to obtain truly subgaussian rates with clipped mean type estimators. Another notable suboptimality of our result is the (la(()))))) dependence on the confidence level (as opposed to the typical In(1/8) scaling). However, this is not major drawback
as our results continue to significantly outperform prior works unless > exp(vV-1) In(11/))) (which is impractical regime). This drawback arises due to the In(In(7))) iterations of our iterative refinement technique and we believe it can be removed via more sophisticated martingale concen- tration arguments. Our work lays the foundation for several interesting avenues for future work including the analysis of heavy tailed statistical estimation under bounded 5th moment assumptions (for p 2) and the development of parameter free statistical estimators that do not require knowledge of problem-dependeee parameter such as ||>]] etc. (or their respective upper bounds). Deriving anytime valid guarantees for clipped SGD using techniques is also an interesting future direction.
10

---

References
[1] M. Abadi, A. Chu, I. Goodfellow, McMahan, Mironov, K. Talwar, and Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 308-318, 2016.
[2] N. Agarwal, Chaudhuri, P. Jain, M. Nagaraj, and P. Netrapalli. Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. In International Conference on Learning Representations, 2021.
[3] A. Ajalloeian and S. U. Stich. On the convergence of sgd with biased gradients. arXiv preprint ar arXiv:2008.0005/ 2020.
[4] F. Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. The Journal of Machine Learning Research, 15(1):595 627, 2014.
[5] A. Bakshi and A. Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 102-115, 2021.
[6] S. Bubeck. Convex optimization: Algorithms and complexity. 2014. doi: 10.48550/ARXIV. 1405.4980. URL/https://arxi
[7] O. Catoni. Statistical learning theory and stochastic optimization: Ecole d E'Eté de Probabilités de Saint-Flour; XXXI-2001, volume 1851. Springer Science & Business Media, 2004.
[8] O. Catoni and I. Giulini. Dimension-free pac-bayesian bounds for the estimation of the mean of a random vector. arXiv preprint arXiv: /802.0038. 2018.
[9] Y. Cherapanamjeri, N. Flammarion, and L. Bartlett. Fast mean estimation with sub-gaussian rates. In Conference on Learning Theory, pages 786-806. PMLR, 2019.
[10] Y. Cherapanamjeri, S. B. Hopkins, T. Kathuria, P. Raghavendra, and N. Tripuraneni. Algorithms for heavy-tailed statistics: Regression, covariance estimation, and beyond. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 601-609, 2020.
[11) B. Chugg, H. Wang, and A. Ramdas. Time-uniform confidence spheres for means of random vectors. arXiv preprint arXiv:2311.08165 2023.
[12] B. Chugg, H. Wang, and A. Ramdas. A unified recipe for deriving (time-uniform) pac-bayes bounds. Journal of Machine Learning Research, 24(372):1 2023.
[13] A. Cutkosky and H. Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883 4895, 2021.
[14] D. Davis, D. Drusvyatskiy, L. Xiao, and J. Zhang. From low probability high confidence in stochastic convex optimization. Journal of machine learning research, 22(49), 2021.
[15] J. Depersin and G. Lecué. Robust sub-gaussian estimation of a mean vector in nearly linear time. The Annals of Statistics, 50(1):511-536 2022.
[16] I. Diakonikolas and D. M. Kane. Algorithmic high-dimensional robust statistics. Cambridge university press, 2023,
[17] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, pages 1596-1606. PMLR, 2019.
[18] I. Diakonikolas, D. M. Kane, A. Pensia, and T. Pittas. Streaming algorithms for high-dimensional robust statistics. arXiv preprint arXiv: arXiv:2204.12399 2022.
[19] J. Fan, W. Wang, and Z. Zhu. A shrinkage principle for heavy-tailed data: High-dimensional robust low-rank matrix recovery. Annals of statistics, 49(3):1239, 2021.
[20] D. A. Freedman, On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
11

---

[21] E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33: 15042-15053, 2020.
[22] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. Sgd: General analysis and improved rates. Proceedings of the 36th International Conference on Machine Learning, pages 5200-5209. PMLR, 2019.
[23] M. Gurbuzbalaban, U. Simsekli, and L. Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pages 3964-3975. PMLR, 2021.
[24] R. Hampel, E. M. Ronchetti, Rousseeuw, and W. A. Stahel. Robust statistics: the approach based influence functions. Inces-nntrsscience; New York, 1986.
[25] N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579-1613. PMLR, 2019.
[26] E. Hazan and S. Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15:2489-2512, 2014.
[27] S. Hopkins, J. Li, and F. Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. Advances in Neural Information Processing Systems, 33:1 1902-11912, 2020.
[28] S. B. Hopkins. Mean estimation with sub- sub-gaussian rates in polynomial time. The Annals of Statistics, 48(2):1193-122 2020.
[29] D. Hsu and S. Sabato. Loss minimization and parameter estimation with heavy tails. The Journal of Machine Learning Research, 17(1):543-582, 2016.
[30] J. Huber. Robust estimation of a location parameter. Ann. Math. Statist., 35(4):73- 1964.
[31] Jain, M. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. SIAM Journal on Optimization, (1): 1008-110,, 2021.
[32] J. C. Lee and P. Valiant. Optimal sub-gaussian mean estimation in very high dimensions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss -aassss- Leibniz Zentrum für Informatik, 2022.
[33] X. Li and Q Sun. Variance-aware decision making with linear function approximation under heavy-tailed rewards. Transactions on Machine Learning Research.
[34] Z. Liu and Z. Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises. arXiv preprint 12Xiv:2303.12227, 2023.
[35] Z. Liu, T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, pages 21884-21914 PMLR, 2023.
[36] G. Lugosi and S. Mendelson. Mean estimation and regression under heavy-tailed distributions: survey. Foundations of Computational Mathematics, 19(5): 1 145-1190, 2019.
[37] G. Lugosi and S. Mendelson. Sub-gaussian estimators of the mean of a random vector. The annals of statistics, 47(2):783-794, 2019.
[38] V. V. Mai and M. Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pages 7325-7335. PMLR, 2021.
[39] S. Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, 21(4): 2308 2335, 2015.
[40] A. V. Nazin, A. S. Nemirovsky, A. B. Tsybakov, and A. B. Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80 (9):1607-1627, 2019.
12

---

[41] T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Advances Neural Information Processing Systems, 36:24191-242222 2023.
[42] R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks.
In International conference on machine learning, pages 1310-1318, Pmlr, 2013.
[43] A. Pensia, V. Jog, and P.-L. Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv preprint arXiv:2009//2976, 2020.
[44] A. Prasad,
Suggala, S. Balakrishnan, and Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXivv1802.064833 2018.
[45] A. Prasad, S. Balakrishnan, and P. Ravikumar. A robust univariate mean estimator is all you need. In International Conference on Artificial Intelligence and Statistics, pages 4034 4044. PMLR, 2020.
[46] N. Puchkin, E. Gorbunov, N. Kutuzov, and A. Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. In International Conference on Artificial Intelligence and Statistics, pages 856-864 PMLR, 2024.
[47] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference Machine Learning, pages 1571-1578, 2012.
[48] A. Sadiev, M. Danilova, E. Gorbunov, Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov, and P. Richtárik. high--probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In International Conference on Machine Learning, pages 29563-29648. PMLR, 2023.
[49] V. Srinivasan, A. Prasad, S. Balakrishnan, and P. K. Ravikumar. Efficient estimators for heavy-tailed machine learning. 2020.
[50] Q. Sun, W.-X. Zhou, and J. Fan. Adaptive huber regression. Journal of the American Statistical Association, 115(529):254 265, 2020.
[51] J. T.oopp. bility, 16(nome):262 270, 2011. doi: 10. 10.1214/ECRv16-16222 URL https::////o htt::////ooo.o/1100/ 1214/ECP, v62-1624
Freedman's 's inequality for matrix martingales. Electronic Communications in Proba-
[52] C.-P. Tsai, Prasad, S. Balakrishnan, and P. Ravikumar. Heavy-tailed streaming statistical estimation. In International Conference on Artificial Intelligence and Statistics, pages 1251- 1282. PMLR, 2022.
[53] J. W. Tukey. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975, volume 2. pages 523-531, 1975. 1975.
[54] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[55] H. Wang and A. Ramdas. Catoni-style confidence sequences for heavy-tailed mean estimation. Stochastic Processes and Their Applications, 163:168-202, 2023.
[56] Zhang, S. Karimireddy, Veit, S. Kim, Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33: 15333-15393,, 2020.
[57] W.-X. Zhou, K. Bose. J. Fan, and H. Liu. A new perspective on robust m-estimation: Finite sample theory and applications to dependence-udjjusted multiple testing. Annals of statistics, 46 (5):1904, 2018
13

---

Contents
Introduction
1.1
Sub-Caussian Error Guarantees for Statistical Estimation
2
Related Work
Contributions
2
Notation and Organization
3
Background and Problem Formulation
4
Results
4.1
Smooth Strongly Convex Objectives
6
Beyond Strongly Convex Objectives
5
Applications Streaming Heavy Tailed Statistical Estimation
5.1
Streaming Heavy- Tailed Mean Estimation
5.2
Streaming Heavy Tailed Linear Regression
8
5.3
Streaming Heavy Tailed Logistic Regression
8
5.4
Streaming Heavy Tailed LAD Regression
Improved Martingale Concentration via Iterative Refinement
7
Proof Sketch
10
Conclusion and Limitations
10
Preliminaries
16
Analysis for Smooth Strongly Convex Functions
18
Proof of Theorem
19
B 2 Proof of Lemma
23
B. Proof of Lemma
24
Proof of Lemma
Analysis for Smooth Strongly Convex Functions Under Quadratic Growth Noise Model
29
Proof of Theorem
30
Proof of Lemma
34
C,
3 Proof of Lemma
36
D Analysis for Smooth Convex Functions
41
D.I Proof of Theorem
43
D.2 Proof of Lemma
43
D.3 Proof of Lemmal
44
14

---

D.4
Proof of Lemmal
44
D.5 Proof of Lemma 13
45
Analysis for Lipschitz Convex Functions
46
E,
Proof of Lemma 14
48
Proof of Lemmal
Proof of Lemma
49
Proof of Lemmal
49
Improved Martingale Concentration via PAC Bayes Theory
50
Proof of Theorem
51
F2 Proof of Theorem
55
F3
Proof of Corollary
56
Applications to Streaming Heavy Tailed Statistical Estimation
56
G.1
Streaming Heavy Tailed Mean Estimation Proof of Corollary
56
G.2
Streaming Heavy Tailed Linear Regression Proof of Corollary
57
G.3
Heavy Tailed Streaming Logistic Regression: Proof of Corollary
59
G.4
Proof of Corollary
61
15

---

A Preliminaries
In this section, collect some preliminary concentration results which will be used in the future sections. For the following lemma, we refer to Exercise 2.8.5 in [54].
Lemma 1. Suppose X is a real valued random variable such that [X] < almost surely, EX = 0 and EXx² v. Then, for any such that [^] I 2r, the following holds:
E exx((XX) I exp(X>v)
Consider a IR valued martingale (M.) with respect to the filtration (Fr) such that Mp 0 almost surely. We consider the martingale difference sequence V, := Mr M for 2 1. Clearly, we must have:
M Σ V
a=1
Definition 1. We say that the martingale M, satisfies (g, T, uniform concentration if:
P( sup || > gVT) < 8
0S1ST
Assume that for fixed I and Σ E Raxd that |/ < I almost surely and E[viv][[[-]]= =; Mr.
Suppose Tr(E,) I qt and |E,lla S Ps almost surely for some non-random constants Pt. 9t- We state a high dimensional version of Freedman's inequality 20 51 below which follows from From Corollary 1.3 of [51, we have
Theorem Suppose Mt satisfies the assumptions above. Let q =
Exm
qe the following is true:
a²/2 TT + 3
P( sup 055S
[M > a) S (d (1+ exp(
To
That is, for any O, the martingale (Mi)sST obeys (T) uniform concentration, where 2r
(6) 3VT
log( d+d)== + loglog( 411
The following inequality is a corollary of Theorem
Lemma 2. Let 9r E Rd be Fe-1 measurable. Then for some constant Cj > 0, we have:
PIU (1 Σ 9.. v. a) Naga {llaاll s A.)) s 2exp( T Eis Pe
a²
Where = SuPiSIIT A
In addition, we also use the following scalar version of Freedman's 's inequality
Lemma 3 (Freedman's Inequality). Let h1 he...... hr be a Fe adapted martingale difference sequence such that [[ 0, h Fi-1] of and ||hll |l S т. Then, for any 5 (0. 1). the following holds with probability at least 5:
Σ h. < 2 In(4/s)
Σ 0 + 27
The following lemma, which bounds the moments clipped random vector, is crucial our analysis of the bias and variance of the clipped stochastic gradient.
Lemma 4 (Moments of Clipped Random Vector). Let E IR be a random vector sampled from the
distribution P with mean m and covariance matrix S. For any > 0, let = clip- (z). and let m and
denote the mean and covariance of à respectively, i.e. m E(2] and = E [ m) (z m)]].
Then, the following hold:
S
|m||
m|| <
[|ml|
+ Tr(S))
(||m) Tr(S))
1
m 12
|
< |||| +
(||m + Tr(S))
1
Tr(S)
< Tr(S)
16

---

Proof. The proof of this lemma uses arguments similar to that of Catoni and Giulini 8 We first note that for any x I
min [1, 1x
clipr(x) x
D-1
X
Following the proof of Proposition 2.1 of Catoni and Giulini min inf p21
8 observe that for any t 0:
pPt
1
(p 1)
Define 0(x) min 7x Te Note that clipr (x) 0(x) we note that:
From the above inequality,
pe
|
0 < 1 - 0(x)
S inf
(5)
P21
1-+1
Fp
Consider any unit vector e E IRd Then,
(e, m m)
E [(e, 2
E [(e, z 8(z)z))
E [(1 Oz)) (e, z m)] + (e, m) E B[ 0()))
< E [[1 0(z)) (e, z m) + [m
| [(1 0(z))]
pe
|| 2 (e, z m)
PP
2 R
E
inf P21
+ |m|||
inf
(p + 1)p+I
(p+11 1 1)p+I
where the second step uses the definition of ((z) and the last step uses equation (5) Now, substituting p = and p = 2 in the first and second terms of the RHS respectively, we obtain the following:
|m|
(c. m) -
E |||z||
(c, m)] +
B|||
r
||m
B
X
(e
m3²
|[[|
r
S||
m
2 + Tr(S)
[|
|| + Tr(S))
r
r
||||
m
|||| + Tr(s))
(Ilm
Tr(S))
T2
where the second step uses the Cauchy Schwarz inequality and the last step uses the subadditivity of the square root. follows that:
im- m||
= sup
(c.
m.m--
m)
||||=1
S
+ m
|m|| + Tr(S)
(||m| 2 Tr(S))
r
1
To bound ||S|], we first note that for any x R 0 f(x) 1. As before, let Bd denote an arbitrary unit vector. We note that El m) El m Hence, follows that,
E[(e, ž m) + El m m) 2
E (e, m)?
E
(e, m)?
E
(0(z) (e, 2) - (ee, m))²
E
(0(z) (e,z m) (1 - -zz)) (e, m))²
< E (()) (e, m)? + (e, m)² 2 EE [(1 0(z)))
||
< E (c. z m)?] 27
||m
|E
inf P21
(p+ + 1)p+1
rp
||m|] |E[|]
||S||2 +
T2
|m
||||
(|
| Tr(S))
12
17

---

where the fourth step uses Jensen's 's inequality by noting that 0 S 0(z) - 1 and the fifth step uses equation (5)
Finally, To upper bound Tr(S), note that clipr is contractive mapping as it is the projection operator onto convex set (namely the ball of radius I' in RS centered at the origin), To this end,
Tr(S)= = B || ml|
E 21.22
tot (z)) clipp (22)
E
[||z]
z211 = Tr(S)
2 21.02
The following result, which is a corollary of Theorem [] is vital for controlling the error introduced due to the variance of the stochastic gradients, and is one of the major components of our analysis. The proof of this result is presented in Appendix F3
Corollary 5 (PAC Bayesian Inequality for Quadratic Variation). Let Vi...., VT be an IRd val- ued martingale difference sequence adapted to the filtration Fi...., FT satisfying [[a O, VVv. = Eg and ||vall S almost surely. Let UP(() := min(T, 21lo82 d) Suppose some universal constant Crower such that whenever T > Clower log((1 + I log(d + 1)) such that the following inequality holds with probability least 1 - 8, for any 8 20
|| 12 S ps and Tr(E.s) S qs for some fixed sequences ,I,....PT and 41....,... QTT Then, there exists /TT
UP(()
(P(E)
Ilvv S CM
Σ as +
In
(2
Cml
Σ V2 [
72
where Ca > O is absolute numerical constant.
B Analysis for Smooth Strongly Convex Functions
Let delf Tr()) and let K (8 CM, In())). For t 2 1, define the filtration Fi T>l
a 1K1,ga1 | < 8 < t) and Fo (x Furthermore, let (x,)) = clip, (g:) + b, + v, where and v. B|clip (g:) [F- clip (g:). We note that
b Vx(x.) (gc
Eiv, Fr-1] = 0 and
1v < ||clip (g:)l (g:)) ]]1 < ||lipp g - (gl)) $ 21
where the first step follows from the triangle inequality. the second step uses Jensen's 's incquality and the last step uses the definition of clip,. Hence v, an F adapted almost surely bounded martingale difference sequence. Now, let D, = ||x, x*1 where x" is the unique minimizer of F' (guaranteed by strong convexity).
Evrry where A > 1 is a numerical constant and 2 An + A 1 is constant depending on K, d and In(s/) which shall specify later. Note that our choice of ensures that 7/ Σ T.ッ for t E [1 I] We prove the following recurrence for D, by using the smoothness and strong convexity properties of F and by exploiting the choice of the step-size.
Lemma 5 (Recurrence for D.). The following holds for every i E [1 []
2 2 [+77)
24
A22A+1
1 1-2A-1
D241
D2
(b,, X, x")
(1 (1+ 7)+
4
424
(8 + (+77)22-2 2A-22
A22A+1 t
(8 + (3+7)22- 7)2A-1
+
bul ||
(v,,X,->)
112
(t (t+ 7)+
(t 7)2A
1244+1
(s (s+ 7)+ (1 + 7)2A
+ 112
||va||2
18

---

Now define RI,5 as follows:
R (7 1)+ + (T + 1111112
(det + dett In(K36))
n?
It is easy to see that I' "yRr, Tm(
In our proof of Theorem
| we shall establish that the following
holds with probability at least
6:
CRT, Vt [t: D S (1+7-1)3
where C' > is absolute numerical constant to be chosen later. To this end, we define the event Eg and the random variables d,, by, Ve as follows for t E [1 T 1]:
CRr,
E, = D2 - (++7-1)) 1)2
d, = (x: - -x')1
b. b.1 {Er}
V. - v,1 {E,}
We note that since X is Fi-1 measurable, so are { de b, and b, Furthermore. B[v, = Fi [E.] 0.
We use the following Lemma to control the bias vector b.
Lemma 6 (Bias Control). The following holds almost surely for every E [1 T):
1 + (1+7- d(T +7) (1+
xIn(1/s)VC
RVCIn(y/)) 1)(T +
||bI]| / RT,8
T+7"
We the following lemma to control the variance vector v.. The proof of this lemma, which uses Freedman's inequality and the PAC Bayesian martingale concentration inequality of Corollary 6 Lemma 7 (Variance Control). The following holds with probability at least 1- - 5 uniformly for every t [T] whenever A 2 3 and 7 2 maxx(x (/ In(lu(()/6)) NVC In((tu((//)))/a
(s 7
(V., d.) S 27pRT,SVC
(1 71+
2A-2
Σ (1t7)
1| S Cmp2 RT, (6+3 22A-13 2.4-1222113 + 24A-17)
where Cas is the absolute numerical constant defined in Corollary
Equipped with this bound on the bias and the variance, we now present the complete proof as follows:
B.1 Proof of Theorem
Proof. Let A 2 3, 2 4 m (n following event
Now, let E denote the
(s + 7) 21
E
(V., & 2T
(t+ 72--2222
2A-2
s +
|| < Casp" RT, (6+ + 3. 24 13 +3 22 VI E [T]}
P(E) 8-8. We now claim that IP (n E: 1, i... conditioned on the event E, the following holds almost surely for every t [1: T +
Note that by Lemma
CRTs VtE (
Dj < (1+7-1) 112
19

---

We prove the above claim by induction. Note that the claim is trivially true for t = 1 as RI.5 2
(7 + 1)2D2 Now, consider any & E [1 : 7] and suppose the claim holds for some S S L.
Recall that by Lemma 5
1)+ (1 (1+7)22-1) 2) DJ
A22A+1
(8 1
(t (t+>) D2-
(b,; X; - -x")
(1+ 71+7)22-2
M
4
(s + 7)2
A22A+1
(8 + 7) 7)2
||b,||
(Vs, X, x")
112
(1 + (+7))2-2
1
(t (++
A 444
(s + 77)22-2 (1 + 7)2A--2
||v 2
112
Under the induction hypothesis, (E,) Vs E [t]. Hence, Under the induction hypothesis. CRr
D [++7-1)++1-2) and thus, d, x, - b., V. v. A S S t.
Substituting this transformation into the above inequality, we obtain the following:
17+ DJ + A22A+1
(s + 7)
(++
(t + 2 d.,, d.)
(t (++
424
(s + 7)2222
(s + 7)2
[oll
(1 + 7)2A-2 (bs.d,)
112
(L 22
8=1
A44
| (s + 7)
b
(6)
n²2
(t + 2
We now bound each of the terms the RHS as follows.
Bounding !
Since A 2 1 and 2 1,
( 1)24 (t 72 Di < (7 RT,5
Since 7 and A satisfy the conditions of Lemma 7 and we have conditioned on the event F,, follows that:
Bounding 2
A2 t
(s + 2)
(++7)2A-2 (V,, 27422441 RISVC
Since y and A satisfy the conditions of Lemma 7 and have conditioned on the event E, it follows that:
Bounding 3
A244+1 2
f
8 877
2A-2
| S 22422 (6+3 24A-13 +3. 22A-177 RT.
(+?)
Before controlling terms and 2 we note that the following holds for every s E [t] by Lemma
|b S nv R (B) - B, + Bg + B1)
20

---

where BI...., B1 are defined as:
1
Bi T+7
kln(K//VVCC
B2 (8+ 11V--(+ 77)
100% (1(K))(
B3 (s+7- 1)3
kIn kl((k/83VVC
B4 (s + 1)(T + +7)
Bounding 4
Since {Fa) =1
CR
2/ //RR5
||&I|
8 8
8 ++7
Hence,
A22
Σ bz, d
(s 2--11
I A22A+2
RI RISVC
(877)
2A-2
(B++ + B2 + B3 + B1)
(t + 722-22
t+,
We now control the first term
7 7
2A-2
8 18+7 7 t+t
2A-2
B1 T+* 7
t+g)
$ T+ < 1
where the first inequality follows from the fact that A 2 1 and s S
We now bound the second term
Σ
(++7)
8 +
2A-2
B₂ B&S xVCIn(K/b)
Σ
8 + 7
2A-2
1
Vd(T +7)
8
Setting A 2 3/2 and using the fact that
3- 2 follows that
2A-2
2x (n(68)
(s (s+ 224-33
Σ
B₂ 5
Vd(T +n)
(t + 7)2A-2
DnVCIn(K/s) 2
Vd(T +7)
Cx² where the last inequality follows by setting 7 2 - IoIlnn(])) (n(K)))2
To control the third term, we set A 2 5/2 and proceed as follows:
2A-2
(s + 24-5
7
Bg S k 3 (n/7)))
t+a
(t + (++7)22-2 2A
k 8/2 1 1n(3//)22
(1+ 7)2
C/22 12/66))2
51
(7 1)²
where the last inequality follows by setting 2 k To bound the last term,
3/2 /// In(
Σ
8 8
2A-2
kC In IC (3/))
(s + 7) 2313
B1 S
t 1+7
T+y
m=1 (t+ 72A-2
<C 1n(182
$
x+1
21

---

where the second inequality uses the fact that A 2 8/2 and the last inequality follows by setting 2 kO ln(K/))2. Putting it all together, it follows that
S 554 A+1 RI,SV
by setting y as follows
C2C ln(K/88, 2h C Ceeh"//nnn/ In(4/6), (nt
7 2 max
Bounding 5
By Lemma
6 and Jensen's inequality
|b,11 S 41 RT, (B] + B3 + B3 + B3)
It follows that
A
||
$ +
2A-2
I A24
s+7
2A-2
(B) B3 B3 Bi)
112
(+1)
t+y)
The first term is controlled as follows using the fact that A 2
(5$22)
2A-2
Σ
B
(T + 7)2 $1
(+7)
8=1
The second term is controlled as
++
24-2
4n (1/K/62)
(8 78
B3
1+7
d(T +7)
(1+ 722-22
4x In2CIn(K/8))
d(l + (T 77) $1
where the last incquality follows because y 2 xi c (6/6)) For controlling the third term, we set A 2 4 to obtain
+ t+?
2A-2
B = K 6 6 In(K//))))
(s + 222
(t + 7) 2A
In
< (7+ 1)5
<
where the last inequality uses the fact that 7 2 k 0// In(K/s)* To control the fourth term, we use the fact that 2 2 to obtain
8 +
2A-2
C²((nnK/))
(8 + 7)
B²-
t t+
77)
+ 2A12
*²((n(K/6))
(x+1)² 1)3
where the last inequality uses the fact that 7 2 C// In(K/o) From the obtained bounds, conclude that 5 - 4+4 RT,5.
Hence, setting A and y = 4C max [| (n(l tain the following
2/ Ix we ob-
Tr(2)
(1+7)2D2 < 1 2 + 3 + 5
RT.
1+CM22A42 (6 (6+3 3- 21A-13 33. 21A-17) + A24 + vo (27A222441 + +5A44+1]
Rr,
(262145 + 524288Cas + 75776VC
< CRTs
22

---

where the last inequality is obtained by setting C (V262145 524288CM 75776)* It follows that
CRr,
D S (1)
Thus, we have proved by induction that conditioned on F,, D2 S particular, the following holds with probability at least 1 - 6:
CRr for every E [T + 1]. In (147)²
7+
C/ (delf + ddell In in(K/6)
Dz+1 SC
Dj +
T+7
(T + +?)
7+1
Tr(E) + V| 2 Tr(E) In(ln(7)))) (T +
X
D +
T+7)
B.2 Proof of Lemma 5
Let = b: + Va.
Di+ [ 17: (F(x) + m)))) x²
< | 1/: (xxx) + mhel1
< D 27 (Vx X4 - xx)) + 277 (EL. x²) + / + 2 cel1
By the coercivity lemma in Bubeck 6
VF $ (L + (1) (VF((x) - LIuD
follows that,
D I (1 - Dz - 2mp | 11(L + μ4] (VF(x)), Xx - -x") ) + 27/ (E1, x') + 2n/ cell
S (1 L1)) D3 2n (T. + u)) + 21tt (0,, -xx) 2n/ 1e:
(1 2nH 2nd 12 )D? + 2n (E,, x x²) + 2n/ 1|:
(1 24/ DJ. 2Tje (c,, x, x*) + 27/21 e|
where the second incquality follows from the strong monotonicity property of VF(x) and the fact that 1/, S L+u since 7 2 An + A Now, substituting 1)+ p((+T))
D2 < (1
24 t+
2A (e, xx") 12 + 7)²
2. 1eel
Dj +
x(t+7)
Since 1 - Vt I,, we note that Vs < t:
II
2A
- Σ
2A
S exp
j=st1 j +
j=
1+1 du
S exp
2A
u u+?
t+ ++1+7)
cxp
24
8 8 ++1+7/
24
++++1)
S 224
8 (8+7)
t t+g
23

---

Using the above bound to unroll the recurence
we obtain:
D
1
2A
D +
2A
c. X x*)
II j=s+1
1 (1-
2A
j+1.
(s 77)
j=1
==1
2
||E 1
1 II
2A
112
(8 + 7)2
j +
jms+1
7+1
24
A224+1
1
(8 + 78+7)2A-1 7)
A222A+1
+ 2222-22
D
- xx) X, +
||s ||
1+7
(++ 7)24
112
(t 7)+
Expanding Cs b, + Vs and using Young's inequality, conclude that the following holds for
every 1 E [1 T]
7 7 t+y)
24
A22A+1
+ 7 11)2--1 (t 72+
D& $
DJ +
(b,, x, -x")
A244+1
lb&l1 (8+ (8+7)2A-2
A224+1
(8 + 7)2A-11
+
(V,, -x)
112
(t (1+7)) 7)24
(++ 7)24
sml
A44+1
(8 7)2
+
|
n22
(t 7)2
B.3 Proof of Lemma 6
Note that by definition of E,
|VF( & (D,1(E,}
v CRT,
s (1 (1+7-1)
Recall that I'
PVRTS In(w/a)
i.c. VRT,5 2ln(1))) Substituting this into the above inequality gives us:
RI' (n/K///VCC
|VF (ED
(8)
1+7-1
We recall that b. = VF(x)) E clip F
[f-1 - (r) Since
Cov[g:[Fe_-1] < Σ by Assumption Bdd.
2nd Moment we obtain the following bound on ||b:||
by an application of Lemma 4
|E|2vderi deff
[VF(())IVVEE)
[[F((x))
||||det [edde///Vii [Fx())
|b.l 5
r
r
1
1
Since 6, b, (Fee), it follows that
[Dllev detf
V 1 {E. v
E
|| {E{}
| /F || {E.)
|bb,1
<
+
+
+
r
r
r
Bounding A
By definition T,
[E dem
|E||2 / den (n/65/))
/v R
(T + 7) El2 V In (K/6)
μTl /Rr,5
"v RI.5
(T + 7)
Hy /y/r,8 R T+7
Hence A <
24

---

Bounding B
Since RT, [Tlladen(T+r)
PyRTA vd(T+>)
Substituting this into
equation 8
VF {EA) v 12
vVCIn(K/))
Mv R
1 1+7-1
Vd(T +
xInl/ssiV (dt7)
Hence, B S IV R
Bounding C
From equation
[V
C In(6))
r2
(1+7-1 1-1- 1)3
S Hv Rr.5 . x3
(1 71
12
Hence, (9 S (n/Roo Rr.
(14-
Bounding
Recall that,
1.2 RT
| 2d
T+7
V VF {Ea}
xIn(K/8)vC
r
( -11 1)
PV R
r
ln(K/a)
follows that
Σ 22
VF [ {Er}
kln(k/6)VVC
D
HV RI,5 (++ - 1)(
1
Hence,
s xIn(/saVCC
C/ IC188)(1)) kVCIn(3/)3
[[ball S HV RT,
(++ + (8+7-1)(2 +
T+* (++ -
B.4 Proof of Lemma
For any s [2', we recall that v. E (g.) clip (g)) Since Egg, VF(x.) and Covig.|F= = E, we obtain the following from Lemma 4
VF(x))Il
VF 1| (Tr(T))
|E v. [ ] || [[Cvv (c.
|| +
r
Tr (E [ F--1]) Tr (Cov (g.)) Tr(
For E [1: T) define V F ]] = Σ.. Since {E,} is F.-1-mmasurrabll and v, = v.1 {E.}.
follows that Σg = E V.v inequality
1 {. Hence, we conclude the following from the above
VF(
[F Tr())) {E.}
1 < || +
r
r2
Tr (T.)) S Tr(
Now, for E [t], define h2 as follows:
(s (8+7)2A-1
h (V., ds) (1 7)2--2
25

---

(st0)22-1 (1+7)24 2 0. Furthermore, since || S ||vell s 2r
Note that E|h F
CRr
and ||d,|| v 8-7-1
v VCR,,
(s + +77)2-11
1h11 S 2r-
8 - 1
(t (1+771 7)2A-2
2A-2
8+7
< 4r CRR,
1+7
AuRTTavC In(K/8)
(10)
For s E [t], define of = 1[hh It follows that,
(s ( V.
d.
()+7)41-4
(s ()
+ 77)dA-- |vo
1/112
4A-4
8 (
4CRT,
|S11|12
|+
s+7
4A-4
VFx,)]]
4CRTs
|||| +
1++7
r2
T2
where the last inequality follows from equation (9) and the fact that det = Tr(E///E12.. We now use the above inequality to control E. o² In(K/s) as follows:
4A-4
Σ of (n/6)) < 4CR1, In (6)))
Σ
|
t t+,
44-4
4CRr, (0fr,sln(K// In(K/s)
Σ
8
t t+?
r
s s+?
44-4
VF
112
Σ
2e
4C ln(K/))
(11)
T2
We now control each of the three terms in the above inequality as follows
8 1+7
4CRT, (n(6/))
[E|| S 4CBr ln(1/))|1)122
(+4)
1.2 R2RS
< ACtRr,
(T + /eff
S S4,2CR2
Before controlling the remaining two terms, we recall from { in the proof of Lemma ?? that
RI (K/8VCC
[VF((x))]I (Ea)
$ +
2n Aalln(K///) K/6)VC
8+7
where r "y R [/(]
follows that
[F(xx)]1
16x402T2
12
(s 7)+
16x C22 L2 (n///)2
= RT, =
(s + 7)
26

---

Thus, we can control the second term in equation as follows
4CR (n(k/)
8 +
1A-4
(x,
II
S 6Ap2
in(
(s + 7
t (+y)
r
(t + 7
S C1 Cm200(()))
(1+
I 644p2CR
where the second inequality follows by setting A 2 2 and the last inequality follows by setting 2 x²/
To control the third term in we note that by equation ( and the definition of RT,5
F
|
2detf
<<(1n(k/))2
S 44
R
(T () +
It follows that
4CRT, ln(K/s)
+ ?
4A-4
VV 11 Σ 22eff
S 116
CCC(nKK/))
(s 2)+
t +
T+y ==1
(t 72)444-
*²(In(K/6) (T ()+
- 16y"CR
S 16p2C177s
where the second inequality follows by setting A > 3/2 and the last inequality follows by setting y kVCIn(K//)>> Substituting the above bounds into equation
note that
of (m(K)) < 84,2
Thus, by Freedman's 's inequality (Lemmaa) we conclude that the following holds with probability at least 1 - 6/2 uniformly for every & E [T]:
(s 2)+ 2111
(t (++7)22-2 (V,, d.)
h4 2
of (n(6/) + SuRT,s 27RT,VVC (12)
A-1
To prove the second inequality of this lemma, we define 2 = - that Elz, F F--1l = 0 and ||z,]| S |[ S 2r. Define the PSD matrices G2 = Elz,21 [Fo1]] =
for E [t]. Note
747
Σ. Recalling that Tr(E.) S Tr(E) and the bound obtained on [Eu12 in equation
we infer the following:
2A-2
8 ++7
Tr(G..) <
Tr(E)
++
8 8877
2A-2
(8+7)
2A-2
VFF(x,)
11 {Es)
|G.ll2 S
|| +
t+
t+t
(8+7
2A-2
(P(()))(T(((E) {E.)
(t+r)
r
Substituting 8 into the bound for
[Grll2, we obtain the following
2A-2
8 + 7
Tr(G.) S.
Tr(E)
(
24-2
|| + (s + (5+7)22-0
G. l S Ps =
(t+ 7)A-) 16x (n(K/8) Ro.
1+7
(8 + 22
4x ())()())))
(13)
(1+ 7)22-2
27

---

By Cauchy Schwarz Inequality,
1A-1
(s 7)
p3 33
3
8 +
12 +
2556 (n(//())) R7,
t (+
(t ( 4)
(8 + 4)
+
16k - C lm(K/))) 1
(14)
(t 7) -)
Since T [n)))ndd), K = (n()n(T) and as S Tr(E) Vs [7], our choice of T ensures that the conditions of Corollary are satisfied. Hence, by Corollary we conclude that the following holds with probability 1 8/2 uniformly for all t E [T]
(P(()
(P Cast
Σ
|2.11 4C ln(*/6) + CM
Σ
9. +
Σ P
4
Simplifying the above using equations (3). inequality which holds with probability at least 5/2 uniformly for every E [2]:
14
and the definition of I,, we obtain the following
UP(()
24-2
3CM
UP(()
4A-4
t tln 1n(K/6))1111
2z 1 < 40Mp Ry, + CM
Tr(E) +
Σ
f+7)
4
t+7
1² RT.
3 M
UP(()
(s + 7)4
(1 (1++ (++7)4d )dAAT 256/x Ca ( RT,
4
3CM
UP(()
(s + 2 16th CF ln(K/))&T((E> 1²2 R2R
(15)
4
(1 + 7)
We now simplify each term in the above inequality by using the fact that UP(t) I min 26). To this end, the second term is simplified as follows by using the fact that A 2 1
(C
4A-4
Σ
Tr(E) I UP(+) S RT,
We now control the third term as follows using the definition of Ryys and the fact that A 2 1:
(P({)
+
4A-4
An((1/)/1E11 1.2 12RT
(UP(L)
I 12 RT, I(T+7))
t t+y)
S S1²TS
To control the fourth term, we use the fact that A 2 3 and note that for 8 S 21, (8 + 7) S 2 +7)
(P(()
(s (8+))44-12
2 (s (s+
256 0 In(//)) 2 Rys S Rr 2 2 In (K/8)
8=1 (t (++7)
(t+
2241 8 C+ (/6)
< 4² RT,55
(1+7)8
24 CA
< 1º² RTT
71+
41² RT, 21A-15
where the last inequality follows by setting 7 2 4k 4x (n(/))
We control the last term by similar argument
(P(
(s (8+7)44- 16tx 'C In ln(K/o)&TT(E)²
2t (s 7)
S 2R,,
C
(t 74))44
4.² RT,
(T 7)²
( ( 77)444-4
t²
24 x2 C22 K/6)
$ (T + 2t + 7))
< 141
11 1 R
28

---

where the last inequality follows by setting y 2 AnvCCin(K/))>> Substituting the obtained bounds into equation
[5]. we conclude that the following holds with probability at least 6/2 uniformly
for every E
[
2A-2
Σ
8 5
| = Σ |2z1| S CMpp Rr, (6+ 3-44-24-13 + 21A-17)
The proof is completed via union bound.
C Analysis for Smooth Strongly Convex Functions Under Quadratic Growth Noise Model
B let K = 4 m Cm. (T)) For fort > 1, define the filtration Fe = o (x1, (x1,g.|1 < 8 S t) and Fo = (x1). Furthermore, let VF(x)) = bb where b, = - As beforem, we note that Fiv = and |/vl| - 2r. Hence V, is an F adapted almost surely bounded martingale difference sequence. Now, let D2 ||x -x"1 where x" is the unique minimizer of F (guaranteed by strong convexity). We also define E = E(x,) and note that |I I aDe + B and Tr( S delf (aD? + B). Furthermore Σ, is Fi-1 measurable. Let 17c = 1+y where A 2 is numerical constant and 2 As + A - is a constant depending on k. d and In(1/) which we shall specify later. Note that our choice of y ensures that 1): S L+u for t E [1 7) An application of Lemma 5 shows that Dr satisfies the following for every L E [1 :
Following convention similar to that of Section
F and v. = [ (g:).
A
7 7
2A
A22A+1
1)2A-1
D2+1 S
(b.: X, x*)
t+y
7)
A24
(8 ++)222--2
A22
1
(s + 7) 2
+ 112
[bll?
(Ve: -xx x*)
(1 (1+7)) 71+7)22
(1 (1++ 7)24
6=1
124A+1
(s + +)+7)2 2A22
+
|v.11
122
(t 7224
We now define R as follows:
RT = ()+) +
(T + 7)B
(deir + V delt In k/))
122
My RT.5 In(K/o)
It is easy to see that r holds with probability at least
In our proof of Theorem I shall establish that the following
6:
CRT, (tE
Dt S 11)
where C' >>0 0 is an absolute numerical constant to be chosen later. To this end, we define the event E, and the Fe measurable random variables d,, b,, v, as follows for E [1 + 1]:
CRT,5
E, D < (++7-1)2
d. = (x: xx)1
b, b.1 {E{}
v. = v,I {E.}
We use the following Lemma to control the bias vector b.
Lemma 8 (Bias Control), The following holds almost surely for every E [1 T):
[ S HV R
B3
j=1
29

---

where BI..... By are defined as follows:
1
B1 T+7
B1 4nCVVIn((((m)))
1²(++7)²
B3 = (8+ d(T +7)
B4 4xC' 4nC(In(u((11/8)6
1488 + +)22
8x/0 (n(n(T)/8)
B3 =
(++
2xV 2R/CIn(n((T)/))
Bg (s + (T + +7
Sand In (nn(((()//))))) (~)
B7
We use the following lemma to control the variance vector Vt. The proof of this lemma, which uses Freedman's inequality and the PAC Bayesian martingale concentration inequality of Corollary [
Lemma (Variance Control). The following holds with probability at least uniformly for every 2/3 2 1/3
t e [T] for A 2 and 2 4C max oday a In(K)))
4/ (n(K/),, 16 In (K/6)//
In (//))
a²a
(s 7))A-1
(t+ 2)21-22-2 de) S 34 URR.VV
s (tt)
2A-2 1| S Cas
(241-325
25 5. 24A-11
+ 5. 244-11 + 241-13) 12? R
where Cas is the absolute numerical constant defined in Corollary
Equipped with this bound on the bias and the variance, we now present the complete proof follows:
C.1 Proof of Theorem 2
3/5 1 1 1/3 ta
Proof. Let A 2 7 2 40 max cdke, ali((//)) n In(K)),,
In (K/6))).
Now, let denote the following event
(s 7
E
(1 7)2--2 (V., d.) 34 HRr. pRTssCVL
2A-2
++7
| 1 53 Casp Ry, E [T]
t t+g
8. We now claim that IP (n E,(E) 1, i.e. conditioned on the event E, the following holds almost surely for every i [
Note that by Lemma 9
P(E)
CRTs DJ (t+ (tE
We prove the above claim by induction. Note that the claim is trivially true for t 1 as Ry,5 2 (7 + 1)2 D?. Now, consider any t E [1 T] and suppose the claim holds for some < t.
30

---

Recall that by Lemma 5
(7+1)22
A224+1
(8 + y - 1)2A-1
(1 (1+7) v (++
7) D2
{b. X, - -xx
(++
1=1
A74
(s 7)2
A22A+1
(s + 7)
112
|bal
(1 (1+7) (1+7)2A-2
+
(1 + 72A-2 (Ve.X. -x)
==1
1344+1
(8 + 7222-2
||
11
(t + ())))2--2
Under the induction hypothesis, [ = 1 vs E [4] Hence, Under the induction hypothesis, CRr,
{
D3 S (st7-1)(+t722)
} = 1 and thus, d, = X - x", b, b., Vs V.
A
S s S t.
Substituting this transformation into the above inequality, we obtain the following:
1)+
122A+1
(s + 7)
(I+ (1+7) <
(1+2)2A-2 D2
(1 22-22 V.)
(1
1
!
(8 +++7 72)2
(8 + 7
(1+ 2 { (b..
112
(1 + 2)
A41
1 (s + 7) (t + 2
by
(16)
112
8=1
We now bound each of the terms the RHS as follows.
Bounding !
Since A 2 1 and t 2 1,
( (1 (1+ (1+7)2A-2 DJ S (7+1) < Ro,5
Bounding 2
Since y and A satisfy the conditions of Lemma 7 have conditioned on the
event E, it follows that:
2
(t+7)2A-2 (V., d,) < 1714 RI,
Since 7 and A satisfy the conditions of Lemma 7 and we have conditioned on the event F, it follows that:
Bounding 3
434
2A-2
1iel1 < A222A+2 2M
22
+ 241-11 5.. 241-611 + 5 241-13 13 RT
n22
(+t)
Bounding
4
Since {E,} =
/CRT
2/RRT,
|d <
s +
$ s+7
Hence, by Lemma
+
bay d,)
(s 7A
(t + ク22カー2 S A22
RT.VV
Σ
s st
24-2 7
Σ B₁
4
t+
j=1
31

---

We now control the first term
7
2A-2
8 8
21-2
Bi = T 7 s=1
t+y
i+t
S T ++7 1
where the first inequality follows from the fact that A 2 1 and 8 S t. We now control the second term
+
2A-2
4aCVVln(K3()
(s 7))
B2 S
t+y
112
71+7)22-
4aCVVln(K//6
(((++7)
where the first inequality follows from the fact that A 2 2 and S t and the second inequality
follows by setting 7 2 (a(k/))())))
n²a
We now bound the third term as follows:
8 2A-2
2BV CRV(1)())))
(s + 7)2A3
Σ
B₂
t+?
+7)
(t + 7)21-2
CnVOIn(K)
((T++))
1x2 1113/60
where we use the fact that A 2 2 and set 2
d
We now bound the fourth term as follows:
+
2A-2
AnCIn((/6))) a
(s + 7-144-
B4
1+7
1
+ 722-2
AnClo(K/))aa m(++
S1
where A 2 and 7 1xC Lo/ooo/
"
We now bound the fifth term as follows
2
(s 72
Bs S 8N 8t ln(K/))2 (n((k)))) 2
(t+ 2
8/'0%/2 (K(K6))
<1
(t+
where A 1 and 7 2 4k 2= 000/ (k/6)).
We now bound the sixth term as follows
2A-2
2x CRVCmnl 1lnK//6)
(s 72
BB S
t+ッ
T+y
22+
2x 2KVCln((K/)
51 T+7
where A 1 and 7 2 2x 2NVCIn(K//)
Finally, we control the seventh term as follows
+
2A-2
By Sand In (K/6))K(())))))))))))) 20
(s + 2)2
(+1)
12
(t + 722--
8and In( (
1
12(1 7)²
32

---

Waaddl((//)) Putting it all together, follows that
where A 2 and 2
S 7A4 A+1 RI,VVCC
by setting y as follows
avdin(K/o)
x² (n(8//22 kyaln(K/6) 22 xn((/)),
Vnad In K//)
7 2 4C' max
112
Bounding
S By Lemma
8 and Jensen's 's incquality
||b.112 S 7u² RT,
B3
j=1
follows that
2
|bb
s +
24-2
S71222A+2RRT
2
RT,
8 8
2A-2
Σ
B3
(
t ttg
j=1
The first term is controlled as follows using the fact that 2
24-2
8
B²
(T +7)2 $1
(+7)
==1
The second term controlled as
+7
24-2
16a 16a Cn (n//8
(8 78+
B3 <
t+>
1rt
7++-)
$
7)
2/13 a 2/3 2/33 133 11(K3))
where A 2 3 and 2
The third term is controlled as
21-2
4n/6/n(K/0)
(s 2
S
1 1+7
d(T +7)
(1 (1+7)22A-2
4x In²CIn(K//8)
d(1 (T +7) 21
where the last inequality follows because 7 2 k/ / ln(//))
The fourth term controlled as
Σ
+
2A-2
B3 <
(s 72A-6
[+7)
122
(1+ 722-2
2/33 2/3
In( (8/))
2/3 1/3
where A 2 3 and > >
For controlling the fifth term, we set A 2 4 to obtain
1/3
+
2A-2
(s 22
B3 = In(K/))))))
1+7
(t+ 724-2
* $1
S 1)5
where the last inequality uses the fact that 7 2 n Ln(K8))
33

---

To control the sixth term, we use the fact that A 2 2 to obtain
2A-2
x C2((61//))
(8 + 7)2A-1
B
t t+y
(T 7))
22
R² C(((((]6)
S
1)3
where the last inequality uses the fact that y K C// in(K/5)4s To control the seventh term, we set A
obtain the following:
2A-2
+ 7)2 64a (kk(5)) S 1
64a n22 (2d]n((/6)6
B
t t+?
10
(t + 2)21-2
( 7)
where 7 2 a 2/0 d In(
From the obtained bounds, we conclude that 5 S
4/
494244+11 RT.5.
Now, we set A and as follows:
ad avdIn(K/8) kValn(K/)) VnadIn(K/s) 2/2 (n(K/)) x In (n(K/6). In(K/b))
n² (2In(K/8)
y max 122
12
1//
d
Under this setting of A and we obtain the following
(L + 7))
!
+++++++
+
241-3 25
RT, + A222A+2C 22
+ 5
24A-111111
5..
241-16
+ 5. 241-13
4
+ 494444411 24444+1 VO
RI,5 (802817 + 6946816CM 98304VC)
CRR.5
where the second inequality holds due to our choice of A and y and the last inequality is obtained by setting C' = (V802817 + 6946816CM + 98304)². It follows that
D S CRTss
(t+
Thus, have proved by induction that conditioned on E, D2 S CR for every t [T +++ 1]. In particular, the following holds with probability least 1 8:
(1+7-1y²
DJ s 7 7+11
2 DJ
CB (dot + ddn In(K/))
T+>)
12(T+
C.2 Proof of Lemma
Following the same steps in that of the proof of Lemma use Lemma 4 and the fact that Cov|g. F(-1] = Σ, to obtain:
[|b.1 < E3
deff [Fa)
VF | Σ. 1 {E.}
|VF x,
31 (Ea)
[3 det
VF | (E.)
1
1
34

---

Bounding A
Note that by Assumption QG 2nd Moment
|= (E,) - (B aD {E,}
4rCRr,
8
(s ()+
follows that
LEllevdi {E.}
B (K/1))
AoC'l((K/)) RRr, +
u(s+7)
Since / delt In (1/6)) S
R 74.
we obtain
|+ vái {E,}
4aCIn(K/a) Rerodeet 1² 772
S MV RT,
+
T+7
Bounding Note that by equation 8
VF {E&}
2RVCIn(K//)
8 8
Furthermore, by Assumption QG 2nd Moment and the definition of E,
2 2/CCRT
/ 2 [E.} S /
8 8
H ar der (T+))
Recalling that B
|[VF(x))] / 121 {Fr.} 2n 2k/CCn(K//)) Rr, (aCln(K/)VV/Be (s + 7) deff (7)
+ (s+
r
(ett + AnClInK//)Va
2x 2xVCIn(K/S)
uvv RT,
+78+7)
Bounding C
By equation
VF X,
31 {Ea}
8/20 In(/6))
I Hy R
1
(s 7))
Bounding D
Since 3d < #² Rrs T+7
it follows tat
V V ||| 2dtt 1 {E.}
2x 2NVDIn(K(6)
AaCRr,dd
Bdd+ 78+
2
"VRT, +7)
2n (1/6)HH R1,5 /RIS
+ 8akd In (kKK))///)/ /Rr,5
(s + 7T
u(s
(k/o)n(k/))2CMM)
< Pv RT,
(T+ +7) + 12 7)3
Hence, we conclude that
7
|b
S A +
+
HV R Σ B3
j=1
35

---

where BI.... By are defined as follows:
1
T+7
B2 4aCVV1n((((11))
n²(
INVCIn(Mn(T/))
B3 (s ()+ /d( +7)
IxC(I((n(TT)/)))
B u(s + +))²
Bs 8x² (n(u(()66))
(s+
Bg 2xv 2RVCIn(M((T//))
(T 77)
B7 Sand (nb((T))(())))
73
C33 Proof of Lemma 9
As before, for [1 T] define V
FF-1] Σ.. Following the same steps as in that of the we use Lemma and the fact that Cov/g, Fi-1] E, to obtain:
proof of Lemma 7
[V((x)]| || {E.}
[VF (
Tr(,)) {Es}
E - [1
1
1
< 1 (EE) (3 + +D)) + |FF(x))
{Ea}
1 [E,)
V VV
(3+ aD?))
1
8 + 4aCRT.
VV 41 (E.)
[V
(I deff {Ea)
4aCRT,
B
(s 72
r2
r2
78+
(17)
where the second inequality follows from Assumption QG 2nd Moment and the second inequality follows by definition of E. Furthermore, since clipp is convex projection, the following holds:
Tr(E.)) S Tr(E,) (E,)
< doff (B aD?) 1 [{E}}
4odC Rr.s
I Bdet 7}+
(18)
Now, for E [t], define h, as follows:
h (V., d,) (8 7)2
(t + 22d-2
VCRA
Note that E,h, [--1] Furthermore, since | S 2T and ||d S +
VCRr
(s + 7)2A-1
1hg1 < 2r
8 -1
(1 + 222--
(8 2A-2
< 4r / CRT,
1+7
AuRT,vVC
(19)
In(K/8)
36

---

For s E [t), define o² = E[ It follows that,
(
o, (t (++7) V. V.V,
(s + 7)41-2
(1 + ) |v,1l
4A-4
s SACRT
|S10||2
(+ッ)
(8+7)
41-4
40CR1
(E,)
[F(()))
den {Es)
4aC
4CCRr
(
(s (s+*)) 7)²
T
(s + 7)?
where the last inequality follows from equation ( and the fact that derr = Tr(E)/11112. We now use the above inequality to control E o3 In (/5) as follows:
S 4A-4
Σ In & 4CR1, (n(K//))
t t+?
(8 7) A
+ 4CRr, (n(K/))
(t + 4414 51,5
$ ++7
4A-4
VF 1|1 {E.}
+ +4CRT
f t+t
r
8 $+?
4A-4
(xxx))11 ||1 {E,} Bdett
+ &
t t+t
1
(s + 4 4/ Vx) || [E.} adCRT,
+ 4CRT, In (K/))
(20)
74
r
We now control each of the five terms in the above inequality follows
4A-4
8 +
4CRr.8 (n/8/))
B S ACRr, (n(K/)))())
t t+ッ
1²² 12Rr,
S 4CtRT,
(T /
442 44/CRT,
To control the second term,
(s + 2 (l + 7) AaCRT, S 16CR,
aC aCCInn (CIn(K/6)
4CRT,5 (n(,ssl(K/)))
(2(1+7)
< 16CR2
where the second inequality follows by setting A 3/2 and the last inequality follows by setting 2 aC k//)/)) Before controlling the remaining terms, we recall from (8) in the proof of Lemma
that
[VF(xx)]l (Ea) < xlln(K/8JVC
$ 8
2xl (K(/8)VCC
847
where r Pv Rr. In(K/8)
follows that
[VF(x.) ( [E.)
16x 16x In
12
(s+
16 ln(3/))2
n² RT 2RRTS
(8+7)4
37

---

Thus, we can control the third term in equation 20 as follows
4A-4
IV
|| 11 (E,)
(s + 7) 2
4CRr, (n())))(//)))))))))))))))))))(
s 64I2ORT, R (n(k))
t+?
r
(t + 7) 4.1
In(/6))))
s 64p
(1+7)3
S 64p
where the second inequality follows by setting A 2 2 and the last inequality follows by setting
Y C// In( (n(*
To control the fourth term in 20 we note that by equation 8 and the definition RI,5
1 de 31 {Es)
4p² RT,5
r
+ 77+)
follows that
s +
44-4
VF(x,)
|12 Bdeff
(s + 7)
ACRT, (/(5/))
$ 16p2CR
t t+>
1
T+Y
(t + 7
C²CIn(K/))
< 16
(T (T+
S 16p2CR2
where the second inequality follows by setting A 2 3/2 and the last inequality follows by setting y 2 (C/)(()))))
To control the fifth term in equation 20
we proceed as follows:
(s 7) ///VF((,))lP) 1| (E,) adCRy,
4CRr, (n(/6)
(++ 7)4444444
r
adk² C2 In 3/)33
(s (s 7)
$ CR
112
(t 77+
C2
<64,2C
7)
s 6442CC
where the second inequality follows by setting A 2 2 and the last inequality follows by setting
1/3 0//3 In(K/s) Substituting the above bounds into equation 20 we note that
7
43
Σ of ln(K/)) S 2644
Thus, by Freedman's 's inequality (Lemma we conclude that the following holds with probability at least 1 6/2 uniformly for every / [T]:
(8+7)24- (++7)21-2 (V,, d,)
h 2
of (n/6)) + SpRT,s & 34RraVC (21)
A-1
To prove the second inequality of this lemma, we define = V,
for E [t]. Note that E[z,|A FF 0 and ||z,|| || < | < 2T. Define the PSD matrices G, = E[z,z] [ 1F-11] =
2A-2 S Recalling the bounds obtained on 1 and Tr($..) in equations (17) and (18). we
38

---

infer the following:
2A-2
8 1 Y
Tr(G.) -
Tr(E,) {
[+7/
$ (+
2A-2
(s 1s+ 7)4
Bdell +
(t + 7)2A-22 Aaden
t+,
(
21-2
|
|Eo|1z
t+,)
8 (
21-2
(s + +))+ 7)22-4
8 (8+ 2A-2
[VF(x)) 11 {F,}
B+ (++ 2)2A-2 4aCRr, +
t+y)
(++
8 ++7
2A-2
(F(x,)) 1 {F,) 3deff
(s 78+ /1F-1///F((x)])))
{ (F:s)
4cxdett C Rr.
+
1 1+7)
(L 72)))2
Substituting equation
into the bound for |G we obtain the following
2A-2
+ 7221-
Tr. S 9 =
BdaM
Aade
11+7
(1+
( (s+9
2A-2
(s 72+
(s 1s+77) 721-6
|. Pp
B
AaCRT,
16k 16 pRT
t+9
(++7)21-2
(++
(s + 722A-
(s 7)
<
4,3d (1 + 71+7)2 2)222
16odee RT
(22)
(1. + 722A-2222
By Cauchy Schwarz inequality,
p 5
+
1A-1
8² +5
(s + 7
(I (1+7)AA- 16a C n + 28+
(1 7) 256x* In(K/))))
1
1+7
(8 + 2A-8
(s (
5
16 R k 4 c (n()//2)) +5 (t 2)) 256a de R2 sh CC In(K//)))
(t + 44-
(23)
Since T (d)) K = In(In())), our choice of I' and the definition of RT,s ensures that the conditions of Corollary are satisfied. Hence, by Corollary 5 we conclude that the following holds with probability 1 8/2 uniformly for all E (T]
UP(
Cmt
Σ |2.11 < m(K//) + CM
Σ
Q.
p2
4
Simplyfing the above using equations
22
23
and the definition of I, we obtain the following:
| 12 < 400pp22
RT, + +CM
(P
3
+
2A-2
3dem + CM
(P
(s 2)
-adeet 4ade##RT.
1+7)
(I + 7(-2)a-2
5C
UP(()
+
4A-4
(2/8)
50M
UP(1)
(s + 7)
16a²Ca 2 (k/22
4
t t+
1.2 R2,5
4 ==1
(t 2++))
122
5CM
UP(()
(s (s 1--12
256m 8 & (n(K/s)0 RI.5 2Rr..
4
(++7)
5C
UP(()
(s 7)4
32
16x In(K/5)6
4
(1+7)2A-1
12RT,
5C
UP(()
7447)4
256 44 a da In K/8) 8
(24)
4
(t (4+
2
39

---

We now simplify each term in the above inequality by using the fact that UP(t) - min 26}. To this end, the second term is simplified as follows by using A 2 1
(P
4A-4
Σ
+ (+7)
Bder S UP(t)Sder S nº RT.
We now control the third term by noting that for 8 - 21, 8 + + 5 2t + ? S 2(t + 7):
(s + 72
22A-2 ad
1
4ade Ry S 2 R
(t+ 2)
R²
7)?
adl
S 22 RT,
p²(++ + 7)²
$ 2 122 RI,5
where the last inquality follows by setting 7 2
Ann
We now control the fourth term as follows:
UP
UP(t) a(T +7)²
S 1² RT,5
S RT.s
12
We now control the fifth term as follows:
16a² Rr In(K8)
UP({)
(s 7847)
21 0022a
n22
(t (++7)4A-4
11t
(t 7)+
12(2In(k/0)2211-
S RT,
7))
$ 24 12
221.666 RI.6
where the last inequality usesy > lnC'a((K/)
We now simplify the sixth term as follows:
UP(()
(s + 72
2: (t (1+7)aa-I 256 RT, 8 C In(K/888t s 4² Rr,st 4 (n(K)))
(t 7)8
$ 1 RT,8 24A-3, 3 ln/K/
+ 7)
< 241115 112 Rr.
where the last inequality follows by setting 7 2 4k 4/3 (K(().
We control the seventh term as follows:
UP(()
(s 24-8
2 ln(K/8
(s + 7)+7)
16 16
& RR,
(t (++4)
Rr,
(T
4A-4
1 RT,6 22
7++
$ 24A-11 11 R
where 7 2 4kv (I((//))/>
We use a similar argument to simplify the final term as follows:
(P)
t(s + 7)
28 Rr, 4 In(K/))
24A a2 (n (K(66))
S n² RT
(l + (4-)
112
(1(17)))
< 24 RT.5
40

---

where y 1n 2/5 d (n(76))
We now set A 2 3 and y as follows:
odet
(l(K//8) 1²²
x x a K In ln(/))
2 4C m
In(*/8))
112
n
Under these parameter settings, substitute the obtained bounds into equation that the following holds with probability at least 1 - 6/2 uniformly for every t E
13
conclude
2A-2
Σ
+ (+,)
|i
Σ
1 S CMMRRT, (21A-322 +5 +5. 24--11 +5.224-11
21A-16 + 5 22A-13
The proof is completed via union bound.
D Analysis for Smooth Convex Functions
Let derr Tx(2))
2 Following a convention similar to that of Section
B
let K m Cm, In(T))
For t 2 1, define the filtration F, = (x1, g. 1 S 8 S t) and Fo = o(x)). Furthermore, (gt) b, Ve where b, F (gt) ). As beforem, we note that [E = and | < 2r. Hence Vi an FF adapted almost surely bounded martingale difference sequence. Now, let D. ||x, x") where x* is the minimizer of F considered in the statement of Theorem Using the smoothness and convexity properties of F, we first prove the following intermediate average iterate guarantee:
let V (x())
E(clip-(g:) F.-1] (g:)) and V,
(g.)
Lemma 10 (Intermediate Average Iterate Guarantee). The following holds for nj S 1/2L.
F(Xr) Fxx") <
D
1
Σ
T
b.,
-x') + T
Σ
T
Ve.
xx) +
21 T
T
bell
27
T
||v
2nI
T 1=1
T
1=1
Define the events E, and the random vectors d,, b, and v, as follows for E [T]:
E, =D; S 2D1}
d, = (x, -x')1 {E,}
b, b,1 {E,}
V. = v,1 {Et}
We use the following lemma to control the bias Lemma 11 (Bias Control). For every E [T]. ||byl| s B where B is defined as follows:
2en 2LD v | SL
2 2| 2d
T
We use the following lemma to control the varince Lemma (Variance Control). Let 2 0 be defined as follows:
V | 16L
4L AL2DD1|E))2d
1
1
Then the following holds with probability at least
5 uniformly for every I. E (T)
(V,, de) & <AD <4D. &DD, In(K/8)
| < 2M
where CM is a numerical constant and 92 is defined as follows
21
1n(2/5)2
22T
g² -
+
T
41

---

Let E' denote the following event
E
V., d.) S 4Di +TD [lll
sm1
Σ | < CTsgTT
[E
We define the constant as follows:
A = |اح| V doft + LDI / 1 VIEa (vT((z) LD,)
We now set the clipping level I' bound on B:
V
AT In(Kyaj
For this choice of T, we obtain the following
Σ 2V delf
2LD
D
2d
B
r
1
1
Aln(K/6)
2LD1 In (K))
s 2
[1 + -L²D?) = B
(25)
AT
Similarly, we bound the value of as follows:
16L ILLD/II(K//)
4 2 (K/5) V
s ||
(26)
AT
AT
Equipped with the above inequality, then bound the value of g as:
21 ln(K/))
VVT
9 S 2def +
VT
21
V
Vin((K/8)
2eet + 2/ Aln(K/6)
2
|| In( (3/6)
In
2L2
In 1/2
S v 22ef + 2/ Aln(K/8)
+
2VA
A72T
A
D In ///8//2
2L
12dde In K//)%/2 of
< E22de + 3 (ln(k)))))
(27)
A
A
We prove the following lemma to control the growth of the iterates D.-
Lemma 13 (Iterate Bound). Lef 7) emin (1/21, Di/B'T, Pi/d/TT where c V80xx+300 conditioned on the event E, D, < 2D, Vt E [T].
Then,
Equipped with the above lemmas, we now present a proof of the following theorem, which is formal restatement of Theorem 3
I-smoothness and Bdd. 2nd Moment be satisfied. Then, for any 8 E (0, 1/2) and T > In(In(d)), there exists an E (0, such that the average iterate of Algorithm run for T iterations with step-size T) = and clipping level /11l//// LD)))
Theorem (Smooth Convex Objectives). Lei Convexity
= In (1(7)))
satisfies the following with probability at least - 8:
Tr(E) + VIEE|2 (Tr(E)) LD() In((n())/6)
LD T
F(XT)- ((x)))((x*) D
T
LD (I(((T)))))
Tr(E) + L2D3
L'D (n)(T))))))
Tr(E) + L
T
|E|||
T/2
Σ
42

---

CLD D.1 Proof of Theorem 7
We condition on the event E and let 17 2 min 1 D. D1) } where v8C +330
Note that
2L. BT g'vT
this choice of 17 satisfies the requirements of Lemma 10 and Lemma 13 By Lemma holds:
10
the following
D2 2nyT
1
211
T
211
F(RT) F(x*(((x=)))))) S
bb, x*)
Σ
Vv. X - x²)
+
by
2
||v.|
T
T
T
t=1
By Lemma
13
1 [
1
Vt
[T). Hence, the following holds.
S
D2
+
Σ
T
bu de)
1 + Σ (Ve, de) Σ
27
|bbl12
2
+
21
T Σ |vll
2n1T
T
1=1
1=1
1=1
Df
Vln(K/)
8D,Lin(K/5)
8
Σ
+ 2BD 2nB² + +n + +4DIV
2n(T
T
T
D2 nT + BT + 2g + 4D1
Vin(K/8) T
Aln(K/))
+ +8D1
T
Where the second inequality uses Lemma and the definition of the event E and the third inequality uses ab S a² + //11. For the rest of the proof, we shall use C denote an absolute numerical constant whose value can differ at every step. By our choice of the step-size
D2
CLD
CD1g
+DD,
n
T
VT
BT < CD,
CD19'
2nC <
VT
Hence, conditioned on the event E, the following holds:
V' V'In(K/8)
Aln(K/6)
F(XT) - F(x*) < T
+ B'D +CDig'T+ + CDI
+ +CD1 V
T
T
Substituting the values of g', B' and V', we obtain the following:
- F(x') CLD}
Aln(K/8)
CLDDIIn(K/))
Tr(E) + D2
+CDIV
T
T
T
A
CLD)Im(K16)
+r( +
L2D2
(n T/22
Tr(2)) + L2
T
A
A
Substituting the value of A, we conclude that the following inequality holds almost surely conditioned on the event E
Tr(E) + 2 V Tr(E) + LDD) In(Iu(T)/6)
LD T
F(XT) F(x") & DI
T
LD (T(()))))))))))))))
Tr(Z) + L2D?
L'D (n()(T)66)7>>
(r(E) + L2D 1/4
||/|
7
|>
The prooof is completed by observing that IPE) 2 5 by Lemma 12 which implies that the above
inequality also holds with probability at least 1 1
D.2 Proof of Lemma 10
Proof. Since 1c is contractive operator
D2 = ||x x2 < DJ 2n (VF(x); b V,,,, - x*) + + - b, - vell
5 DZ - 2n (VF xx")
2n (b,,xr -x)) + 2m (V., Xt -x))
+ 2n7 2 4,
|2,12
43

---

By the coereivity property,
-2n (VF(x)). X - xx) - (2n(F(x)) - F(x")]
Substituting this into the recurrence for 1 we obtain the following:
D141 I Di - 2x( F(x")] 27y (Ve, x*) + 21y (b:, X x')
(22 1/1n--/1)] V/ | |/ + 4n7" |
DJ (xx[((xx) [(x"]] 21y (vr, X x*) 2nj (b,, X x*) + 4n7 vv, + 4n |
where the last inequality uses the fact that 1/ S 1/21. Rearranging and taking averages both sides
T F(x))
D 2n
T
T
2n
r
2n
T
-
Σ
(1 - x*) +
T (v,,
Σ
+
2
bull
2
+
T
T
T
t=1
Using the above inequality and the convexity of F, we conclude that
T
F(XT) F(x*) = F
Σ
F(x*)
T
tm1
$
Σ
F F(x:) - -F(x')
T 1=1
<
D3
T Σ
1
(b Xx - x²)
T
Vts X
x*)
+
2n T
T
by 2
27
| 1
2T7T
t=1
D.3 Proof of Lemma 11
Note that by definition of E;
|| 1 [E.} < LD,1 (E.) < 2LD1
We recall that b, = [[gg[FF-1] E(clip( Ft 1]. Since Covig: [F-1] 3 Σ by Assumption Bdd
2nd Moment
we obtain the following bound on |b. by an application of Lemma 4
Σ dei
||VF(x))
Σ
[VF((1)]
2 [xx))
|b. S
F
r
1
1
Since 6, = b.I [Er,. it follows that
EEll2/deff
|VF(x,) 1 {
ll
1
(F 31 (E,}
|El|ade (F ||1 {E.)
| <
1
1
Ellayd denr
2LD [
8L D
2
| 2dn
1
D.4 Proof of Lemma 12
For any E [T), we recall that v, = E (g. c Since Eig, = VF(x.)
and Cov Covig,|_e F_ z E, we obtain the following from Lemma 4
VF(x))]
(1)
E v. [ ] ||2 |Cvv [clp. | [| +
r2
1
Tr [E V. [(-1l) Tr (Cov /clipr (g.) < Tr(E)
For E [1 : T define E(V.v7 F,-1] 1] = Σ.. Since 1 {E.} is 1--1-mmaaurrble and v, = v,1 {
it follows that Σ, E V [F-1] 1 {E.). Hence, we conclude the following from the above
44

---

inequality
12 - |E1| + (F
|VF(x,)
(r(E) (Ea)
r
16T D1
412
|| +
=V
r
r
Tr(Σ.) - Tr(
(28)
For E (T), define h2 (V., dg). We note that
1ha S |[va]| -|dd]] S 4DD1
E [F = (El (B[v.[F.-1),dd) =0
E F-11 v
d Ed
S | | S 4D
Hence, by Freedman's inequality (Lemma we conclude that the following holds with probability at least 1 - 8/2:
Σ (ve, di) S 4D4D V + AnD,,n(())) V [2]
We now apply Corollary with P, V. 9 Tr(E)) and r = 2 to conclude that the following holds with probability at least - 8/2 uniformly for every t E [T]
1 < 40MI CMUP(()T((() + CMrUU(L)V2
41
CMTRV2
S 40M1 In(k 1n(3 CM)TT(22)
4
4 InKK))2
V²T
s CMr |18]|der +
CM
T
4
where
2 In(K/))2
V2T
g² = 1
+
T
4
The proof is concluded by union bound
D.5 Proof of Lemma 13
We prove the claim via induction. Clearly, the claim is true for t = 1. Now, suppose the claim holds for every for some E [T]. Since Ie contractive operator
D ||x-1 12 < Dj 2n (Vx) b, V,, - x*) /
b, vell
< D2 - 2n (VF (x), X, - x*) + 2n (b,, X x*) + 21 (vi,
+ 22/2 || + 1r 11, bbbl
By the coercivity property,
22n (VF(x)), xx - x*) 5 F - F(x*)] - - (F(x)))
Substituting this into the recurrence for D D we obtain the following:
D - D.- 21/ F(x*)| + 2n (v,, X, -x") + 2n) (b,, x - x")
+ + - // 1/L)I || 4n7 lb.1?
47y2 12
< D2 + 2ny xv"),, + 27 (b. X+ x*) + 4 | + 4nj |b
-x)
45

---

where we use the fact that I 1/2L. Now, by the Cauchy Schwarz inequality and the fact that ab I a² + 6//4 we obtain the following:
D2
2n (b,, xx))
27 + T/
follows that
Di+1 1
1
Di 1 4n vvel2 2n (vi, x*)
27
Unrolling the above recursion for steps and using the fact that (1 + 1/2r) 2, obtain the following:
1 1 )
D
1+ 2T
D
Tbx
1 1v.11 2n (V., X, - -x"))
2T
s=1
< 2DD
+
101 2 bb 2 + 8n/² || An
By the induction hypothesis, 1 [{ = Vs [t]. Hence,
D2 2DD 10 TT
|b,11 817 1| 4n Σ (V,
< 2D2 + 10000/ 2T + 80 gTT + 16
< VVlln(K/)) + 21 (k(K))) (n(k//))
([Hln(K/))+2TT((++ 2
$ 3D) + 10 B² + 8Cmm g 64n²
3DD + 10 + 8C 2T 128 In (K/6) 1n244" ln//6)²
where the second inequality follows from the Lemma IT and the fact that we have conditioned on E. Note that by definition of g² and the AM-GM inequality
221
g2T > T In(K/)) +
2 max(4r In<K/) ba 2VT
4T2
It follows that
D S 53D + 10 (CM
< 3DD + 10c² DJ + 28C + 3200
< 4DD
where the second inequality uses the definition of v and the fact that B' and g' upper bound B and G respectively by equations (25) and (27) and the last inequality sets e VBCxr+330* Hence, D < 2D, which proves the claim by induction.
E Analysis for Lipschitz Convex Functions
Let deff TT())) [ Since Σ is positive semidefinite, 1 deff S d. Moreover, let clipr(g:)
(F(x,) b, + v, where b, = (g+ - represents the bias due to clipping and B|v. 0. Let D, = | x where x" is the minimizer of F considered in the statement of Theorem 3 Using the smoothness and convexity properties of F, we first prove the following intermediate average iterate guarantee:
Lemma 14 (Intermediate Average Iterate Guarantee). The following holds for any 1j >> 0
D
1
F(xr) - F(x*)
( Xx
-x")
Vr, X
x")
2n/T
T
21 T
T ||b,||
27
T
G22 2 +
+
||ve|1
1=1
46

---

Define the events E, and the random vectors d, as follows for t E [T]:
E = [D 5 2D1}
de (x, - {E
We use the following lemma to control the bias Lemma 15 (Bias Control). For every E [T], ||bel| - B where B is defined as follows:
B del + G |
G
Σ
2denG
T
1
We use the following lemma to control the varince Lemma 16 (Variance Control). Let V 2 0 be defined as follows:
G G
12 2deff
V = | +
1
Then the following holds with probability at least â uniformly for every E [2']
Vo. d.) S 4D Vtiv/vll(</b) 8 ln(K/6)
Σ 1 CMg
where Cas is numerical constant and g² defined as follows
2 In(K/6)2
V
g² = 2
+
T
2
Let E denote the following event
E
Vo. d.) S 4D ( VtE [T]
+
Σ 1 < CM Vt [T]}
8=1
Note that by Lemma
16 P(E) > 8. We define the constant A as follows:
|_||2 v dett G vI (vTr(E) G)
We now set the clipping level [n(K/a) For this choice of I, we now simplify the expression
for B follows:
Aln(K/8) T
G (1E)l2dee + G²) In(*/8)
B
(29)
AT
Similarly, the expression for V can be simplified as follows
V V= G2 G2In(K//)
([E)ladeer + G²)
(30)
AT
Using the above inequality, we derive the following upper bound for g:
21' (T'I((/8))
VVT
g S v E2|2de
+
VT
2r
V
Vinn(K/s)
22
2 2 Aln(K/8)
2
|E|| / (n(K/))
G G²In(K/6)9/
= E + 2 Aln(K/8)
(115 + G2)
2/A
A
G2 1n(K/8)//2
< / + 3 Aln(K/))
(111)adde + =
(31)
A
We also prove the following uniform upper bound on the iterates Xt.
47

---

Lemma 17 (Iterate Bound). Let 1) I Emin(Di/Bs conditioned on the event E, D, S 2D1 Vt [T].
where c= vSCas +331
1
Then,
Equipped with the above lemmas, now prove the following theorem which is a formal restatement of Theorem 4
Theorem (Lipschitz Convex Objectives). Let Assumptions Convexity Connveeio GiLipschitzness and Bdd
2nd Moment be sulisfied. Then, for any å E (0, 1/22 and T 2 In(Indd)), there exists an E (0, G[VT]
such that the average iterate of Algorithm [ run for T iterations with step-size tps = 11 and clipping
Tv [IllaaayTT satisfies the following with probability at least - 5 (0(
level r
DGG
Tr(2) 2
(vr(() + G ln(K/))
F(XT) - ((x)) x VT + Dia + T
T
DKG))(K/o)
Tr(E) + G2
D1G2 T
(Tr(z) + G2 4/4
|E
||i|
E.1 Proof of Lemma 14
Proof.
Since Ile is a contractive operator
Di41 = |x++1 - x11 s D3 2n (0F(x)) + b, + V1 -x") +/)+ + b, vvll
S D.. - 21/ (0F - x*) - 27 (bc, X - xx) - -27 Xe xx)
+ 221 || + 4n/ |v, 41/ bel1?
< DJ 2n - F(x*) 2n (b,, x*) -
(v,, -
xx) + 4n 4n7 lv.
where the second inequality follows from the definition of the subgradient and the G lipschitzness of F. Rearranging and taking averages on both sides
T
D
T
1
T
F(x:) F(x*) <
b
x2 - xx)
Ve, Xx - x*)
2nTT
T
T
1=1
T
T
27
211
+ G/
+
||:
12
+
12
T
T
t=l
Using the above inequality and the convexity of F, we conclude that
F F(x*) F
1 Σ Xt
F((x')
T
1
$
F(x:)=
-F(x")
T
D
T
1 T
Σ
(br, Xt -xx)
(ve, Xt xx)
2n/
T
T
t=1
t=1
20 T
T
2n
+ 2 +
Σ
||b:|1
Σ
||v.|1
T
t=1
t=1
48

---

E.2
Proof of Lemma 15
We recall that b, Elg [t-1] (g.) Since Cov(ga|[F-11) 3 Σ by Assumption
Bdd. 2nd Moment, we obtain the following bound on ||ba|| by an application of Lemma
| deef
[ )ll
[xF l1
[2 (X,)))
||b:|| -
r
1
Σ deff
GVEL2
G3
Σ 22eetG
72
1
E.3 Proof of Lemma 16
For any s E [T). we recall that v, = E (clip (lipp(g.)) Since Eig, F = OF (xx)
and Cov [g. [Fs1]] x Σ, we obtain the following from Lemma 4
|[F((x))*
11
[0F Tr())
EE v.v F 1l2 [|Cov (clipr
|1||2+
1
1
G
T²
- ||ل|| +
1 +
1
Tr (E V.V. F F(-1)) = Tr (Cov (c. (g.)) [F.l) < Tr(E)
For s E [T]. define hg- = (v.. de). We note that
|/21 S l|v=ll ||d,|| S 4 [ha F,-1l = (E[v, F.111.... d.) =0
E
E h F-11]
d. El.v'v
d. || < 4D
Hence, by Freedman's inequality (Lemma 3 we conclude that the following holds with probability least 1 6/2:
Σ Vi, de) S 4D1 VttVVilln///
lm(K6) Vt [T]
We now apply Corollary 6 with V. g. Tr(E) and T 2 to conclude that the following holds with probability at least 6/2 uniformly for every [T]
1 < 40M1 CMUP(()T((E)) CMrtUP(EVV2
4T
T222
s 1 CNTTT(E)
2
2 ln2)2((/)
V²T
s CNT
[El12det +
= T
T
2
where
4T (n(K)/)2
V2T
-² -
T
41
The proof is concluded by union bound
E.4 Proof of Lemma 17
We prove the claim via induction. Clearly, the claim is true for / 1. Now, suppose the claim holds for every S L for some E [T]. Since IT is a contractive operator
D2 = |x++1 - x1 < D' 2n (xF(x;;) + b, + Vt, x") + [ + b, + vell
< D2- - 21 (0F (x;), X, x*) - 2n (b,, Xx - xx) 2n (Ve. - xxxxx=x")
21F ||2 4r |v, 4172 b+
< D. - 2x)(F(x)) F(x")] 2n7 (b,, X2 x") 2n (v,, - xx) + 2n + 1,,1 4n2llv.
49

---

where the second inequality follows from the definition of the subgradient and the G lipschitzness of F. Now, by the Cauchy Schwarz inequality and the fact that ab S a² + /a we obtain the following:
D 2T
22 (br, X - x*)
+ 1 TT.1?
It follows that
1 2T
Dit1 (1
Di T/ 2n 4n² 1v22 2nj (V:: Xt -x")
Unrolling the above recursion for steps and using the fact that (1 + 1/2T)" S 2, we obtain the following:
D2 $
1
1
T
D
1
|
1
(5,)
+ 4v)"|lv,, 222 21
27 (V., X, - xx))
2T
2T
t
s 2DD + 412
Σ
10n
2 TT,,,11? 81) 11,1 (vs.
By the induction hypothesis, 1 [[E,] = A4 E [t]. Hence,
Di4 < 2DD + 41 + 10 < 2209 +
|b,l 12 + 81)" ||v.11 4n Σ (v d.)
+ 80M1 - 11n-11
VVin(KK// 21 in
< 3D9 +
+ M0M' gTT - 64n² (VLln(K/)++2T1)
< 3DD +
+ 80 2T
+ In24r=I((//a)
where the second inequality follows from the Lemma 15 and the fact that we have conditioned on E. Note that by definition of g² and the AM-GM inequality
2212
82T 2 2 1n/3 +
2 max(412 2VK 2VT 2V(kk//)))
2
follows that
D4g1 s 3D9 + C + + + 20
<3D + 4 DJ + 10c2 D2 + 2800 + +20)D
< <DD
where the second inequality uses the definition of r and the fact that o' upper bounds and the last inequality
Hence, D41 2D, which proves the claim by induction.
V8CM++33
F Improved Martingale Concentration via PAC Bayes Theory
We have the following re-statement of Theorem for the sake of readability.
Idd valued martingale such that Mo 0 almost surely, the martingale difference sequence V; := M₁- M,-1 is such that | S I and E[v.v] [ Σ, almost surely for every t t= 1,..., T for some I > 0. Assume that there are deterministic sequences Pt,...,P4 and Q1...., such that Tr( S qe and ||E+|] S Pt almost surely.
Theorem 9. Suppose Mofort t- . is
Let q = E Qi and p: Er Pt. Then, for any 5 E (0,
(P(sup || Mill 2 (T, (8VV) <
SST
Where (TT -C [VQ++
PVT
log ) and K log Olog(( L/T + 1) log(d 1)))
V
50

---

Define the event Ag) = {ll & gVT) and (x(g) = 1. Consider the quantity Ne :=
||M, E Vv 112.
Theorem 10. Let 8 E (0, 2) and g g g(T, ) be defined in Theorem 9 Under the conditions of Theorem the following inequality holds for some large enough universal constant
(sup N1J (Cg)Tlog(() + CugTa/2 IST
(nBB())))))))))))))) s
IP
The next corollary is simple consequence of the Theorems 9 and 10
Corollary 6. Let ō E (0. 2)) and g = g(T, }) be as specified Theorem
Under the conditions of
Theorem 9 the following inequality holds with probability at-least 6:
T
lvel S Cg
F1 Proof of Theorem
The aim of this section is to prove the sharp concentration result given in Theorem 9 We now consider the concentration of norms of the martingale ||Mell Define the event Ar := [ s gvT) and B, = As. Let H be any stopping time for the martingale Mi. We have the following inequality which follows from BAC-Bayes theory (see Equation 5.2.1, Page 159 in (7)).
Theorem 11. Suppose æ be any measure over R& and let M₁ (IR)) denote the space of all probability measures over Rd. Letry 0 be arbitrary. Then conditioned on Br, with probability at-least 1 5. the following inequality holds:
(B.)) (1(Brr)
sup Ea-py (Mmin(H.T)::) 0) KL (pllT) S log ENNEE (Rd)
(32)
We will now bound the exponential moment: Ens exp(7 (M,, 8)) whenever -O.O.I..
Theorem 12. Let h(t) == Ei=1 log (1 2 exp(> Txpp2 Then,
Enwa MM
a supermartingale with respect the filtration Ft
Proof. Let E, E[v.v! FF-1 and v, EEll- First, consider Ee-- exp(1 (M, 0)). By the properties the Gaussians, we must have almost surely:
Ea exp(y (M,, = exp( M.ll (BB,)
(33)
Using the fact that || |/, + + || 11?, we have:
E
exp
2 MM 1 ] (B.) F.-1 = [e[epp( 211 +
22llvell 2
+ 72 (vz, M M.-1))
= E expp
21 vill 7² Ma.))
Fi-1 Fr-1
exp( exp( -ill ) (B,-1)
(34)
51

---

We will now bound the quantity:
exp( > lv.11
2 + 72 (ve, (A) F(-1
Using the convex-
ity of x exp(x). conclude:
7
voll=
E
exp
(ve, ()-1)) Fi-1
s 2
exp(> ll (1) + exp(27² Mo-1)) Fc-1
< [1 + Tr( exp(>2r=)]
2 exp(2> (vr, M+-1)) Fz-1
(35)
In the second step, we have used the fact that surely using the power series expansion of the exp() function. Using the power series expansion of exp(x), we have:
- <v+> exp())2xppp)2") almost
E exp(227 (Ve, (v,))
Fi-1
E exp(2?? (Ve, (r-MM-1))) Fi-1
2k
-1+222 M
+
E ([(((ve, My-1)) Fr
h!!
A22
2x
11
B[((v), M- 2 2|
M k- Fo-1l
h!
2b22
< 114
(M-11
[,M,,1))) p M M k-2
k!!
R22
2k22k
< 14
p.
2-2
|M <
<1+
2z exp(2>>p 1exx22 ([T)
(36)
k!
Here, 2/2 = E2 Eellop In the second step we have used the fact that
= and the fact that
(v,, M,-1) S M, || almost surely. Plugging Equation (36) into Equation (35). we conclude:
2
voll?
E
exp(
+ 22 (ve. () Fi-1]
2
2
$ 1
Tr Tr(E,) exp(? x - (x
(37)
Using Equation
37 and that under the event B,-1 must have | S gvT, we conclude:
E exp( Mell
1 [BB) Fi-1
72
2 ti exp(>2122 + 7 >' exp(2xx (19V7) exp 2"1M (B.,
< 1 +
= exp(h((1) h(L 1)) exp (5²1lMa-11) 1BB-1)
(38)
2
Therefore, by induction, we conclude the statement of the theorem.
Theorem 13. For any stopping time H,
Ex exply (Mmin(H.T) s exp(h(T))
(39)
52

---

Where = ((T)=E==)) log (1+ z exp()212) + + "
Proof. From Theorem a2d the optional stopping theorem, we conclude that the following quantity a super-martingale
M Eenr exp(7 (Mmin(H,a) 0) (Bni((
Therefore, have:
Eawa exp(7 (M.innHH,)) 0) h(T))) S M S LEMO
Combining Theorem 13 and Equation 32
conclude that the following inequality holds with probability at-least when conditioned on By:
sup Eg (Mmin(T.n) 0) KL (pll=) & ((T) + log( 3P(Br)
(R
In the RHS of the inequality above, we replace the supremum over MM with the supremum over
the set of all probability distributions {N(of, I) such that 88--1,a 2 0)- We note that
KL (IlIT) = a² to conclude that the following inequality holds with probability at-least when conditioned on By:
a² ST() + log( (
sup ya M H,T)
a>0
2
That is:
2h(T) + log( 3P(Br)
72
Now, note that by definition,
M(T) =
T
72 2 at exp()2r2) + TT exp((2
log
1
T
T 1=1
$ 72 2
( + 7 T ex
(40)
Therefore, whenever: 7 < min on the event By:
|. (+ we note with probability at-least 1 d conditioned
M (H,)) $ / Tq TT 3 log (P(BB))
We therefore state the following theorem:
Theorem 14. Suppose 5, 61 E (0, 1). Mr satisfies (g, T, uniform concentration for some å < Then M, also satisfies (g',T, + 61) concentration, where
log( 11
(g')² - 2 2
2T
for any 7 S min |
53

---

I for some fixed constant co > 0, then we have for some constant Additionally, suppose co क. (C)r ( - Citor (co)lØ +
PVT
log (
Proof. Since 8 < 1. conclude that P(BT)
Given that M, satisfies (g.T, uniform concentration. We conclude from the discussion above that for some universal constant C' and any
2-
7 min 2VTgvT we have:
sup P( C 12 + # log (+))(BT) s 61
H
Picking H to be the stopping time given by infft 2 | 2 C(Tq Tg
log 7 61 ))1 where C' is the constant in the equation above, conclude:
P(sup
|M
C + 22 + # log 2. ()) S 61
K
Only in this proof, call the event 9 := {supist |M C[Tq + 22 + # log 81 ) We
have:
P(G) = IP Br) PP G ()) < P(G)Br) + P(B))) - 61 +
Whenever g 2 co T we can pick
(r() and conclude the result.
VTgVT
We now state consider Lemma 11 from 12) Lemma 18. Suppose a, 3 S 0 with + 0. Consider the function
R+
+ IR given by
2
[ 43
f(u) a + T. Then, f has the unique fixed point: u²
Fort denoting
f()) to be the t fold composition of f with itselff we have for any u E Rt:
(0() - -51 (2( 21-1
2
We are now ready prove the main theorem 9
Proof of Theorem g It is sufficient to show that there exists K = log (log log())) such that M, obeys (g, T, 8) uniform concentration where = C' max
/T
r
+
EVT
+
VT
I log (
Let K be any fixed integer. By Theorem 6 we conclude that the martingale M, is (go( & ),TT. $ uniformly concentrated. Fix some > 0 and (Cto be as in Theorem [4
Define the sequence 9: == Ctter + Citer (ceeggo))): G where PVT r
+ v log( K
If 90 co f then the statement of the theorem follows. Suppose there exists K₁ S K 1 such that 9K, < cor and suppose that it is the first such integer. If K1 0. the statement of the theorem follows from (go( )), T, & uniform concentration of M,. Suppose < K1 < K - 1. Then, min(go.... ... -1, 2 Co -.. Then, by Theorem 14 the fact that VI +ツ / + / and induction, we conclude that M, obeys (gs, T, (+11) for every i K₁. Thus we conclude the statement of the theorem.
/T
K
54

---

I Suppose such a K₁ does not exist. Then, miin(gu......9 co VT. Then, by Theorem 14 the
fact that v + y v vy and induction, conclude that M, obeys (gi, T, (1+1)6 i i 1. Therefore, obeys (gK, 7.8) uniform concentration.
K) for every
Consider the function f Lemma 18 with a = (Citer(coğ and B = /Cteer(c)) and let the corresponding fixed point be denoted by g" It is easy to show that the fixed point g" x / G. After iterations, we must have:
9K S g" + (Citer 2x Ilo gr
Sg
+ +G' 1900 =
log d)). and the bound on r, we conclude the We can show that picking K log (log(((1 + v result.
T
F.2 Proof of Theorem
Proof of Theorem T0 Recall that Eg E[vev] Fi-1), it
| and N₂ ||
Σ vell? Note that 14 S Pt and Tr(E.) Pt almost surely.
Let E R. Define (t( == Σ log
+ 4 (xxp((e)/))//T with empty sum denoting
0. We first show that No = exp(> hx (t) is super martingale with respect to the
filtration F, for 0 S f < T. For 7 2 t 1, we have:
E [1) Bacp:/AAJJAAAaaaaaann0//./l..111
2h #
k!
k=
21 (
1 2k
= (8
kd
k=2
I ||
S (B),
M 2
--2
k!
S <xp(>>N (10-47/wv011eep22//1111)))7
= =exp(7N.-1 1x h2 (1
(41)
This shows that _2,xP a super- super-martingale. Using the fact that N = 1 almost surely, the optional stopping theorem and the Chernoff bound, conclude that for any stopping time H, we have for any a, 7 >
P([NMinnTT,H)) > a} n Br)
< (eixpp?Xmmi(T..am - (B))(BB)]
< (eeppyymmmmnTaaa - (B)in
E N min(T,H)) (exp(px(T)) 1exphrr))
70)
< (Tp yya)
(42)
Taking 7 2TgT allows to conclude:
P({Nuin(T.A) ICgyTlog(()) + 3/9
(BBT)
Let a ICgvT log(?) + 3/3 and take H be the stopping time min(inf;(( > 00: N, > a).T) where infimum of empty set is taken to be infinity. We note that {sup N₁ a) (Nminn(T,H) > a). We thus conclude:
55

---

P({sup N. [Cg)Tlog(3)) + CugTu (BBr) - 2
KT
Taking y negative gives the analogous proof for N; aa.
F.3 Proof Corollary 5
Proof. Consider the set S = (UP(t) : sT. The, |S| - log2(T) (T) + 1. By Corollary 6 we
have for any to E S, the following is true with probability 1 (T)
5
|/ (1o 3(1 + log)(T))
Therefore, by union bound of the above event over every to E S, we have with probability 1 6:
8
sup E
1/ 11
tog 2
3(1 loga (T)) 50
Now, note that E._ Therefore, we conclude that with probability at-least 1 - 6, the following holds for all E [?] simultaneously:
||v
S E |v,1² almost surely for every E [T] since S UP(t).
UP(()
V S (UP(t), ((1+) UP(t)
Using the definition of g()) from Theorem
9 we conclude the result.
G Applications Streaming Heavy Tailed Statistical Estimation
G.1
Streaming Heavy Tailed Mean Estimation Proof of Corollary !
Proof. Recall that for this problem, E C. Eg-
m E C and Cov[g] = E. Consider the
following quadratic loss function f C - IR:
[(x; {) 1 || ElI
g~P P
The associated population risk function given by
1 5 BE-P [||x F(x) = 2
<lI F F(x)
ア x
[|
m|| Tr((ove=.P(E))
Note that F is L-smooth and p-strongly convex with μ 1. Thus, 1. Furthermore, m the unique minimizer F. Hence, solving the streaming heavy tailed mean estimation problem equivalent to solving the (heOSpperoleen for F. To this end, we consider the following stochastic gradient oracle:
(x:: = x
easy that [xx; Fx(),, i.e., the stochastic gradient estimate unbiased. The associated stochastic gradient noise nxx; {) is given by
n(x; v Fx) (xy y
We now note that
[x) = (xn(x: ())(x;
[) E((y m)(y m) 7 = Tr(Covg~P(E)) Σ
Hence, we note that the Bdd. 2nd Moment assumption is satisfied. Hence, the result follows by an application of Theorem
56

---

G.2
Streaming Heavy Tailed Linear Regression Proof of Corollary 2
We use & E C to denote the parameter of F. Recall from Section 5.2 that E = Re x R, and given target parameter 8 P defines the following linear model:
X Q, E
0, E[xx " O;
(x, 0-) + B[dx] = 0, E|c [x] S o²
In addition, we make the following bounded 4th moment asumption on the covariates x B[(x, v) Ca 1)
V
for some numerical constant C₁ 2 1. Recall that the sample loss function is given by:
1
f(0:x. ((0,x) x) y)²
2 (10 ,-, x) c)²
Using the fact that E(c|x] = 0, [x[] 0 and TE| [F(xx" = =
F(O) = 2 (0 (T) TTxxTI(( [(0 0*) + 1B(=
10 " 00 - 8r) + B[e²]
We note that IB(e]] S o² as per our assumption hence F is well defined. Furthermore.
VF(0) = 200 0*) F() =
Thus, the population risk F is L-smooth and j--ttrongyy convex with L = |E|l and Xmiu (E), |Ejla
ie., K Amin 25 Furthermore, the unique minimizer of is 0*. Hence, x = Amin
|| l
the lincar
regression task of estimating 0* is equivalent to solving SCO for the above objective.
The associated stochastic gradient oracle g(0; x,y) y) any E C is given by:
y00:x,y) f((:x,,)) = x( yy) (10 0" x)) -)
xxx (0 0") xe
We first show that g(f; x. y)) is indeed unbiased estimate of V
[[g x, y = Exxx" [ 8*) - E[xE[e|x]] = I(0- --) VF(()
The associated stochastic gradient noise n x0; (0) given by
n(0:x.)) = g x, (0) FF(x)
= (xx" 2 (0 0*) Xe
E()) y))(t xx)n)x)))))) x))).. For convenience, we use M xx Σ and dg 0 0" and note
that M is symmetric. It follows that:
Σ(0) E (Mdg xc) (Mdg xc)
E Md M + E xxx -E [x]1
E
E[xd M E[e[]]] E|Md,x -[{]x
= E Md M
+ 2
where the fact that E(c[x] 0, E < 2² and E[xx?] E.
We shall now upper bound |E[ To do so, we define A = E Md M| and note that A
is a PSD matrix since for any Rd -T A(0v E MM ) 0. Without loss of generality,
57

---

we assume 8 * 0" and observe that
sup ||v|==
E[v"A(0)))
sup ||v||=
Bl(do,
Mv)
de Mr) ?
dell
EK ||v==1 dol
sup
S | ||
(w Mv)
sup
|| I|v ||V|=I|||]|=]
|dol 2
B[[( [w (xx" Σ) v)
sup
||=1 ||||=||[|||=
< |doll
sup
E ((w, x) (v, x) w² x
||v |=1||||/||=
||
I |dol
sup
2 (w" Ev)² +2 (w.x)) (v) x))=
l|v |w/--//|w|l==
VIB(Ww x) 4/ / [v(
2/
| ||||=
sup
s 2|/d,/1
| + C₁
B[(w, x Bi(v, x)
sup
||||=1 w||=1
2/ 2
|Σ + C2 sup
w''Ew
sup v² Ev |v||=1
||w||=1
< dell 21 +1)
where we use the fourth moment assumption on the covariates in the eighth step. Note that the above bound also holds when f Hr since in that case (0) 0 and de = 0. It follows that
|- < ||A(0)]| + 0² ال1ا
2 | 1- + -B|E|||
We shall now derive an upper bound for Tr(E(()) as follows:
Tr(E(()) = E| [n(: x. 2
= E [[]Md, - xel
E| - (MMdd x) [[]]]+[[[|]]+]) |x]]
< E (
We now control [E[| Md [2). Note that E Md || 0 0f = 0* so we shall now consider the case when 0 * 8" To this end, let c....., Ca be orthonormal basis of Rd such that e;
de
||dall
For the remainder of the proof, we use Eij to denote Σi₁- = e De where i,j E [d]. which implies that Tr(E)= Σde En. We also note that for any two symmetric matrices B, C, (B C) - 2B² 2
58

---

Hence,
E| Md
[|2]
||ds| || [|]]
||do| E le (> - xx F e
$ 2/|d0
[of (x² + (xxx cil
e -/ e1 + E (0). x)" x
2|
|159| + EE x) Σ
fei x2))
S 22||d/l 1?
|152]3 + E x01
Bi(e x) (c,, xx
22 1
|122| + [e)
Σ
V
R
(el. [0) E
1=2
|122| 2/
C.IE (el, x
C4 Σ
E
[(er x}(] E [(e))))
d |1>1| + C. 1=1
2/
Σ
EE (el x)
[ee,, x)²]
d Σ
[12] + +Caeee Ee;)
(o Eci)
==1
s 2/ (12))2
Eee)
Ex
$ 2/ (|EI[Tr(Z) Cr|
s 2(C, + 1)||>>| 2 Tr (2)) |del2
Clearly, the above bound holds even when A 0" Hence, we infer that
Tr(E(0)) - 2(C, |)] 11 From these bounds, we can conclude the following
||((0]| < 2(C4 + 1))|=118100 - 0-1| + -2
Tr(
Tr(E(()) <
[2(C+ 1) | 0 + 0² |
|Σ| 2
Thus, the stochastic gradient oracle satisfies Assumption QG 2nd Moment with 2(C4
1)
B = = and der = Tr(l)///s) Hence, the result follows by an application of Theorem
G.3 Heavy Tailed Streaming Logistic Regression Proof of Corollary 3
Recall from Section
5.4 that ==t = Rd {0, 1) and P denotes the following linear-logistic model:
X
E x = 0, E xxxx = Σ; y Bernoulli(@( ())))))
where = (1+
The covariates x are heavy tailed, with only bounded second moments.
The sample-level loss is given by the negative log likelihood of x as follows:
f(0; x, y) = In + exp (x, 0))) - (x, 0)
The associated population loss and stochastic gradient oracle is given by
F(0) = Ex,y-P [In(1 + exp(+e (x, 0))) - y (x, 03
g(0: x) = o((x, 0))x yx
59

---

We now compute the gradient and the Hessian of F
exp( (x, 8))
VF(0) = 1+ exp (x, 0))
X 0((x, 0'))x
[()((x))) 0)) (0(xx 1))))) x]
FFF( E|o' ((x, 0) xxx 1
( (x. 0)) o( (x, 0x)
Since 0 S ot) I 1 for every t E R. we note that 0 N F()) 3 E[xx²] = E (as E[x] = 0). Hence, is convex and smooth with = || Furthermore, since (F()0) = 0 and convex, we conclude that 0* is minimizer of F.
It easy see that EE [0(;; x, v)] gradient is unbiased. Let n00; x, y) denote the stochastic gradient noise, i.c.,:
E ((x((x, 0)) (( ())) (F i.e., the stochastic
n x. y) g(0: x, 9) (F())
の (x. 8) x (x 0) + B[o((x, ))))x] yx
We shall now control the stochastic gradient covariance Σ()) El [n:00, (((0,,)))(0xx,,)))) v) To this end, we define ax(0) and (x. as follows:
ax (0) = ob (x, 0))x E [xx((xx)))
Cx,y (0) = EB (x, ))) y/x
We note that E [cx.y/ [x) = 0 and E[ax (0) 0. Since nx.y (0) ax (0) + bx.y (0), it follows that:
Σ(0)= E nn( x, y n (0; x, y)² E (0) ax (0)²] EE [xx,/ Cx.,y (0)²]
We now control each of the terms in the RHS as follows:
E ax (0) axx (0)²)-
E[ø((x xx) I O)x 0))x
= Eio((s (x, xx)xxxx]]
3 Exxx" ") <>
where we use the fact that (ot) S 1. Similarly,
E (0) Cx (0)²] EEyyxx² Elb (xx, 0*) (1)xx 0x)
= E[ xxx]
3 [x[xx"1 = 2
where we use the fact that E[ya = o(xx, 0*)) < 1. It follows that
( 3 2
Thus, the stochastic gradient oracle satisfies the Bdd. 2nd Moment assumption. Hence, the stochastic gradient oracle satisfies the Bdd. 2nd Moment assumption. Thus, the following result, which is formal version Corollary is implied by Theorem
Corollary 7 (Heavy Tailed Logistic Regression). Under the stochastic subgradient oracle described above, realized using N 2 In(In(d)) i.i.d samples from P. the average iterate of Algorithm 7 when run under the parameter settings of Theorem I
satisfies the following with probability at least - 8:
Tr(E) VIEE|2 (T((E) + 1|E112D1) In(1n(N)/6)
DEll2D
F(θN) - -(00))F(0') S DI
N
N
+ |EER>D +
|Σ
8/4
(Tr(E) + -|E1)D7) 1/4
N
N
60

---

G.4 Proof of Corollary 4
Recall from Section 5.4 that following linear model:
I2 and given target parameter #" E C, P defines the
Q E[x] O, E[xx' E y (x,
v=( 0*) Median(clx) 0
We allow both the covariate and target y to be heavy tailed, assuming only bounded second moments for x. We not assume any moment bounds on é e|x. The Least Absolute Deviation (LADD Regression problem involves estimating by solving SCO with the following sample loss
f(0:x. v) = (x. 8) - yy
The associated population risk and one possible realization of a stochastic subgradient oracle given by:
F()) [1 (0 0" x) -e ell g x. y) sgn( (0, x) y)x
where st) = f for & 0 and sgn = 0. We note that for every (x, E IR x IR, f(0; x, y) is convex function in 8, and thus, the population risk F is convex function, whose subgradient is given by:
(F( Isgn ((0 0" ,x x) c) x
We now show that F is Lipschitz function by bounding (F(0) as follows:
[[))())] E jsgn [(0 8*, x) <x ||
ssgn ((9 0" x) - c)1 |||]
E |
Tr(E)
where the second step follows from Jensen's inequality, the third step uses the fact that (sgn(t)) S and applies the Cauchy Schwarz inequality. Hence, F is G-Lipschitz with = Tr(E). We now show that (F( which would imply that 0" is minimizer of F (as F is convex)
V F(")) EE [sgn(e)x] E x E [sgn(e)
=
where we use the fact that [E|snn median.
[x]
O, because xx is continuous random variable with zero
For the stochastic gradient oracle described above, the associated stochastic gradient noise n(#; x, y) and its covariance (0) are given follows:
n 00 x) sgn((s 0* x) e)xx E (ggn((0 0" 0",x)) -))x]
(() = [sgn(( (0 8", x) - x)²xx² - EE [sgn((( - 0", x) e)x [gnn(( - -0,xx) c)x]²
= E [gnn( (0 8", x) c)2xx xxx
3 Xxx" Σ
Hence, the stochastic gradient oracle satisfies the Bdd. 2nd Moment assumption. Thus, the following result, which is formal version of Corollary 4 implied by Theorem g
Corollary 8 (Heavy Tailed LAD Regression).
Tr(E) + V Tr (r))) (n((n())/8)
D Tr()))) (n(uu(N)6))
D Tr(2)) In(1n(N2/6)>>>
F(θx) -(00) Div
N /V
NeurIPS Paper Checklist
1. Claims
61

---

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide complete mathematical proofs of the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
62

---

All the theorems, formulas, and proofs in the paper should be numbered and cross
referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper is purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer:
[NA]
Justification: Paper do note include experiments requiring code.
Guidelines:
63

---

reproducible, they The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.co cc/
oos.ouooiissoioooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //nips http:/cccppllcccgccccceeccc guides/ Coddeeubmsssse seiiiiiiicyyyyii for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity. the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
64

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: stttps://neurips.ccom http://wwww...cc.bba/lccccccclla
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is purely theoretical and we do foresee any societal impact this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
65

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: purely theoretical work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswwthcode cwm/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
66

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
67


Reviews:
[{"review_id": "dqcccdXfHA", "reviewer": "Reviewer_Wj6A", "summary": "The paper studies the clipping SGD algorithm and shows a refined analysis to improve the dependence on the variance. The authors also provide different applications of their new results.", "questions": "See **Weaknesses**.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The new concentration bounds are interesting, which is the key novel part of the work.", "weaknesses": "1. The key drawback is that the algorithm still requires many problem-dependent parameters like $D_1$ and $\\mathrm{Tr}(\\Sigma)$, which are hard to know, especially in a streaming setting.\n\n1. The time horizon $T$ is also requested to make the algorithm work. Is it possible to extend to the any-time setting?\n\n1. There is an extra $\\log{\\log{T}}$ term in the bounds.\n\n1. Please specify the stepsize $\\eta$ in Theorems 3 and 4.\n\n1. Line 82, missing a square root?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\Tr}{\\mathsf{Tr}} \\newcommand{\\deff}{d_{\\mathsf{eff}}}$ Thank you for your insightful feedback. We hope to address your concerns below:\n\n\n### Problem Dependent Parameters\n\nWhile our results assume knowledge of some problem-dependent quantities, we emphasize that such assumptions are **not unique to our work**. To the best of our knowledge, setting the step-size and related algorithmic parameters as a function of problem dependent quantities like $D_1$ and $\\Tr(\\Sigma)$ is a standard practice in the analysis of stochastic optimization algorithms [1; 2 Ch. 6 Thms 6.1 - 6.3]. Naturally, this is also prevalent in almost all prior works on clipped SGD [3, 4, 5]. For instance, [3, Thm 3.1] requires knowledge of $D_1$, $T$ and $\\Tr(\\Sigma)$ (corresponding to $R_0$, $N$ and $\\sigma^2$ respectively as per their notation) to set the batch-size, clipping level and step-size for clipped SGD. Moreover, our results can be easily adapted to settings where only upper bounds of problem-dependent quantities are available while the precise values are unknown. \n\nWe note that design of *parameter-free optimization algorithms* (i.e. algorithms that don't require prior knowledge of problem-specific parameters) is a sub-field of its own [6] involving significant technical challenges and algorithmic modifications that are orthogonal to the focus of our work. We believe that the techniques developed in our work could be used in conjunction with ideas from the parameter-free optimization literature to develop streaming parameter-free heavy tailed statistical estimators. Investigating this would be an interesting avenue of future work.   \n\n### Known Time Horizon\n\nOur assumption of a known time horizon was primarily made for the sake of clarity, and motivated by the fact that the time horizon (or equivalently, the sample budget) is typically known apriori in most ML and statistics applications (at least up to constant factors). We believe our results can be extended to the anytime setting by using a time-varying clipping level of the form $\\lambda_t = \\Theta(\\sqrt{t})$ (similar to [5]). However, incorporating this adjustment would significantly increase the length and technical complexity of our proofs, and subsequently obscure our key technical contributions. To this end, our results are presented assuming a fixed time horizon, similar to prior works on heavy tailed stochastic optimization [3,4].\n\n### Extra $\\ln(\\ln(T))$ Term\n\nWe respectfully disagree with the claim that the extra  $\\ln(\\ln(T))$ term is a major weakness of our work. We emphasize that, despite this extra term, our obtained rates continue to **significantly outperform** the previous state of the art in all practical regimes. To observe this, let $\\deff = \\tfrac{\\Tr(\\Sigma)}{\\||\\Sigma\\||_2}$ where $\\Sigma$ is the noise covariance. Note that $1 \\leq \\deff \\leq d$. Furthermore, $\\forall \\delta \\in (0,1)$ and $T \\leq e^{\\exp({(\\sqrt{\\deff}-1)\\ln(1/\\delta)})}$ , we have $\\sqrt{\\deff} \\ln(\\ln(T)/\\delta) \\leq \\deff \\ln(1/\\delta)$. Hence, our obtained rate of $\\sqrt{\\frac{\\Tr(\\Sigma) + \\sqrt{\\||\\Sigma\\||_2 \\Tr(\\Sigma)} \\ln(\\ln(T)/\\delta)}{T}}$ significantly outperforms the previous best known rate of $\\sqrt{\\frac{\\Tr(\\Sigma)\\ln(1/\\delta)}{T}}$ unless the time-horizon / sample budget $T$ exceeds $ e^{\\exp({(\\sqrt{\\deff}-1)\\ln(1/\\delta)})}$, which is quite impractical (as it involves a *double exponential* dependence on the effective dimension)\n\n### $\\eta$ in Theorems 3 and 4\n\nThank you for your feedback. We have updated our draft to specify $\\eta$ in the statement of Theorems 3 and 4.\n\n### Line 82\n\nThank you for the pointer. Line 82 is indeed missing a square root and we have updated our draft to rectify this. \n\n***\n### References\n\n1. Chi Jin, Optimization for ML Lecture Notes :  [URL](https://drive.google.com/file/d/1BKqs34avawbcw7WDWgJpq-xkHxNEL4c5/view)\n2. Sebastien Bubeck, Convex Optimization : Algorithms and Complexity\n3. Gorbunov et. al., Stochastic Optimization with Heavy Tailed Noise via Accelerated Gradient Clipping, NeurIPS 2020\n4. Tsai et. al., Streaming Heavy Tailed Statistical Estimation, AISTATS 2022\n5. Nguyen et. al., Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails, NeurIPS 2023\n6. Orabona and Cutkosky, ICML 2020 Tutorial on Parameter Free Online Learning : [URL](https://parameterfree.com/icml-tutorial/)", "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": "", "extra_scores": {}}, {"review_id": "w9m53iyFIs", "reviewer": "Reviewer_86zv", "summary": "The paper introduces significant advancements in the field of statistical estimation and optimization for heavy-tailed data. It improves the convergence complexity of the widely-used clipped-SGD algorithm in both strongly convex and general convex settings, achieving near-optimal sub-Gaussian statistical rates when the second moment of the stochastic gradient noise is finite.\n\nThe paper also introduces refined concentration guarantees for vector-valued martingales using the Donsker-Varadhan Variational Principle, enhancing the PAC-Bayes bounds of Catoni and Giulini.\nAdditionally, it provides a fine-grained analysis of clipped SGD for heavy-tailed SCO problems, achieving nearly subgaussian performance in a streaming setting with improved complexity over previous work.\nFurthermore, the paper develops streaming estimators for various heavy-tailed statistical problems, including mean estimation and regression (linear, logistic, and LAD), all exhibiting nearly subgaussian performance and improving upon prior guarantees.", "questions": "See the Weaknesses part.", "limitations": "The paper is theoretical, and I believe there is no need to confirm societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The paper presents several noteworthy contributions to the field of statistical estimation and optimization for heavy-tailed data, particularly in improving complexity.\n\nThe paper introduces novel improvements to the convergence complexity of the clipped-SGD algorithm, applicable to both strongly convex and general convex settings, as well as various assumption combinations. Achieving near-optimal sub-Gaussian statistical rates is a significant advancement in the field.\nThe technical rigor of the paper is evident in its thorough analysis and detailed proofs, with over 40 pages in the appendix. The authors systematically build on existing literature, as summarized in Table 1, providing a clear and logical progression of their arguments.\nThe fine-grained analysis of clipped SGD for heavy-tailed SCO problems is meticulously executed, demonstrating nearly subgaussian performance in a streaming setting. This improvement over previous work indicates a high level of quality in the research methodology and execution.\nThe paper is well-organized and clearly written, making complex theoretical concepts accessible. The authors effectively explain the significance of their contributions and how they build upon existing work, enhancing overall readability.\n\nThe improvements to the clipped-SGD algorithm have broad implications for practical applications in machine learning and statistical estimation, particularly in scenarios involving heavy-tailed data distributions.\nBy developing streaming estimators for various heavy-tailed statistical problems, the paper addresses a critical need in the field, providing robust solutions that exhibit nearly subgaussian performance. This has the potential to significantly impact both theoretical research and real-world applications.\n\nOverall, the paper excels in originality, quality, clarity, and significance, making substantial contributions to the field of statistical estimation and optimization for heavy-tailed data.", "weaknesses": "I am not an expert in this area and do not have time to check the proofs in detail. Therefore, my understanding relies solely on the content provided in the writing.\nDespite its significant contributions, the paper has several areas that could benefit from improvement:\n1. Lack of Technique-Proof Sketches in the Main Paper: While the paper presents numerous theorems, there is a noticeable absence of technique-proof sketches. These sketches would provide insights into how the authors build upon existing results compared to previous works. Including such sketches would enhance the clarity and transparency of the theoretical developments, making it easier for readers to grasp the novelty and progression of the contributions.\nThe current structure dedicates only half a page to showcasing the main technique in Section 6, which can be challenging for readers. A more effective approach might involve presenting one key theory with a detailed technique description in the main paper, and relegating supplementary theories to either the main paper with abbreviated details or the appendix.\n2. Theoretical Overemphasis: The paper may overly focus on presenting multiple theories without sufficiently integrating them into a cohesive narrative or demonstrating their practical application. A clearer alignment of the theoretical developments with practical implications would strengthen the paper's impact and relevance.\nFor instance, Section 5, which features many applications, could benefit from highlighting some of them in the background to help readers understand the importance and scenarios of the problems studied.\n3. Absence of Experimental Validation: Statistical estimation typically requires extensive data and iterations to observe convergence reliably. The lack of experimental validation in the paper limits its ability to demonstrate the practical effectiveness of the proposed algorithms.\nIncorporating experiments with diverse datasets and comparisons with existing methods would provide empirical evidence of the proposed techniques' efficacy and robustness in real-world scenarios.\n\nAddressing these points would enhance the paper’s clarity, relevance, and applicability, bridging the gap between theoretical developments and practical implementations in statistical estimation and optimization for heavy-tailed data.\nI welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback. We hope to address your concerns below: \n\n### Proof Sketches\n\nThank you for this helpful pointer which has helped improve our work. We have updated our draft to add a detailed proof sketch in the beginning of our Appendix. This new section expands upon the proof sketch of the iterative refinement technique presented in Section 6, and also outlines a proof of Theorem 3 (i.e. clipped SGD for smooth convex objectives) by applyinh the iterative refinement technique. Since camera ready versions of accepted papers are allowed to have an extra page, we would be happy to shift this section to the main paper if our work is accepted. \n\n### Theoretical Overemphasis\n\nThank you for pointing this out. Based on your helpful feedback, we have updated our presentation in Section 1 to emphasize the statistical applications, and added references to Section 5 wherever appropriate.\n\n### Empirical Validation\n\nWe note that gradient clipping is a standard technique in machine learning whose empirical performance very well investigated. Indeed, gradient clipping is widely used in several empirical deployments such as LLMs, Vision Transformers, GANs and PPO. On the contrary, a sharp statistical analysis of gradient clipping which justifies its empirical effectiveness has been relatively limited. To this end, our work focuses on presenting a thorough analysis of the theory behind gradient clipping by sharply characterizing its performance on a wide variety of streaming heavy tailed statistical estimation tasks.", "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": "", "extra_scores": {}}, {"review_id": "OmOmx9vvjQ", "reviewer": "Reviewer_rk1f", "summary": "This paper addresses the problem of high-dimensional heavy-tailed statistical estimation in a streaming setting, which is more challenging than the batch setting due to memory constraints. \n\nThe authors cast the problem as stochastic convex optimization (SCO) with heavy-tailed stochastic gradients. \n\nThey demonstrate that the Clipped Stochastic Gradient Descent (Clipped-SGD) algorithm attains near-optimal sub-Gaussian statistical rates when the second moment of the stochastic gradient noise is finite. \n\nThe rate is better than the previous result in terms of the fluctuation term that depends on $1/\\delta$ in the smooth and strongly convex case and fills the blank for smooth convex and Lipschitz convex cases.", "questions": "1. **Missing Reference**: The paper should include a citation to [1*], which modifies adaptive Huber regression for online bandit and MDP with heavy-tailed rewards. This work is related and should be cited in the \"Heavy-tailed Estimation\" part of Section 1.2.\n\n    - [1*] Li, Xiang, and Qiang Sun. \"Variance-aware decision making with linear function approximation under heavy-tailed rewards.\" Transactions on Machine Learning Research.\n\n2. **Extension to Strongly Convex and Lipschitz Cases**: Is it possible to extend the results to the strongly convex and Lipschitz case? If so, how would these results differ from those already derived in this paper?\n\n3. **Optimization Error and Statistical Error**: The error rate (e.g., $\\|x_{T+1}-x^{\\star}\\|$ in Theorem 1) typically comprises two parts: the optimization error (i.e., $\\frac{\\gamma D_1}{T + \\gamma}$ in (1)) and the statistical error (the other term in (1)). The paper's most significant contribution is on the statistical error, ensuring it behaves like a sub-Gaussian rate even when the gradient noise has only bounded variance. Two questions arise:\n   - Can the optimization error be accelerated using the techniques developed in this paper to handle heavy-tailed issues? This might be achieved by another algorithm. I just wonder whether the analysis technique, i.e., the iterative refinement strategy, could be used to tighten the analysis on the statistical error.\n   - Can the iterative refinement strategy be extended to cases with bounded $1+\\delta_0$ moments, where $\\delta_0 \\in (0, 1]$, rather than just bounded variance?\n\n4. **Comparison to Freedman's and Bernstein’s Inequalities**: The improvement in this paper is analogous to the improvement from Hoeffding's inequality to Bernstein’s inequality. However, to account for the Markov structure, Freedman’s inequality and the iterative refinement strategy are used to decouple dependencies. Is this understanding correct?", "limitations": "See the Questions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Improved Error Bounds**: The paper improves the known error bounds for Clipped-SGD, bringing them closer to the optimal sub-Gaussian rates. \n\n2. **Extension to Various Objectives**: The results are extended to smooth convex and Lipschitz convex objectives, broadening the applicability of Clipped-SGD to a wider range of optimization problems.\n\n3. **Novel Iterative Refinement Strategy**: The introduction of an iterative refinement strategy for martingale concentration is new to me. It might inspire similar techniques.\n\n4. **Good Clarity**: The paper is overall well-written and easy to follow.", "weaknesses": "1. **Missing Reference**: There is one paper from my perspective that is related but not cited.\n\n2. **How to Generalize the Established Results**: The paper contains many new theoretical results. It is unclear how others could use these proposed techniques for their interested cases. There are also some cases that the author didn't mention. See the Questions for the details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\Tr}{\\mathsf{Tr}}$ Thank you for your helpful feedback. We hope to address your concerns below:\n\n### Missing Reference\n\nThank you for pointing out this helpful reference. The work is indeed quite relevant and we have updated our draft to include the citation in Section 1.2.\n\n### Extension to Lipschitz Strongly Convex Problems\n\nIndeed, our proof techniques can be applied to Lipschitz Strongly Convex problems to obtain a guarantee similar to Theorem 1 for the weighted average iterate. However, due to space constraints, we decided to focus on results that directly led to interesting statistical applications such as mean estimation, linear regression, binary classification and LAD regression. \n\n### Improving the Optimization Error\n\nIndeed, we believe our iterative refinement strategy can be used to analyze accelerated stochastic optimization algorithms (such as the clipped SSTM algorithm of [1]) to obtain an improved optimization error rate. Accelerating the optimization error rate whilst simultaneously obtaining a (near)-optimal statistical rate is an interesting avenue of future work which we intend to look into.\n\n### Bounded $1 + \\delta_0$ Moments\n\nWe believe our iterative refinement technique is quite general and can be extended to handle bounded $1 + \\delta_0$ moments for $\\delta_0 \\in (0, 1]$ by carefully modifying the MGF bounds involved in the proof of Theorem 5, along with a re-derivation of the Martix Freedman inequality with $1+\\delta_0$ moment. This is a very promising avenue of future work which we are currently looking into.\n\nWe highlight that, unlike the well-studied case of bounded second moments, very little is known about the optimal statistical rates for heavy tailed estimation tasks under bounded $1 + \\delta_0$ moments, *even in the full batch setting*. To the best of our knowledge, [2] is the only work that analyzes statistical rates in this framework (under the full batch setting) for the specific task of mean estimation. It is still unknown whether existing works that analyze clipped SGD and its variants under bounded $1 + \\delta_0$ moments achieve statistical optimality. \n\n### Comparison to Freedman and Bernstein Inequalities\n\nTo the best of our understanding, the improvement obtained via our iterative refinement technique actually surpasses the typical Hoeffding-to-Bernstein improvement. To observe this, we note the following:\n\n -  Transitioning from Hoeffding to Bernstein leads to a sharper \"variance proxy\" (i.e. it gives us sharper concentration inequalities where the typical fluctuation is of the order of the variance instead of the almost sure bound on the random variable), which is necessary for obtaining an improved statistical rate.  \n\n -  Freedman's Inequality leads to further improvement by allowing the martingale / Markov structure of the noise to be incorporated within Bernstein's Inequality.   \n\n -  However, we find that the above steps alone are insufficient for obtaining the desired near-optimal statistical rate. In particular, as discussed in Section 6, a direct use of (Matrix) Freedman's inequality implies a rate of $\\sqrt{\\frac{\\Tr(\\Sigma) \\ln(d/\\delta)}{T}}$ which is far from optimal. To overcome this, we develop the iterative refinement technique which recursively improves upon the coarse bound implied by Freedman's inequality. As a result, we finally obtain the desired near-optimal statistical rate of $\\sqrt{\\frac{\\Tr(\\Sigma) + \\sqrt{\\||\\Sigma\\||_2 \\Tr(\\Sigma)}\\ln(\\ln(T)/\\delta)}{T}}$.\n***\n### References\n\n1. Gorbunov et. al., Stochastic Optimization with Heavy Tailed Noise via Accelerated Gradient Clipping, NeurIPS 2020. \n\n2. Cherapanamjeri et. al., Optimal Mean Estimation without a Variance, COLT 2022", "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": "", "extra_scores": {}}, {"review_id": "tNZKisqit4", "reviewer": "Reviewer_cbSj", "summary": "The paper gives a new concentration method to improve the bounds for the convergence of clipped-SGD when the noise has bounded second moments in the online/streaming setting. The method has also applications in streaming heavy-tailed statistical estimation, including streaming mean estimation and regression. The main idea of the method is by bootstrapping Freedman's inequality via iterative refinement using a PAC Bayesian argument. This new concentration method allows to obtain better bounds, closer to the optimal bounds than previous methods.", "questions": "- I'm a bit confused about the result in table 1. I didn't do the calculation myself but the bound shown in the last line mentioned both $T$ and $\\epsilon$, which is odd; and the dependence $\\log^2 1/\\delta$ in the lower order term is also higher than other bounds. Could the authors explain?", "limitations": "The authors have adequately addressed the limitations of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Overall, I think the paper has made a good contribution in sharpening known bounds for heavy-tailed clipped-SGD. The idea of bootstrapping Freedman's inequality via PAC Bayesian is very interesting and I agree with the authors that it would be interesting to further investigate the applications of this argument.\n- The proposed method has a wide range of applications and the authors have presented them quite thoroughly.", "weaknesses": "- The second moment bound assumption used in this paper appears to be stronger than the variance bound used in prior work for analyzing clipped-SGD. My understanding, for example from the work of Gorbunov et al, is that with the bounded variance assumption they use the simple scalar version of Freedman's so the dependence on the dimension might not be as good as stated here in the paper. It would be good if the authors can discuss this more clearly, for example what if we just use the high dimension version of Freedman's?\n- Another issue with current assumption 1 is that it seems not easy to extend the work to the bounded $p$-moment case, as we also know that we can do this very easily from the work of Gorbunov et al and follow up works\n- The clipping method requires to know the time horizon, which we know is unnecessary in some prior work, eg, Nguyen et al. The bounds are also sub-optimal in $T$ (with an extra $\\log\\log T$ factor).\n- In terms of presentation, I think proofs, especially section F, can be written in a more streamlined way  and for example, with an outline. \n- Some minor details  \nLine 82: There should be a square root in the bound  \nLine 106: We not(e) that  \n\nReference\n\nE. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping, NeuRIPS, 2020\n\nT. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen.  Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise, NeuRIPS, 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\Tr}{\\mathsf{Tr}} \\newcommand{\\deff}{d_{\\mathsf{eff}}} \\newcommand{\\vx}{\\mathbf{x}} \\newcommand{\\vz}{\\mathbf{z}} \\newcommand{\\vw}{\\mathbf{w}} \\newcommand{\\vn}{\\mathbf{n}} \\newcommand{\\bE}{\\mathbb{E}} \\newcommand{\\bR}{\\mathbb{R}} \\newcommand{\\dotp}[2]{\\left\\langle #1, #2 \\right \\rangle} \\newcommand{\\vv}{\\mathbf{v}} \\newcommand{\\vS}{\\mathbf{S}}$ Thank you for your helpful feedback. We hope to address your concerns below: \n### Assumption 1 and Gorbunov et. al. [3]\n\nAssumption 1 of our work is actually *equivalent to & more fine-grained than* the bounded second moment assumption of [3]. Here $\\Tr(\\Sigma)$ is the same as $\\sigma^2$ in [3], as explained below. Assumption 1 is more fine-grained as it allows us to obtain bounds in terms of both $\\Tr(\\Sigma)$ and $\\||\\Sigma\\||_2$.\n\nLet $\\vz \\in \\bR^d$ be a zero-mean random vector satisfying $\\bE[\\||\\vz\\||^2] \\leq \\sigma^2$ for some $\\sigma \\geq 0$ . By linearity of expectation, $\\Tr(\\bE[\\vz \\vz^T]) = \\bE[\\||\\vz\\||^2] \\leq \\sigma^2$. Hence, $\\bE[\\vz \\vz^T]$ is a well-defined PSD matrix with $\\Tr(\\bE[\\vz \\vz^T]) \\leq \\sigma^2$. It follows that there exists some PSD matrix $\\Sigma$ satisfying $\\bE[\\vz \\vz^T] \\preceq \\Sigma$ such that $\\Tr(\\Sigma) \\leq \\sigma^2$. The converse is argued similarly.\n\n### Iterative Refinement vs High Dimensional Freedman\n\nAs discussed in Section 6, a standalone application of the high-dimensional Freedman's inequality (i.e., Matrix Freedman) in conjunction with Assumption 1, is by itself insufficient to obtain the near-optimal rate, and instead implies a suboptimal rate of $\\sqrt{\\frac{\\Tr(\\Sigma) \\ln(d/\\delta)}{T}}$. This necessitates the development of our iterative refinement technique, which recursively improves the crude bound implied by Matrix Freedman, boosting it to a near-optimal rate of $\\sqrt{\\frac{\\Tr(\\Sigma) + \\sqrt{\\||\\Sigma\\||_2 \\Tr(\\Sigma)}\\ln(\\ln(T)/\\delta)}{T}}$. We have updated our draft to emphasize this point more explicitly in our proof outline. \n\n### Extending Assumption 1\n\nAssumption 1 can be extended to bounded $p^{\\mathsf{th}}$ moments for any $p > 1$ by assuming that there exists a PSD matrix $\\vS$ satisfying $\\bE_{\\xi \\sim P}[|\\dotp{\\vn(\\vx;\\xi)}{\\vv}|^p] \\leq (\\vv^T \\vS \\vv)^{p/2} \\ \\forall \\ \\vv \\in \\bR^d$. We note that this generalization recovers Assumption 1 for $p = 2$ and is similar to the weak moment assumption considered by [1], which, to our knowledge, is the only work that analyzes statistical rates for heavy tailed mean estimation under bounded $p^{\\mathsf{th}}$ moments ($p \\leq 2$). \n\nWe also note that beyond the specific case of mean estimation studied in [1], very little is known about the optimal statistical rates of heavy-tailed estimation under bounded $p^{\\mathsf{th}}$ moments, even in the full batch setting. Thus, it is unknown whether existing works that analyze clipped SGD and its variants under bounded $p^{\\mathsf{th}}$ moments achieve statistical optimality.\n\n### Known Time Horizon\n\nOur assumption of a known time horizon was primarily made for the sake of clarity, and motivated by the fact that the time horizon / sample budget is typically known apriori in most ML and statistics applications. We believe our results can be extended to the anytime setting by using a time-varying clipping level of the form $\\lambda_t = \\Theta(\\sqrt{t})$ (similar to [2]). However, incorporating this adjustment would significantly increase the length and technical complexity of our proofs, and subsequently obscure our main contributions. To this end, our results are presented assuming a fixed time horizon, similar to prior works on heavy tailed stochastic optimization [3,4].\n\n### Extra $\\ln(\\ln(T))$ Term\n\nWe emphasize that the extra  $\\ln(\\ln(T))$ term is not a major weakness of our work since our obtained rates continue to significantly outperform the previous state of the art in all practical regimes. To observe this, let $\\deff = \\tfrac{\\Tr(\\Sigma)}{\\||\\Sigma\\||_2}$  Note that $1 \\leq \\deff \\leq d$. Furthermore, $\\forall \\delta \\in (0,1)$ and $T \\leq e^{\\exp({(\\sqrt{\\deff}-1)\\ln(1/\\delta)})}$ , we have $\\sqrt{\\deff} \\ln(\\ln(T)/\\delta) \\leq \\deff \\ln(1/\\delta)$. Hence, our obtained rate of $\\sqrt{\\frac{\\Tr(\\Sigma) + \\sqrt{\\||\\Sigma\\||_2 \\Tr(\\Sigma)} \\ln(\\ln(T)/\\delta)}{T}}$ significantly outperforms the previous best known rate of $\\sqrt{\\frac{\\Tr(\\Sigma)\\ln(1/\\delta)}{T}}$ unless the time-horizon / sample budget $T$ exceeds $ e^{\\exp({(\\sqrt{\\deff}-1)\\ln(1/\\delta)})}$, which is quite impractical (as it involves a double exponential dependence on $\\deff$)\n\n### Proof Outline\n\n Thank you for this helpful pointer. We have updated our draft to add a brief proof outline for each of our key results in the appropriate sections of the Appendix. Furthermore, in accordance with Reviewer 86zv's feedback,  our updated draft contains an expanded proof sketch section at the beginning of the Appendix, which explains our iterative refinement technique more clearly, and also describes how its applied to prove Theorem 3 (clipped SGD for smooth convex objectives). \n\n### Table 1\n\nThanks for pointing out this typo. The sample complexity bound in the last row of the table is derived from Equation 1; it is obtained by finding the $T$ for which the error in function value is equal to $\\epsilon$. The $\\ln(T)$ term in the table should be replaced by $\\ln(1/\\epsilon),$ which makes the lower order (in $\\epsilon$) term $\\frac{D_1\\ln^2(\\delta^{-1}\\ln{1/\\epsilon})}{\\sqrt{\\epsilon}}$\n\n### Lines 82 and 106 \n\nThanks for pointing these out. Our updated draft corrects these typos.\n\n***\n1. Cherapanamjeri et. al., Optimal Mean Estimation without a Variance, COLT 2022\n2. Nguyen et. al., Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails, NeurIPS 2023\n3. Gorbunov et. al., Stochastic Optimization with Heavy Tailed Noise via Accelerated Gradient Clipping, NeurIPS 2020\n4. Tsai et. al., Streaming Heavy Tailed Statistical Estimation, AISTATS 2022", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the streaming heavy-tailed statistical estimation problem. The authors cast the problem as stochastic convex optimization with heavy-tailed stochastic gradients and prove that the clipped-SGD algorithm attains near-optimal sub-Gaussian statistical rates whenever the second moment of the stochastic gradient noise is finite. The main idea of the method is an iterative refinement for martingale concentration. All the reviewers are positive (one suggests accept, two weak accept, and one borderline accept). I decide to accept the paper.
Decision: Accept (poster)