← All setups

Multirate Distributed Stationarity — Distributed Nonconvex Finite-Sum Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Nonconvex Finite-Sum Optimization · Lean proof

Distributed Nonconvex Finite-Sum Optimization

We seek a stationary point of a possibly nonconvex objective F on d-dimensional Euclidean space Rd. Each worker contributes one component to the average F. Each component has a Lipschitz gradient, and the initial objective gap to a global lower bound is bounded. Workers compute at heterogeneous speeds and communicate over directed links. Each worker’s oracle returns batches of unbiased local gradient estimates with bounded variance, using independent samples within and across workers. For a tolerance ε>0, the goal is an output x¯ satisfying E[∥∇F(x¯)∥2]≤ε2 over sampling and algorithm randomness.

Index the n≥1 workers by i=1,…,n, and write fi:Rd→R for their components, where d is a nonnegative integer. With F(x)=1n∑i=1nfi(x), the optimization problem is infx∈RdF(x). The algorithm receives d, n, the measurable sample space Ω, the starting point x0∈Rd, the bounds (Li,σi)i=1n and Δ, the tolerance ε, and the timing parameters (hi)i=1n, ℓ, and b.

Our assumptions:

Assumption 1 (Component smoothness and initial gap). Each fi is differentiable, and for all x,y∈Rd its gradient satisfies ∥∇fi(x)−∇fi(y)∥≤Li∥x−y∥,Li≥0, where ∥⋅∥ is the Euclidean norm. There is a lower bound a∈R such that a≤F(x)for every x∈Rd,F(x0)−a≤Δwith Δ≥0.

Assumption 2 (Local stochastic gradients). Worker i has a stream (ξi,k)k≥0 of measurable, independent samples with common law μi on Ω. The worker streams are mutually independent, and the algorithm’s randomness is independent of the entire sample array. The map gi:Rd×Ω→Rd is jointly measurable. For every x∈Rd and ξ∼μi, the vector gi(x,ξ) is Bochner integrable, its squared error is integrable, and Eξ∼μi[gi(x,ξ)]=∇fi(x),Eξ∼μi[∥gi(x,ξ)−∇fi(x)∥2]≤σi2, where σi≥0.

Computation and communication.

A computation query at worker i specifies a point x∈Rd and a positive integer batch size m. If k samples have already been used, the worker returns the ordered batch (gi(x,ξi,k+j))j=0m−1 after time mhi, where hi>0 is its time per sample. Each worker processes one batch at a time and ignores further computation requests while a batch is pending. Different workers can compute concurrently.

Every ordered pair of workers, including a worker paired with itself, has a directed link. A message with q≥0 payload bits is padded with 64 zero bits. If submitted at time t, it finishes at max{t,tprev}+ℓ+b(q+64), where tprev is the previous finish time on that link, initially zero, ℓ≥0 is the latency, and b≥0 is the time per transmitted bit. The recipient receives the sender’s identity and the padded bit string. Each link serves messages in submission order. Distinct links can operate concurrently, and communication can overlap computation.

Elapsed time and accuracy.

For an elapsed-time budget T≥0, almost surely the algorithm must process only finitely many events for every deadline s∈[0,T]. At time T, a root worker designated by the algorithm must produce a measurable output x¯∈Rd with integrable squared gradient norm satisfying E[∥∇F(x¯)∥2]≤ε2.

Proved elapsed-time upper bound

max{32⋅(I+R⋅C+q⋅((∑i=0n−1L(i)⋅h(i))n+((∑i=0n−1σ(i)⋅L(i)⋅h(i)))2n3⋅δ2)),0}whereδ=ε512whereq=Δδ2whereR=1+⌈2⋅q⋅(∑i=0n−1L(i))n⌉+whereC=l+b⋅(64+d⋅(11+log2⁡(n⋅(d+1))+log2⁡(R)))whereI=(max0≤a<nh(a))+(∑i=0n−1σ(i)2⋅h(i))(n⋅δ)2

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedComponentSmoothNonconvex.spec
  LongTails.Theorems.MultirateDistributedStationarity.budget

Relevant previous results

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