How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

Abstract

We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than ε is Õ(ε⁻⁴), compared to the near-optimal Õ(ε⁻²) that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to Õ(ε⁻²). We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.

A Unified Efficient Gradient-Based Heuristic For Box-Constrained Expectation-Related and Risk-Averse Stochastic Optimization Problems
Mazen Alamir
arXiv7 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
A Safeguarded Projected-Gradient Framework for Complementarity Constrained Least Squares Problems
Lianghai Xiao, Wei Zhang, Jiayi Zhong
arXiv2 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
A Stochastic Proximal-Gradient Method for Regularized Generally Constrained Continuous Optimization
Frank E. Curtis, Xiaoyi Qu, Daniel P. Robinson
arXiv26 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
A switching proximal gradient method for constrained difference-of-convex optimization problems
Yuncheng Liu, Chuangliang Zhang, Bo Yang
arXiv27 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Online Feedback Optimization for Constrained Stochastic Problems with Decision-Dependent Distributions
Caio Kalil Lauand, Emiliano Dall'Anese
arXiv22 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{alacaoglu2026make,
  title = {{How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond}},
  author = {Ahmet Alacaoglu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08380},
  eprint = {2609.08380},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08380},
}

RIS

TY  - UNPB
TI  - How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
AU  - Ahmet Alacaoglu
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08380
UR  - https://arxiv.org/abs/2609.08380
AB  - We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than ε is Õ(ε^−4), compared to the near-optimal Õ(ε^−2) that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to Õ(ε^−2). We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.
ER  -

Abstract

Related

Cite