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

• URL: http://arxiv.org/abs/2609.08380v1
• Date: Tue, 08 Sep 2026 07:51:34 GMT
• Title: How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
• Abstract summary: We focus on the case when suboptimality is measured in terms of the gradient mapping.<n>We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems.
• Score: 9.865174381229927
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\varepsilon$ is $\widetilde{O}(\varepsilon^{-4})$, compared to the near-optimal $\widetilde{O}(\varepsilon^{-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 $\widetilde{O}(\varepsilon^{-2})$. We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.

Related papers

• Solving Stochastic Variational Inequalities without the Bounded Variance Assumption [8.350639529216876]
  We analyze algorithms for solving variational inequalities (VI) without the bounded variance or bounded domain assumptions.<n>In our setting, this had been obtained with the bounded complexity assumption as not even satisfied for bi min-max problems with an oracle domain.
  arXiv  Detail & Related papers  (2026-02-05T10:44:04Z)
• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  We propose smoothed primal-dual algorithms for solving nonexact optimization problems with linear inequality constraints.<n>Our algorithms are single-loop iterations based on one gradient at each sample.<n>Unlike existing methods, our algorithms are free sub, large sizes or increasing parameters and use dual variable updates to ensure feasibility.
  arXiv  Detail & Related papers  (2025-04-10T09:59:43Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  This paper establishes the complexity for finding approximate stationary points of non-strongly-concave (NC-SC) smooth minimax problems. We deploy a proposed sequence of $Omega-strong$lyconcave sub-2 problems in both general complexity and averaged complexity. In our proposed finite-sum setting, our proposed algorithm provides a nearly-tight dependence on the condition number.
  arXiv  Detail & Related papers  (2021-03-29T18:53:57Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.