← All setups

Uncalibrated Sharp Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a real inner-product space, f is G-Lipschitz with a minimizer u, ∥x0−u∥≤R, and f(x)−f(u)≥μ∥x−u∥. Each call returns (γr,γ(g+e)), where g∈∂f(x) is a global supporting subgradient, ∥g∥≤G, ∥e∥≤ρ, α[f(x)−f(u)]≤r≤β[f(x)−f(u)], and the unknown γ>0 may vary per call. Here 0≤ρ<μ≤G, 0<α≤β, R≥0, and ε>0. Target: f(xK)−f(u)≤ε for every oracle realization.

Comparison for UncalibratedSharp.
Result Oracle complexity Novelty Limitations
(1) RobustPolyak (Ours) (review) O(1+β(G+ρ)2α(μ−ρ)2log(1+GRε)) paired calls
(2) Geometric subgradient steps (Davis et al. 2018, sec. 5). Derived bound: full oracle model. O(1+(G+ρ)2(μ−ρ)2log(1+GRε)) direction calls (1): Updates need no G,R; stopping still needs G,R,ε. Matches the rate when α=β. (1): Needs gap estimates; loses a factor (α+β)2/(4αβ)≤β/α in the bound.
(3) Relaxed Polyak (Davis et al. 2018, sec. 3). Derived bound: ρ=0. O(1+βG2αμ2log(1+GRε)) paired calls; relaxation λk∈[2αα+β,2βα+β]. (1): Scope extends to ∥e∥≤ρ<μ. Matches known rate at ρ=0; identical contraction at α=β. Formalizes the relaxed-step guarantee.

Abbr: K: number of calls; xK: final iterate. A paired call returns (γr,γ(g+e)); a direction call uses only (g+e)/∥g+e∥. log: natural logarithm.

Davis, Damek, Dmitriy Drusvyatskiy, Kellie J. MacPhee, and Courtney Paquette. 2018. “Subgradient Methods for Sharp Weakly Convex Functions.” Journal of Optimization Theory and Applications 179: 962–82. https://doi.org/10.1007/s10957-018-1372-8.

Lean setup