← All setups

Affine Softmax Finite Maximum — Smooth Finite-Maximum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Finite-Maximum Minimization · Lean proof

Smooth Finite-Maximum Minimization

We minimize F(x)=max1≤i≤mfi(x) over C={x∈E:∥x−x0∥≤R}, where E is a finite-dimensional real inner-product space, x0∈E, R>0, and m≥2 is an integer. Each fi:E→R is convex on C, differentiable at every point of C, and has an L-Lipschitz gradient bounded in norm by G, where L≥0 and G>0. The oracle returns (fi(x),∇fi(x)) at (i,x) with x∈C. Given ε>0 and δ∈(0,1), the goal is a measurable output x¯∈C almost surely satisfying F(x¯)−F(x⋆)≤ε with probability at least 1−δ, where x⋆ minimizes F on C and probabilities follow the law P of the algorithm’s randomness.

The optimization problem is minx∈CF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, m, G, L, R, ε, δ, and x0; the component functions and the minimizer are accessed only through the specified oracle information.

Our assumptions:

Assumption 1 (Component convexity). For every i∈{1,…,m}, x,y∈C, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y).

Assumption 2 (Component regularity). Each fi:E→R is Fréchet differentiable at every x∈C. For every i∈{1,…,m} and x,y∈C, ∥∇fi(x)∥≤G,∥∇fi(x)−∇fi(y)∥≤L∥x−y∥.

Assumption 3 (Constrained minimizer). There exists x⋆∈C such that F(x⋆)≤F(x),x∈C.

Oracle access consists of component queries: choosing an index i∈{1,…,m} and a point x∈C returns the exact value and gradient of that component. Each such pair is obtained in one oracle call.

After the allotted calls, the output x¯ must be measurable and satisfy x¯∈CP-a.s.,P(F(x¯)−F(x⋆)≤ε)≥1−δ.

Proved result

(1+clog2(⌈1δ⌉+))⋅⌈2000000000000000000000⋅(1+clog2(⌈2+m+G⋅Rε+L⋅R2ε⌉+))7⋅(m+m⋅(L⋅R2ε)13+m34⋅L⋅R2ε+m67⋅(G⋅L⋅R3ε2)27+G⋅Rε)⌉+

OracleTemplate.Convergence LongTails.Setups.SmoothFiniteMaximum.spec OracleTemplate.AffineSoftmaxFiniteMaximum.budget

Relevant previous results

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