← All setups

Distributed Weighted Interpolation — Distributed Minimization under Weak Interpolation

Descriptions may be stale. Consult the linked Lean sources.

Distributed Minimization under Weak Interpolation · Lean proof

Distributed Minimization under Weak Interpolation

We minimize the average of smooth convex worker objectives on the Euclidean space Rd of dimension d≥0. Their common minimizer set S is nonempty, the given starting point lies within a known radius of S, and the average satisfies quadratic growth relative to S. Workers communicate through a hub and return unbiased local stochastic gradients with bounded variance, using independent samples within and across workers. For a tolerance ε>0, the goal is a measurable output x¯ whose expected squared Euclidean distance to S is at most ε by the elapsed-time deadline.

Let n≥1 be the number of workers, with local objectives fi:Rd→R for i=1,…,n. Write F(x)=n−1∑i=1nfi(x). The optimization problem is minx∈RdF(x). The algorithm receives d, n, the measurable sample space Ω, the worker computation times hi>0, the latency ℓ≥0, the time per bit b≥0, the smoothness constants Li≥0, the growth constant μ>0, the radius R≥0, the noise bound σ≥0, the tolerance ε, and the starting point x0∈Rd. The parameters satisfy nμ≤∑i=1nLi.

Our assumptions:

Assumption 1 (Local convexity and smoothness). Each fi is convex and differentiable on Rd, with ∥∇fi(x)−∇fi(y)∥≤Li∥x−y∥,x,y∈Rd.

Assumption 2 (Common minimizers and quadratic growth). Let S=⋂i=1nargminx∈Rdfi(x) and write dist(x,S)=infz∈S∥x−z∥. There exists x⋆∈S such that ∥x0−x⋆∥≤R,F(x)−F(x⋆)≥μ2dist(x,S)2for all x∈Rd.

Assumption 3 (Local stochastic gradients). 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 entire sample array is independent of the algorithm’s randomness. At any query point x∈Rd, the worker returns x and gi(x,ξi,k), where k counts its previously completed evaluations. The map gi:Rd×Ω→Rd is jointly measurable. For each x and ξ∼νi, the vector gi(x,ξ) is Bochner integrable and its squared error is integrable, with Eξ∼νi[gi(x,ξ)]=∇fi(x),Eξ∼νi[∥gi(x,ξ)−∇fi(x)∥2]≤σ2.

The star network consists of the n computing workers and one communication hub. An evaluation at worker i takes time hi. Each worker can have one evaluation in progress and may abort it without consuming a sample. An evaluation request made while the worker is busy is ignored. Messages travel only between the hub and a worker. A payload of m bits is transmitted with 64 appended zero bits and takes time ℓ+b(m+64). The recipient receives the sender’s identity and the transmitted bits. Each directed link carries at most one message at a time and ignores submissions while occupied. Distinct directed links, including opposite directions of the same connection, can operate concurrently with one another and with worker computations.

For an elapsed-time budget T≥0, almost surely the algorithm must process finitely many events at every deadline t∈[0,T]. At time T, its designated output node must produce a measurable point x¯∈Rd with integrable squared distance to S satisfying E[dist(x¯,S)2]≤ε, where the expectation is over the algorithm’s randomness and the worker sample array.

Proved elapsed-time upper bound

max{2048⋅(σ2S⋅ε+A⋅(1+log⁡(1+R2ε))⋅((max0≤a<nh(a))+l+b⋅(64+1024⋅d⋅w))),0}wherec={choose(h)h:∃t∈R,0≤t∧(∑i=0n−1min{L(i),t⋅h(i)})=n⋅μ0otherwisewhereu(i)=min{L(i),c⋅h(i)}whereS=(∑i=0n−1u(i)h(i)⋅u(i))whereM=(max0≤i<nu(i)⋅L(i))whereA=2⋅(∑i=0n−11h(i))⋅MSwherew=⌈log2⁡(⌈2+d+A+R2+(σ⋅(max0≤i<nu(i))M)2ε⌉++1)⌉+

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedWeakInterpolation.spec
  LongTails.Theorems.DistributedWeightedInterpolation.budget

Relevant previous results

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