← All setups

Multilevel Pipeline Stationarity — Distributed Mean-Squared Smooth Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Mean-Squared Smooth Nonconvex Optimization · Lean proof

Distributed Mean-Squared Smooth Nonconvex Optimization

We seek a stationary point of a differentiable, possibly nonconvex objective f:Rd→R in Euclidean dimension d≥0, given a starting point with bounded objective gap above a global lower bound. Workers on a star network have independent sample streams. Each completed query returns unbiased stochastic gradients at two points using one fresh sample. The gradients have bounded variance and are Lipschitz in mean square. Given ε>0, the goal is to return x¯∈Rd by an elapsed-time deadline with E∥∇f(x¯)∥2≤ε2, averaging over the samples and algorithm randomness.

The underlying optimization problem is infx∈Rdf(x). The algorithm receives the dimension d, the number of workers n≥1, the measurable sample space Ω, the starting point x0∈Rd, the bounds L>0, Δ≥0, and σ≥0, the tolerance ε, and the timing parameters (hi)i=1n, ℓ, and b described below. All norms are Euclidean.

Our assumptions:

Assumption 1 (Objective and initial gap). The function f is differentiable everywhere. There exists a∈R such that a≤f(x)for every x∈Rd,f(x0)−a≤Δ.

Assumption 2 (Worker sampling). For each worker i∈{1,…,n}, the samples (ξi,k)k≥0 are measurable, independent, and identically distributed with law μi on Ω. The worker streams are mutually independent, and the algorithm’s randomness is independent of the full sample array. On its (k+1)st completed query, worker i returns, for any requested x,y∈Rd, the pair (gi(x,ξi,k),gi(y,ξi,k)).

Assumption 3 (Gradient moments and mean-squared smoothness). Each gi:Rd×Ω→Rd is jointly measurable. For every x,y∈Rd and ξ∼μi, the vector gi(x,ξ) is Bochner integrable, both squared norms below are integrable, and E[gi(x,ξ)]=∇f(x),E∥gi(x,ξ)−∇f(x)∥2≤σ2,E∥gi(x,ξ)−gi(y,ξ)∥2≤L2∥x−y∥2.

The star has one communication-only hub and n computing workers. A paired query at worker i takes 2hi units of time, where hi>0. Each worker can have one query in progress. It may abort that query without consuming a sample. Further evaluation requests while the worker is busy are ignored.

Messages travel between the hub and a worker in either direction. A payload of m≥0 bits is transmitted with 64 appended zero bits and takes ℓ+b(m+64) units of time, where ℓ≥0 is the latency and b≥0 is the time per transmitted bit. The recipient receives the sender’s identity and the transmitted bits. Each directed link carries at most one message at a time and ignores new submissions while occupied. Distinct directed links can operate concurrently, including opposite directions on the same edge. Computations at different workers can overlap with one another and with communication.

Let T≥0 be the elapsed-time budget. Almost surely, every deadline t∈[0,T] must be reached with only finitely many events. At time T, the algorithm’s designated output node must return a measurable point x¯ with integrable squared gradient norm satisfying E[∥∇f(x¯)∥2]≤ε2.

Proved elapsed-time upper bound

B(S)+K⋅(max0≤j<J+1B(2⋅(J+1)⋅4j+{Sj=J0otherwise)2j)whereK=max{1,⌈524288⋅L⋅Δε2⌉+}whereS=max{1,⌈(512⋅σε)2⌉+}whereJ=min{log2⁡(K),Nat.log4(S1+Nat.log4(S))}wherec(i)=2⋅h(i)+2⋅l+b⋅(129+3⋅d⋅(14+4⋅log2⁡(2+d+K+S)))wherer(i)=(∑u=0n−1{1c(u)c(u)≤c(i)0otherwise)whereB(m)=4⋅(min0≤i<nmax{c(i),mr(i)})

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedMeanSquaredSmooth.spec
  LongTails.Theorems.MultilevelPipelineStationarity.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.