Robust Polyak — Uncalibrated Sharp Minimization
Descriptions may be stale. Consult the linked Lean sources.
Uncalibrated Sharp Minimization · Lean proof
Uncalibrated
Sharp Minimization
We consider minimizing a Lipschitz function on a real inner product
space , with a global minimizer
and a given starting point
. The objective grows at
least linearly with distance from . The oracle returns a
multiplicative estimate of the objective gap and a perturbed supporting
subgradient, both multiplied by the same unknown positive scale. The
perturbation bound is strictly smaller than the sharpness constant. For
a tolerance , 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 and for its
induced norm. The parameters satisfy The algorithm receives only
, , , , , and ; the constants , , and may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Lipschitz continuity). For every ,
Assumption 2 (Sharpness and initial distance). There
exists a global minimizer such that
Assumption 3 (Uncalibrated oracle). Queries may be
made at any . For every query
history and every realization of the oracle randomness, the reply admits a
representation where and satisfy The scale and the quantities , , and may depend on the query, its history,
and the oracle randomness. Only is returned. The algorithm’s
randomness is independent of the oracle randomness; oracle replies may
be dependent across calls.
After the allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.UncalibratedSharp.spec OracleTemplate.UncalibratedSharp.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.