← All setups

Nonconvex Optimization with Heterogeneous Blocks

Descriptions may be stale. Consult the linked Lean sources.

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

Results

Let Pj project onto coordinate block j of Rd. The differentiable objective satisfies f(x0)−inff≤Δ and, for all x,h, |f(x+h)−f(x)−⟨∇f(x),h⟩|≤12∑j=1BLj∥Pjh∥22, with Lj>0. Each call returns a jointly measurable, integrable full gradient estimate g(x,ξ) from a fresh IID sample, with Eg(x,ξ)=∇f(x) and E∥Pj(g(x,ξ)−∇f(x))∥22≤σj2, σj≥0. The target is E∑j∥Pj∇f(x^)∥2≤ε, ε>0.

Sufficient stochastic-gradient budgets for block-heterogeneous nonconvex optimization.
Result Oracle complexity Novelty Limitations
(1) BlockHeterogeneousSgdUpperBound (Ours) (⋆⋆) (review) O(1+∥L∥1Δε2+ΔS3ε4)
(2) Scalar-step SGD (Ghadimi and Lan 2013)
Derived bound
O(1+BLmaxΔε2+B2Lmax∥σ∥22Δε4) (1) replaces BLmax by ∑jLj and B2Lmax∥σ∥22 by S3. For B=1, the rates match. (1) needs individual block parameters. (2) uses aggregate smoothness and variance bounds and controls the expected squared Euclidean gradient norm.
(3) SignSGD (Tao et al. 2026)
Singleton blocks
O(1+a(1+r2)) including batches, with L∞=∥L∥1 on the overlap. (1) covers arbitrary blocks. For even B, take half the coordinates at (Lj,σj)=(1,1) and half at (B−3,B). With Δ=ε=1, (1) costs O(B3) versus O(B5) for (3). (1) needs individual Lj,σj. (3) uses L∞,∥σ∥1 and permits general ℓ∞-smooth objectives.
(4) AdaGrad (Jiang et al. 2025)
Singleton blocks
O(1+a(1+r2)H+r4H2) (1) replaces ∥L∥1∥σ∥12 by S3, removes the r4 term and logarithms, and covers arbitrary blocks. The noise coefficients coincide for proportional profiles. (1) tunes with Lj,σj,Δ,ε. The updates in (4) use no noise bounds. The smaller coefficient compares proved upper bounds only.
(5) LANTON (Hao et al. 2026)
Euclidean-layer specialization
O(1+aJ+ar2J2+r4/a) with two samples per step, Δ=f(x0)−inff>0, and σj=σ¯j. (1) needs only block variances. On the overlap, S3≤∥L∥1∥σ¯∥12, without logarithms or r4/a. (5) requires block-separable gradients and almost-sure noise bounds above and away from zero in noisy layers. (1) gives expected accuracy for Euclidean blocks. (5) bounds the time-average of gradient norms with probability at least 1−δ and permits general layer norms.

Abbr: Lmax=maxjLj, a=∥L∥1Δ/ε2, r=∥σ∥1/ε, S=∑j(Ljσj2)1/3. For (4), K=1+a(1+r2)+r4 and H=1+log⁡(1+d2K[∥σ∥∞2+K2LmaxΔ]) for damping 1/(2d). For (5), σ¯j bounds the block noise norm almost surely and J=1+log⁡((1+a(1+r2)+r4/a)/δ), 0<δ<1.

Ghadimi, Saeed, and Guanghui Lan. 2013. “Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming.” SIAM Journal on Optimization 23 (4): 2341–68. https://doi.org/10.1137/120880811.
Hao, Jie, Xiaochuan Gong, Jie Xu, Zhengdao Wang, and Mingrui Liu. 2026. Noise-Adaptive Layerwise Learning Rates: Accelerating Geometry-Aware Optimization for Deep Neural Network Training. https://doi.org/10.48550/arXiv.2510.14009.
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.
Tao, Hongyi, Dingzhi Yu, and Lijun Zhang. 2026. When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-Norm Lower Bounds. https://doi.org/10.48550/arXiv.2605.06615.

Lean setup