PaperlayerView exact revision on arXiv

Source-linked AI summary

The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization

Tianxi Zhu, Yi Xu, Xiangyang Ji

arXiv:2609.06064v1math.OCcs.AIstat.ML

TL;DR

Existing min-max analyses under heavy-tailed noise have largely relied on clipping or normalization, and convergence of vanilla SGDA remained unresolved. This paper studies vanilla SGDA in NC-SC and NC-C settings and develops clipping-free methods for regularized min-max optimization. It establishes SGDA convergence guarantees and gives regularized methods with optimal dependence on target accuracy without clipping.

  • Problem

    Existing heavy-tailed min-max studies do not establish convergence for classical methods such as SGDA and do not address regularized min-max problems.

    Source: §1.2 · p. 5

  • Method

    The paper analyzes vanilla SGDA in NC-SC and NC-C settings and proposes Stoc-TRGDAM and Stoc-TRGDAmax for regularized min-max problems.

    Source: §1.1 · p. 4, §5 · p. 18

  • Results

    Vanilla SGDA has convergence guarantees in both settings, and the proposed regularized methods achieve optimal dependence on target accuracy without clipping.

    Source: §5 · p. 18

  • Takeaways & Limitations

    Gradient clipping is not necessary for the stated SGDA convergence guarantees or for the proposed regularized methods’ optimal accuracy dependence.

    Source: §5 · p. 18

    The lower-bound construction does not determine the complexity lower bound’s dependence on parameters such as κ and σ.

    Source: §3.1 · p. 8

Abstract

from arXiv · show

Stochastic min-max optimization has attracted increasing attention due to its applications in modern machine learning, while existing theoretical studies mainly rely on the bounded variance assumption for stochastic gradients. Under heavy-tailed noise, where stochastic gradients only possess a finite $p$-th moment for $p\in(1,2]$, gradient clipping or normalization is commonly believed to be necessary to guarantee convergence. In this work, we revisit stochastic min-max optimization under heavy-tailed noise and provide a comprehensive theoretical study of stochastic gradient descent ascent (SGDA). We first show that vanilla SGDA, without any modification to its update rule, can converge under heavy-tailed noise in both nonconvex-strongly-concave (NC-SC) and nonconvex-concave (NC-C) settings, establishing the first convergence guarantees for SGDA in these regimes. Beyond unregularized problems, we further investigate regularized stochastic min-max optimization, where directly incorporating gradient normalization into proximal updates is nontrivial due to the incompatibility between normalization and proximal structures. We overcome this difficulty by developing new clipping-free algorithms, i.e., Stoc-TRGDAM and Stoc-TRGDmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.

1 Introduction

Prior min-max work under heavy-tailed noise used clipping or normalization, leaving open whether vanilla SGDA converges; heavy-tailed noise may have infinite variance when p < 2. The paper establishes SGDA convergence results in NC-SC and NC-C settings and develops clipping-free methods for regularized problems.

1 Introduction

  • Prior min-max studies used clipping or normalization, leaving vanilla SGDA’s convergence under heavy-tailed noise unresolved.The noise assumption permits infinite variance when p < 2.Source: §1 · p. 2, §1.2 · p. 5

1.1 Contributions

  • Vanilla min-batch SGDA converges in the NC-SC setting under heavy-tailed noise, providing an upper-bound result for this regime.The contribution section identifies this as the first such upper bound for vanilla SGDA.Source: §1.1 · p. 4
  • Stoc-TRGDAM and Stoc-TRGDAmax address regularized NC-SC problems without clipping and achieve optimal dependence on target accuracy.Stoc-TRGDAM is single-loop with batch-size O(1); Stoc-TRGDAmax is nested-loop.Source: §1.1 · p. 4
  • In NC-C problems, SGDA’s complexity matches that of a clipping-based method, while clipping can yield a stronger convergence measure.The result covers a broader setting with an indicator regularizer on an unbounded closed convex set and a general closed convex h.Source: §1.1 · p. 4

1.2 Related Work

  • Prior heavy-tailed min-max studies had not established convergence of classical gradient methods such as SGDA or addressed regularized min-max problems.The paper positions these as two limitations of existing studies.Source: §1.2 · p. 5

2 Preliminaries

This section fixes notation, states the stochastic-oracle assumptions, and specifies SGDA's update framework for min-max problems.

2 Preliminaries

  • Asymptotic notation uses ≲, ≳, ≍ and O, Ω, Θ, while Õ suppresses polynomial logarithmic factors.The paper uses the standard Euclidean inner product.Source: §2 · p. 5
  • The notation uses Euclidean norms and distinguishes the full gradient ∇f from the partial gradients ∇xf and ∇yf.It also defines subdifferentials, projection operators, and closed balls.Source: §2 · p. 5
  • The primal objective is Φ(x)=max_y{f(x,y)−h(y)}, Ψ(x)=Φ(x)+r(x), and Φ is assumed lower bounded.When the maximizer is unique, y⋆(x) denotes the maximizer of f(x,y)−h(y).Source: §2 · pp. 5–6
  • SGDA simultaneously takes a stochastic descent step in x and an ascent step in y using sampled gradients.The algorithm specifies mini-batches for the unregularized case and separate updates for constrained or regularized cases.Source: §2 · p. 6
  • The analysis assumes L-smooth f, unbiased stochastic partial-gradient estimators, and bounded p-th central moments for both partial gradients, with p∈(1,2].The p-th moment bound is stated for p∈(1,2] and a finite σ.Source: §2 · p. 6

3 Convergence of SGDA under heavy-tailed noise

This section studies convergence of vanilla SGDA under heavy-tailed noise in NC-SC and NC-C settings, without gradient clipping or normalization, and notes limits of available lower bounds and proof techniques. Its proof sketch for Theorem 3.6 combines an inequality specialized to the optimizer with subsequence arguments and moment bounds under suitable step sizes.

3.1 NC-SC min-max problems

  • In NC-SC, vanilla SGDA achieves O(ε^(-2p/(p-1))) complexity under heavy-tailed noise, with step-size ratio Θ(κ^2) independent of p.The authors present this as the first SGDA complexity result for p < 2 in NC-SC; the same complexity is argued to be unimprovable for SGDA based on results for SGD.Source: §3.1 · pp. 7–8
  • The NC-SC lower bound extends a variance-bounded result to heavy-tailed noise, but its κ dependence is Ω(κ^1/3) and does not adapt to p.The authors note that this leaves a gap from the best known O(κ) dependence for SAPD+ under light-tailed noise and from the O(κ^1/3) dependence in.Source: §3.1 · pp. 7–8

3.2 NC-C min-max problems

  • For NC-C, Theorem 3.6 gives the first SGDA complexity upper bound under heavy-tailed noise when p < 2; at p = 2, O(∆1D_Y^2L^3(σ^4 ∨ G^2σ^2)ε^-8) matches [LJJ20]’s light-tailed result.Source: §3.2 · p. 9
  • In NC-C, vanilla SGDA matches SGDAClip’s ε-complexity without clipping or extra assumptions, while clipping improves convergence from expectation to high probability.The paper also says its dependence on σ and bδ1 is tighter; Table 1 is identified as the comparison source.Source: §3.2 · p. 10, Table 1 · p. 10

3.3 Proof sketches of Theorem 3.3 and Theorem 3.6

  • The proof handles potentially infinite second moments by raising inequalities to p/2 and bounding martingale sums; mini-batches are needed because the variance term is uncontrolled at batch size one.For NC-C, the analysis uses a descent inequality for the Moreau envelope and accommodates a general closed convex x-constraint without requiring it to be bounded.Source: §3.3 · pp. 11–12
  • The proof first obtains an inequality for any F_{t−2}-measurable y and notes the specialization y=y⋆.Source: §3.3 · p. 12
  • The proof excerpt organizes terms into subsequences indexed by n=0,…,N−1.Source: §3.3 · p. 12
  • Theorem 3.6’s proof combines the preceding pieces and chooses appropriate step sizes to complete the argument.The cited proof excerpt specifies p∈(1,2].Source: §3.3 · p. 12

4 (Stoc-)TRGDA for NC-SC regularized min-max problems

The section develops clipping-free trust-region methods for regularized NC-SC min-max optimization under heavy-tailed noise, targeting the optimal accuracy dependence. It explains why direct normalized proximal updates are problematic and presents two Stoc-TRGDA variants with different complexity trade-offs.

4.1 How to incorporate normalized gradient into SPGD?

  • The two natural normalized-proximal approaches have analytical limitations: one breaks the proximal fixed-point property, while the other has a subgradient-difference term that is difficult to bound for merely convex r.The authors therefore reject both approaches, including in deterministic settings.Source: §4.1 · p. 13
  • TRGM replaces the proximal quadratic penalty with a step-radius constraint, reduces to NGD when r is constant, and motivates the stochastic TRGDA framework.The theorem characterizes the constrained minimizer and relates it to a computable approximation of a normalized composite-gradient step.Source: §4.1 · pp. 13–14

4.2 Two variants of Stoc-TRGDA

  • O(ϵ^−(3p−2)/(p−1)) complexity matches the general first-order lower bound, and Stoc-TRGDAM is the first single-loop method with optimal complexity for regularized NC-SC min-max optimization under heavy-tailed noise.It uses no gradient-clipping technique.Source: §4.2 · p. 15
  • Stoc-TRGDAM has better ϵ-complexity than SGDA for 1 < p < 2, while its κ-dependence is better for p ∈ (1, 4/3) and worse for p ∈ [4/3, 2].With unknown Λ1, L, σ, and p, Stoc-TRGDAM reaches O(ϵ^−2p/(p−1)); SGDA requires adjusting batch size through p to reach that complexity.Source: §4.2 · p. 16
  • Stoc-TRGDAmax improves dependence on κ over Stoc-TRGDAM for p ≤ 2, but requires a mini-batch for x and a sufficiently accurate initial y for a bound without logarithmic factors.For p = 2 and ϵ < 2Lδ1, its result reduces to e O(κ^3ϵ^−4), matching the cited light-tailed SGDAmax result.Source: §4.2 · p. 16
  • Stoc-TRGDAmax matches N2SBA’s stated complexity, while N2SBA still clips the y-gradient; Stoc-TRGDAmax can omit logarithmic factors when its initial y is sufficiently accurate.Table 2 summarizes methods for heavy-tailed stochastic minimax optimization in NC-SC or NC-PL settings and indicates clipping use for x and y.Source: §4.2 · p. 17, Table 2 · p. 17

4.3 Proof sketches of Theorems 4.2 and 4.3

  • The proof sketch for Stoc-TRGDAM constructs a potential and derives a descent inequality when ηy/ηx ≍ κ; its estimator-deviation terms need not rely on unbiasedness.The sketch identifies the estimator error as the deviation between the true gradient and the chosen estimator, including momentum.Source: §4.3 · p. 17

5 Conclusion and Future work

The paper establishes vanilla SGDA convergence under heavy-tailed noise in NC-SC and NC-C settings, with NC-SC suboptimality motivating clipping-free algorithms for regularized problems. It also identifies unresolved complexity and scope questions.

Conclusion

  • Vanilla SGDA converges without modifying stochastic gradients in both NC-SC and NC-C settings, matching clipping-based methods in NC-C but remaining suboptimal in NC-SC.The NC-SC result motivates new algorithms for regularized min-max problems.Source: §5 · p. 18
  • Stoc-TRGDAM and Stoc-TRGDAmax achieve optimal dependence on target accuracy for regularized min-max problems without clipping thresholds.The paper notes that gradient normalization interacts nontrivially with proximal structures.Source: §5 · p. 18

Limitations

  • The lower-bound dependence on κ does not match the upper bound, leaving uncertainty about whether the resulting complexity is loose in κ.The paper also lacks a single-loop method that needs no batch size while achieving the stated NC-SC complexity.Source: §5 · p. 18

Future work

  • Future work includes extending the techniques to stochastic bilevel optimization, adaptive step sizes, and settings such as nonconvex-weakly-concave problems.Stochastic min-max optimization encompasses bilevel optimization as a special case.Source: §5 · p. 18

A.1 Proof of Theorem 3.3

The proof develops one-step SGDA inequalities under Case I conditions, then combines smoothness bounds and heavy-tailed moment control to establish the theorem's convergence analysis.

A.1 Proof of Theorem 3.3

  • For Case I, the proof states one-iteration SGDA inequalities under step-size restrictions involving ηx, ηy, κ, and L.The supplied lemma statements include ηx ≤ 1/(8κL) and ηy ≤ 1/(2L) as conditions for bounds.Source: §A.1 · pp. 23, 26, 27
  • Smoothness, Cauchy-Schwarz, and Young's inequality are used to derive a descent inequality for the dual objective Φ.The proof then sums the inequality over iterations.Source: §A.1 · p. 24
  • The analysis controls stochastic-gradient noise using its finite p-th moment and expectation inequalities.The passage states E[∥ζx,t∥^p] ≤ σ^p.Source: §A.1 · p. 25
  • The proof recursively combines and sums the one-step bounds before completing the argument.The displayed steps raise inequalities to p/2 and take expectations.Source: §A.1 · pp. 27–29

A.1.1 Prove the complexity

The complexity proof selects step sizes, accounts for batch-dependent noise moments, and derives a gradient-complexity upper bound under an additional small-accuracy condition.

A.1.1 Prove the complexity

  • The proof sets ηx = 1/(1156κ^2L) and ηy = 1/(2L) for its complexity argument.Source: §A.1.1 · p. 29
  • The stochastic-gradient noise moment is bounded by 2σ^p/B^(p−1) for batch size B.The same analysis is stated to apply to both x- and y-gradient noise.Source: §A.1.1 · p. 30
  • Under an additional small-ϵ condition, the proof derives an upper bound on total gradient complexity.Source: §A.1.1 · p. 30

A.2 Proof of Theorem 3.6

The NC-C proof uses proximal and smoothness properties to establish inequalities for SGDA, then sums them to obtain a gradient-complexity bound.

A.2 Proof of Theorem 3.6

  • For NC-C, the proof establishes SGDA inequalities using concavity in y, smoothness, and the proximal update.The analysis also invokes boundedness of dom(h) and weak convexity of Φ.Source: §A.2 · pp. 31–33
  • The proof aggregates per-iteration inequalities across windows and uses the resulting bounds to establish the theorem argument.Its steps include a decomposition involving Φ(x) and the approximate dual solution value.Source: §A.2 · pp. 31, 34, 35

A.2.1 Prove the complexity

  • The complexity argument chooses iteration-dependent step sizes and derives an upper bound on total gradient complexity.The proof states an additional condition involving σ, L, D_Y, and ϵ before giving the bound.Source: §A.2.1 · pp. 35–37

A.3 Proof of Theorem 3.4

The proof builds a heavy-tailed stochastic-oracle hard instance to establish an iteration lower bound for zero-respecting algorithms. Its construction uses a probability-q zero-chain and an interleaved arrangement of minimization and maximization variables.

A.3 Proof of Theorem 3.4

  • A probability-q zero-chain reveals at most the next coordinate of the stochastic gradient support, with a probability bound q on revealing beyond the current coordinates.The construction also constrains the algorithm's iterates to coordinates exposed by prior iterates and oracle outputs.Source: §A.3 · p. 38
  • The hard instance decomposes the minimization variable into x and z and arranges these with maximization-variable blocks in an interleaved coordinate sequence.The instance is adapted from and its stated properties are used to obtain the lower bound.Source: §A.3 · p. 38
  • The proof modifies a zero-chain construction's stochastic oracle to satisfy the heavy-tailed noise assumption.The oracle uses a Bernoulli random variable, and the passage states that its p-th central moment is bounded.Source: §A.3 · p. 39
  • The proof gives an iteration lower bound for finding an ε-stationary point with a first-order zero-respecting algorithm.The displayed lower-bound rate is incomplete in the supplied passage.Source: §A.3 · pp. 39–40

B.1 Proof of Theorem 4.1

The proof uses convex-analysis lemmas to justify subgradient relations for constrained composite objectives. A relative-interior qualification is required for the subgradient sum rule.

B.1 Proof of Theorem 4.1

  • Under the relative-interior condition, a subgradient of the function plus the set indicator implies a nonempty subdifferential for the function itself.The indicator is defined for the constraint set.Source: §B.1 · p. 40
  • The relative-interior condition is necessary: the example with f(x) = -√x and X = {0} has a nonempty constrained subdifferential but an empty subdifferential for f at 0.The passage gives ∂(f + δX)(0) = (-∞, +∞) and ∂f(0) = ∅.Source: §B.1 · p. 40
  • The subgradient sum rule for a convex function and a set indicator requires their domains' relative interiors to intersect.The proof uses this condition to relate subgradients of the constrained objective to those of its components.Source: §B.1 · pp. 40–41
  • For a proper closed convex regularizer, minimizing a linearized regularized objective over a ball yields a point with a nonempty regularizer subdifferential and a corresponding normal-cone optimality relation.The proof establishes the relation using the ball constraint and convex-analysis lemmas.Source: §B.1 · p. 41

B.2 Proof of Theorem 4.2

The proof analyzes one iteration of TR-SGDAM and derives a gradient-complexity bound for attaining an average composite-stationarity target. Its trust-region step is presented as a composite analogue of gradient normalization.

B.2 Proof of Theorem 4.2

  • The trust-region gradient method generalizes gradient normalization to composite optimization, and its linearized regularized subproblem has a solution characterized by a subgradient relation.The proof uses this relation in its one-iteration analysis of TR-SGDAM.Source: §B.2 · p. 42
  • The proof establishes one-iteration inequalities for TR-SGDAM under Assumptions 1(a) and 2.The accompanying steps relate primal and maximization-variable updates to function changes and gradient-estimation errors.Source: §B.2 · pp. 42–43

B.2.1 Prove the complexity

  • The complexity analysis controls the accumulated estimation errors using unbiased stochastic gradients and finite first moments under the stated assumptions.The proof bounds the expected error terms for both x and y updates.Source: §B.2.1 · pp. 44–45
  • The complexity proof bounds total gradient calls to attain an average composite-stationarity distance of at most ε.The supplied passages state that the complexity is upper bounded but do not include the bound's full expression.Source: §B.2.1 · p. 46

B.3 Proof of Theorem 4.3

The proof controls the maximization-variable iterates and derives a gradient-complexity bound for the regularized nonconvex-concave setting. Supplementary martingale and norm inequalities support the analysis.

B.3 Proof of Theorem 4.3

  • The inner maximization analysis uses proximal-operator nonexpansiveness and the smoothness and strong concavity of the objective in y.The proof temporarily separates the outer loop while relating the iterate to the maximizer.Source: §B.3 · pp. 47–48
  • The proof controls the distance from the maximization iterates to the maximizer using a contraction factor chosen according to the initial distance regime.The passages distinguish initial-error cases below and above the stated threshold.Source: §B.3 · pp. 49–50

B.3.1 Prove the complexity

  • The complexity proof bounds total gradient calls for an average composite-stationarity target, with separate cases for the ε regimes shown.The supplied bound expressions are incomplete.Source: §B.3.1 · p. 51

C Supplementary Lemmas

  • The supplementary lemmas provide inequalities for p-moment martingale sequences and vectors used in the stochastic analysis.The cited lemmas cover scalar and vector martingales for p in [1, 2].Source: C Supplementary Lemmas · p. 53
Loading 2609.06064v1…