← All setups

Distributed Smooth Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Smooth Nonconvex Optimization

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d≥0 is an integer. Its gradient is L-Lipschitz for L>0, and a given point x0 satisfies f(x0)−flow≤Δ for a global lower bound flow and Δ≥0. A star network has n≥1 computing workers and a coordinator. Each worker returns unbiased stochastic gradients with variance at most σ2, where σ≥0, using independent samples across workers and calls. Computation and bit communication take time. For ε>0, the goal is an output x¯ satisfying EP∥∇f(x¯)∥2≤ε, where P is the law of sampling and algorithm randomness.

The optimization problem is infx∈Rdf(x), with the Euclidean norm ∥⋅∥. Worker i∈{1,…,n} has computation time hi>0. Communication has latency ℓ≥0 and time per bit b≥0. The algorithm receives d,n, a measurable sample space Ω, (hi)i=1n, ℓ,b,L,Δ,σ,ε, and x0∈Rd. The objective, stochastic-gradient maps, and sampling distributions are accessed through the oracles.

Our assumptions:

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

Assumption 2 (Stochastic gradients). 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, its squared error is integrable, and EZ∼μi[gi(x,Z)]=∇f(x),EZ∼μi[∥gi(x,Z)−∇f(x)∥2]≤σ2.

Assumption 3 (Independent sampling). Let Q be the joint law of sample streams (ξi,k)i=1,…,n;k≥0 taking values in Ω. Each coordinate ξi,k is measurable. For each i, the sequence (ξi,k)k≥0 is independent and identically distributed with marginal law μi. The entire streams (ξi,k)k≥0 are independent across workers. Algorithm randomness is independent of these streams.

Assumption 4 (Computation and communication). The network consists of coordinator 0 and workers 1,…,n, with communication only between the coordinator and a worker. Queries may use any point of Rd. An accepted evaluation at worker i and point x takes time hi and returns (x,gi(x,ξi,k)), where k is the number of evaluations previously completed by that worker. Each worker can have at most one pending evaluation; further evaluation requests while it is busy are ignored. A pending evaluation may be aborted, in which case it produces no reply and consumes no sample. The coordinator performs no gradient evaluations.

Messages are finite bit strings. A payload of m≥0 bits sent along a directed coordinator–worker link takes time ℓ+b(m+64), including a fixed 64-bit overhead. The receiver obtains the sender’s identity and transmitted bits. Each directed link can carry at most one pending message; further submissions on that directed link are ignored until delivery. Distinct directed links can operate concurrently, including opposite directions of the same link. Computations at different workers and communication can also proceed concurrently.

The resource budget is an elapsed-time deadline T≥0. The algorithm must have only finitely many events up to every deadline t≤T, almost surely under P, the joint law specified above. Its output x¯∈Rd is taken from a designated node at time T. It must be measurable, ∥∇f(x¯)∥2 must be integrable under P, and the accuracy requirement is EP[∥∇f(x¯)∥2]≤ε.

Results

Lean setup