Convex Minimization with Relative Error
Descriptions may be stale. Consult the linked Lean sources.
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
Results
Lean setup