Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed
Nonconvex Strongly Concave Optimization
We consider on finite-dimensional real inner product spaces and . The differentiable objective has an -Lipschitz joint gradient and is -strongly concave in , with , while it may be nonconvex
in . Given initial points, an
initial value-gap bound, and an initial dual-gradient bound, the oracle
returns unbiased gradient pairs from independent, identically
distributed samples with bounded centered th moment, . The goal is a measurable
output with
with probability at least ,
where , , and .
Write the objective and optimization problem as Equip with the product norm
The given points are and
. The parameters satisfy
The algorithm
receives , the measurable sample
space , all these parameters,
and ; the objective and
sampling law are accessed through the oracle.
Our assumptions:
Assumption 1 (Smoothness and strong concavity). Both
partial gradients of exist
everywhere. For all , For every and ,
Assumption 2 (Initial bounds). For every and , there exists such that The
initial dual gradient satisfies
Assumption 3 (Heavy-tailed stochastic gradients).
Let be a probability measure on
. The oracle maps are jointly measurable.
At each fixed , both
maps are Bochner integrable under and satisfy Define the paired error by For every
, the random variable is integrable and
The samples are
measurable, mutually independent, and each has law under their joint law. At query , call returns the pair
using the same sample for both components. Algorithm randomness is
independent of the sample sequence.
Queries may be made anywhere in . The output requirement includes the existence of a
maximizing selection
satisfying For every such
selection, the measurable output must satisfy where is the joint law of the
samples and the independent algorithm randomness. Since every maximizing
selection represents , this is
the high-probability stationarity requirement for the value
function.