← All setups

High-Dimensional Blockwise Stochastic Stationarity

Descriptions may be stale. Consult the linked Lean sources.

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]≤ε.

Results

On Rd with B≥1 coordinate blocks, f(x0)−inff≤Δ and |f(x+h)−f(x)−⟨∇f(x),h⟩|≤12∑jLj∥Pjh∥22 for all x,h. Each call returns a jointly measurable, unbiased gradient estimate g(x,ξ) using a fresh i.i.d. real sample, with E∥Pj(g(x,ξ)−∇f(x))∥22≤σj2. The target is E∑j∥Pj∇f(x^)∥2≤ε. For (1), each block satisfies 257ε2≤LjΔ and dj≥240(1+BD+V)4, with ε,Lj>0 and σj≥0.

High-dimensional block-heterogeneous nonconvex optimization: lower bounds on necessary gradient calls.
Result Oracle complexity Novelty Limitations
(1) BlockHeterogeneousLowerBound (Ours) (⋆⋆⋆) (review) Ω(∥L∥1Δε2+S3Δε4)
(2) (Arjevani et al. 2022), Thm. 3 and Sec. 1.3 Ω(maxjLjΔε2(1+σj2ε2)). Derived bound, one active high-dimensional block. (1): Equal Lj,σj amplify the deterministic term by B and the noise term by B3 over (2). Same order when one block dominates the sums. (1) needs the accuracy and dimension conditions in every block. (2) needs sufficient dimension and ε≲LjΔ only in the active block.
(3) (Jiang et al. 2025), Thm. 5 Ω(∥L∥1Δ/ε2). Deterministic algorithms, exact gradients, scalar blocks. (1) retains the noiseless order for every randomized algorithm on high-dimensional blocks. With noise, its additional term dominates when S3>ε2∥L∥1. (1) requires large blocks and small ε in every block. Its noiseless prefactor is 2−57, versus 1 in (3) for the strict target ∥∇f∥1<ε.
(4) AdaGrad (Jiang et al. 2025), Thm. 4 Ω((D+V)log⁡(1+D+V)) as ε↓0 at fixed problem parameters. Scalar blocks, δ=0, best queried iterate. (1) establishes the same polynomial dependence for arbitrary randomized algorithms and outputs on high-dimensional blocks, matching the block-SGD upper bound there up to constants. (1) excludes scalar blocks. The AdaGrad-specific lower bound in (4) has an additional logarithmic factor.

Abbr: Pj projects onto block j of dimension dj; ∥L∥1=∑jLj, S=∑j(Ljσj2)1/3, D=∥L∥1Δ/ε2, V=S3Δ/ε4. In (4), δ is the AdaGrad denominator offset.

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. 2022. Lower Bounds for Non-Convex Stochastic Optimization. https://doi.org/10.48550/arXiv.1912.02365.
Jiang, Ruichen, Devyani Maladkar, and Aryan Mokhtari. 2025. “Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization.” In Proceedings of Thirty Eighth Conference on Learning Theory, edited by Nika Haghtalab and Ankur Moitra, vol. 291. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v291/jiang25c.html.

Lean setup