← All setups

Tracking Smooth Strongly Convex Objectives

Descriptions may be stale. Consult the linked Lean sources.

Tracking Smooth Strongly Convex Objectives

We consider tracking the minimizers xk⋆ of differentiable functions fk:E→R, indexed by k≥0, on a separable real Hilbert space E. Each objective is μ-strongly convex with L-Lipschitz gradient, where 0<μ≤L. The minimizer path has bounded initial distance from a given point x0∈E, bounded initial velocity, and uniformly bounded second differences. At call k, the oracle returns an unbiased estimate of ∇fk(x) with variance at most σ2, where σ≥0, using a fresh independent sample. For ε>0, the goal is an output (x¯,N) satisfying E∥x¯−xmax{N−1,0}⋆∥2≤ε, where N counts completed calls and expectation covers oracle and algorithm randomness.

The time-indexed optimization problems are minx∈Efk(x),k∈N0. The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, μ, L, σ, ε, and x0; the parameters Γ,R,V≥0 and H∈N0 may enter only the oracle-call budget. The parameter H imposes no additional condition on the objectives or the minimizer path.

Our assumptions:

Assumption 1 (Strong convexity and smoothness). Each fk is Fréchet differentiable everywhere. For every k∈N0 and x,y∈E, fk(y)≥fk(x)+⟨∇fk(x),y−x⟩+μ2∥y−x∥2,∥∇fk(x)−∇fk(y)∥≤L∥x−y∥.

Assumption 2 (Minimizer path and drift). There exists a sequence (xk⋆)k≥0 of global minimizers satisfying fk(xk⋆)≤fk(x)(k≥0, x∈E),∥x0−x0⋆∥≤R,∥x1⋆−x0⋆∥≤V,∥(xk+2⋆−xk+1⋆)−(xk+1⋆−xk⋆)∥≤Γ(k≥0). The drift bound and tolerance satisfy 9792Γ2(2Lμ+99σ2μ2ε)4≤ε.

Assumption 3 (Stochastic gradient oracle). There is a probability measure ν on Ω and, for every k∈N0, a jointly measurable map gk:E×Ω→E. For every fixed x∈E, gk(x,⋅) is Bochner integrable and ∥gk(x,⋅)−∇fk(x)∥2 is integrable under ν, with Eξ∼ν[gk(x,ξ)]=∇fk(x),Eξ∼ν[∥gk(x,ξ)−∇fk(x)∥2]≤σ2. At call k, a query x∈E receives gk(x,ξk), where the samples (ξk)k≥0 are independent with common law ν and are independent of the algorithm’s randomness.

The output includes the number of completed oracle calls. Specifically, its counter starts at c0=0, increases according to ck+1=ck+1 after each reply, and equals the reported value N at termination. Thus the objective advances with each oracle call, and the reported time cannot be chosen independently of the number of calls.

Let P be the joint law of the algorithm’s randomness and the independent oracle samples. After the allotted calls, the output (x¯,N)∈E×N0 must have integrable squared tracking error under P and satisfy EP[∥x¯−xmax{N−1,0}⋆∥2]≤ε. For N≥1, the reference minimizer belongs to the objective queried on the final call; for N=0, it is x0⋆.

Results

On a separable real Hilbert space, each deterministic fk is differentiable, μ-strongly convex and L-smooth, with 0<μ≤L. Minimizers satisfy ∥x0−x0⋆∥≤R, ∥x1⋆−x0⋆∥≤V and ∥xk+2⋆−2xk+1⋆+xk⋆∥≤Γ. Jointly measurable stochastic gradients use independent samples with common law p, are unbiased and have variance at most σ2 uniformly in x; the relevant first and second moments are integrable. For ε>0 and R,V,Γ,σ≥0, admissibility requires 9792Γ2(2L/μ+99σ2/(μ2ε))4≤ε. The target is ∫∥xN(ω)−xN−1⋆∥2dP(ω)≤ε, where P=p⊗N. The setup requires the output time to count oracle calls, not a particular update rule.

Tracking under SmoothDriftStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) VelocityTrackingSmoothDrift (Ours) (⋆⋆⋆) (review) O(1+H+Alog(1+R2+V2A2ε)) stochastic gradients; every later N succeeds. Updates know μ,L,σ,ε, not Γ,R,V.
(2) SGD with step decay (Cutler et al. 2023), Thms. 4, 28 O(1+κlog(1+R2ε)+σ2μ2ε) gradients to the certified MSE scale ε≍κ2Δ2+(Δσ2/μ2)2/3. Speed-bounded restriction: E∥xk+1⋆−xk⋆∥2≤Δ2; deterministic overlap has V≤Δ, Γ≤2Δ. (1): lower certified error when FΓ≪ε≪(Δσ2/μ2)2/3; every ε>0 if Γ=0. Scope: allows growing speed. No faster cost on the common admissible regime. (1): extra noise logarithm and velocity initialization term; deterministic drift and uniform variance. For Γ≍Δ, requires κ4Δ2 rather than κ2Δ2 accuracy scale.
(3) Romberg NLMS (Moulines et al. 2005), Thm. 8, Cor. 9 No explicit parameter-dependent call budget. MSE O(n−4/5) at smoothness β=2, after a fixed-fraction burn-in; two NLMS updates per sample. Special case: stable time-varying autoregression, smooth coefficients/covariance, bounded innovation and initial moments of order q>8. (1): explicit finite-time extension to nonlinear objectives with arbitrarily changing shape. Matches floor exponent n−4/5 for Γ≍n−2; oracle complexities are not comparable. (1) excludes the multiplicative random-design noise allowed by (3).
(4) Prediction–correction (Kamijima et al. 2025), Thm. 5.5 (q=2) No comparable total-call bound. lim supkE∥x^k−xk⋆∥=O(b+γs+(s+1)h2/5). Requires bounded second trajectory derivative, per-sample strong convexity/smoothness, and correction contracting to sample minimizers with γ∥α∥1<1; history length Θ(h−4/5). (1): finite-time mean square, one fresh gradient per step; removes per-sample convexity and repeated sample solves. The h2/5 rate in (4) requires b=0, γ=O(h2/5). (1) needs variance uniform in x, not just at xk⋆, and excludes convex regularizers. Different oracles and error criteria prevent a cost comparison.

Abbr: κ=L/μ, A=κ+σ2/(μ2ε), FΓ=κ4Γ2+(Γ2σ8/μ8)1/5; H∈N is the supplied horizon slack. MSE: mean-square distance; NLMS: normalized least mean squares; n: sample count in (3). In (4), h is the sampling period, b bounds sample-minimizer bias, s2 bounds its mean-square deviation, γ is the correction contraction factor, and α is the polynomial prediction coefficient vector. ≍ and ≪ denote comparison up to universal factors and asymptotic separation, respectively.

Cutler, Joshua, Dmitriy Drusvyatskiy, and Zaid Harchaoui. 2023. “Stochastic Optimization Under Distributional Drift.” Journal of Machine Learning Research 24 (147): 1–56. https://jmlr.org/papers/v24/21-1410.html.
Kamijima, Tomoya, Naoki Marumo, and Akiko Takeda. 2025. A Regression-Based Prediction-Correction Method for Stochastic Time-Varying Optimization Problems. https://doi.org/10.48550/arXiv.2512.15205.
Moulines, Eric, Pierre Priouret, and François Roueff. 2005. “On Recursive Estimation for Time Varying Autoregressive Processes.” The Annals of Statistics 33 (6): 2610–54. https://doi.org/10.1214/009053605000000624.

Lean setup