← All setups

Velocity Tracking Smooth Drift — Tracking Smooth Strongly Convex Objectives

Descriptions may be stale. Consult the linked Lean sources.

Tracking Smooth Strongly Convex Objectives · Lean proof

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⋆.

Proved result

⌈16⋅(2⋅Lμ+99⋅σ2μ2⋅ε)⋅log⁡(1+15⋅R2+45⋅V2⋅(2⋅Lμ+99⋅σ2μ2⋅ε)2ε)⌉++H+1

OracleTemplate.Convergence LongTails.Setups.SmoothDriftStronglyConvex.spec
  OracleTemplate.VelocityTracking.SmoothDrift.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.