PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ahmet Alacaoglu

arXiv:2609.08380v1math.OCcs.LG

TL;DR

For constrained min-max problems, the primal-dual gap can be infinite at nonoptimal points on unbounded domains. The paper uses recursive regularization and anchored stochastic extragradient, and reports optimal-up-to-logarithmic-terms complexity for the gradient mapping.

  • Problem

    On unbounded domains, the primal-dual gap may be infinite at nonoptimal test points, while the paper seeks optimal-up-to-logarithmic-terms gradient-mapping complexity for constrained problems.

    Source: §1 · p. 2, §7 · p. 24

  • Method

    The construction combines recursive regularization with anchored stochastic extragradient to handle the Blum-Gladyshev variance assumption.

    Source: §2 · pp. 6–7

  • Results

    The paper reports gradient-mapping complexity optimal up to logarithmic terms for constrained convex-concave min-max problems or stochastic variational inequalities.

    Source: §7 · p. 24

  • Takeaways & Limitations

    The results target constrained min-max problems and stochastic variational inequalities, with strongly convex-strongly concave gradient-mapping guarantees also included.

    Source: §7 · p. 24

    The construction uses three loops, and obtaining the same complexity with a single-loop algorithm remains open to the authors’ knowledge.

    Source: §7 · p. 24

Abstract

from arXiv · show

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.

1 Introduction

The introduction argues that gap-based optimality is problematic on unbounded domains, motivating gradient-mapping residuals for constrained min-max problems. It frames the work as improving their stochastic oracle complexity under a broader variance model.

1 Introduction

  • The primal-dual gap can be infinite at nonoptimal test points on unbounded domains, while stochastic iterates complicate restricted-gap constructions.Restricted gaps may require a compact set containing the solution and iterates, and may depend on the solution.Source: §1 · p. 2
  • The gradient mapping generalizes the unconstrained gradient norm and offers an optimality measure suited to unbounded problems.For constrained min-max problems, the paper connects this residual to the monotone-inclusion formulation.Source: §1 · pp. 2–3
  • Constrained min-max gradient-mapping complexity remained eO(ε^-4), except [TDNT26] at eO(ε^-10/3) under stronger stochastic-oracle assumptions.The stated goal is to improve the dependence on ε to an optimal one.Source: §1 · p. 2
  • The paper studies a monotone variational-inequality formulation that covers constrained convex-concave min-max problems through its mapping.The formulation also accommodates nonsmooth convex objectives through a regularizer.Source: §1 · pp. 1–3
  • The contribution targets improved complexity under the Blum-Gladyshev variance assumption without requiring initial-distance or global variance-bound parameters.The assumption generalizes bounded variance; when B = 0, it corresponds to bounded variance.Source: §1 · p. 4, §1.1 · p. 5

1.1 Notation and Preliminaries

  • The analysis also gives gradient-mapping complexity guarantees for strongly convex-strongly concave problems and avoids parameters required by.The cited parameters are the initial distance to a solution and a global variance upper bound.Source: §1.1 · p. 6

2 Algorithm & Statement of Main Results

The method combines anchored stochastic extragradient with recursive regularization to solve constrained or regularized monotone problems. It gives gradient-mapping guarantees for strongly monotone and monotone settings, with the monotone result using the Blum-Gladyshev assumption.

2 Algorithm & Statement of Main Results

  • Anchored stochastic extragradient handles nonzero Blum-Gladyshev variance, while reducing to regular stochastic extragradient when the variance parameter B is zero.The recursive-regularization method solves successive strongly monotone subproblems centered at the current iterate, with added strong monotonicity increasing exponentially.Source: §2 · p. 7

2.1 Complexity for Strongly Monotone Problems

  • For strongly monotone problems, the stated oracle-complexity result assumes bounded variance with B = 0; the algorithm’s parameters depend only on the oracle budget, L_F, and μ_F.Unlike the cited unconstrained method, parameter selection does not require the initial distance to a solution or a global variance upper bound.Source: §2.1 · p. 8

2.2 Complexity for Monotone Problems

  • For monotone problems under Assumptions 1 and 2, Algorithm 3 yields an oracle-complexity guarantee by applying the strongly monotone result to a perturbed problem.The perturbation is chosen small enough, depending on the oracle budget, to transfer the guarantee to the original problem’s gradient mapping.Source: §2.2 · p. 8
  • The monotone result requires algorithmic parameters depending only on L_F, the oracle budget T, and B, not on the initial distance to a solution.The paper also notes that a postprocessing step can transfer the guarantee to the stronger tangent residual.Source: §2.2 · p. 8

3 Analysis for Subsolvers

The subsolver analysis pairs anchored stochastic extragradient with restart-based complexity improvements. Anchoring addresses the iterate-dependent variance term, while the restart analysis handles a sequence of strongly monotone subproblems.

3.1 Layer 1: Anchored Stochastic Extragradient

  • The anchored solver is analyzed for strongly monotone problems whose operator changes at each step of the outer algorithm.Because the inner solution changes, its variance-related term cannot be treated as constant and requires specialized analysis.Source: §3.1 · p. 9
  • Anchoring with weight β absorbs the iterate-dependent B_A term in the variance assumption, relaxing the bounded-variance requirement.The method adds a Halpern-type anchoring step to standard extragradient.Source: §3.1 · p. 9

3.2 Layer 2: Restarting for Better Complexity

  • Under Assumption 3 for problem (3.1), running Algorithm 2 from initial point y0 with oracle budget T ≥ 32bLA/µA yields at most T total oracle calls, where bLA = LA + BA.Source: §3.2 · p. 11

4 Complexity Analysis with Bounded Variance

The analysis applies the recursive solver to bounded-variance problems, then treats strongly monotone and monotone cases. For the monotone case, the chosen perturbation yields complexity scaling as ε^-2 up to logarithmic terms.

4 Complexity Analysis with Bounded Variance

  • Algorithm 3 repeatedly calls Algorithm 2 for S stages to analyze the recursively regularized problem.The section uses the resulting bounds to obtain a gradient-mapping guarantee.Source: §4 · pp. 12–13
  • The bounded-variance analysis first handles B = 0; the B ≠ 0 case needs dedicated control of an additional term involving the inner-solution distance.The authors identify that term as absent from prior analyses requiring uniformly bounded variance.Source: §4 · p. 12

4.1 Strongly Monotone Case

  • For strongly monotone F, the algorithmic parameters depend on the oracle budget T, L_F, and µ_F, not the initial distance to a solution or a global variance bound.The theorem assumes B = 0 and strong monotonicity with µ_F > 0.Source: §4.1 · p. 14

4.2 Monotone Case

  • Under Theorem 4.5’s setup, Corollary 4.6 takes T ≥ 2200 and µ = 96L_F log_2(T)/T; this choice yields complexity scaling as ε^-2 up to logarithmic terms.Source: §4.2 · p. 15

5 Complexity Analysis without Bounded Variance

The analysis extends the complexity result beyond bounded variance, requiring only Assumption 2. For monotone problems, the resulting oracle complexity is of order ε^-2 up to logarithmic terms.

5 Complexity Analysis without Bounded Variance

  • The result removes the bounded-variance requirement, extending [CL24, Theorem 4.1] using only Assumption 2.The section analyzes the monotone case; the strongly monotone case can be handled similarly by replacing µ with the operator's strong monotonicity.Source: §5 · p. 16
  • The proof's S-term order could be improved with a more involved analysis, but the authors chose the simpler argument because it affects only logarithmic terms.Source: §5 · p. 17
  • The oracle complexity is of order ε^-2 up to logarithmic terms under Assumptions 1 and 2.Theorem 5.2 applies Algorithm 3 to problem (MI).Source: §5 · pp. 16, 18

6 Auxiliary Lemmas

The auxiliary results connect solutions across regularization levels and bound residuals for the resulting subproblems. They extend prior analyses to regularized settings and gradient mapping guarantees.

6 Auxiliary Lemmas

  • The auxiliary lemmas connect solutions of subproblems at different regularization levels.The solution comparison generalizes [CL24, Lemma A.1] to include the multi-valued mapping ∂r and retains dependence on approximate subproblem-solution quality.Source: §6 · pp. 19–20
  • The analysis extends [CL24, Lemma 3.1] to gradient mapping and regularized subproblems, without relying on minimization-specific descent inequalities.The authors note that the descent lemma used in minimization analyses such as [AZ18, Lemma 5.1] is unavailable here.Source: §6 · p. 21
  • Under Assumption 2, regularized operators retain the same Blum-Gladyshev constants, while their Lipschitz and strong-monotonicity constants are specified by the regularization level.Source: §6 · p. 22
  • The section supplies numerical sufficient conditions for the complexity results without using the Lambert W function to solve the associated inequalities exactly.The authors use a simple sufficient condition instead of finding exact roots.Source: §6 · p. 23

7 Conclusions

The work targets gradient-mapping complexity optimal up to logarithmic terms for constrained convex-concave min-max problems and stochastic VIs. Its construction uses recursive regularization, while simpler algorithms and direct monotone analysis remain research directions.

7 Conclusions

  • The paper obtains gradient-mapping complexity optimal up to logarithmic terms for constrained convex-concave min-max problems or stochastic VIs.Source: §7 · p. 24
  • The construction uses recursive regularization in a three-loop algorithm; achieving the same complexity with a single-loop method remains open, even for minimization.The authors suggest a two-loop construction combining and [AZ18], but say it is unclear whether it would handle the BG assumption.Source: §7 · p. 24
  • The authors identify direct analysis of monotone problems, rather than perturbation by a small µ, as a direction needed for the best gradient-norm guarantee, even in minimization.They also suggest possible extensions to general monotone inclusions and cohypomonotone operators with constraints.Source: §7 · p. 24
Loading 2609.08380v1…