← All setups

Stochastic Smoothed AGDA under Two-Sided PL

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Smoothed AGDA under Two-Sided PL

We consider infx∈Esupy∈Ff(x,y) for f:E×F→R, where E is a finite-dimensional real inner-product space and F is a separable real Hilbert space. The partial gradients are jointly Lipschitz and satisfy two-sided Polyak–Łojasiewicz inequalities; each inner maximum is attained, and the given initial pair satisfies a bounded potential condition. Each oracle call returns an unbiased, bounded-variance estimate of one partial gradient using a fresh independent sample. Stochastic smoothed alternating gradient descent–ascent (AGDA) must return (x¯,y¯) with E[2Φ(x¯)−Φ∗−f(x¯,y¯)]≤ε, where Φ(x)=supy∈Ff(x,y), Φ∗=infx∈EΦ(x), ε>0, and the expectation includes sampling and algorithm randomness.

The optimization problem is infx∈Esupy∈Ff(x,y). Use the inner-product norms on E and F, and the product norm ∥(x,y)∥1=∥x∥+∥y∥. Fix a starting pair (x0,y0)∈E×F and parameters 0<μx≤L,0<μy≤L,σ≥0,Δ≥0,ε>0. The algorithm receives E, F, the measurable sample space Ω, all six scalar parameters, and (x0,y0); the objective and the sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Partial-gradient smoothness). Each partial function is Fréchet differentiable everywhere. For all x,x′∈E and y,y′∈F, ∥∇xf(x,y)−∇xf(x′,y′)∥≤L(∥x−x′∥+∥y−y′∥),∥∇yf(x,y)−∇yf(x′,y′)∥≤L(∥x−x′∥+∥y−y′∥).

Assumption 2 (Two-sided Polyak–Łojasiewicz inequalities). For every x,x′∈E and y,y′∈F, 2μx(f(x,y)−f(x′,y))≤∥∇xf(x,y)∥2,2μy(f(x,y′)−f(x,y))≤∥∇yf(x,y)∥2. For every x∈E, there exists yx∈F such that f(x,y′)≤f(x,yx)for every y′∈F.

Assumption 3 (Initial potential). The given starting pair satisfies 2Φ(x0)−Φ∗−f(x0,y0)+∥∇xf(x0,y0)∥2L≤Δ.

Assumption 4 (Stochastic partial-gradient oracle). There is a probability distribution ν on Ω and jointly measurable maps Gx:(E×F)×Ω→E,Gy:(E×F)×Ω→F. For each fixed w=(x,y) and a∈{x,y}, the random vector Ga(w,ξ) is Bochner integrable and its squared error is integrable under ξ∼ν, with Eξ∼ν[Ga(w,ξ)]=∇af(w),Eξ∼ν[∥Ga(w,ξ)−∇af(w)∥2]≤σ2. A query at any w∈E×F selects either partial gradient and returns the corresponding estimate. Calls use independent samples with common distribution ν, independent of the algorithm’s randomness.

Our result is algorithm-specific: we analyze stochastic smoothed AGDA. Its tuning parameters are r,τx,τy,β∈R and n∈N0. Initialize the auxiliary point by z0=x0. With independent samples ξ0,ξ1,…∼ν, each complete iteration consists of gxt=Gx((xt,yt),ξ2t),xt+1=xt−τx(gxt+r(xt−zt)),gyt=Gy((xt+1,yt),ξ2t+1),yt+1=yt+τygyt,zt+1=zt+β(xt+1−zt). Thus one complete iteration uses two oracle calls, with the ascent query made after the descent update. The parameters and n are chosen from the available inputs.

For the output rule, draw J uniformly from {0,…,n}, independently of the samples. Given a total call budget B∈N0, let T=⌊B/2⌋ be the number of complete iterations. The returned pair is (x¯,y¯)={(xn+J,yn+J),1≤n+J≤T,(x0,y0),otherwise. An unmatched final descent call does not change the returned pair.

The output must be measurable, its combined primal suboptimality and inner-maximization error must be integrable, and it must satisfy EP[(Φ(x¯)−Φ∗)+(Φ(x¯)−f(x¯,y¯))]≤ε, where P is the joint law of J and the independent oracle samples.

Results

Real inner-product spaces E,F, with E finite-dimensional and F complete and second-countable, carry their Borel structures. Partial gradients are L-Lipschitz in ∥x−x′∥+∥y−y′∥; f(⋅,y) and −f(x,⋅) satisfy PL inequalities against every competitor, with 0<μx,μy≤L. Every maximization in y is attained. Jointly measurable partial-gradient oracles are unbiased, integrable, and have integrable squared errors of expectation at most σ2; calls use independent samples with common probability law p. The setup restricts algorithms to stochastic Smoothed-AGDA. Given σ,Δ≥0 and ε>0, the target is ∫[Φ(x^)−Φ∗+Φ(x^)−f(x^,y^)]dP≤ε, with measurable output and integrable gap; P includes the sample stream and output randomization.

Stochastic two-sided PL minimax optimization: StochasticTwoSidedPL.
Result Oracle complexity Novelty Limitations
(1) StochasticTwoSidedPLSmoothedAgda (Ours) (review) O([L2μxμy+L3σ2μx2μy2ε]ℓ)
(2) Derived bound: restarted Smoothed-AGDA (Yang et al. 2022), Thm. 4.1 plus two-sided PL; Euclidean spaces

O(L2ℓμxμy+L3σ2μx2μy2ε)

Conditional on deterministic expected-gap bounds remaining valid at random restart points.

(1): Matches deterministic rate; extends F to Hilbert space. Single-run potential-PL analysis and formalization; no complexity gain on the Euclidean overlap. (1): Extra factor ℓ in the noise term, conditional on the stated restart bounds.
(3) Stoc-AGDA (Yang et al. 2020), Thm. 3.3; Euclidean spaces, attained minima and a saddle point O(1+L3D0μxμy2ε+L5σ2μx2μy4ε) (1): Noise term smaller by κy2/ℓ when ℓ<κy2, for the shared expected-gap target; not an identical-output speedup. (1): Random second-half iterate instead of last iterate; needs σ,ε,Δ in addition. Its initialization bound includes ∥∇xf(x0,y0)∥2/L.
(4) Warm-started Stoc-AGDA (Yang et al. 2020), Thms. 3.1, 3.3 and Remark 3; Euclidean spaces, attained minima and a saddle point

O(L3ℓμxμy2+L5σ2μx2μy4ε)

Includes the constant-step warm start; uses the common initial bound D0≤Δ.

(1): Deterministic term κxκyℓ instead of κxκy2ℓ; noise gain κy2/ℓ when ℓ<κy2. (1): Random iterate instead of last iterate. Noise term loses when ℓ>κy2; no uniform dominance.
(5) FESS-GDA (Shen et al. 2024), Thm. 3.5, M=1; Euclidean spaces, attained minima and a saddle point Distance target: E[∥xT−x∗∥2+∥yT−y∗∥2]≤δ2. Rates are not comparable to the gap target. (1): Scope: no saddle-point existence assumption. No established complexity comparison across these accuracy criteria. (1): Does not provide the distance guarantee of (5).

Abbr: Φ(x)=maxyf(x,y), Φ∗=infxΦ(x); D0=2Φ(x0)−Φ∗−f(x0,y0); Δ≥D0+∥∇xf(x0,y0)∥2/L; ℓ=1+log⁡(1+Δ/ε); κx=L/μx, κy=L/μy. Costs count individual partial-gradient calls, including calls to each branch. δ is distance accuracy, (x∗,y∗) a saddle point, and M the client count.

Shen, Wei, Minhui Huang, Jiawei Zhang, and Cong Shen. 2024. Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimization. https://doi.org/10.48550/arXiv.2311.00944.
Yang, Junchi, Negar Kiyavash, and Niao He. 2020. “Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems.” Advances in Neural Information Processing Systems 33: 1153–65. https://proceedings.neurips.cc/paper/2020/hash/0cc6928e741d75e7a92396317522069e-Abstract.html.
Yang, Junchi, Antonio Orvieto, Aurelien Lucchi, and Niao He. 2022. “Faster Single-Loop Algorithms for Minimax Optimization Without Strong Concavity.” Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, Proceedings of machine learning research, vol. 151: 5485–517. https://proceedings.mlr.press/v151/yang22b.html.

Lean setup