← All setups

Stochastic Two Sided PLSmoothed Agda — Stochastic Smoothed AGDA under Two-Sided PL

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Smoothed AGDA under Two-Sided PL · Lean proof

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.

Proved result

4⋅⌈218⋅L2μx⋅μy⋅(3+224⋅L⋅σ2μx⋅μy⋅ε)⋅(2+log⁡(1+Δε))⌉++2

OracleTemplate.Convergence LongTails.Setups.StochasticTwoSidedPL.spec OracleTemplate.StochasticTwoSidedPL.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.