Accelerated Inexact Strongly Convex — Inexact Gradient Strongly Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Inexact Gradient Strongly Convex Minimization · Lean proof
Inexact Gradient
Strongly Convex Minimization
We consider minimizing a differentiable, -strongly convex function on a real Hilbert space
, with quadratic upper curvature
bound . A given point
lies within distance of a global minimizer . At , the oracle returns a vector with relative gradient error
controlled by and
additive error controlled by . For a tolerance compatible with this
error, the goal is an output satisfying
almost surely under , the joint
law of the algorithm’s and oracle’s randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives only , , , , and ; the parameters , , and may enter the oracle-call
budget but are not algorithm inputs. In addition to the ranges above,
the parameters satisfy
Our assumptions:
Assumption 1 (Smoothness and strong convexity). The
function is Fréchet
differentiable everywhere on . For
every ,
Assumption 2 (Inexact gradient oracle). Queries may
be made at any point . Every
oracle reply satisfies This bound holds for every query history and
every realization of the oracle randomness. Replies may depend on the
history, and the oracle randomness may be dependent across calls. The
algorithm’s randomness is independent of the oracle randomness.
Assumption 3 (Initial distance). There exists such that
After the allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.InexactGradientStronglyConvex.spec OracleTemplate.InexactGradient.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.