Smooth Finite-Maximum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth Finite-Maximum Minimization
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity). For every
Assumption 2 (Component regularity). Each
Assumption 3 (Constrained minimizer). There exists
Oracle access consists of component queries: choosing an index
After the allotted calls, the output
Results
In a finite-dimensional real inner-product space, minimize
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AffineSoftmaxFiniteMaximum
(Ours) |
|||
| (2) Accelerated linearization (Carmon et al. 2021), App. A.3 | (1): Rate, normalized
regime: polynomial saving for |
(1): Worse for |
|
| (3) (Carmon et al. 2023), Thm. 8.1, ball case; confidence amplification | (1): Rate, normalized
regime: polynomial saving for |
(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, |
(1): On common
global-minimizer instances, polynomial saving for every |
(1): Can lose when |
|
| (5) AffineResidualFiniteMaximum
(Ours) |
|||
| (6) Accelerated linearization (Carmon et al. 2021), App. A.3 | (5): For |
(5): Worse for |
|
| (7) (Carmon et al. 2023), Thm. 8.1 and Table 1, ball case; confidence amplification | (5): Ignoring logs,
improves when |
(5): Can lose when |
|
| (8) (Carmon et al.
2021), Thm. 2; unconstrained, globally convex, |
(5): On common
global-minimizer instances, normalized |
(5): For |
Abbr: