Block Heterogeneous Lower Bound — High-Dimensional Blockwise Stochastic Stationarity
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Blockwise Stochastic Stationarity · Lean proof
High-Dimensional
Blockwise Stochastic Stationarity
We seek a stationary point of a differentiable, possibly nonconvex
function in 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. Each block has a prescribed minimum dimension. At
any query point, the oracle returns an unbiased gradient estimate from a
fresh independent real sample, with bounded mean squared error in each
block. For tolerance , the goal is a
measurable output whose sum of Euclidean block-gradient norms has
expectation at most
over algorithm and oracle randomness.
The underlying optimization problem is A map
assigns each coordinate to a block. Write and let be the orthogonal projection onto
the coordinates in . The
algorithm receives the integers , the map , the block
parameters and for , the gap bound , the tolerance , and the starting point .
Our assumptions:
Assumption 1 (Scale and block dimensions). Write
and .
Every block satisfies
Assumption 2 (Blockwise quadratic bound and initial
gap). The function is
differentiable throughout . For all , There exists
such that for every and .
Assumption 3 (Stochastic gradient oracle). At each
query , the oracle
returns , where indexes the call and
is jointly Borel measurable. The real random variables are independent with
common law , and the sequence is
independent of the algorithm’s randomness. For , write . At every
, the vector is Bochner integrable, each
is
integrable, and
After the allotted oracle calls, the output must be measurable
under the joint law of the
algorithm’s randomness and the oracle samples. The stationarity measure
must be integrable under and satisfy
Proved result
OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalBlockHeterogeneousNonconvex.spec
LongTails.Theorems.BlockHeterogeneousLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.