Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD

Authors: aniket  das
dheeraj  nagaraj
arun sai suggala
prateek  varshney
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 12:33:37

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}.

Main paper: 
 introduction: 
 A fundamental problem in machine learning and statistics is 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: min x F (x) := E ξ∼P [f (x; ξ)], where x represents the parameter to be estimated, P is the underlying probability distribution which can only be accessed through samples, and f (x; ξ) is a function which quantifies the loss incurred at a point ξ by parameter x. In this paper, we focus on the setting where P is a heavy-tailed distribution for which the extreme values are more likely than in distributions like the Gaussian, f (•; •) is convex and the learner only has access to O(d) memory.The heavy-tailed statistical estimation problem has received increased attention of late because of the prevalence of heavy-tailed distributions in many statistical applications dealing with real world data [19, 49, 57, 23] . The presence of such heavy-tailed distributions can significantly degrade the performance of statistical estimation and testing procedures designed under Gaussian (or sub-Gaussian) tail assumptions [30, 24, 53, 24] . This has spurred recent research efforts towards developing estimators specifically tailored for heavy-tailed settings (e.g., [10, 44, 16, 36] ; see Section 1.2 for a more detailed literature review). Despite substantial progress on this problem in recent years, much of the 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 a stochastic convex optimization (SCO) problem with heavy-tailed gradients [17, 44, 52, 48] -with Clipped-SGD as the favored solution due to its simplicity [42] . Indeed, clipping has become a standard component in the training of modern deep neural networks and thus, the properties of Clipped-SGD have been studied widely in the literature [1, 56, 38, 48, 52] in various contexts. Specifically, several works have shown that Clipped-SGD has sub-Exponential or sub-Gaussian tails despite the presence of 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 a bounded 2 nd moment assumption on gradient distribution, are of the order Tr(Σ) ln( 1 /δ) T , where δ is the failure probability [52] . Note that this is still far from the optimal sub-Gaussian rates of Tr(Σ)+∥Σ∥ ln( 1 /δ) T . In this work, we bridge this gap with a sharper analysis of Clipped-SGD for SCO problems, achieving nearly sub-Gaussian rates (see Section 1.1). Our approach leverages a novel technique obtained by bootstrapping the Donsker-Varadhan Variational Principle to Freedman's inequality, yielding tighter concentration inequalities for vector martingales compared to those in [8] . This enables us to derive more refined rates for a variety of settings than a direct application of Freedman's inequality as in [52] .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.i.d) random variables with a finite covariance, behaves roughly like the empirical mean of Gaussian random variables with the same covariance, as T → ∞. That is, the empirical mean μ, the true mean µ and the covariance Σ are such that lim T →∞ P √ T ∥μ -µ∥ > Tr(Σ) + ∥Σ∥ 2 log( 1 δ ) ≤ δ. However, these asymptotic rates need not hold with a 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, 15] ). 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 Tr(Σ) log ( 1 δ ) /T with probability 1 -δ with a finite covariance assumption. Recent ground breaking works [37, 28, 8, 36] further improve upon these results to construct estimators which can achieve the CLT convergence rates of C Tr(Σ)+∥Σ∥2 log( 1 δ ) /T for every T and δ. Some of these estimators work under just the assumption that the second moment is bounded [37, 28, 9] and some even provide a nearly linear time algorithm [15] .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-art optimal mean estimators for robust gradient estimation, such methods can face significant challenges. First, most optimal mean estimators aren't designed for the streaming data setting with batch-size being 1. Second, these estimators can be complex, frequently relying on semi-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 a sub-optimal rate of Tr(Σ) ln( 1 /δ)/T , under bounded 2 nd moment assumption. In this work, we improve upon these rates and show that with T samples, clipped-SGD obtains a sharper rate of ) T with probability 1 -δ, which is closer to the truly sub-Gaussian rates.Table 1 : Sample complexity bounds (for converging to an ϵ approximate solution) of various 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. D 1 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 δ -1 dependence in the sample complexity.1 UnboundedClipped SGD Clipped SGD and it's variants have been studied under a variety of settings including convex, strongly-convex, non-convex losses, with various assumptions on the moments of stochastic gradients. The estimators of [21, 45, 14, 40] work under the assumption of bounded 2 nd moments, but require O(1/ϵ) batch size, to converge to an ϵ-approximate solution. Consequently, they are not suitable for streaming setting. The recent work of [52] , which is closest to our work, addresses this issue by analysing Clipped-SGD for batch size 1 for smooth, strongly convex losses. But they achieve a sub-optimal rate of Tr(Σ) ln( 1 /δ)/T . 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 [48, 46, 41, 34, 13] have studied Clipped-SGD with the assumption that the stochastic gradient has a finite p-th moment for some p ∈ (1, 2] . They derive fine-grained near optimal results in terms of dependence of T and p (but their dependence on log δ -1 is sub-optimal). In contrast, our work specifically the case considers p = 2 with a focus on improving the sub-Gaussian dependence in the high probability bounds in these works from Tr(Σ) log(1/δ) and approaching the truly sub-Gaussian rates for estimation 1.1.Heavy-tailed Estimation Heavy-tailed estimation has a 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 sub-Gaussian rates under the bounded 2 nd moment assumption [36, 10, 9, 27, 28, 15, 45] . Among these, the works of [15, 32] are particularly relevant to our work. The algorithm of [15] runs in linear time while requiring O(d log δ -1 ) memory. But it is not immediately clear how to use their estimator in the framework of SGD. [32] 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 = ω(log 3 δ -1 ), d = ω(log 2 (δ -1 )), 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 is primarily focused on 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 a surge of interest in developing estimators when both covariates and response variables are heavy tailed [5, 44, 17, 43] . However, most of these works are in the batch setting. Another line of work has considered streaming algorithms in the Huber-contamination model, which is a much harder contamination model than heavy-tails [18] . However, these algorithms when adapted to heavy-tailed setting, do not provide optimal rates.Iteratively Refined Martingale Concentration via PAC Bayes Our key technical result obtains fine-grained concentration guarantees for vector-valued martingales by using the Donsker-Varadhan 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 [11] ), which were used to analyze the clipped mean estimator. We believe these iterative refinement arguments could be of independent interest for developing fine-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 performance guarantees in the streaming setting with a batchsize of 1 and O(d) space complexity. In particular, we demonstrate that the sub-optimality gap after T steps scales as Tr(Σ) + ∥Σ∥ 2 Tr(Σ) log( 1 /δ), improving upon the best known scaling of Tr(Σ) 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 (LAD) 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 [8, 52, 32] (either in performance or in generality) For heavy-tailed linear regression under the assumption of bounded 4 th moments for the covariates and bounded 2 nd 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 R d equipped with the standard inner product ⟨•, •⟩ and the induced ℓ 2 norm ∥ • ∥. For any matrix A ∈ R m×n , we use ∥A∥ 2 to denote its Euclidean operator norm ∥A∥ = sup x̸ =0 ∥Ax∥ /∥x∥. For A ∈ R d×d , we denote its trace as Tr(A). For any random vector x, we denote its covariance matrix as Cov[x]. We use ≲, ≳ and ≍ to denote ≤, ≥ and = respectively, upto universal multiplicative constants. We use ∇f (x) to denote the gradient of a differentiable function For any convex function f , we use ∂f (x) to denote an arbitrary subgradient of f at x. 
background and problem formulation: 
 Our work studies the Stochastic Convex Optimization (SCO) problem, described as follows: Let C denote a closed convex subset of R d and let F : C → R be a convex function. We aim to solve:EQUATIONassuming access to a convex projection oracle Π C and a stochastic gradient oracle, which we define as follows: Let P denote a probability measure supported on an arbitrary domain Ξ from which we can draw samples. A stochastic gradient oracle for F is a function g : C × C, which, given a point x ∈ C and a sample ξ ∼ P returns an unbiased estimate g(x; ξ) of ∇F (x) i.e., E ξ∼P [g(x; ξ)] = ∇F (x).If F is nondifferentiable, E ξ∼P [g(x; ξ)] = ∂F (x). Note that we do not assume direct access to ∇F (x), which may be expensive or intractable to compute. Our objective is to (approximately) solve SCO subject to a 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 F (x) := E ξ∼P [f (x; ξ)], where f denotes the sample-level loss function. The associated stochastic gradient oracle is g(x; ξ) := ∇f (x; ξ), ξ ∼ 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 n(x; ξ) = g(x; ξ) -∇F (x) to denote the stochastic gradient noise and assume it has finite second moment, i.e., Σ(x) = E ξ∼P [n(x; ξ)n(x; ξ) T ] exists for every x ∈ C. Our results make use of either of the following assumptions on Σ(x).Assumption 1 (Bounded Second Moment). The exists a positive semidefinite matrix Σ such that:Σ(x) ⪯ Σ ∀ x ∈ C (Bdd. 2 nd Moment)Similar assumption has been made by several prior works [21, 40, 14, 45] . We also consider the following generalized assumption, which is as a refinement of the one made in Tsai et al. [52] .Assumption 2 (Second Moment with Quadratic Growth). There exist constants α, β ≥ 0 and 1 ≤ d eff d such that the following holds for everyx ∈ C ∥Σ(x)∥ 2 ≤ α∥x -x * ∥ 2 + β; Tr(Σ(x)) ≤ d eff α∥x -x * ∥ 2 + β (QG 2 nd 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 to be infinite. That is, our results hold even whenE ξ∼P [| ⟨n(x; ξ), v⟩ | 2+ϵ ] = ∞ for every ϵ > 0, v ∈ R dOur work analyzes SCO under either of the following structural assumptions assumptions on F Assumption 3 (Convexity). F : R d → R is a convex function if the following holds for any t ∈ [0, 1]F (tx + (1 -t)y) ≤ tF (x) + (1 -t)F (y) ∀ x, y ∈ R d (Convexity)Assumption 4 (µ-Strong Convexity). F : R d → R is a µ-strongly convex function for µ ≥ 0 if the following holds for every t ∈ [0, 1]F (tx + (1 -t)y) ≤ tF (x) + (1 -t)F (y) -t(1 -t) • µ 2 ∥x -y∥ 2 ∀ x, y ∈ R d (µ-Strong Convexity)In addition, we also consider either of the two regularity assumptions on F Assumption 5 (L-smoothness). F : R d → R is L-smooth for some L ≥ 0 if F is continuously differentiable and satisfies the following:∥∇F (x) -∇F (y)∥ ≤ L∥x -y∥ ∀ x, y ∈ R d (L-smoothness)Assumption 6 (G-Lipschitzness). F : R d → R is G-Lipschitz for some G ≥ 0, i.e., F is continuous and satisfies the following:∥F (x) -F (y)∥ ≤ G∥x -y∥ ∀ x, y ∈ R d (G-Lipschitzness) 
results: 
 Under the Bdd. 2 nd Moment and QG 2 nd Moment assumptions, streaming algorithms for SCO 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 under heavy tailed stochastic gradients, which typically exhibit large fluctuations from their expected value due to its higher order moments being potentially infinite. Clipped SGD mitigates the large fluctuations typically observed in the heavy tailed stochastic gradient g(x; ξ) by thresholding its norm as follows. The full algorithm is described in Algorithm 1.clip Γ (g(x; ξ)) := g(x; ξ) ∥g(x; ξ)∥ • min{Γ, ∥g(x; ξ)∥}We now present our performance guarantees for clipped SGD for streaming heavy tailed SCO, wherein Algorithm 1 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 * ∈ C to denote an arbitrary minimizer of F , which is assumed to always exist, and guaranteed to be unique if F satisfies µ-Strong Convexity. We use x 1 to denote the initialization of Algorithm 1 and letD 1 = ∥x -x * ∥. Algorithm 1 Clipped Stochastic Gradient Descent Input: Initialization x 1 , Horizon T , Step Sizes (η t ) t∈[T ] , Clipping Level Γ 1: for t ∈ [T ] do 2:g t ← g(x t ; ξ t ), ξ t ∼ P 3: x t+1 ← Π C (x t -η t • clip Γ (g t ))Γ = µ ln(ln(T )/δ) (γ + 1) 2 D 2 1 + (T +γ)µ 2 (Tr(Σ) + Tr(Σ)∥Σ∥2 ln( ln(T ) /δ))satisfies the following with probability at least 1 -δ∥xT +1 -x * ∥ ≲ γD1 T + γ + 1 µ Tr(Σ) + Tr(Σ)∥Σ∥2 ln( ln(T ) /δ) T + γ (1)where γ ≍ max{ ∥Σ∥2κ 2 ln( ln(T ) /δ) 2, κ 3 /2 ln( ln(T ) /δ), κ ln( ln(T ) /δ) 2 }We use Theorem 1 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 5. and clipping level Γ = µ ln( ln(T ) /δ)EQUATIONwhere γ ≍ max{αd eff µ 2 , α √ d eff µ 2 ln( ln(T ) /δ), κ √ α µ ln( ln(T ) /δ), √ καd eff µ ln( ln(T ) /δ), κ 2/3 α 1/3 d 1/3 eff µ 2/3 ln( ln(T ) /δ), κ 3/2 ln( ln(T ) /δ), κ ln( ln(T ) /δ) 2 , κ 2 d eff ln( ln(T ) /δ)}Comparison to Prior Works To the best of our knowledge, the result closest to Theorem 2 is [52,Theorem 1] which analyzes streaming strongly convex SCO and obtains a ζD1 T +ζ + 1µ βd eff ln( 1 /δ) T +ζ rate for ζ ≍ αd eff log( 1 /δ) µ 2. We note that Theorem 2 obtains a significantly better confidence bound which is closer to the optimal subgaussian rate compared [52, Theorem 1] .Extra log log T term: Our bounds for the statistical error is of the form1 µ β(d eff + √ d eff ln( ln(T ) /δ)) T +γwhich has an extra log log T factor in the lower order term. This is still sharper than prior works with bounds of the form Moving beyond strong convexity, we present Theorems 3 for smooth convex functions and 4 for Lipschitz convex function, proved in Appendix D and E respectively. To the best of our knowledge, these are the first results for streaming heavy-tailed convex SCO that exhibits near-subgaussian concentration without strong convexity.Theorem 3 (Smooth Convex Objectives). Let Convexity, L-smoothness and Bdd. 2 nd Moment be satisfied. Then, for any δ ∈ (0, 1 /2) and T ≥ ln(ln(d)), there exists an η ∈ (0, 1 /2L] such that the average iterate of Algorithm 1 run for T iterations with step-size η t = η and clipping levelΓ = T √ ∥Σ∥2( √ Tr(Σ)+LD1) ln( ln(T ) /δ)satisfies the following with probability at least 1 -δ:F (xT ) -F (x * ) ≲ LD 2 1 T + D1 Tr(Σ) + ∥Σ∥2 Tr(Σ) + LD1 ln( ln(T ) /δ) T + oT (L, D1, Σ)where o T (L, D 1 , Σ) represents terms that are of lower order in T (explicated in Appendix D) Theorem 4 (Lipschitz Convex Objectives). Let Assumptions Convexity, G-Lipschitzness and Bdd. 2 nd Moment be satisfied. Then, for any δ ∈ (0, 1 /2) and T ≥ ln(ln(d)), there exists an η ∈ (0, G /√ T ] such that the average iterate of Algorithm 1 run for T iterations with step-size η t = η and clippinglevel Γ = T √ ∥Σ∥2( √ Tr(Σ)+G) ln( ln(T ) /δ)satisfies the following with probability at least 1 -δF (xT ) -F (x * ) ≲ D1G √ T + D1 Tr(Σ) + ∥Σ∥2 Tr(Σ) + G ln( ln(T ) /δ) T + oT (G, D1, Σ)where o T (G, D 1 , Σ) represents terms that are lower order in T (explicated in Appendix E)Remark: We use Theorem 3 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.In Theorems 3 and 4, the leading order term in the error is of the form: 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 sub-Gaussian gradient noise. To be precise, [35, Theorem 3.1] shows a weaker bound ofEQUATIONδ)) /T in the setting of Theorem 4, but when the noise is sub-Gaussian. . Let Ξ = C, E ξ∼P [ξ] = m ∈ C.We further assume Cov[ξ] ⪯ Σ and allow the higher moments to be infinite. As described in Appendix G.1, this is an SCO problem with the sample loss f (x; ξ) = 1 2 ∥x -ξ∥ 2 . The population loss and the stochastic gradient are given by:F (x) = 1 2 ∥x -m∥ 2 + Tr(Cov ξ∼P [ξ]); g(x; ξ) = x -ξThe following result, proved in Appendix G.1 via an application of Theorem 1, shows that the last iterate of clipped SGD attains near-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 ≳ ln(ln(d)) i.i.d samples ξ 1 , . . . , ξ N ∼ P , the last iterate of Algorithm 1 when run under the parameter settings of Theorem 1 satisfies the following with probability at least 1 -δ∥xN+1 -m∥ ≲ γ∥x1 -m∥ N + γ + Tr(Σ) + ∥Σ∥2Tr(Σ) ln( ln(N ) /δ) N + γwhere γ ≍ ln( ln(N ) /δ) 2Comparison to Prior Works The clipped mean estimator of [8] and the clipped-SGD based estimator in [52] come with a guarantee of the form ∥ m -m∥ ≲ Tr(Σ) log( 1 δ ) /N with probability 1 -δ. Our result in Corollary 1 obtains a sharper rate of convergence. In a recent work, Lee and Valiant [32] showed that the trimmed mean estimator achieves the optimal rate of Tr(Σ)/N when N = ω(log 3 δ -1 ), d = ω(log 2 (δ -1 )). Our result matches this optimal rate in those settings, but is considerably more general, as it holds for any N, d. 
streaming heavy tailed linear regression: 
 In the current and subsequent sections, we use θ ∈ C to denote the parameter of F . Let Ξ = R d × R. Given a target parameter θ * ∈ C, P defines the following linear model:x ∼ Q, E[x] = 0, E[xx T ] = Σ ≻ 0; y = ⟨x, θ * ⟩ + ϵ, E[ϵ|x] = 0, E[ϵ 2 |x] ≤ σ 2In addition, we make the following bounded 4 th moment asumption on the covariates xE[⟨x, v⟩ 4 ] ≤ C4(E[⟨x, v⟩ 2 ]) 2 ∀ v ∈ R dfor some numerical constant C 4 ≥ 1. Note that we allow both the covariate x and the 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 is to estimate θ * in a 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 f (θ; x, y) = 1 2 (⟨x, θ⟩ -y) 2 . The associated population loss F (θ) and the stochastic gradient oracle g(θ; x, y) are given by:F (θ) = 1 2 (θ -θ * ) T Σ(θ -θ * ); g(θ; x, y) = (⟨x, θ⟩ -y)xCorollary 2 (Heavy Tailed Linear Regression). Under the stochastic gradient oracle described above, implemented using N ≳ ln(ln(d)) i.i.d samples from P , the last iterate of Algorithm 1 when run under the parameter settings of Theorem 2 satisfies the following with probability at least 1 -δ:∥θN+1 -θ * ∥ ≲ γ∥θ1 -θ * ∥ N + γ + σ λmin (Σ) Tr(Σ) + ∥Σ∥2Tr(Σ) ln( ln(N ) /δ) N + γwhere γ ≍ max C4κ 2 Tr(Σ), C 4 κ 2 Tr(Σ) ∥Σ∥2 ln( ln(N ) /δ), κ ln( ln(N ) /δ) 2 and κ = ∥Σ∥2 λmin(Σ)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∥θ1-θ * ∥ N +ζ + σ λmin (Σ) ∥Σ∥2d ln( 1 /δ) N +ζ with ζ = C 4 dκ 2 ln( 1 /δ).Furthermore, our result is much closer to the optimal subgaussian rate and gracefully adapts to the stable rank or effective dimension [32] , i.e., d eff = Tr(Σ) /∥Σ∥, therefore implying significant speedups over [52] in settings where d eff ≪ d.Let Ξ = R d × {0, 1} and given a target parameter θ * ∈ C, P denote the following linear-logistic model:x ∼ Q, E[x] = 0, E[xx T ] ⪯ Σ; y ∼ Bernoulli(ϕ(⟨θ * , x⟩))where ϕ(t) = (1 + e -t ) -1 . The covariates x are heavy tailed, with only bounded second moments. The negative log likelihood of y|x is given by f (θ; x, y) = ln(1 + exp(⟨x, θ⟩)) -y ⟨x, θ⟩. The objective of the logistic regression problem is to estimate θ * by minimizing the population-level negative log likelihood:F (θ) = E x,y∼P [ln(1 + exp(⟨x, θ⟩)) -y ⟨x, θ⟩]which is minimized at θ * . Here, the stochastic gradient oracle is g(θ; x, y) = ϕ(⟨x, θ⟩)x -yx. The following result applies Theorem 3 to 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 ≳ ln(ln(d)) i.i.d samples from P , the average iterate of Algorithm 1, when run under the parameter settings of Theorem 4 satisfies the following with probability at least 1 -δ:F ( θN ) -F (θ * ) ≲ D1 Tr(Σ) + ∥Σ∥2 Tr(Σ) + ∥Σ∥2D1 ln( ln(N ) /δ) N + oN (Σ, D1)where o N (Σ, D 1 ) represents terms that are lower order in N (explicated in Appendix G.3Note that the standard analysis of SGD, with the assumption that ∥x∥ ≤ R almost surely leads to a bound of the form [4, Proposition 5] :F ( θN ) -F (θ * ) ≲ RD1 √ log( 1 δ ) √ NLet Ξ = R d × R. Given a target parameter θ * ∈ C, P defines the following linear model:x ∼ Q, E[x] = 0, E[xx T ] ⪯ Σ; y = ⟨x, θ * ⟩ + ϵ, Median(ϵ|x) = 0We allow both the covariate x and target y to be heavy tailed, assuming only bounded second moments for x. We do not assume any moment bounds on ϵ|x.The assumption E[x] = 0 is made for the sake 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, θ⟩ -y|. The stochastic subgradient oracle and population risk is given by:g(θ; x, y) = sgn(⟨θ, x⟩ -y)x, F (θ) = E [| ⟨θ -θ * , x⟩ -ϵ|]where sgn(t) = t ∥t∥ for t ̸ = 0 and sgn(0) = 0. The following result, whose full statement and proof is presented in Appendix G.4, applies Theorem 4 to show that the average iterate of clipped SGD attains near-subgaussian 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 ≳ ln(ln(d)) i.i.d samples from P , the average iterate of Algorithm 1, when run under the parameter settings of Theorem 4 satisfies the following with probability at least 1 -δ:F ( θN ) -F (θ * ) ≲ D1 Tr(Σ) + ∥Σ∥2Tr(Σ) ln( ln(N ) /δ) N + oN (Σ, D1)where o N denotes terms that are lower order in N (explicated in Appendix G.4) 
improved martingale concentration via iterative refinement: 
 Our results are based on the following concentration result for R d valued martingales. The proof appears in Appendix F. Suppose M t for t = 0, . . . , T is an R d valued martingale such that M 0 = 0 almost surely, the difference sequencev t := M t -M t-1 is such that ∥v t ∥ ≤ Γ and E[v t v ⊺ t |F t-1 ] = Σ t almostsurely for every t = 1, . . . , T for some Γ > 0. Assume that there exist deterministic sequences p 1 , . . . , p T and q 1 , . . . , q T such that Tr(Σ t ) ≤ q t and ∥Σ t ∥ ≤ p t almost surely. Theorem 5. Let q := 1 T T t=1 q t and p := 1 T T t=1 p t . Then, for any δ ∈ (0, 1 2 ):P(sup t≤T ∥Mt∥ ≥ g(T, δ) √ T ) ≤ δ Where g(T, δ) = C M √ q + p√ T Γ + Γ √ T log( K δ) and K = ln ln((√ qT Γ + 1) log(d + 1)) + C M for some universal constant C MTo prove this result, we first use Freedman's inequality [20, 51] to obtain a coarse-grained g 0 such that P(sup t ∥M t ∥ > g 0 √ T ) ≤ δ. We then iteratively refine this inequality via a PAC Bayesian [8, 11, 12] argument to show that P(supt ∥M t ∥ > g k+1 √ T | B k ) ≤ δ, where B k = {sup t ∥M t ∥ ≤ g k √ T } and g 2 k+1 ≲ Tr(Σ) + g k ∥Σ 2 ∥ log( 1 /δ). 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 ≈ 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 t be the centered version of clip Γ (g t ), ensuring ∥v t ∥ ≤ 2Γ almost surely. Suppose Σ t = Σ for some fixed Σ and let Γ = ∥Σ∥T /log( K δ ). Then, with probability 1 -δ: sup t≤T ∥M t ∥ ≲ T Tr(Σ) + T ∥Σ∥ log( K δ ).Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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, or as supplemental material. 
proof sketch: 
 We sketch our proof technique for the case of smooth convex functions considered in 3. We consider the SGD iterations x 1 , . . . , x T with clipped stochastic gradient at time t denoted by clip Γ (g t ) = ∇F (x t ) + v t + b t . Here, v t is the zero mean 'variance' such that E[v t |x t ] = 0 and ∥v t ∥ ≤ 2Γ almost surely. b t 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 t+1 -x * ∥ 2 ≤ ∥x t -x * ∥ 2 -2η t [F (x t )-F (x * )]-2η t ⟨v t +b t , x t -x * ⟩+η 2t ∥∇F (x t )+v t +b t ∥ 2 Considering constant step-sizes, we sum the inequalities for each t to conclude:EQUATIONThe 'random' terms to bound compared to gradient descent here are t ⟨v t + b t , x t -x * ⟩ and t ∥v t ∥ 2 + ∥b t ∥ 2 Lemma 13 shows that ∥x t -x * ∥ ≤ 2∥x 1 -x * ∥ with high probability. Under this event, we bound t ⟨v t , x t -x * ⟩ using the standard Freeman's inequality and ∥∇F (x t )∥ 2 by using smoothness and the fact that ∇F (x ⋆ ) = 0. The bias of the estimator ∥b t ∥ is bound using arguments similar to [8] (see Lemma 4) . The main improvement of our method is given by our method of bounding 1 T t ∥v t ∥ 2 . We show by an application of Theorem 5 that 1 T t ∥v t ∥ 2 ≲ Tr(Σ) + Tr(Σ)∥Σ∥ 2 log( log T δ ) with probability at-least 1 -δ whenever the clipping factor Γ is appropriately chosen. Choosing the step size η appropriately gives us the result in Theorem 3.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, confidence intervals, or statistical significance tests, at 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified.• 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 of range (e.g. negative error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 of this work.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (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 a 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.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/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 was obtained from people whose asset is used. • 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. 
conclusion and limitations: 
 Our work obtained nearly subgaussian rates for heavy-tailed SCO using clipped SGD by developing a fine-grained iterative refinement strategy for martingale concentration. As corollaries, we obtained state-of-the-art streaming estimators for various heavy tailed statistical problems. We note Clipped-SGD is widely used to 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-probability guarantees for non-convex losses. Our bounds are currently of theform d+ √ d ln( ln(T ) /δ) T, which is suboptimal compared to the tight subgaussian rate of d+ln( 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 ln( ln(T ) /δ) dependence on the confidence level (as opposed to the typical ln( 1 /δ) scaling). However, this is not a major drawback as our results continue to significantly outperform prior works unless T ≫ e exp( √ d-1) ln(1/δ) (which is an impractical regime). This drawback arises due to the ln(ln(T )) iterations of our iterative refinement technique and we believe it can be removed via more sophisticated martingale concentration arguments. Our work lays the foundation for several interesting avenues for future work including the analysis of heavy tailed statistical estimation under bounded p th moment assumptions (for p < 2) and the development of parameter free statistical estimators that do not require knowledge of problem-dependent parameter such as ∥Σ∥, δ etc. (or their respective upper bounds). Deriving anytime valid guarantees for clipped SGD using our techniques is also an interesting future direction.  
 
 Appendix: In this section, we 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 EX 2 = ν. Then, for any λ ∈ R such that |λ| ≤ 1 2Γ , the following holds:E exp(λX) ≤ exp(λ 2 ν) Consider a R d valued martingale (M t ) Tt=0 with respect to the filtration (F t ) T t=0 such that M 0 = 0 almost surely. We consider the martingale difference sequence v t := M t -M t-1 for t ≥ 1. Clearly, we must have:M t = t s=1 v s Definition 1.We say that the martingale M t satisfies (g, T, δ) uniform concentration if:P( sup 0≤t≤T ∥M t ∥ > g √ T ) ≤ δ Assume that for fixed Γ > 0 and Σ ∈ R d×d that ∥v s ∥ ≤ Γ almost surely and E[v t v ⊺ t |F t-1 ] =: Σ t .Suppose Tr(Σ t ) ≤ q t and ∥Σ t ∥ 2 ≤ p t almost surely for some non-random constants p t , q t . 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 6. Suppose M t satisfies the assumptions above. Let q := 1 T T s=1 q t the following is true:P( sup 0≤t≤T ∥M t ∥ > α) ≤ (d + 1) exp(- α 2 /2 qT + Γα 3 )That is, for any δ > 0, the martingale (M t ) t≤T obeys (g 0 (δ), T, δ) uniform concentration, whereg 0 (δ) = 2Γ 3 √ T log( d+1 δ ) + 2q log( d+1 δ )The following inequality is a corollary of Theorem 6. Lemma 2. Let g t ∈ R d be F t-1 measurable. Then for some constant c 1 > 0, we have:EQUATIONWhere A = sup 1≤t≤T A tIn addition, we also use the following scalar version of Freedman's inequality Lemma 3 (Freedman's Inequality). Let h 1 , h 2 , . . . , h T be aF t adapted martingale difference sequence such that E[h t |F t-1 ] = 0, E[h 2 t |F t-1 ] = σ 2t and ∥h t ∥ ≤ τ . Then, for any δ ∈ (0, 1), the following holds with probability at least 1 -δ:t s=1 h s ≤ 2 ln( 1 /δ) t s=1 σ 2 s + 2τ ln( 1 /δ)The following lemma, which bounds the moments of a clipped random vector, is crucial to our analysis of the bias and variance of the clipped stochastic gradient. Lemma 4 (Moments of a Clipped Random Vector). Let z ∈ R d be a random vector sampled from the distribution P with mean m and covariance matrix S. For any Γ > 0, let z = clip Γ (z), and let m and S denote the mean and covariance of z respectively, i.e., m = E[z] andS = E (z -m) (z -m) T .Then, the following hold:∥ m -m∥ ≤ ∥S∥ 2 Γ ∥m∥ + Tr(S) + ∥m∥ Γ 2 ∥m∥ 2 + Tr(S) ∥ S∥ 2 ≤ ∥S∥ 2 + ∥m∥ 2 Γ 2 ∥m∥ 2 + Tr(S) Tr( S) ≤ Tr(S)Proof. The proof of this lemma uses arguments similar to that of Catoni and Giulini [8] . We first note that for anyx ∈ R d clip Γ (x) = x • min{1, Γ -1 ∥x∥} Γ -1∥x∥ Following the proof of Proposition 2.1 of Catoni and Giulini [8] , we observe that for any t > 0:0 ≤ 1 - min{1, t} t ≤ inf p≥1 p p t p (p + 1) p+1 Define θ(x) = min{1,Γ -1 ∥x∥} Γ -1 ∥x∥ ∀x ∈ R d . Note that clip Γ (x) = θ(x) • x.From the above inequality, we note that:0 ≤ 1 -θ(x) ≤ inf p≥1 p p (p + 1) p+1 • ∥x∥ p Γ p (5) Consider any unit vector e ∈ R d . Then, ⟨e, m -m⟩ = E [⟨e, z -z⟩] = E [⟨e, z -θ(z)z⟩] = E [(1 -θ(z)) ⟨e, z -m⟩] + ⟨e, m⟩ E [(1 -θ(z))] ≤ E [(1 -θ(z))| ⟨e, z -m⟩ |] + ∥m∥E [(1 -θ(z))] ≤ E inf p≥1 p p (p + 1) p+1 • ∥z∥ p | ⟨e, z -m⟩ | Γ p + ∥m∥E inf p≥1 p p (p + 1) p+1 • ∥z∥ p Γ pwhere the second step uses the definition of θ(z) and the last step uses equation ( 5). Now, substituting p = 1 and p = 2 in the first and second terms of the RHS respectively, we obtain the following:⟨e, m -m⟩ ≤ 1 Γ E [∥z∥ ⟨e, z -m⟩] + ∥m∥ Γ 2 E[∥z∥ 2 ] ≤ 1 Γ E[∥x∥ 2 ] E[⟨e, z -m⟩ 2 ] + ∥m∥ Γ 2 E[∥z∥ 2 ] ≤ ∥S∥ Γ • ∥m∥ 2 + Tr(S) + ∥m∥ Γ 2 ∥m∥ 2 + Tr(S) ≤ ∥S∥ 2 Γ ∥m∥ + Tr(S) + ∥m∥ Γ 2 ∥m∥ 2 + Tr(S)where the second step uses the Cauchy Schwarz inequality and the last step uses the subadditivity of the square root. It follows that:∥ m -m∥ = sup ∥e∥=1 ⟨e, m -m⟩ ≤ ∥S∥ 2 Γ ∥m∥ + Tr(S) + ∥m∥ Γ 2 ∥m∥ 2 + Tr(S) To bound ∥ S∥, we first note that for any x ∈ R d , 0 ≤ θ(x) ≤ 1. As before, let e ∈ R d denote an arbitrary unit vector. We note that E[⟨e, z -m⟩ 2 ] = E[⟨e, z -m⟩ 2 ] + E[⟨e, m -m⟩ 2 ] ≥ E[⟨e, z -m⟩ 2 ]. Hence, it follows that, E ⟨e, z -m⟩ 2 ≤ E ⟨e, z -m⟩ 2 ≤ E (θ(z) ⟨e, z⟩ -⟨e, m⟩) 2 = E (θ(z) ⟨e, z -m⟩ -(1 -θ(z)) ⟨e, m⟩) 2 ≤ E θ(z) ⟨e, z -m⟩ 2 + ⟨e, m⟩ 2 E [(1 -θ(z))] ≤ E ⟨e, z -m⟩ 2 + ∥m∥ 2 E inf p≥1 p p (p + 1) p+1 ∥z∥ p Γ p ≤ ∥S∥ 2 + ∥m∥ 2 E[∥z∥ 2 ] Γ 2 ≤ ∥S∥ 2 + ∥m∥ 2 Γ 2 ∥m∥ 2 + Tr(S)where the fourth step uses Jensen's inequality by noting that 0 ≤ θ(z) ≤ 1 and the fifth step uses equation (5) .Finally, To upper bound Tr( S), we note that clip Γ is a contractive mapping as it is the projection operator onto a convex set (namely the ball of radius Γ in R d centered at the origin). To this end,Tr( S) = E ∥z -m∥ 2 = 1 2 E z1,z2 i.i.d. ∼ P ∥clip Γ (z 1 ) -clip Γ (z 2 )∥ 2 ≤ 1 2 E z1,z2 i.i.d. ∼ P ∥z 1 -z 2 ∥ 2 = Tr(S)The following result, which is a corollary of Theorem 5, 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 F.3Corollary 5 (PAC Bayesian Inequality for Quadratic Variation). Let v 1 , . . . , v T be an R d valued martingale difference sequence adapted to the filtration F 1 , . . . ,F T satisfying E[v s |F s ] = 0, E[v s v T s |F s ] = Σ s and ∥v s ∥ ≤ τ almost surely. Let UP(t) := min(T, 2 ⌈log 2 t⌉). Suppose ∥Σ s ∥ 2 ≤ p s and Tr(Σ s ) ≤ q s for some fixed sequences p 1 , . . . , p T and q 1 , . . . , q T . Then, there exists a universal constant C lower such that whenever T > C lower log((1 +√ qT Γ ) log(d + 1)) such that the following inequality holds with probability at least 1 -δ, for any δ ∈ (0, 1 2 ):t s=1 ∥v s ∥ 2 ≤ C M UP(t) s=1 q s + C M τ 2 ln( ln(T ) δ ) 2 + C M t τ 2 UP(t) s=1 p 2 s ∀t ∈ [T ]where C M > 0 is an absolute numerical constant.Let d eff = Tr(Σ) ∥Σ∥2 and let K = 4 max{8, C M , ln(T )}. For t ≥ 1, define the filtrationF t = σ (x 1 , g s |1 ≤ s ≤ t) and F 0 = σ(x 1 ). Furthermore, let ∇F (x t ) = clip Γ (g t ) + b t + v t where b t = ∇F (x t ) -E[clip Γ (g t )|F t-1 ] and v t = E[clip Γ (g t )|F t-1 ] -clip Γ (g t ). We note that E[v t |F t-1 ] = 0 and ∥v t ∥ ≤ ∥clip Γ (g t )∥ -∥E[clip Γ (g t )|F t-1 ]∥ ≤ ∥clip Γ (g t )∥ -E[∥clip Γ (g t )∥|F t-1 ] ≤ 2Γwhere the first step follows from the triangle inequality, the second step uses Jensen's inequality and the last step uses the definition of clip Γ . Hence v t is an F adapted almost surely bounded martingale difference sequence. Now, let D t = ∥x t -x * ∥ where x * is the unique minimizer of F (guaranteed by strong convexity).Let η t = A t+γ where A ≥ 1 is a numerical constant and γ ≥ Aκ + A -1 is a constant depending on κ, d and ln( 1 /δ) which we shall specify later. Note that our choice of γ ensures that η t ≤ 1L+µ for t ∈ [1 : T ] We prove the following recurrence for D t by using the smoothness and strong convexity properties of F and by exploiting the choice of the step-size.Lemma 5 (Recurrence for D t ). The following holds for every t ∈ [1 : T ]D 2 t+1 ≤ γ + 1 t + γ 2A D 2 1 + A2 2A+1 µ t s=1 (s + γ -1) 2A-1 (t + γ) 2A ⟨b s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥b s ∥ 2 (s + γ) 2A-2 (t + γ) 2A + A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A ⟨v s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥v s ∥ 2 (s + γ) 2A-2 (t + γ) 2ANow define R T,δ as follows:R T,δ = (γ + 1) 2 D 2 1 + (T + γ)∥Σ∥ 2 µ 2 d eff + d eff ln( K /δ) It is easy to see that Γ = µ √ R T ,δln( K /δ) . In our proof of Theorem 1, we shall establish that the following holds with probability at least 1 -δ:D 2 t ≤ CR T,δ (t + γ -1) 2 ∀ t ∈ [1 : T + 1]where C > 0 is an absolute numerical constant to be chosen later. To this end, we define the event E t and the random variables d t , bt , ṽt as follows for t ∈ [1 : T + 1]:E t = D 2 t ≤ CR T,δ (t + γ -1) 2 d t = (x t -x * )1 {E t } bt = b t 1 {E t } ṽt = v t 1 {E t } We note that since x t is F t-1 measurable, so are 1 {E t } , D t , d t , b t and bt . Furthermore, E[ṽ t |F t-1 ] = E[v t |F t-1 ]1 {E t } = 0.We use the following Lemma to control the bias vector bt Lemma 6 (Bias Control). The following holds almost surely for every t ∈ [1 : T ]:∥ bt ∥ ≤ µ R T,δ 1 T + γ + κ ln( 1 /δ) √ C (t + γ -1) d(T + γ) + κ 3 C 3 /2 ln( 1 /δ) 2 (t + γ -1) 3 + κ √ C ln( 1 /δ) 2 (t + γ -1)(T + γ)We use the following lemma to control the variance vector ṽt . 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 -δ uniformly for every t ∈ [T ] whenever A ≥ 3 and γ ≥ 4 max{κ 4 /3 C 2 /3 ln( ln(T ) /δ), κ √ C ln( ln(T ) /δ) 3 /2 }:t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨ṽ s , d s ⟩ ≤ 27µR T,δ √ C t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 ≤ C M µ 2 R T,δ 6 + 3 • 2 4A-13 + 3 • 2 4A-17where C M is the absolute numerical constant defined in Corollary 5.Equipped with this bound on the bias and the variance, we now present the complete proof as follows:B.1 Proof of Theorem 1 Proof. Let A ≥ 3, γ ≥ 4 max{κ 4 /3 C 2 /3 ln( ln(T ) /δ), κ √ C ln( ln(T ) /δ) 3 /2 }. Now, let E denote the following event E = { t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨ṽ s , d s ⟩ ≤ 27µR T,δ √ C ∀ t ∈ [T ] t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 ≤ C M µ 2 R T,δ 6 + 3 • 2 4A-13 + 3 • 2 4A-17 ∀t ∈ [T ]}Note that by Lemma 7, P(E) ≥ 1 -δ. We now claim that P T +1 t=1 E t |E = 1, i.e., conditioned on the event E, the following holds almost surely for every t ∈ [1 :T + 1] D 2 t ≤ CR T,δ (t + γ -1) 2 ∀ t ∈ [1 : T + 1]We prove the above claim by induction. Note that the claim is trivially true for t = 1 as R T,δ ≥ (γ + 1) 2 D 2 1 . Now, consider any t ∈ [1 : T ] and suppose the claim holds for some 1 ≤ s ≤ t. Recall that by Lemma 5(t + γ) 2 D 2 t+1 ≤ (γ + 1) 2A (t + γ) 2A-2 D 2 1 + A2 2A+1 µ t s=1 (s + γ -1) 2A-1 (t + γ) 2A-2 ⟨b s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥b s ∥ 2 (s + γ) 2A-2 (t + γ) 2A-2 + A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨v s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥v s ∥ 2 (s + γ) 2A-2 (t + γ) 2A-2Under the induction hypothesis,1 {E s } = 1 ∀s ∈ [t]. Hence, Under the induction hypothesis, 1 D 2 s ≤ CR T ,δ (s+γ-1)(s+γ-2) = 1 and thus, d s = x s -x * , b s = bs , v s = ṽs ∀ 1 ≤ s ≤ t.Substituting this transformation into the above inequality, we obtain the following:EQUATIONWe now bound each of the terms in the RHS as follows.Bounding 1 ⃝ Since A ≥ 1 and t ≥ 1,1 ⃝ = (γ + 1) 2A (t + γ) 2A-2 D 2 1 ≤ (γ + 1) 2 D 2 1 ≤ R T,δBounding 2 ⃝ Since γ and A satisfy the conditions of Lemma 7 and we have conditioned on the event E, it follows that:A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨ṽ s , d s ⟩ ≤ 27A2 2A+1 R T,δ √ CBounding 3 ⃝ Since γ and A satisfy the conditions of Lemma 7 and we have conditioned on the event E, it follows that:A 2 4 A+1 µ 2 t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 ≤ C M 2 2A+2 6 + 3 • 2 4A-13 + 3 • 2 4A-17 R T,δBefore controlling terms 4 ⃝ and 5 ⃝, we note that the following holds for every s ∈ [t] by Lemma 6∥b s ∥ ≤ µ R T,δ (B 1 + B 2 + B 3 + B 4 )where B 1 , . . . , B 4 are defined as:B 1 = 1 T + γ B 2 = κ ln( K /δ) √ C (s + γ -1) d(T + γ) B 3 = κ 3 C 3 /2 ln( K /δ) 2 (s + γ -1) 3 B 4 = κ ln( K /δ) 2 √ C (s + γ -1)(T + γ) Bounding 4 ⃝ Since 1 {E s } = 1 ∥d s ∥ ≤ CR T,δ s + γ -1 ≤ 2 CR T,δ s + γ Hence, A2 2A+1 µ t s=1 bs , d s (s + γ) 2A-1 (t + γ) 2A-2 ≤ A2 2A+2 R T,δ √ C t s=1 s + γ t + γ 2A-2 (B 1 + B 2 + B 3 + B 4 )We now control the first termt s=1 s + γ t + γ 2A-2 B 1 = 1 T + γ t s=1 s + γ t + γ 2A-2 ≤ t T + γ ≤ 1where the first inequality follows from the fact that A ≥ 1 and s ≤ t. We now bound the second termt s=1 s + γ t + γ 2A-2 B 2 ≤ κ √ C ln( K /δ) d(T + γ) t s=1 s + γ t + γ 2A-2 1 s + γ -1Setting A ≥ 3 /2 and using the fact that s + γ ≥ 2, it follows thatt s=1 s + γ t + γ 2A-2 B 2 ≤ 2κ √ C ln( K /δ) d(T + γ) t s=1 (s + γ) 2A-3 (t + γ) 2A-2 ≤ 2κ √ C ln( K /δ) d(T + γ) ≤ 2where the last inequality follows by setting γ ≥ Cκ 2 d • ln( K /δ) 2 To control the third term, we set A ≥ 5 /2 and proceed as follows:t s=1 s + γ t + γ 2A-2 B 3 ≤ κ 3 C 3 /2 ln( K /δ) 2 t s=1 (s + γ) 2A-5 (t + γ) 2A-2 ≤ κ 3 C 3 /2 ln( K /δ) 2 (t + γ) 2 ≤ κ 3 C 3 /2 ln( K /δ) 2 (γ + 1) 2 ≤ 1where the last inequality follows by setting γ ≥ κ 3 /2 C 3 /4 ln( K /δ).To bound the last term,t s=1 s + γ t + γ 2A-2 B 4 ≤ κC 1 /2 ln( K /δ) 2 T + γ t s=1 (s + γ) 2A-3 (t + γ) 2A-2 ≤ κC 1 /2 ln( 1 /δ) 2 γ + 1 ≤ 1where the second inequality uses the fact that A ≥ 3 /2 and the last inequality follows by setting γ ≥ κC 1 /2 ln( K /δ) 2 . Putting it all together, it follows that4 ⃝ ≤ 5A4 A+1 R T,δ √ Cby setting γ as followsγ ≥ max κ 2 C d • ln( K /δ) 2 , κ 3 /2 C 3 /4 ln( 1 /δ), κC 1 /2 ln( K /δ) 2Bounding 5 ⃝ By Lemma 6 and Jensen's inequality∥ bs ∥ 2 ≤ 4µ 2 R T,δ B 2 1 + B 2 2 + B 2 3 + B 2 4It follows thatA 2 2 2A+2 µ 2 t s=1 ∥ bs ∥ 2 s + γ t + γ 2A-2 ≤ A 2 4 A+2 R T,δ t s=1 s + γ t + γ 2A-2 B 2 1 + B 2 2 + B 2 3 + B 2 4The first term is controlled as follows using the fact that A ≥ 1t s=1 s + γ t + γ 2A-2 B 2 1 = t s=1 1 (T + γ) 2 ≤ 1The second term is controlled ast s=1 s + γ t + γ 2A-2 B 2 2 = 4κ 2 C ln( K /δ) 2 d(T + γ) t s=1 (s + γ) 2A-4 (t + γ) 2A-2 ≤ 4κ 2 C ln( K /δ) 2 d(t + γ)(T + γ) ≤ 1where the last inequality follows because γ ≥ κ C d ln( K /δ) For controlling the third term, we set A ≥ 4 to obtaint s=1 s + γ t + γ 2A-2 B 2 3 = κ 6 C 3 ln( K /δ) 4 t s=1 (s + γ) 2A-8 (t + γ) 2A-2 ≤ κ 6 C 3 ln( K /δ) 4 (γ + 1) 5 ≤ 1where the last inequality uses the fact that γ ≥ κ 6 /5 C 3 /5 ln( K /δ) 4 /5 To control the fourth term, we use the fact that A ≥ 2 to obtaint s=1 s + γ t + γ 2A-2 B 2 4 = κ 2 C ln( K /δ) 4 (T + γ) 2 t s=1 (s + γ) 2A-4 (t + γ) 2A-2 ≤ κ 2 C ln( K /δ) 4 (γ + 1) 3 ≤ 1where the last inequality uses the fact that γ ≥ κ 2 /3 C 1 /3 ln( K /δ) 4 /3 From the obtained bounds, we conclude that 5⃝ ≤ A 2 4 A+3 R T,δ .Hence, setting A = 4 and γ = 4C max{ ∥Σ∥2κ 2 ln( ln(T ) /δ) 2, κ 3 /2 ln( ln(T ) /δ), κ ln( ln(T ) /δ) 2 }, we obtain the following(t + γ) 2 D 2 t+1 ≤ 1 ⃝ + 2 ⃝ + 3 ⃝ + 4 ⃝ + 5 ⃝ ≤ R T,δ 1 + C M 2 2A+2 6 + 3 • 2 4A-13 + 3 • 2 4A-17 + A 2 4 A+3 + √ C 27A2 2A+1 + 5A4 A+1 ≤ R T,δ 262145 + 524288C M + 75776 √ C ≤ CR T,δwhere the last inequality is obtained by setting C =√ 262145 + 524288C M + 75776 2 . It follows that D 2 t+1 ≤ CR T,δ (t + γ) 2Thus, we have proved by induction that conditioned on E, D 2 t ≤ CR T ,δ (t+γ) 2 for every t ∈ [T + 1]. In particular, the following holds with probability at least 1 -δ:D 2 T +1 ≤ C γ + 1 T + γ 2 D 2 1 + C∥Σ∥ 2 d eff + √ d eff ln( K /δ) µ 2 (T + γ) ≲ γ + 1 T + γ 2 D 2 1 + Tr(Σ) + ∥Σ∥ 2 Tr(Σ) ln( ln(T ) /δ) µ 2 (T + γ) B.2 Proof of Lemma 5 Let ϵ t = b t + v t D 2 t+1 = ∥Π X (x t -η t ∇F (x t ) + η t ϵ t ) -x * ∥ 2 ≤ ∥x t -η t ∇F (x t ) + η t ϵ t ∥ 2 ≤ D 2 t -2η t ⟨∇F (x t ), x t -x * ⟩ + 2η t ⟨ϵ t , x t -x * ⟩ + 2η 2 t ∥∇F (x t )∥ 2 + 2η 2 t ∥ϵ t ∥ 2By the coercivity lemma in Bubeck [6] ,∥∇F (x t )∥ 2 ≤ (L + µ) ⟨∇F (x t ), x t -x * ⟩ -LµD 2 tIt follows that,D 2 t+1 ≤ (1 -2η 2 t Lµ)D 2 t -2η t [1 -η t (L + µ)] ⟨∇F (x t ), x t -x * ⟩ + 2η t ⟨ϵ t , x t -x * ⟩ + 2η 2 t ∥ϵ t ∥ 2 ≤ (1 -2η 2 t Lµ)D 2 t -2η t [1 -η t (L + µ)]µD 2 t + 2η t ⟨ϵ t , x t -x * ⟩ + 2η 2 t ∥ϵ t ∥ 2 ≤ (1 -2η t µ -2η 2 t µ 2 )D 2 t + 2η t ⟨ϵ t , x t -x * ⟩ + 2η 2 t ∥ϵ t ∥ 2 ≤ (1 -2η t µ)D 2 t + 2η t ⟨ϵ t , x t -x * ⟩ + 2η 2 t ∥ϵ t ∥ 2where the second inequality follows from the strong monotonicity property of ∇F (x) and the fact thatEQUATIONSince 1 -t ≤ e -t ∀ t ∈ R, we note that ∀s < t:t j=s+1 1 - 2A j + γ ≤ exp   - t j=s+1 2A j + γ   ≤ exp -2A t+1 s+1 du u + γ ≤ exp -2A ln t + 1 + γ s + 1 + γ = s + 1 + γ t + 1 + γ 2A ≤ 2 2A s + γ t + γ 2AUsing the above bound to unroll the recurence (7) , we obtain:D 2 t+1 ≤   t j=1 1 - 2A j + γ   D 2 1 + 2A µ t s=1 ⟨ϵ s , x s -x * ⟩ (s + γ)   t j=s+1 1 - 2A j + γ   + 2A 2 µ 2 t s=1 ∥ϵ s ∥ 2 (s + γ) 2   t j=s+1 1 - 2A j + γ   ≤ γ + 1 t + γ 2A D 2 1 + A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A ⟨ϵ s , x s -x * ⟩ + A 2 2 2A+1 µ 2 t s=1 ∥ϵ s ∥ 2 (s + γ) 2A-2 (t + γ) 2AExpanding ϵ s = b s + v s and using Young's inequality, we conclude that the following holds for every t ∈ [1 : T ]D 2 t+1 ≤ γ + 1 t + γ 2A D 2 1 + A2 2A+1 µ t s=1 (s + γ -1) 2A-1 (t + γ) 2A ⟨b s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥b s ∥ 2 (s + γ) 2A-2 (t + γ) 2A + A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A ⟨v s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥v s ∥ 2 (s + γ) 2A-2 (t + γ) 2A B.3 Proof of Lemma 6Note that by definition ofE t ∥∇F (x t )∥1 {E t } ≤ LD t 1 {E t } ≤ L CR T,δ (t + γ -1) Recall that Γ = µ √ R T ,δ ln( K /δ) i.e. R T,δ = γ ln( K /δ) µ. Substituting this into the above inequality gives us:EQUATIONWe recall that bt = ∇F (x t ) -E[clip Γ (g t )|F t-1 ] = E[g t |F t-1 ] -E[clip Γ (g t )|F t-1 ]. Since Cov[g t |F t-1 ] ⪯ Σ by Assumption Bdd.2 nd Moment, we obtain the following bound on ∥b t ∥ by an application of Lemma 4∥b t ∥ ≤ ∥Σ∥ 2 √ d eff Γ + ∥∇F (x t )∥ ∥Σ∥ 2 Γ + ∥∇F (x t )∥ 3 Γ 2 + ∥Σ∥ 2 d eff ∥∇F (x t )∥ Γ 2 Since bt = b t 1 {E t }, it follows that ∥ bt ∥ ≤ ∥Σ∥ 2 √ d eff Γ A ⃝ + ∥∇F (x t )∥1 {E t } ∥Σ∥ 2 Γ B ⃝ + ∥∇F (x t )∥ 3 1 {E t } Γ 2 C ⃝ + ∥Σ∥ 2 d eff ∥∇F (x t )∥1 {E t } Γ 2 D ⃝ Bounding A ⃝ By definition of Γ, ∥Σ∥ 2 √ d eff Γ = ∥Σ∥ 2 √ d eff ln( K /δ) µ R T,δ ≤ (T + γ)∥Σ∥ 2 √ d eff ln( K /δ) µT R T,δ ≤ µ R T,δ (T + γ) Hence A ⃝ ≤ µ √ R T ,δ T +γ Bounding B ⃝ Since R T,δ ≥ ∥Σ∥2d eff (T +γ) µ 2 ≥ ∥Σ∥2T µ 2 , ∥Σ∥ 2 ≤ µ √ R T ,δ √ d(T +γ). Substituting this into equation (8) ,∥∇F (x t )∥1 {E t } ∥Σ∥ 2 Γ ≤ κ √ C ln( K /δ) t + γ -1 • µ R T,δ d(T + γ) Hence, B ⃝ ≤ µ R T,δ • κ ln( 1 /δ) √ C (s+γ) √ d(T +γBounding C ⃝ From equation (8) ,∥∇F (x t )∥ 3 Γ 2 ≤ κ 3 C 3 /2 Γ ln( 1 /δ) 3 (t + γ -1) 3 ≤ µ R T,δ • κ 3 C 3 /2 ln( 1 /δ) 2 (t + γ -1) 3 Hence, C ⃝ ≤ µ R T,δ • κ 3 C 3 /2 ln( 1 /δ) 2(t+γ-1) 3Bounding D ⃝ Recall that,∥Σ∥ 2 d eff ≤ µ 2 R T,δ T + γ ∥∇F (x t )∥1 {E t } Γ ≤ κ ln( K /δ) √ C (t + γ -1) Γ = µ R T,δ ln( K /δ) It follows that D ⃝ = ∥Σ∥ 2 d eff ∥∇F (x t )∥1 {E t } Γ 2 ≤ µ R T,δ • κ ln( K /δ) 2 √ C (t + γ -1)(T + γ) Hence, ∥ bt ∥ ≤ µ R T,δ 1 T + γ + κ ln( 1 /δ) √ C (t + γ -1) d(T + γ) + κ 3 C 3 /2 ln( 1 /δ) 2 (t + γ -1) 3 + κ √ C ln( 1 /δ) 2 (t + γ -1)(T + γ) B.4 Proof of Lemma 7 For any s ∈ [T ], we recall that v s = E [clip Γ (g s )|F s-1 ] -clip Γ (g s ). Since E[g s |F s-1 ] = ∇F (x s )and Cov[g s |F s-1 ] ⪯ Σ, we obtain the following from Lemma 4∥E v s v T s |F s-1 ∥ 2 = ∥Cov [clip Γ (g s )|F s-1 ] ∥ ≤ ∥Σ∥ 2 + ∥∇F (x s )∥ 4 Γ 2 + ∥∇F (x s )∥ 2 Tr(Σ) Γ 2 Tr E v s v T s |F s-1 = Tr (Cov [clip Γ (g s )|F s-1 ]) ≤ Tr(Σ) For s ∈ [1 : T ] define E[ṽ s ṽT s |F s-1 ] = Σs . Since 1 {E s } is F s-1 -measurable and ṽs = v s 1 {E s }, it follows that Σs = E v s v T s |F s 1 {E s }.Hence, we conclude the following from the above inequalityEQUATIONNow, for s ∈ [t], we define h s as follows:EQUATIONFor s∈ [t], define σ 2 s = E[h 2 s |F s-1 ]. It follows that, σ 2 s = (s + γ) 4A-2 (t + γ) 4A-4 v T s Σs v s ≤ (s + γ) 4A-2 (t + γ) 4A-4 ∥v s ∥ 2 ∥ Σs ∥ 2 ≤ 4CR T,δ • s + γ t + γ 4A-4 ∥ Σs ∥ 2 ≤ 4CR T,δ s + γ t + γ 4A-4 ∥Σ∥ 2 + ∥∇F (x s )∥ 4 Γ 2 + ∥∇F (x s )∥ 2 ∥Σ∥ 2 d eff Γ 2where the last inequality follows from equation ( 9) and the fact that d eff = Tr(Σ) /∥Σ∥2. We now use the above inequality to control t s=1 σ 2 s ln( K /δ) as follows:EQUATIONWe now control each of the three terms in the above inequality as follows4CR T,δ ln( K /δ) t s=1 s + γ t + γ 4A-4 ∥Σ∥ 2 ≤ 4CR T,δ ln( K /δ)∥Σ∥ 2 t ≤ 4CtR T,δ • µ 2 R T,δ (T + γ) √ d eff ≤ 4µ 2 CR 2 T,δBefore controlling the remaining two terms, we recall from (8) in the proof of Lemma ?? that∥∇F (x s )∥1 {E s } ≤ κΓ ln( K /δ) √ C s + γ -1 ≤ 2κΓ ln( K /δ) √ C s + γ where Γ = µ √ R T ,δ ln( K /δ) . It follows that ∥∇F (x s )∥ 4 Γ 2 ≤ 16κ 4 C 2 Γ 2 ln( K /δ) 4 (s + γ) 4 = µ 2 R T,δ • 16κ 4 C 2 ln( K /δ) 2 (s + γ) 4Thus, we can control the second term in equation (11) as follows4CR T,δ ln( K /δ) t s=1 s + γ t + γ 4A-4 ∥∇F (x s )∥ 4 Γ 2 ≤ 64µ 2 CR 2 T,δ • κ 4 C 2 ln( K /δ) 3 t s=1 (s + γ) 4A-8 (t + γ) 4A-4 ≤ 64µ 2 CR 2 T,δ • κ 4 C 2 ln( K /δ) 3 (t + γ) 3 ≤ 64µ 2 CR 2 T,δwhere the second inequality follows by setting A ≥ 2 and the last inequality follows by setting γ ≥ κ 4 /3 C 2 /3 ln( K /δ).To control the third term in (11) , we note that by equation ( 8) and the definition of R T,δ∥∇F (x s )∥ 2 ∥Σ∥ 2 d eff Γ 2 ≤ 4µ 2 R T,δ • κ 2 C ln( K /δ) 2 (T + γ)(s + γ) 2 It follows that 4CR T,δ ln( K /δ) t s=1 s + γ t + γ 4A-4 ∥∇F (x s )∥ 2 ∥Σ∥ 2 d eff Γ 2 ≤ 16µ 2 CR 2 T,δ • κ 2 C ln( K /δ) 3 T + γ t s=1 (s + γ) 4A-6 (t + γ) 4A-4 ≤ 16µ 2 CR 2 T,δ • κ 2 C ln( K /δ) 3 (T + γ)(t + γ) ≤ 16µ 2 CR 2 T,δwhere the second inequality follows by setting A ≥ 3 /2 and the last inequality follows by setting γ ≥ κ √ C ln( K /δ) 3 /2 . Substituting the above bounds into equation ( 11), we note thatt s=1 σ 2 s ln( K /δ) ≤ 84µ 2 CR T,δThus, by Freedman's inequality (Lemma 3), we conclude that the following holds with probability at least 1 -δ /2 uniformly for every t ∈ [T ]:EQUATIONTo prove the second inequality of this lemma, we define z s = ṽs• s+γ t+γ A-1 for s ∈ [t]. Note that E[z s |F s-1 ] = 0 and ∥z s ∥ ≤ ∥ṽ s ∥ ≤ 2Γ. Define the PSD matrices G s = E[z s z T s |F s-1 ] = s+γ t+γ2A-2 Σs . Recalling that Tr( Σs ) ≤ Tr(Σ) and the bound obtained on ∥ Σs | 2 in equation ( 9), we infer the following:Tr(G s ) ≤ s + γ t + γ 2A-2Tr(Σ)∥G s ∥ 2 ≤ s + γ t + γ 2A-2 ∥Σ∥ 2 + s + γ t + γ 2A-2 ∥∇F (x s )∥ 4 1 {E s } Γ 2 + s + γ t + γ 2A-2 ∥∇F (x s )∥ 2 Tr(Σ)1 {E s } Γ 2Substituting (8) into the bound for ∥G s ∥ 2 , we obtain the followingTr(G s ) ≤ q s = s + γ t + γ 2A-2Tr(Σ)EQUATIONBy Cauchy Schwarz Inequality,EQUATION)Since T ≳ ln(ln(d)), K = ln(ln(T )) and q s ≤ Tr(Σ) ∀s ∈ [T ], our choice of Γ ensures that the conditions of Corollary 5 are satisfied. Hence, by Corollary 5, we conclude that the following holds with probability 1 -δ /2 uniformly for all t ∈ [T ]EQUATIONUP(t) s=1 p 2 sSimplifying the above using equations ( 13), ( 14) and the definition of Γ, we obtain the following inequality which holds with probability at least 1 -δ /2 uniformly for every t ∈ [T ]:EQUATIONWe now simplify each term in the above inequality by using the fact that UP(t) ≤ min{T, 2t}. To this end, the second term is simplified as follows by using the fact that A ≥ 1UP(t) s=1 s + γ t + γ 4A-4 Tr(Σ) ≤ UP(t)Tr(Σ) ≤ µ 2 R T,δWe now control the third term as follows using the definition of R T,δ and the fact that A ≥ 1:UP(t) s=1 s + γ t + γ 4A-4 t ln( K /δ) 2 ∥Σ∥ 2 µ 2 R T,δ ≤ µ 2 R T,δ • tUP(t) d(T + γ) 2 ≤ µ 2 R T,δTo control the fourth term, we use the fact that A ≥ 3 and note that for s ≤ 2t, (s + γ) ≤ 2(t + γ)UP(t) s=1 (s + γ) 4A-12 (t + γ) 4A-4 • 256tκ 8 C 4 ln( K /δ) 6 µ 2 R T,δ ≤ µ 2 R T,δ 2 8 κ 8 C 4 ln( K /δ) 6 2t s=1 (s + γ) 4A-12 (t + γ) 4A-4 ≤ µ 2 R T,δ • t 2 2 4A-3 κ 8 C 4 ln( K /δ) 6 (t + γ) 8 ≤ µ 2 R T,δ • 2 4A-3 κ 8 C 4 ln( K /δ) 6 (t + γ) 6 ≤ µ 2 R T,δ 2 4A-15where the last inequality follows by setting γ ≥ 4κ 4 /3 C 4 /3 ln( K /δ)We control the last term by a similar argumentUP(t) s=1 (s + γ) 4A-8 (t + γ) 4A-4 16tκ 4 C 2 ln( K /δ) 6 Tr(Σ) 2 µ 2 R T,δ ≤ µ 2 R T,δ • t (T + γ) 2 • 2 4 κ 4 C 2 ln( K /δ) 6 2t s=1 (s + γ) 4A-8 (t + γ) 4A-4 ≤ t 2 (T + γ) 2 (t + γ) 4 • 2 4A-3 κ 4 C 2 ln( K /δ) 6 ≤ 2 4A-11 µ 2 R T,δwhere the last inequality follows by setting γ ≥ 4κ √ C ln( K /δ) 3 /2 . Substituting the obtained bounds into equation (15) , we conclude that the following holds with probability at least 1 -δ /2 uniformly for every t ∈ [T ]:t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 = t s=1 ∥z s ∥ 2 ≤ C M µ 2 R T,δ 6 + 3 • 2 4A-13 + 3 • 2 4A-17The proof is completed via a union bound.Following a convention similar to that of Section B, letK = 4 max{8, C M , ln(T )}. For t ≥ 1, define the filtration F t = σ (x 1 , g s |1 ≤ s ≤ t) and F 0 = σ(x 1 ). Furthermore, let ∇F (x t ) = clip Γ (g t )+b t +v t where b t = ∇F (x t )-E[clip Γ (g t )|F t-1 ] and v t = E[clip Γ (g t )|F t-1 ]-clip Γ (g t ).As D 2 t+1 ≤ γ + 1 t + γ 2A D 2 1 + A2 2A+1 µ t s=1 (s + γ -1) 2A-1 (t + γ) 2A ⟨b s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥b s ∥ 2 (s + γ) 2A-2 (t + γ) 2A + A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A ⟨v s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥v s ∥ 2 (s + γ) 2A-2 (t + γ) 2AWe now define R T,δ as follows:R T,δ = (γ + 1) 2 D 2 1 + (T + γ)β µ 2 d eff + d eff ln( K /δ) It is easy to see that Γ = µ √ R T ,δln( K /δ) . In our proof of Theorem 1, we shall establish that the following holds with probability at least 1 -δ:D 2 t ≤ CR T,δ (t + γ -1) 2 ∀ t ∈ [1 : T + 1]where C > 0 is an absolute numerical constant to be chosen later. To this end, we define the event E t and the F t measurable random variables d t , bt , ṽt as follows for t ∈ [1 : T + 1]:E t = D 2 t ≤ CR T,δ (t + γ -1) 2 d t = (x t -x * )1 {E t } bt = b t 1 {E t } ṽt = v t 1 {E t }We use the following Lemma to control the bias vector bt Lemma 8 (Bias Control). The following holds almost surely for every t ∈ [1 : T ]:∥ bt ∥ ≤ µ R T,δ 7 j=1 B jwhere B 1 , . . . , B 7 are defined as follows:B 1 = 1 T + γ , B 2 = 4αC √ d ln( ln(T ) /δ) µ 2 (s + γ) 2 , B 3 = 2κ √ C ln( ln(T ) /δ) (s + γ) d(T + γ) , B 4 = 4κC ln( ln(T ) /δ) √ α µ(s + γ) 2 , B 5 = 8κ 3 C 3 /2 ln( ln(T ) /δ) 2 (s + γ) 3 , B 6 = 2κ √ C ln( ln(T ) /δ) 2 (s + γ)(T + γ) , B 7 = 8ακd ln( ln(T ) /δ) 2 C 3 /2 µ 2 (s + γ) 3We use the following lemma to control the variance vector ṽt . The proof of this lemma, which uses Freedman's inequality and the PAC Bayesian martingale concentration inequality of Corollary 6.Lemma 9 (Variance Control). The following holds with probability at least 1 -δ uniformly for everyt ∈ [T ] for A ≥ 3 and γ ≥ 4C max{ αd eff µ 2 , α ln( K /δ) µ 2 , κ 4 /3 ln( K /δ), κ ln( K /δ) 3 /2 , κ 2 /3 d 1 /3 eff α 1 /3 µ 2 /3 ln( K /δ)} t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨ṽ s , d s ⟩ ≲ 34 • µR T,δ √ C t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 ≲ C M 2 4A-3 25 4 + 5 • 2 4A-11 + 5 • 2 4A-16 + 5 • 2 4A-13 µ 2 R T,δwhere C M is the absolute numerical constant defined in Corollary 5.Equipped with this bound on the bias and the variance, we now present the complete proof as follows:C.1 Proof of Theorem 2 Proof. Let A ≥ 3, γ ≥ 4C max{ αd eff µ 2 , α ln( K /δ) µ 2 , κ 4 /3 ln( K /δ), κ ln( K /δ) 3 /2 , κ 2 /3 d 1 /3 eff α 1 /3 µ 2 /3 ln( K /δ)}. Now, let E denote the following event E = { t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨ṽ s , d s ⟩ ≤ 34 • µR T,δ √ C ∀ t ∈ [T ] t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 ≤ 53 • C M µ 2 R T,δ ∀t ∈ [T ]}Note that by Lemma 9, P(E) ≥ 1 -δ. We now claim that P T +1 t=1 E t |E = 1, i.e., conditioned on the event E, the following holds almost surely for every t ∈ [1 : T + 1]D 2 t ≤ CR T,δ (t + γ -1) 2 ∀ t ∈ [1 : T + 1]We prove the above claim by induction. Note that the claim is trivially true for t = 1 as R T,δ ≥ (γ + 1) 2 D 2 1 . Now, consider any t ∈ [1 : T ] and suppose the claim holds for some 1 ≤ s ≤ t.Recall that by Lemma 5(t + γ) 2 D 2 t+1 ≤ (γ + 1) 2A (t + γ) 2A-2 D 2 1 + A2 2A+1 µ t s=1 (s + γ -1) 2A-1 (t + γ) 2A-2 ⟨b s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥b s ∥ 2 (s + γ) 2A-2 (t + γ) 2A-2 + A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨v s , x s -x * ⟩ + A 2 4 A+1 µ 2 t s=1 ∥v s ∥ 2 (s + γ) 2A-2 (t + γ) 2A-2Under the induction hypothesis,1 {E s } = 1 ∀s ∈ [t].Hence, Under the induction hypothesis,1 D 2 s ≤ CR T ,δ (s+γ-1)(s+γ-2) = 1 and thus, d s = x s -x * , b s = bs , v s = ṽs ∀ 1 ≤ s ≤ t.Substituting this transformation into the above inequality, we obtain the following:EQUATIONWe now bound each of the terms in the RHS as follows.Bounding 1 ⃝ Since A ≥ 1 and t ≥ 1,1 ⃝ = (γ + 1) 2A (t + γ) 2A-2 D 2 1 ≤ (γ + 1) 2 D 2 1 ≤ R T,δBounding 2 ⃝ Since γ and A satisfy the conditions of Lemma 7 and we have conditioned on the event E, it follows that:A2 2A+1 µ t s=1 (s + γ) 2A-1 (t + γ) 2A-2 ⟨ṽ s , d s ⟩ ≤ 17A4 A+1 R T,δ √ CBounding 3 ⃝ Since γ and A satisfy the conditions of Lemma 7 and we have conditioned on the event E, it follows that:A 2 4 A+1 µ 2 t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 ≤ A 2 2 2A+2 C M 2 4A-3 25 4 + 5 • 2 4A-11 + 5 • 2 4A-16 + 5 • 2 4A-13 R T,δ Bounding 4 ⃝ Since 1 {E s } = 1 ∥d s ∥ ≤ CR T,δ s + γ -1 ≤ 2 CR T,δ s + γHence, by Lemma 8A2 2A+1 µ t s=1 bs , d s (s + γ) 2A-1 (t + γ) 2A-2 ≤ A2 2A+2 R T,δ √ C t s=1 s + γ t + γ 2A-2 7 j=1 B jWe now control the first termt s=1 s + γ t + γ 2A-2 B 1 = 1 T + γ t s=1 s + γ t + γ 2A-2 ≤ t T + γ ≤ 1where the first inequality follows from the fact that A ≥ 1 and s ≤ t.We now control the second termt s=1 s + γ t + γ 2A-2 B 2 ≤ 4αC √ d ln( K /δ) µ 2 t s=1 (s + γ) 2A-4 (t + γ) 2A-2 ≤ 4αC √ d ln( K /δ) µ 2 (t + γ) ≤ 1where the first inequality follows from the fact that A ≥ 2 and s ≤ t and the second inequality follows by setting γ ≥ 4αC√ d ln( K /δ) µ 2.We now bound the third term as follows:t s=1 s + γ t + γ 2A-2 B 3 ≤ 2κ √ C ln( K /δ) d(T + γ) t s=1 (s + γ) 2A-3 (t + γ) 2A-2 ≤ 2κ √ C ln( K /δ) d(T + γ) ≤ 1where we use the fact that A ≥ 2 and set γ ≥ 4κ 2 ln( K /δ) 2.We now bound the fourth term as follows:t s=1 s + γ t + γ 2A-2 B 4 ≤ 4κC ln( K /δ) √ α µ t s=1 (s + γ) 2A-4 (t + γ) 2A-2 ≤ 4κC ln( K /δ) √ α µ(t + γ) ≤ 1where A ≥ 2 and γ ≥ 4κC ln( K /δ)We now bound the fifth term as followst s=1 s + γ t + γ 2 B 5 ≤ 8κ 3 C 3 /2 ln( K /δ) 2 t s=1 (s + γ) 2A-5 (t + γ) [ 2A -2] ≤ 8κ 3 C 3 /2 ln( K /δ) 2 (t + γ) 2 ≤ 1where A ≥ 3 and γ ≥ 4κ 3 /2 C 3 /4 ln( K /δ).We now bound the sixth term as followst s=1 s + γ t + γ 2A-2 B 6 ≤ 2κ √ C ln( K /δ) 2 T + γ t s=1 (s + γ) 2A-3 (t + γ) 2A-2 ≤ 2κ √ C ln( K /δ) 2 T + γ ≤ 1where A ≥ 3 and γ ≥ 2κ√ C ln( K /δ) 2Finally, we control the seventh term as followst s=1 s + γ t + γ 2A-2 B 7 ≤ 8ακd ln( K /δ) 2 C 3 /2 µ 2 t s=1 (s + γ) 2A-5 (t + γ) 2A-2 ≤ 8ακd ln( K /δ) 2 C 3 /2 µ 2 (t + γ) 2 ≤ 1where A ≥ 3 and γ ≥ 4√ ακd ln( K /δ)C 3 /4 µ. Putting it all together, it follows that4 ⃝ ≤ 7A4 A+1 R T,δ √ Cby setting γ as followsγ ≥ 4C max α √ d ln( K /δ) µ 2 , κ 2 ln( K /δ) 2 d , κ √ α ln( K /δ) µ , κ 3 /2 ln( K /δ), κ ln( K /δ) 2 , √ καd ln( K /δ) µBounding 5 ⃝ By Lemma 8 and Jensen's inequality∥ bs ∥ 2 ≤ 7µ 2 R T,δ 7 j=1 B 2 j It follows that A 2 2 2A+2 µ 2 t s=1 ∥ bs ∥ 2 s + γ t + γ 2A-2 ≤ 7A 2 2 2A+2 R T,δ t s=1 s + γ t + γ 2A-2 7 j=1 B 2 jThe first term is controlled as follows using the fact that A ≥ 1t s=1 s + γ t + γ 2A-2 B 2 1 = t s=1 1 (T + γ) 2 ≤ 1The second term is controlled ast s=1 s + γ t + γ 2A-2 B 2 2 ≤ 16α 2 C 2 d ln( K /δ) 2 µ 4 t s=1 (s + γ) 2A-6 (t + γ) 2A-2 ≤ 16α 2 C 2 d ln( K /δ) 2 µ 4 (t + γ) 3 ≤ 1 where A ≥ 3 and γ ≥ 2 4 /3 α 2 /3 C 2 /3 d 1 /3 ln( K /δ) 2 /3 µ 4 /3.The third term is controlled ast s=1 s + γ t + γ 2A-2 B 2 3 = 4κ 2 C ln( K /δ) 2 d(T + γ) t s=1 (s + γ) 2A-4 (t + γ) 2A-2 ≤ 4κ 2 C ln( K /δ) 2 d(t + γ)(T + γ) ≤ 1where the last inequality follows because γ ≥ κ C d ln( K /δ) The fourth term is controlled ast s=1 s + γ t + γ 2A-2 B 2 4 ≤ 16κ 2 C 2 ln( K /δ) 2 α µ 2 t s=1 (s + γ) 2A-6 (t + γ) 2A-2where A ≥ 3 and γ≥ 2 4 /3 κ 2 /3 C 2 /3 ln( K /δ) 2 /3 α 1 /3 µ 2 /3For controlling the fifth term, we set A ≥ 4 to obtaint s=1 s + γ t + γ 2A-2 B 2 5 = κ 6 C 3 ln( K /δ) 4 t s=1 (s + γ) 2A-8 (t + γ) 2A-2 ≤ κ 6 C 3 ln( K /δ) 4 (γ + 1) 5 ≤ 1where the last inequality uses the fact that γ ≥ κ 6 /5 C 3 /5 ln( K /δ) 4 /5To control the sixth term, we use the fact that A ≥ 2 to obtaint s=1 s + γ t + γ 2A-2 B 2 6 = κ 2 C ln( K /δ) 4 (T + γ) 2 t s=1 (s + γ) 2A-4 (t + γ) 2A-2 ≤ κ 2 C ln( K /δ) 4 (γ + 1) 3 ≤ 1where the last inequality uses the fact that γ ≥ κ 2 /3 C 1 /3 ln( K /δ) 4 /3To control the seventh term, we set A ≥ 4 to obtain the following:t s=1 s + γ t + γ 2A-2 B 2 6 = 64α 2 κ 2 d ln( K /δ) 4 C 3 µ 4 t s=1 (s + γ) 2A-8 (t + γ) 2A-2 ≤ 64α 2 κ 2 d ln( K /δ) 4 C 3 µ 4 (t + γ) 5 ≤ 1 where γ ≥ 2 6 /5 α 2 /5 κ 2 /5 d 1 /5 ln( K /δ) 4 /5 C 3 /5 µ 4 /5From the obtained bounds, we conclude that 5 ⃝ ≤49A 2 4 A+1 R T,δ .Now, we set A = 4 and γ as follows:γ = max αd µ 2 , α √ d ln( K /δ) µ 2 , κ √ α ln( K /δ) µ 2 , √ καd ln( K /δ) µ , κ 2 /3 d 1 /3 α 1 /3 ln( K /δ) µ 2 /3 , κ 3 /2 ln( K /δ), κ ln( K /δ) 2 , κ 2 ln( K /δ) dUnder this setting of A and γ, we obtain the following(t + γ) 2 D 2 t+1 ≤ 1 ⃝ + 2 ⃝ + 3 ⃝ + 4 ⃝ + 5 ⃝ ≤ R T,δ [1 + A 2 2 2A+2 C M 2 4A-3 25 4 + 5 • 2 4A-11 + 5 • 2 4A-16 + 5 • 2 4A-13 + 49A 2 4 A+1 + 24A4 A+1 √ C] ≤ R T,δ 802817 + 6946816C M + 98304 √ C ≤ CR T,δwhere the second inequality holds due to our choice of A and γ and the last inequality is obtained by setting C = √ 802817 + 6946816C M + 98304 2 . It follows thatD 2 t+1 ≤ CR T,δ (t + γ) 2Thus, we have proved by induction that conditioned on E, D 2 t ≤ CR T ,δ (t+γ-1) 2 for every t ∈ [T + 1]. In particular, the following holds with probability at least 1 -δ:D 2 T +1 ≤ C γ + 1 T + γ 2 D 2 1 + Cβ d eff + √ d eff ln( K /δ) µ 2 (T + γ)Following the same steps as in that of the proof of Lemma 6, we use Lemma 4 and the fact that Cov[g t |F t-1 ] = Σ t to obtain:∥ bs ∥ ≤ ∥Σ s ∥ √ d eff 1 {E s } Γ A ⃝ + ∥∇F (x s )∥ ∥Σ s ∥1 {E s } Γ B ⃝ + ∥∇F (x s )∥ 3 1 {E s } Γ 2 C ⃝ + ∥Σ s ∥d eff ∥∇F (x s )∥1 {E s } Γ 2 D ⃝ Bounding A ⃝ Note that by Assumption QG 2 nd Moment ∥Σ s ∥ 2 1 {E s } ≤ (β + αD 2 s )1 {E s } ≤ β + 4αCR T,δ (s + γ) 2It follows that∥Σ s ∥ 2 √ d1 {E s } Γ ≤ β √ d eff ln( K /δ) µ R T,δ + 4αC ln( K /δ) R T,δ d eff µ(s + γ) 2 Since β √ d eff ln( K /δ) ≤ µ 2 R T ,δT +γ , we obtainA ⃝ = ∥Σ∥ s √ d1 {E s } Γ ≤ µ R T,δ 1 T + γ + 4αC ln( K /δ) R T,δ d eff µ 2 (s + γ) 2Bounding B ⃝ Note that by equation (8) ,∥∇F (x s )∥1 {E s } Γ ≤ 2κ √ C ln( K /δ) s + γFurthermore, by Assumption QG 2 nd Moment and the definition ofE s ∥Σ s ∥ 2 1 {E s } ≤ β + 2 αCR T,δ s + γ Recalling that β ≤ µ 2 R T ,δ d eff (T +γ) , ∥∇F (x s )∥ ∥Σ s ∥ 2 1 {E s } Γ ≤ 2κ √ C ln( K /δ)µ R T,δ (s + γ) d eff (T + γ) + 4κC ln( K /δ) αR T,δ (s + γ) 2 ≤ µ R T,δ 2κ √ C ln( K /δ) (s + γ) d eff (T + γ) + 4κC ln( K /δ) √ α µ(s + γ) 2⃝ By equation (8) ,∥∇F (x s )∥ 3 1 {E s } Γ 2 ≤ µ R T,δ • 8κ 3 C 3 /2 ln( K /δ) 2 (s + γ) 3 Bounding D ⃝ Since βd ≤ µ 2 R T ,δT +γ , it follows tat∥∇F (x s )∥∥Σ s ∥ 2 d eff 1 {E s } Γ 2 ≤ 2κ √ C ln( K /δ) 2 µ R T,δ (s + γ) βd + 4αCR T,δ d (s + γ) 2 ≤ 2κ √ C ln( K /δ) 2 µ R T,δ (s + γ)(T + γ) + 8ακd ln( K /δ) 2 C 3 /2 R T,δ µ(s + γ) 3 ≤ µ R T,δ 2κ √ C ln( K /δ) 2 (s + γ)(T + γ) + 8ακd ln( K /δ) 2 C 3 /2 µ 2 (s + γ) 3Hence, we conclude that∥ bt ∥ ≤ A ⃝ + B ⃝ + C ⃝ + D ⃝ ≤ µ R T,δ 7 j=1 B jwhere B 1 , . . . , B 7 are defined as follows:B 1 = 1 T + γ , B 2 = 4αC √ d ln( ln(T ) /δ) µ 2 (s + γ) 2 , B 3 = 2κ √ C ln( ln(T ) /δ) (s + γ) d(T + γ) , B 4 = 4κC ln( ln(T ) /δ) √ α µ(s + γ) 2 , B 5 = 8κ 3 C 3 /2 ln( ln(T ) /δ) 2 (s + γ) 3 , B 6 = 2κ √ C ln( ln(T ) /δ) 2 (s + γ)(T + γ) , B 7 = 8ακd ln( ln(T ) /δ) 2 C 3 /2 µ 2 (s + γ) 3As before, for s ∈ [1 : T ] define E[ṽ s ṽT s |F s-1 ] = Σs . Following the same steps as in that of the proof of Lemma 7, we use Lemma 4 and the fact that Cov[g t |F t-1 ] = Σ t to obtain:EQUATIONwhere the second inequality follows from Assumption QG 2 nd Moment and the second inequality follows by definition of E s Furthermore, since clip Γ is a convex projection, the following holds:EQUATIONNow, for s ∈ [t], we define h s as follows:h s = ⟨ṽ s , d s ⟩ (s + γ) 2A-1 (t + γ) 2A-2Note that E[h s |F s-1 ] = 0. Furthermore, since ∥ṽ s ∥ ≤ 2Γ and ∥d s ∥ ≤√ CR T ,δ s+γ-1 |h s | ≤ 2Γ • CR T,δ s + γ -1 • (s + γ) 2A-1 (t + γ) 2A-2 ≤ 4Γ CR T,δ s + γ t + γ 2A-2 ≤ 4µR T,δ √ C ln( K /δ) (19) For s ∈ [t], define σ 2 s = E[h 2 s |F s-1 ]. It follows that, σ 2 s = (s + γ) 4A-2 (t + γ) 4A-4 v T s Σs v s ≤ (s + γ) 4A-2 (t + γ) 4A-4 ∥v s ∥ 2 ∥ Σs ∥ 2 ≤ 4CR T,δ • s + γ t + γ 4A-4 ∥ Σs ∥ 2 ≤ 4CR T,δ s + γ t + γ 4A-4 β + 4αCR T,δ (s + γ) 2 + ∥∇F (x s )∥ 4 1 {E s } Γ 2 + ∥∇F (x t )∥ 2 d eff 1 {E s } Γ 2 β + 4αCR T,δ (s + γ) 2where the last inequality follows from equation ( 9) and the fact that d eff = Tr(Σ) /∥Σ∥2. We now use the above inequality to control t s=1 σ 2 s ln( K /δ) as follows:EQUATIONWe now control each of the five terms in the above inequality as follows4CR T,δ ln( K /δ) t s=1 s + γ t + γ 4A-4 β ≤ 4CR T,δ ln( K /δ)βt ≤ 4CtR T,δ • µ 2 R T,δ (T + γ) √ d eff ≤ 4µ 2 CR 2 T,δTo control the second term,4CR T,δ ln( K /δ) t s=1 (s + γ) 4A-6 (t + γ) 4A-4 4αCR T,δ ≤ 16CR 2 T,δ µ 2 αC ln( K /δ) µ 2 (t + γ) ≤ 16CR 2T,δ µ 2 where the second inequality follows by setting A ≥ 3 /2 and the last inequality follows by setting γ ≥ αC ln( K /δ) µ 2Before controlling the remaining terms, we recall from (8) in the proof of Lemma 6 that∥∇F (x s )∥1 {E s } ≤ κΓ ln( K /δ) √ C s + γ -1 ≤ 2κΓ ln( K /δ) √ C s + γ where Γ = µ √ R T ,δ ln( K /δ) . It follows that ∥∇F (x s )∥ 4 1 {E s } Γ 2 ≤ 16κ 4 C 2 Γ 2 ln( K /δ) 4 (s + γ) 4 = µ 2 R T,δ • 16κ 4 C 2 ln( K /δ) 2 (s + γ) 4Thus, we can control the third term in equation ( 20) as follows4CR T,δ ln( K /δ) t s=1 s + γ t + γ 4A-4 ∥∇F (x s )∥ 4 1 {E s } Γ 2 ≤ 64µ 2 CR 2 T,δ • κ 4 C 2 ln( K /δ) 3 t s=1 (s + γ) 4A-8 (t + γ) 4A-4 ≤ 64µ 2 CR 2 T,δ • κ 4 C 2 ln( K /δ) 3 (t + γ) 3 ≤ 64µ 2 CR 2 T,δwhere the second inequality follows by setting A ≥ 2 and the last inequality follows by setting γ ≥ κ 4 /3 C 2 /3 ln( K /δ).To control the fourth term in (20) , we note that by equation ( 8) and the definition of R T,δ∥∇F (x s )∥ 2 d eff β1 {E s } Γ 2 ≤ 4µ 2 R T,δ • κ 2 C ln( K /δ) 2 (T + γ)(s + γ) 2It follows that4CR T,δ ln( K /δ) t s=1 s + γ t + γ 4A-4 ∥∇F (x s )∥ 2 βd eff Γ 2 ≤ 16µ 2 CR 2 T,δ • κ 2 C ln( K /δ) 3 T + γ t s=1 (s + γ) 4A-6 (t + γ) 4A-4 ≤ 16µ 2 CR 2 T,δ • κ 2 C ln( K /δ) 3 (T + γ)(t + γ) ≤ 16µ 2 CR 2 T,δwhere the second inequality follows by setting A ≥ 3 /2 and the last inequality follows by settingγ ≥ κ √ C ln( K /δ) 3 /2 .To control the fifth term in equation ( 20), we proceed as follows:4CR T,δ ln( K /δ) t s=1 (s + γ) 4A-6 (t + γ) 4A-4 4∥∇F (x s )∥ 2 1 {E s } αdCR T,δ Γ 2 ≤ 64µ 2 CR 2 T,δ αdκ 2 C 2 ln( K /δ) 3 µ 2 t s=1 (s + γ) 4A-8 (t + γ) 4A-4 ≤ 64µ 2 CR 2 T,δ • αdκ 2 C 2 ln( K /δ) 3 µ 2 (t + γ) 3 ≤ 64µ 2 CR 2 T,δwhere the second inequality follows by setting A ≥ 2 and the last inequality follows by setting γ ≥α 1 /3 d 1 /3 eff κ 2 /3 C 2 /3 ln( K /δ) µ 2 /3Substituting the above bounds into equation ( 20), we note thatt s=1 σ 2 s ln( K /δ) ≤ 164µ 2 CR T,δThus, by Freedman's inequality (Lemma 3), we conclude that the following holds with probability at least 1 -δ /2 uniformly for every t ∈ [T ]:EQUATIONTo prove the second inequality of this lemma, we define z s = ṽs• s+γ t+γ A-1 for s ∈ [t]. Note that E[z s |F s-1 ] = 0 and ∥z s ∥ ≤ ∥ṽ s ∥ ≤ 2Γ. Define the PSD matrices G s = E[z s z T s |F s-1 ] = s+γ t+γ2A-2 Σs . Recalling the bounds obtained on ∥ Σs ∥ 2 and Tr( Σs ) in equations ( 17) and ( 18), we infer the following:Tr(G s ) ≤ s + γ t + γ 2A-2 Tr(Σ s )1 {E s } ≤ s + γ t + γ 2A-2 βd eff + (s + γ) 2A-4 (t + γ) 2A-2 4αd eff CR T,δ ∥G s ∥ 2 = s + γ t + γ 2A-2 ∥ Σs ∥ 2 ≤ s + γ t + γ 2A-2 β + (s + γ) 2A-4 (t + γ) 2A-2 4αCR T,δ + s + γ t + γ 2A-2 ∥∇F (x s )∥ 4 1 {E s } Γ 2 + s + γ t + γ 2A-2 ∥∇F (x s )∥ 2 1 {E s } βd eff Γ 2 + (s + γ) 2A-4 (t + γ) 2A-2 ∥∇F (x s )∥ 2 1 {E s } 4αd eff CR T,δ Γ 2Substituting equation ( 8) into the bound for ∥G s ∥ 2 , we obtain the followingTr(G s ) ≤ q s = s + γ t + γ 2A-2 βd eff + (s + γ) 2A-4 (t + γ) 2A-2 4αd eff CR T,δ ∥G s ∥ 2 ≤ p s = s + γ t + γ 2A-2 β + (s + γ) 2A-4 (t + γ) 2A-2 • 4αCR T,δ + (s + γ) 2A-6 (t + γ) 2A-2 • 16κ 4 C 2 ln( K /δ) 2 µ 2 R T,δ ≤ (s + γ) 2A-4 (t + γ) 2A-2 • 4βd eff κ 2 C ln( K /δ) 2 + (s + γ) 2A-6 (t + γ) 2A-2 • 16αd eff R T,δ κ 2 C 2 ln( K /δ) 2 (22)By Cauchy Schwarz inequality,EQUATIONSince T ≳ ln(ln(d)), K = ln(ln(T )), our choice of Γ and the definition of R T,δ ensures that the conditions of Corollary 5 are satisfied. Hence, by Corollary 5, we conclude that the following holds with probability 1 -δ /2 uniformly for all t ∈ [T ]t s=1 ∥z s ∥ 2 ≤ 4C M Γ 2 ln( K /δ) 2 + C M UP(t) s=1 Q s + C M t 4Γ 2 t s=1 P 2 sSimplyfing the above using equations ( 22), ( 23) and the definition of Γ, we obtain the following:EQUATIONWe now simplify each term in the above inequality by using the fact that UP(t) ≤ min{T, 2t}. To this end, the second term is simplified as follows by using A ≥ 1UP(t) s=1 s + γ t + γ 4A-4 βd eff ≤ UP(t)βd eff ≤ µ 2 R T,δWe now control the third term by noting that for s ≤ 2t, s + γ ≤ 2t + γ ≤ 2(t + γ):t s=1 (s + γ) 2A-4 (t + γ) 2A-2 • 4αd eff CR T,δ ≤ µ 2 R T,δ • 2 2A-2 αd eff µ 2 2t s=1 1 (t + γ) 2 ≤ 2 2A-1 µ 2 R T,δ • αdt µ 2 (t + γ) 2 ≤ 2 2A-3 µ 2 R T,δwhere the last inquality follows by setting γ ≥ 4αCd eff µ 2 . We now control the fourth term as follows:UP(t) s=1 s + γ t + γ 4A-4 β 2 t ln( K /δ) 2 µ 2 R T,δ ≤ µ 2 R T,δ • UP(t) d(T + γ) 2 ≤ µ 2 R T,δWe now control the fifth term as follows:16α 2 C 2 R T,δ t ln( K /δ) 2 µ 2 UP(t) s=1 (s + γ) 4A-8 (t + γ) 4A-4 ≤ µ 2 R T,δ • 2 4A-4 α 2 C 2 ln( K /δ) 2 t µ 4 2t s=1 1 (t + γ) 4 ≤ µ 2 R T,δ • α 2 C 2 ln( K /δ) 2 2 4A-5 µ 4 (t + γ) 2 ≤ 2 4A-9 µ 2 R T,δwhere the last inequality usesγ ≥ 4αC ln( K /δ) µ 2We now simplify the sixth term as follows:UP(t) s=1 (s + γ) 4A-12 (t + γ) 4A-4 • 256µ 2 R T,δ κ 8 C 4 ln( K /δ) 6 t ≤ µ 2 R T,δ t • 2 4A-4 κ 8 C 4 ln( K /δ) 6 2t s=1 1 (t + γ) 8 ≤ µ 2 R T,δ (t + γ) 6 • 2 4A-3 κ 8 C 4 ln( K /δ) 6 ≤ 2 4A-15 µ 2 R T,δwhere the last inequality follows by setting γ ≥ 4κ 4 /3 C 2 /3 ln( K /δ).We control the seventh term as follows:UP(t) s=1 (s + γ) 4A-8 (t + γ) 4A-4 • β 2 d 2 eff t µ 2 R T,δ • 16κ 4 C 2 ln( K /δ) 6 ≤ µ 2 R T,δ • 2 4 κ 4 C 2 ln( K /δ) 6 t (T + γ) 2 2t s=1 (s + γ) 4A-8 (t + γ) 4A-4 ≤ µ 2 R T,δ • 2 4A-3 κ 4 C 2 ln( K /δ) 6 (t + γ) 4 ≤ 2 4A-11 µ 2 R T,δwhere γ ≥ 4κ√ C ln( K /δ) 3 /2 .We use a similar argument to simplify the final term as follows:UP(t) s=1 t(s + γ) 4A-12 (t + γ) 4A-4 • 2 8 α 2 d 2 eff R T,δ κ 4 C 4 ln( K /δ) 6 µ 2 ≤ µ 2 R T,δ • 2 4A-3 α 2 d 2 eff κ 4 C 4 ln( K /δ) 6 µ 4 (t + γ) 6 ≤ 2 4A-15 µ 2 R T,δ where γ ≥ 4κ 2 /3 d 1 /3 eff C 2 /3 ln( K /δ) µ 2 /3. We now set A ≥ 3 and γ as follows:γ ≥ 4C max{ αd eff µ 2 , α ln( K /δ) µ 2 , κ 4 /3 ln( K /δ), κ ln( K /δ) 3 /2 , κ 2 /3 d 1 /3 eff α 1 /3 µ 2 /3 ln( K /δ)}Under these parameter settings, we substitute the obtained bounds into equation ( 15), we conclude that the following holds with probability at least 1 -δ /2 uniformly for every t ∈ [T ]:t s=1 s + γ t + γ 2A-2 ∥ṽ s ∥ 2 = t s=1 ∥z s ∥ 2 ≤ C M µ 2 R T,δ 2 4A-3 25 4 + 5 • 2 4A-11 + 5 • 2 4A-16 + 5 • 2 4A-13The proof is completed via a union bound.Let d eff = Tr(Σ) ∥Σ∥2 . Following a convention similar to that of Section B, letK = 4 max{8, C M , ln(T )}. For t ≥ 1, define the filtration F t = σ (x 1 , g s |1 ≤ s ≤ t) and F 0 = σ(x 1 ). Furthermore, let ∇F (x t ) = clip Γ (g t ) + b t + v t where b t = ∇F (x t ) -E[clip Γ (g t )|F t-1 ] and v t = E[clip Γ (g t )|F t-1 ] -clip Γ (g t ).As beforem, we note that E[v t |F t-1 ] = 0 and ∥v t ∥ ≤ 2Γ. Hence v t is an F adapted almost surely bounded martingale difference sequence. Now, let D t = ∥x t -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 10 (Intermediate Average Iterate Guarantee). The following holds for η≤ 1 /2L F (x T ) -F (x * ) ≤ D 2 1 2ηT + 1 T T t=1 ⟨b t , x t -x * ⟩ + 1 T T t=1 ⟨v t , x t -x * ⟩ + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2Define the events E t and the random vectors d t , bt and ṽt as follows for t ∈ [T ]:E t = {D t ≤ 2D 1 } d t = (x t -x * )1 {E t } bt = b t 1 {E t } ṽt = v t 1 {E t }We use the following lemma to control the bias Lemma 11 (Bias Control). For every t ∈ [T ], ∥ bt ∥ ≤ B where B is defined as follows:B = ∥Σ∥ 2 √ d eff Γ + 2LD 1 ∥Σ∥ 2 Γ + 8L 3 D 3 1 Γ 2 + 2∥Σ∥ 2 d eff LD 1 Γ 2We use the following lemma to control the varince Lemma 12 (Variance Control). Let V ≥ 0 be defined as follows:V = ∥Σ∥ 2 + 16L 4 D 4 1 Γ 2 + 4L 2 D 2 1 ∥Σ∥ 2 d eff Γ 2Then the following holds with probability at least 1 -δ uniformly for every t ∈ [T ]t s=1 ⟨ṽ t , d t ⟩ ≤ 4D 1 V t ln( K /δ) + 8ΓD 1 ln( K /δ) t s=1 ∥ṽ t ∥ 2 ≤ C M g 2 Twhere C M is a numerical constant and g 2 is defined as followsg 2 = ∥Σ∥ 2 d eff + 4Γ 2 ln( K /δ) 2 T + V 2 T 4Γ 2Let E denote the following eventE = { t s=1 ⟨ṽ s , d s ⟩ ≤ 4D 1 V t ln( K /δ) + 8ΓD 1 ln( K /δ) ∀ t ∈ [T ] t s=1 ∥ṽ s ∥ 2 ≤ C M g 2 T ∀t ∈ [T ]}We define the constant A as follows:A = ∥Σ∥ 2 d eff + LD 1 ∥Σ∥ 2 = ∥Σ∥ 2 Tr(Σ) + LD 1We now set the clipping level Γ = AT ln( K /δ) . For this choice of Γ, we now obtain the following bound on B:EQUATIONSimilarly, we bound the value of V as follows:EQUATIONEquipped with the above inequality, we then bound the value of g as:EQUATIONWe prove the following lemma to control the growth of the iterates D t .Lemma 13 (Iterate Bound).Let η ≤ c min{ 1 /2L, D1 /B ′ T , D1 /g ′ √ T } where c = 1 √ 8C M +330 . Then, conditioned on the event E, D t ≤ 2D 1 ∀t ∈ [T ].Equipped with the above lemmas, we now present a proof of the following theorem, which is a formal restatement of Theorem 3 Theorem 7 (Smooth Convex Objectives). Let Convexity, L-smoothness and Bdd. 2 nd Moment be satisfied. Then, for any δ ∈ (0, 1 /2) and T ≥ ln(ln(d)), there exists an η ∈ (0, 1 /2L] such that the average iterate of Algorithm 1 run for T iterations with step-size η t = η and clipping levelΓ = T √ ∥Σ∥2( √ Tr(Σ)+LD1) ln( ln(T ) /δ)satisfies the following with probability at least 1 -δ :F (x T ) -F (x * ) ≲ D 1 Tr(Σ) + ∥Σ∥ 2 Tr(Σ) + LD 1 ln( ln(T ) /δ) T + LD 2 1 T + LD 2 1 ln( ln(T ) /δ) T Tr(Σ) + L 2 D 2 1 ∥Σ∥ 2 + L 2 D 3 1 ln( ln(T ) /δ) 3 /2 T 3 /2 Tr(Σ) + L 2 D 2 1 ∥Σ∥ 3 1 /4We condition on the event E and let η= c 2 min{ 1 2L , D1 B ′ T , D1 g ′ √ T } where c = 1 √ 8C M +330. Note that this choice of η satisfies the requirements of Lemma 10 and Lemma 13. By Lemma 10, the following holds:F (x T ) -F (x * ) ≤ D 2 1 2ηT + 1 T T t=1 ⟨b t , x t -x * ⟩ + 1 T T t=1 ⟨v t , x t -x * ⟩ + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2 By Lemma 13, 1 {E t } = 1 ∀t ∈ [T ].Hence, the following holds.F (x T ) -F (x * ) ≤ D 2 1 2ηT + 1 T T t=1 bt , d t + 1 T T t=1 ⟨ṽ t , d t ⟩ + 2η T T t=1 ∥ bt ∥ 2 + 2η T T t=1 ∥ṽ t ∥ 2 ≤ D 2 1 2ηT + 2BD 1 + 2ηB 2 + 2ηC M g 2 + 4D 1 V ln( K /δ) T + 8D 1 Γ ln( K /δ) T ≤ D 2 1 ηT + 3ηB 2 T + 2ηC M g 2 + 4D 1 V ln( K /δ) T + 8D 1 A ln( K /δ)T Where the second inequality uses Lemma 11 and the definition of the event E and the third inequality uses ab ≤ a 2 + b 2 /4. For the rest of the proof, we shall use C to denote an absolute numerical constant whose value can differ at every step. By our choice of the step-sizeD 2 ηT ≤ CLD 2 1 T + CD 1 B ′ + CD 1 g ′ √ T 3ηB 2 T ≤ CD 1 B ′ 2ηC M g 2 ≤ CD 1 g ′ √ THence, conditioned on the event E, the following holds:F (x T ) -F (x * ) ≤ CLD 2 1 T + CD 1 B ′ + CD 1 g ′ √ T + CD 1 V ′ ln( K /δ) T + CD 1 A ln( K /δ)T Substituting the values of g ′ , B ′ and V ′ , we obtain the following:F (x T ) -F (x * ) ≤ CLD 2 1 T + CD 1 A ln( K /δ) T + CLD 2 1 ln( K /δ) T • Tr(Σ) + L 2 D 2 1 A + CLD 2 1 ln( K /δ) T • Tr(Σ) + L 2 D 2 A + CL 2 D 3 1 ln( K /δ) 3 /2 T 3 /2 • Tr(Σ) + L 2 D 2 1A 3 /2 Substituting the value of A, we conclude that the following inequality holds almost surely conditioned on the event EF (x T ) -F (x * ) ≲ D 1 Tr(Σ) + ∥Σ∥ 2 Tr(Σ) + LD 1 ln( ln(T ) /δ) T + LD 2 1 T + LD 2 1 ln( ln(T ) /δ) T Tr(Σ) + L 2 D 2 1 ∥Σ∥ 2 + L 2 D 3 1 ln( ln(T ) /δ) 3 /2 T 3 /2 Tr(Σ) + L 2 D 2 1 ∥Σ∥ 3 1 /4The prooof is completed by observing that P(E) ≥ 1 -δ by Lemma 12 which implies that the above inequality also holds with probability at least 1 -δProof. Since Π C is a contractive operatorD 2 t+1 = ∥x t+1 -x * ∥ 2 ≤ D 2 t -2η ⟨∇F (x t ) -b t -v t , x t -x * ⟩ + η 2 ∥∇F (x t ) -b t -v t ∥ ≤ D 2 t -2η ⟨∇F (x t ), x t -x * ⟩ + 2η ⟨b t , x t -x * ⟩ + 2η ⟨v t , x t -x * ⟩ + 2η 2 ∥∇F (x t )∥ + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2By the coercivity property,-2η ⟨∇F (x t ), x t -x * ⟩ ≤ -2η[F (x t ) -F (x * )] - η L ∥∇F (x t )∥ 2Substituting this into the recurrence for D 2 t+1 , we obtain the following:D 2 t+1 ≤ D 2 t -2η[F (x t ) -F (x * )] + 2η ⟨v t , x t -x * ⟩ + 2η ⟨b t , x t -x * ⟩ + η(2η -1 /L)∥∇F (x t )∥ 2 + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2 ≤ D 2 t -2η[F (x t ) -F (x * )] + 2η ⟨v t , x t -x * ⟩ + 2η ⟨b t , x t -x * ⟩ + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2where the last inequality uses the fact that η ≤ 1 /2L, Rearranging and taking averages on both sidesT t=1 F (x t ) -F (x * ) ≤ D 2 1 2ηT + 1 T T t=1 ⟨b t , x t -x * ⟩ + 1 T T t=1 ⟨v t , x t -x * ⟩ + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2Using the above inequality and the convexity of F , we conclude thatF (x T ) -F (x * ) = F 1 T T t=1 x t -F (x * ) ≤ 1 T T t=1 F (x t ) -F (x * ) ≤ D 2 1 2ηT + 1 T T t=1 ⟨b t , x t -x * ⟩ + 1 T T t=1 ⟨v t , x t -x * ⟩ + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2Note that by definition ofE t ∥∇F (x t )∥1 {E t } ≤ LD t 1 {E t } ≤ 2LD 1 We recall that b t = E[g t |F t-1 ] -E[clip Γ (g t )|F t-1 ]. Since Cov[g t |F t-1 ] ⪯ Σ by Assumption Bdd.2 nd Moment, we obtain the following bound on ∥b t ∥ by an application of Lemma 4∥b t ∥ ≤ ∥Σ∥ 2 √ d eff Γ + ∥∇F (x t )∥ ∥Σ∥ 2 Γ + ∥∇F (x t )∥ 3 Γ 2 + ∥Σ∥ 2 d eff ∥∇F (x t )∥ Γ 2 Since bt = b t 1 {E t }, it follows that ∥b t ∥ ≤ ∥Σ∥ 2 √ d eff Γ + ∥∇F (x t )1 {E t } ∥ ∥Σ∥ 2 Γ + ∥∇F (x t )∥ 3 1 {E t } Γ 2 + ∥Σ∥ 2 d eff ∥∇F (x t )∥1 {E t } Γ 2 ≤ ∥Σ∥ 2 √ d eff Γ + 2LD 1 ∥Σ∥ 2 Γ + 8L 3 D 3 1 Γ 2 + 2∥Σ∥ 2 d eff LD 1 Γ 2For any s ∈ [T ], we recall thatv s = E [clip Γ (g s )|F s-1 ] -clip Γ (g s ). Since E[g s |F s-1 ] = ∇F (x s )and Cov[g s |F s-1 ] ⪯ Σ, we obtain the following from Lemma 4∥E v s v T s |F s-1 ∥ 2 = ∥Cov [clip Γ (g s )|F s-1 ] ∥ ≤ ∥Σ∥ 2 + ∥∇F (x s )∥ 4 Γ 2 + ∥∇F (x s )∥ 2 Tr(Σ) Γ 2 Tr E v s v T s |F s-1 = Tr (Cov [clip Γ (g s )|F s-1 ]) ≤ Tr(Σ) For s ∈ [1 : T ] define E[ṽ s ṽT s |F s-1 ] = Σs . Since 1 {E s } is F s-1 -measurable and ṽs = v s 1 {E s }, it follows that Σs = E v s v T s |F s-1 1 {E s }.Hence, we conclude the following from the above inequalityEQUATIONFor s ∈ [T ], define h s = ⟨ṽ s , d s ⟩. We note that|h s | ≤ ∥ṽ s ∥ • ∥d s ∥ ≤ 4ΓD 1 E [h s |F s-1 ] = ⟨E[ṽ s |F s-1 ], d s ⟩ = 0 E h 2 s |F s-1 = d T s E[ṽ s ṽT s ]d s = d T s Σs d s ≤ ∥d s ∥ 2 ∥ Σ∥ ≤ 4D 21 V Hence, by Freedman's inequality (Lemma 3), we conclude that the following holds with probability at least 1 -δ /2:t s=1 ⟨ṽ t , d t ⟩ ≤ 4D 1 V t ln( K /δ) + 8ΓD 1 ln( K /δ) ∀ t ∈ [T ]We now apply Corollary 6 with p s = V , q s = Tr(Σ) and τ = 2Γ to conclude that the following holds with probability at least 1 -δ /2 uniformly for every t ∈[T ] t s=1 ∥ṽ s ∥ 2 ≤ 4C M Γ 2 ln( K /δ) 2 + C M UP(t)Tr(Σ) + C M tUP(t)V 2 4Γ 2 ≤ 4C M Γ 2 ln( K /δ) 2 + C M T Tr(Σ) + C M T 2 V 2 4Γ 2 ≤ C M T ∥Σ∥ 2 d eff + 4Γ 2 ln( K /δ) 2 T + V 2 T 4Γ 2 = C M g 2 Twhereg 2 = ∥Σ∥ 2 d eff + 4Γ 2 ln( K /δ) 2 T + V 2 T 4Γ 2The proof is concluded by a union boundWe prove the claim via induction. Clearly, the claim is true for t = 1. Now, suppose the claim holds for every s ≤ t for some t ∈[T ]. Since Π C is a contractive operator D 2 t+1 = ∥x t+1 -x * ∥ 2 ≤ D 2 t -2η ⟨∇F (x t ) -b t -v t , x t -x * ⟩ + η 2 ∥∇F (x t ) -b t -v t ∥ ≤ D 2 t -2η ⟨∇F (x t ), x t -x * ⟩ + 2η ⟨b t , x t -x * ⟩ + 2η ⟨v t , x t -x * ⟩ + 2η 2 ∥∇F (x t )∥ + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2By the coercivity property,-2η ⟨∇F (x t ), x t -x * ⟩ ≤ -2η[F (x t ) -F (x * )] - η L ∥∇F (x t )∥ 2Substituting this into the recurrence for D 2 t+1 , we obtain the following:D 2 t+1 ≤ D 2 t -2η[F (x t ) -F (x * )] + 2η ⟨v t , x t -x * ⟩ + 2η ⟨b t , x t -x * ⟩ + η(2η -1 /L)∥∇F (x t )∥ 2 + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2 ≤ D 2 t + 2η ⟨v t , x t -x * ⟩ + 2η ⟨b t , x t -x * ⟩ + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2where we use the fact that η ≤ 1 /2L. Now, by the Cauchy Schwarz inequality and the fact that ab ≤ a 2 + b 2 /4 we obtain the following:2η ⟨b t , x t -x * ⟩ ≤ D 2 t 2T + η 2 T ∥b t ∥ 2It follows thatD 2 t+1 ≤ 1 + 1 2T D 2 t + 5η 2 T ∥b t ∥ 2 + 4η 2 ∥v t ∥ 2 -2η ⟨v t , x t -x * ⟩Unrolling the above recursion for t steps and using the fact that (1 + 1 /2T ) T ≤ 2, we obtain the following:D 2 t+1 ≤ 1 + 1 2T T D 2 1 + t s=1 1 + 1 2T t-s 5η 2 T ∥b s ∥ 2 + 4η 2 ∥v s ∥ 2 + 2η ⟨v s , x s -x * ⟩ ≤ 2D 2 1 + t s=1 10η 2 T ∥b s ∥ 2 + 8η 2 ∥v s ∥ 2 -4η ⟨v s , x s -x * ⟩ By the induction hypothesis, 1 {E s } = 1 ∀s ∈ [t]. Hence, D 2 t+1 ≤ 2D 2 1 + 10η 2 T t s=1 ∥ bs ∥ 2 + 8η 2 t s=1 ∥ṽ s ∥ 2 -4η t s=1 ⟨ṽ s , d s ⟩ ≤ 2D 2 1 + 10η 2 T 2 B 2 + 8C M η 2 g 2 T + 16ηD 1 V t ln( K /δ) + 2Γ ln( K /δ) ≤ 3D 2 1 + 10η 2 T 2 B 2 + 8C M η 2 g 2 T + 64η 2 V t ln( K /δ) + 2Γ ln( K /δ) 2 ≤ 3D 2 1 + 10η 2 T 2 B 2 + 8C M η 2 g 2 T + 128η 2 V T ln( K /δ) + 1024Γ 2 ln( K /δ) 2where the second inequality follows from the Lemma 11 and the fact that we have conditioned on E. Note that by definition of g 2 and the AM-GM inequalityg 2 T ≥ 4Γ 2 ln( K /δ) 2 + V 2 T 2 4Γ 2 ≥ max{4Γ 2 ln( K /δ) 2 , 2V T ln( K /δ)} It follows that D 2 t+1 ≤ 3D 2 1 + 10η 2 T 2 B 2 + 8(C M + 40)η 2 g 2 T ≤ 3D 2 1 + 10c 2 D 2 1 + c 2 (8C M + 320)D 2 1 ≤ 4D 2 1where the second inequality uses the definition of η and the fact that B ′ and g ′ upper bound B and G respectively by equations ( 25) and ( 27) and the last inequality sets c = 1 √ 8C M +330 . Hence, D t+1 ≤ 2D 1 which proves the claim by induction.Let d eff = Tr(Σ) ∥Σ∥2 . Since Σ is positive semidefinite, 1 ≤ d eff ≤ d. Moreover, let clip Γ (g t ) = ∂F (x t ) + b t + v t where b t = E[clip Γ (g t )|F t ] -∂F (x t ) represents the bias due to clipping and E[v t |F t ] = 0. Let D t = ∥x t -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 η > 0F (x T ) -F (x * ) ≤ D 2 1 2ηT - 1 T T t=1 ⟨b t , x t -x * ⟩ - 1 T T t=1 ⟨v t , x t -x * ⟩ + ηG 2 + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2Define the events E t and the random vectors d t as follows for t ∈ [T ]:E t = {D t ≤ 2D 1 } d t = (x t -x * )1 {E t }We use the following lemma to control the bias Lemma 15 (Bias Control). For every t ∈ [T ], ∥b t ∥ ≤ B where B is defined as follows:B = ∥Σ∥ 2 √ d eff Γ + G ∥Σ∥ 2 Γ + G 3 Γ 2 + ∥Σ∥ 2 d eff G Γ 2We use the following lemma to control the varince Lemma 16 (Variance Control). Let V ≥ 0 be defined as follows:V = ∥Σ∥ 2 + G 4 Γ 2 + G 2 ∥Σ∥ 2 d eff Γ 2Then the following holds with probability at least 1 -δ uniformly for every t ∈ [T ]t s=1 ⟨v s , d s ⟩ ≤ 4D 1 V t ln( K /δ) + 8ΓD 1 ln( K /δ) t s=1 ∥v s ∥ 2 ≤ C M g 2 Twhere C M is a numerical constant and g 2 is defined as followsg 2 = ∥Σ∥ 2 d eff + 4Γ 2 ln( K /δ) 2 T + V 2 T 4Γ 2Let E denote the following eventE = { t s=1 ⟨v s , d s ⟩ ≤ 4D 1 V t ln( K /δ) + 8ΓD 1 ln( K /δ) ∀ t ∈ [T ] t s=1 ∥v s ∥ 2 ≤ C M g 2 T ∀t ∈ [T ]}Note that by Lemma 16, P(E) ≥ 1 -δ. We define the constant A as follows:A = ∥Σ∥ 2 d eff + G ∥Σ∥ 2 = ∥Σ∥ 2 Tr(Σ) + GWe now set the clipping level Γ = AT ln( K /δ) . For this choice of Γ, we now simplify the expression for B as follows:EQUATIONSimilarly, the expression for V can be simplified as followsEQUATIONUsing the above inequality, we derive the following upper bound for g:EQUATIONWe also prove the following uniform upper bound on the iterates x t satisfies the following with probability at least 1 -δF (x T ) -F (x * ) ≲ D 1 G √ T + D 1 Tr(Σ) + ∥Σ∥ 2 Tr(Σ) + G ln( K /δ) T + D 1 G ln( K /δ) T Tr(Σ) + G 2 ∥Σ∥ 2 + D 1 G 2 ln( 1 /δ) 3 /2 T 3 /2 Tr(Σ) + G 2 ∥Σ∥ 3 1 /4E.1 Proof of Lemma 14Proof. Since Π C is a contractive operatorD 2 t+1 = ∥x t+1 -x * ∥ 2 ≤ D 2 t -2η ⟨∂F (x t ) + b t + v t , x t -x * ⟩ + η 2 ∥∇F (x t ) + b t + v t ∥ ≤ D 2 t -2η ⟨∂F (x t ), x t -x * ⟩ -2η ⟨b t , x t -x * ⟩ -2η ⟨v t , x t -x * ⟩ + 2η 2 ∥∂F (x t )∥ 2 + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2 ≤ D 2 t -2η[F (x t ) -F (x * )] -2η ⟨b t , x t -x * ⟩ -2η ⟨v t , x t -x * ⟩ + 2η 2 G 2 + 4η 2 ∥b t ∥ 2 + 4η 2 ∥v t ∥ 2where the second inequality follows from the definition of the subgradient and the G lipschitzness of F . Rearranging and taking averages on both sidesT t=1 F (x t ) -F (x * ) ≤ D 2 1 2ηT - 1 T T t=1 ⟨b t , x t -x * ⟩ - 1 T T t=1 ⟨v t , x t -x * ⟩ + ηG 2 + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2Using the above inequality and the convexity of F , we conclude that F (x T ) -F (x * ) = F 1 T T t=1 x t -F (x * ) ≤ 1 T T t=1 F (x t ) -F (x * ) ≤ D 2 1 2ηT - 1 T T t=1 ⟨b t , x t -x * ⟩ - 1 T T t=1 ⟨v t , x t -x * ⟩ + ηG 2 + 2η T T t=1 ∥b t ∥ 2 + 2η T T t=1 ∥v t ∥ 2 E.2∥b t ∥ ≤ ∥Σ∥ 2 √ d eff Γ + ∥∂F (x t )∥ ∥Σ∥ 2 Γ + ∥∂F (x t )∥ 3 Γ 2 + ∥Σ∥ 2 d eff ∥∂F (x t )∥ Γ 2 ≤ ∥Σ∥ 2 √ d eff Γ + G ∥Σ∥ 2 Γ + G 3 Γ 2 + ∥Σ∥ 2 d eff G Γ 2 E.3 Proof of Lemma 16For any s ∈ [T ], we recall thatv s = E [clip Γ (g s )|F s-1 ] -clip Γ (g s ). Since E[g s |F s-1 ] = ∂F (x s )and Cov[g s |F s-1 ] ⪯ Σ, we obtain the following from Lemma 4∥E v s v T s |F s-1 ∥ 2 = ∥Cov [clip Γ (g s )|F s-1 ] ∥ ≤ ∥Σ∥ 2 + ∥∂F (x s )∥ 4 Γ 2 + ∥∂F (x s )∥ 2 Tr(Σ) Γ 2 ≤ ∥Σ∥ 2 + G 4 Γ 2 + G 2 Tr(Σ) Γ 2 Tr E v s v T s |F s-1 = Tr (Cov [clip Γ (g s )|F s ]) ≤ Tr(Σ) For s ∈ [T ], define h s = ⟨v s , d s ⟩. We note that |h s | ≤ ∥v s ∥ • ∥d s ∥ ≤ 4ΓD 1 E [h s |F s-1 ] = ⟨E[v s |F s-1 ], d s ⟩ = 0 E h 2 s |F s-1 = d T s E[v s v T s ]d s = d T s Σ s d s ≤ ∥d s ∥ 2 ∥Σ s ∥ ≤ 4D 21 V Hence, by Freedman's inequality (Lemma 3), we conclude that the following holds with probability at least 1 -δ /2:t s=1 ⟨ṽ t , d t ⟩ ≤ 4D 1 V t ln( K /δ) + 8ΓD 1 ln( K /δ) ∀ t ∈ [T ]We now apply Corollary 6 with p s = V , q s = Tr(Σ) and τ = 2Γ to conclude that the following holds with probability at least 1 -δ /2 uniformly for every t ∈ [T ]t s=1 ∥ṽ s ∥ 2 ≤ 4C M Γ 2 ln( K /δ) 2 + C M UP(t)Tr(Σ) + C M tUP(t)V 2 4Γ 2 ≤ 4C M Γ 2 ln( K /δ) 2 + C M T Tr(Σ) + C M T 2 V 2 4Γ 2 ≤ C M T ∥Σ∥ 2 d eff + 4Γ 2 ln( K /δ) 2 T + V 2 T 4Γ 2 = C M g 2 T where g 2 = ∥Σ∥ 2 d eff + 4Γ 2 ln( K /δ) 2 T + V 2 T 4Γ 2The proof is concluded by a union boundWe prove the claim via induction. Clearly, the claim is true for t = 1. Now, suppose the claim holds for every s ≤ t for some t ∈[T ]. Since Π C is a contractive operator D 2 t+1 = ∥x t+1 -x * ∥ 2 ≤ D 2 t -2η ⟨∂F (x t ) + b t + v t , x t -x * ⟩ + η 2 ∥∇F (x t ) + b t + v t ∥ ≤ D 2 t -2η ⟨∂F (x t ), x t -x * ⟩ -2η ⟨b t , x t -x * ⟩ -2η ⟨v t , x t -x * ⟩ + 2η 2 ∥∂F (x t )∥ 2 + 4η 2 ∥v t ∥ 2 + 4η 2 ∥b t ∥ 2 ≤ D 2 t -2η[F (x t ) -F (x * )] -2η ⟨b t , x t -x * ⟩ -2η ⟨v t , x t -x * ⟩ + 2η 2 G 2 + 4η 2 ∥b t ∥ 2 + 4η 2 ∥v t ∥ 2where 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 ≤ a 2 + b 2 /4 we obtain the following:-2η ⟨b t , x t -x * ⟩ ≤ D 2 t 2T + η 2 T ∥b t ∥ 2It follows thatD 2 t+1 ≤ 1 + 1 2T D 2 t + 5η 2 T ∥b t ∥ 2 + 2η 2 G 2 + 4η 2 ∥v t ∥ 2 -2η ⟨v t , x t -x * ⟩Unrolling the above recursion for t steps and using the fact that (1 + 1 /2T ) T ≤ 2, we obtain the following:D 2 t+1 ≤ 1 + 1 2T T D 2 1 + t s=1 1 + 1 2T t-s 5η 2 T ∥b s ∥ 2 + 2η 2 G 2 + 4η 2 ∥v s ∥ 2 -2η ⟨v s , x s -x * ⟩ ≤ 2D 2 1 + 4η 2 G 2 T + t s=1 10η 2 T ∥b s ∥ 2 + 8η 2 ∥v s ∥ 2 -4η ⟨v s , x s -x * ⟩By the induction hypothesis,1 {E s } = 1 ∀s ∈ [t]. Hence, D 2 t+1 ≤ 2D 2 1 + 4η 2 G 2 T + 10η 2 T t s=1 ∥b s ∥ 2 + 8η 2 t s=1 ∥v s ∥ 2 -4η t s=1 ⟨v s , d s ⟩ ≤ 2D 2 1 + 4η 2 G 2 T + +10η 2 T 2 B 2 + 8C M η 2 g 2 T + 16ηD 1 V t ln( K /δ) + 2Γ ln( K /δ) ≤ 3D 2 1 + 4η 2 G 2 T + +10η 2 T 2 B 2 + 8C M η 2 g 2 T + 64η 2 V t ln( K /δ) + 2Γ ln( K /δ) 2 ≤ 3D 2 1 + 4η 2 G 2 T + +10η 2 T 2 B 2 + 8C M η 2 g 2 T + 128η 2 V T ln( K /δ) + 1024Γ 2 ln( K /δ) 2where the second inequality follows from the Lemma 15 and the fact that we have conditioned on E. Note that by definition of g 2 and the AM-GM inequalityg 2 T ≥ 4Γ 2 ln( K /δ) 2 + V 2 T 2 4Γ 2 ≥ max{4Γ 2 ln( K /δ) 2 , 2V T ln( K /δ)} It follows that D 2 t+1 ≤ 3D 2 1 + 4η 2 G 2 T + 10η 2 T 2 B 2 + 8(C M + 40)η 2 g 2 T ≤ 3D 2 1 + 4c 2 D 2 1 + 10c 2 D 2 1 + c 2 (8C M + 320)D 2 1 ≤ 4D 2 1where the second inequality uses the definition of η and the fact that g ′ upper bounds g, and the last inequality sets c = 1 √ 8C M +334 . Hence, D t+1 ≤ 2D 1 which proves the claim by induction.We have the following re-statement of Theorem 5 for the sake of readability. Theorem 9. Suppose M t for t = 0, . . . , T is an R d valued martingale such that M 0 = 0 almost surely, the martingale difference sequence v t := M t -M t-1 is such that ∥v t ∥ ≤ Γ and E[v t v ⊺ t |F t-1 ] = Σ t almost surely for every t = 1, . . . , T for some Γ > 0. Assume that there are deterministic sequences p 1 , . . . , p T and q 1 , . . . , q T such that Tr(Σ t ) ≤ q t and ∥Σ t ∥ ≤ p t almost surely.Let q := 1 T T t=1 q t and p := 1 T T t=1 p t . Then, for any δ ∈ (0, 1 2 )P(sup t≤T ∥M t ∥ ≥ g(T, δ) √ T ) ≤ δ Where g(T, δ) = C √ q + p√ T Γ + Γ √ T log( K δ ) and K = log Θ(log(( √ qT Γ + 1) log(d + 1)))Define the event A t (g) := {∥M t ∥ ≤ g √ T } and B t (g) := ∩ t s=1 A s . Consider the quantity N t := ∥M t ∥ 2 -t s=1 ∥v s ∥ 2 . Theorem 10. Let δ ∈ (0, 1 2 ) and g = g(T, δ 2 ) be as defined in Theorem 9. Under the conditions of Theorem 9, the following inequality holds for some large enough universal constant C.P {sup t≤T |N t | > ΓCg √ T log( 1 δ ) + CνgT 3/2 Γ } ∩ B T (g) ≤ δThe next corollary is a simple consequence of the Theorems 9 and 10.Corollary 6. Let δ ∈ (0, 1 2 ) and g = g(T, δ 3 ) be as specified in Theorem 9. Under the conditions of Theorem 9, the following inequality holds with probability at-least 1 -δ:T t=1 ∥v t ∥ 2 ≤ Cg 2 T F.1 Proof of Theorem 9The 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 ∥M t ∥. Define the event A t := {∥M t ∥ ≤ g √ T } and B t = ∩ t s=1 A s . Let H be any stopping time for the martingale M t . We have the following inequality which follows from PAC-Bayes theory (see Equation 5.2.1, Page 159 in [7] ).Theorem 11. Suppose π be any measure over R d and let M 1 (R d ) denote the space of all probability measures over R d . Let γ > 0 be arbitrary. Then conditioned on B T , with probability at-least 1 -δ, the following inequality holds:EQUATIONWe will now bound the exponential moment: E M E θ∼π exp(γ ⟨M t , θ⟩) whenever π = N (0, I).Theorem 12. Let h(t) := t s=1 log 1 + γ 2 2 q t exp(γ 2 Γ 2 ) + γ 4 p t g 2 T exp(2γ 2 Γg √ T ) . Then,E θ∼π exp(γ⟨M t , θ⟩ -h(t))1(B t )is a supermartingale with respect to the filtrationF t Proof. Let Σ t := E[v t v ⊺ t |F t-1] and ν t := ∥Σ t ∥. First, consider E θ∼π exp(γ ⟨M t , θ⟩). By the properties of the Gaussians, we must have almost surely:EQUATIONUsing the fact that ∥M t ∥ 2 = ∥v t ∥ 2 + 2⟨v t , M t-1 ⟩ + ∥M t-1 ∥ 2 , we have:EQUATIONWe will now bound the quantity:E exp( γ 2 ∥vt∥ 2 2 + γ 2 ⟨v t , M t-1 ⟩)1(A t ) F t-1 .Using the convexity of x → exp(x), we conclude:EQUATIONIn the second step, we have used the fact that exp(γ2 ∥v t ∥ 2 )1(A t ) ≤ 1 + γ 2 ∥v t ∥ 2 exp(γ 2 Γ 2) almost surely using the power series expansion of the exp() function. Using the power series expansion of exp(x), we have:EQUATIONHere, ν t = ∥Σ t ∥ op In the second step we have used the fact that E[v t |F t-1 ] = 0 and the fact that ⟨v t , M t-1 ⟩ ≤ Γ∥M t-1 ∥ almost surely. Plugging Equation (36) into Equation ( 35), we conclude:EQUATIONUsing Equation (37) and that under the event B t-1 we must have ∥M t-1 ∥ ≤ g √ T , we conclude:EQUATIONTherefore, by induction, we conclude the statement of the theorem.Theorem 13. For any stopping time H,EQUATIONWhere h(T ) =T t=1 log 1 + γ 2 qt 2 exp(γ 2 Γ 2 ) + γ 4 p t g 2 T exp(2γ 2 Γg √ T )Proof. From Theorem 12 and the optional stopping theorem, we conclude that the following quantity is a super-martingale:M exp t := E θ∼π exp(γ M min(H,t) , θ -h(min(H, t)))1(B min(H,t) )Therefore, we have:E θ∼π exp(γ M min(H,T ) , θ -h(T ))1(B T ) ≤ M exp T ≤ EM exp 0 = 1Combining Theorem 13 and Equation ( 32), we conclude that the following inequality holds with probability at-least 1 -δ when conditioned on B T :sup ρ∈M1(R d ) E θ∼ρ γ M min(T,H) , θ -KL (ρ|| || ||π) ≤ h(T ) + log( 1 δP(B T ) )In the RHS of the inequality above, we replace the supremum over M 1 with the supremum over the set of all probability distributions {N (αξ, I) such that ξ ∈ S d-1 , α ≥ 0}. We note that KL (N (αξ, I)|| || ||π) = α2 2 to conclude that the following inequality holds with probability at-least 1 -δ when conditioned on B T :sup α>0 γα∥M min(H,T ) ∥ - α 2 2 ≤ h(T ) + log( 1 δP(B T ) )That is:∥M min(H,T ) ∥ ≤ 2h(T ) + 2 log( 1 δP(B T ) ) γ 2Now, note that by definition,EQUATIONTherefore, whenever:γ ≤ min 1 Γ , 1 2 √ Γg √ T, we note with probability at-least 1 -δ conditioned on the event B T :∥M min(H,T ) ∥ ≲ T q + γ 2 pg 2 T 2 + 1 γ 2 log 1 δP(B T )We therefore state the following theorem: Theorem 14. Suppose δ, δ 1 ∈ (0, 1 2 ). If M t satisfies (g, T, δ) uniform concentration for some δ < 1 2 . Then M t also satisfies (g ′ , T, δ + δ 1 ) concentration, where(g ′ ) 2 = C q + γ 2 pg 2 T + log( 1 δ1 ) γ 2 T for any γ ≤ min 1 Γ , Additionally, suppose g ≥ c 0 Γ √T for some fixed constant c 0 > 0, then we have for some constant C iter (c 0 ):(g ′ ) 2 = C iter (c 0 )[q + g p√ T Γ + Γ √ T log( 1 δ1 ) ]Proof. Since δ ≤ 1 2 , we conclude that P(B T ) ≥ 1 2 . Given that M t satisfies (g, T, δ) uniform concentration. We conclude from the discussion above that for some universal constant C and anyγ ≤ min 1 Γ , 1 2 √ Γg √ T, we have:sup H P(∥M min(H,T ) ∥ 2 ≥ C[T q + γ 2 pg 2 T 2 + 1 γ 2 log 1 δ1 ] B T ) ≤ δ 1Picking H to be the stopping time given by H = inf{t ≥ 0 :∥M t ∥ 2 ≥ C[T q + γ 2 pg 2 T 2 + 1 γ 2 log 1 δ1]} where C is the same constant as in the equation above, we conclude:P(sup t≤T ∥M t ∥ 2 ≥ C[T q + γ 2 pg 2 T 2 + 1 γ 2 log 1 δ1 ] B T ) ≤ δ 1Only in this proof, call the eventG := {sup t≤T ∥M t ∥ 2 ≥ C[T q + γ 2 pg 2 T 2 + 1 γ 2 log 1 δ1 ]}. We have: P(G) = P(G ∩ B T ) + P(G ∩ B ∁ T ) ≤ P(G|B T ) + P(B ∁ T ) ≤ δ 1 + δ Whenever g ≥ c 0 Γ √ T , we can pick λ = c1(c0) √ Γg √ Tand conclude the result.We now state consider Lemma 11 from [2] . . For t ∈ N, denoting f (t) to be the t fold composition of f with itself, we have for any u ∈ R + :|f (t) (u) -u * | ≤ β (2-1 2 t-1 ) |u -u * | 1 2 t .We are now ready to prove the main theorem 9Proof of Theorem 9. It is sufficient to show that there existsK = log Θ(log(ΓT d log( 1 δ )))) such that M t obeys (g, T, δ) uniform concentration where g = C max( Γ √ T , q + p√ T Γ + Γ √ T log( K δ ))Let K ∈ N be any fixed integer. By Theorem 6, we conclude that the martingale M t is (g 0 ( δ K ), T, δ K ) uniformly concentrated. Fix some c 0 > 0 and C iter (c 0 ) be as in Theorem 14.i := C iter (c 0 )q + C iter (c 0 )g i-1 G where G = p√ T Γ + Γ √ T log( K δ ). If g 0 ≤ c 0 Γ √T , then the statement of the theorem follows. Suppose there exists K1 ≤ K -1 such that g K1 ≤ c0Γ √T and suppose that it is the first such integer. If K 1 = 0, the statement of the theorem follows from (g 0 ( δ K ), T, δ K ) uniform concentration of M t . Suppose 1 ≤ K 1 ≤ K -1. Then, min(g 0 , . . . , g K1-1 ) ≥ c 0 Γ √ T . Then, by Theorem 14, the fact that√ x + y ≤ √ x + √ yand induction, we conclude that M t obeys (g i , T, (i+1)δ K ) for every i ≤ K 1 . Thus we conclude the statement of the theorem. Suppose such a K 1 does not exist. Then, min(g 0 , . . . , g K-1 ) ≥ c 0 Γ √ T . Then, by Theorem 14, the fact that √ x + y ≤ √ x + √ y and induction, we conclude that M t obeys (g i , T, (i+1)δ K ) for every i ≤ K -1. Therefore, it obeys (g K , T, δ) uniform concentration.Consider the function f in Lemma 18 with α = C iter (c 0 )q and β = C iter (c 0 )G and let the corresponding fixed point be denoted by g * . It is easy to show that the fixed point g * ≲ √ q + G. After K iterations, we must have:g K ≤ g * + (C iter (c 0 )G 1-1 2 K )|g 0 -g * | 1 2 K ≲ g * + (G 1-1 2 K )|g 0 | 1 2 KWe can show that picking K = log Θ(log((1 + √ qT Γ ) log d)), and the bound on Γ, we conclude the result.Proof of Theorem 10. Recall that Σ t := E[v t v ⊺ t |F t-EQUATIONThis shows that N exp t is a super-martingale. Using the fact that N exp 1 = 1 almost surely, the optional stopping theorem and the Chernoff bound, we conclude that for any stopping time H, we have for any α, γ > 0EQUATIONTaking γ = 1 2Γg √ T allows us to conclude:P({N min(T,H) > ΓCg √ T log( 2 δ ) + CνgT 3/2 Γ } ∩ B T ) ≤ δ 2 Let α = ΓCg √ T log( 2 δ ) + CνgT 3/2 Γand take H to be the stopping time min(inf t {t > 0 : N t > α}, T ) where infimum of an empty set is taken to be infinity. We note that {sup t≤T N t > α} = {N min(T,H) > α}. We thus conclude: we assume θ ̸ = θ * and observe thatEQUATIONw T Σv 2 + 2E ⟨w, x⟩ 2 ⟨v, x⟩ 2 ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 2 + sup ∥v∥=1,∥w∥=1 E[⟨w, x⟩ 4 ] E[⟨v, x⟩ 4 ] ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 2 + C 4 sup ∥v∥=1,∥w∥=1 E[⟨w, x⟩ 2 ] • E[⟨v, x⟩ 2 ] ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 2 + C 4 sup ∥w∥=1 w T Σw • sup ∥v∥=1 v T Σv ≤ ∥d θ ∥ 2 • 2∥Σ∥ 2 (C 4 + 1)where we use the fourth moment assumption on the covariates in the eighth step. Note that the above bound also holds when θ = θ * since in that case A(θ) = 0 and d θ = 0. It follows that∥Σ(θ)∥ ≤ ∥A(θ)∥ + σ 2 ∥Σ∥ ≤ 2(C 4 + 1)∥Σ∥ 2 ∥θ -θ * ∥ 2 + σ 2 ∥Σ∥We shall now derive an upper bound for Tr(Σ(θ)) as follows:Tr(Σ(θ)) = E[∥n(θ; x, y)∥ 2 ] = E ∥Md θ -xϵ∥ 2 = E[∥Md θ ∥ 2 ] -2E[⟨Md θ , x⟩ E[ϵ|x]] + E[∥x∥ 2 E[ϵ 2 |x]] ≤ E[∥Md θ ∥ 2 ] + σ 2 Tr(Σ) We now control E[∥Md θ ∥ 2 ]. Note that E[∥Md θ ∥ 2 ] = 0 if θ = θ *so we shall now consider the case when θ ̸ = θ * . To this end, let e 1 , . . . , e d be an orthonormal basis of R d such that e 1 = d θ ∥d θ ∥ . For the remainder of the proof, we use Σ ij to denote Σ ij = e T i Σe j where i, j ∈ [d], which implies that Tr(Σ) = d i=1 Σ ii . We also note that for any two symmetric matrices B, C, (B-C) 2 ⪯ 2B 2 +2C 2 .Hence,E[∥Md θ ∥ 2 ] = ∥d θ ∥ 2 E ∥Me 1 ∥ 2 = ∥d θ ∥ 2 E e T 1 (Σ -xx T ) 2 e 1 ≤ 2∥d θ ∥ 2 E e T 1 Σ 2 + (xx T ) 2 e 1 ≤ 2∥d θ ∥ 2 e T 1 Σ 2 e 1 + E ⟨e 1 , x⟩ 2 ∥x∥ 2 ≤ 2∥d θ ∥ 2 ∥Σ 2 ∥ + E ⟨e 1 , x⟩ 2 d i=1 ⟨e i , x⟩ 2 ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 + E ⟨e 1 , x⟩ 4 + d i=2 E[⟨e 1 , x⟩ 2 ⟨e i , x⟩ 2 ] ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 + E ⟨e 1 , x⟩ 4 + d i=2 E ⟨e 1 , x⟩ 4 E ⟨e i , x⟩ 4 ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 + C 4 E ⟨e 1 , x⟩ 2 2 + C 4 d i=2 E ⟨e 1 , x⟩ 2 E ⟨e i , x⟩ 2 ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 + C 4 d i=1 E ⟨e 1 , x⟩ 2 E ⟨e i , x⟩ 2 ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 + C 4 (e T 1 Σe 1 ) d i=1 (e T i Σe i ) ≤ 2∥d θ ∥ 2 ∥Σ∥ 2 + C 4 (e T 1 Σe 1 ) d i=1 Σ ii ≤ 2∥d θ ∥ 2 (∥Σ∥Tr(Σ) + C 4 ∥Σ∥Tr(Σ)) ≤ 2(C 4 + 1)∥Σ∥ 2 Tr(Σ)∥d θ ∥ 2Clearly, the above bound holds even when θ = θ * . Hence, we infer thatTr(Σ(θ)) ≤ 2(C 4 + 1)∥Σ∥ 2 Tr(Σ)∥θ -θ * ∥ 2 + σ 2 Tr(Σ)From these bounds, we can conclude the following∥Σ(θ)∥ ≤ 2(C 4 + 1)∥Σ∥ 2 2 ∥θ -θ * ∥ 2 + σ 2 ∥Σ∥ Tr(Σ(θ)) ≤ Tr(Σ) ∥Σ∥ 2 2(C 4 + 1)∥Σ∥ 2 2 ∥θ -θ * ∥ 2 + σ 2 ∥Σ∥Thus, the stochastic gradient oracle satisfies Assumption QG 2 nd Moment with α = 2(C 4 + 1)∥Σ∥ 2 2 , β = σ 2 ∥Σ∥ and d eff = Tr(Σ) /∥Σ∥. Hence, the result follows by an application of Theorem 2Recall from Section 5.4 that Ξ = R d × {0, 1} and P denotes the following linear-logistic model:x ∼ Q, E[x] = 0, E[xx T ] ⪯ Σ; y ∼ Bernoulli(ϕ(⟨θ * , x⟩))where ϕ(t) = (1 + e -t ) -1 . The covariates x are heavy tailed, with only bounded second moments.The sample-level loss is given by the negative log likelihood of y|x as follows:f (θ; x, y) = ln(1 + exp(⟨x, θ⟩)) -y ⟨x, θ⟩The associated population loss and stochastic gradient oracle is given byF (θ) = E x,y∼P [ln(1 + exp(⟨x, θ⟩)) -y ⟨x, θ⟩] g(θ; x, y) = ϕ(⟨x, θ⟩)x -yxWe now compute the gradient and the Hessian of F∇F (θ) = E exp(⟨x, θ⟩) 1 + exp(⟨x, θ⟩) • x -ϕ(⟨x, θ * ⟩)x = E [(ϕ(⟨x, θ⟩) -ϕ(⟨x, θ * ⟩)) x] ∇ 2 F (θ) = E[ϕ ′ (⟨x, θ⟩)xx T ] = E[ϕ(⟨x, θ⟩)(1 -ϕ(⟨x, θ⟩))xx T ] Since 0 ≤ ϕ(t) ≤ 1 for every t ∈ R, we note that 0 ⪯ ∇ 2 F (θ) ⪯ E[xx T ] ⪯ Σ (as E[x] = 0).Hence, F is convex and L smooth with L = ∥Σ∥ 2 . Furthermore, since ∇F (θ * ) = 0 and F is convex, we conclude that θ * is a minimizer of F .It is easy to see that E [g(θ; x, y)] = E [(ϕ(⟨x, θ⟩) -ϕ(⟨x, θ * ⟩)) x] = ∇F (θ), i.e., the stochastic gradient is unbiased. Let n(θ; x, y) denote the stochastic gradient noise, i.e.,:n(θ; x, y) = g(θ; x, y) -∇F (θ) = ϕ(⟨x, θ⟩)x -E [ϕ(⟨x, θ⟩)x] + E[ϕ(⟨x, θ * ⟩)x] -yxWe shall now control the stochastic gradient covariance Σ(θ) = E[n(θ; x, y)n(θ; x, y) T ]. To this end, we define a x (θ) and c x,y (θ) as follows:a x (θ) = ϕ(⟨x, θ⟩)x -E [ϕ(⟨x, θ⟩)x] c x,y (θ) = E[ϕ(⟨x, θ * ⟩)x] -yx We note that E [c x,y (θ)|x] = 0 and E[a x (θ)] = 0. Since n x,y (θ) = a x (θ) + b x,y (θ), it follows that: Σ(θ) == E[n(θ; x, y)n(θ; x, y) T ] = E a x (θ)a x (θ) T + E c x,y (θ)c x,y (θ) TWe now control each of the terms in the RHS as follows:E a x (θ)a x (θ) T = E[ϕ(⟨x, θ⟩) 2 xx T ] -E [ϕ(⟨x, θ⟩)x] E [ϕ(⟨x, θ⟩)x] T ⪯ E[ϕ(⟨x, θ⟩) 2 xx T ] ⪯ E[xx T ] ⪯ Σwhere we use the fact that ϕ(t) ≤ 1. Similarly,E c x,y (θ)c x,y (θ) T = E[y 2 xx T ] -E[ϕ(⟨x, θ * ⟩)x]E[ϕ(⟨x, θ * ⟩)x] T ⪯ E[ϕ(⟨x, θ * ⟩)xx T ] ⪯ E[xx T ] ⪯ Σwhere we use the fact that E[y2 |x] = ϕ(⟨x, θ * ⟩) ≤ 1. It follows that Σ(θ) ⪯ 2ΣThus, the stochastic gradient oracle satisfies the Bdd. 2 nd Moment assumption. Hence, the stochastic gradient oracle satisfies the Bdd. 2 nd Moment assumption. Thus, the following result, which is a formal version of Corollary 3, is implied by Theorem 7Corollary 7 (Heavy Tailed Logistic Regression). Under the stochastic subgradient oracle described above, realized using N ≳ ln(ln(d)) i.i.d samples from P , the average iterate of Algorithm 1, when run under the parameter settings of Theorem 4 satisfies the following with probability at least 1 -δ: where sgn(t) = t ∥t∥ for t ̸ = 0 and sgn(0) = 0. We note that for every (x, y) ∈ R d × R, f (θ; x, y) is a convex function in θ, and thus, the population risk F is a convex function, whose subgradient is given by:∂F (θ) = E [sgn (⟨θ -θ * , x⟩ -ϵ) x]We now show that F is a Lipschitz function by bounding ∂F (θ) as follows:∥∂F (θ)∥ = ∥E [sgn (⟨θ -θ * , x⟩ -ϵ) x] ∥ ≤ E [|sgn (⟨θ -θ * , x⟩ -ϵ) | • ∥x∥] ≤ E [∥x∥ 2 ]≤ Tr(Σ)where the second step follows from Jensen's inequality, the third step uses the fact that |sgn(t)| ≤ 1 and applies the Cauchy Schwarz inequality. Hence, F is G-Lipschitz with G = Tr(Σ). We now show that ∂F (θ * ) = 0 which would imply that θ * is a minimizer of F (as F is convex)∇F (θ * ) = E [sgn(ϵ)x] = E [x • E [sgn(ϵ)|x]] = 0where we use the fact that E[sgn(ϵ)|x] = 0, because ϵ|x is a continuous random variable with zero median.For the stochastic gradient oracle described above, the associated stochastic gradient noise n(θ; x, y) and its covariance Σ(θ) are given as follows: NeurIPS Paper Checklist • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.√Γg√ T . 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

1. The time horizon $T$ is also requested to make the algorithm work. Is it possible to extend to the any-time setting?

1. There is an extra $\log{\log{T}}$ term in the bounds.

1. Please specify the stepsize $\eta$ in Theorems 3 and 4.

1. Line 82, missing a square root?
questions: questions: See **Weaknesses**.
limitations: limitations: Not applicable.
paper_summary: paper_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.

The 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.
Additionally, 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.
Furthermore, 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.
strength_weakness: strength_weakness: 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.
Despite its significant contributions, the paper has several areas that could benefit from improvement:
1. 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.
The 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.
2. 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.
For 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.
3. 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.
Incorporating experiments with diverse datasets and comparisons with existing methods would provide empirical evidence of the proposed techniques' efficacy and robustness in real-world scenarios.

Addressing 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.
I welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!
questions: questions: See the Weaknesses part.
limitations: limitations: The paper is theoretical, and I believe there is no need to confirm societal impact.
paper_summary: paper_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. 

The authors cast the problem as stochastic convex optimization (SCO) with heavy-tailed stochastic gradients. 

They 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. 

The 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.
strength_weakness: strength_weakness: 1. **Missing Reference**: There is one paper from my perspective that is related but not cited.

2. **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.
questions: 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.

    - [1*] Li, Xiang, and Qiang Sun. "Variance-aware decision making with linear function approximation under heavy-tailed rewards." Transactions on Machine Learning Research.

2. **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?

3. **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:
   - 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.
   - 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?

4. **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: limitations: See the Questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?
- 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
- 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).
- In terms of presentation, I think proofs, especially section F, can be written in a more streamlined way  and for example, with an outline. 
- Some minor details  
Line 82: There should be a square root in the bound  
Line 106: We not(e) that  

Reference

E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping, NeuRIPS, 2020

T. 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
questions: 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: limitations: The authors have adequately addressed the limitations of the paper.

Comments: title: Thank you
Some notes regarding parameter free algorithms
comment: Thank you very much. We hope to work on the directions pointed out by the reviewer in the future.
I thank the authors for further discussion. Though some parts of the work are suboptimal and undesirable in my view, I think the refined analysis for SGD could potentially bring new insights into the optimization community. As such, I would increase my score to 6.
Thank you for your feedback about removing problem dependent parameters. Obtaining fully parameter free optimization algorithms would be a great direction for future research and we will follow the helpful references provided by the reviewer. Below, we note some additional complexities which arise in the context of our work and argue that this requires additional techniques, beyond the scope of our work..

### Parameter Dependence on $D_1$ and $T$:

The reviewer points to the work [3] as an example to improve parameter dependence in the algorithm. We want to note that [3, Theorem 1] which removes dependence on $T$ in the parameters achieves a sub-optimal bound with extra $\log^2 T$ terms, whereas [3, Theorem 2] which has $T$ dependent parameters removes these extra factors. Since our sharp analysis is meant to remove such extra logarithmic factors from the leading order term, we believe a straightforward adaptation of such techniques might not work in our case. 

Note that [3] considers a fixed upper bound on the stochastic gradient noise. However, Assumption 2 in our work allows for noise whose covariance can grow with distance from the optimum, which is necessary for important applications like linear regression. Thus, removing the dependence on the initial distance in our case might require additional technical considerations.  


### Regarding $\log \log T$ factors:
Thank you for the clarification. After a careful examination of our technical results, removing the $\log \log T$ factors does not seem straightforward. We also note that the results given in [4, Theorem 3.1] and [3, Theorem 3] show that they achieve rates with a dependence of $d\log(1/\delta)$. We compare this to $d + \sqrt{d}\log(\tfrac{\log T}{\delta})$ dependence which we achieve in our work. Note that  $\sigma^2$ in these works corresponds to $\mathsf{Tr}(\Sigma)$ in our work which we take to be $\Theta(d)$ for the sake of comparison. Thus our $\log\log T$ dependence is in the lower order term.
I thank the authors for the thoughtful response. I hope to see the above discussion in the paper. I maintain my current score.
I first thank the author's detailed response.

**Problem-dependent parameters and $T$.** I understand some existing works require these conditions. However, doing research needs to explore new possibilities instead of sticking to old ways. More importantly, as far as I know, at least two different ways can partially remove them at least in the non-smooth and convex case.

  1. Parameter-free algorithms from the online learning community: For example, see [1], which can remove the dependence on $D_1$. However, as mentioned by the authors, I agree this may require additional algorithmic modifications.

  2. Recent advances in stochastic optimization: Another simpler way is to combine the DoG technique proposed by [2]. For example, see [3], which not only removes $D_1$ but also removes $T$ in a simpler way.

Hence, I highly encourage the authors to consider how to remove these parameters (even partially), which can significantly improve the quality of the paper. 

In addition, the authors mentioned that the results can be easily adapted to settings where only the upper bounds of problem-dependent quantities are known. However, I am not very convinced since it is hard to imagine that this can be guaranteed in a streaming setting. Could you provide some concrete examples?

**Extra $\log\log T$.** 

  1. I clarify that I didn't claim this is a major weakness. Instead, I put it in the weakness only because it is undesired and suboptimal. I believe the final goal should always be to find the optimal bound. 

  2. Moreover, I also would like to point out that the optimal rate without any extra logarithmic has already been achieved in prior works like [4] (which is even mentioned by the authors) and [3]. But I understand the double $\log$ factor here may appear due to different reasons, which could require different ways to remove. However, as discussed above, this is still a weakness in my opinion. 

  3. I appreciate the authors' discussion on this weakness, which I recommend adding as a remark in the paper.

**References**

[1] Zhang, J., & Cutkosky, A. (2022). Parameter-free regret in high probability with heavy tails. Advances in Neural Information Processing Systems, 35, 8000-8012.

[2] Ivgi, M., Hinder, O., & Carmon, Y. (2023, July). Dog is sgd’s best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning (pp. 14465-14499). PMLR.

[3] Liu, Z., & Zhou, Z. (2023). Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation. arXiv preprint arXiv:2303.12277.

[4] Nguyen, T. D., Nguyen, T. H., Ene, A., & Nguyen, H. (2023). Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Advances in Neural Information Processing Systems, 36, 24191-24222.
Thank you for the response. I maintain my current evaluation of the paper as it is highly technical and covers areas I am unfamiliar with. I believe the paper could be improved based on the current modifications shown in the rebuttal. Good luck to you.