Block Heterogeneous Sgd Upper Bound — Nonconvex Optimization with Heterogeneous Blocks
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Heterogeneous Blocks · Lean proof
Nonconvex
Optimization with Heterogeneous Blocks
We consider minimizing a differentiable, possibly nonconvex function
in
Euclidean dimension . Its
linearization error admits a quadratic bound with a separate coefficient
for each coordinate block, and its value at a given starting point lies
within a prescribed gap of a global lower bound. At each query, the
oracle uses a fresh independent sample to return an unbiased gradient
estimate with blockwise variance bounds. For a tolerance , the goal is a point
at which the
expected sum of the Euclidean norms of the gradient blocks is at most
.
The optimization problem is For
nonnegative integers and , write with . A map assigns each coordinate to a
block. For , let be the orthogonal projection onto
the coordinates in , which
may be empty. The algorithm receives , , , the measurable sample space , the block parameters with and , the gap bound , the tolerance , and the starting point .
Our assumptions:
Assumption 1 (Block smoothness). The function is differentiable everywhere, and for
every ,
Assumption 2 (Initial objective gap). There exists
such that for every and .
Assumption 3 (Stochastic gradients with blockwise
variance bounds). On call at any
, the oracle
returns , where
is jointly measurable. The samples are independent
measurable random variables with common law on , and the sequence is independent
of the algorithm’s randomness. For , every , and every , the vector is Bochner integrable, the
squared norm is integrable, and
After the allotted oracle calls, the output must be measurable and
must be integrable under the joint law of the samples and the
algorithm’s randomness. Under this law, the required accuracy is
Proved result
OracleTemplate.Convergence LongTails.Setups.BlockHeterogeneousNonconvex.spec
LongTails.Theorems.BlockHeterogeneousSgdUpperBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.