← All setups

Distributed Minimization under Weak Interpolation

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On Rd, the n convex, Li-smooth worker objectives have a common minimizer set S=⋂iarg⁡minfi≠∅. Their average f satisfies f(x)−minf≥μdist(x,S)2/2, with 0<nμ≤∑iLi and dist(x0,S)≤R. Gradients are unbiased with variance at most σ2, sampled IID within workers and independently across workers. On the coordinator star, one gradient at worker i takes hi>0 seconds and a k-bit message takes ℓ+bk seconds. Workers and links operate concurrently, with one pending call per worker and one message per directed link. The target is EPdist(xout,S)2≤ε, ε>0. Times are compared at ℓ=b=0.

Elapsed-time upper bounds for distributed weak interpolation.
Result Oracle complexity Novelty Limitations
(1) DistributedWeightedInterpolation (Ours) (⋆⋆) (review) O(σ2Iε+κq(H+ℓ+bB))
(2) Malenia SGD (Tyurin 2026, Thm. F.2) O(q[HL¯μ+σ2∑ihi(nμ)2ε]) (1) removes q from the noise term and gains a further factor G=I∑ihi/(nμ)2≥1. G>1 exactly when some nμhi>Li∑jhj; G=Θ(s) in the two-worker example of (3). (1) needs a common minimizer, individual Li and exact hi. With equal Li and no binding cap, startup can cost up to H/minihi times more.
(3) Derived bound: Malenia SGD on a subset (Tyurin 2026, Thm. F.2) O(qminT:aT>0[HT∑i∈TLiaT+σ2∑i∈ThiεaT2]) (1) gains Θ(log⁡N) in the noise coefficient before counting q, even over the best subset, for n=2N, Li=1, μ=1/2, h=(1,…,1⏟N,1,…,N). For h=(1,s), L=(2μ,μ/s), s≥2, T={1} already attains O(q[1+v]) versus O(sq+v) for (1).
(4) Rennala SGD (Tyurin 2026, Thm. 3.8) O(qmin1≤m≤nmLmax/μ+σ2/(μ2ε)∑j=1m1/h(j)) (1) allows intersecting minimizer sets and growth only for the average. (4) requires identical minimizer sets and the Polyak–Łojasiewicz condition with constant μ at every worker. For Li=L and μ<L/(2n), (1) has arithmetic-mean noise dependence. On this overlap (4) exploits the harmonic mean of the selected worker times.

Abbr: q=log⁡(2+R2/ε), v=σ2/(μ2ε), H=maxihi, L¯=n−1∑iLi, Lmax=maxiLi. Choose c≥0 so that ui=min{Li,chi} sum to nμ. I=∑iui2/hi, M=maxi(uiLi), κ=(M/I)∑ihi−1, B=1+dlog(2+d+κ+[R2+(σmaxiui/M)2]/ε). For a worker subset T, aT=nμ−∑i∉TLi and HT=maxi∈Thi. Worker times h(j) are in increasing order.

Tyurin, Alexander. 2026. Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult. https://doi.org/10.48550/arXiv.2609.17483.

Lean setup