Second-Order Stationarity in PL Minimax Problems
Descriptions may be stale. Consult the linked Lean sources.
Second-Order Stationarity in PL Minimax Problems
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Attainment and maximization PL
condition). For every
Assumption 3 (Initial gaps). The given points
satisfy
Queries may be made at any point
Results
On finite-dimensional real inner-product spaces,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) EnvelopeCubicNonconvexPL
(Ours) |
|||
| (2) ECRN (Zhou et al. 2026), Thm. 11. Strongly concave inner subclass. | (1): Scope: PL permits nonconcave inner objectives and nonunique maximizers. Matches the leading polynomial rate on the strongly concave overlap. | (1): |
|
| (3) MCN (Luo et al. 2022), Cor. 1. Strongly concave inner subclass. | (1): Scope: strong
concavity to PL. On the overlap, for |
(1) requires values and has larger initialization/logarithmic overhead. Leading-term improvement need not dominate total cost. | |
| (4) Smoothed-AGDA (Yang et al. 2022), Thm. 4.1, Cor. 4.1. Full inner-PL class. | (1) adds second-order stationarity. Costs are not directly comparable: different oracle access and accuracy guarantees. | (1) requires a Lipschitz Hessian and full-Hessian queries; (4) requires only gradient smoothness. |
Abbr: