Online robust non-stationary estimation
Authors: Abishek Sankararaman
Murali Balakrishnan
Venue: NeurIPS 2023 poster (2023)
Keywords: Estimation
heavy-tails
distribution shifts
regret
TL;DR: We give the first provable, algorithm for learning on a data-stream containing heavy-tailed inliers, distribution shifts and outliers.

Abstract: The real-time estimation of time-varying parameters from high-dimensional, heavy-tailed and corrupted data-streams is a common sub-routine in systems ranging from those for network monitoring and anomaly detection to those for traffic scheduling in data-centers. For estimation tasks that can be cast as minimizing a strongly convex loss function, we prove that an appropriately tuned version of the {\ttfamily clipped Stochastic Gradient Descent} (SGD) is simultaneously {\em(i)} adaptive to drift, {\em (ii)} robust to heavy-tailed inliers and arbitrary corruptions,  {\em(iii)} requires no distributional knowledge and {\em (iv)} can be implemented in an online streaming fashion. All prior estimation algorithms have only been proven to posses a subset of these practical desiderata. A observation we make is that, neither the $\mathcal{O}\left(\frac{1}{t}\right)$ learning rate for {\ttfamily clipped SGD} known to be optimal for strongly convex loss functions of a \emph{stationary} data-stream, nor the $\mathcal{O}(1)$ learning rate known to be optimal for being adaptive to drift in a \emph{noiseless} environment can be used. Instead, a learning rate of $T^{-\alpha}$ for $ \alpha < 1$ where $T$ is the stream-length is needed to balance adaptivity to potential drift and to combat noise. We develop a new inductive argument and combine it with a martingale concentration result to derive high-probability under \emph{any learning rate} on data-streams exhibiting \emph{arbitrary distribution shift} - a proof strategy that may be of independent interest. Further, using the classical doubling-trick, we relax the knowledge of the stream length $T$. Ours is the first online estimation algorithm that is provably robust to heavy-tails, corruptions and distribution shift simultaneously. We complement our theoretical results empirically on synthetic and real data.

Online robust non-stationary estimation
Abishek Sankararaman
Balakrishnan (Murali) Narayanaswamy
(abisanka, muralibn Sariiinn@aannn @amazon com, Amazon Web Services, Santa Clara CA, USA.
Abstract
The real-time estimation of time-varying parameters from dighh-dmmessonnl, heavy- tailed and corrupted data-streams a common sub-routine in systems ranging from those for network monitoring and anomaly detection those for traffic scheduling in data-centers. For estimation tasks that can be cast as minimizing strongly convex loss function, we prove that appropriately tuned version of the clipped Stochastic Gradient Descent (SGD) is simultancously (i) adaptive to drift, (ii) robust heavy-tailed inliers and arbitrary corruptions, (iii) requires no distributional knowledge and (iv) can be implemented in an online streaming fashion. All prior estimation algorithms have only been proven posses a subset of these practical desiderata. A observation we make is that, neither the (+) learning rate for clipped SGD known to be optimal for strongly convex loss functions of stationary data-stream, nor the O(1) learning rate known be optimal for being adaptive to drift in a noiseless environment can be used. Instead, learning rate of T for
where T' is the stream-length is needed to balance adaptivity to potential drift and to combat noise. We develop a new inductive argument and combine it with a martingale concentration result to derive gegh-probability under any learning rate on data-streams exhibiting arbitrary distribution shift proof strategy that may be of independent interest. Further, using the classical doubling-trick we relax the knowledge of the stream length T'. Ours is the first online estimation algorithm that is provably robust to heavy-tails, corruptions and distribution shift simultaneously. We complement our theoretical results empirically on synthetic and real data.
Introduction
Technology improvements have made it easier than ever to collect diverse telemetry at high resolution from any cyber physical system, for both monitoring and control (31). This in turn has led to data deluge, where large amounts of data must be processed at scale [ Given the scale and velocity of the data sources, offline processing to make predictions and decisions is computationally cumbersome. For real-time applications such as performance monitoring and anomaly detection, offline/batch processing results in stale predictions (6]. 61). (54). This necessitates computationally cheap, online algorithms that make predictions and decisions on high-dimenssioall streaming data 41. 21. [58]. Further in many applications, the challenge being restricted online algorithms is exacerbated by heavy-fails (2). (3], distribution shift 488 [28 and outiers/anomalles in the
data-stream (29.
In practice, although several heuristics to circumvent these issues
35 42 there is systematic study of the impact of these challenges on the achievable statistical accuracy. Motivated by these problems, we study algorithms for high-dimensional online statistical estimation and rigorously establish performance guarantees which exhibit graceful degradation with distribution shift and outliers in the dtta-stream.
have been designed 1 66
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Gauss an
Pareto
Cumulative regret
Pareto
1000
1NT
13
Gaussian g-1R
bamples Comuptions
600
Goussian 7
403
200
75
100
150
50 125
150
100
(a)
(b)
(c)
Figure 1: Figures (a) and (b) show stream of independent samples (with some corruptions) from unit-variance Gaussian and Pareto distribution with shape parameter 2.001 respectively when the underlying true mean changes with time. Figure (c) shows that clipped-SGD with clip-value of incurs lower regret in estimating the true time-varying mean when the learning rate is set to 1/ / as opposed to the standard 1/(l known to be optimal in stationary environment.
1.1 Problem Setup
The online estimation problem we study is modeled interaction between oblivious adversary and the estimator. The adversary before the interaction begins makes two choices - (i) a sequence of probability distributions FI, Py on I&d and (ii) sequence of measurable corruption functions (C.) where for every t E [T C. Rdxt x Rxxt-1 x RRxt-1 + IRd, whose roles we explain below.
Sequential interaction protocol: At each time E [T], the vector X, == Ze + C., where Ze ~ P. is sampled independently and C, :- C,((Z.)sst, (Cs)aet, (0s)set) is the corruption vector computed using corruption function based on the past random samples and ouiputs. X₃ is shown input the estimation algorithm. Subsequently after observing Xt, the estimation algorithm outputs an estimate 0, E θ and incurs loss 4 := ||0 - 07 Here, strongly convex loss function, ④ C. IR closed convex set denoting the parameter space, and 8r := arg minøge Ez,p, [Z(Z, 0)] is the unique optimizzr of the loss function with respect to the distribution Pt, chosen by the adversary at time f. For every time t, we denote this minimizer 07 E θ as the true parameter at time t. The incurred loss l is un-observed by the algorithm since the true parameter is unknown.
Rd x R' + R a
Formally, an estimation estimatiorFalgorrinn algorithm = (At) a sequence of measurable functions such that for all E [T]. the estimate output := := AX,, X1). where A, Rdxt Rº function of all inputs upto and including time t. After outputting an estimate 0,, the algorithm incurs un-observed loss which is the L2 distance between the estimate and the true parameter.
Causal property of the adversary: Recall that at each time t, the corruption vector is given by C, C. C,(()) (C.)a<t, (0.) which is based only on the past realizations' Zi.... Zt. C CI, ,......--I11 and the estimator's s past outputs ,0,-1. The adversary does not have access to future randomness ".. ZT while choosing the corruption vector Ct. This model of corruptions is stronger than those used in online robust estimation (cf. [19]. adversary can choose the time instants of corruption while in previous models, the time instants of corruption are chosen randomly through i..dd coin flips. Our model of corruption locations are motivated by empirical observations that corruptions rarely occur randomly and are typically bunced Thus we assume that the adversary has causal power to choose the location of corruptions rather than corruptions occuring at random instants.
(3) since in our model, the
23 42
Regret as a Performance Measure: The regret of the algorithm denoted by Regy is defined as
Reg,
Σ t=1
4
10
1=1
Wee denote by T := (1,... Throughout, denote by || as the 1.2 norm operator.
3 Connexxtt implies existence and uniqueness o E In the literature, this is sometimes also denoted optimization algorithm. c.f.

---

the total cumulative loss. This definition is known as clean dynamic regrer [33 since (i) 0r is compared against the true parameter 8r, even if the input X, at time is corrupted, i.e., even Ct * O, and (ii) 0g is compared to the time-varying optimal 07. Technically the regret of an algorithm 2 is a random variable that is a function of the probability measures (P+) and the corruption functions {c and denoted as Regr whenever is clear from context.
(21) ((P:))=1, (C.)==)). We will denote the regret as Regr
We now define the data-stream complexity parameters impacting regret: (i) distribution shift and (ii) corruptions.
Distribution S The cumulative distance between successive optimum points 2r == Ei 00; - 07-11 measures the complexity of distribution-shift on the data-stream. This is a natural measure since if the estimator outputs 0, θ at time t, will incur an L2 loss 4 ||0: 0,
Corruptions:
The corruption measure the count Ar Σ 1(C, * 0), of the number of times the random sample Z is corrupted before inputting to the estimator. The count Ar is a random-variale since the vector C₁ is deterministic function of past random variables.
With this setup, the main desiderata we seek of an estimator is that it (i) is online ((d) run-time per data point stream and (d) overall memory, (ii) is free of distributional knowledge, i.e., does not require bounds on moments of (IPx) ((Pt)s2, distribution shift or corruptions,
(iv) attains sub-linear in T' regret even when the distributions (IP+) (121 are heavy-tailed, and (v) exhibits graceful degradation of regret with respect to distribution shift and corruptions on the data stream.
1.2 Main Contributions
1. Problem formulation and lower bounds: We formalize the problem of online estimation under drift and corruptions and define dimension- ffree target regret benchmark in Equation ( that captures all the aforementioned desiderata. We give lower bounds in Propositions [6. and 2.6 that shows the necessity of assumptions such as finite diameter for the set θ C RR in which the
unknown parameters 0j E lie. Further discussion in Table and Section I1
2. High-probabiiliyy upper bounds: Theorem 5.1 proves that a tuned version of clipped- -GD achieves all aforementioned desiderata. No previous algorithm achieves all the desiderata simulta- neously (Tables and Further in Theorem 4.3 we show that if in addition the data-stream is sub-gaussian, then our bound is optimal in the sense when instantiated with special cases of having no drift and corruptions [4 in the setting of no corruptions and 0 variance 43 it recovers known optimal results.
3. Algorithmic insights: Our key finding is that neither the learning rate of O(1) known to be optimal for SGD to adapt to distribution shift in the absence of noise, nor the ((1/l) learning rate known to be optimal in a stationary environment can be used. Instead learning rate of T for < 1 is needed to combat noise and be adaptive to drift simultancously. See also Figure I We show a lower bound in Proposition 6.1 that this insight is fundamental and not an artifact of our analysis. Knowledge of 7' is relaxed using the doubling trick in Section [4 in the Appendix. Our result improves prior state of art in S that show that in the absence of corruptions, SGD without clipping can give sub-linear regret bounds holding in expectation. However, in the presence of heavy-tailed noise, high probability guarantees are more insightful compared to only in expectation [63]. Our algorithmic contribution is that a tuned version of clipped SGD can give high probability sub-linear regret guarantees, that hold even the presence of non-stationarities and corruptions.
4. Technical contributions in the proof techniques: From technical perspective, we employ novel proof techniques to derive high-probability under any learning rate on data-streams exhibiting arbitrary distribution shift.. The prior state-of-art analysis in [36] (55) are limited to the specialized setting when the learning rate is 7) = 1/(t + 1) and the data does not exhibit drift. To adaptive to drift requires newer techniques even in the case of sub-gaussian tails to achieve dimension-fiee bounds (cf. Section 4.1. We used an induction based technique to apply martingale concentrations in Lemma 19.9 We build upon this technique using contradiction arguments in Lemma 10 extend to the heavy-tailer case. These arguments are of independent interest to prove bounds for other iterative algorithms.
FFollowin convention
22 use the term drift to refer to distribution shift
3

---

Setting
Best lower bound
Best upper bound
Stationary, no-corruptions
[[vT(y TTace(E.)
O[VT( Trace + Vinaz (2) In (T
(fr = 0, Ar = 0)
+ Mmar
2)) 1 (1/6]
10
Stationary, corruptions
Prop 2.6 ((ArD)
Thm 5.1
Ö + THDAT)
(Ør = 0, Ar 2 0)
Non-stationary, no-corruptions
8 ((T2/11//3))
Thm 5.1 O + T 0²) gives bound in expectation only.
(Ør 2 0, Ar 0).
Non-stationary, corruptions
(4r 2 0, Ar 2 0)
Prop 16.1 Ω (A+D)
Thm 5.1
Ö(r 2r + T + T D)
Table 1: Regret bounds for online estimation with heavy-tailed data and strongly convex loss. The setting of Φr 0, Ar 0 (line 1) characterized (upto log factors) in [TO] and [38]. The first dimension free. high probability upper bounds are established in this paper for all other settings. For the setting of (t, 2 0, AT = 0), [8 gives a lower bound and an upper bound holding expectation, while ours is the first high-probability upper bound. Except line 1, there is gap between known lower and upper bounds, closing which is an open problem (see also Section
1.3 Motivating application
Online Anomaly Detection (AD) problems consist of loss function L(:;-) and parameter 0g that varies with time i, such that for the input X, received at time f, the algorithm outputs anomaly score S, [(X,, 0z) (147), (I2]). The objective is output lower scores for samples that are not corrupted, i.c., if at time è the data distribution is Z₁ ~ Pt. then the optimal anomaly score St == _(X,, 0f) the one produced by the model minimizing the average anomaly score i.e., or arg minøge Ez-p, [C(Z, f)] [5T] The distance |60 6, between Be the model used at time t and the optimal 07 is measure of AD performance degradation 32 50 motivating our study of low regret algorithms.
Special cases of such problems include robust online mean estimation 19 and robust online
linear regression (20). both of which we consider in simulations in Section 7 The online mean
estimation corresponds to C(X, 0) == 1 ||| 012 since arg ming Ez-r 7 0|33] (Zzzr
Online linear regression corresponds to splitting the input X E Rdd as X = (x x with ( E Th and (2) RRd and using the re-construction loss L(X, 0) == ( 8" X as anomaly score. The linear regression setting of detecting anomalies by reconstructing one half of the input X from the other is popularly known as self-supervised AD models (52). Empirically, in (30], C(X,0) 0) := || (Ula 0)X || with 0 E dddd matrix of rank k < d and IL E Rddd the identity matrix is used to detect anomalies. The linear model of [30] is extended to a non-linear setting in [42), using an auto-encoder [65]. In (17). tree density model for C(X, 9) is studied. These papers' focus is empirical and do not give statistical guarantees.
Organization of the Paper: In Section 2 we state the target benchmark regret along with the
assumptions under which we seek and appropriate lower bounds. In Section give the clipped- SGD algorithm. In Section 4 we give results under the additional assumption of sub-gaussian tails. This helps build intuition and proof techniques for the general result which we give in Section 5 We state implications of our results in Section 6 provide empirical evidence in Section 7 discuss related work in Section and conclude with open problems in Section
2
Formalizing the desiderata
we state some mild assumptions standard in the study of statistical estimation under which we seek guarantees [55] 19).
Before formalizing the desiderata in Equation I
2.1 Model Assumptions
Assumption 2.1 (Strong convexity). There exists 0 m < M oo known to the algorithm, such that for all f, the function - Ez-r, [C 0)] is M smooth and m strongly convex.
This is a benign assumption that essentially states that properties of the loss function such as the convexity and smoothness are known to the estimation algorithm.

---

Moment assumed
Drift tolerance
Corruption tolerance
Free of distributional knowledge
Methods
Regret
O(avT)
2
X
36
O(oT2/P)
p (1,
OlvdT+
19
2
0
O(T)
x
(dT))//AA
Corollary.
4.8
OTT T
sub-
O
o(T
X
(This paper)
Nr)
gaussian sub-
Theorem 4.3
O(T"01 + +T
O(T2~9)
(This paper)
DT'
gaussian
Corollary 5.3
0(14/54) T
2
O(T1/33
O
(This paper)
D Ar)
Theorem 5.1
+1 OTT
2
O(T 5
O
(This paper)
D
Table Comparison of hiigh-probability regret bounds of online estimation algorithms of strongly convex functions under various moment assumptions. [55] requires distance of the initial point to the unknown optimum. Theorem 4.3 Corollary [.8 [99 and [55] requires bound on σ.. Further, [19 is not dimension- ceneesioon-fre as regret depends on d. We do not include g as their regret bounds only hold in expectation and not with high probability.
Assumption 2.2 (Convex domain). The algorithm knows a closed convex set θ C R2 such that for all 07 : arg mingge Ez-z, [C(Z, [L(Z, 0)] E θ is the true parameter be estimated at time
Assumption 2.3 (Finite diameter). The diameter D == maxX,,ve || yll of θ is finite, i..., D < co.
This is necessary assumption when Ar > 0 (Proposition 2.6 If Ar O, we relax this assumption in Corollaries 4.5 and 5.4. Let (0) = Ez .P, [C( 0)] denote the population risk at time
Assumption 2.4 (Known finite upper bound on the true gradient). There exists known finite G < such that supoce (+) S G.
This is necessary for many online optimization algorithms
36 55
2
Assumption 2.5 (Existence of second moment). There exists a matrix > O, unknown to the algorithm such that for all and / E O, the covariance of the random- L[(, 0)) is bounded by Σ, i.e., Ez-r, (Vt.e,./(CC/), 0) (O) (VL(Z, 8) (R). = holds for and
The class of distributions admissible by this assumption is large including all sub sub-gaussian distri- butions and heavy-tailed distributions that do not have finite higher moments 255 44]. Observe that parameteric assumptions
the distribution family is made. Throughout, and D maz (Σ) as the trace and the largest eigen-value of E respectively. For a positive semi-definite
denote by d²
matrix Σ E PR P(E) is the set of all probability measures satisfying assumptions 2.1 2.4 and 2.5
2.2 Target benchmark for algorithm design
We say that an estimator free of distributional knowledge if it does not need as input bounds on either the moments of IP nor on the stream complexity ΦT and Ar. Our key focus formalized below in Equation (T) - is: can we design an online algorithu without distributional assumptions that has sub-linear regret and that degrades gracefully with drift and corruption?
Can we design an online algorithm 2l without distributional knowledge, such that I, m, < 1 such that v Σ > 0 E RPx,, (IP))== E P(E) and (C.)²=.. the regret bound
( 0o (I'eT + m + T (TDD)))ppp poly (a, (
1
Regr
holds with probability at-least 1 - 8?
&a (0, is input parameter.
5

---

Throughout, we use (.) to hide poly-logarithiic factors. Our main result is Theorem 5.1 where we prove that tuned clipped SGD achieves this, and our other desiderata.
2.3 Why is Equation a good benchmark for regret bounds with drift and corruption?
The benchmark demands robustness to heavy-tailed data, since regret is sub-linear for any distribution with finite second moment. The benchmark is dimension free, since dimension terms d. p do not appear in Equation (I). The finite diameter 'D only affects the bound due to corruptions and nor the other terms. In particular, if Ar bound even if D = oo. In general when Ar > 0 however, dependence on cannot be avoided as we show in Proposition below (proof in Section I6).
almost-surely then the benchmark seeks valid
Proposition 2.6 (Finite diameter is necessary even in the absence of drift). There exists a strongly convex loss function L such that for every D > 0 and d E N, domain θ {z E Rd ||a||| S D) such that for every T E I and every algorithm, there exists probability measure I' on R. from which the un-corrupted samples are drawn from (i.e., 인 0) and sequence of corruption sunuution,uunctions (C,)²= such that the regret is at-least (D) with probability 1.
Thus, even if there is no drift, finite diameter assumption cannot be avoided. Proof is given in Section [6. relies on the modeling asumption that the corruption locations can be arbitrary. This lower bound in contrast to prior work [19] which shows that finite diameter is not necessary in the absence of corruptions and when the time instants of corruptions are random. Further in Table T we compare the best known lower and upper bounds for the various settings in the presence and absence of distribution shifts and corruptions. As can be seen, in all cases involving either distribution shift or corruptions, our work is the first to give high-probability estimation regret bounds.
Equation ① gives drift and corruption tolerance as additional performance measures: Since the regret explicitly depends on Φy and Ar we can define the drift tolerance and corruption tolerance as performance measures of the algorithm. Drift (Corruption) tolerance the largest Φr (largest Ar) for which we still guarantee sub-linear in T regret. Thus, if Equation ① is satisfied by an algorithm, then the drift and corruption tolerance is O(T1-)) and (TTl-a) respectively. Thus, higher these tolerances, the better an algorithm is as they indicate that the algorithm's 's degradation with drifts and corruptions are more graceful. Our method is the only one to have non-zero drift tolerance (Table 2)
3 The clipped SGD Algorithm
In this section, we formally describe the algorithm in Algorithm | that achieves the desiderata. Algorithm produces estimate time / is given by 0, Pe (0,0) m/cliip( LLX,, 0-- A)), where Pe the projection operator to θ and clip(æ,, e) == min(1, c//le//llxx])) Vo E Rd 2 0.
Algorithm 1 Clipped-SGr [55]
1: Input: (M))21, > 0, 0 e,,7 time-horizon
2: for each time 1,2, , do
3: Receive sample X,
4: Output 0g + Pe (0,-1 mclip(V(((X,00-.,,
5: end for
Intuition for why Algorithm I can achieve Equation (I) If there is distribution shift or corruptions, clipped SGD with appropriate learning rate converges to the true parameter (55). Now, if there are corruptions, clipping limits the impact the overall regret. On the other hand, when distribution shift occurs, the dynamics of Algorithm [T]s equivalent to restarting estimation under the new distribution, which will converge to the true parameter of this shifted distribution [55
4 Regret bounds when the gradient vectors have sub-gaussian tails
Before giving the general result, we consider the special case of sub-gaussian distributions this section. We do so because (i) the additional structure of sub-gaussian distributions enable us to prove stronger results in (r.6olaries44.6aandd case enables to build towards the proof of the general setting.
in the sequel, and (ūi the proof techniques from this special

---

Definition 4.1 sub-gaussian random vectors, [57]). A random vector Y E R with carvinancce matrix E is said to be sub-gaussian, if for all > 0 and u E R' with || = 1, (Y S
(E) where (2)) is the highest cigen-value of Σ.
Assumption 4.2 (Sub- gaabbggasssinnn assumption with known upper bound), For every I, and E O, the mean random vector VC(Z, 8) (0). where Z ~ P. is sub-gaussian with covariance matrix upper-bounded in the positive semi-definite sense by an known positive-semi-defiiit matrix
The following the main result of this section.
Theorem 4.3 (Informal version of Theorem 18.1). Suppose Assumption 4.2 holds. For every ō E (0. 1), if Algorithm is run with conslunt step-size y mī for E [0, 1] and clipping value À 2 G+o+0
max (2) In (3) then with probability at-least 6.
TI+aor (V (E) Iu ( to
Regr I <0 T +
+
Regret from distribution shift
T2
T
V Umman Σ) In
+
T V Regret from corruptions
(2)
Finite sample estimation error
The main achievement in Theorem 4.3 is in explicitly identifying how the choice of trade-off's the regret contributions from distribution shift, finite sample error and corruptions. Remark 4.4 (Corruption and drift tolerance). When Theorem 4.3 instantiated with a E (0, 1). Equation
2 yields a drift tolerance O(Tl-a) and corruption tolerance of O ). In particular, instantiating with 2/3 yields (TT1/3) and (T22/3) corruption and drift tolerance respectively.
We now read off several corollaries from this result.
Corollary 4.5 (Finite diameter assumption can be relaxed in the absence of corruptions). Let Ag almost-surely, iee., there are no adversarial corruptions. Then, under the settings of Theorem
4.3 even when the set θ is unbounded, the regret bound given in Equation (2 holds.
Corollary 4.6 (Optimal in the stationary case:). Under the assumptions of Theorem 4.3 if PT
Ar = 0, then when Algorithm 7 is run with parameters X too and 1j 1/mTT, the regret bound
Regr S O TT m (V Vuma E) (T + o)) holds with probability at-least 1 6.
This corollary recovers the well known result 24 of convergence of SGD on strongly convex functions with aab-gaussian gradients.
Corollary 4.7 (Optimal in the noiseless setting). Under the assumptions of Theorem 4.3 if Ar and a 0, i.e., there is no noise, then running Algorithm with = +00 and regret bound of Regt 0 (.)).
m obtains
This result matches the lower bound in the noise-less setting (67 and recovers the upper-bound by previous analysis of online clipped-SGD specialized to the noiseless setting 43
Corollary 4.8 (Special case of = 2/3). When Theorem 4.3 is instantiated with a = 2/3, then w.p. at-least
regret bound of Regr S (/T
T (ool((o G, In(T))))).
T
Remark 4.9 (The excess risk can be bounded using smoothness). Oftentimes, the regret is also measured through the excess risk, i.e., Σ E. Ez-r, [2(Z, 02) L(Z, 07)). Since assume that L
M smooth (Assumption 2.1 Theorem 4.3 also bounds the excess risk regret by observing that
Ez-P, [C 0,) L(Z, 8
0,
4.1 Proof sketch for Theorem 4.3 and technical innovations
The full proof Appendix T8. We first establish due to the condition on À that input sample not corrupted, then the gradient will never be clipped. Then in Lemma 19.6 we expand the one-step
7

---

recursion of the clipped SGD updates by exploiting the cononnxtt....t...... In order to account for the effect of corruptions. we expand the recursion differently if a time-step corrupted or not. If time-step is corrupted, then we accumulate both a bias term of norm at-most À and an appropriate variance term, If one were only interested in bounds in expectation, then the proof will follow the standard clipped SGD analysis as the expectation of the variance terms are 0.
To prove a high probability bound, a natural approach the variance terms as done in (24] in the absence of drifts and corruptions. A naive way to apply martingale concentrations would be to bound the variance error terms due to drifts and corruption by the worst case error by using the finite diameter D. However, this will not lead to the dimension free bound of Theorem 4.3 -inteadd will lead to bound in where the finite diameter D will also multiply the regret term due to finite sample eπror. In particular, this approach will not result in Corollary 4.5 of being able to relax the finite diameter assumption the absence of corruptions.
apply martingale concentrations bound
We circumvent this issue by using an inductive argument to bound the variance terms in Lemma 19.9 Concretely, we prove the induction hypothesis that for each time error terms until time is bounded by an appropriate function of the drifts and corruptions. To establish the induction for time t, we condition on the event the hypothesis holds till time f 1, and employ martingale concentration to show the error at time is small. Then we plug the martingale bound back into the one-step recursion and show the induction hypothesis also holds time t. To get the final oo-conditional result, we un-roll all the conditional events by an union bound.
5 Regret bounds in the general heavy-tailed case
The following is the main result of the paper, where we relax Assumption 4.2 and thus making the algorithm free of distributional knowledge and allowing for potentially heavy-tailed data.
Theorem 5.1 (Informal version of Theorem 20.1
When Algorithm 7 is run with clip value then for every ô E (0,1).
2GT', and step-size 1) mf for [0,
GoT DT m312
oT to DT
T' 3 (G (T)
T ATG
Regt 50
3//2//
m
m
Regret due distributtin shift
Fintie-sample estimittion error
Regret from corruptions
(3)
holds with probability at-least 1-
The achievement in Theorem 5.1 is in explicitly identifying how the choice of trade-offs the regret contributions from distribution shift, finite sample error and corruptions, despite heavy-tailed data.
Remark 5.2 (Price for relaxing assumption 4.2 is sub-optimal bound in the stationary case:). 5.1 is weaker compared that of Theorem 4.3 since (i) sub-gaussian tail
The setting in Theorem 5.1 assumptions are made, and (īi) no knowledge of the upper-bound matrix Σ is assumed. The price for relaxing these assumptions is a weaker regret, specifically in the term due to finite-sample estimation error. This term scales as O(T -3 in Theorem 5.1 while it scales as ( $ in Theorem 4.3 In particular in the stationary case, when Equation (3) is instantiated with
1, the regret bound reads as Regy 2/12/3 02) which is weaker than the optimal O(VTo) for the stationary case [55 39].
Corollary 5.3 (Setting a 1/2). Under the conditions of Theorem 5.1 a = 1/2, then with probability at-least - 6, it satisfies a regret bound of Reg < ( Dy T11/1 / + T5/6 + T3/4 A3 G, G.//m, (n(T)
if Algorithm 7 is run with
Corollary 5.4 (Finite diameter assumption can be relaxed in the absence of corruptions). Let
Ar O almost-surely, ie., there are no adversarial corruptions. Then, under the settings of Theorem
5.1 even when the set θ is unbounded, the regret bound given in Equation (3) holds.
Remark 5.5 (Corruption and drift tolerance). Theorem 5.1 when instantiated with a E (0. 1) yields drift tolerance of O and corruption tolerance of O(T1- -) In particular, instantiating with 1/2 yields 133 and O(T1/4) corruption and drift tolerance respectively.
8

---

6,-01r A.
By 0. D
280
Awa21
14
200
3.0
4.5
8.0
15
13
10
(a)
(b)
(c)
(d)
Figure 2: Plot of regret versus over 10000 steps for mean-estimation. We observe that the best
choice of a decreases as Φr and/or Ar increases, More details in Section 7
5.1 Proof sketch of Theorem 5.1 and technical innovations
The proof for this case builds upon the techniques used to prove Theorem 4.3 gaussian case, we cannot guarantee that only corrupted samples will be clipped in the general case. This introduces an additional bias and variance terms due to clipping of potential un-corrupted samples or inliers. The bias terms of the inliers are handled using techniques from prior works We bound the variance terms using an inductive argument similar in spirit to that of Theorem 4.3 However, identifying the correct hypothesis involving drifts and outliers so that the induction argument holds is challenging. The challenge is because the induction hypothesis assumed till time f 1 impacts the martingale error term, which in-turn impacts whether the induction hypothesis will hold at time t. We introduce a free parameter to the regret term and deduce the induction hypothesis to hold a quadratic equation in this parameter does not have any real roots. This extra term contributes to regret degradation compared to the sub-gausse uub-gaussian case (Lemma 20.10).
Unlike in the sub-
[25 55
Insights and remarks
Known Time Horizon: This is benign assumption and can be overcome by the standard doubling trick (Section 2.3 of [TI) with additional log"(T) factor regret (c.f. Appendix 14).
Price for being adaptive to distribution shift: Theorems 4.3 and 5.1 show that, in order to minimize i.e., choose learning rate of O11/T). This was shown to be optimal in in the absence of drift and corruptions both under sub-gaussian assumptions (24 and in heavy tail settings
regret due to statistical estimation, we need set
[55]. On the other hand, see from Theorems 4.3 and S. that in the presence of drift o > 0, a learning rate a < is sufficient to ensure sub-linear regret. The following lower bound (proved in Appendix [5) shows that a is also necessary.
Proposition 6.1 (Lower bound showing ( learning rate is not adaptive to drifts). There exists a loss function C such that for every T, there exists a sequence of probability measures (Pt) with the diameter D < 2 log(T), distribution shift 4T S 2 (T)) AT 0, such that Algorithm] 7
when with X 1 and step size π) := - र-
1 will incur regret at-least _ with probability 1.
Finite diameter is necessary in general: We already saw Proposition 2.6 that O(ArD) regret
is necessary. We prove the lower-bound by considering mean-estimation in Section 16. Variants of Proposition 2.6 was observed in the literature (for ex. Proposition 1.3 [3), Lemma 6.1 in [33], Theorem D.1 in [4), Line 8 of Algorithm 3 in (9)). In theoretical statistics literature, ((Ar is considered un-desirable [13] and thus the models studied restrict corruptions to occur at random times 13 [9) rather than arbitrary as in our setup. However, in practice corruptions are rarely random and typically occur close in time for instance due to machine failures or other external confounding factors 23 42
Regret bounds are dimension-free: The problem dimensions d, do not appear in the regret bound. Moreover, the finite diameter 'D only appears in the regret term affecting through adversarial corruptions and not in the distribution shift and finite sample error terms. Further, Corollaries 4.5 and 5.4 give regret bounds that hold even when D co in the absence of corruptions.

---

7 Experiments
Theorems 4.3 and 5.1 give upper bounds on regret showing that tuning the learning rate depending
on the amount of distribution shift and number of corruptions in the stream is beneficial. We empirically observe similar phenomena in Figures and (in the Appendix), thus indicating our
theoretical observations are fundamental and not artifact of our bounds. We consider L(X, 0)
X (x(2)
011 corresponding to mean-estimation
Figure and linear-regression of L(X, 0) =
- x where X = =(x(1, (2) with X E Rd-1 x E R. 0 E (R( in Figure in the Appendix in Section 12 We compare clipped-SGD with learning rate 1/miI" for variety of a with clipping À = 27 and use the doubling trick to remove dependence of II' (i.e., use 2 For the case of a = 1, we use the learning rate of 7/2 11/(m(L + 1)) and À = 2VT as suggested in [55]. All plots are averaged over 30 runs and we plot the median along with the 5th and 95th quantile bands. We observe in Figures aad that as 인r or Ar increases, the optimal to use decreases, validating the theoretical insight. Further details in the Appendix in Section Evaluations on real-data is conducted in the Appendix in Section 13
Algorithm
8 Related Work
FITNESS for mean estimation is proposed in [50] that requires variance as input and is adaptive to drifts and corruptions under sub gaussian distributions with per-sample computational complexity is OdT)). In contrast, our algorithm applies to any strongly convex function, does not require moment bounds, data can be heavy-tailed. The work of [8] studied regret bounds in the absence of corruptions and only give bounds in expectation. A sequence of papers in online estimation including [44 [46 13 23 [55] [5]] have derived algorithms that are robust in different ways. However, none of them consider the impact of distribution shift. The works of [46] 13 study robust linear regression in the absence of drifts with (46) making Gaussian assumptions
both covariates and response while 133 makes Gaussian assumption only on the responses. The work of 55 show that clipped SGD attains near optimal rates for any strongly convex loss function in the absence of drifts and corruptions. The paper of [1]] study online estimation of strongly convex loss functions with corruptions, but do not consider drift. Moreover, their regret bounds are not dimension free (cf. Table D Although the paper of (64) gives regret bounds for online learning, more general setting compared to estimation, do not consider impact of drifts. High probability bounds for optimization with heavy-tailed data have been studied by [44] 25 15] 60 36] in recent times. However, none of their analysis considers the impact of drift and corruptions. More related work in Section I0]
Conclusions and Open Problems
We studied online estimation in the presence of drifts and corruptions and potentially heavy-tailed inlier data and proved regret bounds for clipped SGD for strongly convex loss functions. Ours is the first proof that online algorithm can simultancously be robust to heavy-tails and corruptions and adaptive to drift. A key result was to show how the choice of learning- rate trades off drift, finite sample error and corruptions. Our work leaves several interesting open problems.
The optimal choice of a in Theorems 4.3 and 4.3 is a trade-off between distribution shift, finite sample error and corruptions. Can the optimal a set without knowing ΦT, Ar or a in advance?
(TT(T "ooyo"yGG In the absence of corruptions, can regret (( ((VV++TT )olyy(G o, be achieved? Such an algorithm would simultancously have both (i) O(T) distribution shift tolcrance which is the best possible and matching the lower bound established in [50], and (ii)
for some a < 1
closing the gap of Remark 5.2 for the stationary case.
Can m 1/2 in Equation T be achieved in the general case with drift and corruptions? Theorem 5.1 shows that only m 2 273 achievable. For the special case of stationary stream, (55) shows
m 1/2 is achievable, matching the lower bound that 1/2 is necessary.
(Open problem from (55) Does there exists an online algorithm that can obtain the statistically optimal regret of O T Tr(E) + VVmaz (E) log()))))) for stationary stream?
10

---

References
[1] Giuseppe Accto, Alessio Botta, Walter De Donato, and Antonio Pescapé. Cloud monitoring: A survey, Computer Networks, 57(9):293322115, 2013.
[2] Ashkan Aghdai, Fan Zhang, Nadun Dasanayake, Kang Xi. and H Jonathan Chao. Traffic measurement and analysis an organic enterprise data center. 2013 IEEE 14th International Conference High Performance Switching and Routing (HPSR), pages 49-55. IEEE, 2013.
[3] Mohammad Alizadeh, Shuang Yang, Milad Sharif, Sachin Katti, Nick McKeown, Balaji Prabhakar, and Scott Shenker. pfabric: Minimal near-optimal datacenter transport. ACM SIGCOMM Computer Communication Review, 43(4):435-446, 2013.
[4] Arthur Asuncion and David Newman. Uei machine learning repository, 2007.
[5] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Conference on Learning Theoor, pages 359-409. PMLR, 2021.
[6] Jarrod Bakker, Bryan Ng. Winston KG Seah, and Adrian Pekar. Traffic classification with machine learning a live network. In 2019 IFIP/EEEE Symposium on Integrated Network and Service Management (IM), pages 488-498 098-499..4 IEEE, 2019.
[7] Richard G Baraniuk. More is less: Signal processing and the data deluge. Science, 331(6018):717-71,,, 2011.
[8] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- tions research, 6355):1227-1244, 2015.
[9] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
[10] Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study. In Annales de I'IHP Probabilités el statistiques, volume 48, pages 1148-1185, 2012.
[11] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[12] Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3):1-58, 2009.
[13] Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Online and distribution-fre robustness: Regression and contextual bandits with huber contamination. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 684-695. IEEE, 2022.
[14] Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael Jordan, Nicolas Flammar- ion, and Peter L Bartlett. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.08137, 2020.
[15] Ashok Cutkosky and Harsh Mehta. High high-brobayility bounds for non-convex stochastic opti- mization with heavy tails. Advances in Neural Information Processing Systems, 34:4883 4895, 2021.
[16] Guido Dartmann, Houbing Song, and Anke Schmeink. Big data analytics for cyber-physical systems: machine learning for the internet of things. Elsevier, 2019.
[17] Ibrahim Delibalta, Kaan Gokeesu, Mustafa Simsek, Lemi Baruh, and Suleyman S Kozat. Online anomaly detection with nested trees. IEEE Signal Processing Letters, 23(12):1867-1871 2016.
[18] Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensionnal robust statisties. arXiv preprint arXiv: 909991009111 2019.
[19] Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, and Thanasis Pittas. Streaming algorithms for high-dimensional robust statistics. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5061-5117. PMLR, 17-23 Jul 2022.

---

[20] Jiashi Feng, Huan Xu, and Shie Mannor. Outlier robust online learning. arXiv preprint arXiv:1701.00251, 2017.
[21] Massimo Gallo, Alessandro Finamore, Gwendal Simon, and Dario Rossi. Real-time deep learning based traffic analytics. In Proceedings of the SIGCOMM 20 Poster and Demo Sessions, pages 76-78.22 2020.
[22] João Gama, Indré Žliobaité, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM computing surveys (CSUR), 46(4):1-37, 2014.
[23] Peng Gao, Xusheng Xiao, Zhichun Li, Fengyuan Xu, Sanjeev R Kulkarni, and Prateek Mit- tal. {AIQL]: Enabling efficient attack investigation from system monitoring data. In 2018 {USENIX) Annual Technical Conference ( CESSENIXJAATCE 18), pages 113-126, 2018.
[24] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: shrinking procedures and optimal algorithms.
SIAM Journal on Optimization, 23(4):2001 2013.
[25] 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.
[26] M Harries. Splice-2 comparative evaluation: electricity pricing (technical report unsw-cse- tr-9905). Artificial Intelligence Group, School of Computer Science and Engineering, The University of New South Wales, Sydney, 2052, 1999.
[27] Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
[28] Cormac Herley. Automated detection of automated traffic. In 31st USENIX Security Symposium (USENIX Security 22), pages 1615-1632, 2022.
[29] T Ryan Hoens, Robi Polikar, and Nitesh V Chawla. Learning from streaming data with concept drift and imbalance: an overview. Progress in Artificial Intelligence, 1:89-101, 2012.
[30] Hao Huang and Shiva Prasad Kasiviswanathan. Streaming anomaly detection using randomized matrix sketching. Proceedings of the VLDB Endowment, 9(3):192-203, 2015.
[31] Wazir Zada Khan, MH Rehman, Hussein Mohammed Zangoti, Muhammad Khalil Afzal, Nasrullah Armi, and Khaled Salah. Industrial internet of things: Recent advances, enabling technologies and open challenges. Computers & Electrical Engineering, 81:106522, 2020.
[32] Young-geun, Kim, Yongchan Kwon, Hyunwoong Chang, and Myunghee Cho Paik. Lipschitz continuous autoencoders in application to anomaly detection. In International Conference on Artificial Intelligence and Statistics, pages 2507-2517 PMLR, 2020.
[33] Adam Klivans, Pravesh Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018
[34] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, (6(11):2278-2)) 2324, 1998.
[35] Jia Li, Shimin Di, Yanyan Shen, and Lei Chen. Fluxev: fast and effective unsupervised framework for time-series anomaly detection. Proceedings of the 14th ACM International Conference Web Search and Data Mining, pages 824-832, 2021.
[36] Zijian Liu and Zhengyuan Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises. arXiv preprint 3rXiv:2333.12277 1227,
[37] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heave- distributions: survey, Foundations of Computational Mathematics, 1955:1145--1100, 2019.
[38] Gábor Lugosi and Shahar Mendelson. Sub-gaussian estimators of the mean of random vector. 2019.
12

---

[39] Gabor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: the optimality of trimmed mean. The Annals of Statisties, 49(1):393 410, 2021.
[40] Chaitanya Manapragada, Mahsa Salehi, and Geoffrey Webb. Extremely fast hoeftding adaptive tree. In 2022 IEEE International Conference on Data Mining (ICDM), pages 319-328. IEEE, 2022.
[41] M Hammad Mazhar and Zubair Shafiq. Real-time video quality of experience monitoring for https and quic. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pages 1331-1339. IEEE, 2018.
[42] Yisroel Mirsky, Tomer Doitshman, Yuval Elovici, and Asaf Shabtai. Kitsune: an ensemble of autoencoders for online network intrusion detection, arXiv preprint 0rXiv:/802.09000 2018.
[43] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimiza- tion in dynamic environments; Improved regret rates for strongly convex problems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195-7201, IEEE, 2016.
[44] Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 8009):1677-1627, 2019.
[45] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. CoRR, abs//2l 2
[46] Scott Pesme and Nicolas Flammarion. Online robust regression via sgd the 11 loss. Advances in Neural Information Processing Systems, 33:2540-2552, 2020.
[47] Maxim Raginsky, Rebecca M Willett, Corinne Horn, Jorge Silva, and Roummel F Marcia. Sequential anomaly detection in the presence of noise and limited feedback. IEEE Transactions on Information Theory, 58(8):5544-5588 2012.
[48] Hansheng Ren, Bixiong Xu, Yujing Wang, Chao Yi, Congrui Huang, Xiaoyu Kou, Tony Xing, Mao Yang, Jie Tong, and Qi Zhang. Time-series anomaly detection service at microsoft. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 3009-3017, 2019.
[49] Byron Roe, Hai-Jun Yang, Ji Zhu, Yong Liu, Ion Stancu, and Gordon McGregor. Boosted decision trees as an alternative to artificial neural networks for particle identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 543(2-3):577-584 2005.
[50] Abishek Sankararaman, Balakrishnan Narayanaswamy, Vikramank Y Singh, and Zhao Song. Fitness: tune on new and similar samples) to detect anomalies in streams with drift and outliers. In International Conference on Machine Learning, pages 19153-19177. PMLR, 2022.
[51] Bernhard Schölkopf, John C Platt, John Shawe-Taylor, Alex J Smola, and Robert C Williamson. Estimating the support of a niigh-dimensionee distribution. Neural computation, 13(7):1443- 1471, 2001.
[52] Vikash Sehwag, Mung Chiang, and Prateek Mittal. Ssd: A unified framework for self-supervised outlier detection. arXiv preprint arXiv:2103. 2021.
[53] Ohad Shamir. A variant of azuma's 's inequality for martingales with subgaussian tails. arXiv preprint 110.2:11 2011.
[54] Tushar Swamy, Alexander Rucker, Muhammad Shahbaz, Ishan Gaur, and Kunle Olukotun. Tau- rus: a data plane architecture for per- per-packet ml. In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1119, 2022.
[55] Che-Ping Tsai, Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. Heavy-tailed streaming statistical estimation. In International Conference on Artificial Intelligence and Statistics, pages 1251-1282. PMLR, 2022.
13

---

[56] Tim van Erven, Sarah Sachs, Wouter M Koolen, and Wojciech Kotlowski. Robust online convex optimization in the presence of outliers. In Conference on Learning Theory, pages 4174-4194, PMLR, 2021.
[57] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[58] Jonathan Vestin, Andreas Kassler, Deval Bhamare, Karl-Johan Grinnemo, Jan-Olof Andersson, and Gergely Pongracz. Programmable event detection for in-band network telemetry. In 2019 IEEE 8th international conference on cloud networking (CloudNet), pages 1-6. IEEE, 2019.
[59] H Victor. A general class of exponential inequalities for martingales and ratios. The Annals of Probability, 27(1):537-564, 1999.
[60] Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. Conference on Learning Theory, pages 65 102. PMLR, 2022.
[61] Liangcheng Yu, John Sonchack, and Vincent Liu. Mantis: Reactive programmable switches. In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communica- tion on the applications, technologies, architectures, and protocols for computer communication, pages 296-309, 2020.
[62] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:/905. 1881, 2019.
[63] 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 Neural Information Processing Systems, 33:15383-15393, 2020.
[64] Jiujia Zhang and Ashok Cutkosky, Parameter-free regret in high probability with heavy tails. arXiv preprint arXiv:2210. 14355, 2022.
[65] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. Advances in neural information processing systems, 31, 2018.
[66] Chong Zhou and Randy C Paffenroth. Anomaly detection with robust deep autoencoders. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 665-674, 2017.
[67] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936. 2003.
14

---

10 More related work
Comparison with [8] seminal work of [8] started the work on non-stationary estimation in the absence of corruptions. They establish regret lower bound of 12(61/37222 for non- -tatioati estimation in the presence of nonnstaaionaaiitis. They also established an upper bound by showing that SGD withoul clipping yields matching regret upper bounds in expectation. The upper bound in Theorem [_1 on the other hand gives high-probability regret bounds that hold even in the presence of corruptions, in addition to non-stationarities. Expressing an upper bound in high-probability is both technically challenging and algorithmically insightful. The insight we make is that for having
sogh-probbbility bounds, we need to have clipped SGD, On the other hand, since [8] only give bounds holding in expectation, they do not need any clipping in their algorithms. The necessity of clipping in heavy-tailed settings is not an artifact of analysis, but is crucial for good empirical performance, as noted in recent works of [55]. Thus conceptual contribution we make is that even in the absence of corruptions, a different algorithm compared [8] namely that of clipping gradients is required to get regret bounds holding in bigh-probabilit.. From a technical perspective, the proofs for high-probbbility bounds need different techniques as compared to [8) For instance, we need several martingale and induction arguments to arrive at high-probability bounds in heavy tails while [8] have a much more simpler proofs just based on convexity, since they only give bounds in expectation.
Robust Stochastic Optimization The paper of [44) proves high-probabilityy bounds for optimizing convex functions under heavy tailed gradients. However, they do not consider corruptions or drifts and assume finite diameter. In contrast our bounds explicitly depend on drifts and corruptions and can handle infinite diameter in the absence of corruptions. The work of (55 give nigh-probability bounds for offfine clipped gradient descent based algorithms for optimizing both convex and strongly convex functions. However, they do not consider drift or corruptions. The work of [60] studies convergence of gradient descent methods in the absence of second moments, but only give bounds in expectation and do not consider drift or corruptions. The paper of [15] give high-probability bounds for stochastic optimization, but their analysis does not consider drift or corruptions. None of these papers simultaneously consider drifts, corruptions and heavy-tailed noise. The paper of [63] extend this to heavy-tailed noise under only the E (1, 2] th moment and non-convex functions. However, they only give results in expectation and in a setting without drift and corruptions.
Robust Statisties There is a growing literature 18, 37 39 10 that give near-optimal offline algo- rithms in the presence of corruptions but no drifts. Since our focus to devise online algorithms that are adaptive to distribution shift, these algorithms are not directly applicable to our setting.
Dynamic Regret Minimization A parallel line of work concerns algorithms being adaptive drifts for online convex optimization problems (27) where the data are arbitrary rather than sampled from a distribution 667 65 56 5] However, these algorithms assume that there are no noise in the gradients and no corruptions on the data stream.
Gradient clipping The work of (45) showed clipping gradients practical work-around to the 'exploding gradients' problem. Theoretically, [62) study the effect of clipping in offline training under restrictive noise assumptions and do not consider impact of drifts and corruptions.
11 Key algorithmic challenge
All distribution changes initially look like corruptions
In this section, we give simple example to see whay developing algorithms that are robust to drift and corruptions are challenging. Consider a simple example of estimating the mean in the absence of noise, i.e., when variance is O. We will show two possible underlying scenarios that yield the same observation to the forecaster. In both scenarios, the observed samples are all 0 in the first T Ar rounds and is R +f 0 in all of the last Ar rounds. The first scenario is one where the true mean in the first T - AT samples is 0 and the true mean in the last AT samples is R. i.c., this scenario has no adversarial corruptions and cumulative distribution shift of R. In the second scenario, the true mean for all rounds is O, except the last Ar samples are adversarially corrupted, i.c., this scenario has no distribution shift but has Ay adversarially corrupted samples. If the true system is scenario 1, then the regret of a forecaster is the distance from the ground- R, while in the second scenario is the distance from the corrupted mean 0. Thus, any algorithm will ineur in leale one of the scenarios, regret of at-least RAZ This example highlights the main tension in the problem
15

---

6. T.-EXXT A0 007
D.
dy Ogri
11.5
11.
1000
332.
1- 10000
$220
M65
(a)
(h)
(c)
(d)
Figure 3: Over T 10000 steps, we vary 2T and Ar keeping the clipping value 2. for
linear regression. We observe that the best choice of a decreases as the distribution shift 4y and/or corruptions Ar increases.
distribution shift initially presents outliers and the online algorithm needs samples and thus incurs regret in order to learn this to be the 'new normal'.
12 Additional details on simulations
We give more details on experiments reported in Figures 2 and 3 synthetic data.
CraanEsttimatin Setup At each time f, we sample a 0 mean univariate random variable Y, from the Pareto distribution with mean O, variance 6² := 5 and tail parameter 3, so that it has finite second moment. The un-corrupted d-dimensional vector at time is denoted by Z, : (Vs-pe) V, is a unit vector sampled uniformly on the sphere of d = 256 dimensions. The true means μr are chosen by running random walk, i.e., 14g 0 and μl == [4--1 + Wt, where Wi .N (0, - This ensures that 7 z T* In Figures 2a
vd vr, where
set E (0.5, 0.25, 0.15,0) respectively. The instants of corruption are chosen integer multiples of [vT] and the observed sample X, if k| ([VT], for some non-negative integer k. Otherwise, X, = Z₁. For a given underlying mean vector, we run the streaming setup 30 times, and plot the average along with 95% confidence interval on the regret estimates.
2b
2d
Linear Regression Setup: We generate the covariate X, E R256 from a generalized Pareto distribution with mean variance o² == 1, i.c. m 1. The true parameter at time 0 was set to Oo == [d-0.5 d.s).. At each time f, the true parameter 0; we N (0, - E (0.5, 0.25, 0.15, 0) respectively.At each time the response Yt (x
+
We where
This ensures that 4r xe T In Figures 3a
3b
3c
3d we set
62
+ T4 where ne
is Pareto distribution with 0 mean, variance σ² = 3 and shape parameter 2.5. The instants of corruption are chosen at integer multiples of LvT]. At instants of corruption, the covariates are sampled from a normal distribution with identity covariance and mean 100. The response variable for corrupted time point is set to O. For given set of underlying mean vector, run the streaming setup 30 times, and plot the average along with 95% confidence interval on the regret estimates.
We compare clipped-SGID with learning rates γ)- == 1/mT" and clipping values A = 2 for a variety of a and B3. Further we implement the doubling trick given in Algorithm 2 so that clipped-SCCr Happed-SGDDoo does not require knowledge of the time-horizon T. In addition, we also compare against the clipped-SGD version of (55) which uses the varying learning rate of 1/(t) learning and clipping value of 2/T. Note that the algorithm of (55) has strictly more information than the one we implement it has knowledge of time horizon T for setting the clipping value, while the propose does not and relies on the doubling trick. Further, we do not assume that the set O is known and consider the un-projected clipped-SGD for our algorithm, while for that of (55), consider the smallest L2 ball around the horizon that contains all the (0:){=1 Thus, the algorithm we implement truly parameter-free
Methods:
it does not have any problem specific parameters in its implementation.
Observations: All plots Figure 2 show both mean-estimation and linear regression for varying amounts of distribution shift Φ while keeping the number of corruptions A = vT and clipping value \ 0.25 For both mean-estimation in Figures 2a
2b
2c 2d and linear regression in Figures
16

---

Dr Dr-01Tt) O
Fy - Ofr1ity
6i.- 017!!1)
Oy:
1g22 100
192
1ggu
n-
2030
13856
2000
1006
12600
2033
12000
1ime
11n
(b)
8000
3000
2000
400
Tee
See
Tere
(c)
(f)
(g)
(h)
Figure 4: Over T = 10000 steps. we vary of while keeping the number of corruptions Ay = VT and the clipping value X 0.2 the same. The top rows (a) - (d) are for the synthetic mean- estimation and the bottom figures (e) (h) are for linear regression.
3a
we show that as the amount of distribution shift &r increases, the learning rate needs to aggressive be adaptive to the distribution shift.
3b 3c
3d
Sample paths In Figure we plot a particular sample path over time for a variety of settings of a.
13
Real-data experiments
The key result of this section is that even real-data with real performance metrics, adapting the learning-rate to the amount of distribution shift on a data-stream is beneficial. We consider two tasks to demonstrate this online binary classification and online anomaly detection.
Dataset
Stream-length T
Task
Dimension d
ElectricityNSW 26 4]
45312
Binary classification
13
MiniBoone 49
130065
Binary Classification
50
MNIST
34
11811
Anomaly Detection
784
Table Real data-sets used.
13.1 Classification setting
Datasets:
We consider two binary classification datasets available from the UCI repository 4 (i)
NSW Electricity data [26] and (ii) MiniBoone data [49]. The NSW Electricity dataset consists of 45312 samples with each data-point having 6 numeric features and one categorical feature representing the day of week. After one- hot-encoding the categorical feature, we have 13 numeric features and binary target. The MiniBoone dataset has 130065 samples with each data point having 50 numeric features and binary target. We choose these two as they have been shown to be good binary classification benchmark for data-streams with drift [40] particular, the MiniBoone dataset extreme where the first 36499 has target of while all the last 93565 data points have target of 0.
For both the datasets, the order of streaming is the same order in which they are collected. This consistent with the evaluation protocol of streaming algorithms in the presence of drifts [40].
17

---

Electricity Dataset
MiniBoone Dataset
MNS1
10.2
A
11.4
10.1
11.2
0.20
10011 Poggecc
10.0
31.0
00.35
9.8
10.0
0.15
10.0
0.2
3.4 0.6
0.4 0.0 0.0
0.14 01 0.5
1.0
(a)
(b)
(c)
Figure 5: The plot of Regret with different choice of learning rate. In Figures (a) and (b), we plot the log(Regret), where lower is better, while in (c) plot the Drecision-Rectt area under curve, where higher is better. We see for the Electricity and MNIST dataset that a se 0.5 has the best performance, while for the MiniBoone dataset in (b), see that for MiniBoone not surprising as that dataset is has very little noise (a R 0) compared to the Electricity dataset. Thus, the optimal choice of is lower in MiniBoone compared the Electricity data. Furthermore, across datasets, tasks and models, our theoretical insights hold demonstrating that they are artifacts of analysis.
0 has the best performance. The result
Model and Methods: For both data-sets, we consider a simple one layer Logistic regression as the model train. We the gradient clipping value À for both datasets. For both these datasets, deviate from our setup and employ the classical online learning evaluation [40]. At each time 1, the covariate is first shown to the algorithm which then predicts the target. The prediction of the logistic regression is then threshold at 0.5. The instantaneous loss at time is the indicator loss whether if predictor after applying the threshold matches the target. The covariate and label pair is then used to take one step of clipped SGD in order to get the model used at the next time step. We experiment with different learning rates and plot their impact in Figure
Observations: We observe in Figure that for the Electricity dataset which has more shifts and is noisy 0, the optimal choice of Rd 0.5, while for the MiniBoone dataset has just one change point (i.e., T Ro 0) and is noiseless a RV (cf [0 Thus the optimal a Ro O.
13.2 Online Anomaly Detection
We modified to a stream containing drift and corruptions/aoomaliss as follows. We introduce abrupt change points by first streaming in all O's followed by I's and so on with the last of the stream being 9's. This way, the stream has 9 abrupt Stange-pointss In addition, within a change-point, the images are slowly rotating clockwise at fixed angle 1 degree rotation to model slowly varying change in between two abrupt changes. Anomalies introduced at random with probability 0.05 by sampling a digit other than the current segment of time. For instance 5c. the third point on the stream is an anomaly since the digit is different from 0 which is the inlier digit till the first break-point. Similarly, the last but one the data point on the stream is an anomaly since it is different from 9, the inlier digit in that segment.
Dataset: We considered the standard MNIST dataset 334]
Methods: We flatten the image into vector of 784 and consider simple 2 layer auto-encoder with hidden dimension 512 and activation function of ReLU [66). We initialize the network to be random at the beginning of the stream and consider clipped SGD with clip-value set to 5 for various learning rates as shown in Figure 5c| At each time f, the sample X, is revealed to the algorithm, a single clipped gradient step is taken this sample update the model and then the anomaly score is produced from the resulting model.
Observation: In Figure 5c we plot the anomaly detection accuracy measured through the average precision recall score, where higher the score indicates better AD performance. We see that neither too small nor too high value of a obtains the highest performance.
18

---

Abrupt change-points
X1
X
X
b
Time
Slowly varying rotations within change-point
Figure 6: The data stream of MNIST digits with drifts and corruptions. The stream is ordered such that all digits labeled arrive before digits labeled and so-on. The abrupt change points are time instants when the next digit starts appearing. Within an abrupt change-point corresponding to digit i (0,-... ,99 } and time-step t, with probability 0.95, a digit image sampled from the MNIST dataset without replacement, rotated by angle qr- With probability 0.05, image corresponding to a digit other than is sampled, which is labeled (but unknown to the algorithm) as true anomaly. marked with the red-boundie aodboonddry in the figure. The rotation angle varies with time as 4++1 = q + /i i... the rotations are slowly varying. The goal of the algorithm is to detect the true anomalies. In this experiment (see also Table 3). T = 1181 and the number of anomalies was 563.
These images
14 Removing the knowledge of time horizon T from Algorithm
In this section, re-state the doubling trick from to remove the dependence of the stream length on the learning rate tuning Theorems and
Algorithm 2 Online -iiniee--ppeeddeeeeee SGD without time horizon
1: Input: Learning rate exponent E [0, 1], clipping exponent 3 S 2. P θ initialization, m, .M
2: TIME HICEHOORZON + 1, 17 + 1, + 2m(G +
3: for each time = 1, 2, do
4: if HIMI-OOIIIIIO then
5: TIME-HORIZON <- 2* TIME-HORIZON
6: 1/ -TIHHE-ORR22O""
7: À < 2m(G 1)TIME-HORIZON
8: end if
9: Receive sample X₁
10: Output 02 < Pe - (cX
end for
Proposition 14.1 (II). for given a. 3,T, clipped-SGD satisfies R, < R(a, 3,T) In (T)
with probability at-least 1-8, then Algorithm 2 will satisfy regret Rr S (((o,,))))(ogg,(())) In with probability at-least 1 5.
Proof. Over a time interval of T, there are log, (T) times when Line of Algorithm 2 executed. Denote by the time-interval between successive executions of Line 5 as 'phase" of the algorithm. In the ith phase, the hypothesis of the proposition gives that with probability at-most ö, the regret in
phase denoted by R() 2 R(a, B, T) In (2) Thus, taking an union bound over all the log,
19

---

phases, we get that with probability at-least 1 log2 (T)), the total regret Rr is bounded by
1ogg(2)
2 r
RT S R(a, 3, T) In
2
S RT S R(a, (log (T))²
15 Proof of Proposition 6.1
The proof is by construction. For each time = 1, 2, ... denote by the function f((æ) := _ - H where H, Σ'=1 1 Let the initial point fg and let us set the clipping value of clipped gradient descent to be larger than or equal to 1.
We will argue by induction that 0r H, + 1 for all t 1,2, ... Thus, the loss suffereed at time t is
:- 1 +. since the optimal point all times is 1 H₁-
For the base-case of time 1, we see that the gradient of fi( at = 8g = is -. Thus, 81 = 1 H2 and the loss at time 1 is 0 1 }. Assume the induction hypothesis is true for all 1, ,t for some t. Consider the time f + 1. The induction hypothesis tells that at time t. 0g = H1+1- At time
Hz+1 is 1. The step size at time + is 7/++1 84I and thus o,+1 = Hzt1 + F+T = H4+2- Thus, the induction hypothesis holds.
+ 1, the function revealed is (x 1 H++1)² and thus the gradient at any
This gives that the total cumulative regret is
1 (
R₂ = Σ
t=1
2 T - (n))),
T
3
16 Proofs of Lower Bounds on Estimation Regret
Before giving the proof of Proposition 2.6 we state and prove a simpler result that finite diameter is necessary in the presence of both ntn-stationarities and corruptions.
Proposition 16.1 (Finite diameter is necessary in general). There exists strongly convex loss function C such that for every D > O, domain = DD/2,//22 C. R and every N, such that for every algorithm, there exists sequence of probability measures (IP))T and corruptions (Ce) T where regret at-least () with probability 1.
We prove the following Proposition mean-estimation. which will prove Proposition 16.1
Proposition 16.2 (Mean estimation needs finite diameter). Let θ = [-D/2, D/2] R. time- horizon T and the number of corruptions be AT S T and ((Z, 0).. For every algorithm. there exists a sequence of probability measures (P.) and corruption functions (C.) such that the regret incurred is at-least ()ArD with probability 1.
Proof. The crux this lower-bound is that the time instants of corruptions are adversarially chosen. The proof follows by construction where the underlying ground-truth is one of two possibilities and there is no noise, i.e., the variance of the probability distributions chosen by the adversary are all O. We will show that even against oblivious adversary, ((Ay: regret is un-avoidable.
Assume that the adversary has only two choices either an environment which the true mean at all times is 2/2 or one in which the true mean in the first 7 - Ar samples is D/2 and the true mean in the last AT samples -D/2. If the adversary picks the first scenario then does not corrupt any sample and since there is noise, all the T observed samples in the first scenario will be equal to D/2. If
20

---

the adversary picks the second scenario as the environment, then it will corrupt the last Ay samples to show as 2/2 instead of the true DD/2. Thus, either choice of the adversary the observed set of 7 samples by the forecaster is deterministic D/22 for all 7 samples. Thus, the forecaster cannot distinguish whether the underlying environment from scenario forecaster has knowledge of the two possible situations from which the adversary is choosing.
from observations, even if the
Thus, for any deterministic choice of outputs by the algorithm, the adversary can choose one of these two situations such that the regret on the last Ar samples of the stream incurs regret at-least 2 1
16.1
Proof of Proposition 2.6
Similar to Proposition 2.6 consider two scenarios for mean-estimation. In one scenario, the un- corrupted samples are all drawn from a Dirac mass at O, but the first AT samples are corrupted with all coordinates set to D/v In the other scenario, there are no corruptions and the un-corrupted samples are all from Dirac mass at location with all coordinates D/Vd. both situations, the first Ar samples identical. Thus, no estimator in the first Ar samples can distinguish between these two scenarios and will incur regret at-least (Ar-)/44
17 Useful convexity based inequalities
In this section, we collect some inequalities that we will repeatedly use throughout the proofs. Throughout the rest of the paper. for every t E [7], we denote by (6) == B2-P,|C(( 0)] and by 0r := arg mingee R,(0), (0). Convexity of (-) and the domain θ being convex implies that 6 is well-defined, exists and is unique. Recall that for all time f, (0) is strongly convex with parameters
M, m respectively. Thus, we know that
(0,) 2 (1(0-11)+ + (VR((0(-1.. - 02-1) + m 100 01-1112.
(4)
2
Further since 0 == arg ming (0), we have that
Re(0(-1) (R) 2 2 |10=- 1,
Putting these two together, we see that
(R, 0-1 07) 2 ml ml100-1 -0,
(5)
Also, We further use the following lemma.
Lemma 17.1 (Lemma 3.11 from function. Then for all x, y Rd.
19). Let f Rd - R be a M smooth and m strongly convex
mM
1
(V/(x) - V5
M || v12
M+m VV(()) v
By substituting 8,-1, y 07 and f(.) Re(-) and by leveraging the fact that (R,(0,) = we get the inequality that
mM
(VR((0--1,,0-111--
M |10,-1 - 0,112 M VRe(0r-1113.
Re-arranging, we see that
VV. (M - 07112
(6)
Further, using the Cauchy-schwartz inequality that (VR=(0(-1),0 0 < (9)(()-))11 8;' $ D (B) we get from the preceeding inequality that
(R.( (M m)D.
21

---

18 Theorem statement when the gradients are sub-gaussian with known upper-bound
Theorem 18.1 (Formal version of Theorem 4.3
Suppose Assumption 4.2 holds. For every E (0, 1), where C is
Algorithm is run with clipping value X vTr(= C (V VVmas (23)
(2)) In (2T)
given in Proposition 19.1 and step-size 1j > O, then with probability at-least 5,
2(1 + Dr)
6T 8
2m
RegT S
+T
(V
Uman (2) In
+ MMM)
V m
17m7
T&T (Cv/man (2) In
2T (5)
2\ m
4XD 7
+ Ar
21
(8)
17m22
Corollary 18.2. Suppose Assumption 4.2 holds. For every E (0, 1), if Algorithm is run with clipping value X 2 + / Tr(2) + C
(v Vmmax (2) (1) where C' is given in Proposition 19.1
and step-size n mī for E [0, 1), then with probability at-least - 8,
Th (maa(()) 22 + Tr(E)
Regr < O
47 +
Regret dise distribution shift
0
T1
Pmmar (2)
In
6T
TM
(ArT&V
(9)
Regret due adversarial corruptions
Regrot standard stristical
The above theorem immediately yields the following corollary by substituting the learning rate as 2/3 223/3
Corollary 18.3. Suppose Assumption 4.2 holds. For every 8 E (0, 1), if Algorithm I is run with
clipping value X 2 G + (T()) C (v Ummax (E) In (2T) where C' is given in Proposition 19.1
and step-size T 2/3 then with probability at-least -
75/34T (Cy Uman (E) (2T) Tr(
Regr 50 T2/3
Regret due to distribution skift
O
T2/3
Vimaz
Σ) In
67
+ (T(E
)
+ O (ATT2/3
(10)
Regret adversorial corraptions
Regret due standard statistical
19 Proof of Theorem 18.1
The proof in this section is based on the following result on high-dimensional sub-gaussian random vectors.
22

---

Proposition 19.1 (Exercise 6.3.5 [57]). There exists an absolute constant C > 80, such that for every sub sabb-gassiinn random-vector Z with O mean random-veese vectorr and covariance matrix E and every 5 E (0, 1}, the following
(
IP
Z1122 - E11 2 CV Vmax En In
holds, where Vmnar (E) is the largest eigen-value of the upper-bound covariance matrix E.
19.0.1 Notations
We follow the same proof architecture as that of [55 We define three sequences random variables (1hx)es and (1))21 as follows.
a/ == clip(V (- (R((O--)),
3/ = ( (R,(0=1)),
1/ vC 0 (R,(0-
These are random vectors since Z, ~ P. and both C2 and 0₂ are measurable with respect to the sigma algebra generated by a (Z...... Ze, Ci, 1t- Clearly, for all times / 2 on the event that C = 0, 4/2 = th holds almost-surely. Furthermore, from triangle inequality almost-surely for all time 2 have
1 < 11..1 + 2x² 10.
(11)
O, the covariance matrix of the random vector VL( (O) bounded from above the positive semi-definite sense by Σ. Denote by Trace Σ) and Vmax (E)) as the trace and the highest eigen value respectively of the matrix E. Assumption 4.2 implies the following two lemmas.
Recall from Assumption 2.5 that for every t and
Denote by the event Ena-clip
Eno-clip
(vh = }
(12)
19.0.2 Supporting Lemmas based on sub-gaussian concentrations
The main result of this section is stated at the end in Corollary 19.5 In order to state them, we build series of useful bounds along the way. The following lemma bounds the estimation error the true gradient using the sample Z, at each time L.
Lemma 19.2.
21 C (E) (E) In
sup o. Free
P Pz.... Zx
sup [VL(22, (R.(l [E[T]
+ TM(E)
S.
In words, the above lemma states that for any sequence of .,.... Gr, the probability that the norm of the difference between VL((z,, 0.) and its expectation (R. where Z, IP exceeds CV Vmma (E) In (2f) is bounded above by
Proof. Fix any deterministic o..... Ör O. Assumption 4.2 yields that for all time 4, VL(,,,
(R,(0,) is 0 mean sub-gaussian random vector with covariance matrix upper-bounded in the positive definite sense by E. Observe from Jensen's 's inequality that for all and 0 e
E|J VL(., VR.(0)]I s /E][VV(2,,0) (R.(1)) < Tr(E),
(13)
23

---

Now, Hoeffding's inequality in Proposition 19. gives that
27
[VL(2,, (R.(
S
V Vinar (3) In
EIIVL((Z, 0.) (R)II,,
27
S sC Vinax ) In
Tr()))
holds with probability at-least 4. 7. Now, taking union bound over / = {1, T gives that
27
Pz Pi Zr
sup FE[T]
VL(22, 0.) (R.(0:)1 CV Uman EE)n In (σ + (T))
S 5.
Now, since 01, the proof.
Or θ was arbitrary, can take supremum both sides and that concludes
Corollary 19.3. With probability at-least for all times E (1,-.. T.,
27
1e S C
Vinax Σn) In
Tr(E).
Proof. The proof follows from applying the Lemma 19.2 to the set of random locations ., Or.
Lemma 19.4. Algoorihh is run with clipping value À 2 G VTX /'max (E) In (f
where C given Proposition [9.1] then with probability at-least 1 - gradient is never clipped for any un-corrupted sample, i.e., with probability at-least 1 5, event En--clip holds.
Proof of Lemma 19.4
From the definition, we know that the gradients are never clipped for the un-corrupted samples if [[V[((,-1, Z,)l < holds for all t.
From Corollary
19.3
we know that with probability at-least 1 - ò, for all t E (1, ,T,, we have
27 + Tr(E).
VV[ VR. sc SV Uman (E) In
(14)
From the triangle inequality we know that
0V < [V, 01- VR, ( (R)((
$ (7 (R. + sup (Q)[
AEO
||VC 01) (R-()-
(15)
Substituting the bound from Equation 14 into 15
we get that for every [T].
(v Mmax (2) In
|VL[2, s G Tr(E) + +
(V
2T
X
(16)
8
holds with probability at-least 8.
This immediately yields the following corollary.
Corollary 19.5. If Algorithl I is run with clipping value À 2 G+ G+ /T(E)++ (V (E) In (2
where C' is given in Propositton 19.1 then with probability at-least - 26, for all times t E [T').
| s C
G Umaa (E) In
2T
+ v Tr(E).
24

---

Proof. On the event that both Corollary 19.3 and Lemma 19.4 holds, we have the result. Both those events fail hold with probability at-most 28.
Denote by the event
E の
n 1 l1 s
s P'ma
(m)a(()) (2)
In
2T
VT((E)
(17)
8
Corollary 19.5 states that [ 28.
19.1 Lemmas based expanding the gradient descent recursion
Lemma 19.6. Under event yØ,, for every time E [7],
21
10: - 0z 12 s (1 - (1mm--11p00)0 1 -711 11 - -10 - 0 0.+1112+
2n
mm) (0. 0% vo+1) + Bn
0--11
s=1
+ 2x 2-1
[-1
(1-mm)**1c,rt
1I 4n
$1,- Ic,000
(18)
where B - -CCVmmar Σ) In (TT) + (T()) holds.
19.1.1 Proof of Lemma 19.6
Proof. Consider any time We have
||0e 1/ [ C(e,
0,112
(19)
(a)
|10/11 (
(20)
= |10,-1 I Th + (R.(0, - 07
= ||0,-1 17 + 12 + (R((0=11)1 - (m - 87, v2 + (Re(0:-1)).
|10=1 1 + 20y 1 + 2 (0, 2n 0; 32 + VR, (0; 1));
(21)
Step (a) follows since is convex set, (0.) - 0,1 s 100 - 07,0011,, since 07 e. In step (b), we
use the fact that |a + b113 < 2||a||2 + 216b1 for all a, b Rd. Substituting Equation 6 into (2 we get that
|00 0.113 < 10.1- +
21 - 6%, v5,)
+ 2n² ((M + (VR,(((() (0.00)011)0011111 0,) - mM 110,-1 0111 - 21 -0))
Re-arranging the equation above yields
|10- 0.112 < mm M)] - + 21/ 10022220000- -
2n ((M + m)) (8 0, -8)).
Further substituting Equation into the display above yields that
|0
0, 11 < (1 2nmm + 2ny² 2) [| 0: 2n || v. 217 02, 3.).
< (1 - 10m)mm=000--11 11 + 27) 11 2n 1)),
where the inequality comes from the fact that if 17m < 1 = 2mm - 20²²2² > 1ym. We simplify the display above using the inequality in Equation (45)
25

---

|00 9ol12 < (1 - mmm 8 07-1 + (1 mmm) ) 0:1
+ 21/ 11 + An2>>1c,,00 20, 0j, w/) 2n - 02, 1/2 41)) (22)
Using the Cauchy-Schand Schartt- inequality that (01-1 07, vhe - vht) S ||0,- 0f - w/ll 22110t-1-
or |c where the last inequality comes from the fact that for all time i, 11 1/21 S 2A1ci
almost- sumost-surely. Plugging this into Equation (22 yields
1101 0.112 s (1 1pm) 02 (1 mmm)l 0211
2ny² 1 Axf=>=1c,44
(0- - 07, v2) + 4n 1,11 (23)
Using the fact that the diameter of the set O is De now yields that
110| 0.112 s (1 - mmm)l11111 0 12 + (1 mmm) 0,
+ + + > 21y(0c 0r, the) 4n C,70-
Unrolling the recursion yields,
110--0 12 - (1 (1--mm)(-11 1100 0/
(1 - |mm0 110, 07 -0, (1 - mm) 5 11//- s=1
#=1
4nj² x²
mm) C. c1-++1
2n
(1 mm)) ) (00- 100-5-0- bh AA (1-mm) 101 10 10--411700
s=1
Using the fact that E (1 - -1mm)* -
1 we get that
10: - 0, 122 < (1 (1- (1-))m111111 - -0111-
(1
mm)) - -7 01-5+111
1-1
[-1
+ 21)
17m) am
1
11
- 21 Σ
(1 171) 1-1 10 - 07-011 vi-s+1)
s=1
Term
8=1
Term
1-1
+ 4n x2
Σ (1 1pm)
Ic + 4nAD
Σ
1c (24)
Changing the variables in the summation, the above inequality can be written as
10- - 0 s (1 mm)) - 0 +
mmm) 110 110 - 0.+1113
+ 2n²
2
mmm)
|1b
2n
m/m) - - (0. 0 vh+t1)
2=2
Term
e=1
Term
1-1 Σ ==2
1-1 (1 - mm) 1mm)mmm)1la- "c,
+ 4m
X2
(1
mm)
1 10 + 4qAD
Σ
(25)
2=2
Simplifying term I from Corollary 19.5 since event &y holds by assumption of the Lemma, we get that with probability at-least 20,
|10: - 0.113 < (1 - 1mm)=--1111 1|0
01113
11 mm)² 1 - 0; 1 112
BnBB²
-2m
(1 mm)
(0. 0 vo+1) -2n mm) -m))---1((03 - -0 -0+1, (641)
m
1=1
Term 11
26

---

t-1
r-1 4n
4nj² X2
Σ 17m) cc.#0
Σ
1ym)
1c.00
(26)
8=2
where B = CVV Vmaa D) In 27
Tr)).. Further, simplifying using Cauchy Schwartz inequality,
we get the stated result of Lemma 19.6
100
0.12 (1 10--mm
01112 =0 02+11 l1
10:
B
2n
mm) x (0s 07 Mo+1) +2n
9mm)-0-1a5
m
Temm
t-1
417
A²
(1
m7m) -- 10, 0, + 4nAD
Σ
(1
(27)
2
a=2 2
19.2 Martingale Analysis of Term II
Denote by the constant
S.S s - (0mm)=~1100-00 0ill +
(1 17m) 010 -0+11
2y
mpm)
) 1-s-10.
8=1
#=1
Bn
1-1
1-1
2 2
Σ (1
7mm)
c.20 4nAD
Σ pm1
(28)
m
2=2
The following proposition holds by simple algebraic manipulation.
Proposition 19.7. For every [2, T and
(1 nmm² "U, U..
Denote by the sequence (E. \ of random vectors as
{
0: 0, if 00 0.112 20,
8,
(29)
0 otherwise
Denote by the event
20 E) In
2T
m7)) -m -E, vo+1) S
(30)
19m
Lemma 19.8.
P[gg] 2 8-
(31)
Recall the definition of event E in Equation 117 Corollary 19.5 [9.5g give that P( w 2
25.
Lemma 19.9. Under the events &g and E
|10, - 0:112 < 2U,,
(32)
holds for all e [T].
27

---

19.3 Proof of Theorem 18.1
Proof.
Corollary 19.5 gives that P S 26. Lemma 19.8 gives that [| S 8. An union bound E - 26. Thus, we have that both events & and &g hold with
argument thus gives that PlE probability at-least 36, i.e.
F v 0g 2 36.
Under the event EΦ n & Lemma 19.9 gives that
1|0 0, 20..
Now, applying the fact that V2, ri S E, VTi, can simplify VU, as
VU, s V2 (1 17m) - 110
-0ill2 + Σ - pmm))1102+ - 02-11111
(V Vmaaz (
(a)aa()) In) In
21
Tr(E)
V 2n
8
2T In) + 2n ( (Qumaae (m)
+ Tr(E)
mm) t---1 V1103
0:+1ll
[-1 + 2m
(1 rmm) 1-1
10 + AnAD Σ
1c
(33)
Observe the following deterministic identities that be proven by switching the order of summa- tions.
Σ
[1 (1--m)
2
(34)
7m
221
2AT
mm)
10 10 5
(35)
m7m
T 1-1
2
(1 17m) $10 - 1%
07-041ll5
(36)
17m
1=1 s=1
ΣΣ t=1
T (1 mm)
V110: -0=+1l1
2
10;
0.+1
2 2
(37)
1pm
1jm
The first inequality above follows from the fact that for all æ E (0, 1), we have
2 and the
I-v1-
last inequality follows from Cauchy-Sehward inequality that ΣT VI S
T == T.. Recall that
the regret Reg,- = ΣT |10, 1. Thus we get from Equations 332 and (33 that with probability at-least 33,
2(11 + +T)
2T + Tr(E)
2m
Regy v
+
(V
Vinax En)in In
mmm
5
Tor
(C E)) In (2
VTr(E)
2X m
4XD
+ AT
+
2
(38)
1mm2
holds with probability at-least stated result.
33. By change of variables by re-parametrizing 5 yields the
28

---

19.4 Proofs of Lemma 19.9
Proof. We prove this lemma by induction on For the base case of Equation (32) holds with
probability trivially by definition. Now for the induction hypothesis, assume Equation (32 holds
for all E {1...,, 1 for some 1. Since we are on the event &g. we Equation 27 holds.
Thus,
100 0:12 S (1 -pmmm
01112 + Σ (1 pm))
00= + 0++1
==1
Bn
t-1
21
(1 mm))
(0, 0N vot1) +2m (1 (1) (mm)---11
s=1
t-1
[-1
41y
X²
mmm)==11e 1. + 4n Σ (1 mym) mmm)t==
(39)
2=2
From the induction hypothesis, we have that 110 - 00112 < 2U, holds for all E (1,-.,,,- 1}. Thus,
Σ (1-nm)² vot1)
Σ (1 m)m)r-=(( 0%, ve+1).
Further since we are on the event gg. we have that
20 (E. In
2T
Σ mm)) (o+1)
mp
Thus, plugging this back into Equation
39 we get that
||0: - 0:112 - U. S0nUeVmas (2) In
m
From Equation 28 we see that 2n < Ur. Substituting this in the above equation, we see that
Uty 40 (E)
In
10 0.112 S U, +
B
2U,
The second inequality follows since B C Vmma E) In (2f) + IT(E), where C 2 40 given
/DDmmaa (E) In 22
in Proposition 19.1 Thus,
-.
B
19,5
Proof of Lemma 19.8
We first reproduce useful result.
Suppose Y1," YT a martingale sequence with respect to a filtration (Fr) i.e, [[(Y 0 for all Further, suppose there exists deterministic non-negative numbers (o.)² such that for every X E R and Xaa
Lemma 19.10 (Sub- Sub-gaussian Martingale Azuma-Hoeffding inequality 53
t [T], we have F $ exp
almost-surely. Then for every 0,
3a
P
Y
exp
28 Σイ= o
29

---

In order to prove Lemma 19.8 we will show that for each t E [T]. the event
T
{(()
(m))"=((an vo+1) s 2BU,vin
(40)
8
holds with probability at-least j. Then union bound will conclude the proof of Lemma 19.8
To do so, first observe that the sum E1=(( 7m))*"(Ss, 1ss+)) 1) is martingale difference with respect to the filtration (FrYY-1- This follows from two facts.
Fact &. E F. is measurable with respect to the filtration generated by all the random vectors 71,- ... Z5 and the corruption vectors .I. C.. This follows since the adversary causal and does not have access to future randomness to decide on corruption levels.
Fact II E [F] = 0 is un-biased.
Fact III, The sequence of random variables ((1 - m)m))++ (5.s +0+1)) 1))a satisfies the premise of Lemma 19.10 with o, S (1 - (pm)2(==)) ||E, um (E) 2(1 17m) 8- ULUmaz (E), for all 1 s t.
(
The third fact follows from the definition that conditional on Fss the covariance matrix of ds41 is upper-bounded by Σ and || < 2U, for all s, and (1
, S U2 holds for all 8 S t.
observe that the sum of variances Σ o 2 (Σ) Σ. (1 rpm) 1-8 Pummaa (E) Applying Lemma 19.10 get that
In order to apply Lemma 19.10
200,umar (Σ) In (2F) 17m
P
-mm) ( vo41)
S 8.
19.6
Proof of Corollary 4.5
The finite diameter that D < oo fact only used in Lemma 19.6
From observing the proof of
Lemma 19.6 it holds even 'D = co, albeit the bound is vacuous if Ar > 0. Thus, the entire proof holds verbatim even if D oo and gives non-trivial regret guarantees when Ar
20 Theorem statement and Proofs in the general case from Section
Theorem 20.1 (Formal version of Theorem 5.1 For every ê E (0, 1), if Algorithm is with clipping value
2G, and step-size 1j > O, then with probability at-least - 6,
RegT $
910
+
227m
+2)
2(h TT) nm
40T
1 Am
+ ToT + GΛAT
2T 8
X >x/mi
σ
6//33/4
Ao
In (2l)
Thr Am
XT
4AAT
XD
+ 30
+
4NT1
(41)
2/4/4
nm²
Corollary 20.2. For every 8 E 1), if Algorithm is run with clipping value X = (2GT*), and step-size 1j mla for 10, then with probabilut at-least
RegT 50 (( (GTTtD
T _
o DT
F T1+20-0
G
3/2
m
3/2
G
Regret due distribution shife
(VGTI- + + G2T1+28-0
8
Regret due finite sample estimation
30

---

oVD o AT
T
G211240 +1
08/2g
2
(42)
m
VG
Regret tue to adversarial corruptions
Corollary 20.3. For every E (0, 1), if Algorithm 7 is run with clipping value X 2GT',, and step-size 1j mTa for a [0, 1], then with probability at-least 6,
GOT Pr
oT Be ooT
o T
(7)
T ATGRODD
Regr I
3/2
+
m22//
+
Regret due distribution shift
Regret fintte-smple estimation
Regret adversarial corruptions
(43)
Corollary 20.4. For every d E (0, 1), Algorithm 1 is run with clipping value max(2G,T2/3)
and step-size T-1/2 then with probability at-least 8,
Regr I o (T55/((00)) 0 + (T))
Tr(2)
T
+
In
m
Regret due to distribution shift
Regret due to finite sample estimation error
VD
)
0
AT m
2 + T +7 +T
+7 $
(44)
Regres due to adversarial corruptions
20.1
Proof of Theorem 20.1
We follow a similar proof architecture as that of Theorem 18.1 variables (14))211 and (z))21 follows.
We define two sequences random
4/ (Z, - (R.().))).
and by
J. -
01-)),)
(R.(D.))).
These are random vectors since Z₁ ~ P, and both C₁ and 0g are measurable with respect to the sigma algebra generated by .Z...... Zr Ci.... 1t-1). Clearly. for all times 2 on the event that C = O, V/2 th holds almost-surely Furthermore, from triangle inequality almost-surely for all time 2 1, we have
1 1 2X² 1c
(45)
Expanding the one-step recursion
we consider any time and write the Similar to the analysis carried out in the proof of Theorem [8.] recursion as
00. - 11
07
Now, this can be expanded verbatim done in Section 19.1
yield an identical replica of Equation
24
[-1
1007 - -013 < (1 - 1-mm)--1100
0112
Σ
mym)* 107 - 07---111
31

---

1-1
1-1
2nj²
17m) 8-1 110/-0+1112 2n Σ (1
rmm)= )11)))=110) 10,- - -0--011::4--41
a=1
t-1
(1 - -mm) 1-- 1c, 11 + 47AD + 4np x2
Σ (1 17m))=--11 1
(46)
s=1
Denote by th =- 1/6 + 1/) where v. (6)
= Ex, and v (1) = wr (
Using this in the
display above and using that fact that |a b1 S al
+ 2 2bbl2 we get
10, - -0.12 S (1 -pm) 110 01112 +
mnm) 110 0r 07-511l1 11
[-1
41²
(1 7mm)*=111 1-+1-
(8)
++1
12 + 41²
Σ (1 1--mm)
11 (0)
1-+11
s=1
21
11 1-1mm) 8- (-1m)~=11))
10 1--1000
07 0 (-s++))
21)
17m) 5-1 10c- 01-0t1: ((())a))
[-1
4n x2
1mm) 8- 1c + 4n Σ (1 mm))
1c.
(47)
Further simplifying by adding and subtracting Ez, |1 (1)
|13 to be above display, we get
|10| 0.112 s (1 (mm))=1110 01112
mm) " 07-042l1 11
1-1
41 2 [-1
+ 21
(1 rmm)a 1-1
11
1-1Rz
RR 1 11
1-1
+ 4n
(1 (11,,_ 112
E2. 1
1-1
2m
Σ
(1 - m7m))* 11 10, 07 (0) (10 - 21 Σ
(1 - m7m) (mmm)~1(000
-1000000 -7-.-1111 ((o
==1
t-1
21
1/m))==1 (0)))==10000-0011 (0,- 0z ( - -21
17m) e-1))=11//
1000100000 07-011:
8=1
+ + x2
mmm) 1 10 + 4nAD Σ
(1-mm)) ) 1c.
(48)
Lemma 20.5. X 2 2supace [V]] 2G, the following inequalities hold.
1 || < 2A
(49)
2 || 1|2 < X
(50)
Ez, [1 (1) [2] < 10o2
(51)
Simplifying Equation (48) using bounds in Lemma 20.5 get
[-1
|10: - 0.113 < (1
01112
mm)) - 07-042
32

---

16 2 1-1
1-1
mpm)a=1 + =00)²a²
(1 17m) )
A
8=1
==1
f-1
+ 41
8- ++1
Ez. Ill 2 F -0-0+)
[-1
+ 2m
(1 (1- --mm)) 11m))=-1100--- - lllllllv / + 21j
(b)
(1 171) ( 1100 00-
==1
t-1
2n
(1 ()m))=1(() 10,- 07 (1) 1 - -2
(pm))=1(00--
0:--111
8=1
8=1
+ 4n7 X2
(1 mmm) 1 100 + An Σ mm) 8- 1
(52)
Further applying the bound that
|06( S 1
t-1
|10] 0.112 - (1 7pm)--118, -01112
Σ
m7m)"110,
0--01110 12
s=1
16n 20 1-1
(1 pm)) + 407 02 t-1
(1 1pm)
A
1=
[-1
+ 41)
(1 v/m) - (11v5 s+1 112 - -Ez, +11
8=1
80 17
802n t-1
Σ
(1 mmm 1 1--1116 110 - 07
(1
101)= - 0ل---111
A
8=1
s=1
217
mm) --1 10 0%
(r)
22
(1--m))-10
10, - -7- 1/
L-1
1-1
+ 4n 22 X2
17m)*= 10 + 4m/D
1-mmmm* 1c.
(53)
We further simplify the underscored term above as
-2m
(1 mmm)=1 (07 07-5t1 S 2n
mm)*m -100 - 01.+411l16("11 ||
49
4nd
(1 17m) 3 -100)= 07-0tal1-
Using the inequality above into Equation
53 along with the bound that 4n² Σ (1
mm))-11,,- 1c0 I 4n Ar
where Ar
1c,40, we get
m
110- - -0.13 < (1 1-m) 110, 09113 +
(1
07-411l1
16 Am
40n0²
+ 4nj
mm) (1)) - 112 Ez
m
s=1
Term 1
1 A
(-1
(-1 8a 8 7
m
110)= - -0--ol +
7mm)0~11100_ -
00:00------0 0:-041.
33

---

1-1
2m
7m) 1-1 10,- oi-ar 1/ Vi +41d Σ
mmm) 5- -10, 0/-0+11
Term II
4nj X
mm)) "1 1c. 111 4M
17m) - 1c, 111
(54)
Denote by the event (1)
((1)
4r7²
mpm) (1)
- -Bz. -z Illv 12 F(-s) s
21
32m13/2 No
(20
32n 22 In
+
8
2mm
Lemma 20.6.
P 2 1 - 8.
For every t {1,
,T. denote by the constant
U. (1 (1-mm))--11
01
Σ
110m)
02-01112
8=1
16100
40no² +
2T
321 3/2 No
In (27)
2 11
1-1
+32n 22 In
(1mm))~11100 0--
Am
m
V2m
t-1
1-1
+ 1
(1
mm
s-
10 07
+ 217
mmm)
Cc-o1170
==
s=1
t-1
+ 4nAD 8=1
(1 171)
(55)
Proposition 20.7. For every 1 S <s<lST,
(1 17m) 8- Ur_ S Up.
(56)
For each & (1,...,,1 ,T), denote by the event e!(2) as
21 [-1
e(22)
rym) 8- (0,-
S 4ndaQU QU,
2 (1+
mpm
Observe from definition, (P(E(2)] = 1. In order to bound the other events, the following lemma holds. Lemma 20.8. For each E (2....,11
P (2) ((2)
T
Denote by the event
T
(2))
8
(57)
34

---

Corollary 20.9.
P( 2 1 6,
where event ()) is given in Equation 57 Lemma 20.10. Under events {() and E22, for all times & E (,,.., ,7}
12 S QU.,
where Q =
2068² A3m
+
4A²
+ 2. o²
We prove this lemma by induction. The base of holds trivially by definition.
By the induction hypothesis, assume that for some t 1, 12 < QU, holds for all 8 < t. Then, from Equation (44 we have that
80 2 1
- 11-m)))-1100---- 0. 4ndy QUI (1 41+ 17m7
U
U, +
A
(a)
2 17
2
Up +
mmm)
/ (1 4n QQI
X
17m
==1
U +
80
QQU
(1 m7m) -/2 + 4nd QU: (1+ v 1
2
A
17m
8=1
64
1+ ++v15 1+ 2
$ U,
VQU, + 4mdy VQU,
mn
1pm
64
nQu
U0 +
QU, 16
md
m
Step (a) follows from the induction hypothesis. Step (b) follows since
.2 3pm
Claim If
206o Xmn
122 2, then U, + Gid? md
VQU, + 1
nQUe QUe
m
We prove this claim by contradiction. Assume that Q >
200 Xm
+
412
+2 and that U,+ 64g²
VQU++
md
16A
QQU
QU. Re-arranging, we see that
m
64a²
VQU,
161
(Q 1)Ur.
md
m
6462
@@
+
16A1
> (Q 1)V
md
646²
40no²
VQ
16
(Q 1)V
mx
m
m
The last inequality follows from Equation see that
55
where U, 2 40na² Re-aranging the last inequality,
64g
16A
VQ (Q -1). 1).
40mmy
v /40g
It is easy to verify that the above inequality and the fact that Q simultaneously. This can checked by squaring both sides and solving for the root of the quadratic equation in Q.
20662
+ 41a 2 cannot hold /²
X-mm
35

---

20.2 Proof of Theorem 20.1
We know from Lemma 20.6 and Corollary 20.9
that with probability at-least 1 1826, events E(,) gg(a)
holds. Lemma 20.10 gives that for all E [1,... ,T), 0r 0/ < QU, where Q is given in
Lemma 20. and U. is given in Equation 55
Now applying the inequality that vx + y S v / Vvb
we get that
|00 0:1l -
15a
2x +2)
(1 mm)) 110 110
0ill +
Σ (1 mm)) (1m))110rr. 07-
Ammm
2////4 V Ao v In (27)
AV710
/T tbng1 ln
2T
30 /
(-1 Σ
(1 mm) 7 V 100 0-1
v Am +
mm
8
2m 1/4
==1
1-1
1-1
+ +2vn2 11
)m)
V 110 0i-041ll +27A
(1 mpmm
1 10 C,-41170
==1
#=1
t-1 mpm)
+ 2 XD
Recalling that Reg
1=1 ||0 - 0fll. .. we have by simplifying using the series expansions in get that
Equations
35
36
37
Regr 5
150
+
2A
+2)
2(1 4T)
+ 40T
+
ToT 7 + 6
2T
X Ammii
mm
Am
m
67//3/4
λo v
In (2f)
T&T 1mm2
XT
4AAT
XD ?m?
+ 30
+ +2
+ AAT
2m 1/4
mp
20.3 Proof of Lemma 20.8
Proof: Fix time & E {1,... T). We wish to bound the sum 1 m)m))*
s0 107
0r-s, w .) In order to do so, we define the following sequence of random vectors
Denote by the sequence (5,)TT of random vectors as
0
02 if 10 0a1l 0 SQ., otherwise
E.
(58)
0
where Q is defined Lemma 20.10 10 From the induction hypothesis, on the event have
c(()) we
21(11 - 17m)*= (0; P (1) Σ 21(11 17m)* -- (Er- (1())
1
holding almost-surely. We will now bound the sum Σ(=1 21y(1 - --m)===11 -- (5+ (
using
Freedman's martinglae inequality. We know that,
[2n(1 1pm)* (Gn)) (
iil $ 21
mm) --m)~~1| 1 (1
< 4m QU,
Further, the sum of conditional variances can be bounded as
2n(11 v/
-mm)a--Qu
36

---

1QU
m
Applying Freedman's ' inequality, we see that
21 - 1ym) -mmmm=1110 (0/-s - -0-- 1/- Vi-0+1) & 4nA QuuPP + 32X²nęQ, In (T(T/6),
m
s AnAvQUi
(1+ 11 mpm
1+
2
20.4 Useful Martingale concentration inequality
Lemma 20.11 (Freedman's inequality (59]). Suppose Yı,.. Yr is bounded martingale with respect to a filtration (Fi) with F| = and P[||; I B] = for all t E {1,.... .T).
Denote by Vg = Ex=1 Var(Y (ar(Yn|Fnn1)) be the sum of conditional variances. Then, for every a,
-a
P 3n [1,7] such that Σ 12 a and Vn Su
exp
(59)
2( Ba)
Re-arranging the above inequality, we see that if
27
27
))
2T
z Bh
+
Bl
2u In
(60)
then the RHS of Equation 59h is bounded above by 8 2
20.5 Proof of Lemma
20.6
Proof of Lemma 20.6 Fix a {1, T.. For {1, ,t 1}. denote by the random variable y!()) = (1
- 1pm) (1
(0) 1 Ez,... || (2)
++1 [l)) Observe that the sequence
(Y: ==1 is martingale difference sequence with respect to the filtration (G.) where G3 = Fi-s-
Furthermore, Lemma 20.5 gives that with probability 1, | 4 + 4x2) s 32n)2 X². We can bound the conditional variance as
Var(Y: (g.) & 16n
Fr | mm) 200-2)())))))) 12, 1111 11-++1 111 Ez,,, 11 1
1617 1677*8 88
(1 mmm) 2(s
) (1:5-1)-
Ez. 111 (v) 1 - Ez. tn 11
< 1228)) Σ
(1 178) 2(0
)mm))(2-0)0) 1)) 2(0-1) (2B |1| (0) 1112 1(FF.
M1
2560m 12202
(1 (
2560npA2e
m
Now, putting B = 32n X2 and at-least - 8/2,
2000 m
get from Equation (60) that with probability
2T
27
2
5120n 22o02
2T
Term I I <<32g22211
+V
22 In
In
8
m
37

---

32mp3/2 3/2 Xo
In (25)
2T < 22n12 In
8
v 2mm
20.6 Proof of Lemma 20.5
reproduced from 25
This follows from the analysis of 25 and reproduced here for completeness.
Proof of Equation
49
1
(0)
(2,
(
|clip( (1,,(,,,,01)) 0,2.::00))-000000000/(/000111110
cclip(V[(2,, 0z-1), A)il + (1
Equality (a) follows from the fact that 0--1 Fi-1.
Proof of Equation (50)
Denote by the event & == 1 (IV_(22,0,1)23 and by X (192(22---1-VRR000-11010 have À > 2G, we have the inequality that
Since
& S X a.s.
(61)
Then, we have that
((1)),, = V1(2),0--)(11 VC(ZZ,0,_1) VL((2,0,1155
Now, expanding out d we get
||5 (6) 1|2 = ||E,, U Fr-1]l2.
Ez, /clip( V L(z,, O2 1), - F
V FC(Z,,0r-1)) R((0 Fr-1
Bz.
0L(2),01-1) +
|VV[ 0--1)
(4) Ez.
( [
(IVE(ZZ,,11)) 01-1)1
A
VL(Ze, 0r- Er
Fi-1
2
A
Ez.
VL 0 116 F
|L( 12-1)1l
Ez,
|IVL 81-1) F
Ez, (--
Ez. (.
I / 4.2.::/.............../...//111.
Ez, (.,,
0 170-0000000888810000003111111110
S SovEz, F-
(62)
Now computing the probability
Ez, 1xl PIIV
- 7/1
A
38

---

X2
-
4 1
40²
(63)
X2
The last in-equality is from Chebychev's inequality. Substituting Equation (63 into Equation (62 yields the result.
Proof of Equation 51
F: (0)
Ez,
F- 1
VR,
(64)
Inequality (a) follows from the fact that 0,-1 E F and step (b) follows from the fact that for any random vector Z and filtration F and Y E F, E - E E [il Eill 2 holds
almost-surely. To simplify notation, we denote by & = E1 We now bound Equation 664) to conclude.
[[L] VR,(01-1115
E.
V CL 01-1) (R.() - Ee)
AVL(Z,, 8.-1) VRi(O.-1)
+ +E,
VL(,,, 11-1)11
0² + E, (
AVC 01-1)
12
+ + VR, 1)
|VL 0,
(0) 0 E
5X 402
X²
Inequality (a) follows from the fact that for any two vectors a, b, ||a b13 s 2/|a|13 2/1b11 and the assumption that supace [ 0) (0) o²
20.7 Proof of Corollary 5.4
The finite diameter that D De fact is only used in Equation (46 which holds even if D oc, albeit the bound is vacuous if Ar > 0. Thus, the entire proof holds verbatim even if D oc and gives non non-trivial regret guarantees when Ar 0.
39


Reviews:
[{"review_id": "2oLgGCsc0k", "reviewer": "Reviewer_nCPY", "summary": "This paper studies the online robust estimation problem in possibly non-stationary environments. Under the assumption that the loss function is strongly convex, the authors propose an online clipped stochastic gradient descent algorithm with tunable clipping parameter that is able to achieve both adaptiveness in distribution shift and robustness to heavy-tailed inliers and arbitrary corruptions. Moreover, the algorithm does not require distributional knowledge. Theoretical results and experiments are provided.", "questions": "N/A", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents an online estimation algorithm that for the first time provably robust to heavy-tails, corruptions and distribution shift simultaneously. The soundness of the paper is supported by their theoretical results and experiments.", "weaknesses": "The presentation of this paper lacks some organization and the problem setup part is not clear at the beginning. For example, $X_t$ is said to be the corrupted input, which is the summation of the sample $Z_t$ And the corruption $C_t$, then the authors want to estimate $\\theta_t$, which is not reflected in $X_t = Z_t+C_t$ at all. Moreover, some of the contents in the appendix part (simulations on real data) could be moved to the main body. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough read and providing feedback on the paper. \n\n**Regarding model definition:**  The unknown vector $\\theta^{*}_{t}$ is the minimizer of the expected loss function $\\mathcal{L}$, where the expectation is with respect to the random vector $Z_t$​. Concretely,  $\\theta\\_{t}^{\\*}$ $ =  \\arg\\min\\_{\\theta \\in \\theta}\\mathbb{E}\\_{Z_t}[\\mathcal{L}(Z_t; \\theta)]$. However, the estimaotr cannot directly observe $Z_t$, but can only observe $X_t := Z_t + C_t$. We will make this clarification in the revised version. \n\nFurther, the camera ready allows for one extra page which we will use to bring in the key lemmas (Lemma 19.9 and 20.10) in the analysis and details/plots on the real data experiments. \n"}, {"review_id": "WHTHf3arxA", "reviewer": "Reviewer_ijft", "summary": "The paper studys online estimation problems on data stream exhibits challenging properties, including distribution drift, heavy tails, and outlier/anonmalies corruptions. Formally, at each time step, (given all the data that has arrived) the algorithm needs to output an estimation on certain unknown parameter so as to minimize the cumulative regret.\n\nConsider the task of mean estimation as an illustrative example: At each time step, the algorithm receives a data point drawn from an unknown distribution and must estimate the mean of that distribution. The core challenges here are threefold:\n1. Distribution drifting: The mean of the distribution from which the data point is drawn can change over time.\n2. Heavy tail: The data's distribution might possess unbounded 3rd or higher-order moments.\n3. Outliers: Observed data points could be significantly distorted or corrupted.\n\nInterestingly, the paper reveals that a modified version of the clipped Stochastic Gradient Descent (SGD) can attain sublinear regret, even when all three of the aforementioned challenges are present. A particularly notable insight from the research is the necessity of an intermediate learning rate for optimal performance. While an $O(1)$ rate is ideal for addressing distribution drift and an $O(1/t)$ rate is best suited for noise, managing both simultaneously requires a rate of $O(1/T^\\alpha)$, where $\\alpha$ lies between 0 and 1.\n\nWhile these findings are derived under certain assumptions regarding the parameter domain and loss functions, the authors further fortify their claims by proving several lower bounds. This demonstrates the indispensability of the stated assumptions.\n", "questions": "(The paper under review is outside my area of expertise, and I had not initially opted to review it. Unfortunately, I wasn't presented with alternative submissions for evaluation)\n\nWhile I struggled to grasp the entirety of the analysis due to unfamiliarity with the methodologies used, I found the distinction between drift and corruption intriguing. It's a bit surprising to me that, it is possible for an algorithm to even distinguish between *drift* and *corruption*, and it required very different rate ($O(1)$ vs $O(1/t)$) to handle them optimally. The two definitions appear to me to be essentially analogous. The paper's main result seem to confirm this intuition, but the analysis still treats the two issues separately. A more detailed discussion from the authors on this particular point would be beneficial.\n", "limitations": "N/A", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper effectively articulates the problem setting and its significance. Even with my limited familiarity with the subject, it's evident that the problem is complex and the results presented are notably substantive.\n", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough read and providing feedback on the paper. \n\n**Distinguishing between drift and corruption:** Indeed,  the reviewer’s intuition is spot on. Our lower bound in Proposition 2.6 and in the sketch in the attached pdf is based on the fact that drift and corruption in a precise sense are indistinguishable. Further, the analysis of our algorithm does not impose/prove that our algorithm can distinguish between drift and corruption. Rather the analysis only shows that *for any data-stream* with total distribution shift $\\Phi_T$ and corruptions $\\Lambda_T$, the regret of clipped-SGD when appropriately tuned, is bounded by an explicit formula of $\\Phi_T$ and $\\Lambda_T$ as given in Theorem 5.1. \n\nWe hope this clarifies the intuition the reviewer is seeking. "}, {"review_id": "vyFDi2s23M", "reviewer": "Reviewer_stYK", "summary": "The paper studies the problem of online estimation in a setup that generalizes the stochastic i.i.d. input assumption. The authors consider a setting where the input distribution is allowed to change over time (a certain number of times), and furthermore the input is allowed to be adversarially corrupted (a certain number of times). The authors analyze the standard clipped SGD algorithm to tackle both of these issues simultaneously (Being a simple and implementable algorithm, clipped SGD has many favorable properties in practice). In essence, the paper establishes that the clipped SGD algorithm is \"Lipschitz\" with respect to distribution drift and contaminations.\n", "questions": "See above", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper studies an important problem setting in online convex optimization that gracefully generalizes the standard stochastic i.i.d. input assumption. \n", "weaknesses": "1. At a high level, my reservations with the paper are that the paper proposes a goal in terms of drift and corruption tolerance (on page 4) that seems a bit arbitrary. I was unable to see if even one of these in isolation is understood and what the correct rates are in those settings. In particular, in all of the explicit examples that I could find in the paper, all the lower bounds in terms of $\\Delta_T$ (or $\\Phi_t$) did not have any multiplicative term with $T$; see, for example, Proposition 2.6 and Section 11.\n\n1. (How the distribution shift is measured) The paper defines the quantity $\\Phi_t$ to be the number of drifts in the input sequence. However, all of the results in the paper have regret scaling with $\\Phi_T$ times a polynomial in $T$. Is this necessary for algorithms that achieve vanishing regret? What are the best upper bounds and lower bounds for the regret in terms of $\\Phi_T$ (without any outliers)? (See the first point for more context)\n\n2. (How the clean error is measured) For outliers, the paper defines the quantity $\\Delta_t$ to count the number of outliers in the input sequence. However, the results then depend on $\\Delta_T$ multiplied by the diameter of the set and a polynomial in $T$. I am not sure if multiplicative dependence on $T$ is necessary for stochastic inputs  (See the points above for more context). Are there lower bounds?\n\n3. (What counts as dimension free? and Comparison with existing work) The paper lists their results as achieving dimension-independent errors, but they have suboptimal dependence on these quantities in the regret bounds. For example, heavy-tailed mean estimation (where the claimed results are somewhat immediate since they multiplicatively depend on the trace of the covariance matrix). The paper [18] is said to have dimension-dependent errors but I was unable to find the entry corresponding to [18] in Table 1 in the paper [18]. Their result on isotropic covariance matrices naturally uses $d$ samples.\n\n\n\n*All references are based on the version uploaded to the supplementary material.*\n\n---\n## Recommendation\n\nThis is perhaps because I am not from this subfield but I am unable to appreciate the technical results of the paper (more comments below). Thus, I recommend weak reject, and I would be happy to change my score if the authors/other reviews convince me otherwise.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for making a thorough read and providing feedback on the paper. Part of the reviewer's questions are also addressed in the table in the attached pdf. Below here, we respond in text with the reviewer’s questions highlighted in ***bolded italics*** with our response below. \n\n***“At a high level, my reservations with the paper are that the paper proposes a goal in terms of drift and corruption tolerance (on page 4) that seems a bit arbitrary. I was unable to see if even one of these in isolation is understood and what the correct rates are in those settings.“***\n\nIndeed, settings where only either there are distribution shifts or only corruptions is not yet completely understood  as we mention in the conclusion section. We have included a pdf in this rebuttal showing the best known bounds for the various scenarios and what new results our paper contributes. Summarizing from the attached pdf, our paper is the first to give lower and upper bounds in the case when there are corruptions, both in the presence and absence of distribution shift. In the absence of corruptions, prior works have characterized upper and lower bounds only in the absence of distribution shift. In the presence of distribution shifts ours is the first high probability upper bound.  Previous works only gave regret upper bounds *only holding in expectation* for the setting with distribution drift but absence of corruptions. See the table in the attached pdf for specific details.\n\nProving high-probability results for heavy-tailed data is technically non-trivial. Just providing a high-probability bound heavy-tailed settings *without distribution shifts and corruptions* is itself new and an actively emerging field of literature (see [24, 34, 43, 52, 57, 60]). Our work contributes and extends this line of work by providing the first analysis in the presence of distribution shifts and corruptions, that is based on different martingale concentration arguments combined with induction arguments, which we believe are interesting in their own right.\n\nPractically, the setting with drifts and corruptions are important in applications where several heuristics are proposed (see the Introduction on page 1). Our work is the first to put such estimation tasks on a formal footing to identify upper and lower bounds in the different regimes of presence and absence of drifts and corruptions.\n\n***“In all of the explicit examples that I could find in the paper, all the lower bounds in terms of $\\Phi_T$ (or $\\Lambda_T$ ) did not have any multiplicative term with ; see, for example, Proposition 2.6 and Section 11.”***\n\n*Lower bounds for drift:* As we mention in the attached pdf, Besbes et.al.‘s Non-stationary Stochastic Optimization, Operations Research, 2015 and [47], show that $(\\Phi_T)^{1/3}T^{2/3}$, is a lower bound for the expected regret in the absence of corruptions. Further, Besbes et.al., show that  this bound can be achieved *in expectation*. However, since we are seeking regret bounds holding in high-probability, our upper bounds have a gap from the lower bound. Concretely, we can only establish upper bounds of the form $T^{l}\\Phi_T$​ for some l<1 (Thm 5.1). In the conclusions section of our paper, we list as an open question (second bullet point) of whether there exists an algorithm that can obtain high-probability regret bound of the form $T^{l}\\Phi_T^{1-l}$ for some $l\\in(0,1)$, which will then close the gap to the lower bound of Besbes et.al.\n\n*Lower bounds for corruption:* Our work is the first to give non-trivial upper and lower bounds on the regret in the presence of corruptions on the online stream (see also attached pdf).  The contribution in our lower bound in Proposition 2.6 and the attached pdf shows that one cannot aim for standard statistical aspirations of infinite diameter, i.e., $\\mathcal{D}<\\infty$ is needed. However, as the reviewer correctly identifies, our lower bound does not have any dependence on the time-horizon and thus we conjecture it to be loose. This is an artifact of our proof technique where we only consider settings with 0 variance. We believe that more sophisticated arguments with non-zero variance settings, can recover a polynomial in T term in the lower bound. Improving either the lower bound or the high probability upper bound in the case of corruptions is a challenging future work.\n\n\n***“What counts as dimension-free?”*** \nWe follow standard terminology that states that a bound is dimension free if it depends on the trace of the co-variance matrix and not on dimension times the maximum eigen-value of the covariance matrix, (c.f. [35, 36] of our attached draft). To be concrete, for mean-estimation of a $d$ dimensional vector, a regret bound that depends on $\\text{Trace}(\\Sigma)$ is deemed to be “dimension-free”  (c.f. [35, 36] ). On the other hand, a  bound that depends on $d\\nu_{max}​(\\Sigma)$ where $\\nu_{max}(\\Sigma)$ is the highest eigen-value of the co-variance matrix is NOT dimension free. A bound on the trace is more favorable in high-dimensional settings (cf [35,36]) since by definition we always have $d\\nu_{max}​(\\Sigma) \\geq \\text{Trace}(\\Sigma)$. We will add this definition and discussion in the revision stating that our bounds only depend on $\\text{Trace}(\\Sigma)$ and not on $d\\nu_{max}​(\\Sigma)$  thereby making our results dimension-free. We clarify the dimension-free definition in the revision\n\n***Entry corresponding to [18] in Table 1:*** Please look at the third row from the top.\n"}, {"review_id": "I7tiCndn9e", "reviewer": "Reviewer_6VQW", "summary": "This works studies robust sequential estimation under a non-stationary environment. A loss function is fixed in advance. The data generating process is non-stationary over time, and hence the optimal parameter \\theta^*_t, which minimizes the expected loss over the distribution at time t, is changing over time. A policy returns in each round an estimated parameter \\theta_t. The goal is to minimize the regret, defined as sum of differences between \\theta^*_t and \\theta. The central question is, is there a policy that is free of distributional knowledge (i.e., moments of the data-generating distributions or stream complexity). They answered this question by presenting a gradient-based algo with sublinear regret. These upper bounds match the known lower bounds in the no-noise and no-drift setting.", "questions": "It seems that this problem can be reduced to the problem studied in “non-stationary stochastic optimization” (Oper. Res. ‘14) by Besbes et al. Does this work already imply sublinear regret for some special case of this work? I understand in this submission the corruption is assumed to be adversarial, but this does not seem to be an essential consideration.", "limitations": "n/a", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Presented sublinear regret bounds which matches known lower bounds for the no-drift or no-corruption setting.", "weaknesses": "1. I am not able to find significant novelty in either the problem formulation or the results. Maybe there is a good practical reason to consider this particular formulation but at least in this submission, the authors did not sell it well.\n\n2. Writing: In general this paper is not written well.\n-\tThere are plenty of typos and gramatic mistakes, even in the abstract and formulation section. E.g. “A observation … “ in the abstract. Line 133 “formalize”. E.g. “upto” -> up to. Line 99, “to derive high-probability under any rate..” \n-\tConsistency: do not use a concept before defining it. E.g. in the abstract, “neither the O(1/t)....” What is \"t\"? It seems lower case t is not the same as \"T\" \n-\tVague language. Just to name a few, in the Abstract: “A observation … can be used” – I don’t understand this line. In the def of regret, what norm are we using? Line 96, “the data stream is subgaussian”, do you mean the distribution in each round is subgaussian, or the the entire stream?  \n-\tDo not start a sentence with a mathematical notation; see e.g. “X_t is shown as …”\n-\tThe tone switches between being very informal to very formal abruptly (and why use the word “diserderata” so frequently?)\n\n**The above issues combined suggest that the submission has been written in a rush.** I suggest the authors carefully polish the paper.\n\n3. Lacking of discussion to previous work. It seems that this problem can be reduced to the problem studied in “non-stationary stochastic optimization” (Oper. Res. ‘14) by Besbes et al. Both papers proposed gradient-based algo and used the total-variance distance (“\\Phi_T”) to measure the non-stationarity.  I am wondering what results do previous results in OCO imply, and how the results", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Fundamental improvements in the problem setting and results compared to Besbes et.al. :**\n\nWe thank the reviewer for pointing out missing a reference and comparison to Besbes et.al. which we will add in the revision. Here, we highlight two conceptual contributions we make in the paper compared to Besbes et.al. \n\n**1. In expectation bounds given by Besbes et.al versus high-probability bounds in our paper.** Even in the absence of corruptions, we give high-probability regret bounds while the work of Besbes et. al only give regret bound in expectation. This jump from in expectation to high-probability bound is both technically challenging and algorithmically insightful. The insight we make is that for having high-probability bounds, we need to have \"clipped SGD\". On the other hand, since Besebes et.al. only give bounds holding in expectation, they can get away without having to do clipping. The necessity of clipping in heavy-tailed settings is not an artifact of analysis, but is crucial for good empirical performance, as noted in recent works of [24]. Thus a conceptual contribution we make is that even in the absence of corruptions, a different algorithm compared to Besbes et.al., namely that of clipping gradients is required to get regret bounds holding in high-probability. From a technical perspective, the proofs for high-probability bounds need different techniques as compared to Besbes et.al. For instance, we need several martingale and induction arguments to arrive at high-probability bounds in heavy tails while Besbes et.al. have a much more simpler proofs just based on convexity, since they only give bounds in expectation. \n\n**2. Impact of corruptions which we study, is not secondary and is a fundamental algorithmic challenge!** There is a huge line of work in statistics and algorithms that deals with design of algorithms in the presence of adversarial corruptions. (For example the book of Algorithmic Robust Statistics by Ilias Diakonikolas and Daniel M. Kane and the survey of [35] cited in our manuscript). Given this huge literature and sub-field of learning in the presence of corruptions, our result shows rather surprisingly that  a simple algorithm such as clipped SGD can yield algorithms that are simultaneously robust to corruptions and drifts in the online setting. In light of this, we respectfully push back on the claim of the reviewer that corruptions is only a secondary aspect of the problem. \n\nIn light of this, we respectfully dis-agree that *our work is a direct corollary of the work of Besbes et.al.*\n\n**Reiterating the novelty in our work from the paper here in the response:**\n\n**Novelty in the problem setting :** As mentioned in the introduction on Page 1 of our manuscript, online estimation on data streams with high-dimensions, heavy tails and corruptions is a fundamental and important sub-routine in several applications. The conceptual improvement in our problem setting compared to prior work on online estimation is to go beyond the un-corrupted data assumption and consider the impacts of corruptions. The impact of corruptions is both critical to applications (as we show in Page 1), and is also technically challenging (cf. the book of Algorithmic Robust Statistics by Diakonikolas and Kane). However, the impact of corruptions on estimation has mostly been studied in the offline setting. Our setup is the *first* to jointly consider the effects of corruptions and distribution shift simultaneously for online estimation.\n\n**Novelty in the results :** Ours is the first algorithm that is provably robust to outliers and can adapt to distribution shifts in high-dimensional heavy tailed data streams. No other algorithm or analysis can achieve all of these simultaneously. Furthermore, we make conceptual contributions in the paper. For instance, we show in Proposition 2.6 that finite diameter is a necessary criteria to have meaningful performance in the presence of non-stationarities and corruptions. Our work also provides insight that the learning rate should straddle the $O(1)$ known to be optimal in the absence of noise to be adaptive to distribution shift and the $O(1/t)$ known to be optimal in the stationary setting when there is noise. \n\n**Novelty in the analysis :** Providing high-probability finite sample bounds for stationary data streams in the absence of corruptions and drifts are challenging and are only recently being understood (see [24, 34, 43, 52, 57, 60]). All of these papers only present an analysis *in the stationary setting without corruptions*. Our work contributes to this line of work by providing the first analysis in the presence of distribution shifts and outliers that is based on different martingale concentration arguments combined with induction arguments. \n\n**Improvements to the writing:**\n\n We thank the reviewer for a careful review and identifying issues in presentation. We propose to make these changes in the revision.\n"}, {"review_id": "LjEWfkO6J8", "reviewer": "Reviewer_MGHA", "summary": "This paper considers an online estimation setting where the learner observes a sequence of samples, which are drawn from a (previously determined but unknown) sequence of probability distributions, and with some fraction of samples arbitrarily corrupted. In each round, the learner makes a decision, and regret is measured based on how far this decision is from that which would minimize their expected loss if no corruption occurred. The loss function is strongly convex, and the goal is to obtain total regret bounds which are sublinear in the time horizon $T$ (but may scale with some standard parameters like diameter of the decision space, (unknown) amount of distribution shift, (unknown) amount of corruptions, (known) gradient norm upper bound, (unknown) gradient covariance upper bound). The authors show that a tuned version of clipped SGD achieves the desired regret bounds, with some partial lower bounds. The proofs use combine a novel inductive argument with martingale concentration techniques to provide high probability regret bounds under arbitrary distribution shift, and the results are verified with some simple experiments pertaining to mean estimation and linear regression.", "questions": "In addition to the questions raised in the \"weaknesses\" section, I was curious if this approach could be adapted to incorporate differential privacy (since gradient clipping + noise is a common approach to private learning).", "limitations": "Assumptions are made clear, and I don't anticipate any negative impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- To the best of my knowledge, and as claimed by the authors, no work has addressed this issue of online, (outlier/heavy-tail) robust, and non-stationary convex optimization, and this setting seems important for many applications.\n- There are several settings where their regret bounds are tight, and many improvements over the state-of-the-art\n- The proposed algorithm is quite simple, and they empirically validate the choice of tuning suggested by their theory\n- The paper is generally well-written, with thorough explanations of the problem setup, prior work, and the different components of their regret bounds (though I struggled a bit with understanding the analysis of their general regret bound)", "weaknesses": "- It would seem more natural to measure regret via the excess risk\n$\\sum_{t=1}^T \\mathbb{E}\\_{Z \\sim P_t}[\\mathcal{L}(Z,\\theta_t)] - \\inf_{\\theta \\in \\Theta}\\mathbb{E}_{Z \\sim P_t}[\\mathcal{L}(Z,\\theta)].$\nDo your results transfer to this metric? If not, why? Cor. 4.6-style results for the stationary setting without corruptions are usually stated with respect to this benchmark, as far as I am aware.\n- In the stationary setting with corruptions, it is not clear to me that the diameter-dependence is necessary (and this is considered quite undesirable in the robust mean estimation literature). The authors' lower bound in Section 16 looks to require non-stationarity. Can a lower bound be provided without this requirement?\n- There is a claim of dimension independence (modulo the diameter dependence), but I view dependence on the trace of $\\Sigma$ as implicitly depending on the dimension in many cases of interest, so this seems a bit misleading\n- It is rather unclear to me whether these results are fundamentally interesting, or whether the solution is somewhat standard and only new because this combination of problem settings hasn't been explicitly studied before. In particular, clipped SGD is a standard solution in this space, though their tuning analysis appears novel.\n\t- If the analysis for the general case is of fundamental interest, I suggest that more space is spent in the appendix (or added page of a final version) describing the induction details - I found the appendix a bit hard to follow and did not verify correctness\n\nMinor Nits:\n- On line 48, the superscript for the footnote looks like a power. Right after that, the way the loss function is introduced read to me as if it was already used.\n- In the abstract and elsewhere, \"high-probability\" is used as an adjective without an accompanying noun (presumable \"regret bounds\").\n- Footnote 4 appears before its reference in Table 1\n- \"an\" -> \"a\" on line 202\n- \"at-least\" -> \"at least\" in Theorem 4.3\n- Notation \"m\" for strong convexity constant conflicts with power of $T$ in Eq. 1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Excess risk regret is a direct corollary of our result:**\nAs the loss function $\\mathcal{L}$ is M smooth (Assumption 1 in our draft), we have that $\\mathbb{E}[\\mathcal{L}(Z,\\theta_t​)−\\mathcal{L}(Z,\\theta^*_t​)]\\leq M \\|| \\theta_t​− \\theta_t^* \\||^2$. Thus, a regret bound on the norm  $\\||\\theta_t​− \\theta_t^* \\||^2$ translates to a regret bound as measured through the excess risk. We thank the reviewer for this pointer and will add this fact as a corollary.\n\n**Finite diameter assumption is necessary in the presence of corruptions, even if there is no distribution shift**\n\n***Proof Sketch*** Similar to Prop 2.6, consider two scenarios for mean-estimation. In one scenario,  the un-corrupted samples are all drawn from a Dirac mass at $0$, but the first $\\Lambda_T$ samples are corrupted with all $d$ coordinates set to $\\mathcal{D}/\\sqrt{d}$. In the other scenario, there are no corruptions and the un-corrupted samples are all from Dirac mass at location with all coordinates  $\\mathcal{D}/\\sqrt{d}$. In both situations, the first $\\Lambda_T$ samples are identical. Thus, no estimator for the first $\\Lambda_T$ samples can distinguish between these two scenarios and will incur regret at-least $\\Omega(\\Lambda_T\\mathcal{D})$. \n\nWe will add a proposition in the revision showing the necessity of finite diameter in the presence of corruptions, even if there is no distribution shift. This does not contradict  [18] since in their model, corruptions occur at random instants while corruptions occur at arbitrary instants in ours.\n\n*In summary,*  (i) finite diameter is necessary in the presence of corruptions, whether or not there is distribution shift, and (ii) an infinite diameter can be handled in the absence of corruptions even if there is distribution shift. See also the attached pdf.\n\n**Regret depending on $\\text{Trace}(\\Sigma)$ trace of the covariance matrix is a classical ``definition” of dimension free regret in statistics literature:**\nWe follow standard terminology that states that a bound is dimension free if it depends on the trace of the co-variance matrix and not on dimension times the maximum eigen-value of the covariance matrix, (c.f. [35, 36] of our attached draft). To be concrete, for mean-estimation of a $d$ dimensional vector, a regret bound that depends on $\\text{Trace}(\\Sigma)$ is deemed to be “dimension-free”  (c.f. [35, 36] ). On the other hand, a  bound that depends on $d\\nu_{max}​(\\Sigma)$ where $\\nu_{max}(\\Sigma)$ is the highest eigen-value of the co-variance matrix is NOT dimension free. A bound on the trace is more favorable in high-dimensional settings (cf [35,36]) since by definition we always have $d\\nu_{max}​(\\Sigma) \\geq \\text{Trace}(\\Sigma)$. We will add this definition and discussion in the revision stating that our bounds only depend on $\\text{Trace}(\\Sigma)$ and not on $d\\nu_{max}​(\\Sigma)$  thereby making our results dimension-free.\n\n**Our setting and insights are conceptually new and interesting! Our work is the first to extend online robust estimation beyond iid/stationary assumption:** We strongly believe our setting and results are interesting (and new)! To the best of our knowledge this is the first work to understand how to estimate in a streaming setting when there are heavy-tails, distribution shifts, high-dimensional observations and adversarial corruptions. As we mention in our introduction, there is a plethora of work in the applied literature where  heuristics are proposed for dealing with streaming settings with all these characteristics. Our work is the first to formalize the question, set benchmarks and desiderata and present an analysis of an achievable algorithm and lower bounds.\n\nFrom a technical perspective, there are new insights this work provides. For example, we show in Proposition 2.6 (and in this response) that finite diameter is now a necessary in the presence corruptions. \nThe proofs  are non-trivial and are *NOT* a corollary of existing results. Analyzing gradient based methods for heavy-tailed *stationary settings without corruptions* is itself an actively emerging field of literature (see [24, 34, 43, 52, 57, 60]). Our work extends this line of work by providing the first analysis in the presence of distribution shifts and corruptions, that is based on different martingale concentration arguments combined with novel induction arguments. \n\nThus, we respectfully disagree on the claim that “*the work is not interesting since it only combines problem settings not studied before*”. A key surprising result is that a simple/practical algorithm such as clipped SGD with the right tuning is able to be robust to drifts, corruptions, heavy tails and lead to dimension free results. Our work provides insight that the learning rate should straddle the $O(1)$ known to be optimal in the absence of noise to be adaptive to distribution shift and the $O(1/t)$ known to be optimal in the stationary setting when there is no drifts. Thus, we also respectfully disagree with the claim that “*clipped SGD is a standard/known solution for these problems*”.\n\n***That said however***, this is a first work in this space and our paper leaves several fundamental open questions as we list in the conclusions which are exciting avenues of future work.  We will also take up the reviewers suggestion and add more discussion (for example highlight Lemma 19.9 and 20.10) in the additional page that will be available for the camera ready. \n\n**Writing errors and corrections:**\nWe thank the reviewer for a thorough and careful read! We will make these corrections and other writing fixes in the revision.\n\n**Connections with privacy:** Unfortunately, we don't have anything interesting to say. Aggarwal et.al. consider privacy implications in the stationary non-stochastic setting. Studying the price of privacy in a non-stationary setup with drifts , heavy-tails and corruptions is exciting future work.\n\n*Aggarwal et.al. The Price of Differential Privacy for Online Learning, ICML 2017*\n"}]

Author rebuttal:
Here, we address a common questions asked by multiple reviewers - 

***"What is the best known upper and lower bounds for the various settings of online estimation in the presence and absence of distribution shifts and corruptions?"***

We answer this in the table attached in the pdf, which we will add to the revised version. 

To summarize the pdf, our work gives the first results for both upper and lower bounds in the presence of corruptions, whether or not there is distribution shifts. In the absence of corruptions, a lower bound was given in prior work of Besbes et.al. to handle distribution shifts, while ours is the first *high-probability* regret bound for heavy-tailed data under distribution shifts. Proving high-probability results for heavy-tailed data is technically non-trivial with emerging literature establishing bounds in the *stationary setting without drifts and corruptions*. (see [24, 34, 43, 52, 57, 60]). Our work contributes and extends this line of work by providing the first analysis in the presence of distribution shifts and corruptions, that is based on different martingale concentration arguments combined with induction arguments, which we believe are interesting in their own right.

Meta-review: The authors give the first online estimation algorithm (for strongly convex losses) that is provably robust to heavy-tails, corruptions and distribution shift simultaneously, using clipped SGD with intermediate power-decay learning rate. The technical arguments are interesting. Though scores were split, a majority of reviewers were enthusiastic in recommending acceptance. The main issues raised were the problem formulation and novelty over previous work (stYK, 6VQW) and paper presentation (6VQW). From discussions, other reviewers agree that the problem goal is significant (e.g., obtaining high-probability bounds is technically challenging). I recommend acceptance, and remind the authors to incorporate the suggestions on presentation in the revision.
Decision: Accept (poster)