← All setups

Distributed Hessian-Lipschitz Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Hessian-Lipschitz Nonconvex Optimization

We consider minimizing a nonconvex function f:Rd→R, where d≥0 is an integer, using stochastic gradients on a star network. The gradient is L-Lipschitz and the Hessian is Q-Lipschitz, with L>0 and Q≥0. A given point x0 satisfies f(x0)−flow≤Δ, where flow is a global lower bound and Δ≥0. Workers return unbiased gradient estimates with variance at most σ2, where σ≥0, using independent sample streams. Computation and bit communication incur specified elapsed times. For ε>0, the goal is a measurable output x¯ satisfying EP∥∇f(x¯)∥≤ε, where P is the joint law of sampling and independent algorithm randomness.

The optimization problem is infx∈Rdf(x). We use the Euclidean norm on Rd and its induced operator norm ∥⋅∥op on linear maps. The network consists of a coordinator and n≥1 workers. Worker i∈{1,…,n} has computation time hi>0; communication has latency ℓ≥0 and time per bit b≥0. The algorithm receives d,n,x0,L,Q,Δ,σ,ε, the times (hi)i=1n,ℓ,b, and the measurable sample space Ω.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere, its gradient is differentiable everywhere, and, for all x,y∈Rd, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤Q∥x−y∥. There exists flow∈R such that f(x)≥flowfor all x∈Rd,f(x0)−flow≤Δ.

Assumption 2 (Stochastic gradients and sampling). For each worker i, there are a probability measure μi on Ω and a jointly measurable map gi:Rd×Ω→Rd. For every x∈Rd, the map gi(x,⋅) is Bochner integrable under μi, its squared error is integrable, and Eξ∼μi[gi(x,ξ)]=∇f(x),Eξ∼μi[∥gi(x,ξ)−∇f(x)∥2]≤σ2. Under a joint sampling law ν, worker i has measurable samples (ξi,k)k≥0 that are independent and identically distributed with law μi. The entire streams (ξi,k)k≥0 are independent across workers. Sampling is independent of the algorithm’s randomness. The functions gi, measures μi, and joint law ν are not algorithm inputs.

Assumption 3 (Computation and communication). A worker may query any x∈Rd. An accepted query at worker i completes after hi units of time and returns the queried point together with gi(x,ξi,k), where k counts that worker’s previously completed queries. Each worker has at most one pending computation: further computation requests while it is busy are ignored. A pending computation may be aborted without consuming a sample. The coordinator performs no gradient computations.

Communication is available only between the coordinator and a worker, in either direction. A message with an m-bit payload is delivered, together with its sender’s identity, after ℓ+b(m+64) units of time; the additional 64 bits are included in the transmitted message. Each directed link admits at most one pending message, and submissions on an occupied directed link are ignored. Distinct directed links operate concurrently, including opposite directions of the same edge, and communication may overlap computation.

For an elapsed-time budget T≥0, the algorithm must complete only finitely many events almost surely at every deadline in [0,T]. Its output x¯∈Rd is taken from a designated network node at time T. It must be measurable, with ∥∇f(x¯)∥ integrable under P, and satisfy EP[∥∇f(x¯)∥]≤ε. The budget measures elapsed time, including computation and communication.

Results

A common objective f:Rd→R has an L-Lipschitz gradient, differentiable gradient and Q-Lipschitz Hessian, with f≥flow and f(x0)−flow≤Δ. Here L,ε,hi>0 and Q,Δ,σ,ℓ,b≥0. The n≥1 workers have jointly measurable, integrable unbiased gradient oracles of variance at most σ2, IID samples within each worker and independent worker streams. A star network permits parallel worker computation and independent directed links, with one pending query per worker and one packet per directed link; an m-bit packet takes ℓ+bm. Our constructed normalized methods return a selected coordinator iterate X with ∫∥∇f(X(ω))∥dPexec(ω)≤ε, where Pexec is the actual execution law; finite-event execution holds almost surely. The setup imposes no algorithm restriction.

Elapsed-time upper bounds (sufficient budgets) for DistributedHessianLipschitzNonconvex.
Result Oracle complexity Novelty Limitations
(1) DistributedCurvatureNormalized (Ours) (⋆⋆⋆) (review) Fixed elapsed-time deadline: O(A[ℓ+H(1+σ2nε2)+b(λu+λs)+dbλun+dbλsn+(d3b3λuλs2n)1/3+dHσ2bλunε2+dbλsmin{1,QεL}])
(2) DistributedCurvatureNormalizedSimple (Ours) (⋆⋆⋆) (review) Fixed elapsed-time deadline: O(A[ℓ+H(1+σ2nε2)+b(λs+λu)(1+dn1/3)+dbλsmin{1,QεL}+dHσ2bλunε2]). Same algorithm and order as (1); deadline up to 2048 times looser.

Abbr: d: dimension; n: workers; hi: gradient computation time; H=maxihi; ℓ: packet latency; b: time per bit; Δ: initial gap bound; σ2: variance bound; A=1+LΔ/ε2; λs=1+log⁡(1+Ad); λu=1+log⁡(1+(d2A+dmin{σ2/ε2,n})/n); Λ=1+log⁡(2+d+LΔ/ε2+σ2/ε2). For (3), (4), κ,τ: downlink/uplink time per real coordinate (no packet latency or finite-bit encoding); price comparison uses κ=bλs, τ=bλu. In (3), Lmax=max{L,LA,LB} and LA,LB satisfy ∥n−1∑i[∇f(x+ui)−∇f(x)]∥2≤LA2n−1∑i∥ui∥2+LB2∥n−1∑iui∥2 for all x,ui; (LA,LB)=(L,0) is always valid. log: natural logarithm; ≍: equality up to universal factors.

DistributedHessianLipschitzNonconvex (continued).
Result Oracle complexity Novelty Limitations
(3) Inkheart SGD (Begunov and Tyurin 2026), Thm. 2.2. Expected elapsed time: O(LmaxΔε2[H(1+σ2nε2)+κ+τ+dτn+dκn+(d3τκ2n)1/3+dHσ2τnε2]+dκLAΔε2). Common objective; uniform compute bound H; per-coordinate communication prices; E∥∇f(X)∥2≤ε2. (1), (2): For LA≍L, downlink factor Qε/L when Qε<L, at matched coordinate prices. Fixed deadlines; latency and bits charged. With fixed positive L,Q,Δ,σ,H,b,κ,τ, ℓ=0, d≍ε−7/4, n≍ε−3/2: O(ε−15/4)→O(ε−13/4log⁡(1/ε)) for the norm target. (1), (2) require finite Q, guarantee norm rather than squared norm, and charge bit-width logarithms and latency. Downlink advantage can reverse when LA≲Qε.
(4) Synchronous minibatch SGD (Begunov and Tyurin 2026), eq. (2). Elapsed-time upper bound: O(LΔε2[d(κ+τ)+H(1+σ2nε2)]). Uniform compute bound H; coordinate prices; E∥∇f(X)∥2≤ε2; no Hessian regularity required. (1), (2): At κ=bλs, τ=bλu, communication dependence becomes b(λs+λu)(1+d/n1/3)+dbλsmin{1,Qε/L}. Gain for large n and Qε≪L when communication dominates. (1), (2) require Q-Lipschitz Hessians and give the weaker norm criterion. Bit costs and packet latency are additional to this coordinate-cost model.
(5) DistributedBatchedSgd (LongTails, n.d.). Fixed elapsed-time deadline: O(A[mini{hi+1+σ2/ε2∑j:hj≤hihj−1}+ℓ+b(1+dΛ)]). Same bit-cost star model; smooth-only scope; E∥∇f(X)∥2≤ε2. (1), (2): bdΛ becomes b(λs+λu)(1+d/n1/3)+dbλsmin{1,Qε/L}. Savings when n≫1 and Qε≪L, subject to compute/noise terms. (1), (2) require Q, give norm rather than squared-norm accuracy, and use H=maxihi instead of selecting fast workers; stragglers can worsen time.
(6) Serial NIGT (Cutkosky and Mehta 2020), Thm. 3; local-output restriction. Serial computation time: O(Hε−7/2) for fixed positive L,Q,Δ,σ, as ε↓0; one fresh stochastic gradient per step. Expected norm target; network transmission is excluded. (1), (2): Total distributed time O(ε−13/4log⁡(1/ε)) in (3)’s example beats this serial computation bound, despite charging communication. (1), (2) are dimension-dependent; for fixed positive remaining parameters, d≳ε−2 can favor (6)’s serial computation. Full network time is not supplied by (6).

Abbr: d: dimension; n: workers; hi: gradient computation time; H=maxihi; ℓ: packet latency; b: time per bit; Δ: initial gap bound; σ2: variance bound; A=1+LΔ/ε2; λs=1+log⁡(1+Ad); λu=1+log⁡(1+(d2A+dmin{σ2/ε2,n})/n); Λ=1+log⁡(2+d+LΔ/ε2+σ2/ε2). For (3), (4), κ,τ: downlink/uplink time per real coordinate (no packet latency or finite-bit encoding); price comparison uses κ=bλs, τ=bλu. In (3), Lmax=max{L,LA,LB} and LA,LB satisfy ∥n−1∑i[∇f(x+ui)−∇f(x)]∥2≤LA2n−1∑i∥ui∥2+LB2∥n−1∑iui∥2 for all x,ui; (LA,LB)=(L,0) is always valid. log: natural logarithm; ≍: equality up to universal factors.

Begunov, Grigory, and Alexander Tyurin. 2026. Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits. https://doi.org/10.48550/arXiv.2605.07795.
Cutkosky, Ashok, and Harsh Mehta. 2020. “Momentum Improves Normalized SGD.” Proceedings of the 37th International Conference on Machine Learning, Proceedings of machine learning research, vol. 119: 2260–68. https://proceedings.mlr.press/v119/cutkosky20b.html.
LongTails: DistributedBatchedSgd. n.d. Lean convergence theorem and elapsed-time budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/DistributedBatchedSgd.lean.

Lean setup