# Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum

Source: [Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum](<https://www.sota2.com/research/paper/68fa5d6d1e209131ce9da1a8>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-06-25T05:00:21.026Z

Authors: Haoyuan Cai, Sulaiman A. Alghunaim, Ali H.Sayed

Published: 2024-06-18T20:14:52.000Z

## Abstract

Lower-bound analyses for nonconvex strongly-concave minimax optimization problems have shown that stochastic first-order algorithms require at least $\\mathcal{O}(\\varepsilon^{-4})$ sample complexity to find an $\\varepsilon$-stationary point. Some works indicate that this complexity can be improved to $\\mathcal{O}(\\varepsilon^{-3})$ when the stochastic loss gradient is Lipschitz continuous. The question of achieving enhanced convergence rates under distinct conditions, remains open. In this work, we address this question for optimization problems that are nonconvex in the minimization variable and strongly concave or Polyak-Lojasiewicz (PL) in the maximization variable. We introduce novel bias-corrected momentum algorithms utilizing efficient Hessian-vector products. We establish convergence conditions and demonstrate a lower iteration complexity of $\\mathcal{O}(\\varepsilon^{-3})$ for the proposed algorithms. The effectiveness of the proposed method is validated through applications to robust logistic regression and robust adaptive cruise control.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Worst-case risk optimization on mushroom](<https://www.sota2.com/research/sota/worst-case-risk-optimization-on-mushroom.md>): Worst-case risk optimization; Mushroom; Gradient Count: 49540.

- [Worst-case risk optimization on ijcnn1](<https://www.sota2.com/research/sota/worst-case-risk-optimization-on-ijcnn1.md>): Worst-case risk optimization; ijcnn1; Gradient Count: 41140.

- [Worst-case risk optimization on a9a](<https://www.sota2.com/research/sota/worst-case-risk-optimization-on-a9a.md>): Worst-case risk optimization; a9a; Gradient Count: 18340.

- [Worst-case risk optimization on w8a](<https://www.sota2.com/research/sota/worst-case-risk-optimization-on-w8a.md>): Worst-case risk optimization; w8a; Total Gradients: 63940.

- [Worst-case risk optimization on phishing](<https://www.sota2.com/research/sota/worst-case-risk-optimization-on-phishing.md>): Worst-case risk optimization; Phishing; Gradient Magnitude (k): 18340.

- [Stochastic Minimax Optimization on Theoretical Analysis](<https://www.sota2.com/research/sota/stochastic-minimax-optimization-on-theoretical-analysis.md>): Stochastic Minimax Optimization; Theoretical Analysis; Sample Complexity: -3.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2406.13041>)

[PDF](<https://arxiv.org/pdf/2406.13041.pdf>)