Tracking Smooth Strongly Convex Objectives
Descriptions may be stale. Consult the linked Lean sources.
Tracking Smooth Strongly Convex Objectives
We consider tracking the minimizers
The time-indexed optimization problems are
Our assumptions:
Assumption 1 (Strong convexity and smoothness). Each
Assumption 2 (Minimizer path and drift). There
exists a sequence
Assumption 3 (Stochastic gradient oracle). There is
a probability measure
The output includes the number of completed oracle calls.
Specifically, its counter starts at
Let
Results
On a separable real Hilbert space, each deterministic
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) VelocityTrackingSmoothDrift
(Ours) |
|||
| (2) SGD with step decay (Cutler et al. 2023), Thms. 4, 28 | (1): lower certified
error when |
(1): extra noise
logarithm and velocity initialization term; deterministic drift and
uniform variance. For |
|
| (3) Romberg NLMS (Moulines et al. 2005), Thm. 8, Cor. 9 | No explicit parameter-dependent call
budget. MSE |
(1): explicit finite-time
extension to nonlinear objectives with arbitrarily changing shape.
Matches floor exponent |
(1) excludes the multiplicative random-design noise allowed by (3). |
| (4) Prediction–correction
(Kamijima et al.
2025), Thm. 5.5 ( |
No comparable total-call bound. |
(1): finite-time mean
square, one fresh gradient per step; removes per-sample convexity and
repeated sample solves. The |
(1) needs variance
uniform in |
Abbr: