← All setups

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 f:E→R on a real inner product space E, with a global minimizer x⋆ and a given starting point x0∈E. The objective grows at least linearly with distance from x⋆. 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 ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The parameters satisfy 0≤ρ<μ≤G,0<α≤β,R≥0,ε>0. The algorithm receives only E, μ, ρ, α, β, and x0; the constants G, R, and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Lipschitz continuity). For every x,y∈E, |f(x)−f(y)|≤G∥x−y∥.

Assumption 2 (Sharpness and initial distance). There exists a global minimizer x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x)−f(x⋆)≥μ∥x−x⋆∥for every x∈E.

Assumption 3 (Uncalibrated oracle). Queries may be made at any x∈E. For every query history and every realization of the oracle randomness, the reply (s,v)∈R×E admits a representation s=γr,v=γ(g+e),γ>0, where r∈R and g,e∈E satisfy ∥g∥≤G,∥e∥≤ρ,f(x)+⟨g,y−x⟩≤f(y)for every y∈E,α(f(x)−f(x⋆))≤r≤β(f(x)−f(x⋆)). The scale γ and the quantities r, g, and e may depend on the query, its history, and the oracle randomness. Only (s,v) 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 f(x¯)−f(x⋆)≤εP-a.s.

Proved result

⌈(G+ρ)2⋅(α+β)24⋅(μ−ρ)2⋅α⋅β⋅log⁡(1+G2⋅R2ε2)⌉+

OracleTemplate.Convergence LongTails.Setups.UncalibratedSharp.spec OracleTemplate.UncalibratedSharp.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.