← All setups

Graph Quantized Minibatch SGD

Descriptions may be stale. Consult the linked Lean sources.

Graph Quantized Minibatch SGD

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R with L-Lipschitz gradient, where d≥0 and L>0. A given starting point x0 satisfies f(x0)−a≤Δ for a global lower bound a and Δ≥0. Workers communicate over a connected graph with heterogeneous computation times and edge bandwidths. Their oracles return independent, identically distributed unbiased stochastic gradients with variance at most σ2, where σ≥0. We analyze quantized minibatch SGD with a uniformly sampled iterate. For ε>0, the goal is a measurable output x¯ satisfying E∥∇f(x¯)∥2≤ε, with expectation over sampling and algorithm randomness.

The optimization problem is infx∈Rdf(x), where d∈Z≥0 and ∥⋅∥ is the Euclidean norm. There are n≥1 workers, indexed by V={1,…,n}, and a simple undirected graph G=(V,E). Worker i has computation time hi>0 per stochastic gradient. The bandwidth parameters satisfy bij≥0 for all i,j. The algorithm receives d,n, the measurable sample space Ω, G, (bij), (hi), L, Δ, σ, ε, and x0.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere, and there exists a∈R such that ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd,a≤f(x),x∈Rd,f(x0)−a≤Δ. Here L>0, Δ≥0, σ≥0, and ε>0.

Assumption 2 (Stochastic gradients and sampling). There exist a probability measure μ on Ω and a jointly measurable map g:Rd×Ω→Rd such that, for every x∈Rd, Eξ∼μ[g(x,ξ)]=∇f(x),Eξ∼μ[∥g(x,ξ)−∇f(x)∥2]≤σ2. The vector g(x,⋅) is Bochner integrable, and its squared error is integrable, under μ. Under a joint law Q, worker i has a measurable sequence (ξi,r)r≥0 of independent samples with common law μ. These entire sequences are independent across workers. Algorithm randomness is independent of the sample array.

Assumption 3 (Computation and graph communication). The graph G is connected, and each edge satisfies bij=bji>0,{i,j}∈E. A computation request at worker i specifies any point x∈Rd and an integer batch size m≥1. If u samples have already been consumed there, the request takes time mhi and returns the list (g(x,ξi,u),…,g(x,ξi,u+m−1)). Each worker has at most one outstanding computation; requests submitted while it is busy are ignored. Different workers may compute concurrently.

Communication transmits finite bit strings along edges. A payload of ℓ bits carries an additional 64 bits and takes time (ℓ+64)/bij from i to j. Each directed edge has its own serial queue: transmission starts at the later of its submission time and the preceding transmission’s completion time. Opposite directions and different edges may operate concurrently, including during computation. Self-messages take zero time, and messages to other nonneighbors are discarded. Delivered messages identify their sender. A designated root is one of the n workers and supplies the output.

Our result is algorithm-specific: we analyze quantized minibatch SGD. Its tuning consists of an integer K≥1, batch sizes mi∈Z≥0 with B=∑i=1nmi>0, a step size η>0, an integer quantization width w≥1, and a radius function R:Rd→(0,∞). These choices depend only on the algorithm inputs.

To define the quantizer at x, let M=2w−1,δx=2R(x)M,zx(v)={v,∥v∥≤R(x),R(x)∥v∥v,∥v∥>R(x). For each coordinate r∈{1,…,d}, set cr(x,v)=min{M,max{0,⌊(zx(v))rδx+M2⌋}},(Qx(v))r=δx(cr(x,v)−M2). Thus clipping precedes coordinatewise quantization. Starting from the given x0, define the local averages and iterates by vik=1mi∑j=0mi−1g(xk,ξi,kmi+j),mi>0,vik=0,mi=0,xk+1=xk−ηQxk(∑i=1nmiBQxk(vik)). Both the local averages and their weighted aggregate are quantized with the same quantizer at the current iterate.

The algorithm selects J uniformly from {0,…,K−1} using its own randomness, independently of the sample array. The sampled output is xJ. The distributed realization must satisfy the following restrictions for every sample array and every realization of the algorithm randomness. At every deadline and every intermediate stage, the root’s output is either x0 or xJ. Worker i has consumed at most Jmi samples. Whenever it has an outstanding computation, there is an integer l<J such that it has consumed exactly lmi samples and the outstanding request is the batch of size mi at xl. There must also exist a finite deterministic completion deadline, uniform over sample arrays and algorithm randomness, at which the process terminates with root output xJ and exactly Jmi samples consumed at each worker. These restrictions apply for every stochastic-gradient map and sample-array law, rather than only for a particular objective.

A budget T≥0 measures elapsed time under the computation and communication costs above. At every deadline t≤T, the distributed process must terminate after finitely many events almost surely. Let P be the joint law of the independent algorithm randomness and sample array, and let x¯ be the root’s output at deadline T. The output must be measurable, its squared gradient norm must be integrable under P, and the accuracy requirement is EP[∥∇f(x¯)∥2]≤ε.

Results

Differentiable L-smooth f:Rd→R, bounded below by a, with f(x0)−a≤Δ; L,ε>0, Δ,σ≥0. A jointly measurable, unbiased stochastic gradient has variance at most σ2; samples are IID within workers and independent across workers. The connected graph has symmetric full-duplex FIFO links of bandwidth be>0 bits/s, zero latency, and per-bit time 1/be. Worker i takes hi>0 seconds per sample, with one outstanding computation batch; different workers and directed links operate concurrently. Local operations are free. The setup restricts algorithms to quantized minibatch SGD with a uniform iterate selector. Target: ∫∥∇f(xJ(ω))∥2dP(ω)≤ε, where P is the joint sample and algorithm law, for the actual execution at the deadline.

Elapsed-time upper bounds (sufficient budgets) for GraphBandwidthSmoothNonconvex.
Result Oracle complexity Novelty Limitations
(1) GraceSgd (Ours) (⋆⋆) (review)

Elapsed-time upper bound (bits/s):

O(LΔεmin∅≠S⊆V[C(S)+1|S|≥2dℓ+|E|nlog⁡(2+σ2/ε)α(S)])

(2) Grace SGD (Tyurin 2026), v1, Thms. 1.5, F.1

Elapsed-time upper bound (real coordinates/s):

O(LΔεmin1≤k≤n,1≤p≤k1≤m≤|Sk,p|[dw¯k+C(Sk,p,m)]).

(1): Finite binary packets with explicit headers and fill time replace exact-real transmission. Matches computation dependence; subset selection includes every Gomory–Hu prefix. No established total-time gain. (1): Under equal numerical bandwidths, adds ℓ on the d term and |E|nlog⁡(2+σ2/ε)/α(S) per round. Needs exact offline selection instead of polynomial preprocessing.
(3) Derived bound: Grace routing (Tyurin 2026), Thm. F.1, with clipped-grid quantization

Elapsed-time upper bound (bits/s):

O(LΔεmin∅≠S⊆V[C(S)+1|S|≥2dℓ+|E|nlog⁡(2+σ2/ε)α(S)])

Common-grid clipping with radius growing in ∥x−x0∥; packet headers and fill included.

(1): Matches the derived finite-bit rate under the same assumptions; formalizes the actual execution and its packet costs.

Abbr: V: workers, n=|V|; E: undirected edges; d: dimension; Δ: initial gap bound; σ2: variance bound; hi: seconds per sample. C(S)=(σ2/ε+|S|)/(∑i∈Shi−1); ℓ=log⁡(2+d+LΔ/ε+σ2/ε). α(S): minimum total bandwidth of a cut separating S; the communication summand is omitted for |S|=1. 1: indicator. For (2), w¯1≤⋯≤w¯n−1 are Gomory–Hu tree edge weights, w¯n=∞; Sk,p are the components after deleting the k−1 smallest edges; Sk,p,m comprises its m fastest workers. Bandwidths in (2) count exact real coordinates rather than bits.

Tyurin, Alexander. 2026. Optimality in Decentralized Optimization Under Bandwidth Constraints. arXiv:2603.20735v1 [math.OC]. https://doi.org/10.48550/arXiv.2603.20735.

Lean setup