Descriptions may be stale. Consult the linked Lean sources.
Tracking Smooth Strongly
Convex Objectives
We consider tracking the minimizers of differentiable functions
, indexed by
, on a separable real Hilbert
space . Each objective is -strongly convex with -Lipschitz gradient, where . The minimizer path has
bounded initial distance from a given point , bounded initial velocity, and
uniformly bounded second differences. At call , the oracle returns an unbiased
estimate of with
variance at most , where
, using a fresh
independent sample. For , the goal is an output
satisfying ,
where counts completed calls and
expectation covers oracle and algorithm randomness.
The time-indexed optimization problems are The norm is induced by the inner product
on . The algorithm receives , the measurable sample space , , , , , and ; the parameters and may enter only the
oracle-call budget. The parameter
imposes no additional condition on the objectives or the minimizer
path.
Our assumptions:
Assumption 1 (Strong convexity and smoothness). Each
is Fréchet differentiable
everywhere. For every and ,
Assumption 2 (Minimizer path and drift). There
exists a sequence of global minimizers
satisfying The drift bound and tolerance satisfy
Assumption 3 (Stochastic gradient oracle). There is
a probability measure on and, for every , a jointly measurable
map . For
every fixed , is Bochner integrable and
is
integrable under , with At call , a
query receives , where the samples 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 , increases according to after each reply, and
equals the reported value at
termination. Thus the objective advances with each oracle call, and the
reported time cannot be chosen independently of the number of calls.
Let be the joint law of the
algorithm’s randomness and the independent oracle samples. After the
allotted calls, the output must have integrable squared tracking error
under and satisfy For , the reference minimizer belongs
to the objective queried on the final call; for , it is .