Skip to content

Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity

Feb 2024 · International Conference on Machine Learning · pp. 840-878 · 12 citations · ⚡ 2 influential · 69 references
Mathematics Computer Science

TL;DR

This work provides a refined analysis for inexact Halpern iteration that relaxes the required inexactness level to improve some state-of-the-art complexity results even for constrained stochastic convex-concave min-max problems.

Abstract

We focus on constrained, $L$-smooth, potentially stochastic and nonconvex-nonconcave min-max problems either satisfying $\rho$-cohypomonotonicity or admitting a solution to the $\rho$-weakly Minty Variational Inequality (MVI), where larger values of the parameter $\rho>0$ correspond to a greater degree of nonconvexity. These problem classes include examples in two player reinforcement learning, interaction dominant min-max problems, and certain synthetic test problems on which classical min-max algorithms fail. It has been conjectured that first-order methods can tolerate a value of $\rho$ no larger than $\frac{1}{L}$, but existing results in the literature have stagnated at the tighter requirement $\rho<\frac{1}{2L}$. With a simple argument, we obtain optimal or best-known complexity guarantees with cohypomonotonicity or weak MVI conditions for $\rho<\frac{1}{L}$. First main insight for the improvements in the convergence analyses is to harness the recently proposed $\textit{conic nonexpansiveness}$ property of operators. Second, we provide a refined analysis for inexact Halpern iteration that relaxes the required inexactness level to improve some state-of-the-art complexity results even for constrained stochastic convex-concave min-max problems. Third, we analyze a stochastic inexact Krasnosel'ski\u{\i}-Mann iteration with a multilevel Monte Carlo estimator when the assumptions only hold with respect to a solution.

View source

Similar papers

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $\mu$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-en...

Qi-Hao Zhou · 2 citations
#machine learning Preprint Oct 2026

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-P{\L} Min-Max Games

How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-P{\L} (NC-P{\L}) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For...

Junsoo Ha · 0 citations
Preprint Oct 2026

Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization

We characterize the oracle complexity of finding first-order stationary points in smooth nonconvex--strongly-concave (NC--SC) minimax optimization when each query provides the full Hessian in addition to the function value and gradient. For $\Phi(x)=\max_y f(x,y)$, assume that $f$ has an $L$-Lipschitz gradient, a $\rho...

Fang-Qing Zhang, Hai-Han Zhang, Wen-Dao Wu et al. · 0 citations
Preprint Oct 2026

The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization

We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon>0$ in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge1$, F$^2$SA-$p$ achieves $\widetilde O(...

Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al. · 0 citations
Preprint Sep 2026

Lower Bounds for Nonconvex-Concave Minimax Optimization

We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives $f$ that are jointly $L$-smooth in the primal and dual variables $(x,y)$, concave in $y$, and whose primal value function $\Phi(x) := \max_{y\in\mathcal Y} f(x,y)$ satisfies the initial-ga...

Qi-Long Wu, Zhi-Hao Gu, Jun-Chi Yang · 7 citations
Preprint Sep 2026

The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization

A tight lower bound is proved of $\Omega(\lambda^{1/2}\epsilon^{-7/2})$ for finding points satisfying the recently proposed relaxed notion of $(\lambda,\epsilon)$-stationarity, which allows combining further-away gradients.

Guy Kornowski · 3 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.