Descriptions may be stale. Consult the linked Lean sources.
Stochastic Smoothed
AGDA under Two-Sided PL
We consider for , where is
a finite-dimensional real inner-product space and 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 with , where , , , and the expectation
includes sampling and algorithm randomness.
The optimization problem is Use the inner-product norms on and , and the product norm . Fix a starting
pair and
parameters The
algorithm receives , , the measurable sample space , all six scalar parameters, and
; 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 and ,
Assumption 2 (Two-sided Polyak–Łojasiewicz
inequalities). For every and , For every , there exists
such that
Assumption 3 (Initial potential). The given starting
pair satisfies
Assumption 4 (Stochastic partial-gradient oracle).
There is a probability distribution on and jointly measurable maps For each fixed and , the random vector is Bochner integrable and its
squared error is integrable under , with A query at any 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 and
. Initialize the
auxiliary point by . With
independent samples , each complete
iteration consists of Thus one complete iteration uses two oracle
calls, with the ascent query made after the descent update. The
parameters and are chosen from
the available inputs.
For the output rule, draw
uniformly from ,
independently of the samples. Given a total call budget , let be the number of
complete iterations. The returned pair is 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 where is the joint law of and the independent oracle samples.