← All setups

High-Dimensional Stationarity with Separable Noise

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Stationarity with Separable Noise

We seek a stationary point of a differentiable, possibly nonconvex objective f:Rd→R in high dimension d. Its gradient is L-Lipschitz from ℓ∞ to ℓ1, with L>0, and the given starting point x0 lies at most Δ above the finite infimum in objective value. At each query, the oracle uses a fresh independent real sample to return an unbiased gradient estimate whose coordinate standard deviations sum to at most S≥0. For tolerance ε>0, the goal is an output x¯∈Rd satisfying E∥∇f(x¯)∥1≤ε over algorithm and oracle randomness.

The optimization problem is infx∈Rdf(x). The algorithm receives d,L,S,Δ,ε and x0∈Rd. The dimension d∈N and the real parameters satisfy 230ε2≤LΔ,d≥2168(1+LΔε2(1+S2ε2))16.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere. Its Euclidean gradient satisfies ∥∇f(x)−∇f(y)∥1≤L∥x−y∥∞,x,y∈Rd. The infimum f⋆=infx∈Rdf(x) is finite and satisfies f(x0)−f⋆≤Δ.

Assumption 2 (Stochastic gradients with separable noise). On call k, a query at any x∈Rd returns g(x,ξk), where g:Rd×R→Rd is jointly measurable. The real random variables (ξk)k≥0 are independent with common law ν, and the sequence is independent of the algorithm’s randomness. For ξ∼ν and each fixed x, the vector g(x,ξ) is Bochner integrable. Writing ei(x,ξ)=gi(x,ξ)−∂if(x), each ei(x,ξ)2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),∑i=1dEξ∼ν[ei(x,ξ)2]≤S.

After the allotted oracle calls, the output x¯ must be measurable under the joint law of the algorithm’s randomness and the oracle samples. Its gradient norm ∥∇f(x¯)∥1 must be integrable under this law and satisfy E[∥∇f(x¯)∥1]≤ε.

Results

On Rd, f(x0)−inff≤Δ and ∥∇f(x)−∇f(y)∥1≤L∥x−y∥∞. Each gradient query uses a fresh IID real sample. The jointly measurable reply g(x,ξ) is unbiased with finite coordinate variances and ∑iVar(gi(x,ξ))≤S at every x. For L,ε>0, S≥0, A=LΔ/ε2≥230 and d≥2168[1+A(1+S2/ε2)]16, the target is E∥∇f(x^)∥1≤ε for a measurable output of a randomized gradient-only algorithm.

Necessary stochastic gradient calls for high-dimensional ℓ∞-smooth optimization with separable noise.
Result Oracle complexity Novelty Limitations
(1) SeparableNoiseLinfSmoothLowerBound (Ours) (⋆⋆⋆) (review) Lower bound: Ω(A(1+S2/ε2))
(2) SignSGD (Tao et al. 2026, Thm. 2) Lower bound: Ω(A(1+∥σ∥12/ε2)) samples, counting every batch member. Best iterate in expectation: Emint<T∥∇f(xt)∥1. (1) extends hardness to every randomized method and arbitrary output. Under the stated dimension and gap conditions, minibatch SignSGD attains the pointwise-noise minimax rate up to constants. (2) uses fixed coordinate caps Var(gi(x,ξ))≤σi in any dimension. (1) leaves all-method hardness under these caps open and requires A≥230.
(3) Euclidean stationarity (Arjevani et al. 2022, Thm. 3, Eq. (23)) Lower bound: Ω(Aσ2/ε2) single-point value-and-gradient queries for σ>0, ε≤cLΔ. (1) transfers Euclidean hardness to ℓ1 stationarity with separable noise. Direct norm conversion can inflate smoothness by D and noise scale by D in dimension D. (1) covers gradient-only access and requires a larger dimension. (3) allows exact values with each noisy gradient. The geometries preclude direct rate comparison.
(4) Matrix stationarity (Zhang and Lin 2026, Thm. 3.1) Lower bound at p=2: Ω(rAu2) for randomized gradient-only methods. (1) treats vector separable noise. (4) uses spectral-to-nuclear smoothness and nuclear-norm noise and stationarity. Rates are incomparable. (1) requires finite variances. (4) covers 1<p≤2. At p=2, ε≤cmin(LΔ,σ) and M≥CAlog⁡[(2+A)(2+u)].
(5) Matrix stationarity (Hübler et al. 2026, Thm. 3.7) Lower bound at p=2: Ω(ru2) for randomized methods, r≥2. (1), (5): rates are incomparable under separable vector noise and nuclear-norm matrix noise. (5) also covers 1<p<2 for ε<min(σ/4,LΔ/2).
(6) Matrix stationarity (Hübler et al. 2026, Thm. E.9) Lower bound at p=2: Ω(rAu2) for zero-respecting methods, M/r≥A. (1) covers unrestricted randomized methods in vector geometry. The matrix rate in (6) is incomparable. (6) also covers 1<p<2 for ε≤min(σ,LΔ)/300.

Abbr: A=LΔ/ε2, u=σ/ε. In (3), σ2 bounds mean squared Euclidean noise. In (4)–(6), r=min(m,n) and M=max(m,n) for m×n matrices, and σ bounds the Lp norm of the nuclear norm of the noise. c,C>0 denote universal constants at p=2.

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.
Hübler, Florian, Thomas Pethick, and Suvrit Sra. 2026. Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success. https://doi.org/10.48550/arXiv.2606.14560.
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.
Zhang, Jiayu, and Tianyi Lin. 2026. Tight Complexity of Muon Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2605.18528.

Lean setup