← All setups

Smooth Finite-Maximum Minimization

Descriptions may be stale. Consult the linked Lean sources.

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−δ.

Results

In a finite-dimensional real inner-product space, minimize F(x)=maxi≤mfi(x) over B=B―(x0,R), with m≥2. Each fi is convex and differentiable on B, with ∥∇fi∥≤G and L-Lipschitz gradient there; a constrained minimizer x⋆∈B exists. Here G,R,ε>0, L≥0, and 0<δ<1. One exact component query returns (fi(x),∇fi(x)). The target is a measurable feasible output x^ with Pr{F(x^)−F(x⋆)≤ε}≥1−δ.

Comparison for SmoothFiniteMaximum.
Result Oracle complexity Novelty Limitations
(1) AffineSoftmaxFiniteMaximum (Ours) (⋆⋆⋆) (review) O(hℓ7[m+mt1/3+m3/4t1/2+m6/7(st)2/7+s]); deterministic query cap.
(2) Accelerated linearization (Carmon et al. 2021), App. A.3 O(m(1+t)); deterministic accuracy. (1): Rate, normalized regime: polynomial saving for m≫ε−1/2. At m=ε−3/2, O(ε−2) becomes O(hℓ7ε−13/7). (1): Worse for m≪ε−1/2 in the normalized regime; randomized, with hℓ7 overhead and a much larger universal constant.
(3) (Carmon et al. 2023), Thm. 8.1, ball case; confidence amplification O(h[mt1/3+s2]polylog(2+m+s+t)), for 0<ε≤min{LR2,G2/L}. Includes repetitions and O(mh) scoring queries. (1): Rate, normalized regime: polynomial saving for m≪ε−5/3 within the stated accuracy range; matches polynomial order for m≳ε−5/3. Drops the accuracy restriction. (1): Larger polylogarithms and universal constant; query guarantee only, versus runtime bounds and an additional simplex setting.
(4) (Carmon et al. 2021), Thm. 2; unconstrained, globally convex, G-Lipschitz, L-smooth components; global minimizer within R of x0 O(hk3[m{1+(slog⁡m)2/3}+m(slog⁡m+t)]); includes confidence amplification and scoring. (1): On common global-minimizer instances, polynomial saving for every m=ε−α, α>0, in the normalized regime. Scope: local ball assumptions suffice; classes overlap, without nesting. (1): Can lose when L≫G2/ε. For G=R=1, L=ε−2: contains mε−1 versus mε−2/3+mε−3/2, ignoring logarithms.
(5) AffineResidualFiniteMaximum (Ours) (⋆⋆⋆) (review) O(hℓ8[m+mt2/5+m3/4t1/2+t2/3]); sufficient deterministic cap on component value-and-gradient calls.
(6) Accelerated linearization (Carmon et al. 2021), App. A.3 O(m(1+t)); sufficient budget; deterministic accuracy. (5): For t≥1, ignoring logs, saving factor min{t1/10,m1/4,mt−1/6}; strict polynomial gain needs m≫t1/6. Normalized m=ε−1: O(ε−3/2)→O(hℓ8ε−7/5). (5): Worse for m≪t1/6; randomized, with hℓ8 overhead and a much larger universal constant.
(7) (Carmon et al. 2023), Thm. 8.1 and Table 1, ball case; confidence amplification O(h[mt1/3+s2]polylog(2+m+s+t)); sufficient budget for 0<ε≤min{LR2,G2/L}. Includes repetitions, cost cutoffs and O(mh) scoring calls. (5): Ignoring logs, improves when s2≫mt2/5+m3/4t+t2/3; drops the accuracy restriction. Against (1), replaces m6/7(st)2/7+s by mt2/5+t2/3, benefiting sufficiently large G. (5): Can lose when s2 is small; factor t1/15 loss when mt2/5 dominates the compared costs. No runtime/simplex guarantee. Against (1), extra ℓ and worse large-m dependence.
(8) (Carmon et al. 2021), Thm. 2; unconstrained, globally convex, G-Lipschitz, L-smooth components; global minimizer within R of x0 O(hk3[m{1+(slog⁡m)2/3}+m(slog⁡m+t)]); sufficient budget including confidence amplification and scoring. (5): On common global-minimizer instances, normalized m=ε−1 gives O(ε−5/3)→O(ε−7/5), ignoring logs. Scope: local ball assumptions suffice; classes overlap without nesting. (5): For G=R=1, L=ε−2, has O(mε−6/5+m3/4ε−3/2+ε−2) versus O(mε−2/3+mε−3/2), ignoring logs; can lose.

Abbr: s=GR/ε, t=LR2/ε, h=1+log⁡(1/δ), ℓ=log⁡(2+m+s+t), k=1+log⁡(1+slog⁡m). polylog(u) denotes the source’s unspecified polynomial in 1+log⁡u. Normalized regime: G=L=R=1, ε↓0; polynomial comparisons ignore logarithmic factors and use fixed confidence.

Carmon, Yair, Arun Jambulapati, Yujia Jin, and Aaron Sidford. 2021. Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss. https://doi.org/10.48550/arXiv.2105.01778.
Carmon, Yair, Arun Jambulapati, Yujia Jin, and Aaron Sidford. 2023. A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions. https://doi.org/10.48550/arXiv.2311.10886.

Lean setup