← All setups

Distributed Curvature Normalized Simple — Distributed Hessian-Lipschitz Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Hessian-Lipschitz Nonconvex Optimization · Lean proof

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.

Proved elapsed-time upper bound

max{232⋅(1+L⋅Δε2)⋅(l+(max0≤a<nh(a))⋅(1+σ2n⋅ε2)+b⋅(2+log⁡(1+(1+L⋅Δε2)⋅d)+log⁡(1+d2⋅(1+L⋅Δε2)+d⋅min{σ2ε2,n}n))⋅(1+dn13)+d⋅b⋅(1+log⁡(1+(1+L⋅Δε2)⋅d))⋅min{1,Q⋅εL}+d⋅(max0≤a<nh(a))⋅σ2⋅b⋅(1+log⁡(1+d2⋅(1+L⋅Δε2)+d⋅min{σ2ε2,n}n))n⋅ε2),0}

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedHessianLipschitzNonconvex.spec
  LongTails.Theorems.DistributedCurvatureNormalizedSimple.budget

Relevant previous results

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