Stochastic optimization under time drift: iterate averaging, step decay, and high-probability guarantees
Year: 2021

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.

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

heading: 1 Introduction
text: Stochastic optimization underpins much of machine learning theory and practice. Significant progress has been made over the last two decades in the finite-time analysis of stochastic approximation algorithms; see, e.g., [1, 2, 6, 7, 8, 21, 24, 29, 30]. The predominant assumption in this line of work is that the distribution generating the data is 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 a classical problem in signal processing related to stochastic tracking [19, 27], 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 [14, 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 as 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 a “critical step size”.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1.1 Related work
text: 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 as a 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 a more modern viewpoint [5, 23, 32]. In particular, the paper [23] focuses on (accelerated) gradient methods for deterministic tracking problems, while [32] analyzes a 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 are distinct.
Online optimization with controlled increments. Online learning under concept drift was first considered by [22] and further developed in several papers [3, 17]. 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 a time partitioning with an expert in each time interval, and the goal is to compete with the expert in each segment. Closer to this work is [14, 16], 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, 9, 26]. In contrast to 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-probability guarantees in stochastic optimization. A large part of our work revolves around high-probability guarantees in stochastic optimization. Classical references on the subject in static settings and for minimizing regret in online optimization include [4, 15, 20, 25]. There exists a variety of techniques for establishing high-probability guarantees based on Freedman’s inequality and doubling tricks; see, e.g., [4, 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.

heading: 1.2 Outline
text: The outline of the paper is as follows. Section 2 formalizes the problem setting of time-dependent stochastic optimization and records the relevant assumptions. Sections 3 and 4 present the main results of the paper. Specifically, Section 3 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 in Section 5 of the Supplement, and illustrative numerical results appear in Section 6 of the Supplement.

heading: 2 Framework and assumptions

heading: 2.1 Stochastic optimization under time drift
text: We consider the sequence of stochastic optimization problems
min x ϕt(x) := ft(x) + rt(x) (1)
indexed by time t ∈ N. We make the standard standing assumption that (i) each function ft : Rd → R is µ-strongly convex and C1-smooth with L-Lipschitz continuous gradient for some common parameters µ,L > 0, and (ii) each regularizer rt : Rd → R∪{∞} is proper, closed and convex. The
minimizer and minimal value of (1) will be denoted by x?t and ϕ ? t , respectively. Throughout, ‖ · ‖ denotes the `2-norm on Rd induced by the dot product 〈·, ·〉. As motivation, we describe two classical examples of (1) 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 of a drifting target). The problem of stochastic tracking, related to the filtering problem in signal processing, is to track a moving target x?t from observations
bt = ct(x ? t ) + t,
where ct(·) is a known measurement map and t is a mean-zero noise vector. A typical time-dependent problem formulation takes the form
min x E t `t(bt − ct(x)) + rt(x),
where `t(·) derives from the distribution of t and rt(·) encodes available side information about the target x?t . Common choices for rt are the 1-norm and the squared 2-norm. The motion of the target x?t 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 a distributional drift is to learn while the data distribution may change over time. More formally, one problem formulation takes the form
min x E w∼D(ut) `(x,w) + r(x).
where D(ut) is a data distribution that depends on an unknown parameter sequence {ut}, which itself may evolve stochastically. The evolution of ut is often assumed to be piecewise constant in t in online learning [14, 28].
Algorithm 1 Online Proximal Stochastic Gradient PSG(x0, {ηt}, T ) Input: initial x0 and step size sequence {ηt}Tt=0 ⊂ (0,∞) Step t = 0, . . . , T − 1:
Set gt = ∇̃ft(xt) Set xt+1 = proxηtrt(xt − ηtgt)
Return xT
Online proximal stochastic gradient method. The main goal of a learning algorithm for problem (1) is to generate a sequence of points {xt} 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 on two types of tracking error, ‖xt − x?t ‖2 and ϕt(xt)− ϕt(x?t ). We make the standing assumption that at every time t, and at every query point x, the learner may obtain an unbiased estimator ∇̃ft(x) of the true gradient∇ft(x) in order to proceed with a stochastic gradient-like optimization algorithm. With this oracle access, the online proximal stochastic gradient method—recorded as Algorithm 1 above—in each iteration t simply takes a stochastic gradient step on ft at xt followed by a proximal operation on rt:
xt+1 := proxηtrt(xt − ηtgt) = arg min u∈Rd
{ rt(u) +
1 2ηt ‖u− (xt − ηtgt)‖2
} .
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 we obtain allow both the iterates xt and the minimizers x?t to evolve stochastically. This is convenient for example when tracking a moving target x?t whose motion may be governed by a stochastic process such as a random walk or a diffusion (see Example 2.1). Throughout, we define the minimizer drift at time t to be the random variable
∆t := ‖x?t − x?t+1‖.
Clearly, an efficiency estimate for Algorithm 1 must take into account the variation of the functions ft in time t. Two of the most popular metrics for measuring such variations are the minimizer drift ∆t and the gradient variation supx ‖∇ft(x)−∇ft+1(x)‖. Given identical regularizers, a bound on the gradient variation always implies a bound on the minimizer drift.
Lemma 2.3 (Gradient variation vs. minimizer drift). Suppose i, t ≥ 0 are such that the regularizers ri and rt are identical. Then we have
µ‖x?i − x?t ‖ ≤ ‖∇fi(x?t )−∇ft(x?t )‖.

heading: 2.2 Running assumption on the stochastic process
text: Setting the stage, given {xt} and {gt} as in Algorithm 1 we let zt := ∇ft(xt)− gt
denote the gradient noise at time t and we impose the following assumption modeling stochasticity in the online problem throughout Sections 3 and 4.
Assumption 2.4 (Stochastic framework). There exists a filtered probability space (Ω,F ,F,P) with filtration F = (Ft)t≥0 such that F0 = {∅,Ω} and the following holds for all t ≥ 0:
(i) xt, x?t : Ω→ Rd are Ft-measurable,
(ii) zt : Ω→ Rd is Ft+1-measurable with E[zt | Ft] = 0.
The first item of Assumption 2.4 simply says that xt and x?t are fully determined by information up to time t. The second item of Assumption 2.4 asserts that the gradient noise zt is fully determined by information up to time t+ 1 and has zero mean conditioned on the information up to time t; for example, this holds naturally in Example 2.2 if we take gt = ∇`(xt, wt) with wt ∼ D(ut) provided the loss `(·, wt) is C1-smooth.

heading: 3 Tracking the minimizer with the last iterate
text: In this section, we present bounds on the tracking error ‖xt − x?t ‖2 that are valid both in expectation and with high probability under light-tail assumptions. Further, we show that a geometrically decaying learning rate schedule may be superior to a constant learning rate in terms of efficiency.

heading: 3.1 Bounds in expectation
text: We begin with bounding the expected value E‖xt − x?t ‖2. The starting point for our analysis is the following standard one-step improvement guarantee.
Lemma 3.1 (One-step improvement). For all x ∈ Rd, the iterates {xt} produced by Algorithm 1 with ηt < 1/L satisfy the bound:
2ηt(ϕt(xt+1)− ϕt(x)) ≤ (1− µηt)‖xt − x‖2 − ‖xt+1 − x‖2 + 2ηt〈zt, xt − x〉+ η 2 t
1−Lηt ‖zt‖ 2.
For simplicity, we state the main results under the assumption that the second moments E [ ∆2t ]
and E‖zt‖2 are uniformly bounded; more general guarantees that take into account weighted averages of the moments and allow for time-dependent learning rates follow from Lemma 3.1 as well.
Assumption 3.2 (Bounded second moments). There exist constants ∆, σ > 0 such that the following holds for all t ≥ 0.
(i) (Drift) The minimizer drift ∆t satisfies E [ ∆2t ] ≤ ∆2.
(ii) (Noise) The gradient noise zt satisfies E‖zt‖2 ≤ σ2.
The following theorem establishes an expected improvement guarantee for Algorithm 1, 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 1 with constant learning rate η ≤ 1/2L satisfy the bound:
E‖xt − x?t ‖2 . (1− µη)t‖x0 − x?0‖2︸ ︷︷ ︸ optimization + ησ2
µ︸︷︷︸ noise +
( ∆
µη )2 ︸ ︷︷ ︸
drift
.
Interplay of optimization, noise, and drift. Theorem 3.3 states that when using a constant learning rate, the error E‖xt − x?t ‖2 decays linearly in time t, until it reaches the “noise+drift” error ησ2/µ + (∆/µη)2. Notice that the “noise+drift” error cannot be made arbitrarily small. This is perfectly in line with intuition: a learning rate that is too small prevents the algorithm from catching up with x?t . We note that the individual error terms due to 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, we are led to define the following asymptotic tracking error of Algorithm 1 corresponding to E‖xt − x?t ‖2, together with the corresponding optimal step size:
E := min η∈(0,1/2L]
{ ησ2
µ +
( ∆
µη
)2} and η? := min { 1
2L ,
( 2∆2
µσ2
)1/3} .
Plugging η? into the definition of E , we see that Algorithm 1 exhibits qualitatively different behaviors in settings corresponding to high or low drift-to-noise ratio ∆/σ, explicitly given by
E  σ2 µL + ( L∆ µ )2 if ∆σ ≥ √ µ 16L3( ∆σ2
µ2
)2/3 otherwise.
Two regimes of variation are brought to light by the above computation: the high drift-to-noise regime ∆/σ ≥ √ µ/16L3, and the low drift-to-noise regime ∆/σ < √ µ/16L3. The high drift-to-noise regime is uninteresting from the viewpoint of stochastic optimization because the optimal learning rate is as large as in the deterministic setting, η? = 1/2L. In contrast, the low drift-to-noise regime is interesting because the optimal learning rate η? = (2∆2/µσ2)1/3 is smaller than 1/2L and exhibits a nontrivial scaling with the problem parameters.
Learning rate vs. rate of variation. A central question is to find a learning rate schedule that achieves a tracking error E‖xt − x?t ‖2 that is within a constant factor of E in the shortest possible time. The answer is clear in the high drift-to-noise regime ∆/σ ≥ √ µ/16L3. Indeed, in this case, Theorem 3.3 directly implies that Algorithm 1 with the constant learning rate η? = 1/2L will find a point xt satisfying E‖xt−x?t ‖2 . E in time t . (L/µ) log(‖x0−x?0‖2/E). Notice that the efficiency estimate is logarithmic in 1/E ; intuitively, the reason for the absence of a sublinear component is that the error due to the drift ∆ dominates the error due to the variance σ2 in the stochastic gradient.
The low drift-to-noise regime ∆/σ < √ µ/16L3 is more subtle. Namely, the simplest strategy is to
execute Algorithm 1 with the constant learning rate η? = (2∆2/µσ2)1/3. Then a direct application of Theorem 3.3 yields the estimate E‖xt − x?t ‖2 . E in time t . (σ2/µ2E) log(‖x0 − x?0‖2/E). This efficiency estimate can be significantly improved by gradually decaying the learning rate using a “step-decay schedule”, wherein the algorithm is implemented in epochs with the new learning rate chosen to be the midpoint between the current learning rate and η?. Such schedules are well known to improve efficiency in the static setting, as was discovered in [10, 11], and can be used here. The end result is the following theorem (see Theorem 5.5 of the Supplement for the precise statement).
Theorem 3.4 (Time to track in expectation, informal). Suppose that Assumption 3.2 holds. Then there is a learning rate schedule {ηt} such that Algorithm 1 produces a point xt satisfying
E‖xt − x?t ‖2 . E after time t . L
µ log
( ‖x0 − x?0‖2
E
) + σ2
µ2E .
Remarkably, the efficiency estimate in Theorem 3.4 looks identical to the efficiency estimate in the classical static setting [20], with E playing the role of the target accuracy ε. Theorems 3.3 and 3.4 provide useful baseline guarantees for the performance of Algorithm 1. Nonetheless, these guarantees
are all stated in terms of the expected tracking error E‖xt − x?t ‖2, and are therefore only meaningful if the entire algorithm can be repeated from scratch multiple times. There is no shortage of situations in 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.

heading: 3.2 High-probability guarantees
text: We next present high-probability guarantees on the tracking error ‖xt − x?t ‖2. 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 ∆, σ > 0 such that the following holds for all t ≥ 0.
(i) (Drift) The square drift ∆2t is sub-exponential conditioned on Ft with parameter ∆2: E [ exp(λ∆2t ) | Ft ] ≤ exp(λ∆2) for all 0 ≤ λ ≤ ∆−2.
(ii) (Noise) The noise zt is norm sub-Gaussian conditioned on Ft with parameter σ/2: P { ‖zt‖ ≥ τ | Ft } ≤ 2 exp(−2τ2/σ2) for all τ > 0.
Note that the first item of Assumption 3.5 is equivalent to asserting that the minimizer drift ∆t is sub-Gaussian conditioned on Ft. Clearly Assumption 3.5 implies Assumption 3.2 with the same constants ∆, σ. It is worthwhile to 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 [18, 31].
Remark 3.6 (Common settings for Assumption 3.5). Fix constants ∆, σ > 0. If ∆t is bounded by ∆, then clearly ∆2t is sub-exponential (conditioned on Ft) with parameter ∆2. Similarly, if ‖zt‖ is bounded by σ, then zt is norm sub-Gaussian (conditioned on Ft) with parameter σ/2 (by Markov’s inequality). Alternatively, if the increment x?t − x?t+1 is mean-zero sub-Gaussian conditioned on Ft with parameter ∆/ √ d, then x?t − x?t+1 is mean-zero norm sub-Gaussian conditioned on Ft with
parameter 2 √
2 ·∆ and hence ∆2t is sub-exponential conditioned on Ft with parameter c ·∆2 for some absolute constant c > 0. Similarly, if zt is sub-Gaussian conditioned on Ft with parameter σ/4 √ 2d, then zt is norm sub-Gaussian conditioned on Ft with parameter σ/2.
The following theorem shows that if Assumption 3.5 holds, then the expected bound on ‖xt − x?t ‖2 derived in Theorem 3.3 holds with high probability.
Theorem 3.7 (High-probability distance tracking). Suppose that Assumption 3.5 holds and let {xt} be the iterates produced by Algorithm 1 with constant learning rate η ≤ 1/2L. Then there is an absolute constant c > 0 such that for any specified t ∈ N and δ ∈ (0, 1), the estimate
‖xt − x?t ‖2 ≤ ( 1− µη2 )t‖x0 − x?0‖2 + c ( ησ2
µ +
( ∆
µη )2) log (e δ ) holds with probability at least 1− δ.
The proof of Theorem 3.7 employs a technique used in [13]. The main idea is to build a careful recursion for the moment generating function of ‖xt − x?t ‖2, leading to a 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.5 holds and that we are in the low drift-to-noise regime ∆/σ < √ µ/16L3. Then there is a learning rate schedule {ηt} such that for any specified δ ∈ (0, 1), Algorithm 1 produces a point xt satisfying
‖xt − x?t ‖2 . E log (e δ )
with probability at least 1−Kδ after time
t . L
µ log
( ‖x0 − x?0‖2
E
) + σ2
µ2E , where K . log2
( 1 L · ( σ2µ ∆2 )1/3) .

heading: 4 Tracking the minimal value
text: The results outlined so far have focused on tracking the minimizer x?t . In this section, we present results for tracking the minimal value ϕ?t . 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 ft in time t: rather than merely controlling the minimizer drift ∆t, we will assume control on the gradient drift
Gi,t := sup x ‖∇fi(x)−∇ft(x)‖.
Our strategy is to track the minimal value along a running average x̂t of the iterates xt produced by Algorithm 1, as defined in 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 a standard averaging technique to a one-step improvement along xt to obtain the desired progress along x̂t.
Algorithm 2 Averaged Online Proximal Stochastic Gradient PSG(x0, µ, {ηt}, T ) Input: initial x0 =: x̂0, strong convexity parameter µ, and step size sequence {ηt}Tt=0 ⊂ (0, 2µ−1) Step t = 0, . . . , T − 1:
Set gt = ∇̃ft(xt) Set xt+1 = proxηtrt(xt − ηtgt)
Set x̂t+1 = ( 1− µηt2−µηt ) x̂t + µηt 2−µηtxt+1
Return x̂T

heading: 4.1 Bounds in expectation
text: We begin with bounding the expected value E[ϕt(x̂t)−ϕ?t ]. Analogous to Assumption 3.2, we make the following assumption regarding drift and noise.
Assumption 4.1 (Bounded second moments). The regularizers rt ≡ r are identical for all times t and there exist constants ∆, σ > 0 such that the following properties hold for all 0 ≤ i < t:
(i) (Drift) The gradient drift Gi,t satisfies E [ G2i,t ] ≤ (µ∆|i− t|)2.
(ii) (Noise) The gradient noise zi satisfies E‖zi‖2 ≤ σ2 and E〈zi, x?t 〉 = 0.
These two assumptions are natural indeed. Taking into account Lemma 2.3, it is clear that Assumption 4.1 implies the earlier Assumption 3.2 with the same constants ∆, σ. The assumption on the drift intuitively asserts that gradient drift Gi,t can grow only linearly in time |i− t| (in expectation). In particular, returning to Example 2.2, suppose that the distribution map D(·) is γ-Lipschitz continuous in the Wasserstein-1 distance, the loss `(·, w) is C1 smooth for all w, and the gradient ∇`(x, ·) is β-Lipschitz continuous for all x. Then the Kantorovich-Rubinstein duality theorem directly implies E [ G2i,t ] ≤ (γβ)2E‖ui−ut‖2. Therefore, as long as the second moment E‖ui−ut‖2 scales quadratically in |i− t|, the desired drift assumption holds. The assumption on the noise requires a uniform bound on the second moment E‖zi‖2 and for the condition E〈zi, x?t 〉 = 0 to hold. The latter property confers a weak form of uncorrelatedness between the gradient noise zi and the future minimizer x?t , 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.
Theorem 4.2 (Expected function gap). Suppose that Assumption 4.1 holds, and let {x̂t} be the iterates produced by Algorithm 2 with constant learning rate η ≤ 1/2L. Then the following bound holds for all t ≥ 0:
E [ ϕt(x̂t)− ϕ?t ] . ( 1− µη2 )t( ϕ0(x0)− ϕ?0 )︸ ︷︷ ︸ optimization + ησ2︸︷︷︸ noise + ∆2
µη2︸︷︷︸ drift .
The “noise+drift” error term in Theorem 4.2 coincides with µ times the corresponding error term in Theorem 3.3, as expected due to µ-strong convexity. With Theorem 4.2 in hand, we are led to define the following asymptotic tracking error of Algorithm 2 corresponding to E[ϕt(x̂t)− ϕ?t ]:
G := µE = min η∈(0,1/2L]
{ ησ2 + ∆2
µη2
} .
The corresponding asymptotically optimal choice of η is again given by η?, and the dichotomy governed by the drift-to-noise ratio ∆/σ remains:
G  σ2 L + (L∆)2 µ if ∆ σ ≥ √ µ 16L3 µ ( ∆σ2
µ2
)2/3 otherwise.
In the high drift-to-noise regime ∆/σ ≥ √ µ/16L3, Theorem 4.2 directly implies that Algorithm 2 with the constant learning rate η? = 1/2L finds a point x̂t satisfying E[ϕt(x̂t) − ϕ?t ] . G in time t . (L/µ) log((ϕ0(x0) − ϕ?0)/G). In the low drift-to-noise regime ∆/σ < √ µ/16L3, another direct application of Theorem 4.2 shows that Algorithm 2 with the constant learning rate η? = (2∆2/µσ2)1/3 finds a point x̂t satisfying E[ϕt(x̂t)− ϕ?t ] . G in time t . (σ2/µG) log((ϕ0(x0)− ϕ?0)/G). As before, this efficiency estimate can be significantly improved by implementing a stepdecay 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 a learning rate schedule {ηt} such that Algorithm 2 produces a point x̂t satisfying
E[ϕt(x̂t)− ϕ?t ] . G after time t . L
µ log
( ϕ0(x0)− ϕ?0
G
) + σ2
µG .

heading: 4.2 High-probability guarantees
text: Our next result is an analogue of Theorem 4.2 that holds with high probability. Naturally, such a result should rely on light-tail assumptions on the gradient drift Gi,t and the norm of the gradient noise ‖zi‖. We state the guarantee under the assumption that Gi,t and ‖zi‖ are conditionally sub-Gaussian (Assumption 4.4). In particular, we require for the first time that the gradient noise zi is mean-zero conditioned on the σ-algebra
Fi,t := σ(Fi, x?t )
for all 0 ≤ i < t; the property E[zi | Fi,t] = 0 would follow from independence of the gradient noise zi and the future minimizer x?t and is reasonable in light of Examples 2.1 and 2.2.
Assumption 4.4 (Sub-Gaussian drift and noise). The regularizers rt ≡ r are identical for all times t and there exist constants ∆, σ > 0 such that the following properties hold for all 0 ≤ i < t.
(i) (Drift) The square gradient drift G2i,t is sub-exponential with parameter (µ∆|i− t|)2: E [ exp ( λG2i,t )] ≤ exp ( λ(µ∆|i− t|)2 ) for all 0 ≤ λ ≤ (µ∆|i− t|)−2.
(ii) (Noise) The gradient noise zi is mean-zero norm sub-Gaussian conditioned on Fi,t with parameter σ/2, i.e., E[zi | Fi,t] = 0 and
P { ‖zi‖ ≥ τ | Fi,t } ≤ 2 exp(−2τ2/σ2) for all τ ≥ 0.
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, in this case the objective takes the form f(x) = EA,b [ ∑n i=1 log(1 + exp〈ai, x〉)− 〈Ax, b〉] and drawing (A, b) yields the sample gradient ∇̃f(x) = AT (S(Ax) − b), where A ∈ Rn×d has rows a1, ..., an ∈ Rd 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∇f(x)− ∇̃f(x).
The following theorem shows that if Assumption 4.4 holds, then the expected bound on ϕt(x̂t)− ϕ?t 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 {x̂t} be the iterates produced by Algorithm 2 with constant learning rate η ≤ 1/2L. Then there is an absolute constant c > 0 such that for any specified t ∈ N and δ ∈ (0, 1), the estimate
ϕt(x̂t)− ϕ?t ≤ c (( 1− µη2 )t( ϕ0(x0)− ϕ?0 ) + ησ2 + ∆2
µη2 ) log (e δ ) holds with probability at least 1− δ.
The proof of Theorem 4.6 is based on combining the generalized Freedman inequality of [13] 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 ϕt(x̂t) − ϕ?t (as we do with ‖xt − x?t ‖2), we can control the tracking error ϕt(x̂t)− ϕ?t by leveraging control on the martingale ∑t−1 i=0〈zi, xi − x?t 〉ζt−1−i, where ζ = 1−µη/(2−µη). 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 precisely suited to bound such martingales with high probability.
With Theorem 4.6 in hand, we may implement a 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 ∆/σ < √ µ/16L3. Fix δ ∈ (0, 1). Then there is a learning rate schedule {ηt} such that Algorithm 2 produces a point x̂t satisfying
ϕt(x̂t)− ϕ?t . G log (e δ ) with probability at least 1−Kδ after time
t . L
µ log
( ϕ0(x0)− ϕ?0
G
) + σ2 µG log ( log (e δ )) , where K . log2 ( 1 L · ( σ2µ ∆2 )1/3) .

heading: 5 Conclusion
text: 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-probability guarantees extend recent results to the time-dependent setting.

heading: Acknowledgments
text: This work was supported by NSF CCF-2019844, NSF DMS-2023166, NSF DMS-1651851, CIFARLMB, and faculty research awards. Part of this work was done while Z. Harchaoui was visiting the Simons Institute for the Theory of Computing.

Review summaries:
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.

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.  The 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.   The 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.  The 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). The 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.   

This paper studies stochastic optimization under non-stationary drift. Losses are assumed strongly convex with Lipschitz gradients and unbounded domain. Finite-sample bounds are derived for the tracking errors $||x_t - x_t^*||$ and $\ell_t(x_t)-\min_{x^*}\ell_t(x^*)$ of SGD, both in-expectation and with high-probability.