Accelerated Relative Error Convex — Convex Minimization with Relative Error
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Relative Error · Lean proof
Convex Minimization with
Relative Error
We consider minimizing a differentiable convex function on a real Hilbert space
. The function admits a quadratic
upper model with curvature ,
and a given starting point
lies within distance of a
global minimizer . At , the oracle returns a vector satisfying , where . For , the goal is an output
satisfying
almost surely under , the joint
law of algorithm and oracle randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere on . For
every ,
Assumption 2 (Initial distance). There exists such that
Assumption 3 (Relative oracle error). Queries may be
made at any point of . For every
finite query–reply history , every
query , and every realization
of the oracle randomness used for
that reply, the returned vector satisfies Oracle randomness may be dependent
across calls, and replies may depend on the history. The algorithm’s
randomness is independent of the oracle randomness.
After the allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.RelativeErrorSmoothConvex.spec OracleTemplate.RelativeErrorConvex.budget
Relevant previous results
- Nikita Kornilov, Eduard Gorbunov, Mohammad Alkousa, Fedor Stonyakin,
Pavel Dvurechensky, Alexander Gasnikov. Intermediate Gradient Methods
with Relative Inexactness. 2023 (preprint v1; published 2025).
Complexity: fixed relative-error gradient oracle calls
for ,
provided , with sufficiently large universal ; Intermediate Similar Triangle Method
with .