Stochastic optimization under time drift: iterate averaging, step-decay schedules, and high probability guarantees
Authors: Joshua Cutler
Dmitriy Drusvyatskiy
Zaid Harchaoui
Venue: NeurIPS 2021 Poster (2021)
Keywords: stochastic gradient
online tracking
concept drift
high-probability bounds

Abstract: We consider the problem of minimizing a convex function that is evolving in time according to unknown and possibly stochastic dynamics. Such problems abound in the machine learning and signal processing literature, under the names of concept drift and stochastic tracking. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. Notably, we show that the tracking efficiency of the proximal stochastic gradient method depends only logarithmically on the initialization quality when equipped with a step-decay schedule.

Stochastic optimization under time drift: iterate averaging, step decay, and high-probability guarantees
Joshua Cutler University of Washington jocutler@uv.edi
Dmitriy Drusvyatskly University of Washington ddrusv@uw.co .du
Zaid Harchaoui University of Washington zaid@uw.. edu
Abstract
We consider the problem of minimizing a convex function that is evolving in time according unknown and possibly stochastic dynamics. Such problems abound in the machine learning and signal processing literature, under the names of concept drift and stochastic tracking. We provide novel con-asymptotic convergence guar- antees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. Notably, show that the tracking efficiency of the proximal stochastic gradient method depends only logarithmically on the initialization quality when equipped with step-decay schedule.
Introduction
Stochastic optimization underpins much of machine learning theory and practice. Significant progress has been made over the last two decades the finite-timn analysis of stochastic approximation algorithms; see, e.g., [ 2
24 29 30 The predominant assumption in this line of work that the distribution generating the data fixed throughout the run of the process. There is no shortage of problems, however, where this assumption is grossly violated for reasons beyond the learner's control. Indeed, data often shifts and evolves over time for reasons that may be independent of the learning process.
Two examples are worth highlighting. The first is classical problem in signal processing related stochastic tracking [19 (7), wherein the learning algorithm aims to track over time a moving target driven by an unknown stochastic process. The second example is the concept drift phenomenon in online learning [4 28 wherein the true hypothesis may be changing over time, as in topic modeling or spam classification. An important goal in online problems, and the one we adopt here, is to track as closely possible an unknown sequence of minimizers or minimal values. The tracking error efficiency of stochastic algorithms in online settings is much less developed than sample complexity guarantees for static problems.
We present finite-time efficiency estimates in expectation and with high probability for the tracking error of the proximal stochastic gradient method under time drift. Our results concisely explain the interplay between the learning rate, the noise variance in the gradient oracle, and the strength of the time drift. The high-probability results merely assume that the gradient noise and time drift have light tails. Moreover, none of the results require the objectives to have bounded domains. While conventional wisdom and previous work recommend the use of constant step sizes under time drift, we show in an important regime that a significantly better step size schedule is one that is geometrically decaying to "critical step size".
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1
Related work
Our current work fits within the broader literature on stochastic tracking, online optimization with controlled increments, and high-probability guarantees in stochastic optimization. We now survey the most relevant literature in these areas.
Stochastic tracking. Stochastic gradient-type algorithms for stochastic tracking and filtering have been the subject of extensive research in the past century. Most works have focused on the so-called least mean-squares (LMS) algorithm and its variants, which can be viewed stochastic gradient method on a least-squares loss-based objective. Other stochastic algorithms that have been studied in these settings with a larger cost per iteration include recursive least-squares and the Kalman filter [12]. Recent works have revisited these methods from more modern viewpoint [5] 23, 32
In particular, the paper (33 focuses on (accelerated) gradient methods for deterministic tracking problems, while [32] analyzes stochastic gradient method for online problems that is adaptive to unknown parameters. The paper [5] analyzes the dynamic regret of stochastic algorithms for time-varying problems, focusing both on lower and upper complexity bounds. Though the proof techniques in our paper share many aspects with those available in the literature, the results we obtain distinct.
Online optimization with controlled increments. Online learning under concept drift was first considered by [22] and further developed in several papers B In this literature, the data distribution is typically fixed over time and the rate of variation is stated in terms of the probability of disagreement of consecutive target functions, which is assumed to be upper bounded. Another line of work assumes time partitioning with an expert in each time interval, and the goal is to compete with the expert in each segment. Closer this work is [14 [6], where in the framework of online convex optimization the bounds are stated in terms of maximum regret over any contiguous time interval; see also [5] 26). In contrast these works, in our framework we state our bounds in the same spirit as in classical stochastic approximation. that is, in terms of distance to optimum and objective function gap, and we present results holding both in expectation and with high probability.
High-probabbility guarantees in stochastic optimization. A large part of our work revolves around sigh-probubility guarantees stochastic optimization. Classical references on the subject in static
settings and for minimizing regret in online optimization include [ 15 20 25 There exists variety of techniques for establishing high-probability guarantees based on Freedman's 's inequality and doubling tricks; see, e.g., 15). A more recent line of work [13] establishes a generalized Freedman inequality that is custom-tailored for analyzing stochastic gradient-type methods and results in best known high-probability guarantees. Our arguments closely follow the paradigm of [13] based on the generalized Freedman inequality.
1.2 Outline
The outline of the paper is as follows. Section formalizes the problem setting of time-dependent stochastic optimization and records the relevant assumptions. Sections [3] and present the main results of the paper. Specifically, Section focuses on efficiency estimates for tracking the minimizer, while Section[4 focuses on efficiency estimates for tracking the minimal value. Proofs of the main results appear Section 5 of the Supplement, and illustrative numerical results appear in Section 6 of the Supplement.
2 Framework and assumptions
2.1 Stochastic optimization under time drift
We consider the sequence of stochastic optimization problems
(1) indexed by time E N. We make the standard standing assumption that (i) each function ft: Rd - is jlsttrongly convex and Cm-smooth with I.-Lipschitz continuous gradient for some common parameters μ, L O, and (ii) each regularizer _d R {oo} is proper, closed and convex. The
min (x()) fz( + r2(2)

---

minimizer and minimal value of will be denoted by zi and 42 respectively. Throughout, denotes the 22-norm on Id induced by the dot product (.-)).
As motivation, we describe two classical examples of IT) that are worth keeping in mind and that guide our framework: stochastic tracking of a drifting target and online learning under a distributional drift.
Example 2.1 (Stochastic tracking drifting target). The problem of stochastic tracking, related to the filtering problem in signal processing, is to track a moving target z; from observations
be ca (x]) + Ec. where (-) is known measurement map and e, is mean-zero noise vector. A typical time-dependent problem formulation takes the form
min E le(b, - cx()) + rx(),,
where (-))) derives from the distribution of e, and (-) encodes available side information about the target ot. Common choices for 7t are the 1-norm and the squared 2-norm. The motion of the target 2i is typically driven by a random walk or a diffusion 12 27
Example 2.2 (Online learning under distributional drift). The problem of online learning under distributional drift is to learn while the data distribution may change over time. More formally, one problem formulation takes the form
min
E Nn ((.,)
fax, w) + r(x).
where D(u)) is a data distribution that depends on an unknown parameter sequence {w)). which itself may evolve stochastically. The evolution of ut is often assumed be piecewise constant in in online learning [4] 28)
Algorithm 1 Online Proximal Stochastic Gradient
PzG( {nd
Input: initial To and step size sequence {n T C. (0, oc)
Step & O.....
Set 9. = fe(x)) Set 1t+1 prox per, (I0 n1(ttt
Return TT
Online proximal stochastic gradient method. The main goal a learning algorithm for prob- lem (T) generate sequence of points {#r) } that minimize some natural performance metric. The most prevalent performance metrics in the literature are the tracking error and the dynamic regret. We will focus
types of tracking error, || =t 122 and (x( (px(z))
We make the standing assumption that at every time t, and at every query point x, the learner may obtain an unbiased estimator fz(xx) ) of the true gradient (z((()) in order to proceed with stochastic gradient-like optimization algorithm. With this oracle access, the online proximal stochastic gradient method-recorden as Algorithm [ Jbove-ii each iteration i simply takes a stochastic gradient step on St &; followed by proximal operation rz:
F++1 = prox n.r. (xa T(g:) = arg min (re(u) + 2q, l1u (xt n=90)l wERd
The goal of our work is to obtain efficiency estimates for this procedure that hold both in expectation and with high probability.
Minimizer drift. The guarantees obtain allow both the iterates x, and the minimizers sf to evolve stochastically. This is convenient for example when tracking a moving target zt whose motion may be governed by stochastic process such as a random walk or a diffusion (see Example Throughout, we define the minimizer drift at time to be the random variable
A | xi+1ll-

---

Clearly, efficiency estimate for Algorithm 1 must take into account the variation of the functions St in time i. Two of the most popular metries for measuring such variations are the minimizer drift A and the gradient variation sup,, ft) v fi+1 (z)ll. Given identical regularizers, bound on the gradient variation always implies a bound on the minimizer drift.
Lemma 2.3 (Gradient variation vs. minimizer drift), Suppose i, 2 are such that the regularizers and Yt are identical. Then we have
p| 5t |l S VV - (x(()l
2.2 Running assumption the stochastic process
Setting the stage, given {1x} and {ec] in Algorithm|
| we let
24 = V fe(z)) gt
denote the gradient noise at time and we impose the following assumption modeling stochasticity in the online problem throughout Sections and
Assumption 2.4 (Stochastic framework). There exists filtered probability space FR,F, with filtration (Fi) such that Fu = (0, [t} and the following holds for all f 2 0:
Zz. x Ω + Fd are F F--masuurable
(ii) 2z: Ω + Rd is F measurable with E/2 Fil = 0.
The first item of Assumption 2.4 simply says that 2; and z; are fully determined by information up to time The second item of Assumption 2.44 asserss that the gradient noise is fully determined by information up to time
and has zero mean conditioned on the information up to time I; for example, this holds naturally in Example 2.2 if we take yr Vi(E,, wa) with wt D(u:) provided the loss ((, wx) is -mmoohh.
Tracking the minimizer with the last iterate
In this section, present bounds the tracking error || x 2| that valid both in expectation and with high probability under light-tail assumptions. Further, we show that geometrically decaying learning rate schedule may be superior constant learning rate in terms of efficiency.
3.1 Bounds in expectation
We begin with bounding the expected value E| x71 The starting point for our analysis the following standard one-step improvement guarantee.
Lemma 3.1 (One-step improvement). For all x IRd, the iterates {at} produced by Algorithm !
with 1/s < 1/L satisfy the bound:
2T (Fr(2++1) (x)) s (1 - pm))l =1|2-||a<4 - x1|² + (2 Ie 2)
I- Lop 1| 11.
For simplicity, we state the main results under the assumption that the second moments E. 1l are uniformly bounded; more general guarantees that take into account weighted averages of the moments and allow for dieendenn learning rates follow from Lemma 3.1 as well.
[ and
Assumption 3.2 (Bounded second moments). There exist constants A, > 0 such that the following holds for all 2 0.
(Drift) The minimizer drift A, satisfies E[A?] a
(ii) (Noise) The gradient noise 2, satisfies E | 0²
The following theorem establishes an expected improvement guarantee for Algorithm I and serves as the basis for much of what follows; see Section 5.1 of the Supplement for the precise statements and proofs of the present section.

---

Theorem 3.3 (Expected distance). Suppose that Assumption 3.2 holds. Then the iterates produced
by Algorithm 7 with constant learning rate li S 1 1/21. satisfy the bound:
no²
E| ze - =,11 pm) 1| 2ol1
2
p moise
optimization
drift
Interplay of optimization, noise, and drift. Theorem 3.3 states that when using constant learning rate, the error El|a; z 12 decays linearly in time until it reaches the "noise+<drift" emror po²/pe + (A/un)?, Notice that the "noise+drift" error cannot be made arbitrarily small. This is perfectly in line with intuition: learning rate that is too small prevents the algorithm from catching up with z7. We note that the individual error terms due the optimization and noise are classically known to be tight for PSG; tightness of the drift term is proved in 23 Theorem 3.2].
With Theorem 3.3 in hand, are led define the following asymptotic tracking error of Algorithm corresponding to E E 2; together with the corresponding optimal step size:
{ fmm)
A
{ 22
2
1/3
: min (0.11/22
and 7/ min
1OO2
Plugging 7/, into the definition of E, see that Algorithm eexhbbis qualitatively different behaviors in settings corresponding to high or low drift-to-noise ratio A/o, explicitly given by
LA 2/3
if
1673
EX
otherwise.
Two regimes of variation brought to light by the above computation: the high drift-to-noise regime A/a 2 /u/1663 and the low drift-to-noise regime A/a < v1//16,33 The high drift-to-noise regime is uninteresting from the viewpoint of stochastic optimization because the optimal learning rate is as large in the deterministic setting, 7/. 1/2L. contrast, the low drift-to-noise regime interesting because the optimal learning rate 7/. (2A² /a²) smaller than 1/2L and exhibits a nontrivial scaling with the problem parameters.
Learning rate vs. rate of variation. A central question to find a learning rate schedule that achieves a tracking error E1|,, - x7 that is within a constant factor of in the shortest possible time. The answer is clear in the high drift- drift-to-noise regime A/o 2 Vn/16G3. Indeed, in this case, I with the constant learning rate 7/+ = =1/2I. will find
Theorem 3.3 directly implies that Algorithm| point 2t, satisfying El[ar, a 1|2 S E in time L. (T./u) log(1|zro - == / Notice that the efficiency estimate is logarithmic in E/E: intuitively, the reason for the absence of a sublinear component is that the eиror due to the drift A dominates the error due to the variance o² in the stochastic gradient.
The low drift-to triis- regime A/O < VH/16I3 is more subtle. Namely, the simplest strategy is to exccute Algorithm I with the constant learning rate 7) (2 (2A2/u02)1/3 Then direct application of Theorem 3.3 yields the estimate E||x, x; 1| S E in time S (0²/H²²) log([=oo - /E)) This efficiency estimate can be significantly improved by gradually decaying the learning rate using "step-decay schedule", wherein the algorithm implemented epochs with the new learning rate chosen to be the midpoint between the current learning rate and 1).. Such schedules to improve efficiency in the static setting, as was discovered [I], and can be used here. The end result is the following theorem (see Theorem 5.5 of the Supplement for the precise statement).
well known
Theorem 3.4 (Time to track in expectation, informal). Suppose that Assumption 3.2 holds. Then there is learning rate schedule {me) such that Algorithm produces point Ty satisfying
L
[ - 2751 12
o²
Elia, x;i1² S after time
log
128
1
Remarkably, the efficiency estimate in Theorem classical static setting 20), with playing the role of the target accuracy E. Theorems 333 and 3.4 provide useful bascline guarantees for the performance of Algorithm Nonetheless, these guarantees
3.4 looks identical to the efficiency estimate in the
5

---

all stated in terms of the expected tracking error ElIa2 xद 11 and therefore only meaningful the entire algorithm can be repeated from scratch multiple times. There no shortage of situations which a learning algorithm is operating in real time and the time drift is irreversible; in such settings, the algorithm may only be executed once. Such settings call for efficiency estimates that hold with high probability, rather than only in expectation.
3.2 High-probability guarantees
We next present high-probability guarantees on the tracking error || - x;11 To this end, we make the following standard light-tail assumptions on the minimizer drift and gradient noise [13 20 24
Assumption 3.5
(Sub-Gaussian drift and noise). There exist constants A, such that the following holds for all f 2 0.
ii (Drift) The square drift A is sub-exponential conditioned on Fe with parameter A
E exp((AA))
FF < exp(\A²) for all < A
(ii) (Noise) The noise 2, is norm Sab-Gaussian conditioned on F, with parameter o/2:
P[[ 2 T Fi] S eexp( for all
0.
Note that the first item of Assumption 3.5 is equivalent asserting that the minimizer drift A, is sub-Gaussian conditioned on F,. Clearly Assumption 3.5 implies Assumption 3.2 with the same constants A, a. It is worthwhile note some common settings in which Assumption 3.5 holds; the claims in Remark 3.6 follow from standard results on sub-Gaussian random variables [8] 31.
Fix constants A, a > 0. If A, is bounded by A, then clearly A? is sub-exponential (conditioned on F,) with parameter A Similarly, if || is bounded by then is norm sub- Gaussian (conditioned on Fi) with parameter a o/2 (by Markov's inequality). Alternatively, if the increment x; -i+1 mean-7ero sub-Gaussian conditioned on Fg with parameter A/Vd, then z; 2 is mean-zero norm uab-Gausiian conditioned on Fr with parameter 2 A and hence A is sub-exponential conditioned F, with parameter A for some absolute constant e > 0. Similarly, 2, is sub-Gaussian conditioned on Fe with parameter a/4v 2d, then ž is norm sub-Gaussian conditioned on F, with parameter o/2.
Remark 3.6 (Common settings for Assumption 3.5
The following theorem shows that if Assumption 3.5 holds, then the expected bound on || - -xx==1111 11 derived in Theorem 3.3 holds with high probability.
Theorem 3.7 (rogb--robabilityy distance tracking). Suppose that Assumption 3.5 holds and let {a+}
be the iterates produced by Algorithm | with constant learning rate 1) <. 1/2L. Then there is absolute constant c > such that for any specified t E N and E (0, the estimate
no²
A
|| x111² < (1 2
xūl?²
+
log (
J
holds with probability at least 5.
The proof of Theorem 3.7 employs a technique used in [13. The main idea to build careful recursion for the moment generating function of || x 2| leading to one-sided sub-exponential tail bound. As a consequence of Theorem 3.7 we can again implement a step-decay schedule in the low drift-to-noise regime to obtain the following efficiency estimate with high probability; see Section 5.2 of the Supplement for the formal statements and proofs.
Theorem 3.8 (Time to track with high probability, informal). Suppose that Assumption 3.3 holds and that we are in the low drift-to-noise to-soise regime A/o < / 1/p//61" Then there is learning rate schedule {mp such that for any specified (0, 1), Algorithm I produces point 2, satisfying
It x 11 < E log

---

with probability at least 1 K6 after time
L S
200 z0ll
+ o²
1 T,
0 1/3 A
log
where K S log2
3
4 Tracking the minimal value
The results outlined so far have focused on tracking the minimizer x². In this section, we present results for tracking the minimal value sp. These two goals are fundamentally different. Generally speaking, good bounds on the function gap along with strong convexity imply good bounds on the distance to the minimizer; the reverse implication is false. To this end, we require a stronger assumption on the variation of the functions fi in time t: rather than merely controlling the minimizer drift A we will assume control the gradient drift
G sup [[) ff(()))l
Our strategy is to track the minimal value along running average ê, of the iterates produced by Algorithm| 1 as defined Algorithm 2 below. The reason behind using this particular running average is brought to light in Section 5.3 of the Supplement, where we apply standard averaging
technique to a one-step improvement along 22 to obtain the desired progress along St.
Algorithm 2 Averaged Online Proximal Stochastic Gradient
PSG To μ4 {mc). T)
Input:
initial Fy =: f.. strong convexity parameter μu, and step size sequence {nd (0, 2p Step f = o.....
Set = V (x(e)
Set 2++1 = prox miri (Ir - 1/1ttt
Set 6,41 = (1
2-
Lr +
2-
Tt+1
Return 2r
4.1 Bounds in expectation
We begin with bounding the expected value ((,) - v0)) Analogous Assumption 3.2 we make the following assumption regarding drift and noise.
Assumption 4.1 (Bounded second moments). The regularizers r, = r are identical for all times and there exist constants A, > 0 such that the following properties hold for all 0 < <
(Drift) The gradient drift Gt satisfies E E S (pAli t1)
(ii) (Noise) The gradient noise satisfies E | < a² and E(2,, x;) = 0.
These two assumptions are natural indeed. Taking into account Lemma 2.3 it clear that Assump- tion 4.J.imppes the earlier Assumption 3.2 with the same constants A, σ. The assumption on the drift intuitively asserts that gradient drift G can grow only linearly in time particular, returning to Example 2.2 suppose that the distribution map D(-) is --Lischiizz continuous the Wasserstein- distance, 3-Lipschitz continuous for all æ. Then the Setborovicc-Rubinste
t| (in expectation). In
loss ((),w) is C smooth for all w, and the gradient V((x,)) is
duality theorem directly implies E[C S (7/))2|llu - 22? Therefore, as long as the second moment TE||u, u, 1|2 scales quadrat- ically in j - t). the desired drift assumption holds. The assumption on the noise requires uniform bound on the second moment =,, and for the condition E(2z, .r) 0 to hold. The latter property confers weak form of uncorrelatedness between the gradient noise 2; and the future minimizer at and holds automatically if the gradient noise and the minimizers evolve independently of each other, as would typically be the case for instance in Example 2.2
The following theorem provides an expected improvement guarantee for Algorithm 2 for the full statement and proof, see Corollary 5.12 of the Supplement.
7

---

Theorem 4.2 (Expected function gap). Suppose that Assumption
holds, and let { be the iterates produced by Algorithm with constant learning rate 1) S 2l. Then the following bound holds for all 2 0:
E (())( - p.] S (1 (1-11) 2n) ((p(zzu) pō)
+ no
puy drift
optimization
noise
The "noise+drift" enror term in Theorem coincides with μ times the corresponding error term in Theorem 3.3, as expected due to ju-trrong convexity. With Theorem 4.2 in hand, we are led to define the following asymptotic tracking error of Algorithm 2 corresponding ((pr((+)) p
G = μr =
min (E(0.1/2L)
110 +
pm2
The corresponding asymptotically optimal choice of 1 is again given by n. and the dichotomy governed by the drift-to-noise ratio A/o remains:
o² + (LA)²
if
162
G
2/3
Ag²
1
otherwise.
In the high drift-to-non to-no regime A/o 2 v 4/16L3 Theorem 4.2 directly implies that Algorithm
with the constant learning rate 7). 1/2L finds point &, satistying (f)) - -pt 3 in time
t S (L/ log((<o(z0)) - ()) /9). the low drift-to- regime A/o < ////16,3, another direct application of Theorem 4.2 shows that Algorithm 2 with the constant learning rate 7)
(2A² / finds a point é. satisfying (2t) - o & G in time t Z. (a²/pg) log( (4o (G)/ As before, this efficiency estimate can significantly improved by implementing a step- decay schedule. The end result is the following theorem; see Theorem 5.13 of the Supplement for the formal statement and proof.
Theorem 4.3 (Time to track in expectation, informal). Suppose that Assumption 4.1 holds. Then there is learning rate schedule {ne} such that (ggorithm@produccee point ã, satisfying
L t t log
(pu(xo))
P0
o²
Elpp((t)= 21 S
after time
4
g
G
4.2 High-probability guarantees
Our next result is an analogue of Theorem 4.2 that holds with high probability. Naturally, such a result should rely light-tail assumptions the gradient drift Ga, and the norm of the gradient noise || We state the guarantee under the assumption that G and || are conditionally sub-Gaussian (Assumption 4.4). In particular, we require for the first time that the gradient noise 2; is mean-zero conditioned on the o-algebra
Fr, xFF,
for all 0 S i < t; the property B[2; FF..)l = O would follow from independence of the gradient noise 2; and the future minimizer x; and is reasonable in light of Examples 2.1 and 2.2
Assumption 4.4 (Sub- Sotb-Gasssian drift and noise). The regularizers rı r identical for all times / and there exist constants A, > 0 such that the following properties hold for all < < t.
(Drift) The square gradient drift G2 sub-exponential with parameter (pAli t))2: exp (AG < exp (A(alii +))?) for all < (HDji i t|) -
(ii) (Noise) The gradient noise z; is mean-zero norm sub-Gaussian conditioned on F,, with parameter o/2, 2,, i.e., E[z; Fi. = 0 and
P|||a||| 2 r Fo,e} } s eexp -222(222//) for all 2
8

---

Clearly the chain of implications holds:
Assumption 4.4
Assumption
4.1
Assumption 3.2
Example 4.5 (Sub-Gaussian feature model). In the setting of logistic regression, sub-Gaussian gradient noise naturally arises from sampling from a sub- Gaussian feature model. Indeed, this case the objective takes the form fa) A. [Ei= log(1 + exp(a,, 2)) - (Az, b)] and drawing (A, b) yields the sample gradient f(()) A (S(r)) - b). where R has rows 01, an R and S denotes the sigmoid function. Being that S and b are bounded, it therefore follows that if the rows of A are sub-Gaussian, then so is the gradient noise (xx) f(x).
The following theorem shows that Assumption 4.4 holds, then the expected bound on (p((tt) - 4p derived in Theorem 4.2 holds with high probability.
Theorem 4.6 (Function gap with high probability). Suppose that Assumption 4.4 holds, and let {
be the iterates produced by Algorithm 2 with constant learning rate 1) S 1/2I. Then there is an absolute constant > 0 such that for any specified t E N and 8 E (0, 1), the estimate
gi - 1p <(11 (1- (Po(20)) - v6) + noo +
A
log (g)
1m7
holds with probability at least - 5.
The proof of Theorem 4.6 is based on combining the generalized Freedman inequality of [3 with careful control on the drift and noise in improvement guarantees for the proximal stochastic gradient method. The key observation is that although we do not have simple recursive control on the moment generating function of (fx)) Ppt (as we do with ||x - x2il²> we can control the tracking error (ft) -pt by leveraging control the martingale Ei=0 (2,, 24 x;){t=l-i where < pmn pn). This martingale is self-regulating in the sense that its total conditional variance is bound by the history of the process; the generalized Freedman inequality is preciscly suited to bound such martingales with high probability.
With Theorem 4.6lin in hand, we may implement step-decay schedule as before to obtain the following efficiency estimate; see Section 5.4 of the Supplement for the formal statements and proofs.
Theorem 4.7 (Time to track with high probability, informal). Suppose that Assumption 4.4 holds and that we are in the low drift-to-noise regime A/o < vp/16L3. Fix d E (0, 1). Then there is learning rate schedule {Ne) such that Algorithm 2 produces a point &s satisfying
2 S 9 glog (
se (et())
with probability at least 1 K6 after time
L
log p0 (o((x))
+ a²
log (e) )= where K S log,
1
p
1/3
log
-
ug
L
A
Conclusion
We presented finite-time efficiency estimates in expectation and with high probability for the tracking error of the proximal stochastic gradient method under time drift. Through our investigation of the interplay between the learning rate, the noise variance in the gradient oracle, and the strength of the time drift, we uncovered two regimes of interest, each suggesting a different choice of learning rate. The high- nigh-probability guarantees extend recent results to the deeendepe setting.
Acknowledgments
This work was supported by NSF CCF-2019844, NSF DMS-2023166, NSF DMS-1651855 CIFAR- LMB, and faculty research awards. Part of this work done while Z. Harchaoui visiting the Simons Institute for the Theory of Computing.

---

References
[1] A. Agarwal, O. Chapelle, M. Dudík, and J. Langford. A reliable effective terascale linear learning system. Journal of Machine Learning Research, 15()):1111-113,, 2014.
[2] F. Bach and E. Moulines. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, volume 24, pages 451-459. Curran Associates, Inc., 2011.
[3] P. L. Bartlett, S. Ben-David, and S. R. Kulkarni. Learning changing concepts by exploiting the structure of change. Machine Learning, 41(2):153-174, 2000.
[4] P. L. Bartlett, V. Dani, T. P. Hayes, S. M. Kakade, A. Rakhlin, and A. Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the 21st Annual Confer- ence on Learning Theory. Omnipress, 2008.
[5] O. Besbes, Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227-1244, 2015.
[6] L. Bottou. Stochastic learning. In Advanced Lectures on Machine Learning, ML Summer Schools 2003, volume 3176 of Lecture Notes in Computer Science, pages 146-168. Springer, 2003.
[7] L. Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade Second Edition, volume 7700 Lecture Notes in Computer Science, pages 421-436. Springer, 2012.
[8] L. Bottou and O. Bousquet. The tradeoffs of large scale learning. In Advances in Neural Information Processing Systems, volume 20, pages 161-168. Curran Associates, Inc., 2007.
[9] C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory, volume of Proceedings of Machine Learning Research, pages 6.1 6.200. PMLR, 2012.
[10] S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22((): (464))4449111) 1499, 2012.
[11] S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2061-2089, 2013.
[12] L. Guo and L. Ljung. Exponential stability of general tracking algorithms. IEEE Transactions on Automatic Control, 13(6):1376-133 1387, 1995.
[13] N. A. Harvey, Liaw, Y. Plan, and S. Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Proceedings of the 32nd Conference on Learning Theory. volume 99 of Proceedings of Machine Learning Research, pages 1579-1613, PMLR, 2019.
[14] E. Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 233-4):5573325, 2016.
[15] E. Hazan and S. Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489-2512 2014.
[16] E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th International Conference on Machine Learning. Omnipress, 2009.
[17] M. Herbster and M. K. Warmuth, Tracking the best expert. Machine Learning. 32(2):11 1998.
[18] C. Jin, Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv:1902.03336 2019.
10

---

[19] H. J. Kushner and G. G. Yin. Stochastic Approximation Algorithms and Applications, volume 35 of Applications of Mathematics. Springer, 1997.
[20] G. Lan. An optimal method for stochastic composite optimization. Mathematical Programmiing 133(1))365-397, 2012.
[21] H. Lang, L. Xiao, and P. Zhang. Using statistics to automate stochastic optimization. In Advances in Neural Information Processing Systems, volume 32, pages 9536-9546. Curran Associates, Inc., 2019.
[22] P. M. Long. The complexity of learning according to two models of drifting environment. Machine Learning, 37(3):337-34, 1999.
[23] L. Madden, S. Becker, and E. Dall' Anese. Bounds the tracking error of first-order online optimization methods. Journal of Optimization Theory and Applications, 189())437-4577 2021.
[24] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):177--109, 2009.
[25] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. Proceedings of the 29th International Conference on Machine Learning. Omnipress, 2012.
[26] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 993-1019. PMLR, 2013.
[27] A. H. Sayed. Fundamentals of Adaptive Filtering. John Wiley & Sons, 2003.
[28] R. E. Schapire and Y. Freund. Boosting: Foundations and Algorithms. The MIT Press, 2012.
[29] S. Sra, S. Nowozin, and S. J. Wright, Optimization for Machine Learning. The MIT Press, 2011.
[30] N. Srebro, K. Sridharan, and A. Tewari. On the universality of online mirror descent. In Advances in Neural Information Processing Systems, volume 24, pages 2645-2655 1645-2653. Curran Associates, Inc., 2011.
[31] R. Vershynin. Righ-Dimensional Probability: An Introduction with Applications in Data Sci- ence, volume 47 Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[32] C. Wilson, V. Veeravalli, and A. Nedić. Adaptive sequential stochastic optimization. 1EEE Transactions Automatic Control, 64(2):496-555 509, 2018.


Reviews:
[{"review_id": "zjZq5Hlc-4A", "reviewer": "Reviewer_WvZE", "summary": "The paper under review is devoted to the analysis of the stochastic approximation algorithm with the presence of the drift term. The main result is to derive finite-time bounds on the expected mean square error. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors consider the problem of form\n$\nmin f(x) + r_t(x)\n$, where $r_t$ is a drift term. The author assumes that the stochastic gradient used for solving the problem is unbiased. Under that assumptions, the author proves finite-time bounds. The results seem to be correct but I have serious doubts about novelty.  The assumptions about bias and assumptions on drift term in my opinion make that such a bound are well known in the community. In my opinion, this kind of result can be straightforwardly obtained from Athchade et al 2016 or Rossaco et al 2014. Due to that, I do not believe that the paper meets the standards of NIPS conference.\n\n####UPDATE\nAfter reading the author response and other reviews, I agree that  I underestimate the novelty of the paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work has no potential negative impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10h"}, "extra_text": {}}, {"review_id": "uspblFfL3Gs", "reviewer": "Reviewer_YZ6G", "summary": "This work considers the problem of stochastic gradient descent for time varying optimization. Based on the analysis of SGD in this setting, the problem actually contains two qualitatively different regimes: one with high drift-to-noise ratio, and one with low drift-to-noise ratio. The paper further provides tight convergence analysis (both in expectation and in high probability) for the two regimes.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper gives a new way of looking at time varting optimization. The proof techniques are not new, but the discovery of the two regimes is very interesting and this implication can be useful for real world applications. \n\nThis paper is clearly written and well-organized.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential negative societal impact is addressed properly.\n\nI don't have any major problem for this paper. There are only some minor problems (the numbering of the lines is for the supplementary material):\n\nThe checklist is unfinished. The authors should do a double-check.\n\nThe figures do not show the \"95% CI\" indicated in the legend.\n\nLine 323, one of the \"Theorem 4.2\" should be \"Theorem 3.2\".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "khzwoz6bmmt", "reviewer": "Reviewer_wsFZ", "summary": "This paper studies stochastic optimization under non-stationary drift. Losses are assumed\nstrongly convex with Lipschitz gradients and unbounded domain. Finite-sample\nbounds are derived for the tracking errors\n$||x_t - x_t^*||$ and $\\ell_t(x_t)-\\min_{x^*}\\ell_t(x^*)$ of SGD, both in-expectation and with high-probability.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I thought the paper was excellent. The analysis is useful and interesting, and the writing\nwas clear and precise throughout. I could\nsee it becoming a go-to reference for myself, and I can think of several colleagues who would be\nequally enthusiastic. \nMy questions and concerns are mostly minor, revolving around\nadaptive filtering and presentation.\n\n**Adaptive Filtering**\nFirst, I'm generally a bit suspicious about how much the results presented here actually\nrelate to adaptive filtering, as is claimed. It seems to me that the results relate only\nto filtering --- the optimal choice of $\\eta$ depends on knowledge of $\\Delta$, which would\namount to knowing the variance of the process noise driving the hidden state. Concretely, in the classic\nleast-squares setting, we'd have $x_{t}^*=F_{t} x_{t-1}^* +u_t$, $y_t = H_t x_t^* + v_t$ , where $u_t\\sim\\mathcal{N}(0, Q)$ and $v_t\\sim N(0, R)$, and\nwe want to track $x_t^*$ through observations of $y_t$. The results presented here seem to suggest we'd need to\nknow both $R$ and $Q$ in order to set $\\eta=\\eta^*$, but given this information there's really nothing adaptive about the problem ---\nnot knowing these variances is precisely the difficulty of adaptive filtering!\nHowever, I think a lot of the discussion surrounding Adaptive Filtering would be just as effective rephrased in terms\nof regular filtering. I would also be curious to see exactly how the iterates chosen when using the optimal fixed $\\eta^*$\nrelate to the steady-state solution of the Kalman filter, which *also* requires knowledge of the noise variances to\nset its step-size/gain matrix.\n\nPrevious point aside, it seems like the connection to filtering could only hold\nin the 1d and/or time-invariant case without additional information? In higher dimensions, even the\nsquared loss $\\frac{1}{2}(y_t - F_tx_t)^2$ will only satisfy the strong-convexity assumption in a rather small subset \nof filtering problems.\nIn my (quite limited) experience with filtering, it seemed like additional\nassumptions on the transition/measurement matrices (e.g. the observability matrix is invertable, etc)\nto say much of anything in higher dimensions.\n\n**Presentation**\nI am quite irritated with the supplementary materials. Rather than an appendix containing\ntechnical details, the supplementary materials are an extended version of the paper,\nalso with its own appendix. This feels like a rather dishonest way to get around the\npage limit requirements. It was also just generally annoying to navigate, and find what\nI was looking for, with some results now being mixed in along side the things I already read\nin the main paper, some being in the appendix of the supplementary, no real indication of\nwhere I should look to find something mentioned in the main text. For now I've adopted the\noptimistic view that this was a product of time restrictions and a properly structured\nappendix is in the works.\n\nThe experiments were the weakest part of the paper to me; in my opinion these\ncould be moved entirely to the appendix to make room for some of the other\nresults. Further, there's actually a 9 page limit this year, so there's\npotentially two full pages that could be used to avoid deferring so many of the results to the appendix.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Unsure. Reviewed with another paper over the course of a weekend. Periodic distraction by interesting citations."}, "extra_text": {}}, {"review_id": "MyHrG8iEaMh", "reviewer": "Reviewer_6E1U", "summary": "the paper deals with tracking the minimum of a convex function which is evolving in time according to an unknown stochastic dynamic. The racking problem is classical in signal processing and automatic control (identification of linear or non-linear systems which are changing over time). It is less familiar in ML despite the fact that the problem of concept drift is very important in current practice. \nThe paper presents finite-time bound both in expectation and in high-probability for the tracjking of a a proximal stochastic gradient algorithm. The proposed result displays the relations between the learning rate, the excess risk and tracking error. \n\nThe paper uses rather stringent technical assumptions. In particular, the average loss $f_t$ are $\\mu$-strongly convex, and the gradient  $\\nabla f_{t}$  is  $L$-Lipschitz continuous.  The noise $z_{t}:=\\nabla f_{t}\\left(x_{t}\\right)-g_{t}$ is a martingale increment with uniformly bounded variance.\n\nThe paper first provides finite time bounds for $\\mathbb{E}\\left\\|x_{t}-x_{t}^{\\star}\\right\\|^{2}$ under the assumption that $\\mathbb{E}\\left\\|x_{t}^{\\star}-x_{t+1}^{\\star}\\right\\|^{2} \\leq \\Delta^{2}$. The bound in Theorem 3.2. has a transient term, a fluctuation term and a tracking error. The fluctuation term is proportional to the gradient noise variance and the stepsize. The tracking error is inversely proportional to the square of the stepsize.  This result coincides to the classical tracking error for linear system identification (under the considered stochastic model for the parameter).\nThe authors identify two regimes depending on the ratio  $\\Delta / \\sigma$.  The high drift-to-noise is not interesting (the stepsize should then be set like in the stationary case), but the low drift-to-noise  necessitates a  learning which is typicallt smaller that $1/2L$. A finite time bound is obtained in Theorem 3.2 (for constant learning rate) and Theorem 3.8 (for a step-decay schedule). In Section 3.3, the authors develop high-probability guarantees under the assumption that the tracking error is (conditionally to the past) sub-exponential and the gradient noise is sub-gaussian. The HP bound (for fixed stepsize) is given in Theorem 3.10. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: To my knowledge, this is the first paper that deals with tracking in machine learning. The study of tracking is very classical in system theory, but not in ML. Most of the work in pursuit is devoted to the identification of linear systems. The work on bounds in HP is also new.\n\nQuality:  The paper is well written and the main arguments are easy to follow. The proofs are  adapted from the classical arguments in the stationary case, so there are no really major surprises.  I would have liked a more detailed discussion of the assumptions. The assumption of sub-Gaussianity of the gradient seems to me to be costly. If the $f_t(x)= \\mathbb{E}[ (y - \\varphi^x)^2]$ where $\\varphi \\sim N(0,\\sigma^2 Id) $ (the \"easy\" gaussian linear regression), and if $\\tilde{\\nabla} f_t(x)= \\varphi_t ( y_t - \\varphi_t x)$ (assuming for simplicty $\\{(y_t,\\varphi_t)\\}$ i.i.d. then this assumption is not satisfied. Even if the regression vector is  bounded, then the assumption is not satisfied (unless $x_t$ is bounded). Therefore the assumption on the noise term seems strong. It would be good to check the assumption whether the condition is satisfied for the $\\ell_2^2$-regularized logisitc regression (under which condition on the regressors ?). When reading the example, it is not clear to understand what you mean by \"using a noisy gradient $g_t$ satisfying $\\left\\|g_{t}-\\nabla f_{t}\\left(x_{t}\\right)\\right\\| \\leq \\sigma$ for each step  $t$\n\n\n\nSignificance: This is a essentially theoretical paper, a  first step in analyzing the tracking ability of stochastic gradient algorithms. Of course, this work opens many research directions and questions. It is clear that all the results remain very theoretical, one would like to have algorithms able to adapt to different constants (lipschitz, strong convexity, non-stationarity). The assumptions are very strong (in particular, it is very restrictive to assume a priori that the gradient noise is sub-gaussian, this precludes the use of this result even in very simple examples).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers were positive about this paper and felt that it presented a good analysis of less-well-studied problem.

Decision: Accept (Poster)