← All setups

Ball Proximal Sharp Profile — Convex Ball Proximal Minimization

Descriptions may be stale. Consult the linked Lean sources.

Convex Ball Proximal Minimization · Lean proof

Convex Ball Proximal Minimization

We minimize a convex function f:E→R over a convex set C in a finite-dimensional real inner-product space E, with closed constrained epigraph. A given x0∈C satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a minimizer x⋆∈C, where R≥0 and Δ>0. At x∈C, the oracle returns an exact minimizer over {z∈C:∥z−x∥≤t}, where t>0. Ball proximal iteration must return x¯∈C with f(x¯)−f(x⋆)≤ε almost surely under P, the law of oracle randomness, for ε>0.

The optimization problem is minx∈Cf(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, t, R, Δ, ε, and x0; the set C and function f are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and closed epigraph). The set C⊆E is convex, and for all x,y∈C and λ∈[0,1], f((1−λ)x+λy)≤(1−λ)f(x)+λf(y). The constrained epigraph {(x,a)∈E×R:x∈C, f(x)≤a} is closed in E×R.

Assumption 2 (Initialization and minimizer). The given starting point satisfies x0∈C. There exists x⋆∈C such that f(x⋆)≤f(x)for every x∈C,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 3 (Exact ball proximal oracle). For every query x∈C, every oracle reply y satisfies y∈C,∥y−x∥≤t,f(y)≤f(z)for all z∈C with ∥z−x∥≤t. These conditions hold for every query history and every realization of the oracle randomness. The oracle may select among multiple minimizers using that history and randomness.

Our formulation is algorithm-specific: we analyze ball proximal iteration with fixed radius t. Starting at the given x0, each step queries the oracle at the current iterate and replaces it by the returned point: xk+1∈argminz∈C∥z−xk∥≤tf(z),k=0,…,K−1. Here K≥0 is the integer oracle-call budget, each step uses one call, and the output is the last iterate x¯=xK. All queries therefore lie in C.

The required accuracy is x¯∈C,f(x¯)−f(x⋆)≤εP-a.s. The minimizer x⋆ is fixed independently of the oracle randomness.

Proved result

⌈min{(Rt)2,Rt⋅(min{12,max{0,1−εΔ}})2+max{0,log⁡(Δ2⋅ε)}2}⌉+

OracleTemplate.Convergence LongTails.Setups.ConvexBallProximal.spec OracleTemplate.BallProximal.budget

Relevant previous results