← All setups

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 f:Rd→R in dimension d. 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 ε>0, 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 infx∈Rdf(x). A map b:{1,…,d}→{1,…,B} assigns each coordinate to a block. Write Ij={i:b(i)=j} and let Πj be the orthogonal projection onto the coordinates in Ij. The algorithm receives the integers d,B≥1, the map b, the block parameters Lj>0 and σj≥0 for 1≤j≤B, the gap bound Δ>0, the tolerance ε, and the starting point x0∈Rd.

Our assumptions:

Assumption 1 (Scale and block dimensions). Write S=∑i=1BLi and T=∑i=1B(Liσi2)1/3. Every block j satisfies LjΔ≥257ε2,|Ij|≥240(1+BSΔε2+T3Δε4)4.

Assumption 2 (Blockwise quadratic bound and initial gap). The function f is differentiable throughout Rd. For all x,h∈Rd, |f(x+h)−f(x)−⟨∇f(x),h⟩|≤12∑j=1BLj∥Πjh∥22. There exists ℓ∈R such that f(x)≥ℓ for every x∈Rd and f(x0)−ℓ≤Δ.

Assumption 3 (Stochastic gradient oracle). At each query x∈Rd, the oracle returns g(x,ξk), where k indexes the call and g:Rd×R→Rd is jointly Borel measurable. The real random variables (ξk)k≥1 are independent with common law ν, and the sequence is independent of the algorithm’s randomness. For ξ∼ν, write e(x,ξ)=g(x,ξ)−∇f(x). At every x, the vector g(x,ξ) is Bochner integrable, each ∥Πje(x,ξ)∥22 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥Πje(x,ξ)∥22]≤σj2,1≤j≤B.

After the allotted oracle calls, the output x¯∈Rd must be measurable under the joint law P of the algorithm’s randomness and the oracle samples. The stationarity measure ∑j=1B∥Πj∇f(x¯)∥2 must be integrable under P and satisfy EP[∑j=1B∥Πj∇f(x¯)∥2]≤ε.

Proved result

⌊(∑j=0B−1L(j))⋅Δε2+((∑j=0B−1(L(j)⋅σ(j)2)13))3⋅Δε4257⌋+

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.