Predictor-corrector algorithms for stochastic optimization under gradual distribution shift
Authors: Subha Maity
Debarghya Mukherjee
Moulinath Banerjee
Yuekai Sun
Venue: ICLR 2023 poster (2023)

Abstract: Time-varying stochastic optimization problems frequently arise in machine learning practice (e.g., gradual domain shift, object tracking, strategic classification). Often, the underlying process that drives the distribution shift is continuous in nature. We exploit this underlying continuity by developing predictor-corrector algorithms for time-varying stochastic optimization that anticipates changes in the underlying data generating process through a predictor-corrector term in the update rule.  The key challenge is the estimation of the predictor-corrector term; a naive approach based on sample-average approximation may lead to non-convergence. We develop a general moving-average based method to estimate the predictor-corrector term and provide error bounds for the iterates, both in presence of pure and noisy access to the queries from the relevant derivatives of the loss function. Furthermore, we show (theoretically and empirically in several examples) that our method outperforms non-predictor corrector methods that do not anticipate changes in the data generating process.

Published as a conference paper at ICLR 2023
PREDICTOR-CORRECTOR ALGORITHMS FOR STOCHAS- TIC OPTIMIZATION UNDER GRADUAL DISTRIBUTION
SHIFT
Subha Maity
Debarghya Mukherjee Department of Operations Research Financial Engineering, Princeton University,
Moulinath Banerjee
Department of Statistics, University of Michigan, smaityêune yuum ch. edu
Department of Statistics,
University of Michigan, moul umumi ch edu
dm8 3 4 1 @err deppincetoon.e..
Yuekai Sun
Department of Statistics, University of Michigan, yuekai @ umi ch. edu
ABSTRACT
Time-varying stochastic optimization problems frequently arise machine learn- ing practice (e.g. gradual domain shift, object tracking, strategic classification). Often, the underlying process that drives the distribution shift is continuous in na- ture. We exploit this underlying continuity by developing predictor-corrector algo- rithms for time-varying stochastic optimization that anticipates changes in the un- derlying data generating process through predictor-corrector term the update rule. The key challenge is the estimation of the predictor-corrector term; a naive approach based on sample-average approximation may lead to non-convergence. We develop general moving-average based method to estimate the predictor- corrector term and provide eтror bounds for the iterates, both in presence of pure and noisy access to the queries from the relevant derivatives of the loss function. Furthermore, we show (theoretically and empirically in several examples) that method outperforms preddcccctoorr corrector methods that do not anticipate changes in the data generating process.
INTRODUCTION
Stochastic optimization is basic problem in modern machine learning (ML) theory and practice. Although there is a voluminous literature on stochastic optimization (Agarwal et al. 2014 Moulines Bach, 2011 BBttoou| 2003 2012] Bottou & Bousquet (007)), most prior works consider a time- invariant stochastic optimization problem in which the data generating distribution is not changing over time. However, there is an abundance of real examples in which the underlying optimization problem is time-varying which can be broadly divided into two categories: the first kind arises due to exogeneous variation in the data generating process. A concrete example is the object tracking problem in which an observer observes (noisy) signals regarding the position of moving object, and the goal is inferring the trajectory of the object. The second kind time-varying optimization problem arises due to endogeneous variation in the data generating process. Examples here include strategic classification (Dong et al.) 2018 Hardt et al. 2016) and performative prediction (Perdomo al. 2020 Mendler-Dünner
2020; Brown et al. 2022). Although there few recent papers on time-varying stochastic optimization (e.g., Cutler et al. (202T); NNohooff & Müller (2020): Dixit al. (209 2018), ) they model the temporal drift discrete, precluding them from exploiting the smoothness in the drift. This leads to worse asymptotic tracking error, depending on the magnitude
of the temporal drift of the optimal solution, (e.g. see PPokkov (2005). Zavlanos et al. (2012) Zhang
et al. (2009). Ling & Ribeiro (2033) and references therein).
Coodes: http::/:/ht....mmmiiiiymmmocoooh

---

Published as a conference paper at ICLR 2023
In this paper, focus time- varying stochastic optimization problems in which the temporal drift is driven by a continuous time process. We leverage the smoothness of the temporal drift to develop predictor-corrector (PC) methods for stochastic optimization that anticipates future changes in the data generating process to improve the asymptotic tracking error (ATE) (see Definition 2.T). The main benefit of such methods is smaller tracking error (compared other stochastic optimization al- gorithms that does not leverage smoothness of the temporal drift), A primary challenge in stochastic time-varying optimization is properly accounting for the temporal drift through PC term in the up- date rule. The noise in the stochastic setting makes naive estimates of the PC term unstable, and may lead to non-convergence. One of our main contributions developing a general way of estimating the PC term.
We complement the methodological contributions with theoretical results that show PC stochas- tic optimization algorithms inherit the benefits of their non-stochastic counterparts for time-varying problems. particular, we show that PC stochastic optimization algorithms have smaller asymptotic tracking error (ATE) compared to their non-PC counterparts. We also demonstrate the superiority of PC algorithms empirically in a time-narying linear regression and target tracking applications. The rest of the paper is organized as follows: In Sections and B] we present the algorithm and high- light the difference between predictor-correctt like simple gradient descent. We further present theories regarding the bound on ATE of the algo- rithms of both kinds. In Section 4 we present three concrete instances of time-varying stochastic optimization problems driven by underlying gradual distributions shifts and derive the details of PC algorithms for these problems. Section SatiionSSccone ccnncludes.
based algorithm and time non -daatiieive algorithms
2 FRAMEWORK AND ALGORITHM
In a typical learning problem, we have n samples XI....,X, ~ P and based on the data, we estimate some parametric (or non-parametric) functional of the underlying distribution 0" v(P) by minimizing some loss function E(0, X). A standard assumption for consistent estimation of 0* is that R() & [XE 0)] is uniquely minimized at 6", In a time varying framework, we assume that the data generating distribution P = P; changes with time and does the parameter of interest 0; v P:) along with the (time-varying) risk function R(,,t) Ep, [e(X,)). 0)]
As a concrete example, consider the object tracking problem studied in Patra et al. (2020): suppose have installed sensors positions si...., F,, (which remain fixed over time) and let 07 be the location of the target object at time 1. At each time, we get some noisy feedback from the sensors regarding the position of the target, i.e.
Vi.t = ||=; 1/ + ett for S n,
where é 's are iid (over and f) with mean zero and variance 72. Denote by y: E R." to be the vector of observations from sensors at time t. A natural approach to estimate 0ī is to minimize squared error loss E(y,, 0) = En (Vi. - || - 013)), which yields the risk function
R(0, t) = Σm_ E( |2; -01 - nr² + " 0,11 ||2; - -8113)2
From the risk function, it is immediate that under very mild assumptions on II...., Fn (i.e. they are in general position, as discussed in Appendix A. we have
#* (t) = arg R(0, t), t 0.
(2.1)
We will use the notations (t) and 0j interchangeably denote the same thing. From the above formulation, it is immediate that we are merely observing one sample/incident at each time point. Therefore if Or behaves erratically over time, there is no hope to learn the evolution pattern from the data. Therefore, it is imperative to assume some smoothness on the target function 07 Our proposed method exploits the smoothness of 0 to improve its estimation over time.
We now formulate the problem: continuously with time f. As statisticians, we query the model at discrete time steps (i.e. say at time where h is the time step which controls the frequency of query) and observe n samples (Xahsven from the distribution at that time. As a consequence, we have a sequential batch of data using which we aim to estimate 0h i.e. the parameters at the time of query. Note that estimate the parameter at time one may use all previous data points. We evaluate the quality of our estimator using the asymptotic tracking error (ATF) defined below.
we assume that the underlying distribution function (Pt} changes
2

---

Published as a conference paper at ICLR 2023
Definition 2.1 (Asymptotic tracking error (ATE)). Let the true dynamic parameter {0), t 2 0} be sequentially estimated {0xh: NJ over the time grid {kh k N), where h > 0 is the time step. Then the asymptotic tracking error is defined as
ATE(6) = lim sunsuup
|00R
As mentioned in the Introduction, we here compare performance of time-adjusted (PC) gradi- ent descent method to time-unadjusted (GD) one. As will be evident, both the methods require evaluation of certain derivatives the risk function.
To motivate the predictor-corrector (PC) algorithm, we start by deriving the prediction correction term when the optimizer has access to the exact gradients of the (time-varying) cost function. The optimality of 87 implics
g(t) = VoR t) = 0 for all t.
(2.2)
Thus g = O; i.e.
V Vee t) + Ve ( =
(2.3)
where 0z is the temporal drift of the optimal solution 8. We see that 07 satisfies the ODE:
0r = R () (V=
(2.4)
We interpret the right side of this ODE a prediction of the change in 0z This suggests modifying the update rule of stochastic optimization algorithms to account for the predicted change in 07. This leads to the update rule
Q(x+1Ja = 6RA V R kh) 1 V R R(Oan kh)] -V Ve kh),
where 77 > 0 is a learning rate, h is (time) step, and V,R(0, t), R(,,( R(, estimates of Vg t), (eo t). (o, t) respectively. We summarize the stochastic PC
algorithm in [lgorithm
Algorithm Stochastic predictor-correctt based method
Require: step size > 0, learning rate > O, estimated gradients VoR kh), Hessians R.,, kh) and time derivative of the gradient R( kh) for ls E N
1: Initialize 6g at some value.
2: for do
3: Update 0(1+1)h ORn --- RO kh)
Vo kh)
4: end for
To motivate the benefit of accounting for the predicted change in 02 we present here brief com- parison of the tracking error of the PC algorithm with simple stochastic gradient descent without the correction term. For simplicity of exposition, we study the tracking error of these two algorithms in the non-stochastic setting. We begin by showing a lower bound on the tracking error of gradi- descent. We suspect this result known experts, but it does not appear (to the best of our knowledge) in the literature.
Theorem 2.2 (Lower bound). There exists R(0, t) that satisfies Assumption 3.1 such that the gradient descent algorithm with time step size h > O and learning rate n7 > 0 satisfies the following: there exists c such that
h 17
lim inf |kkh 8-+00
0inll2
As shall in the subsequent section (see Theorem 3.3 the tracking error of the PC algorithm in the stochascchhic setting is O L"*² We restate this special case of Theorem 3.3 here for the reader's convenience.
My
3.3 Assume that 3.1 and 3.2 holds and that RR(0 () is twice differentiable in both co-ordinates. Then with access the true gradients, the sequence of estimates in Algorithm I with step size h > 0 and learning rate satisfies:
Corollary 2.3. (Non-stochastic version of Theorem
lim sum |p0h 0% Mn+KM"
L"A²
where M' supa, (V. -o R(0, ooo
M = supreo R t)]l and I" =
max [1(((1)] are finite.
3

---

Published as a conference paper at ICLR 2023
To compare the rates for the PC algorithm and gradient descent, we set learning rate such that h/n - 0 as h - 0. We see from Theorem 2.2 that the ATE for gradient descent ATE cannot con- verge faster than h/y By comparison, the ATE for PC algorithm in the non-stochastic setting (see L"R² My as long as h/n + 0), which a faster rate than h/m. Hence, we conclude that the ATE for predictor-corrector update con- verges at a faster rate than the ATE for gradient descent update. A high-level reasoning for such a distinction is the following: the gradient descent method does not consider or calibrate for the under- lying smoothness in 8* (t) while performing the time updates, whereas predictor-correet corrector calibrates for the smoothness in the time update by adjusting the term Vo
Theorem 2.3 converges to zero at rate 1² /n (since it holds MothM x
Vor ().
One of the main challenge in implementing the stochastic PC algorithm is obtain estimates of VoR t), (o, t). Ro t):
1. Estimation of gradient: VeR(0, t) also appears in the SGD update rule; it is typically estimated with sample average approximation.
2. Estimation of PC term: R(0, t). R(,,( t) are quantities that arise due to the presence of the PC term in the stochastic PC update rule. Although it is possible to construct unbiased sample average approximations of them individually, obtaining an unbiased estimate of the overall PC term is generally not possible due to the presence of non-linearity: the PC term is a product of the inverse of the hessian matrix and the cross derivative with respect the parameter and time. Fortunately, the stochastic PC algorithm is robust against biases in the estimate of the PC term. That said, naively estimating the PC term with sample average approximation can lead to non-convergence of the stochastic PC algorithm (see Remark [3.5] for details). In section 4 we present two ways of /vvaluuatgg Vee ((0,t) t), V ((,tt that ensure the stochastic PC algorithm converges.
In the next section, we elucidate how errors in the estimates of VoR(0, t), (o,R(0, (o. affect the asymptotic tracking error of the stochastic PC algorithm.
3 THEORETICAL PROPERTIES OF THE STOCHASTIC PC ALGORITHM
We begin by stating our assumptions on the problem. We assume that the risk function is strongly convex with respect to f. This assumption implies that 0* is uniquely identified at time t and is crucial in studying the convergence of ATE.
Assumption 3.1. R(,,t) t) is j-strongly convex with respect to 0 iee. for any 0,, 02 and t 2 0 it holds:
R(02,1) 2 R(01, (02-0,) (0)(0 (. + 1 11.
We now assume that as a function of t, (t) smooth, which is naturally satisfied in numerous examples including dynamic least squares recovery, object tracking, etc..
Assumption 3.2. The function Ar E C2. ([0, oo)), i.e. 0* twice continuously differentiable with respect to time and its double derivative is uniformly bounded over time.
As will be seen in the subsequent theorems. the bounds on the ATE of these stochastic algorithms depend on the error in the estimation of the pertinent gradients, which are defined as follows:
& Ro, 8) - to
denotes the estimation error of the gradient and
Se = R(0,, (x) V (2) - V V ( t4)
represents the error in the adjustment term for the temporal drift. We use og (resp. σx)) to denote an upper bound on sup, [[] (resp. sup, [[]]<=I]). These bounds may may not be a function of ht depending on the application. Note that we do not assume the estimates the gradients are unbiased. Below
present our main theorems regarding the bounds on the ATE of stochastic gradient descent and Indin in terms of ag, Cç, learning rate 77 and stepsize h:
Theorem 3.3 (Stochastic predictor-correcto method). The update sequence of stochastic predictor- corrector method presented in Algorithm yields the follows bound on ATE:
lim sup Elllenh 0hall]
1995 hōç-
7M4MM
4

---

Published as a conference paper at ICLR 2023
for any small n O. When og and oc are independent of h then choice of 1) h implies that ATE of stochastic predictor-corrector method is at-most of the order of h.
Note that we don not require zero mean for the noise; we merely require them to have finite second moment. This is slightly more general that the usual stochastic optimization setting in which the noise is assumed to have mean zero. That said, most of the applications that we have in mind, the noise comes from approximation of expectations by sample means, so the noise will be mean zero.
To see the benefits of the PC algorithm in the stochastic setting, we compare the ATE of the PC algorithm with that of stochastic approximation. Recall the stochastic gradient descent update rule:
((++I)A uRn - n R(Oan. kh).
(3.1)
for some estimate of gradient. Its ATE known (Cutler et al. 2021). but we restate it here to facilitate comparison:
Theorem 3.4 (Stochastic gradient descent, Cutler et al. (2021) ) The update sequence of stochastic
gradient method satisfies:
lim sumpup--oo [B[ [[ 0% II] S LA + nog
for any small n > 0. Minimizing the right hand side with respect n yields:
lim supk I[[ 0r 11] S V L
Therefore, when dg does not depend on h, the rate is O(
If we assume the error variances are independent of h. then simple stochastic gradient descent yields a bound of the order /ha on the ATE, whereas, the time-adjusted predictor-corretta based method yields bound of the order of h, implying the superiority of the later for small stepsize. The superi- ority continues to hold even when the variances depend on h, as will be evident in the applications in the subsequent section.
Remark 3.5 (Naive estimation of PC term fails). In practice it is straightforward obtain esti- mates of (,R(O, t) (e.g. sample average approximation), but it is less straightforward to estimate the cross-derivative term R. t). naive application of first-ordrr finite differences esti- mating the drrsivverv term leads to poor tracking performance because this estimate of the drrss-derivttive term leads to a og term that O(h-)) Indeed, we have
Vo kh) VoR(O, VoR(O, (k (k-1)h)
h VoR(O, kh) VoR(O, (Is 1)h) Ekh E(R- 13th
h
h
As long as R((,t) is smooth with respect to t, the first term is R(O,t) + O(h). But the second term is generally O(h-1), e.g., e. we assume that the errors over time are independent. Plugging this into the bound on the tracking error in Theorem 3.3 we see that the term that includes og no longer depends h, leading obtain more accurate estimates of R(, 1) to avoid this pitfall (e.g., for least square recovery problem in $4.1see see Equation 4.4 and Lemma for it's estimation and error analysis).
vacuous O(1) bound. In Section 4 we use moving average schemes to
APPLICATIONS
In this section, we present three concrete time-varying optimization problems; all are characterized a gradual underlying distribution shift. This allows to leverage the predictor-corrector (PC) method to improve tracking of the optimal trajectory. some applications (e.g. the strategic classification example), there is model for the distribution shift, so it is possible to evaluate the PC term exactly. In other applications, there is no such model, so it is necessary to approximate the PC term. We use generie mhite-difference approach in $4.1 and $4.3 to approximate the PC term. This approach is generally applicable, but it may not be optimal in applications in which the underlying distribution shift exhibits higher orders of smoothness.
5

---

Published as a conference paper at ICLR 2023
4.1 LEAST SQUARES RECOVERY WITH FIXED DESIGN MATRIX
We first demonstrate the performance of the predictor-correcton method and compare it with gradient descent method in a linear regression model. We observe Ykhh - [Ykng]]== at time kh for & E N and some fixed stepsize h, where the observations are modeled as: Yr X0; + -, Here X E R is a fixed time-ing iivariinaiaant design matrix and the co-ordinates of E are i.i.d with mean and variance T². The parameter of interest here is the function 0* [0. oc) + Rd. We consider a low dimensional scenario (i.e. < n) and assume that the columns of are in general position, i.e. X is invertible. This immediately implies the following:
Lemma 4.1. For any E [0, oc). O% is the unique solution of the least square problem:
0j = arg minnennnn(CC () = arg mingeRs 1 [lly, [
2n
where R is the risk function and the expectation is taken with respect the distribution of
The proof of Lemma can be found in Appendix [ We now compare the performance of stochastic gradient descent method (3.1) and PC method (Algorithm[]) D). The gradient of the risk function (with respect to) 0 is: ((0, E) X (X0- XOT). We propose moving average based technique to estimate the gradient of the risk function, i.e. for any time we define:
(oR(0,1) X X0 - EnD osyr-sh): & = V (O)(0,1).
(4.1)
The optimal choice of the moving window length m and {a.)r-o' Im= depends on careful analysis of bias-variance trade-off of the estimation error &s. First, note that & can be decomposed into two terms as follows:
& = X x (0r - Ei a;0% -
ETT a, Er AA
We can expand the bias term A via a two step Taylor expansion:
0: -io -m a,0i = 02 { Em as} hō* (t) ia; + 42t "a,0" (E:)
for some &, E it, 8). The following lemma presents an optimal scheme for choosing {m; 0ie i 0, O,..., m - 1}:
Lemma 4.2 (Gradient estimate). For any fixed m, choosing the weights {az} as:
(oo. am am-1) 1) E arg min Em= of Em=ol = 1, and Em= ia; = 0, E R
(4.2)
we obtain the following:
1. || = ab x O(m+))), where og = max120
x
Ø. (1)
2. B| = b3 x (m where 1ig = 72 (TR
x x x
}.
n
Therefore, taking m Oh 1/5 (0001//(an//// (bo 2/33) we have:
E|||@/1a]+ < || + [E[||B|]]
O(aom2 12) + (0mmm0000000000
(4.3)
The proof of this Lemma is deferred to the Appendix A. It established in the proof that the optimal
weights are: as; = 2(2m - 1- - 3 {m + 1)]. Using the error bound of Lemma 4.2 in Theorem 3.4 yields for small 7, ATE bounded by ((h/n) + (1ph2/5). The right hand minimized by taking 77 = 3/110 which yields the order for asymptotic tracking error (h7/10).
For prediction-correcto based method (Alg (Algorithm[] IT we additionally need to estimate the Hessian and the time derivative of the gradient. The Hessian is constant (X X/n) and known (as we assume to know X). To estimate R( = -X X X/nJ07, method, f.e. set:
we again resort to a moving average based
(o.R(0,1)
- D B
(4.4)

---

Published as a conference paper at ICLR 2023
QD
GD
Figure 1: The two left-most figures show the performance of gradient descent and the PC method for lime-varying linear regression. The left-most figure presents tracking error of GD and the PC methods for various choices of h on the time interval E [0, 3]. The second figure from the left one compares the performance for a fixed 3 3 and different the methods vary with h. The two right-most figures show the performance of gradient descent and the PC method for object tracking. The second figure from the right shows the tracking error of the object tracking model for GD and the PC method for different choices of h. The Yaxis represents the tracking error and -axxs represents the time interval E (0,3).
illustrate how the performance of
for some choice of p and the weights {8,}5=ō- where the weights and the size of the window is obtained from a birs-variance trade-off:
St = x -1
V Bc R ( - (o,R(0,1))
= 3,0 + - xxxX) - 1xT 1 & C.+D
The following lemma presents the optimal choice of the weights, window length and consequently an error bound:
Lemma 4.3. (Estimate of time derivative) For any p. if we choose the weights 3, 's as:
(Bo..... 3p-1) E arg min Ei bi EnT b; O, and E ib, - 4. E R
(4.5)
we have the following bounds on the error:
1. ||CI13 max ||0- (t) 3 O & x
[|] = 7 [TR [TR[(TXXX] X/n) (I/n)_I/nn>>>> O(h 3h--2p-0 3) a di 3p-33--)
Setting p = (do/co) 1/4h //41//////////////////)) 3/4 we have:
E [[[[ < ||C||2 2 (B|1 O(cohp) + Odgh "p /
(4.6)
The 3, in the above lemma takes the value 6(p plp--1h elaborated in the proof of the Lemma (see 1/4))4) Furthermore,
Appendix A). From the above lemma have 0ę max; Eill< we have established in the analysis of gradient descent method that the order of the error of the gradient estimation is oe = O(h//5) (Lemma 4.2). Using these rates Theorem 3.3 we conclude that ceddictor-corretto method with step size r7 ATE is the order O(h2/ (1 + h
(1hh2/5) + (h5/4). The bound is minimized at = 4/5 and consequently, the order of the tracking error (1,/55). Therefore, rredictor-corracto method yields faster rate (in terms of the step-size h) in comparison the gradient based method.
Simulation studies: We compare the tracking performance of the gradient descent based and the predictor-corrector based method for the regression model via simulation. For simulation purpose, set d 2, = 40. The values of {X,) == generated independently from (00 .2) and remain fixed over time. The true parameter taken to be 07 = (sin(2nt), cos(2 and at time t, coststt
the observation y; E R is generated y. X0; c, where e, AO0 0.5I,). Runtime analysis for the gradient descent based and the credictor-correctorr based methods can be found in Figure 2 in Appendix C
The tracking performance of the methods over a finite time interval (t E (0,3)) and the effect of on the limiting enror (i.e. tracking error for some large f) are presented in Figure T In the left plot

---

Published as a conference paper at ICLR 2023
of Figure 1 observe that the predietor-corrector based method (denoted by PC) outperforms the gradient-descent based method (denoted by GD) in terms of the tracking error for all moderately large (here, t 1) for all choices of h {10 10 10 100000+1000 10 101--.00. As illustrated in theory, the rate of convergence of limiting error of predictor-corrector based method decreases faster in compared to the gradient descent based method. The right side of Figure Maaareeesttabihhhe this phenom-
ena through comparing the performances at 3 for several choices of h. As |0, - f4 a random quantity, error bars (over 10 Monte- Carlo iterations) are provided to quantify the variability of the tracking error, which turns out to be relatively small compared to the mean difference of the tracking enror of the methods.
4.2 STRATEGIC CLASSIFICATION
In strategic classification, samples correspond to agents who change their features strategically to affect the output of the ML model (e.g. scammers modifying their scam to skirt scam detector). To keep things simple, we assume the ML model is a binary classifier, and the positive output is advantageous for the agents. Following HHardt al. (2016), we assume the agents are maximizing utility, and they have full information regarding the classifier. Thus an agent with features x changes their features by solving the (expected) utility maximization problem
(x) - arg (x(x") c(z,=')
(4.7)
where u. > 0 is the utility from a positive output, f(x) is the predicted probability of having positive output for x from an ML model, u4 ((x) is the expected utility at x, and c(x,,2²) > encodes the cost of changing features from x to x'.
Let P1 be the probability density function (pdf) of the positive class conditional time & and se be the ML model deployed at time f. The agents respond strategically to fú; i.e. an agent with feature x changes their features to x (x) (their label remains unchanged). The resulting change in the class conditional satisfies the continuity equation:
O.p + V (up1)= = 0,
3za] is the spatial gradient operator and is the vector field v(x) - x (x) a. Similarly, the pdf of the negative class conditional also satisfies the continuity equation.
where -
10z,
This change in the distribution of agent features leads to a time-varying optimization problem:
((t) E arg f t) _ Ix ((fo(z), ()dP) + (1 x) fx ((fo()),))dP(())
where π A F|Y 1} is the faction of the positive class and is a loss function for the classification task. Interchanging limits freely, we see that it is possible estimate (ef(0,t) and (0, empirically:
(o,(0,)) = Sx Vol(fo()), 1)dP)))) + + (1-1) *) Jx vol(f((s),)))P((()) Vee -0, V)((f((#), 1)dP (1- (j((((
Similarly, it is possible to estimate Va.( () empirically:
(o, = Jx 1)) (z, + (1 fx ((f(()), 0)0,po(z t)dz
= =- f- ( -x 1) (1 (z) ())x)))) l)dx. v(z)po(
(1- Sx {fo(()) 0,V (u(x)po(z, t)
where we appealed to the continuity equation in the second step and Green's 's identities in the third step. Unlike the other two applications this section, possible to compute the PC term exactly (without resorting to finiteddifference approximation) here.
4.3 OBJECT TRACKING
Our third application object tracking problem proposed and analyzed by Patra et al. (2020). As- sume we have sensors placed the position {X in 2dd and 6* (t) denotes position of the object (that we aim to track) at t. At any given point, we observe a noisy version of some monotone function of distance of the object from the sensors, i.e. observe:
YE,+ = s([X, 0:l12) + ELet A1 visign.
8

---

Published as a conference paper at ICLR 2023
In this example, assume know f. The case of unknown f is more complicated and beyond the scope of the paper. The risk function for estimating ff under quadratic loss function is:
(] =
- Σ 2n 1=1
- - 02))) - ((xx
= 2 2n Σ (f(1x, - 0113) - f(llx; - 01 0))
0²
Note that the risk function here is not strongly convex (so it does not satisfy the assumptions of Theorem (.3). but we shall see, the PC algorithm nevertheless outperforms standard first-order methods. The gradient and the Hessian, that are required for GD and PC methods, can be easily
estimated as using sample averages (exact expressions are presented in the Appendix B The time
derivative of the gradient is:
Vo,,((0,1)
E.= ['IIx; 011²)(0 x.) x /(IX; -0111²)
To estimate d 111 - -3] we again resort to the moving average procedure:
0 0;113)= - 3,Y,,-jh
where p. (8,}i=1 are chosen carefully to balance the bias variance trade-off. For notational simplic- ity we drop the index and define g(l) X[] l1). From the relation Y,, g(() + ci,t and Assumption 3.2. we have:
Σ5
Ej 3, (g(1) jhg'(1) (1) + 222 g" EE 3,c,,195
Now if the sequence 13,30-1 satisfies Σ; 35 = 0 and E, jB} = -(11h) then we have:
E By gt( =2, + Ej=o ByEar-5h-
The variance of the error term is of E, 8/. Therefore we will choose (3,) and by minimizing Σ, By subject the above constraints. Similar calculation as of Example (Lemma 4.3) yields 61p-1-2/)
p = (3/4) and {3,35-0 is B3 p
Simulation study We consider
0.8, 1)2 C [_1, grid. The moving object takes the path 0 = (sinn(2t)) cos (2Tt)) and we let f(x) = We generate noisy observations of the object as yer = |X - 0:1 1 + 65t where 6st NO0 1/4). Run- time analysis for the two methods can be found in Figure 2 in Appendix C Figure (third and forth plots from left) presents the tracking error of both the methods (gradient descent based method (resp, predictor-correcton based method) is represented
11 sensors placed at (-1.
GD (resp. PC)) for four choices of h e {10-², 10-3 10-4 10 50- The superiority of the performance of the PC method for all t 2 1 and for various choices of h is evident from the third picture from the left-side of Figure picture, we compare the limiting performance of both the methods (here we take the error at t to be the limiting error) for several choices of h. The superiority of the performance of PC corroborates our theoretical finding that the tracking error for PC converges faster in terms of h compared to the GD. We also show error bars (over 10 Monte-Carlo iterations) of the random tracking error [|d; -0; 3 on the right picture, which indicates that the variability is relatively small compared the difference of the mean tracking error of the methods.
In the last
CONCLUSION
We developed predictor corrector algorithms for stochastic time-varying optimization. These algo- rithms leverage smoothness in the temporal drift to anticipate changes to the optimal solution. We showed that these algorithms have smaller asymptotic tracking errors than their non-predictor cor- rector counterparts and demonstrated their efficacy in three applications. Although we focused on first-order algorithms in this paper, the predictor corrector term in the update rules our PC algo- rithms can be incorporated into the update rules of other algorithms (e.g. Newton-type methods). We hope that the benefits of first-order PC algorithms motivates others to study PC versions of other algorithms.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 2027737 and 2113373.
REFERENCES
Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, and John Langford. A reliable effective terascale linear learning system. The Journal of Machine Learning Research, 15()):1111-133, 2014.
Léon Bottou. Stochastic learning. In Summer School on Machine Learning, pp. 146-168. Springer, 2003.
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp. 421- 436. Springer, 2012.
Léon Bottou and Olivier Bousquet. The tradeoff's of large scale learning. Advances neural information processing systems, 20, 2007.
Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in stateful world. In International Conference on Artificial Intelligence and Statistics, pp. 6045-6061. PMLR, 2022.
Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Stochastic optimization under time drift: Iterate averaging. step-decay schedules, and high probability guarantees. In Thirty-Fifih Confer- ence on Neural Information Processing Systems, May 2021.
Rishabh Dixit, Amrit Singh Bedi, Ruchi Tripathi, and Ketan Rajawat. Time varying optimization via inexact proximal online gradient descent. In 2018 52nd Asilomar Conference on Signals, Systems, and Computers, pp. 759-763. IEEE, 2018.
Rishabh Dixit, Amrit Singh Bedi, Ruchi Tripathi, and Ketan Rajawat. Online learning with inexact proximal online gradient descent algorithms. IEEE Transactions Signal Processing, 67(5): 1338-1352, 2019.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strate- gic classification from revealed preferences. Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55-70, 2018
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifica- tion. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 112-122, 2016.
Qing Ling and Alejandro Ribeiro. Decentralized dynamic optimization through the alternating di- rection method of multipliers. IEEE Transuctions on Signal Processing, 62(5):1185-1199) 2013.
Celestine Mendler-Dünner, Juan Perdomo, Tijana Zmncc, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33:4929-4939, 2020.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
Marko Nonhoff and Mauthias A Müller. Online gradient descent for linear dynamical systems.
IFAC- PPAC--apersOOLLin, 53(2):945-99) 952, 2020.
Rohit K Patra, Moulinath Banerjee, and George Michailidis. A serimearamttric model for target localization in distributed systems. arXiv preprint arXiv:20/2.02022, 2020.
Juan C. Perdomo. Tijana Zmic, Celestine Mendler-Dünner, and Moritz Hardt. Performative Predic-
tion. arXiv:2002.06673 [es, stat], June 2020.
A Yu Popkov. Gradient methods for nonstationary unconstrained optimization problems. Automa- fion and Remote Control, 66(6):883-6)) 2005.
10

---

Published as a conference paper at ICLR 2023
Michael M Zavlanos, Alejandro Ribeiro, and George J Pappas. Network integrity in mobile robotic networks. IEEE Transactions on Automatic Control, 58(1):3-18, 2012.
Yunong Zhang, Ke Chen, and Hong-Zhou Tan. Performance analysis of gradient neural network exploited for online time-varying matrix inversion. IEEE Transactions on Automatic Control, 54 (8):1940-1945, 2009.


Reviews:
[{"review_id": "vyjeFnihYS", "reviewer": "Reviewer_iKWJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_paper": "The paper considers the problem of tracking the sequence of best parameters of quadratic functions, where the best parameters changes in a stochastic way. The paper proposes an algorithm called PC and proves its convergence guarantees in terms of ATE. Then, some application problems are introduced, and the PC algorithm is applied. Experimental results show the advantages of PC against the SGD.", "summary_of_the_review": "The theoretical and empirical results seem non-trivial, but I have some concerns about details of theoretical results.", "strength_and_weaknesses": "Strength\n- simple update rule with a non-trivial theoretical guarantee\n- promising experimental results\n\n\nWeakness\n- some technical issues are not clear (see below)\n\nAs summarized above, the claimed technical contributions are non-trivial and solid. However, I have several concerns on technical details, which could affect the evaluations of the theoretical results. \n\n* The sample complexity or success probability are not discussed. \nThe problem setting is stochastic and the goal is to minimize ATE, i.e., the distance between the proposed and true parameters. To minimize this, the statistician has only access to finite samples from the distributions, which causes estimation errors. So, I am strongly wondering how the authors obtain the claimed results while avoiding these sampling/estimation issues. The paper needs some explanation on this matter to justify the results. Or some implicit assumptions exist.\n\nSo far, I do not have an intuition that the claimed results are correct. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ikXlkiHurqd", "reviewer": "Reviewer_YXuw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_paper": "This paper presents a method to incorporate some knowledge about gradual distribution shifts during online gradient descent. The key idea is to add a predictor-corrector term to the gradient (i.e., adding an approximation of the time derivative), which tries to take into account the fact that the expected error changes over time with the current parameters. \n", "summary_of_the_review": "This paper may be interesting to some, but given the language on handling distribution shift and offering improvements to object tracking, I expected something more practical, rather than assumptions/lemmas/theorems and toy experiments in simulated data. ", "strength_and_weaknesses": "The paper is somewhat interesting, and appears to be quite thorough, but relatively unconvincing to me, since it is mostly theoretical, and the only experiments are in toy synthetic tasks/settings. For me this is particularly surprising because so much of the text talks about very practical issues, like distribution shift, and object tracking. In fact the paper is not doing any normal kind of tracking, and instead considers a simple synthetic problem where \"sensors\" return estimates of the target's \"distance\", with some zero-mean variance. Maybe this paper will be convincing and helpful to some, but in my case I don't know what to do with it.  Since the paper is out of my domain I certainly won't fight to reject it, but I hope my suggestions on language will be somewhat helpful. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hBSf_7SqtV", "reviewer": "Reviewer_SvER", "summary": "", "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": "", "summary_of_the_paper": "This paper considers the problem of tracking a drifting optimization target under the assumption that the loss function is a smooth function of both the optimization parameter and time. The key insight is to compute the derivative of the minimizer with respect to time by differentiating the loss function with respect to time. Gradient descent is then augmented with an estimate of this derivative in order to more closely track the target.\n\nHigh level calculations show that with sufficiently good estimates, this method will track the target with a better dependence on the time interval between updates ($h\\rightarrow h^2$ where $h$ is the time interval).\n\nIn any given example, one then needs to build good estimates of the derivative of the target with respect to time. The authors explore several specific examples in which this can be obtained.\n", "summary_of_the_review": "The paper initiates a study of drifting optimization utilizing temporal structure in the loss function. Results are presented that can improve over naive gradient descent, along with experimental validation on certain problems.\n\nThe theoretical development seems promising, although perhaps a little more limited than ideal, establishing some cases in which the techniques can improve over SGD in certain cases, but without many general convergence bounds.\n", "strength_and_weaknesses": "The proposed approach makes a lot of sense and is presented clearly and intuitively. I agree with the authors that most approaches to tracking tend to ignore any possible temporal structure in the losses, and exploiting this seems a promising direction.\n\nThe requirement for strong convexity seems a bit limiting, however. This seems mostly needed for tracking the parameter vector distance, but one might expect that in many cases we are not interested in $$\\|\\theta -\\theta^\\star\\|$$ but $$R(\\theta)-R(\\theta^\\star)$$. Do the described techniques have any relevance for this metric?\n\nMoreover, modern analysis of gradient descent methods typically focuses on non-asymptotic convergence bounds. Is there any way to obtain such a bound here? \n\nThe paper could have been augmented with a discussion of lower bounds - is there any way in which the described techniques are optimal?\n\nFinally, the authors may wish to compare with the literature on dynamic regret in online convex optimization, which may provide another alternative to gradient descent which has seen a lot of recent development. Since these techniques also ignore temporal structure in the losses, I would expect this method to still compare favorably.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "VXdo8vjhWDx", "reviewer": "Reviewer_UaJ8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This paper presents a novel predictor-corrector algorithm for time-varying stochastic optimization. It exploits the continuity of the domain shift. This work demonstrates the superiority of the proposed algorithm over stochastic gradient descent both theoretically and empirically. Further, this works shows that a simple sample average estimation of the predictor-corrector term may lead to non-convergence. In applications shown, a moving average based method is instead applied to estimate the predictor-corrector term. The utility of the proposed method is shown in three concrete real applications. ", "summary_of_the_review": "I think this paper targets a very important question and provides direction for an intuitive solution. Yet, there are some important parts missing from its current form which somehow prevents it from being more useful and practical.", "strength_and_weaknesses": "Strengths:\n1. This work focuses on an important and interesting question in ML community.\n2. The proposed solution (adding an additional predictor-correct term to the gradient updating rule) is intuitive, general, and easy to implement.\n3. Some theoretical insights are given to demonstrate the usefulness of the proposed algorithm, together with some concrete applications.\n\nWeakness:\nIt seems to me this work does not provide a general way to estimate the predictor-correct term. Instead, only some specific forms for the applications in Section 4 are discussed. For the proposed algorithm to be truly useful, I wonder how easy it is for a practitioner to come-up with an estimation for the term, or what would be the general recommendation for them. Or maybe, another question whether the proposed moving average algorithm can be shown to be useful in for general applications.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster