← All setups

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 f:Rd→R in Euclidean 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. At each query, the oracle uses a fresh independent sample to return an unbiased gradient estimate with blockwise variance bounds. For a tolerance ε>0, the goal is a point x¯∈Rd at which the expected sum of the Euclidean norms of the gradient blocks is at most ε.

The optimization problem is infx∈Rdf(x). For nonnegative integers d and B, write [n]={1,…,n} with [0]=∅. A map b:[d]→[B] assigns each coordinate to a block. For j∈[B], let Πj be the orthogonal projection onto the coordinates in b−1(j), which may be empty. The algorithm receives d, B, b, the measurable sample space Ω, the block parameters (Lj,σj)j∈[B] with Lj>0 and σj≥0, the gap bound Δ≥0, the tolerance ε, and the starting point x0∈Rd.

Our assumptions:

Assumption 1 (Block smoothness). The function f is differentiable everywhere, and for every x,y∈Rd, |f(y)−f(x)−⟨∇f(x),y−x⟩|≤12∑j∈[B]Lj∥Πj(y−x)∥2.

Assumption 2 (Initial objective gap). There exists ℓ∈R such that f(x)≥ℓ for every x∈Rd and f(x0)−ℓ≤Δ.

Assumption 3 (Stochastic gradients with blockwise variance bounds). On call k at any x∈Rd, the oracle returns g(x,ξk), where g:Rd×Ω→Rd is jointly measurable. The samples (ξk)k≥0 are independent measurable random variables with common law ν on Ω, and the sequence is independent of the algorithm’s randomness. For ξ∼ν, every x∈Rd, and every j∈[B], the vector g(x,ξ) is Bochner integrable, the squared norm ∥Πj(g(x,ξ)−∇f(x))∥2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥Πj(g(x,ξ)−∇f(x))∥2]≤σj2.

After the allotted oracle calls, the output x¯ must be measurable and ∑j∈[B]∥Πj∇f(x¯)∥ must be integrable under the joint law of the samples and the algorithm’s randomness. Under this law, the required accuracy is E[∑j∈[B]∥Πj∇f(x¯)∥]≤ε.

Proved result

⌈8⋅(∑j=0B−1L(j))⋅Δε2+20⋅((∑j=0B−1(L(j)⋅σ(j)2)13))3⋅Δε4⌉++1

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.