Online Metric Accelerated — Diagonal Smooth Strongly Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Diagonal Smooth Strongly Convex Minimization · Lean proof
Diagonal Smooth
Strongly Convex Minimization
We consider minimizing a differentiable function , where . For hidden weights , define . In this
norm, is -smooth and -strongly convex, with hidden . Its known minimum value
is attained at a
global minimizer . A given
starting point satisfies , where . The oracle returns at . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The inner
product
and gradient are Euclidean; the weighted norm specifies the quadratic
bounds below. The algorithm receives only , , and ; the weights , strong convexity
parameter , initial gap bound
, and tolerance may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Diagonal smoothness and strong
convexity). The function is
differentiable everywhere on . For every ,
Assumption 2 (Attained minimum and initial gap).
There exists
such that
Queries may be made at any point of , with each query returning
both the exact function value and the exact gradient. After the allotted
oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.DiagonalSmoothStronglyConvex.spec
OracleTemplate.OnlineMetricAccelerated.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.