← All setups

Multiscale Aggregate 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 Rd, the mean of n≥1 differentiable worker objectives in dimension d≥0. The aggregate gradient is Lipschitz, and the gap from the given starting value to a global lower bound is bounded. Each worker returns an unbiased estimate of its own gradient with bounded variance, using independent samples across evaluations and workers. Workers communicate through a central node. For a tolerance ε>0, the goal is to return x¯∈Rd within an elapsed-time budget with E∥∇F(x¯)∥≤ε, averaging over sampling and algorithm randomness.

Write fi:Rd→R for the objective at worker i∈{1,…,n} and use the Euclidean norm throughout. The optimization problem is infx∈RdF(x),F(x)=1n∑i=1nfi(x). The algorithm receives d, n, the measurable sample space Ω, the starting point x0∈Rd, the smoothness and gap bounds L>0 and Δ≥0, the noise bounds σi≥0, the tolerance ε, and the timing parameters hi>0, ℓ≥0, and b≥0.

Our assumptions:

Assumption 1 (Aggregate smoothness and initial gap). Each fi is differentiable everywhere. For every x,y∈Rd, ∥∇F(x)−∇F(y)∥≤L∥x−y∥. There exists Flow∈R such that Flow≤F(x)for every x∈Rd,F(x0)−Flow≤Δ.

Assumption 2 (Worker sampling and gradient estimates). Worker i has a sequence (ξi,k)k≥0 of measurable i.i.d. samples with law μi on Ω. The worker sequences are mutually independent, and the algorithm’s randomness is independent of the entire sample array. On its kth completed evaluation, indexed from zero, worker i returns the query point x and the vector gi(x,ξi,k), where gi:Rd×Ω→Rd is jointly measurable. For each 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.

Assumption 3 (Star network and timing). The center communicates with each of the n workers in both directions. Only workers perform gradient evaluations. An evaluation at worker i takes time hi and may be aborted. While an evaluation is pending, the worker ignores new evaluation requests. Each directed link carries at most one message at a time and ignores send requests while occupied. Computations at different workers and transmissions on distinct directed links may proceed concurrently, and communication may overlap computation. A payload of m≥0 bits is transmitted with 64 trailing zero bits and arrives with the sender’s identity after time ℓ+b(m+64), where ℓ is the latency and b is the time per transmitted bit.

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

Proved elapsed-time upper bound

2⋅K⋅((max0≤a<nh(a))+V+2⋅C)whereK=1+⌈219⋅L⋅Δε2⌉+whereV=max{218⋅(∑i=0n−1h(i)⋅σ(i)2)n2⋅ε2,0}whereC=l+b⋅(64+d⋅(5+⌈log2⁡(n⋅(d+1)+1)⌉+))

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedAggregateSmoothNonconvex.spec
  LongTails.Theorems.MultiscaleAggregateStationarity.budget

Relevant previous results

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