Introduction
We consider a decentralized optimization problem over a possibly time-varying network:
min x ∈ R d F ( x ) : = 1 m ∑ i = 1 m f i ( x ) , \min_{x\in\mathbb{R}^d} F(x) := \frac{1}{m}\sum_{i=1}^{m} f_i(x), x ∈ R d min F ( x ) := m 1 i = 1 ∑ m f i ( x ) ,
where node i i i stores its own nonlinear-regression samples and the network objective is the average of the local ones. Such problems model learning from data that cannot be collected in one place and arise in federated learning, in sensor and multi-agent systems, and in large-scale training, where decentralized communication can be cheaper than routing everything through a central server [42 , 38 , 32 ] .
Even for a realizable monotone-link model, this objective need not be convex: its Hessian can be indefinite. Nevertheless, if the link has slope at least α > 0 \alpha> 0 α > 0 and is M M M -Lipschitz, the objective satisfies the one-point inequality $\gamma\left[F(x)-F(x^\star)\right] \le ⟨ ∇ F ( x ) , x − x ⋆ ⟩ \langle\nabla F(x), x-x^\star\rangle ⟨ ∇ F ( x ) , x − x ⋆ ⟩ with the globally valid parameter γ = min { 1 , 2 α / M } \gamma=\min\{1,2\alpha/M\} γ = min { 1 , 2 α / M } ; see Proposition 2.4. This quasar-convexity condition holds globally for generalized linear models with monotone links (§ 5 ) and for star-convex objectives, which are 1-quasar-convex ([19 ] ). Weaker versions restricted to a domain of parameters arise elsewhere, for instance in learning linear dynamical systems ([16 ] ); such cases need a projection or an invariance argument and are not covered by our global theorems. We ask whether the accelerated inverse-quadratic rate survives when the gradient is assembled by only finitely many peer-to-peer communication rounds.
Acceleration for convex decentralized problems is well studied ([17 , 26 , 27 , 31 ] (Scaman et al. 2017; Xu et al. 2020)), but a convex decentralized proof cannot simply be copied. Quasar-convexity gives a lower model only for the pair ( x , x ⋆ ) (x,x^\star) ( x , x ⋆ ) , not for two arbitrary query points, and it does not imply monotonicity of the gradient, so a consensus error cannot be inserted into the usual affine estimate-sequence inequalities.
Our approach separates the acceleration mechanism from the network. We first prove a continuized acceleration result for an abstract inexact oracle with a predictable bias and a state-dependent variance (Theorem 4.3 ): after T T T events in expectation, the objective gap is O ~ ( L ∥ x 0 − x ⋆ ∥ 2 / ( γ 2 T 2 ) ) \widetilde{O}(L\lVert x_0-x^\star\rVert^2/(\gamma^2T^2)) O ( L ∥ x 0 − x ⋆ ∥ 2 / ( γ 2 T 2 )) plus variance and bias terms. We then show that finitely many gossip rounds followed by the selection of one node’s mixed row implement such an oracle without bias, at every mixing depth: unfinished averaging enters only as variance, which the quasar-convex analysis can absorb. We call this method CQA-Net. It is synchronized, blocking, and common-state, and it relies on three global primitives: exact dissemination of the selected row, a shared event clock, and a shared uniform root. Dissemination is natural in federated learning, but in a peer-to-peer network, and especially on a changing graph, it is a strong requirement. We therefore give two further implementations. A walking token carries the common state along a random walk, so that the clock and the root travel with the token and nothing is disseminated. D-CQA keeps local states and mixes them; only a shared clock seed and synchronous rounds remain, and the dissemination depth disappears from the round count. Table 1 compares the three designs with related methods. We do not address physical asynchrony, fault recovery, partial participation, wall-clock time, or communication optimality.
Table 1. Comparison with nearby network-optimization models. “Common” means that all nodes hold identical optimization states after each event; “local” allows node disagreement.
§ 5 tests the methods on instances whose constants are certified in closed form: a nonconvex leaky-tanh regression on static and changing graphs, the individual variance mechanisms of CQA-Net, and a comparison of CQA-Net, the token, and D-CQA by communication rounds. It also quantifies how conservative the global certificates can be.
Main contributions.
Theorem 4.3 gives one Lyapunov bound for oracles with a predictable bias and a state-dependent variance. It retains the variance integral and a gradient reserve that absorbs multiplicative noise, and it handles a mean-square bias by a square-root Gronwall argument, without projection or damping.
Lemma 4.6 gives the conditional moments of any selected-row oracle: a mixed matrix of local rows, a root with an arbitrary law, and an optional importance weight. It yields unbiased finite mixing at every depth (Theorem 4.8 , fixed and changing graphs) and the walking-token oracle (Corollaries 4.13 and 4.14).
Theorem 4.19 analyzes the local-state variant D-CQA, and Corollary 4.20 bounds its communication by O ~ ( χ L R 0 / ( γ θ ε ) ) \widetilde{O}(\sqrt{\chi}\sqrt{LR_0}/(\gamma\theta\sqrt{\varepsilon})) O ( χ L R 0 / ( γ θ ε )) rounds, without a dissemination term.
For shared-landscape finite sums, exact-snapshot restarts give a geometric rate with an accuracy-independent inner depth and batch size (Remark 4.10 and Appendix D).
Related work
Acceleration beyond convexity. Smooth convex acceleration originates with Nesterov [44 ] (1983). Accelerated methods for weakly quasi-convex and star-convex objectives use auxiliary one- or low-dimensional searches ([14 , 29 , 28 , 19 ] ), which are costly across a network because every trial point may need a global comparison. Continuized acceleration avoids this search: Even et al. [10 ] introduced exactly simulable Poisson-time acceleration, and Wang and Wibisono (2023) obtained the optimal deterministic dependence on the quasar parameter. Stochastic, robust, non-Euclidean, constrained, zeroth-order, proximal, and distributional developments appear in ([11 , 18 , 15 , 30 , 37 , 12 , 21 , 8 , 2 , 9 ] ); related one-point structures arise, on restricted domains, in learning linear dynamical systems ([16 ] ). Nonconvex stochastic lower bounds (Saad et al., 2025) do not yield a matching lower bound for our model.
Acceleration in networks. Communication-optimal convex decentralized methods combine objective and spectral acceleration ([17 , 26 ] (Scaman et al. 2017; Xu et al. 2020)), with sliding, similarity, and second-order variants ([27 , 1 , 7 ] (Takezawa et al. 2025; Tian et al. 2022)). Gradient tracking and primal-dual methods maintain local states ([43 , 31 , 20 ] (Qu and Li 2018)), DADAO uses asynchronous edge and gradient clocks ([41 ] ), DCatalyst wraps a decentralized solver in an accelerated outer loop ([4 ] ), and time-varying and finite-sum settings are treated in ([39 , 40 , 34 , 33 , 35 ] (Rogozin et al. 2020)). CQA-Net keeps one common state, so its round count contains the broadcast depth D D D in addition to the Chebyshev depth; at γ = 1 \gamma= 1 γ = 1 it is a non-optimal common-state specialization. D-CQA removes D D D and, under bounded heterogeneity, matches the convex local-state round scale up to a logarithm. Random-walk methods process one node per step along a walk ([22 , 36 ] ); our token uses this mechanism only to deliver the oracle, and push-sum-type protocols ([24 ] ) are a natural route to message loss, which we do not treat.
Node sampling. At q = 0 q = 0 q = 0 CQA-Net is uniform node sampling followed by dissemination, as in client sampling, Local SGD, and SCAFFOLD-type control variates ([23 , 13 , 25 ] ) and randomized broadcast gossip ([3 ] ). The uniform-row identity is elementary; we use it to supply the exact conditional moments that the quasar-specific Lyapunov theorem needs.
Organization. § 2 sets the geometry and the stochastic model, § 3 defines the algorithms, § 4 contains the analysis, and § 5 the numerical study. Technical proofs and reproducibility details are in the appendices.
Problem statement and notation
We separate the optimization state from the network data used to construct one oracle vector. The continuized dynamics live in R d \mathbb{R}^{d} R d and are written with lowercase variables. A node index appears only on local rows and on the transient matrices used by the communication protocol. In CQA-Net every node stores the same optimization vectors at the end of each event; § 3.6 introduces a variant with local states.
The one-vector problem
Let F : R d → R F:\mathbb{R}^{d} \to\mathbb{R} F : R d → R be differentiable and let x ⋆ x^{\star} x ⋆ be a fixed global minimizer. Continuous-time states and the oracle lie in R d \mathbb{R}^{d} R d and are denoted x t , z t , g t x_t,z_t,g_t x t , z t , g t ; all processes are right-continuous with left limits. For a jump index k ≥ 1 k \ge1 k ≥ 1 ,
x ( k ) = x τ k , y ( k ) = x τ k − , z ( k ) = z τ k , g ( k ) = g τ k , x^{(k)} = x_{\tau_k}, \qquad y^{(k)} = x_{\tau_k-}, \qquad z^{(k)} = z_{\tau_k}, \qquad g^{(k)} = g_{\tau_k}, x ( k ) = x τ k , y ( k ) = x τ k − , z ( k ) = z τ k , g ( k ) = g τ k ,
so y ( k ) y^{(k)} y ( k ) is the pre-jump query and x ( k ) x^{(k)} x ( k ) the post-jump state, and F τ k − \mathcal{F}_{\tau_k-} F τ k − collects everything revealed strictly before τ k \tau_k τ k . We set x ( 0 ) = x 0 x^{(0)} = x_0 x ( 0 ) = x 0 , z ( 0 ) = z 0 z^{(0)} = z_0 z ( 0 ) = z 0 , τ 0 = 0 \tau_0 = 0 τ 0 = 0 , E k − 1 = τ k − τ k − 1 E_{k-1} = \tau_k - \tau_{k-1} E k − 1 = τ k − τ k − 1 , and R 0 : = ∥ x 0 − x ⋆ ∥ R_0 := \lVert x_0 - x^{\star}\rVert R 0 := ∥ x 0 − x ⋆ ∥ .
Definition 2.1 (Smoothness). The objective is L L L -smooth if ∥ ∇ F ( x ) − ∇ F ( y ) ∥ ≤ L ∥ x − y ∥ \lVert\nabla F(x) - \nabla F(y)\rVert\le L\lVert x-y\rVert ∥ ∇ F ( x ) − ∇ F ( y )∥ ≤ L ∥ x − y ∥ for all x , y ∈ R d x,y \in\mathbb{R}^{d} x , y ∈ R d . Then the descent inequality
F ( y ) ≤ F ( x ) + ⟨ ∇ F ( x ) , y − x ⟩ + L 2 ∥ y − x ∥ 2 . (1) F(y) \le F(x) + \langle\nabla F(x), y-x \rangle+ \frac{L}{2}\lVert y-x\rVert^{2}. \tag*{(1)} F ( y ) ≤ F ( x ) + ⟨ ∇ F ( x ) , y − x ⟩ + 2 L ∥ y − x ∥ 2 . (1)
holds for all x , y ∈ R d x,y \in\mathbb{R}^{d} x , y ∈ R d .
Definition 2.2 (Quasar-convexity / weak quasi-convexity). For γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] , the objective is γ \gamma γ -quasar-convex with respect to x ⋆ x^\star x ⋆ if
γ ( F ( x ) − F ( x ⋆ ) ) ≤ ⟨ ∇ F ( x ) , x − x ⋆ ⟩ for every x ∈ R d . (2) \gamma\left(F(x)-F(x^\star)\right) \le\langle\nabla F(x),x-x^\star\rangle\qquad\text{for every } x \in\mathbb{R}^{d}. \tag*{(2)} γ ( F ( x ) − F ( x ⋆ ) ) ≤ ⟨ ∇ F ( x ) , x − x ⋆ ⟩ for every x ∈ R d . (2)
The number γ \gamma γ is any certified admissible value. Every statement remains valid after replacing it by a smaller positive value.
Definition 2.3 (Quadratic growth). The objective satisfies fixed-minimizer quadratic growth with constant μ > 0 \mu> 0 μ > 0 if
F ( x ) − F ( x ⋆ ) ≥ μ 2 ∥ x − x ⋆ ∥ 2 for every x ∈ R d . (3) F(x)-F(x^\star) \ge\frac{\mu}{2}\lVert x-x^\star\rVert^{2} \qquad\text{for every } x \in\mathbb{R}^{d}. \tag*{(3)} F ( x ) − F ( x ⋆ ) ≥ 2 μ ∥ x − x ⋆ ∥ 2 for every x ∈ R d . (3)
Condition (3) uses the same distinguished minimizer as quasar-convexity.
Convexity implies Definition 2.2 with γ = 1 \gamma=1 γ = 1 , but the converse is false. The condition supplies a lower model only in the pair ( x , x ⋆ ) (x,x^\star) ( x , x ⋆ ) : it gives neither an affine lower model at an arbitrary second point nor monotonicity of the gradient. It nevertheless implies that every stationary point is globally optimal. Quadratic growth is invoked only for the dissipative closure of Corollary 4.9(c).
Certified quasar-convex models
A concrete globally nonconvex class is realizable nonlinear regression with a strongly monotone link. Let φ : R → R \varphi:\mathbb{R}\to\mathbb{R} φ : R → R be a differentiable link function; quantitative assumptions on φ ′ \varphi' φ ′ are stated in Proposition 2.4. Given features a r ∈ R d a_r \in\mathbb{R}^{d} a r ∈ R d and a target x ⋆ x^\star x ⋆ , the responses are realizable, y r = φ ( a r T x ⋆ ) y_r=\varphi(a_r^{\mathsf T}x^\star) y r = φ ( a r T x ⋆ ) , and the squared-loss objective is
F ( x ) = 1 2 N ∑ r = 1 N ( φ ( a r T x ) − y r ) 2 . (4) F(x)=\frac{1}{2N}\sum_{r=1}^{N}\left(\varphi(a_r^{\mathsf T}x)-y_r\right)^2. \tag*{(4)} F ( x ) = 2 N 1 r = 1 ∑ N ( φ ( a r T x ) − y r ) 2 . (4)
Proposition 2.4 gives the constants used in the numerical section. Appendix E contains the proof.
Proposition 2.4 (Monotone-link and leaky-tanh certificates). Assume that φ \varphi φ is differentiable and 0 < α ≤ φ ′ ( u ) ≤ M 0<\alpha\le\varphi'(u)\le M 0 < α ≤ φ ′ ( u ) ≤ M for every u u u . Then (4) is globally γ \gamma γ -quasar-convex with γ = min { 1 , 2 α / M } \gamma=\min\{1,2\alpha/M\} γ = min { 1 , 2 α / M } . If Σ = N − 1 ∑ r a r a r T ≻ 0 \Sigma=N^{-1}\sum_r a_ra_r^{\mathsf T}\succ0 Σ = N − 1 ∑ r a r a r T ≻ 0 , it satisfies quadratic growth with μ = α 2 λ min ( Σ ) \mu=\alpha^2\lambda_{\min}(\Sigma) μ = α 2 λ m i n ( Σ ) .
For α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] and φ α ( u ) = α u + ( 1 − α ) tanh u \varphi_\alpha(u)=\alpha u+(1-\alpha)\tanh u φ α ( u ) = α u + ( 1 − α ) tanh u , let v r = a r T x ⋆ v_r=a_r^{\mathsf T}x^\star v r = a r T x ⋆ and
B α ( v ) = 1 + 4 α ( 1 − α ) e + 4 α ( 1 − α ) 3 3 ∣ v ∣ + 8 ( 1 − α ) 2 3 3 . B_\alpha(v)=1+\frac{4\alpha(1-\alpha)}{e}+\frac{4\alpha(1-\alpha)}{3\sqrt{3}}\lvert v\rvert+\frac{8(1-\alpha)^2}{3\sqrt{3}}. B α ( v ) = 1 + e 4 α ( 1 − α ) + 3 3 4 α ( 1 − α ) ∣ v ∣ + 3 3 8 ( 1 − α ) 2 .
Then ∇ F \nabla F ∇ F is globally Lipschitz with any L ≥ N − 1 ∑ r B α ( v r ) ∥ a r ∥ 2 L\ge N^{-1}\sum_r B_\alpha(v_r)\lVert a_r\rVert^2 L ≥ N − 1 ∑ r B α ( v r ) ∥ a r ∥ 2 .
The quasar part sharpens Lemma 3 of Wang and Wibisono (2023), which gives the constant 2 α 2 / M 2 2\alpha^2/M^2 2 α 2 / M 2 under the same assumptions, by the factor M / α M/\alpha M / α ; the quadratic-growth constant matches their quasar-growth bound. The certificate is global and permits negative curvature. In the scalar case N = d = 1 N=d=1 N = d = 1 , α = 1 / 2 \alpha=1/2 α = 1/2 , and x ⋆ = − 2 x^\star=-2 x ⋆ = − 2 , direct interval evaluation gives − 0.253 < F ′ ′ ( 1 ) < − 0.250 -0.253<F''(1)<-0.250 − 0.253 < F ′′ ( 1 ) < − 0.250 . Realizability is essential: response noise creates a nonzero residual at x ⋆ x^\star x ⋆ and requires a separate one-point argument.
Certified examples used below. The smooth convex case has γ = 1 \gamma=1 γ = 1 and serves as a calibration and ridge benchmark. The realizable leaky-tanh regression instance is globally quasar-convex and satisfies quadratic growth despite being nonconvex; its rounded constants are γ = 0.36 \gamma=0.36 γ = 0.36 , L = 2.3631 L=2.3631 L = 2.3631 , and μ = 1.457 ⋅ 10 − 3 \mu=1.457\cdot10^{-3} μ = 1.457 ⋅ 1 0 − 3 . It is used for the static- and changing-network experiments. The aligned multiplicative quadratic has a convex network average with γ = μ = L = 1 \gamma=\mu=L=1 γ = μ = L = 1 but nonconvex local terms and heterogeneity coefficient h 1 = 1.28 h_1=1.28 h 1 = 1.28 . Full-precision constants are stored in the accompanying metadata.
Network average and local rows
Node i ∈ { 1 , … , m } i\in\{1,\ldots,m\} i ∈ { 1 , … , m } stores a differentiable local function f i : R d → R f_i:\mathbb{R}^{d}\to\mathbb{R} f i : R d → R , and
F ( x ) = 1 m ∑ i = 1 m f i ( x ) . (5) F(x)=\frac{1}{m}\sum_{i=1}^{m}f_i(x). \tag*{(5)} F ( x ) = m 1 i = 1 ∑ m f i ( x ) . (5)
Only the average F F F is assumed smooth and quasar-convex; the f i f_i f i may be nonconvex, may fail the quasar condition, and may have different minimizers. Weighted empirical partitions are encoded in the definitions of the f i f_i f i , so (5) remains exact when local sample counts differ.
At jump k ≥ 1 k \ge1 k ≥ 1 , all nodes receive the same predictable query y ( k ) ∈ R d y^{(k)} \in\mathbb{R}^d y ( k ) ∈ R d . Node i i i produces a random row g i ( k ) ( y ( k ) ) ∈ R d g_i^{(k)}(y^{(k)}) \in\mathbb{R}^d g i ( k ) ( y ( k ) ) ∈ R d with
E [ g i ( k ) ( y ( k ) ) ∣ F τ k − ] = ∇ f i ( y ( k ) ) , E [ ∥ g i ( k ) ( y ( k ) ) − ∇ f i ( y ( k ) ) ∥ 2 ∣ F τ k − ] ≤ σ 2 b . (6) \mathbb{E}\left[g_i^{(k)}(y^{(k)}) \mid\mathcal{F}_{\tau_k-}\right] = \nabla f_i(y^{(k)}), \qquad\mathbb{E}\left[\left\|g_i^{(k)}(y^{(k)})-\nabla f_i(y^{(k)})\right\|^2 \mid\mathcal{F}_{\tau_k-}\right] \le\frac{\sigma^2}{b}. \tag*{(6)} E [ g i ( k ) ( y ( k ) ) ∣ F τ k − ] = ∇ f i ( y ( k ) ) , E [ g i ( k ) ( y ( k ) ) − ∇ f i ( y ( k ) ) 2 ∣ F τ k − ] ≤ b σ 2 . (6)
Write K i , k K_{i,k} K i , k for a regular conditional kernel, given F τ k − \mathcal{F}_{\tau_k-} F τ k − , of the row rule prescribed at that event (either the ordinary local row above or a control-variate row introduced later). Whenever a root R k R_k R k is used, it is conditionally uniform and conditionally independent, given F τ k − \mathcal{F}_{\tau_k-} F τ k − , of a latent family of row innovations having kernels ( K i , k ) i = 1 m (K_{i,k})_{i=1}^m ( K i , k ) i = 1 m . Equivalently, in the lazy q = 0 q=0 q = 0 implementation, after R k = i R_k=i R k = i is revealed the only evaluated row is sampled from K i , k K_{i,k} K i , k using fresh randomness independent of the root, so that
L ( g i ( k ) ( y ( k ) ) ∣ F τ k − , R k = i ) = K i , k = L ( g i ( k ) ( y ( k ) ) ∣ F τ k − ) . (7) \mathcal{L}\left(g_i^{(k)}(y^{(k)}) \mid\mathcal{F}_{\tau_k-}, R_k=i\right) = K_{i,k} = \mathcal{L}\left(g_i^{(k)}(y^{(k)}) \mid\mathcal{F}_{\tau_k-}\right). \tag*{(7)} L ( g i ( k ) ( y ( k ) ) ∣ F τ k − , R k = i ) = K i , k = L ( g i ( k ) ( y ( k ) ) ∣ F τ k − ) . (7)
This latent coupling is a statement about the conditional law; it does not require unelected nodes to evaluate gradients. Cross-node row innovations may be dependent unless a later covariance bound explicitly requires otherwise. The stack of rows is G ( k ) ∈ R m × d G^{(k)} \in\mathbb{R}^{m \times d} G ( k ) ∈ R m × d , and e i ∈ R m e_i \in\mathbb{R}^m e i ∈ R m denotes the i i i th standard basis vector. The single vector returned after finite mixing, row selection, and broadcast is denoted g ^ ( k ) ∈ R d \widehat{g}^{(k)} \in\mathbb{R}^d g ( k ) ∈ R d . The squared heterogeneity at a common point is
ζ 2 ( y ) = 1 m ∑ i = 1 m ∥ ∇ f i ( y ) − ∇ F ( y ) ∥ 2 . (8) \zeta^2(y) = \frac{1}{m}\sum_{i=1}^{m}\left\|\nabla f_i(y)-\nabla F(y)\right\|^2. \tag*{(8)} ζ 2 ( y ) = m 1 i = 1 ∑ m ∥ ∇ f i ( y ) − ∇ F ( y ) ∥ 2 . (8)
The quantity in (8) measures disagreement of local mean rows, not disagreement of node states.
Analytical and simulation filtrations
Let n t n_t n t be a unit-rate Poisson counting process with event times 0 < τ 1 < τ 2 < ⋯ 0 < \tau_1 < \tau_2 < \cdots 0 < τ 1 < τ 2 < ⋯ . The analysis is carried out in a filtration F = ( F t ) t ≥ 0 \mathbb{F}=(\mathcal{F}_t)_{t\ge0} F = ( F t ) t ≥ 0 relative to which n t n_t n t has predictable intensity one. A random kernel K t ( ω , d g ) K_t(\omega,dg) K t ( ω , d g ) is F \mathbb{F} F -predictable if, for every bounded Borel function ϕ \phi ϕ , the map ( t , ω ) ↦ ∫ ϕ ( g ) K t ( ω , d g ) (t,\omega)\mapsto\int\phi(g)K_t(\omega,dg) ( t , ω ) ↦ ∫ ϕ ( g ) K t ( ω , d g ) is measurable with respect to the predictable sigma-field of F \mathbb{F} F . An exact simulator may instead pre-draw the exponential interarrivals; the enlarged filtration then knows the next jump time, so the compensator identity is used only in F \mathbb{F} F . Lemma A.1 in Appendix § 8 shows that both constructions have the same law provided every event parameter (graph, depth, batch size, operator) is chosen from the revealed past before the corresponding interarrival is drawn. An adaptive scheduler may therefore depend on all past states, gradients, roots, and graph products, but not on the just-drawn interarrival.
At a jump the oracle value is g t ∈ R d g_t \in\mathbb{R}^d g t ∈ R d , queried at x t − x_{t-} x t − .
Assumption 2.5 (Conditional oracle moments). There are predictable vectors e t ∈ R d e_t \in\mathbb{R}^d e t ∈ R d and predictable scalars ς t ≥ 0 \varsigma_t \ge0 ς t ≥ 0 such that
E [ g t ∣ F t − ] = ∇ F ( x t − ) + e t , E [ ∥ g t − E [ g t ∣ F t − ] ∥ 2 ∣ F t − ] ≤ ς t 2 . (9) \mathbb{E}[g_t \mid\mathcal{F}_{t-}] = \nabla F(x_{t-}) + e_t, \qquad\mathbb{E}\left[\left\|g_t-\mathbb{E}[g_t\mid\mathcal{F}_{t-}]\right\|^2\mid\mathcal{F}_{t-}\right]\le\varsigma_t^2. \tag*{(9)} E [ g t ∣ F t − ] = ∇ F ( x t − ) + e t , E [ ∥ g t − E [ g t ∣ F t − ] ∥ 2 ∣ F t − ] ≤ ς t 2 . (9)
CQA-Net and the fixed-graph token have e t = 0 e_t=0 e t = 0 ; the changing-graph token, and D-CQA have a predictable bias.
Communication chronology and cost metrics
A communication subround exchanges one d d d -vector along every active edge. At jump k ≥ 1 k \ge1 k ≥ 1 , W k , q ∈ R m × m W_{k,q} \in\mathbb{R}^{m\times m} W k , q ∈ R m × m is the input-output operator of the depth-q q q mean-preserving protocol (see § 3.2 ). The graph and protocol parameters for jump k k k are fixed from the revealed past before E k − 1 E_{k-1} E k − 1 is exposed. At τ k \tau_k τ k the common pre-jump query is formed. If q > 0 q>0 q > 0 , fresh rows are generated and mixed first, and only then is a conditionally uniform root, independent of their innovations, revealed. If q = 0 q=0 q = 0 , the root may be revealed first, but only through the lazy coupling (7), which has the same law and avoids all unelected gradient evaluations. The selected row is then broadcast. Pre-shared clock and root streams implement this chronology for an oblivious schedule; an adaptive deployment needs separate primitives for clock and root generation, whose cost is not included in the round ledger.
We report expected events, component-gradient evaluations per node and in aggregate, critical-path neighbor rounds, and transmitted d d d -vectors. On a fixed undirected graph, D D D is a broadcast depth, M b r M_{\mathrm{br}} M br bounds its transmitted vectors, χ : = λ m / λ 2 \chi:= \lambda_m/\lambda_2 χ := λ m / λ 2 is the ratio of the largest to the smallest nonzero Laplacian eigenvalue, and one Laplacian multiplication sends at most 2 ∣ E ∣ 2|E| 2∣ E ∣ directed vectors. Changing-graph costs are expressed through certified mixing and dissemination bounds.
Algorithm design
The method has three layers, each with a narrow input-output interface. Figure 1 shows one network event. This section describes how to run the algorithms; moment and convergence estimates are in § 4 .
Figure 1. One event of CQA-Net. All nodes share the query, form local rows, run a finite mean-preserving protocol, reveal one row conditionally uniformly, and use its broadcast value in the common accelerated jump. At q = 0 q=0 q = 0 , the law-equivalent lazy coupling evaluates only the selected row, using a family of conditional row kernels fixed independently of the root.
The layers are the following.
The exact flow and Poisson jumps in Algorithm 1 produce one oracle vector per event; Theorem 4.3 analyzes this one-vector interface.
Algorithm 2 combines local rows, depth-q q q mixing, a uniform root, and broadcast into one common vector targeted at the average row; Lemma 4.6 establishes the required moments.
Algorithm 3 substitutes the network oracle into the flow and therefore gives every node the same trajectory x t x_t x t ; Theorem 4.8 treats static and changing graphs.
Layers 2 and 3 use three global primitives, which § 3.4 makes explicit. § 3.5 and § 3.6 replace these layers by a walking token (Algorithms 4 and 5) and by local states (Algorithm 6); the first layer is unchanged.
The basic continuized process
The first layer replaces the auxiliary low-dimensional searches used by early accelerated quasar-convex methods with an exactly solvable event-driven flow. The point x t x_t x t is the point at which the objective is controlled, while z t z_t z t is a momentum-like auxiliary state. Between events, z t z_t z t is fixed and x t x_t x t moves toward it; at an event, both states use the same oracle vector with different weights. The coefficients solve the two cancellation requirements of the quasar Lyapunov balance. The deterministic undamped specialization is the continuized quasar dynamics of Wang and Wibisono (2023); the parameter θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] leaves a tunable dissipative reserve when θ < 1 \theta<1 θ < 1 .
Starting from x 0 = z 0 ∈ R d x_0=z_0\in\mathbb{R}^d x 0 = z 0 ∈ R d , define
d x t = 2 γ t ( z t − x t ) d t − 1 L g t d n t , d z t = − γ θ 2 t 2 L g t d n t . (10) dx_t=\frac{2}{\gamma t}(z_t-x_t)\,dt-\frac{1}{L}g_t\,dn_t,\qquad dz_t=-\frac{\gamma\theta^2t}{2L}g_t\,dn_t. \tag*{(10)} d x t = γ t 2 ( z t − x t ) d t − L 1 g t d n t , d z t = − 2 L γ θ 2 t g t d n t . (10)
The oracle is queried at x t − x_{t-} x t − . If no event occurs on ( r , t ] (r,t] ( r , t ] , then
z t = z r , x t = z r + ( r t ) 2 / γ ( x r − z r ) . (11) z_t=z_r,\qquad x_t=z_r+\left(\frac{r}{t}\right)^{2/\gamma}(x_r-z_r). \tag*{(11)} z t = z r , x t = z r + ( t r ) 2/ γ ( x r − z r ) . (11)
The singularity at the origin is removable because x 0 = z 0 x_0=z_0 x 0 = z 0 : before the first event the state remains fixed. Because of (11) , the process can be simulated without a line search.
Algorithm 1 CQA: exact simulation of the one-vector continuized process
Require: horizon T > 0 T > 0 T > 0 , L > 0 L > 0 L > 0 , γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] , θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] , initial point x ( 0 ) x^{(0)} x ( 0 ) , oracle, optional Q \mathcal{Q} Q
τ 0 ← 0 \tau_0 \leftarrow0 τ 0 ← 0 , z ( 0 ) ← x ( 0 ) z^{(0)} \leftarrow x^{(0)} z ( 0 ) ← x ( 0 ) , k ← 0 k \leftarrow0 k ← 0
while true do
draw E k ∼ Exp ( 1 ) E_k \sim\operatorname{Exp}(1) E k ∼ Exp ( 1 ) and set τ k + 1 ← τ k + E k \tau_{k+1} \leftarrow\tau_k + E_k τ k + 1 ← τ k + E k
if τ k + 1 > T \tau_{k+1} > T τ k + 1 > T then
return z ( k ) + ( τ k / T ) 2 / γ ( x ( k ) − z ( k ) ) z^{(k)} + (\tau_k/T)^{2/\gamma}(x^{(k)} - z^{(k)}) z ( k ) + ( τ k / T ) 2/ γ ( x ( k ) − z ( k ) ) , with ( 0 / T ) 2 / γ : = 0 (0/T)^{2/\gamma} := 0 ( 0/ T ) 2/ γ := 0
end if
y ( k + 1 ) ← z ( k ) + ( τ k / τ k + 1 ) 2 / γ ( x ( k ) − z ( k ) ) y^{(k+1)} \leftarrow z^{(k)} + (\tau_k/\tau_{k+1})^{2/\gamma}(x^{(k)} - z^{(k)}) y ( k + 1 ) ← z ( k ) + ( τ k / τ k + 1 ) 2/ γ ( x ( k ) − z ( k ) )
g ( k + 1 ) ← Oracle ( y ( k + 1 ) ) g^{(k+1)} \leftarrow\operatorname{Oracle}(y^{(k+1)}) g ( k + 1 ) ← Oracle ( y ( k + 1 ) )
x ( k + 1 ) ← y ( k + 1 ) − g ( k + 1 ) / L x^{(k+1)} \leftarrow y^{(k+1)} - g^{(k+1)}/L x ( k + 1 ) ← y ( k + 1 ) − g ( k + 1 ) / L
z ( k + 1 ) ← z ( k ) − γ θ 2 τ k + 1 g ( k + 1 ) / ( 2 L ) z^{(k+1)} \leftarrow z^{(k)} - \gamma\theta^{2}\tau_{k+1}g^{(k+1)}/(2L) z ( k + 1 ) ← z ( k ) − γ θ 2 τ k + 1 g ( k + 1 ) / ( 2 L )
if the biased localized variant is used then
z ( k + 1 ) ← Π Q ( z ( k + 1 ) ) z^{(k+1)} \leftarrow\Pi_{\mathcal{Q}}(z^{(k+1)}) z ( k + 1 ) ← Π Q ( z ( k + 1 ) )
end if
k ← k + 1 k \leftarrow k + 1 k ← k + 1
end while
For a predictable biased oracle one may project the auxiliary jump onto a closed convex set Q ∋ { x 0 , x ⋆ } \mathcal{Q} \ni\{x_0,x^\star\} Q ∋ { x 0 , x ⋆ } . This projected variant is used only by the projected bound of Theorem 4.3 (b) and its application to the changing-graph token; CQA-Net, the fixed-graph token, and D-CQA never project.
Algorithm 1 is an exact simulator of (10) , not a time discretization. The Poisson clock is chosen because its compensator turns the expected weighted jump sum into the time integral of the continuous drift; this alignment permits the cancellation proof and gives E n T = T \mathbb{E}n_T = T E n T = T . We do not claim physical asynchrony, and we do not know whether the random clock is necessary; a deterministic grid would need a separate discrete estimate-sequence analysis.
Distributed gradient estimation
A depth-q q q mean-preserving mixer is a linear distributed protocol that is implementable in q q q neighbor rounds, may use finite local memory, and has an input-output map U ↦ W k , q U U \mapsto W_{k,q}U U ↦ W k , q U satisfying W k , q 1 = 1 W_{k,q}\mathbf{1} = \mathbf{1} W k , q 1 = 1 and 1 ⊤ W k , q = 1 ⊤ \mathbf{1}^{\top}W_{k,q} = \mathbf{1}^{\top} 1 ⊤ W k , q = 1 ⊤ ; set W k , 0 = I m W_{k,0} = I_m W k , 0 = I m . Put J : = m − 1 11 ⊤ J := m^{-1}\mathbf{1}\mathbf{1}^{\top} J := m − 1 1 1 ⊤ , the exact-averaging operator. Mean preservation is equivalent to W k , q J = J W k , q = J W_{k,q}J = JW_{k,q} = J W k , q J = J W k , q = J , so W k , q − J W_{k,q} - J W k , q − J acts only on the disagreement subspace. The definition covers ordinary products of one-round matrices and polynomial filters.
For a fixed connected undirected graph, a Chebyshev filter can be executed by a three-term recurrence. Let L L L be the Laplacian, let 0 < λ ‾ ≤ λ 2 ( L ) 0 < \underline{\lambda} \le\lambda_2(L) 0 < λ ≤ λ 2 ( L ) and λ m ( L ) ≤ λ ‾ \lambda_m(L) \le\overline{\lambda} λ m ( L ) ≤ λ , and put c = ( λ ‾ + λ ‾ ) / 2 c = (\underline{\lambda} + \overline{\lambda})/2 c = ( λ + λ ) /2 , r = ( λ ‾ − λ ‾ ) / 2 r = (\overline{\lambda} - \underline{\lambda})/2 r = ( λ − λ ) /2 , R = ( c I − L ) / r R = (cI - L)/r R = ( c I − L ) / r , and ξ = c / r \xi= c/r ξ = c / r . For an input row matrix U U U , set V 0 = U V_0 = U V 0 = U , V 1 = R U V_1 = RU V 1 = R U , a 0 = 1 a_0 = 1 a 0 = 1 , a 1 = ξ a_1 = \xi a 1 = ξ , and iterate
V ℓ + 1 = 2 R V ℓ − V ℓ − 1 , a ℓ + 1 = 2 ξ a ℓ − a ℓ − 1 . V_{\ell+1} = 2RV_\ell- V_{\ell-1}, \qquad a_{\ell+1} = 2\xi a_\ell- a_{\ell-1}. V ℓ + 1 = 2 R V ℓ − V ℓ − 1 , a ℓ + 1 = 2 ξ a ℓ − a ℓ − 1 .
The output is W q U = V q / a q W_qU = V_q/a_q W q U = V q / a q . Each recurrence step uses one Laplacian multiplication and stores two matrices locally. When the certified interval collapses, the one-round polynomial I − L / λ 2 I - L/\lambda_2 I − L / λ 2 gives exact averaging. The spectral contraction supplied by this implementation is analyzed after the oracle has been constructed.
Algorithm 2 turns arbitrary local rows into one common vector. At positive depth, the ordering “protocol and rows first, root second” prevents the selected index from influencing the row matrix whose average is to be estimated. At depth zero, a root-first implementation is permitted only through the root-independent lazy conditional kernel in (7) ; it is distributionally identical to selecting from a latent row family fixed independently of the root.
At q = 0 q = 0 q = 0 this is uniform node sampling followed by broadcast. Equation (7) is essential: marginal row unbiasedness alone would not suffice if the post-selection row law could depend on the root. Positive depth is not needed for unbiasedness. It can reduce the selected-row variance when the certified norm profile of W k , q W_{k,q} W k , q contracts; mean preservation by itself does not imply such a contraction. The price is one fresh row at every node and the additional neighbor rounds.
Algorithm 2 Finite-mixing uniform-row network oracle
Require: jump index k ≥ 1 k \ge1 k ≥ 1 , common query y ( k ) y^{(k)} y ( k ) , local row kernels, batch size b ∈ N b \in\mathbb{N} b ∈ N with b ≥ 1 b \ge1 b ≥ 1 , mean-preserving W k , q W_{k,q} W k , q
if q = 0 q = 0 q = 0 then
reveal R k R_k R k conditionally uniformly, independently of the latent row innovations
only node R k R_k R k samples K R k , k K_{R_k,k} K R k , k using a fresh seed independent of R k R_k R k
node R k R_k R k computes g R k ( k ) ( y ( k ) ) g_{R_k}^{(k)}(y^{(k)}) g R k ( k ) ( y ( k ) )
g ^ ( k ) ← g R k ( k ) ( y ( k ) ) \widehat{g}^{(k)} \leftarrow g_{R_k}^{(k)}(y^{(k)}) g ( k ) ← g R k ( k ) ( y ( k ) )
else
for all nodes i i i in parallel do
compute a fresh row g i ( k ) ( y ( k ) ) g_i^{(k)}(y^{(k)}) g i ( k ) ( y ( k ) )
end for
stack the rows in G ( k ) G^{(k)} G ( k ) and run the q q q -round protocol to form W k , q G ( k ) W_{k,q}G^{(k)} W k , q G ( k )
reveal R k R_k R k conditionally uniformly after W k , q W_{k,q} W k , q and all fresh rows are fixed
g ^ ( k ) ← e R k ⊤ W k , q G ( k ) \widehat{g}^{(k)} \leftarrow e_{R_k}^{\top}W_{k,q}G^{(k)} g ( k ) ← e R k ⊤ W k , q G ( k )
end if
node R k R_k R k broadcasts g ^ ( k ) \widehat{g}^{(k)} g ( k ) ; every node returns that vector
Algorithm 3 CQA-Net: synchronized common-state network acceleration
Require: the inputs of Algorithm 1, depth q q q , batch b b b , and an admissible event-indexed network schedule
every node keeps a copy of ( x , z , τ ) (x,z,\tau) ( x , z , τ ) , initialized to ( x ( 0 ) , x ( 0 ) , 0 ) (x^{(0)},x^{(0)},0) ( x ( 0 ) , x ( 0 ) , 0 ) , and runs Algorithm 1 on it with two changes:
before E k E_k E k is drawn, the graph and W k + 1 , q W_{k+1,q} W k + 1 , q are chosen from the revealed history, and E k E_k E k is common to all nodes
line 8 is replaced by Algorithm 2 at the common query y ( k + 1 ) y^{(k+1)} y ( k + 1 ) ; every node uses the broadcast g ^ ( k + 1 ) \widehat{g}^{(k+1)} g ( k + 1 )
Composition: CQA-Net
CQA requires one vector per event, and Algorithm 2 returns exactly one common vector. Their composition therefore needs no new state variable. Every node stores identical copies of x ( k ) x^{(k)} x ( k ) and z ( k ) z^{(k)} z ( k ) ; after a common flow and a broadcast jump, the copies remain identical. We call the resulting method CQA-Net .
Because all rows of the optimization state are identical, the objective is always evaluated at the common vector x t ∈ R d x_t \in\mathbb{R}^d x t ∈ R d ; no matrix-valued extension of F F F is introduced. The network matrix acts only on the transient stack of local oracle rows. This reduction works only because the last line of Algorithm 2 delivers the same vector to every node; Section 3.4 discusses the cost of that step and Sections 3.5–3.6 remove it.
Global primitives of CQA-Net
Algorithms 2 and 3 use three operations that involve the whole network at every event: (G1) exact dissemination of g ^ ( k ) \widehat{g}^{(k)} g ( k ) from R k R_k R k to every node (line 14 of Algorithm 2); (G2) a shared event clock; and (G3) a shared conditionally uniform root. (G1) is essential: the common-state invariant, and hence the reduction to Theorem 4.3, needs every node to receive exactly the same vector. Approximate averaging cannot replace it, since finitely many gossip rounds give close but unequal vectors and the copies of ( x , z ) (x,z) ( x , z ) drift apart. In federated learning (G1) is a server broadcast. In a peer-to-peer network it costs D D D rounds per event, which is exactly the term that separates the round count of CQA-Net from the local-state scale (Section 4.2). On a changing graph Theorem 4.8 takes a dissemination bound B b r B_{\mathrm{br}} B br as an input, and such a bound exists only if the schedule is known in advance or every window of rounds is connected.
We call a method fully decentralized if (R1) every message travels along one edge of the current graph; (R2) all nodes run the same code, with no fixed or moving coordinator; (R3) every node keeps its own copy of the optimization variables, brought together only by neighbor exchanges; and (R4) nodes never wait for an operation to finish over the whole network. Sections 3.5 and 3.6 give two implementations without (G1); Table 2 lists which requirements each design meets and what one event costs. The token removes all three global primitives but keeps a single mobile state. D-CQA has local states and keeps only a shared clock seed and synchronous rounds, as do synchronous gossip methods such as decentralized gradient descent and gradient tracking.
Table 2. Decentralization requirements and the cost of one event in the three implementations.
A walking token
In the token variant the state ( x , z , τ ) (x, z, \tau) ( x , z , τ ) is stored in a single message, the token , that moves along edges. The node holding it is the holder . The holder draws the next interarrival itself, so no shared clock is needed. The root is the node at which a random walk of the token stops, so no shared root is needed. The oracle vector is used where it is computed, so nothing is disseminated. Algorithm 1 is executed unchanged; only the place where its lines run moves through the network.
Walk matrices. At event k k k the token makes h w ≥ 0 h_w \ge0 h w ≥ 0 hops with matrices P k , 1 , … , P k , h w P_{k,1}, \ldots, P_{k,h_w} P k , 1 , … , P k , h w . Each of them is entrywise nonnegative, doubly stochastic, and supported on the self-loops and the active edges of its hop; Metropolis weights of the current graph are an example. The sequence is fixed from the revealed event history before the interarrival that produces τ k \tau_k τ k is drawn, and it does not depend on the positions visited by the walk itself. We write o k o_k o k for the holder at the start of event k k k , so o k = R k − 1 o_k = R_{k-1} o k = R k − 1 for k ≥ 2 k \ge2 k ≥ 2 and o 1 o_1 o 1 is the initial holder.
Local mixer. For q ≥ 0 q \ge0 q ≥ 0 the token oracle uses a mean-preserving, F \mathbb{F} F -predictable W k , q W_{k,q} W k , q with the ball-support property ( W k , q ) v i = 0 (W_{k,q})_{vi} = 0 ( W k , q ) v i = 0 whenever dist ( v , i ) > q \operatorname{dist}(v,i) > q dist ( v , i ) > q ; we set W k , 0 = I m W_{k,0} = I_m W k , 0 = I m . On a fixed graph every degree-q q q Laplacian polynomial has this property, in particular the normalized Chebyshev filter of § 3.2 . Then the selected row e v T W k , q G ( k ) \mathbf{e}_v^{\mathsf{T}}W_{k,q}G^{(k)} e v T W k , q G ( k ) depends only on the rows of the ball B q ( v ) = { i : dist ( v , i ) ≤ q } B_q(v) = \{i : \operatorname{dist}(v,i) \le q\} B q ( v ) = { i : dist ( v , i ) ≤ q } . To evaluate it, v v v floods the query to B q ( v ) B_q(v) B q ( v ) , every node of the ball forms its row, and the three-term recurrence is run only where it is needed: step ℓ \ell ℓ of the recurrence is computed at the nodes with dist ( ⋅ , v ) ≤ q − ℓ \operatorname{dist}(\mathord{\cdot},v) \le q - \ell dist ( ⋅ , v ) ≤ q − ℓ . This costs 2 q 2q 2 q subrounds. On a changing graph we use q = 0 q = 0 q = 0 , because a ball-local evaluation of a time-varying product is not considered here.
Two modes. In the fixed mode the graph and the walk matrix P k , s = P = P T P_{k,s} = P = P^{\mathsf{T}} P k , s = P = P T are fixed, and the oracle is reweighted by ω k = 1 / ( m ( P h w ) o k R k ) \omega_k = 1/(m(P^{h_w})_{o_kR_k}) ω k = 1/ ( m ( P h w ) o k R k ) , the inverse of m m m times the probability of the realized endpoint. Node i i i stores row i i i of P h w P^{h_w} P h w , which a one-time setup computes by h w h_w h w rounds of gossip with messages of m m m scalars. In the changing mode no weight is used, ω k = 1 \omega_k = 1 ω k = 1 . Optionally, the auxiliary jump is projected onto a closed bounded convex set Q ∋ x ( 0 ) , x ⋆ Q \ni x^{(0)}, x^\star Q ∋ x ( 0 ) , x ⋆ , as in the localized variant of Algorithm 1; the projection is needed only for the second of the two bounds in Corollary 4.14. The fixed mode needs θ < 1 \theta< 1 θ < 1 , because the walk creates multiplicative noise that the reserve must absorb.
Chronology, storage, and cost. The walk runs after the query is formed and before the row is sampled, so its endpoint is part of the event mark, exactly as R k R_k R k in § 2.5 ; the walk randomness is independent of the interarrivals, so Lemma A.1 applies verbatim. The token carries ( x , z , τ ) (x,z,\tau) ( x , z , τ ) between events and ( y , z , τ ′ , o ) (y,z,\tau',o) ( y , z , τ ′ , o ) during the walk, that is, 2 d + 2 2d + 2 2 d + 2 scalars. Table 2 gives the cost of one event: h w h_w h w sequential hops replace the D D D rounds of dissemination, and Remark 4.15 shows that h w h_w h w is of order t r e l log m t_{\mathrm{rel}}\log m t rel log m , where t r e l = ( 1 − λ P ) − 1 t_{\mathrm{rel}} = (1 - \lambda_P)^{-1} t rel = ( 1 − λ P ) − 1 .
Algorithm 4 Walking-token network oracle (replaces Algorithm 2)
Require: event index k ≥ 1 k \ge1 k ≥ 1 ; token ( y ( k ) , z , τ k , o k ) (y^{(k)}, z, \tau_k, o_k) ( y ( k ) , z , τ k , o k ) at node o k o_k o k ; hop count h w h_w h w ; walk matrices P k , 1 , … , P k , h w P_{k,1}, \ldots, P_{k,h_w} P k , 1 , … , P k , h w ; depth q q q and W k , q W_{k,q} W k , q as above; batch b ≥ 1 b \ge1 b ≥ 1 ; mode ∈ { fixed , changing } \in\{\text{fixed},\text{changing}\} ∈ { fixed , changing }
v ← o k v \leftarrow o_k v ← o k
for s = 1 , … , h w s = 1, \ldots, h_w s = 1 , … , h w do
node v v v draws j j j with probability ( P k , s ) v j (P_{k,s})_{vj} ( P k , s ) v j , independently of all row innovations and interarrivals
if j ≠ v j \ne v j = v , node v v v sends the token to its neighbor j j j ; v ← j v \leftarrow j v ← j
end for
R k ← v R_k \leftarrow v R k ← v ▹ replaces the uniform root of Algorithm 2
if q = 0 q = 0 q = 0 then
node R k R_k R k samples g ~ ( k ) ∼ K R k , k \tilde{g}^{(k)} \sim K_{R_k,k} g ~ ( k ) ∼ K R k , k with a fresh seed
else
R k R_k R k floods y ( k ) y^{(k)} y ( k ) to B q ( R k ) B_q(R_k) B q ( R k ) ▹ q q q subrounds
every i ∈ B q ( R k ) i \in B_q(R_k) i ∈ B q ( R k ) samples a fresh row g i ( k ) ( y ( k ) ) ∼ K i , k g_i^{(k)}(y^{(k)}) \sim K_{i,k} g i ( k ) ( y ( k ) ) ∼ K i , k
run the recurrence of § 3.2 ; step ℓ \ell ℓ only at dist ( ⋅ , R k ) ≤ q − ℓ \operatorname{dist}(\cdot,R_k) \le q-\ell dist ( ⋅ , R k ) ≤ q − ℓ ▹ q q q subrounds
g ~ ( k ) ← e R k ⊤ W k , q G ( k ) \tilde{g}^{(k)} \leftarrow e_{R_k}^{\top}W_{k,q}G^{(k)} g ~ ( k ) ← e R k ⊤ W k , q G ( k ) at node R k R_k R k
end if
if mode = = = fixed then
ω k ← 1 / ( m ( P h w ) o k R k ) \omega_k \leftarrow1/(m(P^{h_w})_{o_kR_k}) ω k ← 1/ ( m ( P h w ) o k R k ) ▹ read from the stored row of P h w P^{h_w} P h w
else
ω k ← 1 \omega_k \leftarrow1 ω k ← 1
end if
g ~ ( k ) ← ω k g ~ ( k ) \tilde{g}^{(k)} \leftarrow\omega_k\tilde{g}^{(k)} g ~ ( k ) ← ω k g ~ ( k ) ; the vector stays at node R k R_k R k ▹ no dissemination
Algorithm 5 CQA with a walking token (replaces Algorithm 3)
Require: the inputs of Algorithm 1 with θ < 1 \theta< 1 θ < 1 in fixed mode; h w h_w h w , q q q , b b b ; initial holder o 1 o_1 o 1 ; optionally, in changing mode, a closed bounded convex Q ∋ x ( 0 ) , x ⋆ Q \ni x^{(0)}, x^\star Q ∋ x ( 0 ) , x ⋆
the token stores ( x , z , τ ) = ( x ( 0 ) , x ( 0 ) , 0 ) (x,z,\tau)=(x^{(0)},x^{(0)},0) ( x , z , τ ) = ( x ( 0 ) , x ( 0 ) , 0 ) and the identity of its holder; the holder runs Algorithm 1 with three changes:
h w h_w h w , q q q , W k + 1 , q W_{k+1,q} W k + 1 , q and the walk matrices are fixed from the revealed history, and the holder alone draws E k E_k E k ▹ no shared clock
line 8 is replaced by Algorithm 4, which moves the token to R k + 1 R_{k+1} R k + 1 ; lines 9–10 are executed there
if Q Q Q is given, line 12 projects z z z onto Q Q Q
Local states: D-CQA
The second implementation removes the common state. Every node keeps its own pair ( x i , z i ) (x_i,z_i) ( x i , z i ) , runs the closed-form flow, takes a local step with its own row at its own query, and then q q q rounds of a mean-preserving protocol mix the states , not the rows. There is no root, no dissemination and no token. We write X , Z ∈ R m × d X,Z \in\mathbb{R}^{m \times d} X , Z ∈ R m × d for the stacked states, with rows x i , z i x_i,z_i x i , z i , and x ˉ = m − 1 X ⊤ 1 \bar{x}=m^{-1}X^\top\mathbf{1} x ˉ = m − 1 X ⊤ 1 , z ˉ = m − 1 Z ⊤ 1 \bar{z}=m^{-1}Z^\top\mathbf{1} z ˉ = m − 1 Z ⊤ 1 . The disagreement is X ⊥ : = ( I − J ) X X_\perp:= (I-J)X X ⊥ := ( I − J ) X . Between events the flowed states are X ( t ) = Z + ( τ k / t ) 2 / γ ( X − Z ) X(t)=Z+(\tau_k/t)^{2/\gamma}(X-Z) X ( t ) = Z + ( τ k / t ) 2/ γ ( X − Z ) .
Relative to Algorithms 2–3, the rows are no longer mixed, the uniform root and the dissemination step disappear, the queries y i y_i y i differ across nodes, and every node returns its own point. The only global element left is the shared clock seed: every node generates the same event times locally, without communication, and rounds are synchronous. Each event costs one row per node, q q q rounds and 4 ∣ E ∣ q 4|E|q 4∣ E ∣ q transmitted vectors in R d \mathbb{R}^d R d . Because the queries differ, quasar-convexity can no longer be applied at the point where the gradients are evaluated. Section 4.4 therefore analyzes the network average, for which the disagreement acts as a bias.
Main results
Two results carry the analysis. Theorem 4.3 bounds the continuized process for any oracle with a predictable bias and a state-dependent variance. Lemma 4.6 computes the conditional moments of every network oracle that returns one, possibly reweighted, row of a mixed matrix. Every other statement substitutes moments into these two results, certifies the network operators, or closes the resulting oracle inequality. For CQA-Net, Lemma 4.6 (ii) and Theorem 4.3 (a) give Theorem 4.8 , which Corollary 4.9 closes, and Lemma 4.7 and Corollary 4.11 certify the operators. For the Algorithm 6 D-CQA: decentralized CQA with local states (replaces Algorithms 2 and 3)
Require: T , L > 0 T, L > 0 T , L > 0 ; γ , θ ∈ ( 0 , 1 ] \gamma, \theta\in(0, 1] γ , θ ∈ ( 0 , 1 ] ; batch b ≥ 1 b \ge1 b ≥ 1 ; common x ( 0 ) x^{(0)} x ( 0 ) ; an admissible sequence of mean-preserving q q q -round mixers W k W_k W k
every node sets x i ← x ( 0 ) , z i ← x ( 0 ) ; τ 0 ← 0 , k ← 0 x_i \leftarrow x^{(0)}, z_i \leftarrow x^{(0)}; \ \tau_0 \leftarrow0, \ k \leftarrow0 x i ← x ( 0 ) , z i ← x ( 0 ) ; τ 0 ← 0 , k ← 0
while true do
fix W k + 1 W_{k+1} W k + 1 from the revealed history ▷ before E k E_k E k
every node computes the common E k ∼ Exp ( 1 ) E_k \sim\operatorname{Exp}(1) E k ∼ Exp ( 1 ) from a shared seed; τ k + 1 ← τ k + E k \tau_{k+1} \leftarrow\tau_k + E_k τ k + 1 ← τ k + E k
if τ k + 1 > T \tau_{k+1} > T τ k + 1 > T then
every node returns z i + ( τ k / T ) 2 / γ ( x i − z i ) z_i + (\tau_k/T)^{2/\gamma}(x_i-z_i) z i + ( τ k / T ) 2/ γ ( x i − z i ) , with ( 0 / T ) 2 / γ : = 0 (0/T)^{2/\gamma} := 0 ( 0/ T ) 2/ γ := 0 ; stop
end if
for all nodes i i i in parallel do
y i ← z i + ( τ k / τ k + 1 ) 2 / γ ( x i − z i ) y_i \leftarrow z_i + (\tau_k/\tau_{k+1})^{2/\gamma}(x_i-z_i) y i ← z i + ( τ k / τ k + 1 ) 2/ γ ( x i − z i )
g i ← g_i \leftarrow g i ← fresh local row at y i y_i y i ▷ own query, own data
x ~ i ← y i − g i / L , z ~ i ← z i − γ θ 2 τ k + 1 g i / ( 2 L ) \widetilde{x}_i \leftarrow y_i-g_i/L,\quad\widetilde{z}_i \leftarrow z_i-\gamma\theta^2\tau_{k+1}g_i/(2L) x i ← y i − g i / L , z i ← z i − γ θ 2 τ k + 1 g i / ( 2 L )
end for
run the q q q -round protocol on both stacks: X ← W k + 1 X ~ , Z ← W k + 1 Z ~ X \leftarrow W_{k+1}\widetilde{X},\ Z \leftarrow W_{k+1}\widetilde{Z} X ← W k + 1 X , Z ← W k + 1 Z ▷ each message: two vectors in R d \mathbb{R}^d R d
k ← k + 1 k \leftarrow k+1 k ← k + 1
end while
token, Lemma 4.12 and Lemma 4.6 (ii)–(iii) give Corollaries 4.13 and 4.14. For D-CQA, Lemmas 4.17 and 4.18 and Theorem 4.3 (a) give Theorem 4.19 . The quantities to be certified are therefore the oracle bias and variance envelope, the operator norms ∥ W k , q − J ∥ 2 \lVert W_{k,q}-J\rVert_2 ∥ W k , q − J ∥ 2 and m − 1 ∥ W k , q ∥ F 2 m^{-1}\lVert W_{k,q}\rVert_{\mathrm{F}}^2 m − 1 ∥ W k , q ∥ F 2 , and the walk contraction.
The basic process and the one-vector oracle
For t > 0 t>0 t > 0 , put
A t = γ 2 θ 2 t 2 4 L , c t = γ θ 2 t 2 L , V θ = 1 + θ 2 2 , (12) A_t=\frac{\gamma^2\theta^2t^2}{4L},\qquad
c_t=\frac{\gamma\theta^2t}{2L},\qquad
V_\theta=\frac{1+\theta^2}{2}, \tag*{(12)} A t = 4 L γ 2 θ 2 t 2 , c t = 2 L γ θ 2 t , V θ = 2 1 + θ 2 , (12)
and define
Φ t = A t ( F ( x t ) − F ( x ⋆ ) ) + 1 2 ∥ z t − x ⋆ ∥ 2 . (13) \Phi_t=A_t\bigl(F(x_t)-F(x^\star)\bigr)+\frac{1}{2}\lVert z_t-x^\star\rVert^2. \tag*{(13)} Φ t = A t ( F ( x t ) − F ( x ⋆ ) ) + 2 1 ∥ z t − x ⋆ ∥ 2 . (13)
The weights solve the two cancellation equations A t ′ = γ c t A_t'=\gamma c_t A t ′ = γ c t and c t 2 = θ 2 A t / L c_t^2=\theta^2 A_t/L c t 2 = θ 2 A t / L . Together with 2 A t / ( γ t ) = c t 2A_t/(\gamma t)=c_t 2 A t / ( γ t ) = c t and A t / A T = t 2 / T 2 A_t/A_T=t^2/T^2 A t / A T = t 2 / T 2 , these identities follow by direct substitution. Within the nonzero positive quadratic–linear family, the linear equation alone leaves an overall scale free, but the quadratic equation fixes that scale; with the process normalization above the two equations determine the displayed weights exactly. (The identically zero pair is the irrelevant degenerate solution.)
For a predictable mark kernel K t K_t K t from § 2.4 , define the predictable extended drift operator on a smooth test function Ψ ( t , x , z ) \Psi(t,x,z) Ψ ( t , x , z ) by
D t Ψ ( t , x , z ) = ∂ t Ψ ( t , x , z ) + ⟨ ∇ x Ψ ( t , x , z ) , 2 γ t ( z − x ) ⟩ + ∫ [ Ψ ( t , x − g / L , z − c t g ) − Ψ ( t , x , z ) ] K t ( d g ) , (14) \mathcal{D}_t\Psi(t,x,z)=\partial_t\Psi(t,x,z)+\left\langle\nabla_x\Psi(t,x,z),\frac{2}{\gamma t}(z-x)\right\rangle
+\int\left[\Psi(t,x-g/L,z-c_tg)-\Psi(t,x,z)\right]K_t(\mathrm{d}g), \tag*{(14)} D t Ψ ( t , x , z ) = ∂ t Ψ ( t , x , z ) + ⟨ ∇ x Ψ ( t , x , z ) , γ t 2 ( z − x ) ⟩ + ∫ [ Ψ ( t , x − g / L , z − c t g ) − Ψ ( t , x , z ) ] K t ( d g ) , (14)
with z − c t g z-c_tg z − c t g replaced by its projection in the localized variant. Under Markovian rules this is the usual time-inhomogeneous PDMP generator; under the history-dependent model it is a predictable drift characteristic, and the proof uses the Itô compensator identity rather than the Markov property.
Lemma 4.1 (Predictable Lyapunov drift). Suppose that F F F is L L L -smooth and γ \gamma γ -quasar-convex, and that Assumption 2.5 holds. For the unprojected process,
D t Φ t ≤ A t ′ ( F ( x t − ) − F ( x ⋆ ) ) − c t ⟨ ∇ F ( x t − ) , x t − − x ⋆ ⟩ − A t ( 1 − θ 2 ) 2 L ∥ ∇ F ( x t − ) ∥ 2 + A t V θ L ζ t 2 − c t ⟨ z t − − x ⋆ , e t ⟩ + A t θ 2 L ⟨ ∇ F ( x t − ) , e t ⟩ + A t V θ L ∥ e t ∥ 2 . (15) \begin{aligned}
\mathcal{D}_t\Phi_t
&\le A_t'\bigl(F(x_{t-})-F(x^\star)\bigr)-c_t\langle\nabla F(x_{t-}),x_{t-}-x^\star\rangle\\
&\quad-\frac{A_t(1-\theta^2)}{2L}\lVert\nabla F(x_{t-})\rVert^2+\frac{A_tV_\theta}{L}\zeta_t^2\\
&\quad-c_t\langle z_{t-}-x^\star,e_t\rangle+\frac{A_t\theta^2}{L}\langle\nabla F(x_{t-}),e_t\rangle+\frac{A_tV_\theta}{L}\lVert e_t\rVert^2. \tag*{(15)}
\end{aligned} D t Φ t ≤ A t ′ ( F ( x t − ) − F ( x ⋆ ) ) − c t ⟨ ∇ F ( x t − ) , x t − − x ⋆ ⟩ − 2 L A t ( 1 − θ 2 ) ∥ ∇ F ( x t − ) ∥ 2 + L A t V θ ζ t 2 − c t ⟨ z t − − x ⋆ , e t ⟩ + L A t θ 2 ⟨ ∇ F ( x t − ) , e t ⟩ + L A t V θ ∥ e t ∥ 2 . (15)
The first line is nonpositive because A t ′ = γ c t A'_t=\gamma c_t A t ′ = γ c t and (2) . The third term is the dissipative reserve. If the auxiliary jump is projected onto a bounded convex Q ∋ { x 0 , x ⋆ } Q\ni\{x_0,x^\star\} Q ∋ { x 0 , x ⋆ } , the term − c t ⟨ z t − − x ⋆ , e t ⟩ -c_t\langle z_{t-}-x^\star,e_t\rangle − c t ⟨ z t − − x ⋆ , e t ⟩ is at most c t R Q ∥ e t ∥ c_tR_Q\|e_t\| c t R Q ∥ e t ∥ , where R Q = sup z ∈ Q ∥ z − x ⋆ ∥ R_Q=\sup_{z\in Q}\|z-x^\star\| R Q = sup z ∈ Q ∥ z − x ⋆ ∥ .
Proof. The deterministic drift and the two jump increments are computed before taking conditional moments. In the last part, the weights (12) remove every occurrence of the auxiliary state and leave the quasar inequality at the single point x t − x_{t-} x t − .
Step 1: drift between jumps. Between events, z t z_t z t is constant and x ˙ t = 2 ( z t − x t ) / ( γ t ) \dot{x}_t=2(z_t-x_t)/(\gamma t) x ˙ t = 2 ( z t − x t ) / ( γ t ) . The time derivative of (13) and the drift of x t x_t x t give
A t ′ ( F ( x t − ) − F ( x ⋆ ) ) + 2 A t γ t ⟨ ∇ F ( x t − ) , z t − − x t − ⟩ . A'_t\bigl(F(x_{t-})-F(x^\star)\bigr)+\frac{2A_t}{\gamma t}\langle\nabla F(x_{t-}),z_{t-}-x_{t-}\rangle. A t ′ ( F ( x t − ) − F ( x ⋆ ) ) + γ t 2 A t ⟨ ∇ F ( x t − ) , z t − − x t − ⟩ .
The identity 2 A t / ( γ t ) = c t 2A_t/(\gamma t)=c_t 2 A t / ( γ t ) = c t converts the second coefficient to the same c t c_t c t that appears in the auxiliary jump.
Step 2: jump contributions. Smoothness gives
F ( x t − − g t / L ) − F ( x t − ) ≤ − 1 L ⟨ ∇ F ( x t − ) , g t ⟩ + 1 2 L ∥ g t ∥ 2 . F(x_{t-}-g_t/L)-F(x_{t-})\leq-\frac{1}{L}\langle\nabla F(x_{t-}),g_t\rangle+\frac{1}{2L}\|g_t\|^2. F ( x t − − g t / L ) − F ( x t − ) ≤ − L 1 ⟨ ∇ F ( x t − ) , g t ⟩ + 2 L 1 ∥ g t ∥ 2 .
The auxiliary distance changes exactly by
1 2 ∥ z t − − c t g t − x ⋆ ∥ 2 − 1 2 ∥ z t − − x ⋆ ∥ 2 = − c t ⟨ z t − − x ⋆ , g t ⟩ + c t 2 2 ∥ g t ∥ 2 . \frac{1}{2}\|z_{t-}-c_tg_t-x^\star\|^2-\frac{1}{2}\|z_{t-}-x^\star\|^2=-c_t\langle z_{t-}-x^\star,g_t\rangle+\frac{c_t^2}{2}\|g_t\|^2. 2 1 ∥ z t − − c t g t − x ⋆ ∥ 2 − 2 1 ∥ z t − − x ⋆ ∥ 2 = − c t ⟨ z t − − x ⋆ , g t ⟩ + 2 c t 2 ∥ g t ∥ 2 .
Projection cannot increase this distance because x ⋆ ∈ Q x^\star\in Q x ⋆ ∈ Q .
Step 3: conditional moments and cancellation. The conditional moment relations (9) imply
E [ g t ∣ F t − ] = ∇ F ( x t − ) + e t , E [ ∥ g t ∥ 2 ∣ F t − ] ≤ ∥ ∇ F ( x t − ) + e t ∥ 2 + ς t 2 . \mathbb{E}[g_t\mid\mathcal{F}_{t-}]=\nabla F(x_{t-})+e_t,\qquad
\mathbb{E}[\|g_t\|^2\mid\mathcal{F}_{t-}]\leq\|\nabla F(x_{t-})+e_t\|^2+\varsigma_t^2. E [ g t ∣ F t − ] = ∇ F ( x t − ) + e t , E [ ∥ g t ∥ 2 ∣ F t − ] ≤ ∥∇ F ( x t − ) + e t ∥ 2 + ς t 2 .
The term A t ′ [ F ( x t − ) − F ( x ⋆ ) ] A'_t[F(x_{t-})-F(x^\star)] A t ′ [ F ( x t − ) − F ( x ⋆ )] pairs with the quasar inner product through A t ′ = γ c t A'_t=\gamma c_t A t ′ = γ c t ; the z t − z_{t-} z t − part of the drift term cancels the linear auxiliary jump and leaves − c t ⟨ ∇ F ( x t − ) , x t − − x ⋆ ⟩ -c_t\langle\nabla F(x_{t-}),x_{t-}-x^\star\rangle − c t ⟨ ∇ F ( x t − ) , x t − − x ⋆ ⟩ ; the linear part of the x t x_t x t jump, − A t ∥ ∇ F ( x t − ) ∥ 2 / L -A_t\|\nabla F(x_{t-})\|^2/L − A t ∥∇ F ( x t − ) ∥ 2 / L , is partly cancelled by the two jump squares, A t ( 1 + θ 2 ) ∥ ∇ F ( x t − ) ∥ 2 / ( 2 L ) A_t(1+\theta^2)\|\nabla F(x_{t-})\|^2/(2L) A t ( 1 + θ 2 ) ∥∇ F ( x t − ) ∥ 2 / ( 2 L ) , which leaves the reserve; and the centered fluctuation gives A t V θ ς t 2 / L A_tV_\theta\varsigma_t^2/L A t V θ ς t 2 / L . Here c t 2 = θ 2 A t / L c_t^2=\theta^2A_t/L c t 2 = θ 2 A t / L and V θ = ( 1 + θ 2 ) / 2 V_\theta=(1+\theta^2)/2 V θ = ( 1 + θ 2 ) /2 combine the quadratic jump terms. Expanding the mean as ∇ F ( x t − ) + e t \nabla F(x_{t-})+e_t ∇ F ( x t − ) + e t gives the three bias terms in the last two lines of (15) .
The next theorem integrates Lemma 4.1. It is the only place where the Poisson clock, rather than merely the event-driven algorithm, enters the convergence proof, and every rate in this paper is obtained from it by substituting conditional oracle moments. Two elementary integral inequalities are used to close the estimates.
Lemma 4.2 (Linear and square-root Gronwall inequalities). Let u : [ 0 , T ] → [ 0 , ∞ ) u:[0,T]\to[0,\infty) u : [ 0 , T ] → [ 0 , ∞ ) be bounded and measurable, let a ≥ 0 a\geq0 a ≥ 0 , and let p , h ≥ 0 p,h\geq0 p , h ≥ 0 be integrable on [ 0 , T ] [0,T] [ 0 , T ] .
(i) If λ ≥ 0 \lambda\geq0 λ ≥ 0 and u ( t ) ≤ a + ∫ 0 t [ λ u ( r ) + h ( r ) ] d r u(t)\leq a+\int_0^t[\lambda u(r)+h(r)]\,\mathrm{d}r u ( t ) ≤ a + ∫ 0 t [ λ u ( r ) + h ( r )] d r for all t t t , then
u ( t ) ≤ e λ t [ a + ∫ 0 t e − λ r h ( r ) d r ] ≤ e λ t [ a + ∫ 0 t h ( r ) d r ] . (16) u(t)\leq e^{\lambda t}\left[a+\int_0^t e^{-\lambda r}h(r)\,\mathrm{d}r\right]\leq e^{\lambda t}\left[a+\int_0^t h(r)\,\mathrm{d}r\right]. \tag*{(16)} u ( t ) ≤ e λ t [ a + ∫ 0 t e − λ r h ( r ) d r ] ≤ e λ t [ a + ∫ 0 t h ( r ) d r ] . (16)
(ii) If a > 0 a>0 a > 0 and u ( t ) ≤ a + ∫ 0 t [ p ( r ) u ( r ) + h ( r ) ] d r u(t)\leq a+\int_0^t[p(r)\sqrt{u(r)}+h(r)]\,\mathrm{d}r u ( t ) ≤ a + ∫ 0 t [ p ( r ) u ( r ) + h ( r )] d r for all t t t , then
u ( t ) ≤ a + ∫ 0 t h ( r ) d r + 1 2 ∫ 0 t p ( r ) d r . (17) \sqrt{u(t)}\leq\sqrt{a+\int_0^t h(r)\,\mathrm{d}r}+\frac{1}{2}\int_0^t p(r)\,\mathrm{d}r. \tag*{(17)} u ( t ) ≤ a + ∫ 0 t h ( r ) d r + 2 1 ∫ 0 t p ( r ) d r . (17)
Proof. Part (i) is the classical Gronwall inequality. For part (ii), let v ( t ) v(t) v ( t ) be the right side of the assumed inequality and H ( t ) = a + ∫ 0 t h H(t)=a+\int_0^t h H ( t ) = a + ∫ 0 t h . Then v v v is absolutely continuous, u ≤ v u\leq v u ≤ v , v ≥ H > 0 v\geq H>0 v ≥ H > 0 , and v ′ ≤ p v + h v'\leq p\sqrt{v}+h v ′ ≤ p v + h almost everywhere. Therefore ( v ) ′ = v ′ / ( 2 v ) ≤ p / 2 + h / ( 2 H ) = p / 2 + ( H ) ′ (\sqrt{v})'=v'/(2\sqrt{v})\leq p/2+h/(2\sqrt{H})=p/2+(\sqrt{H})' ( v ) ′ = v ′ / ( 2 v ) ≤ p /2 + h / ( 2 H ) = p /2 + ( H ) ′ , and integration from 0 0 0 , where v ( 0 ) = H ( 0 ) = a v(0)=H(0)=a v ( 0 ) = H ( 0 ) = a , gives (17) .
Theorem 4.3 (Master continuized acceleration with an inexact oracle). Suppose that F F F is L L L -smooth and γ \gamma γ -quasar-convex with respect to x ⋆ x^\star x ⋆ , let θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] , and let Algorithm 1 start from x 0 = z 0 x_0=z_0 x 0 = z 0 with R 0 = ∥ x 0 − x ⋆ ∥ R_0=\lVert x_0-x^\star\rVert R 0 = ∥ x 0 − x ⋆ ∥ . Let Assumption 2.5 hold, and suppose that for a constant η ≥ 0 \eta\ge0 η ≥ 0 and a predictable ς ˉ t ≥ 0 \bar{\varsigma}_t \ge0 ς ˉ t ≥ 0 ,
ς ˉ t 2 ≤ η ∥ ∇ F ( x t − ) ∥ 2 + ς ˉ t 2 , V θ η ≤ 1 − θ 2 2 . (18) \bar{\varsigma}_t^2 \le\eta\lVert\nabla F(x_{t-})\rVert^2+\bar{\varsigma}_t^2,\qquad V_\theta\eta\le\frac{1-\theta^2}{2}. \tag*{(18)} ς ˉ t 2 ≤ η ∥ ∇ F ( x t − ) ∥ 2 + ς ˉ t 2 , V θ η ≤ 2 1 − θ 2 . (18) Assume the finite-horizon conditions
E sup 0 ≤ t ≤ T Φ t < ∞ , \mathbb{E}\sup_{0\le t\le T}\Phi_t<\infty, E 0 ≤ t ≤ T sup Φ t < ∞ , E sup 0 ≤ t ≤ T ( ∥ x t ∥ + ∥ z t ∥ ) < ∞ , \mathbb{E}\sup_{0\le t\le T}(\lVert x_t\rVert+\lVert z_t\rVert)<\infty, E 0 ≤ t ≤ T sup (∥ x t ∥ + ∥ z t ∥) < ∞ , E ∫ 0 T A t ∥ ∇ F ( x t ) ∥ 2 d t < ∞ , \mathbb{E}\int_0^T A_t\lVert\nabla F(x_t)\rVert^2\,dt<\infty, E ∫ 0 T A t ∥ ∇ F ( x t ) ∥ 2 d t < ∞ , E ∫ 0 T A t ς ˉ t 2 d t < ∞ . \mathbb{E}\int_0^T A_t\bar{\varsigma}_t^2\,dt<\infty. E ∫ 0 T A t ς ˉ t 2 d t < ∞. (a) Mean-square bias, no projection. Let e ˉ : [ 0 , T ] → [ 0 , ∞ ) \bar e:[0,T]\to[0,\infty) e ˉ : [ 0 , T ] → [ 0 , ∞ ) be deterministic, measurable, with ∫ 0 T t 2 e ˉ t 2 d t < ∞ \int_0^T t^2\bar e_t^2\,dt<\infty ∫ 0 T t 2 e ˉ t 2 d t < ∞ , and suppose E ∥ e t ∥ 2 ≤ e ˉ t 2 \mathbb{E}\lVert e_t\rVert^2\le\bar e_t^2 E ∥ e t ∥ 2 ≤ e ˉ t 2 for t ∈ [ 0 , T ] t\in[0,T] t ∈ [ 0 , T ] . Put
Γ T : = 2 L R 0 2 γ 2 θ 2 T 2 + V θ L T 2 ∫ 0 T t 2 ( E ς ˉ t 2 + e ˉ t 2 ) d t , B T : = ( 1 + θ ) θ 2 L T ∫ 0 T t e ˉ t d t . \Gamma_T:=\frac{2LR_0^2}{\gamma^2\theta^2T^2}+\frac{V_\theta}{LT^2}\int_0^T t^2\left(\mathbb{E}\bar{\varsigma}_t^2+\bar e_t^2\right)\,dt,\qquad B_T:=\frac{(1+\theta)\theta}{\sqrt{2LT}}\int_0^T t\bar e_t\,dt. Γ T := γ 2 θ 2 T 2 2 L R 0 2 + L T 2 V θ ∫ 0 T t 2 ( E ς ˉ t 2 + e ˉ t 2 ) d t , B T := 2 L T ( 1 + θ ) θ ∫ 0 T t e ˉ t d t . Then
E [ F ( x T ) − F ( x ⋆ ) ] + ( 1 − θ 2 ) / 2 − V θ η L T 2 ∫ 0 T t 2 E ∥ ∇ F ( x t ) ∥ 2 d t ≤ ( Γ T + B T ) 2 . (19) \mathbb{E}\left[F(x_T)-F(x^\star)\right]+\frac{(1-\theta^2)/2-V_\theta\eta}{LT^2}\int_0^T t^2\mathbb{E}\lVert\nabla F(x_t)\rVert^2\,dt\le\left(\sqrt{\Gamma_T}+B_T\right)^2. \tag*{(19)} E [ F ( x T ) − F ( x ⋆ ) ] + L T 2 ( 1 − θ 2 ) /2 − V θ η ∫ 0 T t 2 E ∥ ∇ F ( x t ) ∥ 2 d t ≤ ( Γ T + B T ) 2 . (19) In particular, for an unbiased oracle (e t = 0 e_t=0 e t = 0 , e ˉ = 0 \bar e=0 e ˉ = 0 ),
E [ F ( x T ) − F ( x ⋆ ) ] + ( 1 − θ 2 ) / 2 − V θ η L T 2 ∫ 0 T t 2 E ∥ ∇ F ( x t ) ∥ 2 d t \mathbb{E}\left[F(x_T)-F(x^\star)\right]+\frac{(1-\theta^2)/2-V_\theta\eta}{LT^2}\int_0^T t^2\mathbb{E}\lVert\nabla F(x_t)\rVert^2\,dt E [ F ( x T ) − F ( x ⋆ ) ] + L T 2 ( 1 − θ 2 ) /2 − V θ η ∫ 0 T t 2 E ∥ ∇ F ( x t ) ∥ 2 d t ≤ 2 L R 0 2 γ 2 θ 2 T 2 + V θ L T 2 ∫ 0 T t 2 E ς ˉ t 2 d t . (20) \le\frac{2LR_0^2}{\gamma^2\theta^2T^2}+\frac{V_\theta}{LT^2}\int_0^T t^2\mathbb{E}\bar{\varsigma}_t^2\,dt. \tag*{(20)} ≤ γ 2 θ 2 T 2 2 L R 0 2 + L T 2 V θ ∫ 0 T t 2 E ς ˉ t 2 d t . (20) (b) Bias with projection. Let θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) and V θ η < ( 1 − θ 2 ) / 2 V_\theta\eta<(1-\theta^2)/2 V θ η < ( 1 − θ 2 ) /2 , project every z z z -jump onto a closed convex Q ∋ x 0 , x ⋆ Q\ni x_0,x^\star Q ∋ x 0 , x ⋆ with R Q : = sup z ∈ Q ∥ z − x ⋆ ∥ < ∞ R_Q:=\sup_{z\in Q}\lVert z-x^\star\rVert<\infty R Q := sup z ∈ Q ∥ z − x ⋆ ∥ < ∞ , and assume E ∫ 0 T t ∥ e t ∥ d t < ∞ \mathbb{E}\int_0^T t\lVert e_t\rVert\,dt<\infty E ∫ 0 T t ∥ e t ∥ d t < ∞ and E ∫ 0 T t 2 ∥ e t ∥ 2 d t < ∞ \mathbb{E}\int_0^T t^2\lVert e_t\rVert^2\,dt<\infty E ∫ 0 T t 2 ∥ e t ∥ 2 d t < ∞ . Put C θ , η = V θ + θ 4 / [ 2 ( 1 − θ 2 − 2 V θ η ) ] C_{\theta,\eta}=V_\theta+\theta^4/[2(1-\theta^2-2V_\theta\eta)] C θ , η = V θ + θ 4 / [ 2 ( 1 − θ 2 − 2 V θ η )] , so that C θ , 0 = V θ + θ 4 / [ 2 ( 1 − θ 2 ) ] C_{\theta,0}=V_\theta+\theta^4/[2(1-\theta^2)] C θ , 0 = V θ + θ 4 / [ 2 ( 1 − θ 2 )] . Then
E [ F ( x T ) − F ( x ⋆ ) ] ≤ 2 L R 0 2 γ 2 θ 2 T 2 + 2 R Q γ 2 T 2 ∫ 0 T t E ∥ e t ∥ d t \mathbb{E}[F(x_T)-F(x^\star)]\le\frac{2LR_0^2}{\gamma^2\theta^2T^2}+\frac{2R_Q}{\gamma^2T^2}\int_0^T t\mathbb{E}\lVert e_t\rVert\,dt E [ F ( x T ) − F ( x ⋆ )] ≤ γ 2 θ 2 T 2 2 L R 0 2 + γ 2 T 2 2 R Q ∫ 0 T t E ∥ e t ∥ d t + C θ , η L T 2 ∫ 0 T t 2 E ∥ e t ∥ 2 d t + V θ L T 2 ∫ 0 T t 2 E ς ˉ t 2 d t . (21) +\frac{C_{\theta,\eta}}{LT^2}\int_0^T t^2\mathbb{E}\lVert e_t\rVert^2\,dt+\frac{V_\theta}{LT^2}\int_0^T t^2\mathbb{E}\bar{\varsigma}_t^2\,dt. \tag*{(21)} + L T 2 C θ , η ∫ 0 T t 2 E ∥ e t ∥ 2 d t + L T 2 V θ ∫ 0 T t 2 E ς ˉ t 2 d t . (21)
Proof of part (a). Step 1: drift. Insert (18) into (15) . The quasar bracket is nonpositive, and the term A t V θ η ∥ ∇ F ( x t − ) ∥ 2 / L A_tV_\theta\eta\lVert\nabla F(x_{t-})\rVert^2/L A t V θ η ∥ ∇ F ( x t − ) ∥ 2 / L is absorbed by the dissipative reserve, which leaves the coefficient κ η : = ( 1 − θ 2 ) / 2 − V θ η ≥ 0 \kappa_\eta:=(1-\theta^2)/2-V_\theta\eta\ge0 κ η := ( 1 − θ 2 ) /2 − V θ η ≥ 0 . For the two linear bias terms, 1 2 ∥ z t − − x ⋆ ∥ 2 ≤ Φ t − \frac{1}{2}\lVert z_{t-}-x^\star\rVert^2\le\Phi_{t-} 2 1 ∥ z t − − x ⋆ ∥ 2 ≤ Φ t − gives − c t ⟨ z t − − x ⋆ , e t ⟩ ≤ c t 2 Φ t − ∥ e t ∥ -c_t\langle z_{t-}-x^\star,e_t\rangle\le c_t\sqrt{2\Phi_{t-}}\lVert e_t\rVert − c t ⟨ z t − − x ⋆ , e t ⟩ ≤ c t 2 Φ t − ∥ e t ∥ . Because x ⋆ x^\star x ⋆ is a global minimizer, ∥ ∇ F ( x ) ∥ 2 ≤ 2 L [ F ( x ) − F ( x ⋆ ) ] \lVert\nabla F(x)\rVert^2\le2L[F(x)-F(x^\star)] ∥ ∇ F ( x ) ∥ 2 ≤ 2 L [ F ( x ) − F ( x ⋆ )] , hence ∥ ∇ F ( x t − ) ∥ 2 ≤ 2 L Φ t − / A t \lVert\nabla F(x_{t-})\rVert^2\le2L\Phi_{t-}/A_t ∥ ∇ F ( x t − ) ∥ 2 ≤ 2 L Φ t − / A t ; with c t = θ A t / L c_t=\theta\sqrt{A_t/L} c t = θ A t / L this gives ⟨ ∇ F ( x t − ) , e t ⟩ ≤ θ c t 2 Φ t − ∥ e t ∥ \langle\nabla F(x_{t-}),e_t\rangle\le\theta c_t\sqrt{2\Phi_{t-}}\lVert e_t\rVert ⟨ ∇ F ( x t − ) , e t ⟩ ≤ θ c t 2 Φ t − ∥ e t ∥ . Therefore
D t Φ t ≤ − κ η A t L ∥ ∇ F ( x t − ) ∥ 2 + ( 1 + θ ) 2 c t Φ t − ∥ e t ∥ + A t V θ L ( ς ˉ t 2 + ∥ e t ∥ 2 ) . \mathcal{D}_t\Phi_t\le-\frac{\kappa_\eta A_t}{L}\lVert\nabla F(x_{t-})\rVert^2+(1+\theta)\sqrt{2}c_t\sqrt{\Phi_{t-}}\lVert e_t\rVert+\frac{A_tV_\theta}{L}\left(\bar{\varsigma}_t^2+\lVert e_t\rVert^2\right). D t Φ t ≤ − L κ η A t ∥ ∇ F ( x t − ) ∥ 2 + ( 1 + θ ) 2 c t Φ t − ∥ e t ∥ + L A t V θ ( ς ˉ t 2 + ∥ e t ∥ 2 ) .
Neither a projection nor the reserve is spent on the bias.
Step 2: localization. Let τ R = inf { t ≥ 0 : ∥ x t ∥ + ∥ z t ∥ + Φ t ≥ R } ∧ T \tau_R=\inf\{t\ge0:\lVert x_t\rVert+\lVert z_t\rVert+\Phi_t\ge R\}\wedge T τ R = inf { t ≥ 0 : ∥ x t ∥ + ∥ z t ∥ + Φ t ≥ R } ∧ T , and put u R ( t ) = E Φ t ∧ τ R u_R(t)=\mathbb{E}\Phi_{t\wedge\tau_R} u R ( t ) = E Φ t ∧ τ R and w R ( t ) = u R ( t ) + κ η L E ∫ 0 t ∧ τ R A s ∥ ∇ F ( x s − ) ∥ 2 d s w_R(t)=u_R(t)+\frac{\kappa_\eta}{L}\mathbb{E}\int_0^{t\wedge\tau_R}A_s\lVert\nabla F(x_{s-})\rVert^2\,ds w R ( t ) = u R ( t ) + L κ η E ∫ 0 t ∧ τ R A s ∥ ∇ F ( x s − ) ∥ 2 d s ; both are bounded by the finite-horizon conditions. For fixed s s s , Φ s − = Φ s \Phi_{s-}=\Phi_s Φ s − = Φ s almost surely and 1 { s ≤ τ R } Φ s ≤ Φ s ∧ τ R \mathbf{1}_{\{s\le\tau_R\}}\Phi_s\le\Phi_{s\wedge\tau_R} 1 { s ≤ τ R } Φ s ≤ Φ s ∧ τ R . The stopped compensator identity (36) and Cauchy–Schwarz therefore give
w R ( t ) ≤ Φ 0 + ∫ 0 t [ ( 1 + θ ) 2 c s e ˉ s u R ( s ) + A s V θ L ( E ς ˉ s 2 + e ˉ s 2 ) ] d s . w_R(t)\le\Phi_0+\int_0^t\left[(1+\theta)\sqrt{2}c_s\bar e_s\sqrt{u_R(s)}+\frac{A_sV_\theta}{L}\left(\mathbb{E}\bar{\varsigma}_s^2+\bar e_s^2\right)\right]\,ds. w R ( t ) ≤ Φ 0 + ∫ 0 t [ ( 1 + θ ) 2 c s e ˉ s u R ( s ) + L A s V θ ( E ς ˉ s 2 + e ˉ s 2 ) ] d s .
Since u R ≤ w R u_R\le w_R u R ≤ w R , the same inequality holds with w R \sqrt{w_R} w R in place of u R \sqrt{u_R} u R . Step 3: Gronwall and the limit R → ∞ R \to\infty R → ∞ . Lemma 4.2(ii) with a = Φ 0 = R 0 2 / 2 a=\Phi_0=R_0^2/2 a = Φ 0 = R 0 2 /2 (if R 0 = 0 R_0=0 R 0 = 0 , let a ↓ 0 a \downarrow0 a ↓ 0 ) gives
w R ( T ) ≤ Φ 0 + V θ L ∫ 0 T A s ( E ξ ˉ s 2 + e ˉ s 2 ) d s + 1 + θ 2 ∫ 0 T c s e ˉ s d s . \sqrt{w_R(T)} \le\sqrt{\Phi_0+\frac{V_\theta}{L}\int_0^T A_s\left(\mathbb{E}\bar{\xi}_s^2+\bar{e}_s^2\right)\,\mathrm{d}s}+\frac{1+\theta}{\sqrt{2}}\int_0^T c_s\bar{e}_s\,\mathrm{d}s. w R ( T ) ≤ Φ 0 + L V θ ∫ 0 T A s ( E ξ ˉ s 2 + e ˉ s 2 ) d s + 2 1 + θ ∫ 0 T c s e ˉ s d s .
Finite-horizon nonexplosion gives τ R = T \tau_R=T τ R = T for all large R R R almost surely. Fatou’s lemma for Φ T ∧ τ R ≥ 0 \Phi_{T\wedge\tau_R}\ge0 Φ T ∧ τ R ≥ 0 and monotone convergence for the gradient integral let R → ∞ R\to\infty R → ∞ on the left.
Step 4: normalization. The jump times are Lebesgue-null, so x t − x_{t-} x t − may be replaced by x t x_t x t inside time integrals. Divide by A T A_T A T and use Φ T ≥ A T [ F ( x T ) − F ( x ⋆ ) ] \Phi_T\ge A_T[F(x_T)-F(x^\star)] Φ T ≥ A T [ F ( x T ) − F ( x ⋆ )] , A t / A T = t 2 / T 2 A_t/A_T=t^2/T^2 A t / A T = t 2 / T 2 , Φ 0 / A T = 2 L R 0 2 / ( γ 2 θ 2 T 2 ) \Phi_0/A_T=2LR_0^2/(\gamma^2\theta^2T^2) Φ 0 / A T = 2 L R 0 2 / ( γ 2 θ 2 T 2 ) , and A T − 1 / 2 c t = θ t / ( L T ) A_T^{-1/2}c_t=\theta t/(\sqrt{L}T) A T − 1/2 c t = θ t / ( L T ) . This gives (19) ; for e ˉ = 0 \bar e=0 e ˉ = 0 , B T = 0 B_T=0 B T = 0 and (19) is (20) .
The proof of part (b) spends the reserve on the bias and is given in Appendix § 10 . A primitive sufficient condition for the finite-horizon requirements is a linear conditional second-moment bound on the oracle: Lemma A.2 shows that it implies all of them, and every oracle below satisfies it whenever the local gradient second moments grow at most linearly.
Remark 4.4 (Which part is used where). Part (a) with e t = 0 e_t=0 e t = 0 covers CQA-Net (Theorem 4.8 ) and the fixed-graph token (Corollary 4.13); there η = 0 \eta=0 η = 0 or η \eta η is the multiplicative noise created by the walk. Part (a) with a bias covers the changing-graph token without projection (Corollary 4.14) and D-CQA (Theorem 4.19 ). Part (b) gives the alternative projected bound for the changing-graph token. The two parts complement each other. For a constant bias e ˉ \bar e e ˉ and vanishing variance, expanding the square in (19) gives the cross term ( 1 + θ ) R 0 e ˉ / γ (1+\theta)R_0\bar e/\gamma ( 1 + θ ) R 0 e ˉ / γ , which has the form of the term R Q e ˉ / γ R_Q\bar e/\gamma R Q e ˉ / γ of (21) with R 0 ≤ R Q R_0\le R_Q R 0 ≤ R Q ; the quadratic bias term grows like T 2 e ˉ 2 / L T^2\bar e^2/L T 2 e ˉ 2 / L in part (a) and like T e ˉ 2 / L T\bar e^2/L T e ˉ 2 / L in part (b). Part (a) needs neither Q Q Q nor θ < 1 \theta<1 θ < 1 and keeps the gradient integral on the left. A persistent nonzero bias leaves an accuracy floor in both parts.
The exact-gradient specialization calibrates the constants and the γ \gamma γ -dependence against the known continuized quasar dynamics.
Corollary 4.5 (Exact-gradient acceleration). Under Theorem 4.3 , if g t = ∇ F ( x t − ) g_t=\nabla F(x_{t-}) g t = ∇ F ( x t − ) , then
E [ F ( x T ) − F ( x ⋆ ) ] ≤ 2 L ∥ x 0 − x ⋆ ∥ 2 γ 2 θ 2 T 2 . (22) \mathbb{E}[F(x_T)-F(x^\star)]\le\frac{2L\lVert x_0-x^\star\rVert^2}{\gamma^2\theta^2T^2}. \tag*{(22)} E [ F ( x T ) − F ( x ⋆ )] ≤ γ 2 θ 2 T 2 2 L ∥ x 0 − x ⋆ ∥ 2 . (22)
Estimate (22) shows that T = O ( L ∥ x 0 − x ⋆ ∥ / ( γ θ ε ) ) T=O(\sqrt{L}\lVert x_0-x^\star\rVert/(\gamma\theta\sqrt{\varepsilon})) T = O ( L ∥ x 0 − x ⋆ ∥ / ( γ θ ε )) is sufficient for expected error ε \varepsilon ε , and E N T = T \mathbb{E}N_T=T E N T = T .
At θ = 1 \theta=1 θ = 1 , Corollary 4.5 is the deterministic continuized result of Wang and Wibisono (2023). The network results need the predictable, state-dependent variance term, the bias terms, and the explicit reserve, which can absorb centered noise proportional to the squared gradient norm.
The selected-row oracle and CQA-Net
Every network oracle in this paper returns one row of a mixed matrix of local rows, possibly reweighted: CQA-Net selects a uniform row, and the walking token selects the endpoint of a random walk. One lemma gives the conditional moments in all cases, even when individual row means are not local gradients.
Setting. Condition on F τ k − \mathcal{F}_{\tau_k-} F τ k − . Let U ^ ( k ) , U ( k ) ∈ R m × d \widehat{U}^{(k)},U^{(k)}\in\mathbb{R}^{m\times d} U ( k ) , U ( k ) ∈ R m × d have rows U ^ i ( k ) \widehat{U}^{(k)}_i U i ( k ) and U i ( k ) = E [ U ^ i ( k ) ∣ F τ k − ] U_i^{(k)}=\mathbb{E}[\widehat{U}^{(k)}_i\mid\mathcal{F}_{\tau_k-}] U i ( k ) = E [ U i ( k ) ∣ F τ k − ] , put u ˉ ( k ) = m − 1 ( U ( k ) ) ⊤ 1 \bar{u}^{(k)}=m^{-1}(U^{(k)})^\top\mathbf{1} u ˉ ( k ) = m − 1 ( U ( k ) ) ⊤ 1 and D ( k ) = U ( k ) − 1 ( u ˉ ( k ) ) ⊤ D^{(k)}=U^{(k)}-\mathbf{1}(\bar{u}^{(k)})^\top D ( k ) = U ( k ) − 1 ( u ˉ ( k ) ) ⊤ , and define the block covariances
Σ i j ( k ) : = E [ ( U ^ i ( k ) − U i ( k ) ) ( U ^ j ( k ) − U j ( k ) ) ⊤ ∣ F τ k − ] . \Sigma_{ij}^{(k)}:=\mathbb{E}\left[\left(\widehat{U}_i^{(k)}-U_i^{(k)}\right)\left(\widehat{U}_j^{(k)}-U_j^{(k)}\right)^\top\mid\mathcal{F}_{\tau_k-}\right]. Σ ij ( k ) := E [ ( U i ( k ) − U i ( k ) ) ( U j ( k ) − U j ( k ) ) ⊤ ∣ F τ k − ] .
Let W ∈ R m × m W\in\mathbb{R}^{m\times m} W ∈ R m × m be fixed under this conditioning and mean preserving, W 1 = 1 W\mathbf{1}=\mathbf{1} W 1 = 1 and 1 ⊤ W = 1 ⊤ \mathbf{1}^\top W=\mathbf{1}^\top 1 ⊤ W = 1 ⊤ , and for every node v v v let S ( v ) S(v) S ( v ) be a fixed set with W v i = 0 W_{vi}=0 W v i = 0 for i ∉ S ( v ) i\notin S(v) i ∈ / S ( v ) (the choice S ( v ) = { 1 , … , m } S(v)=\{1,\ldots,m\} S ( v ) = { 1 , … , m } is always admissible). Put
N ( k ) : = 1 m ∑ i , j = 1 m ( W ⊤ W ) i j Tr Σ i j ( k ) , B ( k ) : = 1 m ∥ ( W − J ) D ( k ) ∥ F 2 + N ( k ) . \mathcal{N}^{(k)}:=\frac{1}{m}\sum_{i,j=1}^{m}(W^\top W)_{ij}\operatorname{Tr}\Sigma_{ij}^{(k)},\qquad\mathcal{B}^{(k)}:=\frac{1}{m}\lVert(W-J)D^{(k)}\rVert_F^2+\mathcal{N}^{(k)}. N ( k ) := m 1 i , j = 1 ∑ m ( W ⊤ W ) ij Tr Σ ij ( k ) , B ( k ) := m 1 ∥( W − J ) D ( k ) ∥ F 2 + N ( k ) .
The root R k R_k R k has a conditional law π \pi π and is independent of the latent row innovations, and ω \omega ω is a positive weight fixed under the conditioning. The selected rows are produced in one of two chronologies: rows first , where the latent rows are fixed before R k R_k R k is revealed, or root first , where after R k = v R_k=v R k = v the rows indexed by S ( v ) S(v) S ( v ) are sampled jointly from the restriction of the latent law, with randomness independent of R k R_k R k . The estimator is
g ^ ( k ) = ω ( R k ) e R k ⊤ W U ^ ( k ) , Ω : = max v m π ( v ) ω ( v ) 2 . (23) \widehat{g}^{(k)}=\omega(R_k)e_{R_k}^{\top}W\widehat{U}^{(k)},\qquad\Omega:=\max_v m\pi(v)\omega(v)^2. \tag*{(23)} g ( k ) = ω ( R k ) e R k ⊤ W U ( k ) , Ω := v max mπ ( v ) ω ( v ) 2 . (23)
Lemma 4.6 (Selected-row oracle). In the setting above the following statements hold.
(i) Law. Given R k = v R_k=v R k = v , the selected row e v ⊤ W U ^ ( k ) e_v^{\top}W\widehat{U}^{(k)} e v ⊤ W U ( k ) has the same conditional law in both chronologies; root first evaluates only the ∣ S ( v ) ∣ |S(v)| ∣ S ( v ) ∣ rows of S ( v ) S(v) S ( v ) .
(ii) Importance weight, π ω ≡ 1 / m \pi\omega\equiv1/m π ω ≡ 1/ m . Then E [ g ^ ( k ) ∣ F τ k − ] = u ˉ ( k ) \mathbb{E}[\widehat{g}^{(k)}\mid\mathcal{F}_{\tau_k-}]=\bar{u}^{(k)} E [ g ( k ) ∣ F τ k − ] = u ˉ ( k ) and
E [ ∥ g ^ ( k ) − u ˉ ( k ) ∥ 2 ∣ F τ k − ] ≤ Ω B ( k ) + ( Ω − 1 ) ∥ u ˉ ( k ) ∥ 2 , (24) \mathbb{E}\left[\left\|\widehat{g}^{(k)}-\bar{u}^{(k)}\right\|^2\mid\mathcal{F}_{\tau_k-}\right]\leq\Omega B^{(k)}+(\Omega-1)\left\|\bar{u}^{(k)}\right\|^2, \tag*{(24)} E [ g ( k ) − u ˉ ( k ) 2 ∣ F τ k − ] ≤ Ω B ( k ) + ( Ω − 1 ) u ˉ ( k ) 2 , (24) with equality for a uniform root and ω ≡ 1 \omega\equiv1 ω ≡ 1 , where Ω = 1 \Omega=1 Ω = 1 .
(iii) No weight, ω ≡ 1 \omega\equiv1 ω ≡ 1 . Then E [ g ^ ( k ) ∣ F τ k − ] = u ˉ ( k ) + e k \mathbb{E}[\widehat{g}^{(k)}\mid\mathcal{F}_{\tau_k-}]=\bar{u}^{(k)}+e_k E [ g ( k ) ∣ F τ k − ] = u ˉ ( k ) + e k with e k ⊤ = ( π − 1 / m ) ⊤ ( W − J ) D ( k ) e_k^{\top}=(\pi-1/m)^{\top}(W-J)D^{(k)} e k ⊤ = ( π − 1/ m ) ⊤ ( W − J ) D ( k ) , so ∥ e k ∥ ≤ ∥ π − 1 / m ∥ 2 ∥ W − J ∥ 2 ∥ D ( k ) ∥ F \|e_k\|\leq\|\pi-1/m\|_2\|W-J\|_2\|D^{(k)}\|_F ∥ e k ∥ ≤ ∥ π − 1/ m ∥ 2 ∥ W − J ∥ 2 ∥ D ( k ) ∥ F , and the conditional centered variance is at most Ω B ( k ) \Omega B^{(k)} Ω B ( k ) .
Moreover m − 1 ∥ ( W − J ) D ( k ) ∥ F 2 ≤ ∥ W − J ∥ 2 2 m − 1 ∥ D ( k ) ∥ F 2 m^{-1}\|(W-J)D^{(k)}\|_F^2\leq\|W-J\|_2^2m^{-1}\|D^{(k)}\|_F^2 m − 1 ∥ ( W − J ) D ( k ) ∥ F 2 ≤ ∥ W − J ∥ 2 2 m − 1 ∥ D ( k ) ∥ F 2 , and for W = I m W=I_m W = I m with S ( v ) = { v } S(v)=\{v\} S ( v ) = { v } (lazy depth zero) only the diagonal blocks Σ i i ( k ) \Sigma_{ii}^{(k)} Σ ii ( k ) enter N ( k ) \mathcal{N}^{(k)} N ( k ) , so the bounds do not depend on how unevaluated latent rows are coupled.
Proof. Step 1: law. Since W v i = 0 W_{vi}=0 W v i = 0 for i ∉ S ( v ) i\notin S(v) i ∈ / S ( v ) , the selected row e v ⊤ W U ^ ( k ) = ∑ i ∈ S ( v ) W v i U ^ i ( k ) e_v^{\top}W\widehat{U}^{(k)}=\sum_{i\in S(v)}W_{vi}\widehat{U}_i^{(k)} e v ⊤ W U ( k ) = ∑ i ∈ S ( v ) W v i U i ( k ) is a fixed linear function of the rows indexed by S ( v ) S(v) S ( v ) . In both chronologies these rows have, given R k = v R_k=v R k = v , the restricted latent law, because the root is independent of the latent innovations and the root-first randomness is independent of the root. This proves (i); all expectations below may therefore be computed under the latent construction.
Step 2: the average over all rows. Write E ( k ) = U ^ ( k ) − U ( k ) E^{(k)}=\widehat{U}^{(k)}-U^{(k)} E ( k ) = U ( k ) − U ( k ) . Since 1 ⊤ D ( k ) = 0 \mathbf{1}^{\top}D^{(k)}=0 1 ⊤ D ( k ) = 0 and W J = J W = J WJ=JW=J W J = J W = J ,
W U ^ ( k ) = 1 ( u ˉ ( k ) ) ⊤ + ( W − J ) D ( k ) + W E ( k ) . W\widehat{U}^{(k)}=\mathbf{1}\left(\bar{u}^{(k)}\right)^{\top}+(W-J)D^{(k)}+WE^{(k)}. W U ( k ) = 1 ( u ˉ ( k ) ) ⊤ + ( W − J ) D ( k ) + W E ( k ) .
The three terms are orthogonal in expectation: the first two are Frobenius-orthogonal because 1 ⊤ ( W − J ) = 0 \mathbf{1}^{\top}(W-J)=0 1 ⊤ ( W − J ) = 0 , and E ( k ) E^{(k)} E ( k ) is conditionally centered. Hence
1 m ∑ v E [ ∥ e v ⊤ W U ^ ( k ) − u ˉ ( k ) ∥ 2 ] = B ( k ) , 1 m ∑ v E [ ∥ e v ⊤ W U ^ ( k ) ∥ 2 ] = ∥ u ˉ ( k ) ∥ 2 + B ( k ) , (25) \frac{1}{m}\sum_v\mathbb{E}\left[\left\|e_v^{\top}W\widehat{U}^{(k)}-\bar{u}^{(k)}\right\|^2\right]=B^{(k)},\qquad
\frac{1}{m}\sum_v\mathbb{E}\left[\left\|e_v^{\top}W\widehat{U}^{(k)}\right\|^2\right]=\left\|\bar{u}^{(k)}\right\|^2+B^{(k)}, \tag*{(25)} m 1 v ∑ E [ e v ⊤ W U ( k ) − u ˉ ( k ) 2 ] = B ( k ) , m 1 v ∑ E [ e v ⊤ W U ( k ) 2 ] = u ˉ ( k ) 2 + B ( k ) , (25)
where m − 1 E ∥ W E ( k ) ∥ F 2 = N ( k ) m^{-1}\mathbb{E}\|WE^{(k)}\|_F^2=\mathcal{N}^{(k)} m − 1 E ∥ W E ( k ) ∥ F 2 = N ( k ) by expanding the square.
Step 3: means. By Step 1, E [ g ^ ( k ) ∣ F τ k − ] ⊤ = ∑ v π ( v ) ω ( v ) e v ⊤ W U ( k ) \mathbb{E}[\widehat{g}^{(k)}\mid\mathcal{F}_{\tau_k-}]^{\top}=\sum_v\pi(v)\omega(v)e_v^{\top}WU^{(k)} E [ g ( k ) ∣ F τ k − ] ⊤ = ∑ v π ( v ) ω ( v ) e v ⊤ W U ( k ) . If π ω ≡ 1 / m \pi\omega\equiv1/m π ω ≡ 1/ m , this is m − 1 1 ⊤ W U ( k ) = ( u ˉ ( k ) ) ⊤ m^{-1}\mathbf{1}^{\top}WU^{(k)}=\left(\bar{u}^{(k)}\right)^{\top} m − 1 1 ⊤ W U ( k ) = ( u ˉ ( k ) ) ⊤ . If ω ≡ 1 \omega\equiv1 ω ≡ 1 , write W U ( k ) = 1 ( u ˉ ( k ) ) ⊤ + ( W − J ) D ( k ) WU^{(k)}=\mathbf{1}\left(\bar{u}^{(k)}\right)^{\top}+(W-J)D^{(k)} W U ( k ) = 1 ( u ˉ ( k ) ) ⊤ + ( W − J ) D ( k ) and use ( π − 1 / m ) ⊤ 1 = 0 (\pi-1/m)^{\top}\mathbf{1}=0 ( π − 1/ m ) ⊤ 1 = 0 ; this gives the formula for e k e_k e k , and the norm bound follows from ∥ D ( k ) ∥ 2 ≤ ∥ D ( k ) ∥ F \|D^{(k)}\|_2\leq\|D^{(k)}\|_F ∥ D ( k ) ∥ 2 ≤ ∥ D ( k ) ∥ F .
Step 4: variances. If π ω ≡ 1 / m \pi\omega\equiv1/m π ω ≡ 1/ m , then π ω 2 = ω / m \pi\omega^2=\omega/m π ω 2 = ω / m and Ω = max v ω ( v ) \Omega=\max_v\omega(v) Ω = max v ω ( v ) , so by (25)
E ∥ g ^ ( k ) ∥ 2 = 1 m ∑ v ω ( v ) E [ ∥ e v ⊤ W U ^ ( k ) ∥ 2 ] ≤ Ω ( ∥ u ˉ ( k ) ∥ 2 + B ( k ) ) , \mathbb{E}\|\widehat{g}^{(k)}\|^2=\frac{1}{m}\sum_v\omega(v)\mathbb{E}\left[\left\|e_v^{\top}W\widehat{U}^{(k)}\right\|^2\right]\leq\Omega\left(\left\|\bar{u}^{(k)}\right\|^2+B^{(k)}\right), E ∥ g ( k ) ∥ 2 = m 1 v ∑ ω ( v ) E [ e v ⊤ W U ( k ) 2 ] ≤ Ω ( u ˉ ( k ) 2 + B ( k ) ) ,
with equality when ω ≡ 1 \omega\equiv1 ω ≡ 1 . Subtracting the squared mean ∥ u ˉ ( k ) ∥ 2 \|\bar{u}^{(k)}\|^2 ∥ u ˉ ( k ) ∥ 2 gives (24) . If ω ≡ 1 \omega\equiv1 ω ≡ 1 , the centered variance is at most the second moment about u ˉ ( k ) \bar{u}^{(k)} u ˉ ( k ) , which is ∑ v π ( v ) E [ ∥ e v ⊤ W U ^ ( k ) − u ˉ ( k ) ∥ 2 ] ≤ Ω B ( k ) \sum_v\pi(v)\mathbb{E}\left[\left\|e_v^{\top}W\widehat{U}^{(k)}-\bar{u}^{(k)}\right\|^2\right]\leq\Omega B^{(k)} ∑ v π ( v ) E [ e v ⊤ W U ( k ) − u ˉ ( k ) 2 ] ≤ Ω B ( k ) by (25) . The final claims follow from ∥ ( W − J ) D ∥ F ≤ ∥ W − J ∥ 2 ∥ D ∥ F \|(W-J)D\|_F\leq\|W-J\|_2\|D\|_F ∥ ( W − J ) D ∥ F ≤ ∥ W − J ∥ 2 ∥ D ∥ F and from ( W ⊤ W ) i j = δ i j (W^{\top}W)_{ij}=\delta_{ij} ( W ⊤ W ) ij = δ ij when W = I m W=I_m W = I m .
We keep the noise term in block form because pairwise nonpositive cross-covariances do not automatically reduce it for a signed polynomial filter: the entries of W ⊤ W W^{\top}W W ⊤ W need not be nonnegative. The simpler scalar term is used only under the direct domination
1 m ∑ i , j = 1 m ( W ⊤ W ) i j Tr Σ i j ( k ) ≤ ∥ W ∥ F 2 m σ 2 b . (26) \frac{1}{m}\sum_{i,j=1}^{m}(W^{\top}W)_{ij}\operatorname{Tr}\Sigma_{ij}^{(k)}
\leq\frac{\|W\|_F^2}{m}\frac{\sigma^2}{b}. \tag*{(26)} m 1 i , j = 1 ∑ m ( W ⊤ W ) ij Tr Σ ij ( k ) ≤ m ∥ W ∥ F 2 b σ 2 . (26)
Conditional cross-node uncorrelatedness is sufficient. More generally, Σ ( k ) ⪯ ( σ 2 / ( b d ) ) I m d \Sigma^{(k)}\preceq(\sigma^2/(bd))I_{md} Σ ( k ) ⪯ ( σ 2 / ( b d )) I m d is a checkable correlated-noise example that implies (26) . For ordinary rows U i ( k ) = ∇ f i ( y ( k ) ) U_i^{(k)}=\nabla f_i(y^{(k)}) U i ( k ) = ∇ f i ( y ( k ) ) , so u ˉ ( k ) = ∇ F ( y ( k ) ) \bar{u}^{(k)}=\nabla F(y^{(k)}) u ˉ ( k ) = ∇ F ( y ( k ) ) and m − 1 ∥ D ( k ) ∥ F 2 = ζ 2 ( y ( k ) ) m^{-1}\|D^{(k)}\|_F^2=\zeta^2(y^{(k)}) m − 1 ∥ D ( k ) ∥ F 2 = ζ 2 ( y ( k ) ) ; then
B ( k ) ≤ ∥ W − J ∥ 2 2 ζ 2 ( y ( k ) ) + ∥ W ∥ F 2 m σ 2 b . (27) B^{(k)}\leq\|W-J\|_2^2\zeta^2(y^{(k)})+\frac{\|W\|_F^2}{m}\frac{\sigma^2}{b}. \tag*{(27)} B ( k ) ≤ ∥ W − J ∥ 2 2 ζ 2 ( y ( k ) ) + m ∥ W ∥ F 2 b σ 2 . (27)
The network enters only through ∥ W − J ∥ 2 \|W-J\|_2 ∥ W − J ∥ 2 and m − 1 ∥ W ∥ F 2 m^{-1}\|W\|_F^2 m − 1 ∥ W ∥ F 2 . On a fixed graph the Chebyshev recurrence of § 3.2 controls both.
Lemma 4.7 (Chebyshev disagreement bound). Let a fixed connected undirected graph have Laplacian eigenvalues 0 = λ 1 < λ 2 ≤ ⋯ ≤ λ m 0 = \lambda_{1} < \lambda_{2} \le\cdots\le\lambda_{m} 0 = λ 1 < λ 2 ≤ ⋯ ≤ λ m and χ = λ m / λ 2 > 1 \chi= \lambda_{m}/\lambda_{2} > 1 χ = λ m / λ 2 > 1 . The degree-q q q normalized Chebyshev protocol has a mean-preserving input-output operator W q W_{q} W q satisfying
∥ W q − J ∥ 2 ≤ 2 ( χ − 1 χ + 1 ) q ≤ 2 exp ( − 2 q χ + 1 ) , 1 m ∥ W q ∥ F 2 ≤ 1 m + ∥ W q − J ∥ 2 2 . (28) \lVert W_{q} - J \rVert_{2} \le2\left(\frac{\sqrt{\chi}-1}{\sqrt{\chi}+1}\right)^{q} \le2\exp\left(-\frac{2q}{\sqrt{\chi}+1}\right), \qquad\frac{1}{m}\lVert W_{q}\rVert_{\mathrm{F}}^{2} \le\frac{1}{m} + \lVert W_{q}-J\rVert_{2}^{2}. \tag*{(28)} ∥ W q − J ∥ 2 ≤ 2 ( χ + 1 χ − 1 ) q ≤ 2 exp ( − χ + 1 2 q ) , m 1 ∥ W q ∥ F 2 ≤ m 1 + ∥ W q − J ∥ 2 2 . (28) Certified spectral endpoints may replace the exact eigenvalues. If χ = 1 \chi= 1 χ = 1 , one round gives W 1 = J W_{1}=J W 1 = J .
The proof is in Appendix § 9 . The O ( χ log ( 1 / δ ) ) O(\sqrt{\chi}\log(1/\delta)) O ( χ log ( 1/ δ )) depth concerns only pre-mixing; every CQA-Net event also pays the broadcast depth D D D . On changing graphs an instantaneous spectral gap cannot be inserted into a noncommuting product, so we condition on the actual input-output operator and require bounds on that operator itself; Corollary 4.11 below gives one explicit class.
Theorem 4.8 (Network oracle inequality for CQA-Net). Suppose that F F F is L L L -smooth and γ \gamma γ -quasar-convex, the local rows satisfy (6) , and CQA-Net uses the root–row chronology of § 2.5 , including the lazy kernel (7) when q = 0 q=0 q = 0 , over a horizon T > 0 T>0 T > 0 with θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] . At jump k ≥ 1 k\ge1 k ≥ 1 an event-indexed scheduler chooses a mean-preserving W k , q W_{k,q} W k , q from the revealed past before E k − 1 E_{k-1} E k − 1 is exposed, and the centered row noise satisfies (26) for the selected W k , q W_{k,q} W k , q . Let w ˉ q ≥ ∥ W k , q − J ∥ 2 \bar{w}_{q}\ge\lVert W_{k,q}-J\rVert_{2} w ˉ q ≥ ∥ W k , q − J ∥ 2 and ν ˉ q ≥ m − 1 ∥ W k , q ∥ F 2 \bar{\nu}_{q}\ge m^{-1}\lVert W_{k,q}\rVert_{\mathrm{F}}^{2} ν ˉ q ≥ m − 1 ∥ W k , q ∥ F 2 be deterministic uniform bounds (or essential suprema over all revealed histories), and assume the finite-horizon conditions of Theorem 4.3. Then
E [ F ( x T ) − F ( x ∗ ) ] + 1 − θ 2 2 L T 2 ∫ 0 T t 2 E ∥ ∇ F ( x t ) ∥ 2 d t \mathbb{E}[F(x_{T})-F(x^{*})]+\frac{1-\theta^{2}}{2LT^{2}}\int_{0}^{T}t^{2}\mathbb{E}\lVert\nabla F(x_{t})\rVert^{2}\,\mathrm{d}t E [ F ( x T ) − F ( x ∗ )] + 2 L T 2 1 − θ 2 ∫ 0 T t 2 E ∥ ∇ F ( x t ) ∥ 2 d t ≤ 2 L R 0 2 γ 2 θ 2 T 2 + ν ˉ θ w ˉ q 2 L T 2 ∫ 0 T t 2 E ζ 2 ( x t ) d t + ν ˉ θ ν ˉ q σ 2 T 3 L b . (29) \le\frac{2LR_{0}^{2}}{\gamma^{2}\theta^{2}T^{2}}+\frac{\bar{\nu}_{\theta}\bar{w}_{q}^{2}}{LT^{2}}\int_{0}^{T}t^{2}\mathbb{E}\zeta^{2}(x_{t})\,\mathrm{d}t+\frac{\bar{\nu}_{\theta}\bar{\nu}_{q}\sigma^{2}T}{3Lb}. \tag*{(29)} ≤ γ 2 θ 2 T 2 2 L R 0 2 + L T 2 ν ˉ θ w ˉ q 2 ∫ 0 T t 2 E ζ 2 ( x t ) d t + 3 L b ν ˉ θ ν ˉ q σ 2 T . (29) On a fixed graph with W k , q = W q W_{k,q}=W_{q} W k , q = W q one may take w ˉ q = ∥ W q − J ∥ 2 \bar{w}_{q}=\lVert W_{q}-J\rVert_{2} w ˉ q = ∥ W q − J ∥ 2 and ν ˉ q = m − 1 ∥ W q ∥ F 2 \bar{\nu}_{q}=m^{-1}\lVert W_{q}\rVert_{\mathrm{F}}^{2} ν ˉ q = m − 1 ∥ W q ∥ F 2 . The expected event count is T T T . For q > 0 q>0 q > 0 , the direct implementation uses b T bT b T expected samples per node and m b T mbT mb T in aggregate; for q = 0 q=0 q = 0 , root-first sampling uses b T / m bT/m b T / m per node and b T bT b T in aggregate. On a fixed graph, expected critical-path rounds and transmitted vectors are at most T ( q + D ) T(q+D) T ( q + D ) and T ( 2 q ∣ E ∣ + M b r ) T(2q\lvert E\rvert+M_{\mathrm{br}}) T ( 2 q ∣ E ∣ + M br ) . On a changing graph where the selected row can be disseminated within B b r B_{\mathrm{br}} B br subrounds and M b r t v M_{\mathrm{br}}^{\mathrm{tv}} M br tv transmitted vectors and mixing uses at most M m i x t v ( q ) M_{\mathrm{mix}}^{\mathrm{tv}}(q) M mix tv ( q ) vectors, they are at most T ( q + B b r ) T(q+B_{\mathrm{br}}) T ( q + B br ) and T [ M m i x t v ( q ) + M b r t v ] T[M_{\mathrm{mix}}^{\mathrm{tv}}(q)+M_{\mathrm{br}}^{\mathrm{tv}}] T [ M mix tv ( q ) + M br tv ] .
Proof. Fix jump k ≥ 1 k\ge1 k ≥ 1 . The operator W k , q W_{k,q} W k , q is measurable with respect to the history through jump k − 1 k-1 k − 1 , and after the interarrival has produced the predictable query, W k , q W_{k,q} W k , q and the query are fixed under F τ k − \mathcal{F}_{\tau_{k}^{-}} F τ k − while the rows and the root remain fresh. Lemma 4.6(ii) with a uniform root, ω ≡ 1 \omega\equiv1 ω ≡ 1 and S ( v ) = { 1 , … , m } S(v)=\{1,\ldots,m\} S ( v ) = { 1 , … , m } (or W ‾ = I m \overline{W}=I_{m} W = I m , S ( v ) = { v } S(v)=\{v\} S ( v ) = { v } at q = 0 q=0 q = 0 ) gives conditional mean ∇ F ( x τ k − ) \nabla F(x_{\tau_{k}^{-}}) ∇ F ( x τ k − ) , and (27) gives the centered variance
ζ t 2 ≤ w ˉ q 2 ζ 2 ( x t ) + ν ˉ q σ 2 b . \zeta_{t}^{2}\le\bar{w}_{q}^{2}\zeta^{2}(x_{t})+\bar{\nu}_{q}\frac{\sigma^{2}}{b}. ζ t 2 ≤ w ˉ q 2 ζ 2 ( x t ) + ν ˉ q b σ 2 .
Insert this envelope into (20) with η = 0 \eta=0 η = 0 . The heterogeneity remains inside the weighted integral because it depends on the trajectory; the mini-batch term is constant and integrates using T − 2 ∫ 0 T t 2 d t = T / 3 T^{-2}\int_{0}^{T}t^{2}\,\mathrm{d}t=T/3 T − 2 ∫ 0 T t 2 d t = T /3 . This step uses the common-state property: Theorem 4.3 is applied to x t ∈ R d x_{t}\in\mathbb{R}^{d} x t ∈ R d , not to a matrix. Finally, E N T = T \mathbb{E}N_{T}=T E N T = T , and the two branches of Algorithm 2 together with the certified per-event mixing and dissemination costs give the ledgers.
Theorem 4.8 reduces the network problem to externally certified products and does not prove a new consensus result. It is also an oracle inequality: the integral of ζ 2 ( x t ) \zeta^{2}(x_{t}) ζ 2 ( x t ) depends on the trajectory. There are three useful closures. On changing graphs each of them holds with ∥ W q − J ∥ 2 \lVert W_{q}-J\rVert_{2} ∥ W q − J ∥ 2 and m − 1 ∥ W q ∥ F 2 m^{-1}\lVert W_{q}\rVert_{\mathrm{F}}^{2} m − 1 ∥ W q ∥ F 2 replaced by w ˉ q \bar{w}_{q} w ˉ q and ν ˉ q \bar{\nu}_{q} ν ˉ q .
Corollary 4.9 (Closed network rates). Under Theorem 4.8, the following statements hold.
(a) Gronwall closure. If ζ 2 ( x ) ≤ h 0 + h 1 [ F ( x ) − F ( x ∗ ) ] \zeta^{2}(x)\le h_{0}+h_{1}[F(x)-F(x^{*})] ζ 2 ( x ) ≤ h 0 + h 1 [ F ( x ) − F ( x ∗ )] globally, then
E [ F ( x T ) − F ( x ∗ ) ] ≤ e ν ˉ θ ∥ W q − J ∥ 2 2 h 1 T / L [ 2 L R 0 2 γ 2 θ 2 T 2 + ν ˉ θ T 3 L ( ∥ W q − J ∥ 2 2 h 0 + ∥ W q ∥ F 2 m σ 2 b ) ] . (30) \mathbb{E}[F(x_{T})-F(x^{*})]\le e^{\bar{\nu}_{\theta}\lVert W_{q}-J\rVert_{2}^{2}h_{1}T/L}\left[\frac{2LR_{0}^{2}}{\gamma^{2}\theta^{2}T^{2}}+\frac{\bar{\nu}_{\theta}T}{3L}\left(\lVert W_{q}-J\rVert_{2}^{2}h_{0}+\frac{\lVert W_{q}\rVert_{\mathrm{F}}^{2}}{m}\frac{\sigma^{2}}{b}\right)\right]. \tag*{(30)} E [ F ( x T ) − F ( x ∗ )] ≤ e ν ˉ θ ∥ W q − J ∥ 2 2 h 1 T / L [ γ 2 θ 2 T 2 2 L R 0 2 + 3 L ν ˉ θ T ( ∥ W q − J ∥ 2 2 h 0 + m ∥ W q ∥ F 2 b σ 2 ) ] . (30) It is at most ϵ \epsilon ϵ if T ≥ 2 L R 0 / ( γ θ ϵ ) T\ge2\sqrt{L}R_{0}/(\gamma\theta\sqrt{\epsilon}) T ≥ 2 L R 0 / ( γ θ ϵ ) , the exponent is at most log ( 4 / 3 ) \log(4/3) log ( 4/3 ) , and the round bracket is at most 3 L ϵ / ( 4 ν ˉ θ T ) 3L\epsilon/(4\bar{\nu}_{\theta}T) 3 L ϵ / ( 4 ν ˉ θ T ) .
(b) Global envelope. If ζ 2 ( x ) ≤ ζ ˉ 2 \zeta^{2}(x)\le\bar{\zeta}^{2} ζ 2 ( x ) ≤ ζ ˉ 2 globally, then (30) holds with h 0 = ζ ˉ 2 h_{0}=\bar{\zeta}^{2} h 0 = ζ ˉ 2 , h 1 = 0 h_{1}=0 h 1 = 0 and no exponential factor. It is at most ϵ \epsilon ϵ if T ≥ 2 L R 0 / ( γ θ ϵ ) T\ge2\sqrt{L}R_{0}/(\gamma\theta\sqrt{\epsilon}) T ≥ 2 L R 0 / ( γ θ ϵ ) and each of the two variance terms in the round bracket is at most 3 L ϵ / ( 4 ν ˉ θ T ) 3L\epsilon/(4\bar{\nu}_{\theta}T) 3 L ϵ / ( 4 ν ˉ θ T ) ; for the Chebyshev protocol of Lemma 4.7 the disagreement condition is implied by q ≥ χ + 1 4 [ log ( 16 ν ˉ θ ζ ˉ 2 T 3 L ϵ ) ] + q\ge\frac{\sqrt{\chi}+1}{4}\left[\log\left(\frac{16\bar{\nu}_{\theta}\bar{\zeta}^{2}T}{3L\epsilon}\right)\right]_{+} q ≥ 4 χ + 1 [ log ( 3 L ϵ 16 ν ˉ θ ζ ˉ 2 T ) ] + , where [ a ] + : = max { a , 0 } [a]_{+}:=\max\{a,0\} [ a ] + := max { a , 0 } .
(c) Dissipative closure. Suppose quadratic growth holds , ζ 2 ( x ) ≤ h 0 + h 1 [ F ( x ) − F ( x ⋆ ) ] \zeta^2(x) \le h_0 + h_1[F(x) - F(x^\star)] ζ 2 ( x ) ≤ h 0 + h 1 [ F ( x ) − F ( x ⋆ )] , θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , and
2 V θ h 1 ∥ W q − J ∥ 2 2 γ 2 μ ≤ 1 − θ 2 2 . (31) \frac{2V_\theta h_1\lVert W_q-J\rVert_2^2}{\gamma^2\mu} \le\frac{1-\theta^2}{2}. \tag*{(31)} γ 2 μ 2 V θ h 1 ∥ W q − J ∥ 2 2 ≤ 2 1 − θ 2 . (31)
Then (30) holds without the exponential factor.
Proof. (a) Insert the affine bound into the variance envelope of Theorem 4.8 . Since A t [ F ( x t − ) − F ( x ⋆ ) ] ≤ Φ t − A_t[F(x_{t-}) - F(x^\star)] \le\Phi_{t-} A t [ F ( x t − ) − F ( x ⋆ )] ≤ Φ t − , the gap-dependent term contributes at most ( V θ ∥ W q − J ∥ 2 2 h 1 / L ) Φ t − (V_\theta\lVert W_q-J\rVert_2^2h_1/L)\Phi_{t-} ( V θ ∥ W q − J ∥ 2 2 h 1 / L ) Φ t − to the stopped drift; apply Lemma 4.2(i), remove the stopping as in Theorem 4.3 , and use A T − 1 ∫ 0 T A t d t = T / 3 A_T^{-1}\int_0^T A_t\,\mathrm{d}t = T/3 A T − 1 ∫ 0 T A t d t = T /3 . The stated conditions bound the bracket by 3 ε / 4 3\varepsilon/4 3 ε /4 , and the exponential factor is at most 4 / 3 4/3 4/3 . (b) Substitute ζ 2 ≤ ζ ˉ 2 \zeta^2 \le\bar{\zeta}^2 ζ 2 ≤ ζ ˉ 2 directly into (29) . (c) Quasar-convexity, quadratic growth, and Cauchy–Schwarz give ∥ ∇ F ( x ) ∥ 2 ≥ γ 2 μ [ F ( x ) − F ( x ⋆ ) ] / 2 \lVert\nabla F(x)\rVert^2 \ge\gamma^2\mu[F(x)-F(x^\star)]/2 ∥ ∇ F ( x ) ∥ 2 ≥ γ 2 μ [ F ( x ) − F ( x ⋆ )] /2 , so the gap-dependent variance is at most η ∥ ∇ F ( x t − ) ∥ 2 \eta\lVert\nabla F(x_{t-})\rVert^2 η ∥ ∇ F ( x t − ) ∥ 2 with η = 2 h 1 ∥ W q − J ∥ 2 2 / ( γ 2 μ ) \eta= 2h_1\lVert W_q-J\rVert_2^2/(\gamma^2\mu) η = 2 h 1 ∥ W q − J ∥ 2 2 / ( γ 2 μ ) , and (31) is V θ η ≤ ( 1 − θ 2 ) / 2 V_\theta\eta\le(1-\theta^2)/2 V θ η ≤ ( 1 − θ 2 ) /2 ; apply Theorem 4.3 with this η \eta η and drop the gradient integral.
Part (a) is general but may be vacuous on long horizons; part (c) is horizon-free but requires quadratic growth, damping, and enough mixing. Their common premise holds with h 0 = 2 ζ 2 ( x ⋆ ) h_0 = 2\zeta^2(x^\star) h 0 = 2 ζ 2 ( x ⋆ ) and h 1 = 4 δ ˉ 2 / μ h_1 = 4\bar{\delta}^2/\mu h 1 = 4 δ ˉ 2 / μ under quadratic growth if ∥ [ ∇ f i ( x ) − ∇ F ( x ) ] − [ ∇ f i ( y ) − ∇ F ( y ) ] ∥ ≤ δ i ∥ x − y ∥ \lVert[\nabla f_i(x)-\nabla F(x)]-[\nabla f_i(y)-\nabla F(y)]\rVert\le\delta_i\lVert x-y\rVert ∥[ ∇ f i ( x ) − ∇ F ( x )] − [ ∇ f i ( y ) − ∇ F ( y )]∥ ≤ δ i ∥ x − y ∥ and δ ˉ 2 = m − 1 ∑ i δ i 2 \bar{\delta}^2=m^{-1}\sum_i\delta_i^2 δ ˉ 2 = m − 1 ∑ i δ i 2 (Appendix § 9 ). Mixing as accurately as possible is not generally optimal: if T q T_q T q is the smallest horizon satisfying a closed bound at depth q q q , the communication choice is q c o m m ∈ arg min q ≥ 0 ( q + D ) T q q_{\mathrm{comm}} \in\arg\min_{q\ge0}(q+D)T_q q comm ∈ arg min q ≥ 0 ( q + D ) T q , so positive finite depth trades computation against communication and does not always help.
Complexity to a target accuracy
Set
T ε = Θ ( L R 0 γ θ ε ) . T_\varepsilon=\Theta\left(\frac{\sqrt{LR_0}}{\gamma\theta\sqrt{\varepsilon}}\right). T ε = Θ ( γ θ ε L R 0 ) .
Let q ε , b ε q_\varepsilon,b_\varepsilon q ε , b ε satisfy a chosen closure above. A CQA-Net event costs q ε + D q_\varepsilon+D q ε + D critical-path rounds and 2 q ε ∣ E ∣ + M b r 2q_\varepsilon|E|+M_{\mathrm{br}} 2 q ε ∣ E ∣ + M br transmitted vectors, and uses m b ε mb_\varepsilon m b ε row samples for q ε > 0 q_\varepsilon>0 q ε > 0 and b ε b_\varepsilon b ε for q = 0 q=0 q = 0 , so the total round count is ( q ε + D ) T ε (q_\varepsilon+D)T_\varepsilon ( q ε + D ) T ε .
At γ = 1 \gamma=1 γ = 1 the optimal convex local-state scale is O ~ ( χ L R 0 / ε ) \widetilde{O}(\sqrt{\chi}\sqrt{LR_0/\varepsilon}) O ( χ L R 0 / ε ) rounds ((Scaman et al., 2017)). Up to logarithmic and numerical factors, the ratio of the common-state round bound to this scale is roughly ( D + χ log ( 1 / ε ) ) / χ (D+\sqrt{\chi}\log(1/\varepsilon))/\sqrt{\chi} ( D + χ log ( 1/ ε )) / χ . On a bounded-degree expander family, χ = Θ ( 1 ) \sqrt{\chi}=\Theta(1) χ = Θ ( 1 ) whereas a common broadcast still has D = Θ ( log m ) D=\Theta(\log m) D = Θ ( log m ) . In the stochastic regime, q ε q_\varepsilon q ε generally grows logarithmically with 1 / ε 1/\varepsilon 1/ ε , while the sufficient batch size scales as ε − 3 / 2 \varepsilon^{-3/2} ε − 3/2 because T ε = Θ ( ε − 1 / 2 ) T_\varepsilon=\Theta(\varepsilon^{-1/2}) T ε = Θ ( ε − 1/2 ) and the stochastic term must be at most ε \varepsilon ε . The resulting aggregate stochastic sample scale remains Θ ( ε − 2 ) \Theta(\varepsilon^{-2}) Θ ( ε − 2 ) ; acceleration acts on the deterministic term. D-CQA has no dissemination term: its round count q ε T ε q_\varepsilon T_\varepsilon q ε T ε (Corollary 4.20) matches the local-state scale up to a logarithm, at the price of the assumptions of Section 4.4.
Block contraction gives one explicit class of certificates for Theorem 4.8 on changing graphs; an unfinished block must be controlled separately.
Corollary 4.11 (Uniformly block-contractive changing graphs). Suppose each complete block of B b l k B_{\mathrm{blk}} B blk communication rounds implements a mean-preserving Q ℓ Q_\ell Q ℓ with ∥ Q ℓ − J ∥ 2 ≤ η b l k < 1 \lVert Q_\ell-J\rVert_2\le\eta_{\mathrm{blk}}<1 ∥ Q ℓ − J ∥ 2 ≤ η blk < 1 . For each remainder s ∈ { 0 , … , B b l k − 1 } s\in\{0,\ldots,B_{\mathrm{blk}}-1\} s ∈ { 0 , … , B blk − 1 } , suppose every admissible partial product R s R_s R s is mean preserving and ∥ R s − J ∥ 2 ≤ κ s \lVert R_s-J\rVert_2\le\kappa_s ∥ R s − J ∥ 2 ≤ κ s , with κ 0 = 1 \kappa_0=1 κ 0 = 1 . If q = r B b l k + s q=rB_{\mathrm{blk}}+s q = r B blk + s , then
∥ W k , q − J ∥ 2 ≤ κ s η b l k r , 1 m ∥ W k , q ∥ F 2 ≤ 1 m + κ s 2 η b l k 2 r . (32) \lVert W_{k,q}-J\rVert_2\le\kappa_s\eta_{\mathrm{blk}}^r,\qquad
\frac{1}{m}\lVert W_{k,q}\rVert_F^2\le\frac{1}{m}+\kappa_s^2\eta_{\mathrm{blk}}^{2r}. \tag*{(32)} ∥ W k , q − J ∥ 2 ≤ κ s η blk r , m 1 ∥ W k , q ∥ F 2 ≤ m 1 + κ s 2 η blk 2 r . (32)
For q = r B b l k q = rB_{\mathrm{blk}} q = r B blk the remainder factor is absent. Products of symmetric lazy doubly stochastic maps are nonexpansive on the disagreement subspace, so one may take κ s ≤ 1 \kappa_s \le1 κ s ≤ 1 .
Proof. Factorization controls the disagreement operator. The Frobenius estimate then matches the quantity in the row-noise term.
Step 1: product factorization. Mean preservation gives A J = J A = J AJ = JA = J A J = J A = J for every factor. Therefore ( A − J ) ( B − J ) = A B − J (A-J)(B-J)=AB-J ( A − J ) ( B − J ) = A B − J , and induction yields
W k , q − J = ( R s − J ) ( Q r − J ) ⋯ ( Q 1 − J ) . W_{k,q}-J=(R_s-J)(Q_r-J)\cdots(Q_1-J). W k , q − J = ( R s − J ) ( Q r − J ) ⋯ ( Q 1 − J ) .
Submultiplicativity gives the first bound in (32) .
Step 2: row-noise factor. The orthogonal decomposition ∥ W k , q ∥ F 2 = ∥ J ∥ F 2 + ∥ W k , q − J ∥ F 2 \lVert W_{k,q}\rVert_{\mathrm{F}}^2=\lVert J\rVert_{\mathrm{F}}^2+\lVert W_{k,q}-J\rVert_{\mathrm{F}}^2 ∥ W k , q ∥ F 2 = ∥ J ∥ F 2 + ∥ W k , q − J ∥ F 2 , together with ∥ J ∥ F 2 = 1 \lVert J\rVert_{\mathrm{F}}^2=1 ∥ J ∥ F 2 = 1 and m − 1 ∥ A ∥ F 2 ≤ ∥ A ∥ 2 m^{-1}\lVert A\rVert_{\mathrm{F}}^2\leq\lVert A\rVert^2 m − 1 ∥ A ∥ F 2 ≤ ∥ A ∥ 2 , gives the second.
Corollary 4.11 is one explicit way to supply the product norms w ˉ q , ν ˉ q \bar{w}_q,\bar{\nu}_q w ˉ q , ν ˉ q required by Theorem 4.8 . Exact averaging sets W k , q = J W_{k,q}=J W k , q = J and removes row-mean disagreement, but the stochastic-row upper bound still contains σ 2 / ( m b ) \sigma^2/(mb) σ 2 / ( mb ) . The exact-gradient corollary is recovered only when the local rows are deterministic as well.
The walking-token oracle
This subsection analyzes Algorithms 4 and 5. At event k k k put
P k : = P k , 1 P k , 2 ⋯ P k , h w , π k : = P k T e o k , ϱ k : = ∥ P k − J ∥ 2 . P_k:=P_{k,1}P_{k,2}\cdots P_{k,h_w},\qquad\pi_k:=P_k^{\mathsf{T}}e_{o_k},\qquad\varrho_k:=\lVert P_k-J\rVert_2. P k := P k , 1 P k , 2 ⋯ P k , h w , π k := P k T e o k , ϱ k := ∥ P k − J ∥ 2 .
Given F τ k − \mathcal{F}_{\tau_k^-} F τ k − , the vector π k \pi_k π k is the conditional law of the walk endpoint R k R_k R k , which is independent of the latent row innovations. On a fixed graph P k = P h w P_k=P^{h_w} P k = P h w with P = P T P=P^{\mathsf{T}} P = P T ; we put λ P : = max { ∣ λ 2 ( P ) ∣ , ∣ λ m ( P ) ∣ } < 1 \lambda_P:=\max\{|\lambda_2(P)|,|\lambda_m(P)|\}<1 λ P := max { ∣ λ 2 ( P ) ∣ , ∣ λ m ( P ) ∣ } < 1 and ρ h : = m λ P h w \rho_h:=m\lambda_P^{h_w} ρ h := m λ P h w .
The token oracle is the selected-row oracle of Lemma 4.6 with root law π k \pi_k π k , root-first chronology, S ( v ) = B q ( v ) S(v)=B_q(v) S ( v ) = B q ( v ) , and weight ω k = 1 / ( m π k ) \omega_k=1/(m\pi_k) ω k = 1/ ( m π k ) in fixed mode or ω k ≡ 1 \omega_k\equiv1 ω k ≡ 1 in changing mode. Only the walk law is new.
Lemma 4.12 (Walk endpoint law). If every P k , s P_{k,s} P k , s is doubly stochastic, then ∥ π k − 1 / m ∥ 2 ≤ ϱ k \lVert\pi_k-\mathbf{1}/m\rVert_2\leq\varrho_k ∥ π k − 1 / m ∥ 2 ≤ ϱ k and max i m π k ( i ) ≤ 1 + m ϱ k \max_i m\pi_k(i)\leq1+m\varrho_k max i m π k ( i ) ≤ 1 + m ϱ k . On a fixed graph with P = P T P=P^{\mathsf{T}} P = P T , moreover ϱ k = λ P h w \varrho_k=\lambda_P^{h_w} ϱ k = λ P h w , ∣ m π k ( i ) − 1 ∣ ≤ ρ h |m\pi_k(i)-1|\leq\rho_h ∣ m π k ( i ) − 1∣ ≤ ρ h for every i i i , and ω k = 1 / ( m ( P h w ) o k R k ) = 1 / ( m π k ( R k ) ) \omega_k=1/(m(P^{h_w})_{o_kR_k})=1/(m\pi_k(R_k)) ω k = 1/ ( m ( P h w ) o k R k ) = 1/ ( m π k ( R k )) . If ρ h ≤ 1 / 2 \rho_h\leq1/2 ρ h ≤ 1/2 , every node is reached with positive probability and max i ω k ( i ) ≤ ( 1 − ρ h ) − 1 ≤ 1 + 2 ρ h \max_i\omega_k(i)\leq(1-\rho_h)^{-1}\leq1+2\rho_h max i ω k ( i ) ≤ ( 1 − ρ h ) − 1 ≤ 1 + 2 ρ h .
Proof. Since P k T 1 = 1 P_k^{\mathsf{T}}\mathbf{1}=\mathbf{1} P k T 1 = 1 and J ( e o k − 1 / m ) = 0 J(e_{o_k}-\mathbf{1}/m)=0 J ( e o k − 1 / m ) = 0 , π k − 1 / m = ( P k T − J ) ( e o k − 1 / m ) \pi_k-\mathbf{1}/m=(P_k^{\mathsf{T}}-J)(e_{o_k}-\mathbf{1}/m) π k − 1 / m = ( P k T − J ) ( e o k − 1 / m ) , and ∥ e o k − 1 / m ∥ 2 2 = ( m − 1 ) / m ≤ 1 \lVert e_{o_k}-\mathbf{1}/m\rVert_2^2=(m-1)/m\leq1 ∥ e o k − 1 / m ∥ 2 2 = ( m − 1 ) / m ≤ 1 . This gives the first two claims. For symmetric P P P , ∥ P h w − J ∥ 2 = λ P h w \lVert P^{h_w}-J\rVert_2=\lambda_P^{h_w} ∥ P h w − J ∥ 2 = λ P h w , each coordinate deviation is at most the Euclidean norm, and π k ( v ) = ( P h w ) o k v \pi_k(v)=(P^{h_w})_{o_kv} π k ( v ) = ( P h w ) o k v .
Corollary 4.13 (Fixed-graph token rate). Assume the hypotheses of Theorem 4.8 on F F F and on the rows, a fixed graph, θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , a ball-supported W q W_q W q , and
h w ≥ ln ( 4 m V θ / ( 1 − θ 2 ) ) ln ( 1 / λ P ) , so that ρ h ≤ 1 − θ 2 4 V θ ( ≤ 1 2 ) . (33) h_w\geq\frac{\ln(4mV_\theta/(1-\theta^2))}{\ln(1/\lambda_P)},\qquad\text{so that}\qquad\rho_h\leq\frac{1-\theta^2}{4V_\theta}\left(\leq\frac{1}{2}\right). \tag*{(33)} h w ≥ ln ( 1/ λ P ) ln ( 4 m V θ / ( 1 − θ 2 )) , so that ρ h ≤ 4 V θ 1 − θ 2 ( ≤ 2 1 ) . (33) Then the oracle of Algorithm 4 in fixed mode is unbiased, its centered variance is at most ( 1 + 2 ρ h ) [ ∥ W q − J ∥ 2 ζ 2 ( y ( k ) ) + ∥ W q ∥ F 2 σ 2 / ( m b ) ] + 2 ρ h ∥ ∇ F ( y ( k ) ) ∥ 2 (1+2\rho_h)[\lVert W_q-J\rVert^2\zeta^2(y^{(k)})+\lVert W_q\rVert_{\mathrm{F}}^2\sigma^2/(mb)]+2\rho_h\lVert\nabla F(y^{(k)})\rVert^2 ( 1 + 2 ρ h ) [∥ W q − J ∥ 2 ζ 2 ( y ( k ) ) + ∥ W q ∥ F 2 σ 2 / ( mb )] + 2 ρ h ∥ ∇ F ( y ( k ) ) ∥ 2 , and Algorithm 5 satisfies
E [ F ( x T ) − F ( x ⋆ ) ] + ( 1 − θ 2 ) / 2 − 2 V θ ρ h L T 2 ∫ 0 T t 2 E [ ∥ ∇ F ( x t ) ∥ 2 ] d t \mathbb{E}[F(x_T)-F(x^\star)]+\frac{(1-\theta^2)/2-2V_\theta\rho_h}{LT^2}\int_0^T t^2\mathbb{E}[\lVert\nabla F(x_t)\rVert^2]\,dt E [ F ( x T ) − F ( x ⋆ )] + L T 2 ( 1 − θ 2 ) /2 − 2 V θ ρ h ∫ 0 T t 2 E [∥ ∇ F ( x t ) ∥ 2 ] d t ≤ 2 L R 0 2 γ 2 θ 2 T 0 2 + ( 1 + 2 ρ h ) V θ ∥ W q − J ∥ 2 L T 2 ∫ 0 T t 2 E [ ζ 2 ( x t ) ] d t + ( 1 + 2 ρ h ) V θ ∥ W q ∥ F 2 σ 2 T 3 L m b . \leq\frac{2LR_0^2}{\gamma^2\theta^2T_0^2}+(1+2\rho_h)\frac{V_\theta\lVert W_q-J\rVert^2}{LT^2}\int_0^T t^2\mathbb{E}[\zeta^2(x_t)]\,dt+(1+2\rho_h)\frac{V_\theta\lVert W_q\rVert_{\mathrm{F}}^2\sigma^2T}{3Lm b}. ≤ γ 2 θ 2 T 0 2 2 L R 0 2 + ( 1 + 2 ρ h ) L T 2 V θ ∥ W q − J ∥ 2 ∫ 0 T t 2 E [ ζ 2 ( x t )] d t + ( 1 + 2 ρ h ) 3 L mb V θ ∥ W q ∥ F 2 σ 2 T . Corollary 4.9(a) and (b) hold with their variance terms multiplied by 1 + 2 ρ h 1+2\rho_h 1 + 2 ρ h . Corollary 4.9(c) holds if condition (31) is replaced by
2 V θ ( 1 + 2 ρ h ) h 1 ∥ W q − J ∥ 2 γ 2 μ ≤ 1 − θ 2 2 − 2 V θ ρ h . \frac{2V_\theta(1+2\rho_h)h_1\lVert W_q-J\rVert^2}{\gamma^2\mu}\leq\frac{1-\theta^2}{2}-2V_\theta\rho_h. γ 2 μ 2 V θ ( 1 + 2 ρ h ) h 1 ∥ W q − J ∥ 2 ≤ 2 1 − θ 2 − 2 V θ ρ h .
Proof. By Lemma 4.12 , π k ω k ≡ 1 / m \pi_k\omega_k \equiv1/m π k ω k ≡ 1/ m and Ω = max ω k ≤ 1 + 2 ρ h \Omega= \max\omega_k \le1 + 2\rho_h Ω = max ω k ≤ 1 + 2 ρ h . Lemma 4.6 (ii) and (27) give unbiasedness and the displayed variance, which has the form (18) with η = 2 ρ h \eta= 2\rho_h η = 2 ρ h and ς ˉ t = ( 1 + 2 ρ h ) [ ∥ W q − J ∥ 2 2 ( x t − ) + ∥ W q ∥ F 2 σ 2 / ( m b ) ] \bar{\varsigma}_t = (1 + 2\rho_h)[\lVert W_q - J\rVert_2^2(\mathit{x}_{t-}) + \lVert W_q\rVert_F^2\sigma^2/(mb)] ς ˉ t = ( 1 + 2 ρ h ) [∥ W q − J ∥ 2 2 ( x t − ) + ∥ W q ∥ F 2 σ 2 / ( mb )] . The condition V θ η ≤ ( 1 − θ 2 ) / 2 V\theta\eta\le(1-\theta^2)/2 V θ η ≤ ( 1 − θ 2 ) /2 is exactly ρ h ≤ ( 1 − θ 2 ) / ( 4 V θ ) \rho_h \le(1-\theta^2)/(4V\theta) ρ h ≤ ( 1 − θ 2 ) / ( 4 V θ ) . Since ω k ≤ 1 + 2 ρ h \omega_k \le1 + 2\rho_h ω k ≤ 1 + 2 ρ h , the linear second-moment bound (37) is inherited from the rows, and Lemma A.2 supplies the finite-horizon conditions. Theorem 4.3 , in the form (20) , gives the rate. For the closures, the affine heterogeneity bound enters with the factor 1 + 2 ρ h 1 + 2\rho_h 1 + 2 ρ h ; in part (c) the multiplicative coefficient becomes η = 2 ρ h + 2 ( 1 + 2 ρ h ) h 1 ∥ W q − J ∥ 2 2 / ( γ 2 μ ) \eta= 2\rho_h + 2(1 + 2\rho_h)h_1\lVert W_q-J\rVert_2^2/(\gamma^2\mu) η = 2 ρ h + 2 ( 1 + 2 ρ h ) h 1 ∥ W q − J ∥ 2 2 / ( γ 2 μ ) , and V θ η ≤ ( 1 − θ 2 ) / 2 V\theta\eta\le(1-\theta^2)/2 V θ η ≤ ( 1 − θ 2 ) /2 is the displayed condition.
On a changing graph the endpoint law π k \pi_k π k cannot be computed locally, so no weight is used and the walk introduces a predictable bias.
Corollary 4.14 (Changing-graph token rate). Let F F F be L L L -smooth and γ \gamma γ -quasar-convex, let ζ ( x ) ≤ ζ ˉ \zeta(x) \le\bar{\zeta} ζ ( x ) ≤ ζ ˉ globally, let the rows satisfy (6) and (26) , and assume the uniform certificates ϱ k ≤ ϱ ˉ \varrho_k \le\bar{\varrho} ϱ k ≤ ϱ ˉ , ∥ W k , q − J ∥ 2 ≤ w ˉ q \lVert W_{k,q}-J\rVert_2 \le\bar{w}_q ∥ W k , q − J ∥ 2 ≤ w ˉ q and m − 1 ∥ W k , q ∥ F 2 ≤ ν ˉ q m^{-1}\lVert W_{k,q}\rVert_F^2 \le\bar{\nu}_q m − 1 ∥ W k , q ∥ F 2 ≤ ν ˉ q (for q = 0 q=0 q = 0 , w ˉ 0 = ν ˉ 0 = 1 \bar{w}_0=\bar{\nu}_0=1 w ˉ 0 = ν ˉ 0 = 1 ). Put e ˉ : = m ϱ ˉ w ˉ q ζ ˉ \bar{e}:=\sqrt{m}\,\bar{\varrho}\bar{w}_q\bar{\zeta} e ˉ := m ϱ ˉ w ˉ q ζ ˉ and σ ˉ w 2 : = ( 1 + m ϱ ˉ ) [ w ˉ q 2 ζ 2 + ν ˉ q σ 2 / b ] \bar{\sigma}_w^2 := (1+m\bar{\varrho})[\bar{w}_q^2\zeta^2+\bar{\nu}_q\sigma^2/b] σ ˉ w 2 := ( 1 + m ϱ ˉ ) [ w ˉ q 2 ζ 2 + ν ˉ q σ 2 / b ] . Then the oracle of Algorithm 4 in changing mode has a predictable bias ∥ e k ∥ ≤ e ˉ \lVert e_k\rVert\le\bar{e} ∥ e k ∥ ≤ e ˉ and centered variance at most σ ˉ w 2 \bar{\sigma}_w^2 σ ˉ w 2 , and the following hold under the corresponding finite-horizon conditions of Theorem 4.3 .
(a) Without projection and for θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] ,
E [ F ( x T ) − F ( x ∗ ) ] ≤ ( 2 L R 0 2 γ 2 θ 2 T 2 + V θ T 3 L ( σ ˉ w 2 + e ˉ 2 ) + ( 1 + θ ) θ T e ˉ 2 2 L ) 2 . \mathbb{E}[F(x_T)-F(x^*)] \le\left(\sqrt{\frac{2LR_0^2}{\gamma^2\theta^2T^2}+\frac{V\theta T}{3L}(\bar{\sigma}_w^2+\bar{e}^2)}+\frac{(1+\theta)\theta T\bar{e}}{2\sqrt{2L}}\right)^2. E [ F ( x T ) − F ( x ∗ )] ≤ γ 2 θ 2 T 2 2 L R 0 2 + 3 L V θ T ( σ ˉ w 2 + e ˉ 2 ) + 2 2 L ( 1 + θ ) θ T e ˉ 2 . (b) If every z z z -jump is projected onto Q Q Q and θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) ,
E [ F ( x T ) − F ( x ∗ ) ] ≤ 2 L R 0 2 γ 2 θ 2 T 2 + R Q γ e ˉ + C θ , 0 T 3 L e ˉ 2 + V θ T 3 L σ ˉ w 2 . \mathbb{E}[F(x_T)-F(x^*)] \le\frac{2LR_0^2}{\gamma^2\theta^2T^2}+\frac{R_Q}{\gamma}\bar{e}+\frac{C_{\theta,0}T}{3L}\bar{e}^2+\frac{V\theta T}{3L}\bar{\sigma}_w^2. E [ F ( x T ) − F ( x ∗ )] ≤ γ 2 θ 2 T 2 2 L R 0 2 + γ R Q e ˉ + 3 L C θ , 0 T e ˉ 2 + 3 L V θ T σ ˉ w 2 . If every block of B b l k B_{\mathrm{blk}} B blk hops contracts as in Corollary 4.11, then ϱ ˉ ≤ κ s η b l k r \bar{\varrho}\le\kappa_s\eta_{\mathrm{blk}}^r ϱ ˉ ≤ κ s η blk r for h w = r B b l k + s h_w=rB_{\mathrm{blk}}+s h w = r B blk + s ; in both bounds the bias terms are then below any prescribed ε / 4 \varepsilon/4 ε /4 once h w h_w h w is logarithmic in 1 / ε 1/\varepsilon 1/ ε , and the variance term behaves as in Corollary 4.9 (b) with the extra factor 1 + m ϱ ˉ ≤ 2 1+m\bar{\varrho}\le2 1 + m ϱ ˉ ≤ 2 once m ϱ ˉ ≤ 1 m\bar{\varrho}\le1 m ϱ ˉ ≤ 1 .
Proof. Lemma 4.6 (iii) with ω ≡ 1 \omega\equiv1 ω ≡ 1 , Ω = max i m π k ( i ) \Omega=\max_i m\pi_k(i) Ω = max i m π k ( i ) and (27) , together with Lemma 4.12 , gives the bias ∥ e k ∥ ≤ ϱ k w ˉ q m ζ ( y ( k ) ) ≤ e ˉ \lVert e_k\rVert\le\varrho_k\bar{w}_q\sqrt{m}\,\zeta(y^{(k)})\le\bar{e} ∥ e k ∥ ≤ ϱ k w ˉ q m ζ ( y ( k ) ) ≤ e ˉ and the variance bound σ ˉ w 2 \bar{\sigma}_w^2 σ ˉ w 2 . The bias is predictable because it depends only on o k o_k o k , the walk matrices, W k , q W_{k,q} W k , q , and the query. Part (a) is Theorem 4.3 (a) with η = 0 \eta=0 η = 0 , constant e ˉ t = e ˉ \bar{e}_t=\bar{e} e ˉ t = e ˉ and ς ˉ t = σ ˉ w \bar{\varsigma}_t=\bar{\sigma}_w ς ˉ t = σ ˉ w , after dropping the gradient integral; part (b) is Theorem 4.3 (b) with η = 0 \eta=0 η = 0 , using ∫ 0 T t d t = T 2 / 2 \int_0^T t\,dt=T^2/2 ∫ 0 T t d t = T 2 /2 and ∫ 0 T t 2 d t = T 3 / 3 \int_0^T t^2dt=T^3/3 ∫ 0 T t 2 d t = T 3 /3 . The block bound is Corollary 4.11 applied to the walk matrices, which are mean preserving, and the logarithmic choice of h w h_w h w follows because all bias terms are increasing in ϱ ˉ \bar{\varrho} ϱ ˉ and vanish as ϱ ˉ → 0 \bar{\varrho}\to0 ϱ ˉ → 0 .
Remark 4.15 (Length of the walk). On the fixed ring with m = 16 m=16 m = 16 and Metropolis weights, λ P = 0.94925 \lambda_P=0.94925 λ P = 0.94925 , and for θ 2 = 1 / 2 \theta^2=1/2 θ 2 = 1/2 condition (33) gives h w = 88 h_w=88 h w = 88 hops per event against D = 8 D=8 D = 8 for dissemination. On bounded-degree graphs h w h_w h w scales like χ log m \chi\log m χ log m , whereas D = O ( χ log m ) D=O(\sqrt{\chi}\log m) D = O ( χ log m ) ([6 ] ); nonreversible lifted walks can shorten the walk, for instance from O ( m 2 ) O(m^2) O ( m 2 ) to O ( m ) O(m) O ( m ) on the cycle ([5 ] ), with Lemma 4.12 replaced by the mixing bound of the lifted chain. Parallel work beyond B q ( R k ) B_q(R_k) B q ( R k ) , several tokens, loss of the token, and a token version of finite-sum variance reduction are not covered here.
Local states: analysis of D-CQA D-CQA needs two assumptions that the common-state analysis does not use.
Assumption 4.16 (Local-state model). F F F is L L L -smooth and γ \gamma γ -quasar-convex with respect to x ∗ x^* x ∗ , and R 0 = ∥ x ( 0 ) − x ∗ ∥ R_0=\lVert x^{(0)}-x^*\rVert R 0 = ∥ x ( 0 ) − x ∗ ∥ . In addition:
every f i f_i f i is L l o c L_{\mathrm{loc}} L loc -smooth; without loss of generality L l o c ≥ L L_{\mathrm{loc}}\ge L L loc ≥ L , and we set κ l o c : = L l o c / L ≥ 1 \kappa_{\mathrm{loc}}:=L_{\mathrm{loc}}/L\ge1 κ loc := L loc / L ≥ 1 ;
ζ ( y ) ≤ ζ ˉ \zeta(y)\le\bar{\zeta} ζ ( y ) ≤ ζ ˉ for every y ∈ R d y\in\mathbb{R}^d y ∈ R d , with ζ ˉ \bar{\zeta} ζ ˉ as in (8) ;
at event k k k , conditionally on F τ k − \mathcal{F}_{\tau_k-} F τ k − , node i i i returns g i ( k ) g_i^{(k)} g i ( k ) with mean ∇ f i ( y i ( k ) ) \nabla f_i(y_i^{(k)}) ∇ f i ( y i ( k ) ) and E [ ∥ g i ( k ) − ∇ f i ( y i ( k ) ) ∥ 2 ∣ F τ k − ] ≤ σ 2 / b \mathbb{E}[\lVert g_i^{(k)}-\nabla f_i(y_i^{(k)})\rVert^2\mid\mathcal{F}_{\tau_k-}]\le\sigma^2/b E [∥ g i ( k ) − ∇ f i ( y i ( k ) ) ∥ 2 ∣ F τ k − ] ≤ σ 2 / b ; noises of different nodes are conditionally uncorrelated, and the innovations at event k k k are conditionally independent of the interarrival times ( E j ) j ≥ k (E_j)_{j\ge k} ( E j ) j ≥ k ;
(iv) every W k W_k W k is mean preserving, is chosen from the revealed history before the interarrival that produces τ k \tau_k τ k , and satisfies ∥ W k − J ∥ 2 ≤ δ m i x \lVert W_k-J\rVert_2\le\delta_{\mathrm{mix}} ∥ W k − J ∥ 2 ≤ δ mix .
Items (i) and (ii) are new. Item (ii) holds, for example, for shared-landscape models f i = F + ⟨ c i , x ⟩ f_i=F+\langle c_i,x\rangle f i = F + ⟨ c i , x ⟩ with ∑ i c i = 0 \sum_i c_i=0 ∑ i c i = 0 , where ζ ≡ ( m − 1 ∑ i ∥ c i ∥ 2 ) 1 / 2 \zeta\equiv\left(m^{-1}\sum_i\lVert c_i\rVert^2\right)^{1/2} ζ ≡ ( m − 1 ∑ i ∥ c i ∥ 2 ) 1/2 ; there the f i f_i f i have different minimizers and fail the quasar condition at x ⋆ x^\star x ⋆ . Item (ii) excludes the partitioned-data regression of § 5 , where ζ \zeta ζ grows with ∥ y − x ⋆ ∥ \lVert y-x^\star\rVert ∥ y − x ⋆ ∥ . Put A t A_t A t , c t c_t c t , V θ V_\theta V θ as in (12) and
Φ t = A t [ F ( x ˉ t ) − F ( x ⋆ ) ] + 1 2 ∥ z ˉ t − x ⋆ ∥ 2 . \Phi_t=A_t\left[F(\bar{x}_t)-F(x^\star)\right]+\frac{1}{2}\lVert\bar{z}_t-x^\star\rVert^2. Φ t = A t [ F ( x ˉ t ) − F ( x ⋆ ) ] + 2 1 ∥ z ˉ t − x ⋆ ∥ 2 .
Lemma 4.17 (The network average is a biased CQA process). Under Assumption 4.16, the averages ( x ˉ t , z ˉ t ) (\bar{x}_t,\bar{z}_t) ( x ˉ t , z ˉ t ) follow the flow (11) between events. At event k k k they satisfy
x ˉ ( k ) = y ˉ ( k ) − g ˉ ( k ) / L , z ˉ ( k ) = z ˉ ( k − 1 ) − c τ k g ˉ ( k ) , g ˉ ( k ) = 1 m ∑ i g i ( k ) , \bar{x}^{(k)}=\bar{y}^{(k)}-\bar{g}^{(k)}/L,\qquad
\bar{z}^{(k)}=\bar{z}^{(k-1)}-c_{\tau_k}\bar{g}^{(k)},\qquad
\bar{g}^{(k)}=\frac{1}{m}\sum_i g_i^{(k)}, x ˉ ( k ) = y ˉ ( k ) − g ˉ ( k ) / L , z ˉ ( k ) = z ˉ ( k − 1 ) − c τ k g ˉ ( k ) , g ˉ ( k ) = m 1 i ∑ g i ( k ) , with y ˉ ( k ) = x ˉ τ k − \bar{y}^{(k)}=\bar{x}_{\tau_k-} y ˉ ( k ) = x ˉ τ k − . Hence they form the process (10) driven by the oracle g ˉ \bar{g} g ˉ , whose conditional moments are
E [ g ˉ ( k ) ∣ F τ k − ] = ∇ F ( y ˉ ( k ) ) + e k , e k = 1 m ∑ i ( ∇ f i ( y i ( k ) ) − ∇ f i ( y ˉ ( k ) ) ) , \mathbb{E}[\bar{g}^{(k)}\mid\mathcal{F}_{\tau_k-}]
=\nabla F(\bar{y}^{(k)})+e_k,\qquad
e_k=\frac{1}{m}\sum_i\left(\nabla f_i(y_i^{(k)})-\nabla f_i(\bar{y}^{(k)})\right), E [ g ˉ ( k ) ∣ F τ k − ] = ∇ F ( y ˉ ( k ) ) + e k , e k = m 1 i ∑ ( ∇ f i ( y i ( k ) ) − ∇ f i ( y ˉ ( k ) ) ) , *with predictable e k e_k e k , ∥ e k ∥ ≤ L l o c ∥ Y ⊥ ( k ) ∥ F / m \lVert e_k\rVert\le L_{\mathrm{loc}}\lVert Y_\perp^{(k)}\rVert_F/\sqrt{m} ∥ e k ∥ ≤ L loc ∥ Y ⊥ ( k ) ∥ F / m , and centered variance at most σ 2 / ( m b ) \sigma^2/(mb) σ 2 / ( mb ) .
Proof. Since 1 ⊤ W k = 1 ⊤ \mathbf{1}^{\top}W_k=\mathbf{1}^{\top} 1 ⊤ W k = 1 ⊤ , the averages of W k X ~ W_k\widetilde{X} W k X and W k Z ~ W_k\widetilde{Z} W k Z are those of X ~ \widetilde{X} X and Z ~ \widetilde{Z} Z . The flow is linear and identical at all nodes, so it commutes with averaging. For the bias, local smoothness and Cauchy–Schwarz give ∥ e k ∥ ≤ L l o c m ∑ i ∥ y i − y ˉ ∥ ≤ L l o c ∥ Y ⊥ ∥ F / m \lVert e_k\rVert\le\frac{L_{\mathrm{loc}}}{m}\sum_i\lVert y_i-\bar{y}\rVert\le L_{\mathrm{loc}}\lVert Y_\perp\rVert_F/\sqrt{m} ∥ e k ∥ ≤ m L loc ∑ i ∥ y i − y ˉ ∥ ≤ L loc ∥ Y ⊥ ∥ F / m . The queries are F τ k − \mathcal{F}_{\tau_k-} F τ k − -measurable, so e k e_k e k is predictable, and uncorrelated node noises give the variance bound. □ \square □
Lemma 4.18 (Disagreement bound). Let Assumption 4.16 hold with a common initialization. Put c T : = γ θ 2 T / ( 2 L ) c_T:=\gamma\theta^2T/(2L) c T := γ θ 2 T / ( 2 L ) and ζ ˉ b : = ζ ˉ + σ / b \bar{\zeta}_b:=\bar{\zeta}+\sigma/\sqrt{b} ζ ˉ b := ζ ˉ + σ / b , and assume
ψ : = δ m i x ( 2 + κ l o c + κ l o c γ θ 2 T / 2 ) ≤ 1 2 . (34) \psi:=\delta_{\mathrm{mix}}\left(2+\kappa_{\mathrm{loc}}+\kappa_{\mathrm{loc}}\gamma\theta^2T/2\right)\le\frac{1}{2}. \tag*{(34)} ψ := δ mix ( 2 + κ loc + κ loc γ θ 2 T /2 ) ≤ 2 1 . (34) Let E \mathcal{E} E be the sigma-field generated by all interarrivals and s k 2 : = E [ ∥ X ⊥ ( k ) ∥ F 2 + ∥ Z ⊥ ( k ) ∥ F 2 ∣ E ] / m s_k^2:=\mathbb{E}\left[\lVert X_\perp^{(k)}\rVert_F^2+\lVert Z_\perp^{(k)}\rVert_F^2\mid\mathcal{E}\right]/m s k 2 := E [ ∥ X ⊥ ( k ) ∥ F 2 + ∥ Z ⊥ ( k ) ∥ F 2 ∣ E ] / m . Then s k ≤ s ˉ : = 2 δ m i x ( 1 / L + c T ) ζ ˉ b s_k\le\bar{s}:=2\delta_{\mathrm{mix}}(1/L+c_T)\bar{\zeta}_b s k ≤ s ˉ := 2 δ mix ( 1/ L + c T ) ζ ˉ b for every event with τ k ≤ T \tau_k\le T τ k ≤ T . Moreover E ∥ X ⊥ ( t ) ∥ F 2 / m ≤ s ˉ 2 \mathbb{E}\lVert X_\perp(t)\rVert_F^2/m\le\bar{s}^2 E ∥ X ⊥ ( t ) ∥ F 2 / m ≤ s ˉ 2 for every t ∈ [ 0 , T ] t\in[0,T] t ∈ [ 0 , T ] , and the bias
e t : = m − 1 ∑ i [ ∇ f i ( x i ( t − ) ) − ∇ f i ( x ˉ t − ) ] e_t:=m^{-1}\sum_i\left[\nabla f_i(x_i(t-))-\nabla f_i(\bar{x}_{t-})\right] e t := m − 1 i ∑ [ ∇ f i ( x i ( t − )) − ∇ f i ( x ˉ t − ) ] satisfies
E ∥ e t ∥ 2 ≤ e ˉ 2 , e ˉ : = L l o c s ˉ = 2 δ m i x κ l o c ( 1 + γ θ 2 T / 2 ) ζ ˉ b . \mathbb{E}\lVert e_t\rVert^2\le\bar{e}^2,\qquad
\bar{e}:=L_{\mathrm{loc}}\bar{s}
=2\delta_{\mathrm{mix}}\kappa_{\mathrm{loc}}\left(1+\gamma\theta^2T/2\right)\bar{\zeta}_b. E ∥ e t ∥ 2 ≤ e ˉ 2 , e ˉ := L loc s ˉ = 2 δ mix κ loc ( 1 + γ θ 2 T /2 ) ζ ˉ b . Proof. Step 0: conditioning on the clock. Condition on E \mathcal{E} E ; event times and the number of events in [ 0 , T ] [0,T] [ 0 , T ] become deterministic. By Assumption 4.16(iii) and the tower property, the conditional second moment of the noise at event k k k given E \mathcal{E} E is still at most σ 2 / b \sigma^2/b σ 2 / b per node, because E \mathcal{E} E is generated by F τ k − \mathcal{F}_{\tau_k-} F τ k − and the future interarrivals. Write rms ( A ) : = ( E [ ∥ A ∥ F 2 ∣ E ] / m ) 1 / 2 \operatorname{rms}(A):=\left(\mathbb{E}[\lVert A\rVert_F^2\mid\mathcal{E}]/m\right)^{1/2} rms ( A ) := ( E [∥ A ∥ F 2 ∣ E ] / m ) 1/2 ; it satisfies Minkowski’s inequality.
Step 1: flow. Between events Z ⊥ Z_\perp Z ⊥ is constant and X ⊥ ( t ) = α X ⊥ + ( 1 − α ) Z ⊥ X_\perp(t)=\alpha X_\perp+(1-\alpha)Z_\perp X ⊥ ( t ) = α X ⊥ + ( 1 − α ) Z ⊥ with α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . By convexity of ∥ ⋅ ∥ F 2 \lVert\cdot\rVert_F^2 ∥ ⋅ ∥ F 2 , ∥ X ⊥ ( t ) ∥ F 2 ≤ ∥ X ⊥ ∥ F 2 + ∥ Z ⊥ ∥ F 2 \lVert X_\perp(t)\rVert_F^2\le\lVert X_\perp\rVert_F^2+\lVert Z_\perp\rVert_F^2 ∥ X ⊥ ( t ) ∥ F 2 ≤ ∥ X ⊥ ∥ F 2 + ∥ Z ⊥ ∥ F 2 . In particular the next query satisfies rms ( Y ⊥ ) ≤ s k \operatorname{rms}(Y_\perp)\le s_k rms ( Y ⊥ ) ≤ s k .
Step 2: one event. Since ( I − J ) W = W − J = ( W − J ) ( I − J ) (I-J)W=W-J=(W-J)(I-J) ( I − J ) W = W − J = ( W − J ) ( I − J ) ,
X ⊥ ( k + 1 ) = ( W − J ) ( Y ⊥ − G ⊥ / L ) , Z ⊥ ( k + 1 ) = ( W − J ) ( Z ⊥ ( k ) − c G ⊥ ) , X_\perp^{(k+1)}=(W-J)(Y_\perp-G_\perp/L),\qquad
Z_\perp^{(k+1)}=(W-J)(Z_\perp^{(k)}-cG_\perp), X ⊥ ( k + 1 ) = ( W − J ) ( Y ⊥ − G ⊥ / L ) , Z ⊥ ( k + 1 ) = ( W − J ) ( Z ⊥ ( k ) − c G ⊥ ) , with W = W k + 1 W=W_{k+1} W = W k + 1 , G ⊥ = ( I − J ) G G_\perp=(I-J)G G ⊥ = ( I − J ) G , and c = c τ k + 1 ≤ c T c=c_{\tau_{k+1}}\le c_T c = c τ k + 1 ≤ c T .
Step 3: gradient disagreement. Write G = [ ∇ f i ( y i ) − ∇ f i ( y ˉ ) ] i + [ ∇ f i ( y ˉ ) ] i + Ξ G=[\nabla f_i(y_i)-\nabla f_i(\bar{y})]_i+[\nabla f_i(\bar{y})]_i+\Xi G = [ ∇ f i ( y i ) − ∇ f i ( y ˉ ) ] i + [ ∇ f i ( y ˉ ) ] i + Ξ , where Ξ \Xi Ξ is the noise. The projection I − J I-J I − J does not increase the Frobenius norm, and ( I − J ) [ ∇ f i ( y ˉ ) ] i (I-J)[\nabla f_i(\bar{y})]_i ( I − J ) [ ∇ f i ( y ˉ ) ] i has Frobenius norm m ζ ( y ˉ ) ≤ m ζ ˉ \sqrt{m}\,\zeta(\bar{y})\le\sqrt{m}\,\bar{\zeta} m ζ ( y ˉ ) ≤ m ζ ˉ . Hence rms ( G ⊥ ) ≤ L l o c s k + ζ ˉ + σ / b \operatorname{rms}(G_\perp)\le L_{\mathrm{loc}}s_k+\bar{\zeta}+\sigma/\sqrt{b} rms ( G ⊥ ) ≤ L loc s k + ζ ˉ + σ / b .
Step 4: recursion. Minkowski’s inequality and ∥ ( W − J ) A ∥ F ≤ δ m i x ∥ A ∥ F \lVert(W-J)A\rVert_F\le\delta_{\mathrm{mix}}\lVert A\rVert_F ∥( W − J ) A ∥ F ≤ δ mix ∥ A ∥ F give
s k + 1 ≤ rms ( X ⊥ ( k + 1 ) ) + rms ( Z ⊥ ( k + 1 ) ) ≤ δ m i x [ ( 2 + κ l o c + c T L l o c ) s k + ( 1 / L + c T ) ζ ˉ b ] = ψ s k + s ˉ 2 , s_{k+1}\le\operatorname{rms}(X_\perp^{(k+1)})+\operatorname{rms}(Z_\perp^{(k+1)})
\le\delta_{\mathrm{mix}}\left[(2+\kappa_{\mathrm{loc}}+c_TL_{\mathrm{loc}})s_k+(1/L+c_T)\bar{\zeta}_b\right]
=\psi s_k+\frac{\bar{s}}{2}, s k + 1 ≤ rms ( X ⊥ ( k + 1 ) ) + rms ( Z ⊥ ( k + 1 ) ) ≤ δ mix [ ( 2 + κ loc + c T L loc ) s k + ( 1/ L + c T ) ζ ˉ b ] = ψ s k + 2 s ˉ , where c T L l o c = κ l o c γ θ 2 T / 2 c_TL_{\mathrm{loc}}=\kappa_{\mathrm{loc}}\gamma\theta^2T/2 c T L loc = κ loc γ θ 2 T /2 . Since s 0 = 0 s_0=0 s 0 = 0 and ψ ≤ 1 / 2 \psi\le1/2 ψ ≤ 1/2 , induction gives s k ≤ s ˉ s_k\le\bar{s} s k ≤ s ˉ .
Step 5: fixed times. For t ≤ T t\le T t ≤ T the index n t n_t n t is E \mathcal{E} E -measurable, and Step 1 gives E [ ∥ X ⊥ ( t ) ∥ F 2 ∣ E ] / m ≤ s n t 2 ≤ s ˉ 2 \mathbb{E}[\lVert X_\perp(t)\rVert_F^2\mid\mathcal{E}]/m\le s_{n_t}^2\le\bar{s}^2 E [∥ X ⊥ ( t ) ∥ F 2 ∣ E ] / m ≤ s n t 2 ≤ s ˉ 2 . Taking expectations and applying the bias bound of Lemma 4.17 at x i ( t − ) x_i(t-) x i ( t − ) completes the proof. □ \square □
The two lemmas place D-CQA inside Theorem 4.3 (a): the network average is a CQA process whose oracle has a mean-square bias bounded by e ˉ \bar e e ˉ , and the square-root Gronwall argument absorbs the linear bias terms without a projection.
Theorem 4.19 (Fully decentralized accelerated bound). Let Assumption 4.16 hold with a common initialization, θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] , and (34). Assume the finite-horizon integrability conditions of Theorem 4.3 for the stacked process; they hold by Lemma A.2, because the local gradients grow at most linearly. Then Algorithm 6 satisfies
E [ F ( x ˉ T ) − F ( x ∗ ) ] ≤ ( 2 L R 0 2 γ 2 θ 2 T 2 + V θ T 3 L ( e ˉ 2 + σ 2 m b ) + ( 1 + θ ) θ T e ˉ 2 2 L ) 2 (35) \mathbb{E}[F(\bar{x}_T)-F(x^*)]\leq\left(\sqrt{\frac{2LR_0^2}{\gamma^2\theta^2T^2}+\frac{V_\theta T}{3L}\left(\bar{e}^2+\frac{\sigma^2}{mb}\right)}+\frac{(1+\theta)\theta T\bar{e}}{2\sqrt{2L}}\right)^2 \tag*{(35)} E [ F ( x ˉ T ) − F ( x ∗ )] ≤ ( γ 2 θ 2 T 2 2 L R 0 2 + 3 L V θ T ( e ˉ 2 + mb σ 2 ) + 2 2 L ( 1 + θ ) θ T e ˉ ) 2 (35) and the node outputs satisfy 1 m ∑ i E [ F ( x i ( T ) ) − F ( x ∗ ) ] ≤ \frac{1}{m}\sum_i\mathbb{E}[F(x_i(T))-F(x^*)]\leq m 1 ∑ i E [ F ( x i ( T )) − F ( x ∗ )] ≤ (right side of (35) ) + e ˉ 2 / ( 2 κ l o c 2 L ) +\bar{e}^2/(2\kappa_{\mathrm{loc}}^2L) + e ˉ 2 / ( 2 κ loc 2 L ) .
Proof. By Lemma 4.17 , ( x ˉ t , z ˉ t ) (\bar{x}_t,\bar{z}_t) ( x ˉ t , z ˉ t ) is the process (10) driven by an oracle with predictable bias e t e_t e t and centered variance at most σ 2 / ( m b ) \sigma^2/(mb) σ 2 / ( mb ) , so Theorem 4.3 (a) applies with η = 0 \eta=0 η = 0 , ς ˉ t 2 = σ 2 / ( m b ) \bar{\varsigma}_t^2=\sigma^2/(mb) ς ˉ t 2 = σ 2 / ( mb ) , and, by Lemma 4.18 , the constant e ˉ t = e ˉ \bar{e}_t=\bar{e} e ˉ t = e ˉ . Then Γ T = 2 L R 0 2 / ( γ 2 θ 2 T 2 ) + V θ T ( e ˉ 2 + σ 2 / ( m b ) ) / ( 3 L ) \Gamma_T=2LR_0^2/(\gamma^2\theta^2T^2)+V_\theta T(\bar{e}^2+\sigma^2/(mb))/(3L) Γ T = 2 L R 0 2 / ( γ 2 θ 2 T 2 ) + V θ T ( e ˉ 2 + σ 2 / ( mb )) / ( 3 L ) and B T = ( 1 + θ ) θ T e ˉ / ( 2 2 L ) B_T=(1+\theta)\theta T\bar{e}/(2\sqrt{2L}) B T = ( 1 + θ ) θ T e ˉ / ( 2 2 L ) ; dropping the nonnegative gradient integral gives (35) . For the node outputs, smoothness of F F F and ∑ i ( x i − x ˉ ) = 0 \sum_i(x_i-\bar{x})=0 ∑ i ( x i − x ˉ ) = 0 give 1 m ∑ i F ( x i ) ≤ F ( x ˉ ) + L 2 m ∥ X ⊥ ∥ F 2 \frac{1}{m}\sum_i F(x_i)\leq F(\bar{x})+\frac{L}{2m}\lVert X_\perp\rVert_F^2 m 1 ∑ i F ( x i ) ≤ F ( x ˉ ) + 2 m L ∥ X ⊥ ∥ F 2 , and Lemma 4.18 bounds the expectation of the last term by L s ˉ 2 / 2 = e ˉ 2 / ( 2 κ l o c 2 L ) L\bar{s}^2/2=\bar{e}^2/(2\kappa_{\mathrm{loc}}^2L) L s ˉ 2 /2 = e ˉ 2 / ( 2 κ loc 2 L ) .
Corollary 4.20 (Complexity of D-CQA). Let ϵ > 0 \epsilon>0 ϵ > 0 and suppose that
T ≥ 5 L R 0 / ( γ θ ϵ ) T\geq5\sqrt{LR_0}/(\gamma\theta\sqrt{\epsilon}) T ≥ 5 L R 0 / ( γ θ ϵ ) ;
b ≥ 4 V θ T σ 2 / ( L m ϵ ) b\geq4V_\theta T\sigma^2/(Lm\epsilon) b ≥ 4 V θ T σ 2 / ( L m ϵ ) (void if σ = 0 \sigma=0 σ = 0 );
the mixing accuracy satisfies δ m i x ≤ δ ϵ \delta_{\mathrm{mix}}\leq\delta_\epsilon δ mix ≤ δ ϵ , where
δ ϵ : = min { 1 2 ( 2 + κ l o c + κ l o c γ θ 2 T / 2 ) , min { L ϵ / ( 4 V θ T ) , 2 L ϵ / ( ( 1 + θ ) θ T ) } 2 κ l o c ( 1 + γ θ 2 T / 2 ) ζ ˉ b } . \delta_\epsilon:=\min\left\{\frac{1}{2(2+\kappa_{\mathrm{loc}}+\kappa_{\mathrm{loc}}\gamma\theta^2T/2)},\frac{\min\left\{\sqrt{L\epsilon/(4V_\theta T)},\sqrt{2L\epsilon/((1+\theta)\theta T)}\right\}}{2\kappa_{\mathrm{loc}}(1+\gamma\theta^2T/2)\bar{\zeta}_b}\right\}. δ ϵ := min ⎩ ⎨ ⎧ 2 ( 2 + κ loc + κ loc γ θ 2 T /2 ) 1 , 2 κ loc ( 1 + γ θ 2 T /2 ) ζ ˉ b min { L ϵ / ( 4 V θ T ) , 2 L ϵ / (( 1 + θ ) θ T ) } ⎭ ⎬ ⎫ . Then E [ F ( x ˉ T ) − F ( x ∗ ) ] ≤ ϵ \mathbb{E}[F(\bar{x}_T)-F(x^*)]\leq\epsilon E [ F ( x ˉ T ) − F ( x ∗ )] ≤ ϵ , and the average of the node outputs is at most ( 1 + 1 4 T ) ϵ (1+\frac{1}{4T})\epsilon ( 1 + 4 T 1 ) ϵ . On a fixed graph, Chebyshev filtering with q ≥ χ + 1 2 ln ( 2 / δ ϵ ) q\geq\frac{\sqrt{\chi}+1}{2}\ln(2/\delta_\epsilon) q ≥ 2 χ + 1 ln ( 2/ δ ϵ ) suffices. For small ϵ \epsilon ϵ the binding term of δ ϵ \delta_\epsilon δ ϵ is of order γ ϵ 3 / 2 / ( θ κ l o c L R 0 2 ζ ˉ b ) \gamma\epsilon^{3/2}/(\theta\kappa_{\mathrm{loc}}\sqrt{L R_0^2\bar{\zeta}_b}) γ ϵ 3/2 / ( θ κ loc L R 0 2 ζ ˉ b ) , so
q ϵ = O ( χ log κ l o c L R 0 2 ζ ˉ b γ ϵ ) , r o u n d s = T q ϵ = O ~ ( χ L R 0 γ θ ϵ ) . q_\epsilon=O\left(\sqrt{\chi}\log\frac{\kappa_{\mathrm{loc}}\sqrt{L R_0^2\bar{\zeta}_b}}{\gamma\epsilon}\right),\qquad\mathrm{rounds}=Tq_\epsilon=\widetilde{O}\left(\frac{\sqrt{\chi}\sqrt{LR_0}}{\gamma\theta\sqrt{\epsilon}}\right). q ϵ = O ( χ log γ ϵ κ loc L R 0 2 ζ ˉ b ) , rounds = T q ϵ = O ( γ θ ϵ χ L R 0 ) . Per event, each node evaluates one row and the network transmits 4 ∣ E ∣ q 4|E|q 4∣ E ∣ q vectors in R d \mathbb{R}^d R d . On changing graphs any certificate of the form (32) applies: with κ s ≤ 1 \kappa_s\leq1 κ s ≤ 1 it suffices to run r ≥ ln ( 1 / δ ϵ ) / ln ( 1 / η b l k ) r\geq\ln(1/\delta_\epsilon)/\ln(1/\eta_{\mathrm{blk}}) r ≥ ln ( 1/ δ ϵ ) / ln ( 1/ η blk ) blocks of B b l k B_{\mathrm{blk}} B blk rounds per event. No dissemination bound is needed.
Proof. Let a 2 a^2 a 2 be the expression under the square root in (35) and β e \beta_e β e the second summand. Condition (i) gives 2 L R 0 2 / ( γ 2 θ 2 T 2 ) ≤ 2 ϵ / 25 ≤ ϵ / 12 2LR_0^2/(\gamma^2\theta^2T^2)\leq2\epsilon/25\leq\epsilon/12 2 L R 0 2 / ( γ 2 θ 2 T 2 ) ≤ 2 ϵ /25 ≤ ϵ /12 , and (ii) gives V θ T σ 2 / ( 3 L m b ) ≤ ϵ / 12 V_\theta T\sigma^2/(3Lmb)\leq\epsilon/12 V θ T σ 2 / ( 3 L mb ) ≤ ϵ /12 . Condition (iii) gives ψ ≤ 1 / 2 \psi\leq1/2 ψ ≤ 1/2 , V θ T e ˉ 2 / ( 3 L ) ≤ ϵ / 12 V_\theta T\bar{e}^2/(3L)\leq\epsilon/12 V θ T e ˉ 2 / ( 3 L ) ≤ ϵ /12 , and β e 2 ≤ ϵ / 4 \beta_e^2\leq\epsilon/4 β e 2 ≤ ϵ /4 . Hence ( a + β e ) 2 ≤ 2 a 2 + 2 β e 2 ≤ ϵ (a+\beta_e)^2\leq2a^2+2\beta_e^2\leq\epsilon ( a + β e ) 2 ≤ 2 a 2 + 2 β e 2 ≤ ϵ . The node term is e ˉ 2 / ( 2 κ l o c 2 L ) ≤ ϵ / ( 8 κ l o c V θ T ) ≤ ϵ / ( 4 T ) \bar{e}^2/(2\kappa_{\mathrm{loc}}^2L)\leq\epsilon/(8\kappa_{\mathrm{loc}}V_\theta T)\leq\epsilon/(4T) e ˉ 2 / ( 2 κ loc 2 L ) ≤ ϵ / ( 8 κ loc V θ T ) ≤ ϵ / ( 4 T ) . The Chebyshev depth follows from Lemma 4.7 . For the order of δ ϵ \delta_\epsilon δ ϵ , substitute T T T from (i): after division by 1 + γ θ 2 T / 2 1+\gamma\theta^2T/2 1 + γ θ 2 T /2 , the second entry of the inner minimum scales like ϵ 3 / 2 \epsilon^{3/2} ϵ 3/2 , the first like ϵ 5 / 4 \epsilon^{5/4} ϵ 5/4 , and the first entry of the outer minimum like ϵ 1 / 2 \epsilon^{1/2} ϵ 1/2 , so the second entry of the inner minimum is binding.
Remark 4.21 (Why the mixing accuracy must shrink like T − 2 T^{-2} T − 2 ). The auxiliary step c t = γ θ 2 t / ( 2 L ) c_t=\gamma\theta^2t/(2L) c t = γ θ 2 t / ( 2 L ) grows linearly in time. Each event therefore injects disagreement c t ζ t c_t\zeta_t c t ζ t into Z Z Z , and the bias grows like δ m i x c T ζ \delta_{\mathrm{mix}}c_T\zeta δ mix c T ζ . In (35) this bias is multiplied once more by T T T , through ∫ 0 T c t d t \int_0^T c_t\,\mathrm{d}t ∫ 0 T c t d t . In CQA-Net the same heterogeneity enters as variance, V θ ∥ W q − J ∥ 2 2 T / ( 3 L ) V_\theta\lVert W_q-J\rVert_2^2T/(3L) V θ ∥ W q − J ∥ 2 2 T / ( 3 L ) , and only ∥ W q − J ∥ 2 ≲ ϵ 3 / 4 \lVert W_q-J\rVert_2\lesssim\epsilon^{3/4} ∥ W q − J ∥ 2 ≲ ϵ 3/4 is needed. Both requirements give O ( χ log ( 1 / ϵ ) ) O(\sqrt{\chi}\log(1/\epsilon)) O ( χ log ( 1/ ϵ )) rounds per event and differ only in the constant inside the logarithm; CQA-Net additionally pays the dissemination depth D D D .
Comparison of the three implementations
Table 2 compares the cost of one event. CQA-Net keeps the strongest guarantee, an unbiased oracle at every mixing depth with no additional assumptions, and pays the global primitives (G1)–(G3). The token removes all global primitives with no new assumption on a fixed graph, but its walk is sequential and long. D-CQA meets the usual synchronous notion of decentralization and removes the dissemination depth from the round count, at the price of local smoothness, bounded heterogeneity, and a mixing accuracy that must improve with the horizon (δ m i x ≲ ε 3 / 2 \delta_{\mathrm{mix}} \lesssim\varepsilon^{3/2} δ mix ≲ ε 3/2 , against ∥ W q − J ∥ 2 ≲ ε 3 / 4 \lVert W_q-J\rVert_2 \lesssim\varepsilon^{3/4} ∥ W q − J ∥ 2 ≲ ε 3/4 for CQA-Net). The main results are Theorem 4.8 for CQA-Net, Corollaries 4.13 and 4.14 for the token, and Theorem 4.19 with Corollary 4.20 for D-CQA.
Numerical experiments
The experiments examine individual parts of the analysis under constants that can be checked from the supplied data. We record both deterministic horizons and realized oracle work, and report computation separately from communication. Static and two-window-connected graphs are tested, and a separate experiment isolates persistent stochastic noise. § 5.4 runs the walking token and D-CQA of § 3.5 –§ 3.6 ; all other experiments use CQA-Net. Appendix § 13 describes the code, runwise data, full-precision constants, and validation checks.
Protocol and cost accounting
We simulate the closed-form flow exactly. For every event index, the graph and mixer are fixed from the revealed past before the current exponential interarrival is generated; local rows and the fresh uniform root are then sampled in the order required by Lemma A.1. Unless stated otherwise, CQA-Net uses θ = 1 \theta= 1 θ = 1 . Curves compared with the theory are sample means over 24 independent runs with pointwise normal-approximation bands mean ± 1.96 \pm1.96 ± 1.96 SE; medians and interquartile intervals are used for typical-run cost plots. Values below 10 − 16 10^{-16} 1 0 − 16 are clipped only for logarithmic display and values below roughly 10 − 14 10^{-14} 1 0 − 14 are interpreted as numerical zero.
On a ring of diameter D D D , a finite-mixing event is charged q + D q+D q + D critical-path rounds and exact reduction plus dissemination is charged 2 D 2D 2 D . At q = 0 q=0 q = 0 , the root is selected before local computation, so only one node forms a row. For q > 0 q>0 q > 0 , every node forms a row before mixing. Aggregate row/full-gradient or component work, critical-path rounds, and transmitted-vector volume are kept separate, as labeled. In the regression ledger, one exact local full-gradient row counts as one evaluation. The baselines are exact-average gradient descent with step 1 / L 1/L 1/ L , classical convex Nesterov acceleration, and synchronous gradient tracking with a lazy Metropolis matrix. The tracking step was selected from the declared grid { 1 , 1 / 2 , 1 / 4 , 1 / 8 , 1 / 16 , 1 / 32 } / L \{1,1/2,1/4,1/8,1/16,1/32\}/L { 1 , 1/2 , 1/4 , 1/8 , 1/16 , 1/32 } / L ; 1 / L 1/L 1/ L minimized the final gap. The plotted tracker average is an offline diagnostic, and nodewise and consensus errors are reported below.
The principal instances and their certified geometry are described in § 2.2 . All manuscript constants are rounded; the machine-readable metadata retain full precision.
Certified nonconvex regression on fixed and changing graphs
Each of m = 16 m=16 m = 16 nodes stores 120 samples in dimension 18. Responses are realizable under the link φ 0.18 ( u ) = 0.18 u + 0.82 tanh u \varphi_{0.18}(u)=0.18u+0.82\tanh u φ 0.18 ( u ) = 0.18 u + 0.82 tanh u . Proposition 2.4 certifies γ = 0.36 \gamma=0.36 γ = 0.36 , L = 2.3631 L=2.3631 L = 2.3631 , and μ = 1.457 ⋅ 10 − 3 \mu=1.457\cdot10^{-3} μ = 1.457 ⋅ 1 0 − 3 ; the initial gap is 8.543 ⋅ 10 − 2 8.543\cdot10^{-2} 8.543 ⋅ 1 0 − 2 . On the ring, the measured pairs ( ∥ W q − J ∥ 2 , m − 1 ∥ W q ∥ F 2 ) (\lVert W_q-J\rVert_2,m^{-1}\lVert W_q\rVert_F^2) (∥ W q − J ∥ 2 , m − 1 ∥ W q ∥ F 2 ) are ( 1 , 1 ) (1,1) ( 1 , 1 ) , ( 0.55887 , 0.22483 ) (0.55887,0.22483) ( 0.55887 , 0.22483 ) , ( 0.12524 , 0.06913 ) (0.12524,0.06913) ( 0.12524 , 0.06913 ) , and ( 0.011736 , 0.062572 ) (0.011736,0.062572) ( 0.011736 , 0.062572 ) for q = 0 , 3 , 7 , 13 q=0,3,7,13 q = 0 , 3 , 7 , 13 . Thus unbiasedness is present already at q = 0 q=0 q = 0 , while finite mixing reduces both row disagreement and, toward its 1 / m 1/m 1/ m floor, independent row noise.
Table 3 merges accuracy and realized-work summaries, and Figure 2 shows the sample-mean progress. At gap 10 − 8 10^{-8} 1 0 − 8 , every CQA-Net run reaches the target.
Table 3. Static-ring performance. The first two columns use pointwise median horizons; the remaining columns are medians of runwise first-passage work to 10 − 8 10^{-8} 1 0 − 8 .
Figure 2. Globally certified leaky-tanh regression on the static 16-node ring: sample-mean objective gap versus the process horizon.
Table 3 : Static-ring performance. The first two columns use pointwise median horizons; the remaining columns are medians of runwise first-passage work to 10 − 8 10^{-8} 1 0 − 8 .
At horizon 520, realized Poisson counts range from 485 to 570, with median 526, so deterministic horizon and actual work are close only in aggregate. Along the exact representative trajectory the empirical quasar ratio remains above 1.9917, much larger than the global certificate 0.36; a separate near-tight one-dimensional diagnostic is reported below.
For a changing network, every communication subround is a disconnected perfect matching. Even and odd matchings alternate, so the union of two consecutive subrounds is the ring. The measured pairs are
q = 1 : ( ∥ W k , q − J ∥ 2 , m − 1 ∥ W k , q ∥ F 2 ) = ( 1 , 0.5 ) , q = 4 : ( ∥ W k , q − J ∥ 2 , m − 1 ∥ W k , q ∥ F 2 ) = ( 0.78858 , 0.15625 ) , q = 10 : ( ∥ W k , q − J ∥ 2 , m − 1 ∥ W k , q ∥ F 2 ) = ( 0.49039 , 0.092804 ) . \begin{aligned}
q &= 1:\quad\left(\lVert W_{k,q}-J\rVert_2,\,m^{-1}\lVert W_{k,q}\rVert_F^2\right)=(1,0.5),\\
q &= 4:\quad\left(\lVert W_{k,q}-J\rVert_2,\,m^{-1}\lVert W_{k,q}\rVert_F^2\right)=(0.78858,0.15625),\\
q &= 10:\quad\left(\lVert W_{k,q}-J\rVert_2,\,m^{-1}\lVert W_{k,q}\rVert_F^2\right)=(0.49039,0.092804).
\end{aligned} q q q = 1 : ( ∥ W k , q − J ∥ 2 , m − 1 ∥ W k , q ∥ F 2 ) = ( 1 , 0.5 ) , = 4 : ( ∥ W k , q − J ∥ 2 , m − 1 ∥ W k , q ∥ F 2 ) = ( 0.78858 , 0.15625 ) , = 10 : ( ∥ W k , q − J ∥ 2 , m − 1 ∥ W k , q ∥ F 2 ) = ( 0.49039 , 0.092804 ) .
Root dissemination is charged separately as 8 matching subrounds, the exact worst-case broadcast depth of the alternating 16-node ring. A full exact reduction followed by broadcast costs 16 matching subrounds.
The pointwise-median horizons to gap 10 − 10 10^{-10} 1 0 − 10 are 287, 294, and 244 for q = 1 , 4 , 10 q=1,4,10 q = 1 , 4 , 10 , compared with 267 under exact averaging. These values show that the optimization dynamics use the actual product norms supplied by the external schedule, as stated in Theorem 4.8 .
Variance mechanisms: mixing, damping, and noise
Finite pre-mixing and the scope of the closed certificates. On the ring, consider f i ( x ) = a i x 2 / 2 f_i(x)=a_i x^2/2 f i ( x ) = a i x 2 /2 with mean curvature one and local curvature heterogeneity aligned with the fixed Fourier mode v i = 2 cos ( π i / 2 + π / 2 ) v_i=\sqrt{2}\cos(\pi i/2+\pi/2) v i = 2 cos ( π i /2 + π /2 ) , i = 0 , … , 15 i=0,\ldots,15 i = 0 , … , 15 , so that a i = 1 + 0.8 v i a_i=1+0.8v_i a i = 1 + 0.8 v i . This explicit phase avoids any dependence on a numerical eigenbasis. The network objective is F ( x ) = x 2 / 2 F(x)=x^2/2 F ( x ) = x 2 /2 and ζ 2 ( x ) = 1.28 [ F ( x ) − F ( x ⋆ ) ] \zeta^2(x)=1.28[F(x)-F(x^\star)] ζ 2 ( x ) = 1.28 [ F ( x ) − F ( x ⋆ )] . With q = 3 q=3 q = 3 , the selected mode is attenuated by 0.06620 even though the worst-case norm is ∥ W 3 − J ∥ 2 = 0.55887 \lVert W_3-J\rVert_2=0.55887 ∥ W 3 − J ∥ 2 = 0.55887 . Empirically, the q = 0 q=0 q = 0 sample mean is dominated by rare unstable paths and does not reach 10 − 6 10^{-6} 1 0 − 6 by horizon 120, whereas q = 3 q=3 q = 3 reaches it at horizon 26, using 416 aggregate gradients and 286 communication rounds. Exact averaging reaches it sooner, at horizon 16 with 256 gradients and 256 rounds, so the test contrasts mixing with the unstable unmixed sample mean and makes no claim that it beats exact averaging.
The global worst-case norm certificate does not cover this example. The Gronwall small-exponent condition permits only T ≤ 0.72 T\le0.72 T ≤ 0.72 at q = 3 q=3 q = 3 , while the factor at T = 26 T=26 T = 26 is about 3.27 ⋅ 10 4 3.27\cdot10^4 3.27 ⋅ 1 0 4 . For θ 2 = 1 / 2 \theta^2=1/2 θ 2 = 1/2 , the dissipative condition (31) has left-hand side 0.5997 > 0.25 >0.25 > 0.25 at q = 3 q=3 q = 3 . The favorable q = 3 q=3 q = 3 curves come from mode alignment; the global ∥ W q − J ∥ 2 \lVert W_q-J\rVert_2 ∥ W q − J ∥ 2 certificate does not explain them.
At q = 7 q=7 q = 7 , the global dissipative certificate does apply: 2 V g b l ∥ W 7 − J ∥ 2 2 = 0.03012 < 0.25 2V_g b_l\lVert W_7-J\rVert_2^2=0.03012<0.25 2 V g b l ∥ W 7 − J ∥ 2 2 = 0.03012 < 0.25 for θ 2 = 1 / 2 \theta^2=1/2 θ 2 = 1/2 . The resulting ablation gives sample-mean hitting horizons 18, 17, and 24 for θ = 1 \theta=1 θ = 1 , θ 2 = 1 / 2 \theta^2=1/2 θ 2 = 1/2 , and θ = 1 / 2 \theta=1/2 θ = 1/2 , respectively: moderate damping absorbs the certified multiplicative noise, while stronger damping slows the method down.
Persistent mini-batch noise. Balanced affine component perturbations create nonzero mini-batch variance without changing any full local gradient or the global objective. At horizon 400, the sample-mean full-gradient gap is 1.62 ⋅ 10 − 9 1.62\cdot10^{-9} 1.62 ⋅ 1 0 − 9 , whereas the means for b = 16 , 8 , 4 b=16,8,4 b = 16 , 8 , 4 are 1.24 ⋅ 10 − 3 1.24\cdot10^{-3} 1.24 ⋅ 1 0 − 3 , 2.06 ⋅ 10 − 3 2.06\cdot10^{-3} 2.06 ⋅ 1 0 − 3 , and 6.04 ⋅ 10 − 3 6.04\cdot10^{-3} 6.04 ⋅ 1 0 − 3 . This is the noise accumulation isolated by the t 2 t^2 t 2 variance integral.
Broadcast-free implementations
We run the walking token (Algorithm 5) and D-CQA (Algorithm 6) next to CQA-Net on the certified regression of § 5.2 , with 24 independent runs to horizon 520. All methods use θ 2 = 1 / 2 \theta^2 = 1/2 θ 2 = 1/2 , because the token in fixed mode requires θ < 1 \theta< 1 θ < 1 . Costs per event follow Table 2 : CQA-Net is charged q + D q + D q + D rounds, the token h w + 2 q h_w + 2q h w + 2 q sequential rounds, and D-CQA q q q rounds, in each of which every node sends the pair ( x i , z i ) (x_i, z_i) ( x i , z i ) to each neighbor.
On the fixed ring the weighted token walks with lazy Metropolis weights. We use h w = 48 h_w = 48 h w = 48 , the smallest length for which the computed endpoint law satisfies max i ∣ m π k ( i ) − 1 ∣ ≤ 1 / 6 \max_i |m\pi_k(i) - 1| \le1/6 max i ∣ m π k ( i ) − 1∣ ≤ 1/6 ; Lemma 4.12 and Corollary 4.13 hold with this computed deviation in place of ρ h \rho_h ρ h , whereas the spectral condition (33) would require h w = 88 h_w = 88 h w = 88 . We also run a lifted walk that carries a direction and reverses it with probability 4 / m 4/m 4/ m per hop; it reaches the same deviation with h w = 11 h_w = 11 h w = 11 , and its exact endpoint law gives the weight, so Lemma 4.6 (ii) still makes the oracle unbiased. D-CQA mixes the states with the Chebyshev filter W q W_q W q , q ∈ { 1 , 3 , 7 } q \in\{1, 3, 7\} q ∈ { 1 , 3 , 7 } , and we report the gap of the network average x ˉ \bar{x} x ˉ . On the alternating matchings of § 5.2 , the token is unweighted, and D-CQA mixes with the product of q ∈ { 2 , 8 , 32 } q \in\{2, 8, 32\} q ∈ { 2 , 8 , 32 } matching subrounds.
Figure 3 (a) shows that per event all methods progress alike: every run reaches 10 − 8 10^{-8} 1 0 − 8 , at median horizons between 202 and 219, and the D-CQA node outputs reach it at the same horizons as x ˉ \bar{x} x ˉ . The methods differ in what one event costs (Figure 3 (b)). To reach 10 − 8 10^{-8} 1 0 − 8 , CQA-Net with q = 0 q = 0 q = 0 needs 1,464 rounds. The Metropolis token needs 8,520, which is the latency price of a sequential walk, while the lifted token needs only 1,991. D-CQA with one round per event needs 154 rounds, 9.5 times fewer than CQA-Net; it pays in computation, 2,464 row evaluations against 183, and in data, 1.8 ⋅ 10 5 1.8 \cdot10^5 1.8 ⋅ 1 0 5 transmitted scalars against 4.9 ⋅ 10 4 4.9 \cdot10^4 4.9 ⋅ 1 0 4 . On the alternating matchings (Figure 3 (c)), D-CQA with q = 2 q = 2 q = 2 , one connected window per event, needs 308 subrounds, against 1,400 for CQA-Net with dissemination and 1,552 for the token with h w = 8 h_w = 8 h w = 8 ; the token transmits the least data, 2.9 ⋅ 10 4 2.9 \cdot10^4 2.9 ⋅ 1 0 4 scalars against 4.7 ⋅ 10 4 4.7 \cdot10^4 4.7 ⋅ 1 0 4 and 1.8 ⋅ 10 5 1.8 \cdot10^5 1.8 ⋅ 1 0 5 .
Figure 3. Broadcast-free implementations on the certified regression instance (θ 2 = 1 / 2 \theta^2 = 1/2 θ 2 = 1/2 , 24 runs). (a)–(b) CQA-Net, the weighted token (Metropolis walk with h w = 48 h_w = 48 h w = 48 , lifted walk with h w = 11 h_w = 11 h w = 11 ), and D-CQA with Chebyshev mixing (network average x ˉ \bar{x} x ˉ ). (c) Alternating matchings: CQA-Net with dissemination, the unweighted token, and D-CQA with q q q matching subrounds per event.
These runs lie partly outside the hypotheses of the corresponding results. The partitioned regression violates item (ii) of Assumption 4.16, and the unweighted token with h w = 8 h_w = 8 h w = 8 has m ϱ k = 9.2 m\varrho_k = 9.2 m ϱ k = 9.2 , far from the regime m ϱ ˉ ≤ 1 m\bar{\varrho} \le1 m ϱ ˉ ≤ 1 of Corollary 4.14. Both methods nevertheless converge because the instance is realizable: every local gradient vanishes at x ⋆ x^\star x ⋆ , so the walk bias and the disagreement injected by D-CQA vanish there as well. The counts are rounds and messages; they do not measure the latency of sequential hops or of synchronous rounds.
Diagnostics and limits of interpretation
The gradient-tracking comparator reaches an offline mean gap 9.58 ⋅ 10 − 8 9.58 \cdot10^{-8} 9.58 ⋅ 1 0 − 8 at iteration 520; the node-1 and worst-node gaps are 9.60 ⋅ 10 − 8 9.60 \cdot10^{-8} 9.60 ⋅ 1 0 − 8 and 9.69 ⋅ 10 − 8 9.69 \cdot10^{-8} 9.69 ⋅ 1 0 − 8 , with mean squared consensus error 5.56 ⋅ 10 − 9 5.56 \cdot10^{-9} 5.56 ⋅ 1 0 − 9 . Replacing Poisson interarrivals by deterministic unit intervals gives gap 1.20 ⋅ 10 − 13 1.20 \cdot10^{-13} 1.20 ⋅ 1 0 − 13 at index 520, while the Poisson-process sample mean is 2.05 ⋅ 10 − 12 2.05 \cdot10^{-12} 2.05 ⋅ 1 0 − 12 with standard error 1.16 ⋅ 10 − 12 1.16 \cdot10^{-12} 1.16 ⋅ 1 0 − 12 (see Figure 4 ). On this instance the random clock is needed for the proof and the exact simulator, but not for convergence in practice.
Figure 4. Poisson versus unit-clock events on the certified regression. The deterministic-clock recurrence is not covered by the compensator proof.
Chebyshev filtering reaches ∥ W q − J ∥ 2 ≤ 0.1 \lVert W_q - J \rVert_2 \le0.1 ∥ W q − J ∥ 2 ≤ 0.1 on rings of size m = 8 , 16 , 32 , 64 m = 8, 16, 32, 64 m = 8 , 16 , 32 , 64 at depths 4, 8, 16, 31, compared with 11, 45, 179, 717 for plain lazy-Metropolis powers. A separate smooth monotone link has certified γ = 0.2 \gamma= 0.2 γ = 0.2 and an observed one-point ratio 0.205405 at an explicit probe, only 2.70% above the certificate.
The static, changing, and aligned-mode tests show how finite mixing changes the variance; they do not show that it always beats q = 0 q = 0 q = 0 or exact averaging. The certified q = 7 q = 7 q = 7 , θ 2 = 1 / 2 \theta^2 = 1/2 θ 2 = 1/2 ablation shows that damping absorbs multiplicative noise, but it does not optimize θ \theta θ . Agreement between the continuized formulas, sample means, and realized event counts says nothing about wall-clock time or about whether random clocks are necessary, and the experiments include no lower bounds, cluster timings, fault tolerance, or comparison with every local-state accelerated method.
Conclusion
Continuized quasar-convex acceleration survives finite network averaging. One Lyapunov theorem handles any oracle with a predictable bias and a state-dependent variance, and one lemma gives the moments of every selected-row network oracle. CQA-Net mixes local rows and disseminates one uniformly selected row: the oracle is unbiased at every depth, incomplete averaging enters only as variance, and the round count contains the dissemination depth D D D . The walking token removes every global primitive at the price of a sequential walk of length of order t r e l log m t_{\mathrm{rel}}\log m t rel log m ; on a fixed graph an importance weight keeps it unbiased, and on a changing graph its bias is controlled by walk products. D-CQA mixes local states: the network average is a biased CQA process, the mixing accuracy must improve like T − 2 T^{-2} T − 2 , and the round count O ~ ( χ L R 0 γ ε ) \widetilde{O}\left(\frac{\sqrt{\chi}\sqrt{LR_0}}{\gamma\sqrt{\varepsilon}}\right) O ( γ ε χ L R 0 ) has no dissemination term, at the price of local smoothness and bounded heterogeneity. For shared-landscape finite sums, exact-snapshot restarts give a geometric rate with fixed inner depth and batch size.
The results do not cover physical asynchrony, fault tolerance, or wall-clock performance, and the broadcast-free implementations are simulated only on a small instance (m = 16 m = 16 m = 16 , d = 18 d = 18 d = 18 ). Open questions include a lower bound on the per-event communication of common-state methods with an unbiased oracle, gradient tracking for D-CQA, which could remove the logarithm and the bounded heterogeneity assumption, variance reduction for finite sums with mixed rather than exact snapshots, and asynchronous clocks and message loss.
Acknowledgments
The research was supported by Russian Science Foundation (project No. 23-11-00229), https://rscf.ru/en/project/23-11-00229/.
Compensator calculus and localization
This appendix supplies the compensator, finite-horizon moment, and localization facts used in Theorem 4.3 . None of them is needed to implement the algorithms or to check the finite-mixing algebra.
Predictable drift and the simulation law
Let K t ( d g ) K_t(dg) K t ( d g ) be an F-predictable version of the conditional law of the event oracle. For a smooth test function, the predictable extended drift operator is the operator D t \mathcal{D}_t D t defined in (14) . If the oracle and mixer rules depend only on a finite-dimensional current state, this is the extended generator of a time-inhomogeneous piecewise-deterministic Markov process. Under the more general predictable history dependence used in the paper, it is a predictable local characteristic; the proof needs no Markov property.
For a bounded stopping time ρ ≤ T \rho\leq T ρ ≤ T and a test function of suitable smoothness and growth, the stopped Itô compensator identity reads
E ϕ ( ρ , x ρ , z ρ ) = E ϕ ( 0 , x 0 , z 0 ) + E ∫ 0 ρ ( D t ϕ ) ( t , x t − , z t − ) d t . (36) \mathbb{E}\phi(\rho,x_\rho,z_\rho)=\mathbb{E}\phi(0,x_0,z_0)+\mathbb{E}\int_0^\rho(\mathcal{D}_t\phi)(t,x_{t-},z_{t-})\,dt. \tag*{(36)} E ϕ ( ρ , x ρ , z ρ ) = E ϕ ( 0 , x 0 , z 0 ) + E ∫ 0 ρ ( D t ϕ ) ( t , x t − , z t − ) d t . (36)
Identity (36) follows from the unit predictable intensity of n t n_t n t and the usual jump Itô formula and optional stopping of the compensated jump integral. It is applied below with ρ = T ∧ τ R \rho=T\wedge\tau_R ρ = T ∧ τ R . Smooth truncation first makes the stopped local martingale integrable; the stated moment conditions then remove the truncation for the Lyapunov function.
Lemma A.1 (Law equivalence of on-line and pre-drawn clocks). Suppose the initial state is independent of i.i.d. Exp(1) interarrivals. After jump k k k , suppose the graph, the depth, the batch size, and the mean-preserving input-output operator for jump k + 1 k+1 k + 1 are chosen from the revealed past before E k E_k E k is revealed. Suppose also that the oracle/root mark at τ k + 1 \tau_{k+1} τ k + 1 is generated from an F-predictable kernel, with the root–row compatibility (7) when a lazy root is used, and is conditionally independent of future interarrivals. Then the event-driven simulation using the pre-drawn stream has the same finite-dimensional law as the jump process constructed in F with unit compensator dt and the same mark kernel.
Proof of Lemma A.1. The proof compares one conditional event transition and then iterates that identity over the event index.
Step 1: one-event conditional law. Let H k \mathcal{H}_k H k contain the state and all revealed innovations after jump k k k . In the analytical construction, the graph, mixer, batch size, and all other parameters for jump k + 1 k+1 k + 1 are selected as H k \mathcal{H}_k H k -measurable functions. An independent exponential variable E k E_k E k is then drawn, the deterministic flow forms the pre-jump query at τ k + 1 \tau_{k+1} τ k + 1 , and the fresh row and root innovations are sampled from their predictable conditional kernels. In the simulation construction the sequence ( E k ) k ≥ 0 (E_k)_{k\ge0} ( E k ) k ≥ 0 may have been generated in advance, but the same event parameters are required to be functions of H k \mathcal{H}_k H k alone and hence do not use the unrevealed value of E k E_k E k .
Conditionally on H k \mathcal{H}_k H k , both constructions therefore use the same iterated kernel: first the Exp ( 1 ) \operatorname{Exp}(1) Exp ( 1 ) law for E k E_k E k , then the predictable mark kernel evaluated at the resulting pre-jump history. This need not be a product law because a state-dependent oracle kernel can depend on the flowed query. Within the mark kernel, positive-depth rows precede an independent uniform root; at depth zero, (7) gives the equivalent product coupling of a uniform root and latent row seeds. The closed-form flow and jump map are deterministic functions of the sampled quantities.
Step 2: iteration and compensator filtration. Induction on k k k gives equality of the joint laws of every finite event prefix. Since i.i.d. positive exponential interarrivals are nonexplosive, these prefix laws determine the finite-horizon path law. The analytical filtration reveals E k E_k E k only through the occurrence of the next event, so n t n_t n t has compensator t t t there. The enlarged simulation filtration is useful for implementation but is not the filtration in which the compensator calculation is performed.
The coefficient 2 / ( γ t ) 2/(\gamma t) 2/ ( γ t ) has a removable singularity at the origin. Between two events, z t = z r z_t=z_r z t = z r and x t − z r = ( r / t ) 2 / γ ( x r − z r ) x_t-z_r=(r/t)^{2/\gamma}(x_r-z_r) x t − z r = ( r / t ) 2/ γ ( x r − z r ) for t ≥ r > 0 t\ge r>0 t ≥ r > 0 . Since x 0 = z 0 x_0=z_0 x 0 = z 0 , the continuous extension is constant before the first event. This also explains why the process can be simulated without a time discretization.
Finite-horizon moments
Assume that for constants 0 ≤ a 0 , a 1 < ∞ 0\le a_0,a_1<\infty 0 ≤ a 0 , a 1 < ∞ and all event times t ≤ T t\le T t ≤ T ,
E [ ∥ g t ∥ 2 ∣ F t − ] ≤ a 0 + a 1 ( ∥ x t − ∥ 2 + ∥ z t − ∥ 2 ) . (37) \mathbb{E}\left[\lVert g_t\rVert^2\mid\mathcal{F}_{t-}\right]\le a_0+a_1\left(\lVert x_{t-}\rVert^2+\lVert z_{t-}\rVert^2\right). \tag*{(37)} E [ ∥ g t ∥ 2 ∣ F t − ] ≤ a 0 + a 1 ( ∥ x t − ∥ 2 + ∥ z t − ∥ 2 ) . (37)
Lemma A.2 (Finite-horizon state moments). Under (37), for every finite T T T there is C T < ∞ C_T<\infty C T < ∞ such that
E sup 0 ≤ t ≤ T ( 1 + ∥ x t ∥ 2 + ∥ z t ∥ 2 ) ≤ C T ( 1 + ∥ x 0 ∥ 2 + ∥ z 0 ∥ 2 ) . \mathbb{E}\sup_{0\le t\le T}\left(1+\lVert x_t\rVert^2+\lVert z_t\rVert^2\right)\le C_T\left(1+\lVert x_0\rVert^2+\lVert z_0\rVert^2\right). E 0 ≤ t ≤ T sup ( 1 + ∥ x t ∥ 2 + ∥ z t ∥ 2 ) ≤ C T ( 1 + ∥ x 0 ∥ 2 + ∥ z 0 ∥ 2 ) .
Global smoothness and the linear-growth oracle therefore imply the finite-horizon integrability used in Theorem 4.3 .
Proof. The exact flow controls the state between events. A stopped compensator estimate then handles the jump increments.
Step 1: between-event control. Put S t = 1 + ∥ x t ∥ 2 + ∥ z t ∥ 2 S_t=1+\lVert x_t\rVert^2+\lVert z_t\rVert^2 S t = 1 + ∥ x t ∥ 2 + ∥ z t ∥ 2 and M t = sup 0 ≤ r ≤ t S r M_t=\sup_{0\le r\le t}S_r M t = sup 0 ≤ r ≤ t S r . Between events, x t = ( r / t ) 2 / γ x r + [ 1 − ( r / t ) 2 / γ ] z r x_t=(r/t)^{2/\gamma}x_r+[1-(r/t)^{2/\gamma}]z_r x t = ( r / t ) 2/ γ x r + [ 1 − ( r / t ) 2/ γ ] z r ; this is a convex combination because ( r / t ) 2 / γ ∈ [ 0 , 1 ] (r/t)^{2/\gamma}\in[0,1] ( r / t ) 2/ γ ∈ [ 0 , 1 ] . Hence ∥ x t ∥ ≤ max { ∥ x r ∥ , ∥ z r ∥ } \lVert x_t\rVert\le\max\{\lVert x_r\rVert,\lVert z_r\rVert\} ∥ x t ∥ ≤ max {∥ x r ∥ , ∥ z r ∥} , so the previously implicit between-event constant is exactly one.
Step 2: stopped jump estimate. At a jump, the two state increments are linear in g t g_t g t , with coefficients 1 / L 1/L 1/ L and c t ≤ γ θ 2 T / ( 2 L ) c_t\le\gamma\theta^2T/(2L) c t ≤ γ θ 2 T / ( 2 L ) . The elementary square inequality therefore gives a constant C = C ( L , γ , θ , T ) C=C(L,\gamma,\theta,T) C = C ( L , γ , θ , T ) such that, pathwise,
M T ∧ τ R ≤ C M 0 + C ∫ 0 T ∧ τ R ( 1 + M t − + ∥ g t ∥ 2 ) d n t . M_{T\wedge\tau_R}\le CM_0+C\int_0^{T\wedge\tau_R}(1+M_{t-}+\lVert g_t\rVert^2)\,dn_t. M T ∧ τ R ≤ C M 0 + C ∫ 0 T ∧ τ R ( 1 + M t − + ∥ g t ∥ 2 ) d n t .
The marked compensator identity and (37) then give
E M T ∧ τ R ≤ C M 0 + C ∫ 0 T [ ( 1 + a 0 ) + ( 1 + a 1 ) E M t ∧ τ R ] d t . \mathbb{E}M_{T\wedge\tau_R}\le CM_0+C\int_0^T\left[(1+a_0)+(1+a_1)\mathbb{E}M_{t\wedge\tau_R}\right]\,dt. E M T ∧ τ R ≤ C M 0 + C ∫ 0 T [ ( 1 + a 0 ) + ( 1 + a 1 ) E M t ∧ τ R ] d t .
Gronwall gives a bound independent of R R R , now with constants depending also on a 0 a_0 a 0 , a 1 a_1 a 1 , and Fatou yields the claim. Global smoothness and the existence of the fixed minimizer give the corresponding linear gradient-growth bounds; the oracle bias and centered variance are controlled by its conditional second moment.
Localization and exit times
For local smoothness or local quasar geometry on a region B \mathcal{B} B , let τ B \tau_{\mathcal{B}} τ B be the first time at which a pre-jump query, a post-jump state, or a line segment used by the smoothness model exits B \mathcal{B} B . The same calculation proves the estimate only up to T ∧ τ B T\wedge\tau_{\mathcal{B}} T ∧ τ B . A global conclusion then requires a separate invariance proof or an exit-probability bound.
Network and communication lemmas
The spectral estimate proves Lemma 4.7 , the affine heterogeneity bound closes Corollary 4.9 , and a Poisson tail bound supports the work interpretation in § 5 .
Chebyshev spectral estimate
Proof of Lemma 4.7 . The polynomial is controlled on the disagreement spectrum. The resulting spectral estimate gives the Frobenius row-noise factor.
Step 1: spectral contraction. When χ = 1 \chi= 1 χ = 1 , all nonzero Laplacian eigenvalues coincide and the degree-one polynomial 1 − λ / λ 2 1 - \lambda/\lambda_2 1 − λ / λ 2 gives exact averaging. Assume χ > 1 \chi> 1 χ > 1 . The normalized polynomial equals one at the consensus eigenvalue. For every λ ∈ [ λ 2 , λ m ] \lambda\in[\lambda_2,\lambda_m] λ ∈ [ λ 2 , λ m ] , its numerator argument lies in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , so the absolute numerator is at most one. Hence
∥ W q − J ∥ 2 ≤ 1 cosh ( q arcosh ( ( χ + 1 ) / ( χ − 1 ) ) ) . \lVert W_q - J\rVert_2 \le\frac{1}{\cosh(q\operatorname{arcosh}((\chi+1)/(\chi-1)))}. ∥ W q − J ∥ 2 ≤ cosh ( q arcosh (( χ + 1 ) / ( χ − 1 ))) 1 .
Now 1 / cosh u ≤ 2 e − u 1/\cosh u \le2e^{-u} 1/ cosh u ≤ 2 e − u and arcosh ( ( χ + 1 ) / ( χ − 1 ) ) = log ( ( χ + 1 ) / ( χ − 1 ) ) ≥ 2 / ( χ + 1 ) \operatorname{arcosh}((\chi+1)/(\chi-1)) = \log((\sqrt{\chi}+1)/(\sqrt{\chi}-1)) \ge2/(\sqrt{\chi}+1) arcosh (( χ + 1 ) / ( χ − 1 )) = log (( χ + 1 ) / ( χ − 1 )) ≥ 2/ ( χ + 1 ) , which gives (28).
Step 2: Frobenius factor. Finally, mean preservation implies W q J = J W q = J W_qJ = JW_q = J W q J = J W q = J and Frobenius orthogonality of J J J and W q − J W_q-J W q − J ; therefore m − 1 ∥ W q ∥ F 2 = m − 1 + m − 1 ∥ W q − J ∥ F 2 ≤ m − 1 + ∥ W q − J ∥ 2 2 m^{-1}\lVert W_q\rVert_F^2 = m^{-1} + m^{-1}\lVert W_q-J\rVert_F^2 \le m^{-1}+\lVert W_q-J\rVert_2^2 m − 1 ∥ W q ∥ F 2 = m − 1 + m − 1 ∥ W q − J ∥ F 2 ≤ m − 1 + ∥ W q − J ∥ 2 2 .
The argument concerns a fixed symmetric graph or a certified common spectral interval. It is not a substitute for controlling noncommuting products on an arbitrary changing graph.
Affine heterogeneity from primitive local regularity
Suppose ∥ [ ∇ f i ( x ) − ∇ F ( x ) ] − [ ∇ f i ( x ⋆ ) − ∇ F ( x ⋆ ) ] ∥ ≤ δ i ∥ x − x ⋆ ∥ \lVert[\nabla f_i(x)-\nabla F(x)]-[\nabla f_i(x^\star)-\nabla F(x^\star)]\rVert\le\delta_i\lVert x-x^\star\rVert ∥[ ∇ f i ( x ) − ∇ F ( x )] − [ ∇ f i ( x ⋆ ) − ∇ F ( x ⋆ )]∥ ≤ δ i ∥ x − x ⋆ ∥ and let δ ˉ 2 = m − 1 ∑ i δ i 2 \bar{\delta}^2=m^{-1}\sum_i\delta_i^2 δ ˉ 2 = m − 1 ∑ i δ i 2 . Writing d i ( x ) = ∇ f i ( x ) − ∇ F ( x ) d_i(x)=\nabla f_i(x)-\nabla F(x) d i ( x ) = ∇ f i ( x ) − ∇ F ( x ) gives ∥ d i ( x ) ∥ 2 ≤ 2 ∥ d i ( x ⋆ ) ∥ 2 + 2 δ i 2 ∥ x − x ⋆ ∥ 2 \lVert d_i(x)\rVert^2\le2\lVert d_i(x^\star)\rVert^2+2\delta_i^2\lVert x-x^\star\rVert^2 ∥ d i ( x ) ∥ 2 ≤ 2 ∥ d i ( x ⋆ ) ∥ 2 + 2 δ i 2 ∥ x − x ⋆ ∥ 2 . Averaging and using quadratic growth yields
ζ 2 ( x ) ≤ 2 ζ 2 ( x ⋆ ) + 4 δ ˉ 2 μ [ F ( x ) − F ( x ⋆ ) ] . \zeta^2(x)\le2\zeta^2(x^\star)+\frac{4\bar{\delta}^2}{\mu}[F(x)-F(x^\star)]. ζ 2 ( x ) ≤ 2 ζ 2 ( x ⋆ ) + μ 4 δ ˉ 2 [ F ( x ) − F ( x ⋆ )] .
which is the certificate quoted after Corollary 4.9 .
Actual versus expected event work
The event count n T n_T n T is Poisson with mean T T T , so the standard Bernstein bound gives ∣ n T − T ∣ ≤ 2 T log ( 2 / δ ) + 2 3 log ( 2 / δ ) \lvert n_T-T\rvert\le\sqrt{2T\log(2/\delta)}+\frac{2}{3}\log(2/\delta) ∣ n T − T ∣ ≤ 2 T log ( 2/ δ ) + 3 2 log ( 2/ δ ) with probability at least 1 − δ 1-\delta 1 − δ : the deterministic horizon is the expected work, and the realized work fluctuates by order T \sqrt{T} T .
Proof of the projected bound
The reserve left by θ < 1 \theta<1 θ < 1 is spent on the bias, which is why no gradient integral remains on the left of (21).
Proof of Theorem 4.3 (b). Step 1: localized drift. Projection is nonexpansive relative to x ⋆ ∈ Q x^\star\in\mathcal{Q} x ⋆ ∈ Q , while z t ∈ Q z_t\in\mathcal{Q} z t ∈ Q implies ∣ ⟨ z t − x ⋆ , e t ⟩ ∣ ≤ R Q ∥ e t ∥ \lvert\langle z_t-x^\star,e_t\rangle\rvert\le R_{\mathcal{Q}}\lVert e_t\rVert ∣⟨ z t − x ⋆ , e t ⟩∣ ≤ R Q ∥ e t ∥ . Lemma 4.1 therefore applies with this linear contribution.
Step 2: reserve accounting. After inserting the multiplicative centered variance, the coefficient of ∥ ∇ F ( x t − ) ∥ 2 \lVert\nabla F(x_{t-})\rVert^2 ∥ ∇ F ( x t − ) ∥ 2 is − ( 1 − θ 2 ) / 2 + V θ η -(1-\theta^2)/2+V\theta\eta − ( 1 − θ 2 ) /2 + V θ η . Completing the square gives
− ( 1 − θ 2 2 − V θ η ) ∥ ∇ F ∥ 2 + θ 2 ⟨ ∇ F , e t ⟩ ≤ θ 4 ∥ e t ∥ 2 2 ( 1 − θ 2 − 2 V θ η ) . -\left(\frac{1-\theta^2}{2}-V\theta\eta\right)\lVert\nabla F\rVert^2+\theta^2\langle\nabla F,e_t\rangle\le\frac{\theta^4\lVert e_t\rVert^2}{2(1-\theta^2-2V\theta\eta)}. − ( 2 1 − θ 2 − V θ η ) ∥ ∇ F ∥ 2 + θ 2 ⟨ ∇ F , e t ⟩ ≤ 2 ( 1 − θ 2 − 2 V θ η ) θ 4 ∥ e t ∥ 2 .
This uses all remaining gradient dissipation; hence no gradient-norm integral appears on the left of (21).
Step 3: compensation and normalization. Apply the stopped compensator identity and remove the stopping exactly as in the proof of Theorem 4.3 (a), with Fatou’s lemma for Φ T ∧ τ R \Phi_{T\wedge\tau_R} Φ T ∧ τ R and dominated convergence for the integrals. Finally use A T − 1 ∫ 0 T c t d t = 1 / γ A_T^{-1}\int_0^T c_t\,\mathrm{d}t=1/\gamma A T − 1 ∫ 0 T c t d t = 1/ γ and A T − 1 ∫ 0 T A t d t = T / 3 A_T^{-1}\int_0^T A_t\,\mathrm{d}t=T/3 A T − 1 ∫ 0 T A t d t = T /3 to obtain (21).
Algorithm 7 Restarted exact-snapshot CQA-Net with variance reduction
Require: stages S S S , stage horizon T s t T_{\mathrm{st}} T st , inner depth q q q , batch b b b , common x ( 0 ) x^{(0)} x ( 0 )
for s = 0 , 1 , … , S − 1 s=0,1,\ldots,S-1 s = 0 , 1 , … , S − 1 do
set the common snapshot y ( s ) ← x ( s ) y^{(s)}\leftarrow x^{(s)} y ( s ) ← x ( s ) ; every node computes ∇ f i ( y ( s ) ) \nabla f_i(y^{(s)}) ∇ f i ( y ( s ) )
exactly reduce and broadcast ∇ F ( y ( s ) ) \nabla F(y^{(s)}) ∇ F ( y ( s ) )
run CQA-Net from x 0 = z 0 = y ( s ) x_0=z_0=y^{(s)} x 0 = z 0 = y ( s ) for horizon T s t T_{\mathrm{st}} T st with rows (38)
set x ( s + 1 ) x^{(s+1)} x ( s + 1 ) to the common stage output
end for
return x ( S ) x^{(S)} x ( S )
Variance reduction for shared-landscape finite sums
This appendix proves the statements summarized in Remark 4.10. The additive variance in Theorem 4.8 grows with the horizon. Quadratic growth permits fixed-length restarts, and an exact SVRG snapshot turns the remaining stochastic error into a term proportional to the current and snapshot gaps.
Finite sums and the control-variate row. Let f i ( x ) = n i − 1 ∑ j = 1 n i f i j ( x ) f_i(x)=n_i^{-1}\sum_{j=1}^{n_i}f_{ij}(x) f i ( x ) = n i − 1 ∑ j = 1 n i f ij ( x ) and N Σ : = ∑ i = 1 m n i N_{\Sigma}:=\sum_{i=1}^{m}n_i N Σ := ∑ i = 1 m n i . With a snapshot y y y and the exact network gradient ∇ F ( y ) \nabla F(y) ∇ F ( y ) , node i i i uses
u ^ i ( x ; y ) = 1 b ∑ r = 1 b [ ∇ f i , j i , r ( x ) − ∇ f i , j i , r ( y ) ] + ∇ F ( y ) . (38) \widehat{u}_i(x;y)=\frac{1}{b}\sum_{r=1}^{b}\left[\nabla f_{i,j_{i,r}}(x)-\nabla f_{i,j_{i,r}}(y)\right]+\nabla F(y). \tag*{(38)} u i ( x ; y ) = b 1 r = 1 ∑ b [ ∇ f i , j i , r ( x ) − ∇ f i , j i , r ( y ) ] + ∇ F ( y ) . (38)
Conditionally on the stage-start sigma-field and the pre-event history, the indices j i , r j_{i,r} j i , r are i.i.d. uniform on { 1 , … , n i } \{1,\ldots,n_i\} { 1 , … , n i } across r r r , the same index is used in both gradients of each difference, and the batches are conditionally independent across nodes and independent of the fresh clock and root. Cross-node independence may be replaced by the direct block-trace domination (26) . An individual row mean need not equal ∇ f i ( x ) \nabla f_i(x) ∇ f i ( x ) ; only their average must equal ∇ F ( x ) \nabla F(x) ∇ F ( x ) , which Lemma 4.6 allows.
Stage horizon and similarity. Let F s \mathcal{F}_s F s be the sigma-field at the beginning of stage s s s , after the exact snapshot has been computed and before fresh inner clocks, component samples, and roots are generated. Exact-gradient acceleration and quadratic growth give the deterministic stage factor 4 L / ( μ γ 2 θ T 2 ) 4L/(\mu\gamma^2\theta T^2) 4 L / ( μ γ 2 θ T 2 ) , which equals 1 / 4 1/4 1/4 for
T s t = 4 γ θ L μ . (39) T_{\mathrm{st}}=\frac{4}{\gamma\theta}\sqrt{\frac{L}{\mu}}. \tag*{(39)} T st = γ θ 4 μ L . (39)
For comparison, quasar-convexity and quadratic growth imply ∥ ∇ F ( x ) ∥ 2 ≥ γ 2 μ [ F ( x ) − F ( x ⋆ ) ] / 2 \lVert\nabla F(x)\rVert^2\ge\gamma^2\mu[F(x)-F(x^\star)]/2 ∥ ∇ F ( x ) ∥ 2 ≥ γ 2 μ [ F ( x ) − F ( x ⋆ )] /2 , so gradient descent with step 1 / L 1/L 1/ L needs O ( L / ( γ 2 μ ) log ( 1 / ε ) ) O(L/(\gamma^2\mu)\log(1/\varepsilon)) O ( L / ( γ 2 μ ) log ( 1/ ε )) iterations, whereas restarted exact-gradient CQA needs O ( L / μ / ( γ θ ) log ( 1 / ε ) ) O(\sqrt{L/\mu}/(\gamma\theta)\log(1/\varepsilon)) O ( L / μ / ( γ θ ) log ( 1/ ε )) expected events. The control variate is analyzed under two global gap-relative similarity conditions with constants β , Λ c o m p ≥ 0 \beta,\Lambda_{\mathrm{comp}}\ge0 β , Λ comp ≥ 0 : for all x , y ∈ R d x,y\in\mathbb{R}^d x , y ∈ R d and every node i i i ,
1 m ∑ i = 1 m ∥ [ ∇ f i ( x ) − ∇ f i ( y ) ] − [ ∇ F ( x ) − ∇ F ( y ) ] ∥ 2 ≤ 2 β ( F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ) . (40) \frac{1}{m}\sum_{i=1}^{m}\left\lVert[\nabla f_i(x)-\nabla f_i(y)]-[\nabla F(x)-\nabla F(y)]\right\rVert^2
\le2\beta\left(F(x)-F(x^\star)+F(y)-F(x^\star)\right). \tag*{(40)} m 1 i = 1 ∑ m ∥ [ ∇ f i ( x ) − ∇ f i ( y )] − [ ∇ F ( x ) − ∇ F ( y )] ∥ 2 ≤ 2 β ( F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ) . (40)
E j ∥ [ ∇ f i j ( x ) − ∇ f i j ( y ) ] − [ ∇ f i ( x ) − ∇ f i ( y ) ] ∥ 2 ≤ 2 Λ c o m p ( F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ) . (41) \mathbb{E}_j\left\lVert[\nabla f_{ij}(x)-\nabla f_{ij}(y)]-[\nabla f_i(x)-\nabla f_i(y)]\right\rVert^2
\le2\Lambda_{\mathrm{comp}}\left(F(x)-F(x^\star)+F(y)-F(x^\star)\right). \tag*{(41)} E j ∥ [ ∇ f ij ( x ) − ∇ f ij ( y )] − [ ∇ f i ( x ) − ∇ f i ( y )] ∥ 2 ≤ 2 Λ comp ( F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ) . (41)
Lemma D.1 (Stage contraction under relative variance). Suppose F F F is L L L -smooth, γ \gamma γ -quasar-convex, and satisfies quadratic growth with constant μ \mu μ . Conditionally on F s \mathcal{F}_s F s , let the inner-stage oracle be unbiased and satisfy, for F s \mathcal{F}_s F s -measurable 0 ≤ a s , c s < ∞ 0\le a_s,c_s<\infty 0 ≤ a s , c s < ∞ , ζ t 2 ≤ a s ( F ( x t ) − F ( x ⋆ ) ) + c s ( F ( x ( s ) ) − F ( x ⋆ ) ) \zeta_t^2\le a_s(F(x_t)-F(x^\star))+c_s(F(x^{(s)})-F(x^\star)) ζ t 2 ≤ a s ( F ( x t ) − F ( x ⋆ )) + c s ( F ( x ( s ) ) − F ( x ⋆ )) . Then, for a stage of length T > 0 T>0 T > 0 ,
E [ F ( x ( s + 1 ) ) − F ( x ⋆ ) ∣ F s ] ≤ e V θ a s T / L [ 4 L μ γ 2 θ T 2 + V θ c s T 3 L ] ( F ( x ( s ) ) − F ( x ⋆ ) ) . (42) \mathbb{E}\left[F(x^{(s+1)})-F(x^\star)\mid\mathcal{F}_s\right]
\le e^{V_\theta a_sT/L}\left[\frac{4L}{\mu\gamma^2\theta T^2}+\frac{V_\theta c_sT}{3L}\right]\left(F(x^{(s)})-F(x^\star)\right). \tag*{(42)} E [ F ( x ( s + 1 ) ) − F ( x ⋆ ) ∣ F s ] ≤ e V θ a s T / L [ μ γ 2 θ T 2 4 L + 3 L V θ c s T ] ( F ( x ( s ) ) − F ( x ⋆ ) ) . (42)
Proof. Condition on F s \mathcal{F}_s F s and reset inner time to zero. The stopped compensator inequality obtained from Lemma 4.1, after dropping nonpositive terms and using A t [ F ( x t ) − F ( x ⋆ ) ] ≤ Φ t A_t[F(x_t)-F(x^\star)]\le\Phi_t A t [ F ( x t ) − F ( x ⋆ )] ≤ Φ t , reads
E [ Φ t ∧ τ R ∣ F s ] ≤ Φ 0 + V θ a s L ∫ 0 t E [ Φ r ∧ τ R ∣ F s ] d r + V θ c s L ( F ( x ( s ) ) − F ( x ⋆ ) ) ∫ 0 t A r d r . \mathbb{E}[\Phi_{t\wedge\tau_R}\mid\mathcal{F}_s]\le\Phi_0+\frac{V_\theta a_s}{L}\int_0^t\mathbb{E}[\Phi_{r\wedge\tau_R}\mid\mathcal{F}_s]\,dr+\frac{V_\theta c_s}{L}\left(F(x^{(s)})-F(x^\star)\right)\int_0^t A_r\,dr. E [ Φ t ∧ τ R ∣ F s ] ≤ Φ 0 + L V θ a s ∫ 0 t E [ Φ r ∧ τ R ∣ F s ] d r + L V θ c s ( F ( x ( s ) ) − F ( x ⋆ ) ) ∫ 0 t A r d r .
Because ∇ F ( x ⋆ ) = 0 \nabla F(x^\star)=0 ∇ F ( x ⋆ ) = 0 , smoothness gives ∥ ∇ F ( x ) ∥ ≤ L ∥ x − x ⋆ ∥ \|\nabla F(x)\|\le L\|x-x^\star\| ∥∇ F ( x ) ∥ ≤ L ∥ x − x ⋆ ∥ and F ( x ) − F ( x ⋆ ) ≤ L ∥ x − x ⋆ ∥ 2 / 2 F(x)-F(x^\star)\le L\|x-x^\star\|^2/2 F ( x ) − F ( x ⋆ ) ≤ L ∥ x − x ⋆ ∥ 2 /2 ; with unbiasedness and the relative variance bound this is a conditional linear second-moment bound, so Lemma A.2 supplies the finite-horizon integrability and nonexplosion. Apply Lemma 4.2(i), let R → ∞ R\to\infty R → ∞ as in Theorem 4.3 , and use Φ 0 = ∥ x ( s ) − x ⋆ ∥ 2 / 2 ≤ [ F ( x ( s ) ) − F ( x ⋆ ) ] / μ \Phi_0=\|x^{(s)}-x^\star\|^2/2\le[F(x^{(s)})-F(x^\star)]/\mu Φ 0 = ∥ x ( s ) − x ⋆ ∥ 2 /2 ≤ [ F ( x ( s ) ) − F ( x ⋆ )] / μ , Φ T ≥ A T [ F ( x ( s + 1 ) ) − F ( x ⋆ ) ] \Phi_T\ge A_T[F(x^{(s+1)})-F(x^\star)] Φ T ≥ A T [ F ( x ( s + 1 ) ) − F ( x ⋆ )] , and A T − 1 ∫ 0 T A t d t = T / 3 A_T^{-1}\int_0^T A_t\,\mathrm{d}t=T/3 A T − 1 ∫ 0 T A t d t = T /3 . Division by A T A_T A T gives (42) .
Lemma D.2 (Similarity-aware network oracle). Under (40) and (41) , let x , y x,y x , y be predictable and W q W_q W q mean preserving, and assume conditional cross-node independence of the mini-batch differences or the corresponding block-trace domination. The uniform-row estimate built from (38) is conditionally unbiased for ∇ F ( x ) \nabla F(x) ∇ F ( x ) and satisfies
E [ ∥ g ^ ( k ) − ∇ F ( x ) ∥ 2 ∣ F τ k − ] ≤ 2 K q , b ( F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ) , (43) \mathbb{E}\left[\|\widehat{g}^{(k)}-\nabla F(x)\|^2\mid\mathcal{F}_{\tau_k-}\right]\le2K_{q,b}\left(F(x)-F(x^\star)+F(y)-F(x^\star)\right), \tag*{(43)} E [ ∥ g ( k ) − ∇ F ( x ) ∥ 2 ∣ F τ k − ] ≤ 2 K q , b ( F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ) , (43) where K q , b = β ∥ W q − J ∥ 2 2 + ( Λ c o m p / b ) m − 1 ∥ W q ∥ F 2 K_{q,b}=\beta\|W_q-J\|_2^2+(\Lambda_{\mathrm{comp}}/b)m^{-1}\|W_q\|_{\mathrm{F}}^2 K q , b = β ∥ W q − J ∥ 2 2 + ( Λ comp / b ) m − 1 ∥ W q ∥ F 2 .
Proof. Condition on F τ k − \mathcal{F}_{\tau_k-} F τ k − . The mean of row i i i is ∇ f i ( x ) − ∇ f i ( y ) + ∇ F ( y ) \nabla f_i(x)-\nabla f_i(y)+\nabla F(y) ∇ f i ( x ) − ∇ f i ( y ) + ∇ F ( y ) , whose network average is ∇ F ( x ) \nabla F(x) ∇ F ( x ) , so Lemma 4.6 (ii) with a uniform root and ω ≡ 1 \omega\equiv1 ω ≡ 1 gives unbiasedness and the variance bound B ( k ) B^{(k)} B ( k ) . Its first term involves the centered mean rows [ ∇ f i ( x ) − ∇ f i ( y ) ] − [ ∇ F ( x ) − ∇ F ( y ) ] [\nabla f_i(x)-\nabla f_i(y)]-[\nabla F(x)-\nabla F(y)] [ ∇ f i ( x ) − ∇ f i ( y )] − [ ∇ F ( x ) − ∇ F ( y )] , and (40) bounds it by 2 β ∥ W q − J ∥ 2 2 2\beta\|W_q-J\|_2^2 2 β ∥ W q − J ∥ 2 2 times the sum of the two gaps. In the noise term the same component is used at x x x and y y y , so (41) bounds one centered difference, averaging b b b independent copies divides its variance by b b b , and the block-trace condition contributes the factor m − 1 ∥ W q ∥ F 2 m^{-1}\|W_q\|_{\mathrm{F}}^2 m − 1 ∥ W q ∥ F 2 .
Theorem D.3 (Exact-snapshot restarted variance reduction). Suppose F F F is L L L -smooth, γ \gamma γ -quasar-convex with respect to x ⋆ x^\star x ⋆ , and satisfies quadratic growth with constant μ \mu μ relative to the same minimizer. Assume (40) , (41) , the sampling conditions stated after (38) , and an exact snapshot all-reduce on every stage. Let θ ∈ ( 0 , 1 ] \theta\in(0,1] θ ∈ ( 0 , 1 ] and use T s t T_{\mathrm{st}} T st from (39) . If
K q , b ≤ K ⋆ : = L log ( 4 / 3 ) 2 V θ T s t = γ θ log ( 4 / 3 ) 8 V θ L μ , (44) K_{q,b}\le K^\star:=\frac{L\log(4/3)}{2V_\theta T_{\mathrm{st}}}=\frac{\gamma\theta\log(4/3)}{8V_\theta}\sqrt{L\mu}, \tag*{(44)} K q , b ≤ K ⋆ := 2 V θ T st L log ( 4/3 ) = 8 V θ γ θ log ( 4/3 ) Lμ , (44) then every stage of Algorithm 7 contracts the conditional expected gap by r s t = 4 3 ( 1 4 + 1 3 log 4 3 ) ≈ 0.4612 < 1 2 r_{\mathrm{st}}=\frac{4}{3}\left(\frac{1}{4}+\frac{1}{3}\log\frac{4}{3}\right)\approx0.4612<\frac{1}{2} r st = 3 4 ( 4 1 + 3 1 log 3 4 ) ≈ 0.4612 < 2 1 , and
E [ F ( x ( S ) ) − F ( x ⋆ ) ] ≤ r s t S ( F ( x ( 0 ) ) − F ( x ⋆ ) ) , (45) \mathbb{E}\left[F(x^{(S)})-F(x^\star)\right]\le r_{\mathrm{st}}^S\left(F(x^{(0)})-F(x^\star)\right), \tag*{(45)} E [ F ( x ( S ) ) − F ( x ⋆ ) ] ≤ r st S ( F ( x ( 0 ) ) − F ( x ⋆ ) ) , (45) so S = ⌈ log ( [ F ( x ( 0 ) ) − F ( x ⋆ ) ] / ε ) / log ( 1 / r s t ) ⌉ S=\left\lceil\log([F(x^{(0)})-F(x^\star)]/\varepsilon)/\log(1/r_{\mathrm{st}})\right\rceil S = ⌈ log ([ F ( x ( 0 ) ) − F ( x ⋆ )] / ε ) / log ( 1/ r st ) ⌉ stages suffice for accuracy ε \varepsilon ε . On a fixed graph and for q > 0 q>0 q > 0 , the expected per-stage costs are at most T s t T_{\mathrm{st}} T st events, 2 D + T s t ( q + D ) 2D+T_{\mathrm{st}}(q+D) 2 D + T st ( q + D ) critical-path rounds, n i + 2 b T s t n_i+2bT_{\mathrm{st}} n i + 2 b T st component gradients at node i i i , N Σ + 2 m b T s t N_\Sigma+2mbT_{\mathrm{st}} N Σ + 2 mb T st in aggregate, and 2 ( m − 1 ) + T s t ( 2 q ∣ E ∣ + M b r ) 2(m-1)+T_{\mathrm{st}}(2q|E|+M_{\mathrm{br}}) 2 ( m − 1 ) + T st ( 2 q ∣ E ∣ + M br ) transmitted vectors; for q = 0 q=0 q = 0 , root-first sampling gives n i + 2 b T s t / m n_i+2bT_{\mathrm{st}}/m n i + 2 b T st / m component gradients at node i i i and N Σ + 2 b T s t N_\Sigma+2bT_{\mathrm{st}} N Σ + 2 b T st in aggregate.
Proof. Fix s s s and condition on F s \mathcal{F}_s F s ; the exact snapshot makes x ( s ) x^{(s)} x ( s ) and ∇ F ( x ( s ) ) \nabla F(x^{(s)}) ∇ F ( x ( s ) ) fixed. Lemma D.2 with y = x ( s ) y=x^{(s)} y = x ( s ) verifies Lemma D.1 with a s = c s = 2 K q , b a_s=c_s=2K_{q,b} a s = c s = 2 K q , b . At T = T s t T=T_{\mathrm{st}} T = T st the deterministic coefficient in (42) is 1 / 4 1/4 1/4 , and with u = 2 V θ K q , b T s t / L u=2V_\theta K_{q,b}T_{\mathrm{st}}/L u = 2 V θ K q , b T st / L the stage factor is e u ( 1 / 4 + u / 3 ) e^u(1/4+u/3) e u ( 1/4 + u /3 ) . It increases in u ≥ 0 u\ge0 u ≥ 0 , and (44) gives u ≤ log ( 4 / 3 ) u\le\log(4/3) u ≤ log ( 4/3 ) , so the factor is at most r s t r_{\mathrm{st}} r st ; log ( 1 + x ) < x \log(1+x)<x log ( 1 + x ) < x also gives r s t < 13 / 27 < 1 / 2 r_{\mathrm{st}}<13/27<1/2 r st < 13/27 < 1/2 . The tower property yields (45) , and solving r s t S [ F ( x ( 0 ) ) − F ( x ⋆ ) ] ≤ ε r_{\mathrm{st}}^S[F(x^{(0)})-F(x^\star)]\le\varepsilon r st S [ F ( x ( 0 ) ) − F ( x ⋆ )] ≤ ε gives the stage count. For the costs, each stage begins with one exact local full pass, one exact reduction, and one broadcast. For q > 0 q>0 q > 0 every event evaluates the same sampled components at the current point and at the snapshot on every node (2 b 2b 2 b evaluations per node) and uses q q q mixing rounds and one broadcast; for q = 0 q=0 q = 0 only the root, revealed first, evaluates the two batches, and conditional uniformity spreads its expected work equally over the nodes.
The similarity conditions are strong. A distance-based certificate, for instance a uniform bound δ 2 \delta^2 δ 2 on m − 1 ∑ i ∥ ∇ 2 f i ( u ) − ∇ 2 F ( u ) ∥ 2 2 m^{-1}\sum_i\|\nabla^2 f_i(u)-\nabla^2 F(u)\|_2^2 m − 1 ∑ i ∥ ∇ 2 f i ( u ) − ∇ 2 F ( u ) ∥ 2 2 , gives β = 2 δ 2 / μ \beta=2\delta^2/\mu β = 2 δ 2 / μ through ∥ x − y ∥ 2 ≤ 4 [ F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ] / μ \|x-y\|^2\le4[F(x)-F(x^\star)+F(y)-F(x^\star)]/\mu ∥ x − y ∥ 2 ≤ 4 [ F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ )] / μ , and for a generic deviation δ 2 ≲ L 2 \delta^2\lesssim L^2 δ 2 ≲ L 2 the threshold (44) then requires ∥ W q − J ∥ 2 2 ≲ ( μ / L ) 3 \|W_q-J\|_2^2\lesssim(\mu/L)^3 ∥ W q − J ∥ 2 2 ≲ ( μ / L ) 3 up to constants; on unstructured nonlinear data such certificates can be vacuous. The shared-landscape class avoids the factor 1 / μ 1/\mu 1/ μ .
Lemma D.4 (Shared-landscape certificate). Let F F F be L L L -smooth and attain its global minimum at x ⋆ x^\star x ⋆ , and suppose f i j ( x ) = a i j F ( x ) + ⟨ c i j , x ⟩ + d i j f_{ij}(x)=a_{ij}F(x)+\langle c_{ij},x\rangle+d_{ij} f ij ( x ) = a ij F ( x ) + ⟨ c ij , x ⟩ + d ij . Write a i = n i − 1 ∑ j a i j a_i=n_i^{-1}\sum_j a_{ij} a i = n i − 1 ∑ j a ij and assume m − 1 ∑ i a i = 1 m^{-1}\sum_i a_i=1 m − 1 ∑ i a i = 1 and that the averaged affine gradient vanishes. Then (40) and (41) hold with
β = 2 L v n o d e , Λ c o m p = 2 L v c o m p , (46) \beta=2Lv_{\mathrm{node}},\qquad\Lambda_{\mathrm{comp}}=2Lv_{\mathrm{comp}}, \tag*{(46)} β = 2 L v node , Λ comp = 2 L v comp , (46) where v n o d e : = m − 1 ∑ i ( a i − 1 ) 2 v_{\mathrm{node}}:=m^{-1}\sum_i(a_i-1)^2 v node := m − 1 ∑ i ( a i − 1 ) 2 and v c o m p : = max i n i − 1 ∑ j ( a i j − a i ) 2 v_{\mathrm{comp}}:=\max_i n_i^{-1}\sum_j(a_{ij}-a_i)^2 v comp := max i n i − 1 ∑ j ( a ij − a i ) 2 .
Proof. Affine terms cancel in gradient differences, so the node- and component-level differences are ( a i − 1 ) [ ∇ F ( x ) − ∇ F ( y ) ] (a_i-1)[\nabla F(x)-\nabla F(y)] ( a i − 1 ) [ ∇ F ( x ) − ∇ F ( y )] and ( a i j − a i ) [ ∇ F ( x ) − ∇ F ( y ) ] (a_{ij}-a_i)[\nabla F(x)-\nabla F(y)] ( a ij − a i ) [ ∇ F ( x ) − ∇ F ( y )] . Since x ⋆ x^\star x ⋆ is a global minimizer, the descent lemma gives ∥ ∇ F ( u ) ∥ 2 ≤ 2 L [ F ( u ) − F ( x ⋆ ) ] \|\nabla F(u)\|^2\le2L[F(u)-F(x^\star)] ∥∇ F ( u ) ∥ 2 ≤ 2 L [ F ( u ) − F ( x ⋆ )] , hence ∥ ∇ F ( x ) − ∇ F ( y ) ∥ 2 ≤ 4 L [ F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ ) ] \|\nabla F(x)-\nabla F(y)\|^2\le4L[F(x)-F(x^\star)+F(y)-F(x^\star)] ∥∇ F ( x ) − ∇ F ( y ) ∥ 2 ≤ 4 L [ F ( x ) − F ( x ⋆ ) + F ( y ) − F ( x ⋆ )] , and comparing with the factor 2 2 2 in (40) and (41) gives (46) .
Corollary D.5 (Shared-landscape finite sums). Under the assumptions of Theorem D.3 with components of the form in Lemma D.4, the geometric rate (45) holds whenever
v n o d e ∥ W q − J ∥ 2 2 + v c o m p b m − 1 ∥ W q ∥ F 2 ≤ γ θ log ( 4 / 3 ) 16 V θ μ L . (47) v_{\mathrm{node}}\lVert W_q-J\rVert_2^2+\frac{v_{\mathrm{comp}}}{b}m^{-1}\lVert W_q\rVert_{\mathrm{F}}^2\leq\frac{\gamma\theta\log(4/3)}{16V_\theta}\sqrt{\frac{\mu}{L}}. \tag*{(47)} v node ∥ W q − J ∥ 2 2 + b v comp m − 1 ∥ W q ∥ F 2 ≤ 16 V θ γ θ log ( 4/3 ) L μ . (47) With the Chebyshev protocol of Lemma 4.7 , the inner depth q q q and the batch b b b that satisfy (47) do not depend on the target accuracy.
Proof. Insert (46) into (43) : K q , b = 2 L [ v n o d e ∥ W q − J ∥ 2 2 + ( v c o m p / b ) m − 1 ∥ W q ∥ F 2 ] K_{q,b}=2L[v_{\mathrm{node}}\lVert W_q-J\rVert_2^2+(v_{\mathrm{comp}}/b)m^{-1}\lVert W_q\rVert_{\mathrm{F}}^2] K q , b = 2 L [ v node ∥ W q − J ∥ 2 2 + ( v comp / b ) m − 1 ∥ W q ∥ F 2 ] , and (44) becomes (47) . Both sides of (47) are independent of ε \varepsilon ε , and Lemma 4.7 makes ∥ W q − J ∥ 2 2 \lVert W_q-J\rVert_2^2 ∥ W q − J ∥ 2 2 and m − 1 ∥ W q ∥ F 2 m^{-1}\lVert W_q\rVert_{\mathrm{F}}^2 m − 1 ∥ W q ∥ F 2 as small as needed by a fixed q q q .
Numerical check. Take the coordinatewise leaky-tanh landscape in dimension 12 with γ = 0.90 \gamma=0.90 γ = 0.90 , L = 0.19219 L=0.19219 L = 0.19219 , and μ = 0.016875 \mu=0.016875 μ = 0.016875 , and components f i j ( x ) = a i j F ( x ) + ⟨ c i j , x ⟩ f_{ij}(x)=a_{ij}F(x)+\langle c_{ij},x\rangle f ij ( x ) = a ij F ( x ) + ⟨ c ij , x ⟩ on the 16-node ring. The Hessian of F F F has the negative eigenvalue − 3.61 ⋅ 10 − 2 -3.61\cdot10^{-2} − 3.61 ⋅ 1 0 − 2 at an explicit probe. Lemma D.4 gives β = 2.3543 ⋅ 10 − 2 \beta=2.3543\cdot10^{-2} β = 2.3543 ⋅ 1 0 − 2 and Λ c o m p = 1.2012 ⋅ 10 − 2 \Lambda_{\mathrm{comp}}=1.2012\cdot10^{-2} Λ comp = 1.2012 ⋅ 1 0 − 2 ; with q = 7 q=7 q = 7 and b = 8 b=8 b = 8 , K 7 , 8 = 4.7307 ⋅ 10 − 4 < K ⋆ = 1.8431 ⋅ 10 − 3 K_{7,8}=4.7307\cdot10^{-4}<K^\star=1.8431\cdot10^{-3} K 7 , 8 = 4.7307 ⋅ 1 0 − 4 < K ⋆ = 1.8431 ⋅ 1 0 − 3 , so the threshold of Theorem D.3 holds before the run (K 7 , 8 / K ⋆ = 0.25667 K_{7,8}/K^\star=0.25667 K 7 , 8 / K ⋆ = 0.25667 ). Figure 5 shows geometric progress after including the repeated exact-snapshot cost: at stage eight the gaps are numerical zero (< 10 − 14 <10^{-14} < 1 0 − 14 ) for full gradients and for SVRG with b = 8 b=8 b = 8 , whereas the restarted plain b = 8 b=8 b = 8 method has gap 2.55 ⋅ 10 − 5 2.55\cdot10^{-5} 2.55 ⋅ 1 0 − 5 . The plain and SVRG stage costs are 1,920 and 5,760 component-gradient evaluations, the latter including the exact snapshot. On the unstructured nonlinear data of § 5 , by contrast, the generic Hessian certificate misses the threshold by the factor K / K ⋆ ≈ 2.44 ⋅ 10 4 K/K^\star\approx2.44\cdot10^4 K / K ⋆ ≈ 2.44 ⋅ 1 0 4 even at the largest tested batch.
Figure 5. Exact-snapshot variance reduction on the shared-landscape nonconvex finite sum: objective gap versus component-gradient evaluations, including the snapshot cost. Curves are sample means with pointwise normal-approximation bands.
Proofs of the quasar-convex model certificates
This appendix proves Proposition 2.4.
Strongly monotone links
Let u r = a r T x u_r=a_r^\mathsf{T}x u r = a r T x , v r = a r T x ⋆ v_r=a_r^\mathsf{T}x^\star v r = a r T x ⋆ , and d r = φ ( u r ) − φ ( v r ) d_r=\varphi(u_r)-\varphi(v_r) d r = φ ( u r ) − φ ( v r ) . The factors d r d_r d r and u r − v r u_r-v_r u r − v r have the same sign. Since ∣ d r ∣ ≤ M ∣ u r − v r ∣ |d_r|\leq M|u_r-v_r| ∣ d r ∣ ≤ M ∣ u r − v r ∣ and φ ′ ( u r ) ≥ α \varphi'(u_r)\geq\alpha φ ′ ( u r ) ≥ α ,
⟨ ∇ F ( x ) , x − x ⋆ ⟩ = 1 N ∑ r d r φ ′ ( u r ) ( u r − v r ) ≥ 2 α M F ( x ) . \langle\nabla F(x),x-x^\star\rangle=\frac{1}{N}\sum_r d_r\varphi'(u_r)(u_r-v_r)\geq\frac{2\alpha}{M}F(x). ⟨ ∇ F ( x ) , x − x ⋆ ⟩ = N 1 r ∑ d r φ ′ ( u r ) ( u r − v r ) ≥ M 2 α F ( x ) .
Together with F ( x ⋆ ) = 0 F(x^\star)=0 F ( x ⋆ ) = 0 and the convention γ ≤ 1 \gamma\leq1 γ ≤ 1 , this proves the quasar certificate. The lower derivative bound also gives ∣ d r ∣ ≥ α ∣ u r − v r ∣ |d_r|\geq\alpha|u_r-v_r| ∣ d r ∣ ≥ α ∣ u r − v r ∣ , and therefore
F ( x ) ≥ α 2 2 ( x − x ⋆ ) T ( 1 N ∑ r a r a r T ) ( x − x ⋆ ) . F(x)\geq\frac{\alpha^2}{2}(x-x^\star)^\mathsf{T}\left(\frac{1}{N}\sum_r a_ra_r^\mathsf{T}\right)(x-x^\star). F ( x ) ≥ 2 α 2 ( x − x ⋆ ) T ( N 1 r ∑ a r a r T ) ( x − x ⋆ ) .
which proves the quadratic-growth constant.
For an arbitrary data partition, use the scaled local objective
f i ( x ) = m 2 N ∑ r ∈ I i [ φ ( a r T x ) − φ ( a r T x ⋆ ) ] 2 . f_i(x)=\frac{m}{2N}\sum_{r\in I_i}\left[\varphi(a_r^\mathsf{T}x)-\varphi(a_r^\mathsf{T}x^\star)\right]^2. f i ( x ) = 2 N m r ∈ I i ∑ [ φ ( a r T x ) − φ ( a r T x ⋆ ) ] 2 .
Then m − 1 ∑ i f i = F m^{-1}\sum_i f_i=F m − 1 ∑ i f i = F even when the local sample counts are unequal. A noisy or misspecified response leaves a nonzero residual at x ⋆ x^\star x ⋆ and is not covered by this realizable certificate.
The leaky-tanh smoothness envelope
For α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] and φ α ( u ) = α u + ( 1 − α ) tanh u \varphi_\alpha(u)=\alpha u+(1-\alpha)\tanh u φ α ( u ) = α u + ( 1 − α ) tanh u , the Hessian is N − 1 ∑ r c r ( x ) a r a r T N^{-1}\sum_r c_r(x)a_ra_r^\mathsf{T} N − 1 ∑ r c r ( x ) a r a r T , where
c r ( x ) = φ α ′ ( u ) 2 + [ φ α ( u ) − φ α ( v ) ] φ α ′ ′ ( u ) , u = a r T x , v = a r T x ⋆ . c_r(x)=\varphi_\alpha'(u)^2+[\varphi_\alpha(u)-\varphi_\alpha(v)]\varphi_\alpha''(u),\qquad u=a_r^\mathsf{T}x,\qquad v=a_r^\mathsf{T}x^\star. c r ( x ) = φ α ′ ( u ) 2 + [ φ α ( u ) − φ α ( v )] φ α ′′ ( u ) , u = a r T x , v = a r T x ⋆ .
Since φ α ′ ( u ) = α + ( 1 − α ) sech 2 u \varphi_\alpha'(u)=\alpha+(1-\alpha)\operatorname{sech}^2u φ α ′ ( u ) = α + ( 1 − α ) sech 2 u , the squared derivative lies in [ α 2 , 1 ] [\alpha^2,1] [ α 2 , 1 ] . Put t = ∣ tanh u ∣ t=|\tanh u| t = ∣ tanh u ∣ . Then
∣ φ α ′ ′ ( u ) ∣ = 2 ( 1 − α ) ( 1 − t 2 ) t ≤ 4 ( 1 − α ) 3 3 . |\varphi_\alpha''(u)|=2(1-\alpha)(1-t^2)t\leq\frac{4(1-\alpha)}{3\sqrt{3}}. ∣ φ α ′′ ( u ) ∣ = 2 ( 1 − α ) ( 1 − t 2 ) t ≤ 3 3 4 ( 1 − α ) .
The residual satisfies
∣ φ α ( u ) − φ α ( v ) ∣ ≤ α ∣ u ∣ + α ∣ v ∣ + 2 ( 1 − α ) . |\varphi_\alpha(u)-\varphi_\alpha(v)|\leq\alpha|u|+\alpha|v|+2(1-\alpha). ∣ φ α ( u ) − φ α ( v ) ∣ ≤ α ∣ u ∣ + α ∣ v ∣ + 2 ( 1 − α ) .
Also,
∣ u ∣ sech 2 u ∣ tanh u ∣ ≤ 4 ∣ u ∣ e − 2 ∣ u ∣ ≤ 2 e . |u|\operatorname{sech}^2u|\tanh u|\leq4|u|e^{-2|u|}\leq\frac{2}{e}. ∣ u ∣ sech 2 u ∣ tanh u ∣ ≤ 4∣ u ∣ e − 2∣ u ∣ ≤ e 2 .
Splitting the residual into the three terms above gives the explicit bound
∣ [ φ α ( u ) − φ α ( v ) ] φ α ′ ′ ( u ) ∣ ≤ 4 α ( 1 − α ) e + 4 α ( 1 − α ) 3 3 ∣ v ∣ + 8 ( 1 − α ) 2 3 3 . |[\varphi_\alpha(u)-\varphi_\alpha(v)]\varphi_\alpha''(u)|\leq\frac{4\alpha(1-\alpha)}{e}+\frac{4\alpha(1-\alpha)}{3\sqrt{3}}|v|+\frac{8(1-\alpha)^2}{3\sqrt{3}}. ∣ [ φ α ( u ) − φ α ( v )] φ α ′′ ( u ) ∣ ≤ e 4 α ( 1 − α ) + 3 3 4 α ( 1 − α ) ∣ v ∣ + 3 3 8 ( 1 − α ) 2 .
Hence ∣ c r ( x ) ∣ ≤ B α ( v r ) |c_r(x)|\leq B_\alpha(v_r) ∣ c r ( x ) ∣ ≤ B α ( v r ) . Finally,
∥ ∇ 2 F ( x ) ∥ 2 ≤ 1 N ∑ r = 1 N ∣ c r ( x ) ∣ ∥ a r ∥ 2 ≤ 1 N ∑ r = 1 N B α ( v r ) ∥ a r ∥ 2 , \|\nabla^2F(x)\|_2\leq\frac{1}{N}\sum_{r=1}^{N}|c_r(x)|\|a_r\|^2\leq\frac{1}{N}\sum_{r=1}^{N}B_\alpha(v_r)\|a_r\|^2, ∥ ∇ 2 F ( x ) ∥ 2 ≤ N 1 r = 1 ∑ N ∣ c r ( x ) ∣∥ a r ∥ 2 ≤ N 1 r = 1 ∑ N B α ( v r ) ∥ a r ∥ 2 ,
which proves the global Lipschitz constant in Proposition 2.4.
When the feature vectors are the coordinate basis, the Hessian is diagonal. In that special case the generic sum can be sharpened to ∥ ∇ 2 F ( x ) ∥ 2 ≤ max r B α ( v r ) ∥ a r ∥ 2 / N \|\nabla^2F(x)\|_2\leq\max_r B_\alpha(v_r)\|a_r\|^2/N ∥ ∇ 2 F ( x ) ∥ 2 ≤ max r B α ( v r ) ∥ a r ∥ 2 / N .
Negative curvature within the certified class
For N = d = 1 N=d=1 N = d = 1 , a 1 = 1 a_1=1 a 1 = 1 , α = 1 / 2 \alpha=1/2 α = 1/2 and x ⋆ = − 2 x^\star=-2 x ⋆ = − 2 , the objective F ( x ) = [ φ 1 / 2 ( x ) − φ 1 / 2 ( − 2 ) ] 2 / 2 F(x)=[\varphi_{1/2}(x)-\varphi_{1/2}(-2)]^2/2 F ( x ) = [ φ 1/2 ( x ) − φ 1/2 ( − 2 ) ] 2 /2 is globally quasar-convex, and outward-rounded interval evaluation of F ′ ′ = φ 1 / 2 ′ 2 + [ φ 1 / 2 ( x ) − φ 1 / 2 ( − 2 ) ] φ 1 / 2 ′ ′ F''=\varphi_{1/2}'^2+[\varphi_{1/2}(x)-\varphi_{1/2}(-2)]\varphi_{1/2}'' F ′′ = φ 1/2 ′2 + [ φ 1/2 ( x ) − φ 1/2 ( − 2 )] φ 1/2 ′′ gives − 0.253 < F ′ ′ ( 1 ) < − 0.250 -0.253<F''(1)<-0.250 − 0.253 < F ′′ ( 1 ) < − 0.250 .
Reproducibility statement
This appendix summarizes the setup behind the numerical figures and tables in § 5 ; it is independent of the mathematical proofs.
All experiments are CPU-only Python simulations using NumPy, pandas, and Matplotlib. Every stochastic stream has a distinct mixed-radix seed indexed by experiment block, method, and replication, so all runs are exactly repeatable. The main certified monotone-link instance uses m = 16 m=16 m = 16 nodes, dimension d = 18 d=18 d = 18 , a realizable leaky-tanh link, and the rounded global constants reported in § 2.2 ; the finite-mixing and damping examples use the explicit phase-fixed mode v i = 2 cos ( π i / 2 + π / 2 ) v_i=\sqrt{2}\cos(\pi i/2+\pi/2) v i = 2 cos ( π i /2 + π /2 ) rather than a numerically selected eigenvector. Roots are sampled after the rows for q > 0 q>0 q > 0 and before the sole local row computation for q = 0 q=0 q = 0 , matching Lemma 4.6 .
All mixing operators are verified against explicit mean-preservation assertions, and an automated validation pass recomputes the spectral profiles, similarity constants, event counts, and every summary and first-passage value quoted in the paper directly from the raw runwise data. The manuscript rounds all constants to a readable number of significant digits; full-precision values are kept in machine-readable metadata. The simulation code, raw data, and validation scripts are available from the authors upon reasonable request.