Robust Stochastic Optimization via Gradient Quantile Clipping
Authors: Ibrahim Merad
Stéphane Gaïffas
Venue: Accepted by TMLR ()

Abstract: We introduce a clipping strategy for Stochastic Gradient Descent (SGD) which uses quantiles of the gradient norm as clipping thresholds. We prove that this new strategy provides a robust and efficient optimization algorithm for smooth objectives (convex or non-convex), that tolerates heavy-tailed samples (including infinite variance) and a fraction of outliers in the data stream akin to Huber contamination. Our mathematical analysis leverages the connection between constant step size SGD and Markov chains and handles the bias introduced by clipping in an original way. For strongly convex objectives, we prove that the iteration converges to a concentrated distribution and derive high probability bounds on the final estimation error. In the non-convex case, we prove that the limit distribution is localized on a neighborhood with low gradient. We propose an implementation of this algorithm using rolling quantiles which leads to a highly efficient optimization procedure with strong robustness properties, as confirmed by our numerical experiments.

Published in Transactions on Machine Learning Research (10/2024)
Robust Stochastic Optimization via Gradient Quantile Clip- ping
Ibrahim Merad
émerad@lpsm.paris
LPSM, UMR 8001 Université Paris Cité, Paris, France
Stéphanc Gaïffas
LPSM, UMR 8001 Université Paris Cité, Paris, France
DMA, École normale supéricure
Reviewed on OpenReview: https:///peereeieeel net/ formm? id= V3RK/
Abstract
We introduce clipping strategy for Stochastic Gradient Descent (SGD) which uses quantiles of the gradient norm as clipping thresholds. We prove that this new strategy provides robust and efficient optimization algorithm for smooth objectives (convex non-convex), that tolerates hcavy-tailed samples (including infinite variance) and fraction of outliers in the data stream akin to Huber contamination. Our mathematical analysis leverages the connection between constant step size SGD and Markov chains and handles the bias introduced by clipping in an original way. For strongly convex objectives, we prove that the iteration converges a concentratod distribution and derive high probability bounds the final estimation error. In the non-convex case, prove that the limit distribution is localized neighborhood with low gradient. We propose implementation of this algorithm using rolling quantiles which leads to highly efficient optimization procedure with strong robustness properties, as confirmed by our numerical experiments.
1 Introduction
Stochastic gradient descent (SGD) (Robbins & Monro 1951
is the core optimization algorithm at the
origin of most. stochastic optimization procedures (Kingma Ba 2014 Defazio et al. 2014 Johnson & Zhang 2013). SGD and its variants are ubiquitously employed in machine learning in order train
models Kushner & Yin 2003: Benveniste et al. 2012 Lan 2020 Shalev-Shwartz et al.) 2007 Bottou et al.
2018
Ma et al.
2018
The convergence properties of SGD are therefore subjects of major interest.
Early studies of SGD convergence generally relied on strong assumptions such as bounded domain Shalev-
Shwartz et al. 2009 or uniformly bounded gradient variance (Rakhlin et al.) 2011] and obtained error
bounds expectation. With the recent. resurgence of interest. for robust statistics (Hsu & Sabato 2016
Diakonikolas et al. 2019 Lecué Lerasle 2017 Prasad al. 2018). variants SGD based on clipping are
shown to be robust. heavy-tailed gradients (GGorbunov et al. 2020 Tsai et. al. 2022 where the gradient
samples are only required to have finite variance. The latter requireent has been further weakened to
the existence of a q-th moment for some q > 1 in (Sadiey et al.
2023
Nguyen et al. 2023). In this paper,
we go further and show that another variant of clipped SGD with proper thresholds is robust both to heavy tails and outliers in the data stream.
Robust statistics appeared in the 60s with the pioncering works of Huber, Tukey and others Tukey 1960
Huber 1992 1972 Roussceuw Hubert 2011 Hampel 1971). More recently, the field found new momentum
thanks to series of works about robust scalar mean estimation (Catoni 2012 Alon et al.
1996 Jerrum

---

Published in Transactions on Machine Learning Research (10/2024)
et al. 1986;
Lugosi & Mendelson 2021 and the more challenging multidimensional case (Hopkins
2020:
Catoni & Giulini, 2018:
Lugosi & Mendelson
2019
Minsker
2015
Cherapanamjeri et al.] 2019 Depersin
& Lecué 2022
Lei et al. 2020 Diakonikolas et al.
2020).
These paved the way to the elaboration of a
host of robust lcarning algorithms (Holland & Ikeda 2019
Prasad et al. 2018 Lecué & Lerasle 2017 Liu
et al.
2020 Pensia et al.]
2020) which have to date wverwhelmingly locused on the batch learning setting,
We consider the sotting streaming stochastic optimization (Bottou & Cun 2003 Bottou & Lecun 2005;
McMahan al.] 2013), which raises an additional difficulty coming from the fact that algorithms can see
each sample only once and must operate under an (dd) memory and complexity constraint for d-dimensional
optimization problems. A limited number of papers (Tsai et al. 2022 Nazin et al. 2019 Diakonikolas et al.
2022 propose theoretical guarantees for robust algorithms learning from streaming data.
This work introduces such an algorithm that learns from data on the fly and is robust both to heavy tails and outliers, with minimal computational overhead and sound thcoretical guarantees.
We consider the problem of minimizing a smooth objective
min (()) =- [c((( 6ER
(1)
using observations G(B, G)) of the unknown gradient VC()), based on samples (G))so received sequentially that include corruptions with probability < 1/2. Formulation ( is common to numerous machine learning problems where a loss function evaluating the fit of a model with parameters 0 on a sample Ç, the expectation E w.r.t the unknown uncorrupted sample distribution.
We introduce quantile-lippeed SGD (QC-SGD) which uses the iteration
0.t1 -+ .
TO: Ge) with 0g =min (IIGGO
(2)
where 3 > 0 is a constant step size and ae, is the clipping factor with threshold chosen as the p-th quantile To, (I (:)ll) with G(O,. (1) uncorrupted sample of V(())) and p E (0, (details will follow). Quantiles are natural choice of clipping threshold which allows to handle heavy tails (Rothenberg et al. 1964 Bloch 1966) and corrupted data. For instance, the trimmed mean offers robust and computationally efficient estimator of scalar expectation (Lugosi & Mendelson 2021). Since the quantile (p(() (e)ll) is non-observable, we introduce method based on rolling quantiles in Section 5 which keeps the procedure ((d) both memory and complexity-wise. The main benefit of QC-SGD 2 is to grant robustness to the presence of a proportion < 1/2 of corruptions in the stream gradient samples. This could not be achieved by previous clipped SGD methods (Gorbunov et al.) 2020 Tsai et al.] 2022 Sadiev et al., 2023 Nguyen et al. 2023). We also show that itcration (2) adaptive to heavy-tailed gradient variance and converges to a limit distribution with strong concentration properties.
Contributions. Our main contributions are follows:
For small enough and well-chosen p, we show that, whenever the optimization objective is smooth and strongly convex, QC-SGD converges geometrically to limit distribution such that the deviation around the optimum achieves the optimal dependence on 17.
In the non-corrupted case = 0 and with a strongly convex objective, we prove that a coordinated choice of 3 and ensures that the limit distribution is sub-Gaussian with constant of order (VB)). In the corrupted case v) >> 0, the limit distribution is sub-exponential.
For a smooth objective (non-convex) whose gradient satisfies an identifiability condition, we prove that the total variation distance between QC-SGD iterates and its limit distribution vanishes sub- linearly. In this case, the limit distribution such that the deviation of the objective gradient is optimally controlled in terms of 17.
Finally, we provide experiments to demonstrate that QC-SGD can be casily and efficiently imple- mented by estimating @p G(0,, ()]l)) with rolling quantiles. In particular, we show that the iteration is indeed robust. to heavy tails and corruption on multiple stochastic optimization tasks.
2

---

Published in Transactions on Machine Learning Research (10/2024)
Our theoretical results are derived thanks to modelling through Markov chains and hold under an Lg assumption on the gradient distribution with g > 1.
Related works. Convergence in distribution of the Markov chain generated by constant step size SGD, relatively the Wasserstein metric, was first established in (Dieuleveut. et al. 2020). Another geometric convergence result was derived in (Yu et al. 2021) for non-convex, non-smooth, but quadratically growing objectives, where a convergence statement relatively to weighted total variation distance is given and CLT is established. These papers do not consider robustness to heavy tails or outliers. Early works proposed stochastic optimization and parameter estimation algorithms which are robust to wide class of noise of
distributions Martin & Masreliez
1975
Polyak & Tsypkin 1979; [981
Price & VandeLinde] 1979 Stankovid
& Kovačević 1986 Chen et al.;
1987
Chen & Gao 1989 Nazin et al. 1992). where asymptotic convergence
guarantees are stated for large sample sizes. Initial evidence of the robustness of clipped SGD to heavy
tails was given by (Zhang et al. 2020) who obtained results in expoctation. Subsequent works derived high- confidence sub-Gaussian performance bounds under finite variance assumption (Gorbunov et al.) 2020;
Tsai et al., 2022) and later under an Ly assumption (Sadiev et al. 2023 Nguyen et al. 2023) with q I. A similar SGD clipping scheme to (2) is presented in (Seetharaman et al. 2020 however, in contrast to our work, they do not consider the robust setting and focus on experimental study while we also provide theoretical guarantees.
Robust versions of Stochastic Mirror Descent (SMD) are introduced in (Nazin et al, 2019 Juditsky et al, 2023). For a proper choice of the mirror map, SMD is shown handle infinite variance gradients without any explicit clipping (Nemirovskij & Yudin, 1983 Vural et al. 2022). Finally, (Diakonikolas et al. 2022) study heavy-tailed and outlier robust streaming estimation algorithms of the expectation and covariance. On this basis, robust algorithms for linear and logistic regression are derived. However, the involved filtering procedure is hard to implement in practice and no numerical evaluation of the considered approach is proposed.
Agenda. In Section 2 we set notations, state the assumptions required by our theoretical results and provide some necessary background on continuous state Markov chains. In Section 3 we state results for strongly convex objectives including geometric ergodicity of QC-SGD (Theorem the limit distribution and deviation bounds on the final estimate. In Section 4 we remove the convexily assumption and obtain a weaker ergodicity result (Theorem and characterize the limit distribution in terms of the deviations of the objective gradient. Finally, we present a rolling quantile procedure Section 5 and demonstrate its performance through a few numerical experiments on synthetic and real data.
characterizations of
2 Preliminaries
The model parameter space Rd endowed with the Euclidean norm || B(R)) the Borel o-algebra of Rd and we denote by MM (TR.) the set of probability measures over Rd We assume throughout the paper that the objective C is smooth.
Assumption 1. The objective C is L-Lipschit--smotth namely
L C(0') < ((0) + (VC()), 8) 2-11 1'
with L < +oo for all 0 ERd
The results from Section 3 below use the following
Assumption 2. The objective C is p-strongly conver, namely
C(0') > C(0)+ (VC()), 0) + " 1010-00 0112
with μ > 0 for all 0, e Rd.
An immediate consequence of Assumption 2 is the existence of a unique minimizer 8* arg minger L(B).
The next assumption formalizes our corruption model.
3

---

Published in Transactions on Machine Learning Research (10/2024)
Assumption 3 (n-corruption). The gradients (G(O).()))2) used in Iteration ( are sampled G( (i) U,Ō(0,) + (1-0))((,,))) where U. are ii.d Bernoulli random variables with parameter 1) 1 1/2, ((+)) Do(0,) with Do(0.) an urbilrary distribulion and GiO,, St) ~ Dr(O,) follows the true gradienl distribulion and is independent from the past given Oz.
Assumption 3 is an online analog of the Huber contamination model (Huber 1965 occur with probability y and where the distribution of corrupted samples Do (0,) (outliers) is not fixed and may depend on the current iterate lz On the other hand, (r,),) denotes the distribution of inliers. This
1992)
where corruptions
notation and dichotomy between inlicrs and outliers follows the example of (Locué & Lerasle 2017 Locué &
Lerasle 2019). Assumption X corresponds
addilève contamination (Diakonikolas & Kane, 2023 Section
1.2.2) where corruptions are only added to the data. A more general TV-contamination model allowing for true samples to be adversely removed is used in (Diakonikolas et al. 2022). Note however, that the latter mainly focuses on mean estimation. Note also that additive contamination remains realistic since it accounts for invalid entries occurring in the data stream even it. doesn't support entries being targeted and censored. The next assumption requires the true gradient distribution to be unbiased and diffuse.
Assumption 4. For all 0, non-corrupted gradient samples G(0,S) Dr) are such that
G(0,))= + E0:
(3)
where Eo is centered noise E|co [0] 0 with distribution 5vo,1 + (1 8)vo.2 where 5 > 0 and Vo.1, vo.2 are distribulions over R2d such that 18,1 admils a density he w.r.l. the Lebesgue measure salisfying
inf |
ho(w) > 2( 00
for all R > O, where x(-) is independent of 0.
In addition to the unbiased property, Assumption imposes that the noise distribution be exprossible the combination of two components, one of which must be diffuse with density satisfying minorization inequality. Note that this is a weak constraint since it is satisfied, for example, as soon as the noise admits a density w.r.t. Lebesgue's measure which is positive everywhere. This condition is similar to (Yul et al. 2021 Assumption 2.3) since both find their origin Markov chain minorization conditions (Meyn & Tweedie 1993, Section 5.2). These ensure that a chain properly explores state space and are a common way to prove Markov chain convergence (Rosenthal] 1995b Douc al., [2004] Meyn & Tweedie 1994; Baxendale 2005). Our last assumption formalizes the requirement of finite moment for the gradient error.
Assumption 5. There is > 1 such that for G(O,C) ~ Dz(0), we have
E B[llol| 10100 E[]]ã(,,)) V 0) 1/9 A, 0*1| + Bg
(4)
for all E Rd, where Ag, Bg > 0. When L is not strongly conver, we further assume that A, = 0.
The bound captures the case of arbitrarily high noise magnitude through the dependence on ||0 8" This consistent with convex optimization problems with I=Lipschitz-smoolh objectives (Assumption T where the norm of the gradient [V is bounded by L 10 0- Assumption 5 improves upon the
conditions used in (Gorbunov et al. 2020 Tsai et al., 2022 Gorbunov et al., 2023 Nguyen el al.) 2023) since these either required uniformly constant upperbound (independent of () or only considered the case q = 2 (finite variance). For non-strongly convex L, require Ag 0 since 8* may not exist.
Definition 1. If X is a real random variable, we say that K-sub-GGaan Gaussiann for K > if
E Eexp(X?X3) S Pk² for 1/KK
(5)
We say that X is K --suu--epponnntall for K> 0 if Eexp(\/x))<exx((A
S exp(AK) for all 0 05A
(6)
4

---

Published in Transactions on Machine Learning Research (10/2024)
The convergence results presented in this paper use the following formalism of contimuous state Markov chains. Given step size / >> O and quantile E (0, 1), we denote by Pa.p the Markov transition kernel governing the Markov chain (0:)e20 generated by QC-SGD, so that
P(1 E 0 = P3.p(02,
for 2 0 and A E B(RR). The transition kernel P3.p acts on probability distributions v E M2 through the mapping v - vP which defined, for all A E B(R*), by (P = -A (0,p(0, A)du(0) P(0++1 E A p). For 2 I, we similarly define the multi-step transition kernel P.pp which is such that P. (0,, A) P(Oc-n E A 02) and acts on probability distributions V E (R(R") through PP ( Finally, we define the total variation (TV) norm of a signed measure V as
/ f(0)v(d0)= sup v(A)
2||v/TTV
sup finis
inf "(A).
(7)
AEB(R4)
AEB(R*)
In particular, recover the TV distance between v1, 1/2 E Mi (TR))
drv(ui, u2) ||21 12/|TV sup AEB(RO)
(A) - (2(
The second equality reflects the fact that the TV distance between two probability measures corresponds the largest absolute difference between the probabilitics they assign to the same event. The TV distance is broadly used metric to quantify the convergence of Markov chains (Levin & Peres 2017 Baxendale 2005 Meyn & Tweedie 1993 Rosenthal 1995a besides the Wasserstein distance (Dieuleveut al. 2020
In the next scction, we will prove that the Markov chain defined by iteration 2 converges to unique invariant distribution in TV distance. This convergence mode will allow us to extrapolate the properties of the limit distribution on the iterates Og and thus derive -symmtypitoicc concentration bounds for them, see Corollaries 2 and below.
3 Strongly Convex Objectives
We are ready to state our convergence result for the stochastic optimization of strongly convex objective using QC-SGD with corruppee samples.
Theorem (Geometric ergodicity). such that
Let Assumptions
hold and ussume there quantile p E [n) v)
= (1 n)pp nL (1 p) p) A2(1
p(1 7)) 0.
(8)
Then, for step size B satisfying
1 B << 4 n22 24m 2 28A2 P L'
R
2
(9)
the Markov chain (0e):20 generated by QC-SGD with porameters and p converges geometrically to a unique invariant measure Ta.p for any initial 0, E Rd, there is p < and M < such that after T iterations
|10,, PT. - Mp" (1 + 110 13))
where 6a, is the Dirac measure located at On-
The proof of Theorem is given in Appendix D.3 and relies on the geometric ergodicity result of (Meyn & Tweedie 1993] Chapter 15) for Markov chains with a gcomctric drift property. A similar result for quadratically growing objectives was established by (Yu et al., 2021) and convergence w.r.t. Wasserstein's 's metric was shown in (Dieuleveut et al. 2020) assuming gradient co-coercivity. However, robustness was not considered in these works. Theorem essablishes the iteration's 's convergence a unique invariant measure Tgpp. The properties of this limit distribution will be explored in the sequel. The restriction p E [n, 1-,1 comes from the consideration that other quantiles are not estimable in the event of n-corruption. Condition (8) is
5

---

Published in Transactions on Machine Learning Research (10/2024)
best interpreted for the choice p 17 in which case it translates into 1/ ( + Ag)) implying that it is verified for y small enough within limit fixed by the problem conditioning. A similar condition with q = 2 appears in (Diakonikolas et al. 2022 Theorem E.9) which uses finite variance assumption.
When is satisfied, one clearly has that x = O(n). Considering = 2 for simplicity and taking the maximum allowed corruption rate this case 7 = On22/ + A2)2) leads to an upperbound on the step-size 3 of order O(u/(z² + A&) 1/).. While the condition 3 (L/L) is standard in smooth optimization, the additional condition in terms of A, ensures that the noise introduced to the iteration by the gradient samples does not cause it to diverge.
The constants M and P controlling the geometric convergence speed in Theorem depend on the parameters B, p and the initial 0g Among choices fulfilling the convergence conditions, it is straightforward that greater step size 3 and 8g closer to l lead to faster convergence. However, the dependence in p is more intricate and should be evaluated through the resulting value of k. We provide a more detailed discussion about the value of p in Appendix C
The choice p 1 77 appears to be ideal since it leads to optimal deviation of the invariant distribution around the optimum 0" which is the essence of our next statement.
Proposition 1. Assume the same as in Theorem 1 and condition
with the choice p = 1 - 7). For step
size 3 salisfying 9 q 2 2, and addilionally:
B 12 2-/2////0 ////n,
(10)
for 0 ~ TB,1-n, we have the following upper bound:
Gry Grjz-1/9B,
E - 0-133
R
Proposition [ is proven in Appendix D.4 proof and can be found in Appendix D.5 Proposition [ may be compared to (Yu et al. 2021 Theorem 3.1)
An analogous result holds for q (1,2) but requires different
which shows that the asymptotic estimation error can be reduced arbitrarily using small step size. However, this is impossible in our case since we consider corrupted gradients. The performance of Proposition D is best discussed in the specific context of linear regression where gradients are given as G(O, (X, = x(X Y-
for samples X, Y E Rd x R such that Y = T 6r + with a centered noise. In this case, a finite moment of order k for the data implics order k/2 for the gradient corresponding to an 17' 1/2h rate in Proposition 1 Since Assumption does not include independence of the noise e from X, this corresponds to the negatively correlated moments assumption of (Bakshi & Prasad. 2021) being unsatisfied. Consequently, Proposition 1 is information therreticlly optimal in 77 based on (Bakshi & Prasad, 2021, Corollary 4.2). Nonetheless, the dimension dependence through Bg remains poor since we have Bg ~ Vd in general because the Euclidean norm is used in Assumption 5 This dimension dependence may be improvable by using the quantiles supl|-/=1 (KG(O.,)))) v)l) as clipping thresholds and adapting ideas from (Catoni & Giulini 2018 in the analysis. However, exploring this method beyond our scope as the involved estimations lor all ||||| = would be excessively sample hungry and computationally heavy for stochastic optimization. the gradient is sub-Gaussian with constant K, we would have Bg S K /4 for q 2 (see (Vershynin 2018) for reference). in which case, the choice = log(1/n) recovers the optimal rate in n/log((/n) for the Ganssian case.
We now turn to showing strong concentration propertics for the invariant distribution Tz2z. For this purpose, we restrict the optimization bounded and convex set θ Rdd and replace Iteration (2) by the projected iteration
p = To (9, ag, (G(,,,G))
(11)
where He is the projection onto θ Assuming that the latter contains the optimum A E O one can chock that the previous results continue to hold thanks to the inequality
(0) - 8* (0) - le(())) < 1011
which results from the convexity of θ. The restriction of the optimization to a bounded set allows us uniformly bound the clipping threshold 7a, which is indispensable for the following result.
6

---

Published in Transactions on Machine Learning Research (10/2024)
Proposition 2.
! consider projected QC-SGD diam(@) the diameler of @ and Bg A Bq.
In the setting of Theorem
11 and let 7 supeee To, D
Consider the non-corrupted 17 0 and set the quantile p such that p 2 1 (B8p)xr1 Then, for f ~ Rp the variable |00 l1 is uub-Gaussian in the sense of Definition with constont
23(B + 72)
K 41
pp
Consider the corrupted case > O, and set the quantile E [n, 11.1-1i, such that Inequality ( holds. Then, for Rg the variable 1 - cob-expomential in the sense of Definition 1 with constant
K 7 + (1 p) 1/1
ри
The proof can be found in Appendix D.6 The strong concentration properties given by Proposition 2 for the invariant distribution appear to be new. Still, the previous result remains asymptotic in nature. High confidence deviation bounds for iterate 0g can be derived by leveraging the convergence in Total Variation distance given by Theorem | leading to the following result.
Corollary 1. In the setting of Proposition in the absence of corruption n = 0, after T iterations, for 0, we have
2 log(e/6)
(( 110- - 0 4 B 72
S 58+p (1+ 1100 - 10
Choosing a smaller step size ,3 in Corollary ! allows to improve the deviation bound. However, this comes at the cost of weaker confidence bocause of slower convergence due to a greater p. See Appendix C for a discussion including possible compromise. Corollary 1 may be compared to the results of (Gorbunov al., 2020 Tsai al. 20222] [Sadiev et al., 2023 Nguyen et al., (202)) which correspond 8 1/T and have a similar dependence the dimension through the gradient variance. Although their approach is also based gradient. clipping, they use different thresholds and proof methods. In the presence of corruption, the invariant distribution is not sub-Gaussian. This can be seen by considering the following toy Markov chain:
(xx+t + w.p.
1-
X
X,
w.p.
where < 1, 0 are constants and & is positive random noise. Using similar methods to the proof of Theorem 1 one can show that (Xt)220 converges (for any initial Xo) to invariant distribution whose moments can be shown to grow linearly, indicating sub-exponential distribution and excluding a sub- Gaussian one. We provide additional details for the underlying argument in Appondix D.7, For the corrupted case, the sub-exponentia property stated in Proposition 2 holds with constant K of order F/μ, which is not satisfactory and leaves little room for improvement due the inevitable bias introduced by corruption. Therefore, we propose the following procedure in order to obtain high confidence estimate, similarly to
Corollary I
Algorithm uses ideas from Hsu & Sabato 2016) (see also Minsker 2015 Juditsky et al. 2023 and combines the collection of weak estimators (0)) (0"")ee[n) (only satisfying L2 bounds) into strong one with sub-exponential deviation. This is done by picking 0/ which is such that the median of its distances to other estimators (6) T[N/2] is minimal. The aggregated estimator 0 satisfies the high probability bound given in the next result.
Consider 0 given by Algorithm with Corollary 2. Assume the same as Theorem i and Proposition 1
the assumption that the gradient sample sels used for each (0(m) nE[N] in Equation (12) are independent. For 8 8>0 0, if N 16 161og(1/6) and T satisfies
T N 1og(155(1 + 0-11))) log(1/p).

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 1: Aggregation of cycling iterates
Input:
Step size 3 > O, quantile index p E (0, 1), initial parameter dg E O horizon T and number of concurrent iterates N 1. Optimize multiple parameters 0!" ...., w starting from common 0g 06 for
[N] =: [1 and T steps = 0, ......T T using the following cycling iteration:
0/
()())
a a
) m ..)
i - mod N,
(12)
otherwise.
2 Compute the pairwise distances rij = 10 - 0 for i,j [N].
3 For i e [N]] let y(0) E R be the vector ri.: == Ii,,,..., Vi,N] sorted in non decreasing order.
Compute the aggregated estimator as 0 -= 0 with ī arg min [N//2]"
(8)
return 0
then, with probability at least 5, we have
27m 1 Bg 10-00 1
(13)
K
We obtain high confidence version of the bound in expectation previously stated in Proposition 1 As argued before, the above bound depends optimally on Similar bounds to 13 are obtained for 2 in (Diakonikolas et al. 2022) for streaming mean estimation, linear and logistic regression. Their results enjoy better dimension dependence but are less general than ours since we handle the case 9 E (1,2) and consider strongly convex objectives more broadly. In addition, our results further extend non-convex objectives detailed in the next section. Finally, the implementation of the algorithm in (Diakonikolas et al. 2022 is not straightforward whereas our method is quite easy to use (see Section 5
4 Non-Convex Objectives
In this section, we drop Assumption 2 and consider the optimization of possibly non-convex objectives. Consequently, the existence of a unique optimum 0 and the quadratic growth of the objective are no longer guaranteed. This motivates us to use uniform version of Assumption 5 with A, = 0 since the gradient is no longer assumed cocrcive and its deviation moments can be taken as bounded. In this context, we obtain the following weaker (compared to Theorem
1 ergodicity result for QC-SGD.
Theorem (Ergodicity). Let Assumplions
i 4 and 5 hold with Ag 0 (uniformly bounded moments) Do is finite. Let (6:)czo be the Markov chain generated by
and let C be an objective such that inf, C(0)
QC-SGD with step size B and quantile p [n. 7)- Assume that and B such that 3p(1 nn)/4 L8 + and that the subset of & given by
{0: |100 (1-
27)
(14)
p(1 ()p(1)))ppppppp n)/4 LB n)
is bounded. Then, for any initial 6, E Rd, there exists M < +o0 such that after T. iterations
M T
|00 3.p TBP rV
(15)
where TB. is a unique invariant measure and where 6a, is the Dirac measure located 0g.
The proof is given Appendix D.10 and uses ergodicity results from Meyn Tweedic 1993 Chapter 13).
Theorem provides convergence conditions for an SGD Markov chain on smooth objective a robust
setting. We are unaware of anterior results of this kind in the literature. Condition (14 requires that the
8

---

Published in Transactions on Machine Learning Research (10/2024)
set where the true gradient norm is smaller than the estimation error is bounded. This aims to exclude the possibility that the iteration gets trapped within this set and keep using unreliable gradient estimates causing it to diverge. The result is stronger when the upperbound in (14) is smaller. Note that setting close to 1-11 7 increases the clipping threshold and the cstimation error as a consequence, making this condition harder satisly. On the other hand, using 3 = (1)LL) and a more conservative value of p makes the upperbound of order (BB)) and condition 14 casier to satisfy. Observe that, for no corruption (n = 0), the condition always fulfilled for some and p. Note also that without strong convexity (Assumption 2 convergence occurs at slower sublinear rate which is consistent with the optimization rate expected for smooth objective (see [Bubeck] 2015 Theorem 3.3)).
As previously, we complement Theorem 1 with a characterization of the invariant distribution.
Proposition 3. Under the conditions of Theorem & assume that the choice p 1 ny is such that the set 14 is bounded. For step size B S 1/² [L, the stationary measure 0 ~ R8,1-n satisfies
5n B
p(1 (11-n)(ppp111 - n)/4 (3) [[(0)
(16)
L3 -
The statement of Proposition is clearly less informative than Propositions and 2 since it only pertains to the gradient rather than, for example, the excess risk. This is due to the weaker assumptions that do not allow to relate these quantities. Still, the purpose remains to find a critical point and is achieved up to 10/1-1/1) precision according to this result. Due to corruption, the estimation error on the gradient cannot be reduced beyond 121)21//9) (Prasad et al., 2020: Hopkins Li 2018 Diakonikolas & Kane 2019). Therefore, one may draw a parallel with a corrupted mean estimation task, in which case, the previous rate is, in fact, informatiion-theoretialllll optimal.
5 Implementation and Numerical Experiments
The use of the generally unknown quantile ()(()((0, in QC-SGD constitutes the main obstacle to its implementation. For strongly convex objectives, one may proxy such allê, Oret + 6 with positive o, b and 0 E Rd an approximation of 6* serving as reference point. This choice is consistent with Assumptions and see Lemma in Appendix For instances of Problem [ defined with an
Algorithm 2: Rolling QC-SGD
Input: Step size 8 >> O, quantile index
p (0,1) initial parameter Og E Rd, Tunif > O, buffer B of size S and horizon T.
Fill B with S - values equal to Tunif.
for t= 1....77 T do
Draw a sample G(O,, Gi) and add |[G(O,, Ge)ll to B.
Qp + [pS] rank element of B.
O++1 +- 0, (el, (t), Qp) Delete the oldest value in B.
return OT
asymptotically linear function such as the logistic, hinge Huber's loss, constant threshold can be used since the gradient is priori uniformly bounded, implying the same for the quantiles of its deviations. In practice, we propose simpler and more direct approach: use rolling quantile procedure, described in Algorithm 2 The latter stores the values ([(G(0-s,, (r-)))l in a buffer of size S E No and replaces ()( (ll)) in QC-SGD by an estimate Q, which is the [pS]-th order statistic in the buffer. Note that only the norms of previous gradients are stored in the buffer, limiting the memory overhead to O(S). The computational cost of Q, can also be kept O(S) per iteration thanks to a bookkeeping procedure (sce A Appendix B
9

---

Published in Transactions on Machine Learning Research (10/2024)
Note that, since Algorithm 2 uses the corrupted samples G(8,, (t) rather than the true ones G(O,, St) to estimate the quantiles, a more conservative upperbound of roughly p S 1 - 2q should be respected when an estimate of 1 is available. Otherwise, one may default to = 1/2 as an imitial guess and adapt based on performance. In practice, our experiments show that relatively low values within p E [0.1,0.2] are best for strongly convex objectives while higher values are affordable in other cases. See Appendix for more details.
We implement this procedure for few tasks and compare its performance with relevant baselines. We do are
not include comparison with (Diakonikolas et al. 2022) whose procedure has no implementation aware of and is difficult to use in practice. Indeed, the algorithm in question heavily depends on several problem parameters and involves a filtering procedure which requires multiple passes on large data mini- batches making it impractical for the streaming setting. Moreover, a number of special methods are required to mitigate the costs of the matrix operations needed in the original procedure making the algorithm's implementation even more involved.
Our experiments on synthetic data consider an infinite horizon, dimension d 128, and constant step size for all methods.
Linear regression. We consider least-squares linear regression and compare RQC-SGD with Huber's estimator (Huber 1973) and clipped SGD (designated as CClip(A)) with three clipping levels Ao vd for À {0.8, 1.0, where mmax is a fixed data scaling factor. These thresholds provide rough estimate of the gradient norm near the optimum 8*. We generate covariates X and labels Y both heavy-tailed and corrupted. Corruption in the data stream is generated according to Assumption B with outliers represented either by aberrant values or fake samples Y = X Otake + using a false parameter Ojake, see Appendix B for further details on data generation and fine luning of the Huber parameter. All methods are run with constant step size and averaged results over 100 runs are displayed on Figure ! (top row).
As anticipated, Huber's loss function is not robust to corrupted covariates. In contrast, using gradient clipping allows convergence to meaningful estimates. Although this holds true for constant threshold, Figure I shows it may considerably slow the convergence if started away from the optimum. In addition, the clipping level also affects the final estimation procision and requires tuning. Both of the previous issues are well addressed by RQC-SGD whose adaplive clipping level allows fast progress of the optimization and accurate convergence towards a small neighborhood of the optimum.
Logistic regression. We test the same methods logistic regression. Huber's baseline is represented by the modified Huber loss (also known as quadratic SVM (Zhang, 2004)). We generate data similarly to the previous task except for the labels which follow Y ~ Bernoulli (x)))) with a the sigmoid function. Corrupled labels are either uninformative, flipped or obtained with a fake Otake (see details in Appendix B Results are displayed on the bottom row of Figure !
As previously, Huber's estimator performs poorly with corruption. However, constant clipping appears to be better suited when the gradient is bounded, so that the optimization is less affected by its underestination. We observe, nonetheless, that higher clipping level may lead to poor convergence properties, even at a low corruption rate. Note also that the constant levels we use are based on prior knowledge about the data distribution and would have to be fine tuned in practice. Meanwhile, the latter issue is well addressed by quantile clipping. Finally, notice that no algorithm truly approaches the true solution for this task. This reflects the difficulty of improving upon Proposition 3 which only states convergence to a neighborhood where the objective gradient is comparable to the estimation error in magnitude.
Classification with shallow networks. Finally, we evaluate the performance on the task of training a single hidden layer neural network classifier on some real datasets which corresponds to a non-convex optimization problem. To handle multiclass data, we use the cross entropy loss and replace Huber's baseline with plain SGD for simplicity. We define constant clipping basclines using thresholds given by the quantiles of order p = 0.25, 0.5, and 0.75 of the norms of a batch of gradients the beginning of the optimisation. Due to the greater sensitivity to corruption observed in this case, we set v) = 0.02 and use p 0.9 for RQC-SGD.
10

---

Published in Transactions on Machine Learning Research (10/2024)
n) = 0.02
= 0.06
n= 0.1
Co dg- Me mit Xemjje
Mo wid e00n 30 20mepp
6p- Ne mage vp0n 20m000
10
10
00'
10
110:
0.1
10000
20000
10000
20000
10000
20000
RQC-SGD
=m/ HUBER a CClip(A 0.8)
-+ + CClip(A 1.0)
CClip(A 1.2)
30
30
20
20
10-
10000
20000
10000
20000
10000
20000
Figure 1: Evolution of |00 - 0*1 on the tasks linear regression (top row) and logistic regression (bottom row) averaged over 100 runs at increasing corruption levels (error bars represent half the standard deviation). Estimators based Huber's loss are strongly affected by data corruption. SGD with constant clipping thresholds is robust but slow to converge for linear regression and requires tuning for better final precision. RQC-SGD combines fast. convergence with good final precision thanks to its adaptive clipping strategy.
codra
sensorless
covtype
0.68
2.6
1.6
2.4
0.66
1.4
2.2
Loss
0.64
2.0
1.2
1.8
0.62
1.0-
1.6
0.60
1.4
0.8
400000
800000
25000 50000 75000 100000
0.00
0.25
0.50
0.75
1.00
RQC_ SGD SGD
CClip(p=0.25) CClip(p=0.5)
CClip(p=0.75)
1e6
Figure 2: Evolution of the test loss (y-axis) against itcration (æ-axis) for the training of single hidden layer network on different real world classification datasets (average over 20 runs). We observe more consistent and stable objective decrease for RQC-SGD whereas constant clipping baselines are slower and may fail to converge.
We train all methods with one sample per iteration using equal step sizes and evaluate them through the test loss. We provide further results and experimental details in Appendix B Results are displayed on Figure 2
Unsurprisingly, standard SGD not robust to corrupted samples and, while using a constant clipping level helps keep the optimisation on track, the experiments show that careful tuning may sometimes be necessary prevent divergence. On the other hand, the adaptive clipping levels used by RQC-SGD allow to make the iteration faster and more resilient. to corruption. This leads to optimization path with consistent
11

---

Published in Transactions on Machine Learning Research (10/2024)
decrease of the objective. Moreover, also observe that RQC-SGD allows for better control of the asymptotic variance of the optimized parameter compared to constant clipping.
6 Conclusion
We introduced new clipping strategy for SGD and proved that it defines stochastic optimization procedure which is robust to both heavy tails and outliers in the data stream. We also provided an efficient rolling quantile procedure to implement it and demonstrated its performance through numerical experiments on synthetic and real data. Future research directions include improving the dimension dependence our bounds, possibly by using sample rejection rules or by considering stochastic mirror descent (Nemirovskij & Yudin 1983 Beck & Teboulle, 2003) clipped with respect a non Euclidean norm. This may also procure robustness to higher corruption rates. Another interesting research track is the precise quantification of the geometric convergence speed of the Markov chain generated by constant step size SGD on strongly convex objective.
Acknowledgments
This research is supported by the Agence Nationale de la Recherche as part of the "Investissements d'avenir" program (reference ANR-19-P3IA-00001; PRAIRIE 3IA Institute).
References
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments.
In Proceedings of the Eoenty--iighte Annuol ACM Symposium Theory of Computing, pp. 20 20-29, 1996.
Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceed- ings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 102-115, 2021.
Martyna Bator. Dataset for Sensorless Drive Diagnosis. UCI Machine Learning Repository, 2015. DOI: https://doi.orr/1000
Peter H Baxendale. Renewal theory and computable convergence rates for geometrically ergodic Markov chains. The Annals of Applied Probubility, 15(1B):700 738, 2005.
Amir Bock and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167 175, 2003.
Witold Bednorz. The Kendall's Theorem and its Application to the Geometric Ergodicity of Markov Chains. 1481, 2013.
arXiv preprint
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive Algorithms and Stochastic Approcima- tions, volume 22. Springer Science & Business Media, 2012.
Kenneth S Berenhaut and Robert Lund. Geometric renewal convergence rates from hazard rates. Journal of Applied Probability, 38(1):180-194, 2001.
Jock Blackard. Covertype. https::/ddi.org//iie /C5KK5N.
UCI Machine
Learning Repository, 1998.
DOL:
Joseph K Blitzstein and Jessica Hwang. Introduction to probability. Cre Press, 2019.
D. A. Bloch. A note on the estimation of the location parameter of the cauchy distribution. Journal of the American Statistical Association, 61:852-855 1966.
Léon Bottou and Yann Cun. Large scale online learning. S. Thrun, L. Saul, and
B. Schölkopf (ods.), Advances Neural Information Processing Systems, volume MIT Press, 2003.
URL https://prroeeedings.u neurips......... httprr/pp.cc/pppe..eee/////ppp/p fites//apprr/00///1//
12

---

Published in Transactions on Machine Learning Research (10/2024)
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. STAM revieu, 60(2):223-3)) 2018.
Léon Bottou and Yann Lecun. On-line learning for very large data sets. Applied Stochastic Models in Business and Industry, 21:137 - 151, 03 2005. doi: 10.1002/asmb.53k
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundalions and TrendsI in Machine Learning, 8(3-4):231 357, 2015.
Hervé Cardot, Peggy Cénac, and Pierre-André Zitt. Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm. Bernoulli, 19(1):18 43, 2013. doi: 10.3150/11-BE13900 URL htttpe///abi.orr////311///11--11
Hervé Cardot, Peggy Cénac, and Antoine Fodichon-Baggione Online estimation of the geometric median in Hilbert spaces: Nonasymptotie confidence balls. The Annals of Statistics, 45(2):591 614, 2017. doi:
10.1214/16-AOS4400 URL https:://bi..rrg//// 1tt.:///0/.....11111111111 1214/16-A0S148
Olivier Catoni. Challenging the empirical mcan and empirical variance: A deviation study. Annales de I'Instiuu Henri Poincaré, Probabilités et Statistiques, 48(4):1148 - 1185, 2012. doi: 10.1214/11-AIHPP
URL https: 100/ 1211111-111AH4555
Olivier Catoni and Ilaria Giulini. Dimension-free pac- bayesian bounds for the estimation of the mean of random vector. Xrx preprint ar 1iv:1802.04300 2018.
Han-fu Chen and AIJJUN Gao. Robustness analysis for stochastic approximation algorithms. Stochaslics and Stochastic Reports, 26(1):3 20, 1989.
Han-Fu Chen, Lei Guo, and Ai-Jun Gao. Convergence and robustness of the Sobinss-oore algorithm truncated at randomly varying bounds. Stochastic Processes and their Applications, 27:217-231, 1987.
Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. Fast mean estimation with sub- gaussian rates. In Conference on Learning Theory, pp. 156-806. PMIRR 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neurol Information Processing Systems, 27, 2014.
Jules Depersin and Guillaume Lecué. Robust sub-Gaussian estimation of a mean vector nearly lincar time. The Annols of Slatistics, 50(1):511 536, 2022. doi: 10.1214/11-0022188. URL https://doi.org
10. 1214/21-1102111
Mass Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensionall robust statistics. arXiv preprinl Xrxi::9911.000 2019.
Maas Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cambridge university
press, 2023.
Ilaas Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability, SIAM Journal on Computing, 48 (2):742-864 864, 2019.
Tlas Diakoníkolas, Daniel M Kane, and Ankit Pensia. Outlier robust mean estimation with subgaussian rates via stability. Advances in Neural Information Processing Systems, 33:1830 1840, 2020.
Mlaas Diakonikolas, Daniel M Kane, Ankit Pensia, and Thanasis Pittas. Streaming algorithms for high- dimensional robust statistics. In International Conference on Machine Learning, pp. 5061-5117. PMLR, 2022.
Aymeric Diculeveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1348 1382, 2020. doi: 10.1214/ 19- AO$1850. https://:: 101/110.121//99-0011555
13

---

Published in Transactions on Machine Learning Research (10/2024)
R. Douc, E. Moulines, and Jeffrey S. Rosenthal. Quantitative bounds convergence of time- inhomogeneous Markov chains. The Annals of Applied Probability, 14(4):1643 - 1665, 2004. doi: URL https://doi.org org/10.
htt.://.....ogg......00000000100 124400000000000000000000
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042-
15053, 2020.
Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability convergence for composite and distributed stochastic minimization and variational inequalities with heavy-tailed noise. arXiv preprint arXiv:2310.01800 2023.
Frank R. Hampel. A general qualitative definition of robustness. The Annals of Mathematical Statistics, 42 (6):1887-1896, 1971.
Abdelhakim Hannousse and Salima Yahiouche. Web page phishing detection. Mendeley Data, 2, 2020-
Matthew Holland and Kazushi Tkeda. Better generalization with less data using robust gradient descent. Tn Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2761 2770. PMLR, 09-15 Jun 2019. URL https://proceedingg mlr
Samuel B. Hopkins. Mean estimation with SabbGaassian rates in polynomial time. The Annals of Statistics, 48(2):1193 1213, 2020. doi: 10. 10.1214/19-A0S1443 URL
Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1021-1034, 2018.
Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. The Journal of Machine Learning Research, 17(1):543-35 582, 2016.
Peter J Huber. A robust version of the probability ratio test. The Annals of Mathematical Statistics, pp. 1753-1758, 1965.
Peter J Huber. The 1972 wald lecture robust statistics: A review. The Annals of Mathematical Statistics, 43(4):1041-1067, 1972.
Peter J. Huber. Robust Regression: Asymptotics, Conjectures and Monte Carlo. The Annals of Statistics, 821, 1973. doi: 10.1214/aai /as/ 1176342503. URL https://doi.. 11t.://111111///1111111111111111
1(5):799
Peter Huber. Robust estimation of location parameter. Breakthroughs in statistics: Methodology and distribution, pp. 492 518, 1992.
Daniel Jerison. Quantitative convergence rates for reversible Markov chains via strong random times. arXiv preprint 190: 0644,, 2019.
Mark R Jerrum, Leslic G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Compuler Science, 43:169 188, 1986.
Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
Anatoli Juditsky, Andrei Kulunchakov, and Hlib Tsyntseus. Sparse recovery by reduced variance stochastic approximation. Information and Inference: A Journal of the IMA, 12(2):851-896, 2023.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Harold Kushner and G. George Yin. Stochastic Approzimation and Recursive Algorithms and Applications, volume 35. Springer New York, NY, 2003.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Guanghui Lan. First- Order and Stochastic Optimization Methods for Machine Learning, volume 1. Springer, 2020.
Guillaume Lecué and Matthieu Lerasle. Learning from mom's principles: Le cam's approach. Processes and their applications, 129(11):4385-44 44100, 2019.
Slochastic
Guillaume Lecué and Matthieu Lerasle. Robust machine learning by median-of-means. Theory and practice. The Annals of Statistics, 48, 11 2017. doi: 11121411--0SSII
Zhixian Lei, Kyle Luh, Prayaag Venkat, and Fred Zhang. A fast spectral algorithm for mean estimation with sub-Ganssian rates. In Conference on Learning Theory, pp. 2598 2612. PMLR, 2020.
David Levin and Yuval Peres. Markow chains and micing times, volume 107. American Mathematical Soc., 2017.
Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis. High dimensional robust sparse regression. In International Conference on Artificial Intelligence and Statistics, pp. 411 421. PMLR, 2020.
Gábor Lugosi and Shahar Mendelson. Sub-gaussian estimators of the mean of random vector. The Annals of Statistics, 47(2):783-794 2019.
Gábor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: The optimality of trimmed mean. The Annals of Statistics, 49(1):393 410, 2021. doi: 10.1214/00-001990 URL https://doi. org/10 10.11..2211 2214/20-AAS196
Robert B Lund, Sean P Meyn, and Richard L Tweedie. Computable exponential convergence rates for stochastically ordered Markov processes. The Annols of Applied Probability, 6(1):218-223) 1996.
Siyuan Ma, Racf Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In International Conference on Machine Learning, pp. 3325-3334. PMLR, 2018.
Rainer Martin and Carl Masreliez. Robust estimation via stochastic approximation. IEEE Transactions on Information Theory, 21(3):263 271, 1975. doi: 11.100//TIT1195.1053333
H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: view from the trenches. Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data måning, pp. 1222-1230, 2013.
Sean Meyn and Richard L Tweedie. Markow Chains and Stochaslic Slability. Springer London, 1993.
Sean P Meyn and Robert L Tweedie. Computable bounds for geometric convergence rates of Markov chains.
The Annals of Applied Probability, pp. 981-1011, 1994.
Stanislav Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli, 21(4):2308 2335,
2015. doi: 10.3150/14 14 BEJ645. URL https: httg::///oo.orr//1.oo wtt.
Alexander V Nazin, Boris T Polyak, and Alexandre B Tsybakov. Optimal and robust kernel algorithms for passive stochastic approximation. IEEE Transactions on Information Theory, 38()):1577-1583, 1992.
Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky. Algorithms of robust stochastic optimization based mirror descent method. Automation and Remote Control, 80: 1607 1627, 2019.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem Complezity and Method Efficiency in Optimization. A Inley-Intersciience publication. Wiley, 1983. ISBN 9780471103455. URL https:
//books. //bboks.google.ff.. htt.://r/bbooo......lllAAAAA.A
Yurii Nesterov. Introductory Lectures on Conver Optimization: Basic Course. Springer Publishing Com-
pany, Incorporated, edition, 2014. ISBN 1461346916.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Le Nguyen. High probability convergence of clipped-SGD under heavy-tailed noise. arxiv preprint 2Xxx:2302.05437, 2023.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv preprint arXiv:2009. 12976, 2020.
Boris Teodorovich Polyak and Yakov Zalmanovich Tsypkin. Adaptive estimation algorithms: convergence, optimality, stability. Automation and Remote Control, 40(3):378 389, 1979.
Boris Teodorovich Polyak and Yakov Zalmanovich Tsypkin. Robust pseudogradient adaptation algorithms. Automation and Remote Control, 41(00):1444-1400 1981.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82, 2018.
Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A robust univariate mean estimator is all you need. In International Conference on Artificial Intelligence and Statistics, pp. 1034-4044, PMLR, 2020.
E Price and V VandeLinde. Robust estimation using the robbins-monro stochastic approximation algorithm. IEFE Transactions on Information Theory, 25(6):698-770 -0499 1979.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.56; 2011.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annols of Mathematical Statistics, pp. 400-407, 1951.
Gareth O Roberts and Richard Tweedie. Rates of convergence of stochastically monotone and continuous time Markov models. Journal of Applicd Probability, 37(2):359-375 2000.
Byron Roc. MiniBooNE particle identification. 1ttpg///1.244///500000
UCI Machine Learning Repository, 2010. DOT:
Jeffrey S Rosenthal. Convergence rates for Markov chains. Siam Review, 37(3):387-44) 1995a.
Jeffrey S Rooenthal, Minorization conditions and convergence rates for markov chain monte carlo. Journal of the American Statistical Association, 90(430) :558 566, 1995b.
Thomas J. Rothenberg, Franklin M. Fisher, and C. B. Tilanus. A note estimation from cauchy sample, Journal of the American Statistical Association, 53000)):460-463, 1964. doi: 10. 10.10800000 1599000661149. 1964. 10482170. URL https:///wwet http://wwwwafffooonn/.//oooo wtt.a//oinne....coooo//oaaaaaaaa
10482170
Peter J Rousseeuw and Mía Hubert. Robust statistics for outlier detection. Wiley Interdisciplinary Reviews:
Dala Mining and Knowledge Discovery, 1(1):73 79, 2011.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochastic opti- mization and variational inequalities: the case of unbounddd variance. Tn International Conference on Machine Learning, pp. 29563-29648. PMLR, 2023.
Prem Seetharaman, Gordon Wichern, Bryan Pardo, and Jonathan Le Roux. Autoclip: Adaptive gradient clipping for source separation networks. In 2020 IEEE 30th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2020.
Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub-gradient solver for svm. In Proceedings of the 24th International Conference Machine Learning, pp. 807-814 -84, 2007.
Shai
Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In Conference Learning Theory, volume 2, pp. 5, 2009.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Srdjan S Stanković and Branko D Kovačevié. Analysis of robust stochastic approximation algorithms for process identification. Automalicn, 22(4))488-455 1986.
Che-Ping Tsai, Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. Heavy-tailed streaming statistical estimation. In International Conference Artificial Intelligence and Statisties, pp- 1251-1282. PMLR, 2022.
John Wilder Tukey, A survey of sampling from contaminated distributions. Contributions to Probability and Statisties, pp. 448-485, 1960.
Andrew V Uzilov, Joshua M Keegan, and David H Mathews. Detection of non-coding rnas on the basis of predicted secondary structure formation free energy change. BMC bioinformalics, 7(1):1-33 10::1-0,,-00 2006.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science, vol- ume 47. Cambridge universily press, 2018.
Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Conference Learning Theory, pp. 65-102. PMLR, 2022.
Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. An analysis of constant step size SGD the non-convex regime: Asymptotic normality and bias. Advances Neural Information Processing Systems, 34:4231-4244 2021.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neurol Information Processing Systems, 33:15383 15393, 2020.
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the Twenty-Fite First International Conference on Machine Learning, pp. 116, 2004.
17

---

Published in Transactions on Machine Learning Research (10/2024)
Supplementary Material
Robust Stochastic Optimization via Gradient Quantile Clipping
A
Additional experimental results
miniboone
phishing
0.70
0.75
0.68
0.73
0.65
0.70
Loss
0.62
0.68
0.60
0.65
0.58
0.63
0.55
0.60
100000
200000
10000
20000
30000
MQC_SGD
SGD
CClip(p=0.22)
CClip(p=0.55 .... CClip(p=0.75)
Figure 3: Evolution of the test. loss (y-axis) against iteration / (I-axis) for the training of a single hidden layer network on additional real world classification datasets (average over 20 runs).
Classification with shallow networks. We performed the same experiment using two additional datasots. The results are displayed on Figure and corroborate our statements in the main paper.
Expectation estimation. We estimate the expectation of a random vector X by minimizing the objectivve ((0) = 110-00112 with dr =] using a stream of both corrupted and heavy-tailed samples, see Appendix B for details. We run RQC-SGD (Algorithm 2 and compare it an online version of geometric and coordinate- wise Median-Of-Menn minimize In objective (see Appendix By. Although these estimators
(GMOM and CMOM (Carrot et al., 2017 2013) which use block sample means
a priori not robust to n-corruption, meaningful by limiting r to 4% and using blocks of 10 samples. Thus, blocks are corrupted with probability < 1/2 so that the majority contains only true samples. Figure g displays the evolution of ||0, 0 0' for each met averaged over 100 runs for increasing and constant step size. We also display a single run for = 0.04. We observe that RQC-SGD is only weakly affected by the increasing corruption whereas the performance of GMOM and CMOM quickly degrades with y, leading to unstable estimates.
ensure that their estimates
B Experimental details
As previously mentioned, the dimension is set to d = 128 in our experiments with synthetic data. We also set Omin = 1 and Fmax = 5 as minimum and maximum scaling factors. For all tasks and algorithms, the optimization starts from Og
Bookkeeping in RQC-SGD The buller in Algorithu 2 stores values in sorted order along with their "ages". The most recent and oldest values have ages 0 and S 1 respectively. At each iteration, a new gradient received, all ages are incremented and the oldest value replaced by the new one with age The latter is then sorted using one iteration of insertion sort. The estimate Qp retrieved each iteration the value at position [pS].
18

---

Published in Transactions on Machine Learning Research (10/2024)
n 0.01
n 0.025
1=0.04
10
Algorithm
RQC-SGD
8-
CMOM
6-
GMOM
110
4-
2-
0
0
2000
4000
6000
8000
0
2000
4000
6000
8000
2000
4000
6000
8000
Figure 4: Evolution of |[0g - 11 (g-axis) against iteration (a-axis) for the expectation estimation task, averaged over 100 runs at different corruption levels (bands widths correspond to the standard deviation of the 100 runs). For y= 0.04, the evolution on a single run also displayed. We observe good performance for RQC-SGD for increasing 77 while CMOM and GMOM are more sensitive.
B.1 Mean estimation
Data generation We compute matrix E =AAA + A)/2 where A E Rdxd is random matrix with i..d centered Gaussian entries with variance 1/d sampled once and for all. We generate true samples = VV where V is a vector of i.i.d symmelrized Pareto random variables with parameter 2 and 1 e Rd denotes the vector with all entries equal to 1.
We draw corrupted samples as X= 10v 100 x where V is a vector of i.dd symmetrized Pareto variables with parameter 1.5. We use step size 3 10-3
GMOM and CMOM The geometric and coordinatewise Median-Of-Mean estimators (GMOM and CMOM) optimize the following objectives respectively:
E||o x Nxal2 and 0
where XN, is the average of N₂ independent copics of X. The block size is set to N₂ = 10 in the whole experiment. The above objectives are optimized by computing samples of XN, in a streaming fashion so that one step made for each N, samples. In order to compensate for this inefficiency we multiply the step size by N₂ for both GMOM and CMOM. For GMOM, we additionally multiply the step size by v in order to compensate the normalization included in the gradient formula.
RQC-SGD For mean estimation, we implement RQC-SGD (Algorithm 2 with buffer size S = 100, = 0.2
and Funif = 10.
B.2
Linear regression
Data generation We choose the true paramcter 8* by independently sampling its coordinate uniformly in the interval +5). The true covariates are sampled as ΣV where Σ a diagonal matrix with entries sampled uniformly in the interval [aminn mmax] (once and for all) and V a vector of i.i.d symmetrized Pareto random variables with parameter 2. The labels are sampled as Y X 0* +e where is symmetrized Pareto random variable with parameter 2.
The corrupted samples are obtained according to one of the following possibilities with equal probability:
X 1000(max; E,)u + W where e is a fixed unit vector and W is a standard Gaussian vector and (1r2)
X 1m00 V with V a unit norm random vector with uniform distribution and Y 1000(Z U) where Z is random sign and U is uniform over [-1/5,1/85
19

---

Published in Transactions on Machine Learning Research (10/2024)
X 10V with V random vector with i.idd entries following symmetrized Log- normal distribution and Y = xTaake + with Otake fake parameter drawn similarly to 0 once and for all and a standard Gaussian variable.
We use step size B = 10-3
Huber parameter In order to tune the parameter 8 of Huber's loss function, we proceed as follows:
For each corruption level 7, consider 10 candidate values 6j 101/2-5 for 0 S < 10.
For each candidate 6,, we train 250 estimators (0)))
ie [250]] using 1000 samples each.
We choose j for which the average 250 E |00% l+ is minimal and use ő = 0y parameter.
RQC-SGD For linear regression, we run RQC-SGD with buffer size S = 100 and Tunif = 10. The quantile value was set to p = 0.1 for ry E (0.02, 0.06) and p = 0.05 for rj = 0.1.
B.3 Logistic regression
Data generation The true parameter 0 and covariates X are chosen similarly to linear regression. Given
X, the label is set to +1 with probability and 11 otherwise.
where a is the sigmoid function oxx) = (1 + + -
The corrupted covariates are determined similarly to linear regression while the labels are as follows in each respective case:
Y is set or with equal probability.
= sign(X
Y sign(X (X Otake) with Diake fake parameter drawn similarly to 0* once and for all.
We step size B = 6 10-3
Huber parameter The same procedure is used to lune the parameter of the modified Huber loss as for linear regression.
RQC-SGD For logistic regression, we run RQC-SGD with bulfer size S = 100 and Tunif = 10. The quantile value was set to p = 1 - -7 0.1 for 77 0.02 and = - 7 - 0.05 otherwise.
B.4 Single hidden layer neural network classifier
We train a single hidden layer neural network classifier with 100 hidden neurones for all datasets. We use one sample per iteration and step size 3 = 10-2 for all mothods.
As previously, RQC-SGD is run with buffer size S 100 and Junir 10. The quantile value was set p 0.9. We compute the gradient norms over a batch of samples of size S the beginning of the optimization and use the quantiles of order p 0.25, 0.5 and 0.75 as the clipping level for the constant clipping baselines.
Data We used publicly available datasets for our experiments. We provide details about their character- istics and sources Table
We use 10% share of each dataset as a test set in order to compute the test loss plotted in Figures and We also ensure the test set contains least 5000 elements. Optimization run using the remaining train set which is corrupted specified next. The results averaged over 20 runs for each datasets.
20

---

Published in Transactions on Machine Learning Research (10/2024)
Dataset
# Samples
# Features
# Classes
Source
Codrna Uzilov et al.
2006
488,565
8
2
OpenML
Sensorless [Bator 2015
58,509
48
11
UC1
Covtype Blackard 1998
581,012
52
sci scikit-learn
Miniboone Roe 2010
130,065
50
2
UCI
Phishing (Hanoouse Yahiouche 2020)
11,430
87
Kaggle
Main characteristics of the data sets used in experiments, including number of samples, number of features, number of classes and sources.
Table 1:
Data corruption = 0.02.
We corrupt train data samples at each iteration uniformly at random with probability
Although we run the optimization using one sample per iteration, the datasets we use are available offline so that we have a data matrix denoted p=x(d+1) whose last column represents the labels. This corresponds to samples and d features.
For each feature j E [d], compute ïi and ōj the empirical mean and standard deviation respectively. We also sample a random unit vector u of size d and introduce corruption as follows:
For the label column, we introduce corruption by changing the value uniformly at random among the other possible modalities.
For features, we introduce corruption by replacing the original values with one of the following possibilities with equal probability:
a vector & sampled coordinatewise according to E = ry 1000 x ,,v where ry is a value randomly picked in the column X..j and v a sample from the Student distribution with 2.1 degrees of freedom.
a vector & sampled coordinatewise according to Ej = 73g + 1000 x Gyug + where a is a standard Gaussian.
vector & sampled according to f2 1000 ō @ where w is uniformly sampled unit vector.
C Geometric convergence speed and relation to step size
The geometric Markov chain convergence stated in Theorem I occurs at a speed determined by the con- traction factor P which mainly depends on the step size 3 and quantile defining the iteration. Therefore, an explicit formulation of this dependency is necessary to precisely quantily the convergence speed. This question is lightly touched upon in (Yu al. 2021) whose Proposition 2.1 an analogous SGD ergodicity result. Like Theorem [1] the latter relics the Markov chain theory presented in (Meyn & Tweedie, 1993). It is argued in (Yu al. 2021] that a vanishing step size 3 + 0 causes p to be close to one, leading to slow convergence but with smaller bias. However, these considerations remain asymptotic and do not quite address the convergence speed issue.
More generally, the precise estimation of the factor p goes back to the evaluation the convergence speed of a Markov chain satisfying a geometric drift property. Near optimal results exist for chains with particular properties such stochastic order (Lund et al., 1996 Roberts & Tweedie 2000), reversibility (Jerison 2019) or special assumptions the renewal distribution (Berenhaut & Lund 2001]. Unfortunately, such properties do not hold for SGD. Let (0:)220 be Markov chain satisfying the drift property:
AV(0) < - ()) for $ C for EEC
with X (0. 1).b < +00, real function such that V(Ø) 2 for all 0 and C (bounded) small set (see Meyn & Tweedie 1993 Chapter 5)). Then, based the available literature (Baxendale) 2005 Bednorz 2013
21

---

Published in Transactions on Machine Learning Research (10/2024)
(02) converges as in Theorem 1 with p = 1- the latter estimation being unimprovable without further information on (0z)e20 (see the discussion following (Baxendale] 2005 Theorem 3.2)). For the specific setting of Theorem (and more generally for SGD by setting = 1), this only yields an excessively pessimistic estimate
/ (D33))²
(17)
whereas it is reasonable conjecture that p 1 1--1-pppp- p8p. The suboptimality of (17) is felt in the uncorrupted case in Proposition 2 and Corollary [ where one is tempted to set of order 1/T, with T the horizon, reducing the bias to (11/VT). However, this results in an unacceptable sample cost of order 7 before convergence occurs. On the other hand, assuming the estimate p ~ 1 - p3μ holds, using step size of order /Tg allows to combine fast convergence and near optimal statistical performance. Finally, note that in the corrupted case, the optimal statistical rate is 0/1) so that striking such a compromise is unnecessary.
Proofs
D.1 Preliminary lemmas
Lemma 1. Grant Assumptions
1 and 2
For any 8 A' Rd and B S 2
M+I. we have :
- (V-(0) (0' (V'- s 31) 0111
(18)
Proof. For 5 2 H+L we have:
||0 0 3V2()) (0' - (V
110 01 28 0¹, VC() -0,, VZ(00) VL(0')22
S (1 - F2uL)10 012- 3(2 - 3(u + L))(V(())) VL(0), - 07))
S (1 3² 1b 01 -33- 8(u + L))m(0- - 0
(1 3² - 20p + pm(( + L))110 -0112
(1 By1)2110 0²
where we used the inequalities: :
VC(0) - VC(0)]] < -
- 0- - 8²) - -uL10 - 8
(19)
M|10 - 2 6' < (V V 8¹).
(20)
Theoerem 2.1.12) valid for all 0.0' Inequality 19 is stated, for example, in Nesterov 2014
(see
also (Bubeck 2015, Lemma 3.11) and (20 is just a characterization of strong convexity (see for instance Nes-
terov 2014
Theorem 2.1.9)).
Note that Lemma] is a simple generalization of the usual contraction property in strongly-convex optimiza- tion where 0' usually taken as 0+, In that case, one has VL((') = 0. An example of such result given by (Bubeck 2015 Theorem 3.1 A similar inequality Lemma was previously obtained in @Dieuleveut et al. 2020 Proposition 2) where convergence of SGD Markov chain was studied.
In the sequel we will write gradient samples G(B,C) and G(0,C) () simply as G(Ø) and G()) respectively in order to lighten notation. The following lemma will be needed in the proof of Theorem
Lemma 2. Let Assumptions / and 5 hold. Let 0 E IRd be fixed and let Ō(() Dz(() be non corrupted gradient sample. Choosing the clipping threshold as To = Qp(IG(()]I)) for some E (0, 1) and denoting
ag = min (1, ( )
the clipping factor and its average Tg = E(ao/0, G(D)= G(0)~ we have:
[l(a)((0)] aa VC(0)]| s (1 1)2 10 0" Bg),
(21)
22

---

Published in Transactions on Machine Learning Research (10/2024)
Σ VC( + (p((l=
- V + p1-p) p)- 1/9) (A, - 1000--011---
+ +B))
(22)
If Assumption 3 holds with 2 2 then we also have
(0) - Ela, s (Ayl10 - 0-11 + B₂)² + +5(11 - -p)Tē-
(23)
Proof. We condition on the event. that the sample G(0) not corrupted i.e. ((0)=G(()~Dz((0) Noticing that | = | and using the equality E[G(O)] - VL()), we find
E[as ag VL( = (( - (ā(()) VC(0))]
(G(0) (1)
VZ(0)) 110001100 + E [(00 (G(0))((())) 11ā0)))))
= (To - 1)) - 1 110(0)11701 E (ō(() - VC( 1100) 12:00
+ +E((ro/I((0)]) (G(A) -L()) 11ā00)12T0
(G()) VZ())) 110011100
Using our choice of To and Hölder's inequality, we find:
[[(a)((0) - 0o VL(
- E | 1 1 To/ - - vc(0)]]
< B 1100))>>>>
|[((0)
VC
< (1 - -0- [[(( - VC(0)]
s (1 - p) 1) 1-19 (A,110 0'1l B,),
where the second step corresponds to the inequality || - To/ /0/ < 1 under the event {I > m
Note also that we used Assumption since is fixed. Inequality 21 now proven. To show 22 we first write the inequality:
Tp = Qx ( + ==ll) - [| + @p(1=)))),
which holds since [|G(0]]] a positive random variable. Further, using Assumption
we have:
E| < A 8- - Bg
- = P(leall > (p(leel))) <
(p(lol))
@p(1Foo))
It only remains to take the g-th root and plug the obtained bound on (p back above to obtain 22
To show
23 we define the event E {I)((0)] S To} and denote its complement such that P(E) = P
PEE). We write
Bl|age(0) Elaaū((0)11
p pB]llas@(1)) (0)1
+(1 (1-p) (1-p)B(laccCC)--B(o[([(
[(( + +4(1 p)
+ =| 4(1 - p)7
+ PP
ppr8
p [[o + 1001--)7-- +4( p)TØ
p -[a0)()))]))))]]] - -
23

---

Published in Transactions on Machine Learning Research (10/2024)
where used the identity 110
and the inequalities [|ag S
and p(1 p) - 1/4 which hold in all cases. In addition, we have
pE pB|l [[oo((0))1]]]
piB
||| ( E[ [| - E[]] E[G(O))]I
B|||((0) (=) S (A,l10 0* B₂)
The first inequality obtained by applying Lemma to each coordinate G()) while conditioning on The second one uses Jensen's inoquality and the third results from Assumption
The statement of Lemma 2 appears to be novel and is enabled by the specific choice of the gradient norm quantile clipping threshold.
Lemma 3. Let Y be real random variable and & an event, then we have the inequality
- F B(Y -E(Y))²
Proof. Define the conditional variance of real random variable Y w.r.t. another variable Y as Var(Y|X) = E[(Y -]
By Eve's law(see for instance (Blitsstein & Hwang 2019 Theorem 9.5.4)) we have the identity
Var(Y) = E[Var(Y X)] + Var(E[Y[X)),
which entails the inequality Var(Y) 2 ([Var(aa)))) Applying the latter with X 1g yields
E(Y - [[]] =ar(()))Vr())) > - + (1 ((E) -(
which implies the result.
We show the geometric ergodicity of the SGD Markov chain (0:)c20 by relying on Meyn & Tweedie 1993 Theorem 15.0.1). We will show that the following function
V(0)= = 1 + 110 0²
satisfies a geometric drift property. We define the action of the transition kernel Pp. on real integrable functions f over Rdd through:
( = 1(0)) E[s onp 3G())
We also define the variation operator:
A
((0).
In many of our proofs, we will make use of the following adjustable bound. Fact 1. For any real reumbers a, and positive e, we have the inequality
2ab < b2
D.2 Preliminary properties for Markov chains
In order to prove Theorem we set up the formalism we neod from (Meyn & Tweodic 1993 through the following definitions.
Definition 2 (Small set). set C E B(Rd) is called a small set if there enists 0, and non-trivial measure on B(RR) such that for all 0 C and B B(Rd).
(0, B) 2 v (B).
When this is the case, we say that C is (m, small.
24

---

Published in Transactions on Machine Learning Research (10/2024)
Minorization properties such the one above are useful for proving the convergence of Markov chains. We define an analogous one via the notion of sampled chain.
Definition 3 (Sampled chain). Let a be a probability measure on 24 t.e. such that a(n) 2 0 for a 2 0 and En=oa a()) Then the transition kernel for the sampled Markov chain w.r.t. the distribution is
Ka A) = Σ
(0 A),()))))) for ZER,, AE B(R*). (
7=U
We define the notion of petite set for sampled Markov chain. Definition 4 (Petite set). Let a be probability measure on Ey defining sampled chain. set B(R))
is called (a, peptite if
Ko (BB),
for all E C and B E B(R²) where v is a non-trivial measure on B(R
Note that an (m, -mmll set is also (a, petttte with a = Sm. Finally, we define the norm of measure w.r.t. a potential function.
Definition 5 (f-norm). Let ::R. + R be function such that f 2 and let be a signed measure R. We define the -norm of as
If s(0)u(a)))
|
|v(g]| sup s:lalis g:lals
sup
In porticular, we have ||v|ls 2 ||/|TV.
D.3 Proof of Theorem
We will assume in this proof that q 2 2. The case g (1,2) will be treated in Appendix D.5
First, we define I = infg Ta. Note that Assumption excludes the existence of such that G()) = almost surely, therefore, we have 7 O.
Thanks to Assumption 4 and conditioning 0, = 0 e Rd for 2 O, the distribution of 0.+1 has strictly positive density at least
ball of radius BI around 0,. This implies that the chain is aperiodic since (0,, Wo.) > 0 for any neighborhood Wo, contained in the previous ball. Moreover, by induction, the distribution of Oc+m has positive density at least on ball of radius mBI around 0.. Thus for m high enough we have Phr, (0,, A) > 0 for any set with non zero Lebesgue measure. It follows that the Markov chain is irreducible w.r.t. Lebesgue's measure and is thus vi-irreducible (see (Meyn & Tweedie 1993 Chapter 4)).
For fixed 0, condition (g implies B ziz and using Lemma and denoting ag and 0e as in Lemma we find:
po - 0-1 = 0 - Baa - 0-12
S 7 - 8' + 3T0)² 2 + (1 - - - 1
:|B[ +111+800 + 1) ag. 0-12
20(0 - x. - 0' a0,a)(()) VZ)) (3 (la() a [
$ 600] + (00000000111-0""=000000000000000 (10-))[(100 - -0111
+ -| -. V2
(A, + B,) + 5,83 - p)
where the last step uses that E (() - Vc
E ( Ela (
3. -
and Lemma 2
25

---

Published in Transactions on Machine Learning Research (10/2024)
Using Lemmas
and and Assumption 5 and grouping the terms by powers of ||0 - 8*1,, we arrive at
pa 0- - (1 + (1 - - +
2 ||0 00 (177 + + 7)( T0
[[oo -
8² (1T) - (1 1--)
- [oV(())]] + (A,110 0- B₂)² + 5(1 - p))
- R | 0" + 2/ -0'1] 3
332 C
< (8l 3k) [100 0- [1]
(24)
where we used Fact
! and defined the quantities 21, B, E which may be bounded as follows
2 = 21110-0--111100000022233---11---
p) 1/1) + (1 n)((1 - T133)((1 - 111 An)
+
+ 44
1 - (100
1/9) - (1 - 1)((1 - -TBBp)(1 - 11111/1 Ag) A)) ((1 - 2(7+ 5(1 p))
(1- (1-p)
+4A7)
$1 - 2- n). (11
(111-(1 -))) + +B2 24m + +28A7)
28x + 83 (32 +2,, ( 2843),
B (n(1 1// + (1 - 1) 3)) 1)9 B
$ (1 - p) 1/4 B1 + (1-y))
C (4 2(1 + 5(1 - (1) -p) 2/9 R33
The above bounds use the simple properties p S ag 1 1, 0 7 11, 1- $ and (a b)2 < 2a 252 for all a, b.
Thanks to our choice of B, we get that + 3K < 1. It is now easy to check that V(0) 1+ 110-0011 satisfies the contraction
Pa. < (A + 3K) V(0) +1 +1- (2l =K) 38
C.
=xA=
We now define the set C 10 E Rdd V(0)= S 20/(1 - -}}} for which we have:
AV(O) < 2 N V(0) + Eloec-
(25)
For such C, let A diam(C) be its diameter and set mc = of the proof, conditioning on 0g = 0, the distribution of 0.+m admits a positive density at least over ball of radius m3I around 0 i.e. there exists h ("("(w)
Ac
As previously mentioned in the beginning
PI
(w) 2 0 satisfying
h (w) 0 for |0 - w|l < mBR and P (0, A) 2 / h 11th (w)dw for Ae B(Rd).
We then let he(w)= infeec m= and define the measure ve by:
vc(A) S/nc ho(()d
The above mcasure is non trivial since choice of me ensures that he defines non zero density at least C. It follows that for all Og E C, we have the following minorization property:
Pit (fo, A) 2 ve(A) for all A B(Rd)
(26)
26

---

Published in Transactions on Machine Learning Research (10/2024)
which implics that the set C is (me, small and also (6me: Pe)pettee result. We have previously shown that the Markov chain (0x) is irreducible and aperiodic. Moreover, we have exhibited petite set C
(via (26)) towards which the geometric drift property 25 holds. Thus, condition (ii) of (Meyn & Tweedie 1993 Theorem 15.0.1) is fulfilled.
By the latter result, it follows that the chain (0t) admits a unique invariant probability measure Tg.p and there exist and M < oo such that:
Σ 22:0
r' pll
- r S (V)))).
(27)
Taking r- and using that ||||| 2 |PI|TV for any signed measure y concludes the proof.
D.4 Proof of Proposition 1
We consider the case q 2 2. Since the distribution Tp is invariant by the transition kernel Pp.p, we can deduce that for 9 ~ p, we have
0 0-1 Ell0 Box G(o) 0-
From here, we can follow similar computations to those leading to
24 in the proof of Theorem By setting
= - 17 and using that 2 2, we additionally have the bounds B $ 37 1-111//BB Bg and e < 16B,
Hence, we have that:
BB3
E|l0- - 1²2 < (2l + 3K)B - 1-
+ 3
833
32
E|l0 1¹1 <
+ 1 21 3R
(28)
x(1 21 3K)
Note that entails
1 A - Br 2 3x 84 + 24111. + +2842) 2 38x/4.
(29)
Plugging this into 28 and using 10 we find
12n2-2/9 B²
648B2
341/2-2/1
E 1-1125 <
R²
3x
x2
which implies the result.
D.5 The case E (1,2)
Similar results hold for the case E (1,2) but require a different proof given below.
Proposition 4. Let Assumptions 1 hold with q (1,2) and let QC-SGD be run with quantile p In, - 7].
Assume that
w (1 1)pp - qnL q(n(1 p) 1/9 + (1 -
(1-p)'-11 1 -119) A., O,
(30)
and take a step-size satisfying
R²
2 86(L + A₂)
(31)
then the generated Markov chain (0t); converges geometrically to unique invariant measure T8.1-n as in
Theorem D In addition, for p = 1 7, 3 < n/K' and ~ 1- we have
n 1/0 B
1 < 128
R
27

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. We first need to prove that convergence holds as stated in Theorem | of irreducibility, aperiodicity and exhibit. a petite similarly as before. However, the demonstration of a geometric drift property such as (25 requires a different approach.
We establish the properties
In this proof, we will use the following inequalities valid for all positive æ, y and e and g E (1,2)
(x + y) v 29 (x9 + y²),
(32)
(x + w) < x + q. -1 y + +3²
(33)
(a consequence of the incquality (1+ + a) & 1 + qa + a for a > 0),
(x + y) v ,. 1--11 + 1
(34)
and
ry S (xE)
9 -
(w/e) (y/=)
(35)
g q
which is consequence of Young's inequality applied to the pair and w/e with exponent q and its conjugale. We first write
pa - 0-11-- = 0 (() 0-11 S n 0- 1| +
+ (1 (
ag
Defining the notation E-|-| |[, we have
E 0- [ (110) -
-
20(0 -0 ao a. + +
< [V (2V 0- -
[B((a)((0)] -
-200--2-00000000 0*, -
- - VV(() + =
+ (9El(a00(()) E. (0))])
< E[[1 -. 0- -
ae 23 0. VL 0r, -
8 -all::(G(00-aaV((000000010
< B(11- 0. (V) 0* + Eo Eala, ag VC()))) + 3a
- Eo(aoE(0)]13,
where we used 34 conditioned on 0, then used Jensen's 's inequality for E, and a Cauchy-Schward inequality. We focus the last term. Defining the event E = (0) тh) such that P(E) p, have
(()a - TEg (cr (())) = (1 - (0- B[[( E0(
+ -1c
< (1 - + 111-l(2r)++ [|T
In addition, using
34
twice, we find
Elll B[|aaaG(0) E ((()111)))
V2()) - Eg(a,
< - 20-1211111111111 --000-0)0V]0(00
VL(00 - Eolac(()))))
28

---

Published in Transactions on Machine Learning Research (10/2024)
Therefore, from the two previous displays and using Assumption V=(0)] (0) [C())) we get
1 Lemma 2 and the inequality pE|I|((0)
E| [l) E((a) S (1 (1- (1TT) 2 - 0-11"
+ + 24
((A 0- + BB)
We also have
0- (1-1) s (1- (1)))
pp)
- ((L+ + A,)110 - 0' + By)"
Plugging into the previous display and simplifying lcads to
El|aoE(0)- [o(a) - 2 A,)1 0*ll B₂y ) + 2p1-~2p11111102 a00 11))
+ +220-2 -2- 0'1
s (2 --) 00 + B₁)" + (220-2 + 20 121-1111111111111111111111111111 - p)-
-A,000 - 0- + BBy
S +14((L+A.)) -,) -0 By)"
(36)
Using these inequalities along with Lemma to bound B| 1- we find that
p1 11 s ( + B + (1 ,0 Ee(o)
+ (1 -
0*1 [[]] - ag VL(O)))
011000001 + - [|1
(g)) 1-
+ ||
+ (1- (1-7) (a. Eo(a)((())]
s [ (1
(1 - 7) - 1|01 1 (NT
+ (1 Gao - (*
+ (1 - ( [2000 - E [((o)(())]1)
(
$ (1 (((1 1)pp (1- 9(1 7) p)) A1/9
+ (10 14 + A,
(1 71 -000--))-0000)000--0---++1011111 0" -|0 ((1 - m) - -p)p-111111
+ (1 - p) - +
+ -0 m) (1)) p) B3 + +14Bg) -
< 2E 0 1
(37)
where the second inequality uses Lemma and 33 twice, the third inequality rearranges according to
powers of 110 - 01,, I1, the fourth one applies Lemma
2 and (36 and the last inequality defines the factors 21 B
and C. Since p < 1 - 1/, these satisly:
2 < Bn' + 8828 (16)(L A,) B B and e S 24/
Applying 35 we have for all & >>> that
+ E 11
B/0) +
R'Ell0 1-1
23
n²'
1-9
BEIA 0- S
(38)
// l/(g-10 - 1)
q
8q
8(g q
1)
9-1 4
where the second inequality corresponds to the choice 6
n²'
Plugging back into (37 and using
110--1
8800
condition 31 ensures that 2 8x' / < 1. Defining V(0)= = 1 100
0* 0-110, we get that satisfies the contraction
n²'
1-9 +
(0) < (Ml + Brd 88 (00 +1 - (2l + 3K' /8) + 323
-8424-109
8(9 1)
=AX1
29

---

Published in Transactions on Machine Learning Research (10/2024)
From here, we use the same argument the previous proof of Theorem to deduce that the Markov chain converges to unique invariant distribution "p.p- Now, since convergence occurs to limit distribution Tp.pt we have, as before, for O ~ Tapp the identity
0 - -- El10
(() 11.
By sctting p 77, can show that in fact
B S 21 1 Bg. Plugging back into
37 and using 38
and 31 we find
E - 0 1 < (1 (7/8) + 32 + A,) - 0- + 3(21) B(211-1/9B,)
1-g
+ +-333 By
8(q 11)
n¹' 1-9 s (1 - (3/8) 8r ((2)) (1) + 0232293 By
Now using the condition B S n/k/ and rearranging the incquality, we finally arrive at
8
(1111// ) (2((((- 1))a- + 32)
B 0- 1 -
3
R¹
11 1/111//B²
S 128
which is the desired result.
D.6 Proof of Proposition 2
We use the invariance of Tp by the transition kernel P3.p- For real X, this implies the equality
Eexp (22110 - 0r 11²) = Eexp (12110 ag) 11))
(39)
We then write:
0 ao 0 2= - (000
-23 VL(( 0", oz)((() E(aaG(0)) + B(aoG(0)) F(ooC(( ao VC())).
We also have the inequality
(oo())-aVV((0))) < 2l)0aG((0) +
Conditioning upon 0. we have that || (a) E(a)](0)]] < 2To S 2T. Moreover, the vector GaG
E[aaG(()] is centered, therefore is sub-Gaussian with constant 27 (see (Vershynin) 2018 Proposition 2.5.2)). Still conditioning on 0, using these two properties and Mauchy-Schwarz inequality, we find:
Eexp (X*(23)1oo0G00)) - E(aa)(0)]] -2 1000-a.3VV200 0-, aaG -0", I exp (2X33
BlanG(0))))) - 0- 13)
Putting everything logether in
39
we get:
Eexp -1100-0003) (00 0r -2 -8322
+ + +22
[|a 00 V ((()
< Eexp
+ +=200-1000))BBB00CC0))=00000/000 +
30

---

Published in Transactions on Machine Learning Research (10/2024)
where we used Fact to find:
Now, recalling that ag 2 p, we set ToBp//2 and restrict À to À (47 v 2233pp)
Eexp (A2110 - Bexp +0)0
-
21 + (1 20011111220/11000000000000000000
48
Eexp (10-- 86
[[aoG((0]-aVZi
Cpp
< Eexp (1) (003))(11 -g P10 12 +,837 + 43
((1 - -p) p)1-1/4B,)) ))
agH
< Exxp (A1 Tee 31) (Te 1- 2 B B/DD)))
where we used Lemma bound relating and p.
!
inequality 21 from Lemma
(recall that 17 0 in this context) and the imposed
Finally, using Jensen's 's inequality and the fact that T6g 2 p 2 1/2 we gel:
8x B3 Exxp (12100-011) S exp aB (a)p)² (aB4)²3
88 822 + B²z)
S exp
which concludes the first part of the proof. We now consider the corrupted case 17 > 0. Let À >> 0 and write
E [xep (All0 11]] B exp (Al16 og) 0 Il)
- BB exp (AII- -01)) + (1-1)) exp (A1001a80(0)-0'1))
< nB[ exp (A(110 0-11 + (Ta))] + (1- -) (Xll- V. - 0*|l
+ AB(1aa)((0) E[a)0(0)]] + - -
$ nB[[ep (Allo 6*1)] e
+ (1 - E1 exp (>(1 p3pp) ||e [1)] exp (A5(27 + (1 - (11pp)1-1//0 -))--1/9Bg))
where we used Lemma the inequality og 2 p; the inequality ||aaG(0) BlaaG S 2To S 27 and 21 from Lemma Using Hölder's inequality, this leads to:
E exp (Allo 1*1)] - (1 - neA#8 1 )
1 1-
1/(81))
cxp (A(27 + (1
(1- - (1
BT log(1/n)²
Now we use the inequality log 1
x
SFFF log(1/n) valid for X 2 0 which leads to:
17 N0A
1/(p3p)
pu log(111))) for 0 O5A= log(1/n)
2XF
I exp
2,T
Using that 1) < 1/2, we find that for 0 S A
log(1/n) 2
the following incquality holds
X
1
E[exp(A||0 8- [)] exp
2T 1 +
+ +(1 - 1--pp)/1/BBB BB,
1og(L/n)²
< exp
(7F + (1 (1- (1-p)
Noticing that 8 < 1. allows to finish the proof.
D.7 Unimprovability of the sub cub-exponential property for 7 0
We consider the Markov chain
axx+ w.p. 1-1
X
X1 +
w.p. 7
31

---

Published in Transactions on Machine Learning Research (10/2024)
Assuming that the distribution of the noise & has density, one can show that the chain is aperiodic and satisfies minorization property as in the proof of Theorem | (see Appendix D.3).
Defining (xx) = 1 22 we can show that V verifies a geometric drift property similar to 25 Consequently,
Theorem 15.0.1 of (Meyn & Tweedie, 1993] applies to the chain (X1)120 and implies that it converges
geometrically to a limit distribution я analogously the claim of Theorem 1
We denote M X| the absolute moments of X for 2 1 and show that Mr. !2(k) (we merely provide sketch and do not attempt to explicitly compute the involved constants). For X x following the invariant measure, using the recursion defining X, and the positivity of &, it is easy to establish the inequality for k 2
(1 (1-n) n) (1-n)[1aa)acl 2 n E T D'MM3
where one may use the convention that Mo 1. We now postulate the induction hypothesis M, 2 Cj up to = - for some k > and C > 0. Using Suirling's formula, we find:
(1 n1 )²) M
7 (C(k - -)) -))) Σ
h!
r' (C j)) ())
k-j
7
jM(k -]]!
1=1
k T (((k--))] -)) -5)) k-j
j(k- 5) (7) (2)xt k
k
j(k-j) û) pkk-
- 5)k-3
(kk)
where Z denotes an inequality up to a universal constant and we took the term j = 1 in the last step. It is TV only left to set C' small enough such that [[-))([-a] 2 1 in order to finish the induction. It follows that
M₁ (k) implying that may be sub-exponential but cannot. be sub-Gaussian since that would require
M₁ (Vk)) (see (Vershynin 2018 Chapter 2) for reference).
D.8 Proof of Corollary 1
We need the following lemma.
Lemma 4. Let X be a real sub- Gaussian vandom variable with consland K then, with probabilily at least 5, we have
[ < K K log(e/8)
Proof. Using Chernoff's method, we find for >> 0 and À 0:
P([ > t) = P(X2x² > x²62 = IP( ((exp(X2xx²) > exp()?t9)
S xexx((>XX) -222-222 s exp () (K22
x22
Choosing 1-1,, we have exp (1-(1/)))<8-=111 K / log(e/0) and the result follows.
28
By Theorem 1 the Markov chain (0z) is geometrically converging to the invariant distribution Tapp w.r.f. the Total Variation distance so that for any event & E B(Rd), we have:
P(Or E) PONTER (0 < V(
(40)
Proposition 2 states that, in the absence of corruption, for 0 ~ Tp the variable |00 001 is sub-Gaussian
with constant K = =v 28(B the claimed bound.
It only left combine this conclusion with Lemma order obtain
PP
32

---

Published in Transactions on Machine Learning Research (10/2024)
D.9 Proof of Corollary 2
We assume without loss of generality that T is multiple of N. Note that according the assumptions, the estimators g) for n E [[] are independent and for each n. For positive c < 1 define the events
En == {110 00 S à 20 that
We first assume that E 1 > N/2 then there exists i' E [N] such
ne
0-1| 2 11-2 20
1
| 0-1 + |00
N/2
RE
Morcover, among the N/2 estimators closest to 8 at least one of them 8/
satisfies [10] - 0 1
9 Bg v2 thus find:
0 8- = [0 8- - 18 0 + 10(") 0-
(
Bg 20
17
BBy22
S
r N/2
(41)
AE
KE
Notice that setting c c= 1/2 immediately yields
13
We now show that Σ 1E, > N/2 happens with
high probability. Thanks to Theorem 1 and Proposition D we have:
P(EA)) se + Mp (1 1100 11)
Consequently, the variables 1,, are stochastically dominated by Bernoulli variables with parameter e so that their sum is stochastically dominated by a Binomial random variable S == Bin(N, +e'). We compute
P
1E. < N/22) =P Σ
E, > N/2)
x PP(S
ES > N/2 (62 + +)NN
S exp
-2
< exp
2N(112- - 1///22-1/--- M M/T (1 + 100 - -0-112))3) -1/1))² S exp ( log (1/)) = 5
S exp
where we used Hoeffding's inequality, the choice = 1/2 and the fact that our condition on T implies MpT/N (1 + 100- 01 < 1/15. The last inequalities result from our condition on N.
D.10 Proof of Theorem 2
As previously done in the proof of Theorem 1 we show that the Markov chain is aperiodic. Note that since L has finite lower bound inf, C, we can replace it with 1 + [()) info C and assume it is positive in the rest of the proof without loss of generality. We will now show that it satisfies a drift property. Let E θ be fixed, using Assumptions and we have
E E|C(O- (003aaa)(()) [()) SE (V + |anG(0))1
LB2
s E ( (11(-10200) asā())) + |aaa((0))))++
L
2
(VL() a(() + (1-n) n) (-
L
2 ||a0
33

---

Published in Transactions on Machine Learning Research (10/2024)
Note that have ||aoG(0)], |aaE I ro, therefore
[[ - ag. (()) s =
(1 (1-m)(8((<(())))))) + T,8278
2
Further, we write
E [(VL10).,))(
(VL(()) (O),(), وe +
Te VZ((0)))
Plugging back and using Cauchy-Schwartz and the incquality |0)0 S no leads
[[ (,)3G(0))] - < (4) (()) 3(1 7) VL(0)]]
LB
8(1- ((0_
< - [
-
8(1- - [(c1 V(((] L,37T8
We now use the inequalities < [ (1 (see Lemma 2 and (a S $2a² + +2b2 to find that
E B[c(0 ao)G)())) (()) < (1) 1)) - L - n) +
ao Vc(O
Next, letting > 0, and using Fact
gives
VV +1 (1 -1- (1--0)/((cdd((0)-aa-a/)))>)))<10 <VV=0))))))
(nop((l + (1 m) [((a ao - (
We now plug back with the choice c= p 1)/2 and use that ag ž p find
B[c(0 (a000))))( L()) -1000//)0000((00)((((1001111)001 7)
L3 - -)) + 2p
(1 0
p(1 p(1-1)
Finally, we use Lemma 2 to bound the terms (sell) and [B(as - āo V (()))| leading to
- anSG(())] - =[c(0-a,,C10)) =
L3 - n) + L3 pp) B²+
(B - (1
p(1 -(1-)) 17)
< - (3ppp -n)/4 L - n)+
(B, pp) (LB+ 2n7²) + 217 2-
(42)
p(1 p(1-1)
By assumption, we have 3p(1 - 7)/4 - T,B - 1 0. Define the quantity {= B3 ((1-p) (1942)7)4277 and
p(1-1)
the set C C= = {0 f F rd: } [[ < 3p(1 -1 } By assumption, C is bounded and it is clear that the right hand side in 42 negative outside C. Define the function V(O)- ((8) which positive and satisfies:
(V 11+2 10ec-
(43)
34

---

Published in Transactions on Machine Learning Research (10/2024)
In addition, show similarly to Theorem that the set C. is small and, therefore, also petite according to the definitions of (Meyn & Tweedie 1993 Chapter 5). Since V is everywhere finite and bounded on C (because the latter is compact), the conditions of (Meyn & Tweedie 1993 Theorem 11.3.4) are fulfilled implying that the chain is Harris recurrent.
We have shown that the Markov chain verifies the fourth condition of (Meyn & Tweedie 1993 13.0.1). This allows that ||P - TapllTy 0 and the following sum is finite
Theorem conclude that the Markov chain ergodic i.e. have for any initial measure À
Ellee TBlllIV <c.
In addition, by (Meyn & Tweedie
Proposition 13.3.2) the terms in the above sum non-increasing 1993
which implics that |P
Tg. TV
O(t=²) ') and the result follows.
D.11 Proof of Proposition
By Theorem 2 the assumptions imply that the Markov chain (0))2o converges to an invariant distribution "g.p- For 0 -9,1-9; by invariance of #3,1-n: we have that the variables L(0 oa)G(()) and ((0) are identically distributed. Taking the expectation w.r.t. 0, this implies the identity =IC(O--a03((())=LL[CC)
Plugging into Inequality (42 from the proof of Theorem 2 we find
[[(()) < (2 ()(11)))(LL+2111 21 21)
-111)(3b111)444-11 L3
(3 p) b1) 22
p - (3p 1)/ LB 11)
p(1 m) (3p(1 (3)11-)334444
where we used the choices S of and 1 1/.
35


Reviews:
[{"review_id": "6yscaloRSl", "reviewer": "Reviewer_kBQC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nTheoretical claims in this paper look solid. The proofs in the appendix are easy to follow except for some minor issues described below. \n\n**Weaknesses:**\n\nThe proposed quantile clipping is an interesting algorithm. However, the motivation for its use (compared to the standard clipping) remains unclear to me. I could not find any theoretical justification, how does it compare in theory to standard clipped SGD?\n\nMain issue: Quantiles are not computable (since the distribution is unknown) and can be hard to estimate under heavy tailed noise. Authors say in introduction that QC-SGD can be implemented using rolling quantiles, but when it comes to section 5 it turns out that Algorithm 2 is actually a different algorithm. There is no proof that it implements exactly the rule (2) that is analyzed in theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work proposes a new variant of clipped SGD with the choice of clipping threshold based on quantiles of stochastic gradients. The convergence of this algorithm in distribution is studied for strongly convex and non-convex problems. Numerical results complement the study.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. [62] and [30] do not require sub-Gaussian assumption.\n\n2. Before [85], NY in [63] already showed how to handle heavy tailed noise by changing the mirror map. \n\n3. \"initial evidence of the robustness of clipped SGD to heavy tails was given by [87]\". \n\n4. Part 1 of Lemma 2 controls the bias of uncorrupted stochastic gradients and looks standard for for gradient clipping analysis. Perhaps adding some references would be appropriate. Same applies to Lemma 1 if it appeared in prior work. \n\n5. Why the definition of the transition kernel is different on page 4 and on page 24. The most confusing thing for me is that on page 4 and in the discussion on 25, the transition kernel has the event A as an argument, but in the definition on page 24, it does not have it. \n\n6. To make the paper self-contained it's better to add some formulations from [58], for instance, in the end of the proof of Theorem 1 on page 26, some condition (iii) from [58] is referenced but not stated. Definition of petit set is not given, is it even relevant for the proof? \n\n7. How does (25) imply the result of Theorem 1? Where the measure $\\pi_{\\beta, p}$ is defined? \n\n8. A better title for section 4 is perhaps \"Non-convex objectives\" because results of section 3 are also for smooth functions.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zwKKegJHmr", "reviewer": "Reviewer_z2UW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- The paper tackles a relatively unexplored problem.\n- It introduces “in distribution” convergence, which appears novel for this family of methods.\n- The authors provide rigorous theoretical analysis.\n- Extensive numerical experiments comparing the performance to baselines are presented.\n\n## Weaknesses\n- The introduction section lacks practical motivation. Why are the results important and interesting in the specific context of streaming stochastic optimization with heavy tails and outliers?\n- The paper's presentation and theoretical results are not very clear.\n\nNext, I structure my comments and questions according to the sections.\n\n### Section 2\n\nIn my opinion, Assumptions 3-5 need a more detailed discussion. How realistic are these assumptions? Are they introduced for the first time, or are they standard in the literature? Are there any other analogs or alternatives? Are these conditions technical and introduced to make the proof work, or do they naturally hold in some applications that motivate the work? This section seems to lack references to prior works that may have relied on some of the assumptions.\n\nAssumption 4 seems unusual in representing the error’s distribution as a linear combination. What is \\(\\theta\\)? Is it a parametrization of the density?\n\n- What do the subscripts $\\mathcal{I}$ and $\\mathcal{O}$ for $\\mathcal{D}$ denote or refer to?\n- It is unclear why Assumptions 4 and 5 are separated, as both seem to impose conditions on the stochastic gradient error.\n- The part on the total variation (TV) norm lacks references. Perhaps I am not an expert in this area. What is $f$ in the integral definition, and what are the necessary assumptions on it? Why was this particular measure chosen?\n\n### Section 3\n\n- Can the result of Theorem 1 hold for an arbitrary quantile, or does it need to be specifically chosen based on the generally unknown corruption rate $\\eta$?\n- The conditions on $\\kappa$ and step size $\\beta$ are unclear and hard to interpret. The bound on the corruption rate $\\eta$ seems very restrictive concerning the condition number of the problem $\\mu/L$, as the latter can be extremely small.\n- How restrictive is the condition (7)? How does it compare to LMC/SGD without clipping? In general, it seems the paper could benefit from more comparisons like this.\n- The discussion after Proposition 1 mentions “poor dimension dependence through $B_q$”. Why is it poor, and why is this the case? It mentions the choice $q=\\log(1/\\eta)$. Why do you have a choice of $q$ if it is part of the assumption? The restriction on the set $\\Theta$ is quite restrictive.\n- Why are the concentration properties given by Proposition 2 called “strong”?\n- The formatting of Algorithm 1 could be improved. It is not very clear. I suggest adding a verbal description. What does the notation $r^{(i)}_{N/2}$ mean? Maybe I missed the definition. There is an extra break in the input description.\n- The end of Section 3 mentions that \n  > [28] results enjoy better dimension dependence but are less general than ours.\n\n How much more general is this analysis compared to prior works?\n\n### Section 4\n\nWhy does Theorem 2 require the objective to be positive? Condition (13) looks quite obscure and hard to interpret. Can it be simplified?\n\n### Section 5\n\nThe statement that\n> In the non-strongly convex case, a constant threshold can be used since the gradient is a priori uniformly bounded\n\nDoes not seem correct, as a non-strongly convex quadratic function may not have a bounded gradient.\n\nHow does Algorithm 2 compare to adaptive clipping [1]?\n\nThe *linear regression* paragraph states that\n> These thresholds provide a rough estimate of the gradient norm.\n\nThe \"gradient norm\" computed at which point?\n\n### Minor Comments\n- The template used is different from the official one suggested by TMLR.\n- The table of contents in the PDF is absent. The links (to equations and references) starting from the second page are not working properly. Combined with the split into the main paper and supplementary material, this makes the paper very inconvenient to read and review. I recommend attaching the full paper as supplementary material on OpenReview.\n\n___\n[1] Andrew, Galen, et al. \"Differentially private learning with adaptive clipping.\" Advances in Neural Information Processing Systems 34 (2021).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of stochastic optimization under a modified heavy tails assumption on gradient estimates, with potential probabilistic corruptions of the samples. The authors propose a method based on SGD with a clipping threshold selected according to the quantiles of stochastic gradient norms. They provide several theoretical results on the convergence of the iterates' \"distribution\" and the deviation of the stationary measure samples from the optimum for both strongly convex and non-convex cases. Finally, a more practical algorithm variation is introduced and tested on various synthetic and small machine learning problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Elaborate on the realism and literature precedent of Assumptions 3-5 to justify their inclusion.\n2. Correct the PDF's non-functional links, absence of a table of contents, and alignment with TMLR formatting guidelines.\n3. Improve the presentation and clarity by addressing the weaknesses comments.", "broader_impact_concerns": "No, for this work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CzWQ5d5mSE", "reviewer": "Reviewer_m6Va", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper introduces gradient quantile clipping at the first time to the best of my knowledge, and provide sound theoretical guarantee for it robustness to corruptions in the data stream.\n2. The paper also provide a rolling quantile procedure for simple implementation and shows its performance through numerical experiments.\n\nWeaknesses:\n1. It is mentioned in this paper several times that another work [28] (which also proposes algorithms for data corruption robust streaming estimation) is difficult to implement and compare, could the authors provide more detailed reasons about this?\n2. The high probability bound given in Corollary 2 is still weaker than the results in [28] due to stronger dimension dependence, could the authors provide potential improvement on current procedure (Algorithm 1)? And could the general results be further improved for specific linear and logistic regression to achieve the similar bounds with [28]?\n3. The authors' main argument that the proposed algorithm is better than [28] is that it is easy to implement without dependence on a number of unknown constants. However, it is still not clear to me how to choose $p$ in the implementation of specific tasks, which is an essential parameter for the convergence of the proposed algorithm as stated in Theorem 1 and Theorem 2.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a gradient quantile clipping strategy for SGD (QC-SGD) in the setting of streaming stochastic optimization with data corruption. The contributions include:\n1. Gives the result of convergence in distribution of the Markov Chain by SGD with constant step size: For both strongly convex and non-convex objective, with well chosen clipping quantile $p$, QC-SGD allows to combine both fast convergence and optimal dependence on corruption parameter $\\eta$.\n2. Proposes a rolling quantile procedure for the quantile estimation and confirm its robustness by numerical experiments on three stochastic optimization tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add more comparisons with [28] as above.\n2. Add some details about how to choose $p$.", "broader_impact_concerns": "No broader impact is discussed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper receives three positive reviews from experts in stochastic optimization. The reviews acknowledge the novelty of the theoretical analysis and the algorithm design, as well as the extensive experimental analysis. In particular, the paper presents interesting convergence analysis based on convergence in distributions, which has potential to be applied to other convergence analysis. The theoretical analysis seems to be rigorous. Efficient implementation based on rolling quantiles is also given with experimental verification. 

Suggestion: it may be better to remove the contents part in the paper.
Decision: Accept (poster)