acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Decentralized Online Non-Convex Optimization

Abstract

This paper studies decentralized online non-convex optimization (D-ONO), where a network of agents collaboratively minimizes a sequence of non-convex global loss functions through local computation and communication. Existing approaches either rely on an offline optimization oracle, which may require computational cost, or analyze window-averaged local regret based on local objectives, which does not accurately characterize the performance of individual agents. How to solve D-ONO under the standard notion of local regret, without requiring computations beyond gradient evaluations, remains largely unexplored. We propose Accelerated Decentralized Gradient Tracking (ADGT), which integrates gradient tracking into a block-wise online accelerated gossip scheme. Under both exact and stochastic gradient oracle feedback, we establish nearly optimal upper bounds on individual local regret and provide matching lower bounds. Extensive experiments on both synthetic and real-world datasets corroborate our theoretical findings and demonstrate the effectiveness of the proposed algorithm.

Primary area:
learning theory
Keywords:
Online Non-Convex Optimization, Decentralized Optimization, Optimal Regret

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_4yJyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies decentralized online non-convex optimization using individual local regret defined as Ri(T)=∑t=1T∣∣∇ft(xi,t)∣∣2R_i(T)=\sum_{t=1}^T ||\nabla f_t(x_{i,t})||^2, where ft=1n∑i=1nfi,tf_t=\frac1n\sum_{i=1}^n f_{i,t}. The authors propose Accelerated Decentralized Gradient Tracking (ADGT), an algorithm that holds decisions fixed within blocks while accumulating gradients and performing one accelerated gossip step per round. The authors derive an exact-gradient upper bound of O~(ρ−1/2(1+VT))\widetilde O(\rho^{-1/2}(1+V_T)) where ρ\rho is the spectral gap of the communication matrix and VTV_T measures the variation of functions (some sort of temporal variation of local losses). They also provides a stochastic upper bound (i.e., under stochastic gradient feedback), and present lower bounds to justify claims of near-optimality. Validation consists of controlled synthetic experiments and CIFAR10 experiments.

Critical strengths
  • The individual-agent guarantee for the global problem is quite appropriate. Indeed, measuring ∇ft(xi,t)\nabla f_t(x_{i,t}) avoids getting stuck in a possible bad outcome merely where each agent is stationary for its own local loss. The proposed separation of communication, variation, and stochastic-noise effects is also a good idea.

  • I like the idea of dealing with communication delays in an online fashion as described in the proposed ADGT algorithm (which spreads accelerated gossip across online rounds while keeping decisions fixed within each block).

Critical weaknesses
  • If I am not mistaken, the stochastic upper bound and algorithmic guarantee are not justified under the stated assumptions and parameters. In particular Assumption 2.4 gives pointwise unbiasedness and bounded variance, but Eq.(56), p.24, requires cross-agent noise cross terms to vanish or be nonpositive. Note that identical mean-zero additive noise shared by all agents satisfies the stated marginal assumption yet does not average down by 1/n1/n. Also I feel that the block-noise bounds and Eq.(40) would need a precise conditional noise model and a specification of admissible loss adaptivity. Finally, the accelerated-gossip parameter θ\theta is not specified, and Theorems 4.1 and 4.2 impose only upper bounds on γ\gamma, but the proof contains term like (1+VT)/γ(1+V_T)/\gamma. Arbitrarily small positive stepsizes do not necessarily imply the displayed final rates. In my view, these omissions may affect the central speedup and upper-bound claims.

  • There are issues in the derivation of the matching lower bounds. In particular, on p.28, the proof uses ∣∣∇fi,t∣∣2≤23c/K||\nabla f_{i,t}||_2 \leq 23c/\sqrt{K}, but the direct Euclidean bound after scaling from the infinity norm should instead be 23c23c. This impacts the justification of the stochastic oracle variance. The stochastic bound also needs parameter restrictions: for example, boundedness and smoothness imply Ri(T)≤4LMTR_i(T)\le4LMT, so the stated noise-dependent lower bound cannot hold uniformly for arbitrarily large σg\sigma_g. The p=1p=1 regime and the coordinate-block construction when K>BK>B require careful description. Finally, Theorem 5.1 gives a lower bound for some node, whereas Corollary 5.3 gives it for every node, and changes the diameter restriction from O(T/(1+VT))O(T/(1+V_T)) to O(T(1+VT))O(T(1+V_T)). This is confusing. Separate hard instances do not by themselves justify that stronger statement.

Questions for authors

The following are requests for clarification or correction of the current results:

  • Stochastic model and upper bound: What conditional unbiasedness and cross-agent/temporal independence assumptions are intended? Are the losses oblivious or adaptive to past oracle noise? Please state a precise filtration and explain why Eqs.(40) and (56) hold. What exact choices of θ\theta and γ\gamma yield the claimed rates, and which of VTV_T, TT, and σg\sigma_g must be known?

  • Stochastic lower bound: Can the variance calculation on p.28 be repaired by bounding the masked coordinates rather than the full gradient norm? Please give the valid parameter ranges, handle the p=1p=1 and K>BK>B cases, and reconcile the result with Ri(T)≤4LMTR_i(T)\le4LMT.

  • Combined optimality statement: Can Corollary 5.3 be proved with its printed ``every node'' quantifier, or should it be weakened to a worst-node minimax statement? Please also resolve its diameter condition and state explicitly the spectral-gap and dimension restrictions of the matching result.

  • Experimental interpretation: What matrix is used in the ring experiments? Under the stated weights, its diagonal is 1−2w1-2w and its smallest eigenvalue for the ten-node ring is 1−4w=−1/31-4w=-1/3 at w=1/3w=1/3, violating the PSD assumption. Please explain how the global gradient at each agent's model is evaluated. Please also reconcile the claimed local-regret advantage with Figures 2--3, where DSGD has smaller cumulative local regret for a substantial portion of training.

2 comments

We thank the reviewer for the insightful comments. Here are our response.

W1, Q1: about the stochastic assumption

Thank you for pointing out these omissions.

  • ``Are the losses oblivious or adaptive to past oracle noise?'' We have clarified in Assumption 2.4 that our stochastic analysis considers oblivious losses. In our blockwise gradient-tracking scheme, the descent analysis involves a cross term between the current block gradient and the previous block's noise. An adaptive adversary may choose the current losses based on this noise, so the cross term can not vanish under conditioning on the history before that noise is sampled. A possible direction is to use a potential function based on an earlier loss and bound with function variation VTV_T. We leave extending the stated guarantees to adaptive loss sequences as future work.

  • ``Please state a precise filtration and explain why Eqs.(40) and (56) hold.'' We have revised Assumption 2.4 to specify independent oracle sampling across calls and agents, following the i.i.d. settings of Hallak et al. [1, Section 4.1] and Hazan et al. [2, Assumption 4.2]. Our analysis considers oblivious losses, fixed in advance independently of the oracle randomness. Let Hz\mathcal H_z denote the history before block zz. Independent sampling implies $\mathbb E[\bar e_{z-1} \mid\mathcal H_{z-1}]=\mathbf0$; together with the measurability provided by the delayed update and fixed losses, this justifies Eq.(40). Moreover, $\mathbb E[|\mathbf e_{i,z}|^2\mid\mathcal H_z] \le B\sigma_g^2$ and $\mathbb E[|\bar e_z|^2\mid\mathcal H_z] \le B\sigma_g^2/n$ justify the block-noise bound and the 1/n1/n variance reduction in Eq.(56). We have updated the corresponding appendix explanations.

  • ``The accelerated-gossip parameter θ\theta is not specified.'' We now specify θ=(1+1−σ22(W))−1\theta=(1+\sqrt{1-\sigma_2^2(W)})^{-1}, following Wan et al. [3, Lemma 1].

  • ``Theorems 4.1 and 4.2 impose only upper bounds on γ\gamma.'' We have revised the stepsize choices to γ=Θ(B−1)\gamma=\Theta(B^{-1}) and $\gamma=\Theta(\min{B^{-1}, \sqrt{n(1+V_T)/(\sigma_g^2T)}})$, respectively, with sufficiently small constant factors, and verified the preceding lemmas' conditions. These choices control the (1+VT)/γ(1+V_T)/\gamma terms. The stochastic tuning requires TT, VTV_T, and σg\sigma_g; the deterministic tuning does not. The stated regret rates and the linear-speedup conclusion in Remark 4.3 remain unchanged.

W2 Q2: some typos, explanation of p=1p=1, K>BK>B and Ri(T)≤4LMTR_i(T) \leq 4LMT in lower bound

  • about the typos: We thank the reviewer for identifying the error on page 28, line 1504. We have corrected the derivation in the revised manuscript. Specifically, the probabilistic zero-chain property ensures that at most one masked coordinate has a nonzero gradient, allowing us to establish the desired bound using the ∣∣⋅∣∣∞||\cdot||_\infty norm.

  • about p=1p=1 and K>BK>B: In the revised manuscript, we consider two cases and adopt different constructions accordingly. When σg\sigma_g is sufficiently large, we retain the stochastic zero-chain construction, with K=Θ(cnB/σg)K=\Theta(c\sqrt{nB}/\sigma_g) and p=(23c)2/(Kσg2)p=(23c)^2/(K\sigma_g^2). The lower threshold on σg\sigma_g ensures both K≤BK\leq B and p<1p<1, making the construction valid. This case yields our original lower bound \Omega\left(\sigma_g\sqrt{\frac{(1+V_T)T}{n}}\right). \tag{1} When σg\sigma_g is sufficiently small, we instead adopt an exact-gradient construction by setting p=1p=1 and K=BK=B. This yields a lower bound of \Omega(1+V_T). \tag{2} We make this modification because, for sufficiently small σg\sigma_g, the original lower bound (1) can become arbitrarily small, potentially falling below the intrinsic lower bound (2). Combining these two cases, we establish the desired lower bound in terms of the maximum of the two terms, i.e., Ω(max⁡1+VT,σg(1+VT)Tn)\Omega\left(\max{ 1+V_T, \sigma_g \sqrt{\frac{(1+V_T)T}{n}} }\right) The detailed derivations and parameter choices are provided in the revised appendix, in the proof of Theorem 5.2.

  • about Ri(T)≤4LMTR_i(T) \leq 4LMT: We clarify that our lower bound is not claimed to hold for arbitrarily large σg\sigma_g. Under the upper bound imposed in Theorem 5.2, we have σg(1+VT)Tn=O(T).\sigma_g\sqrt{\frac{(1+V_T)T}{n}}=O(T). Thus, the stochastic lower bound grows at most linearly with TT, which is consistent with the universal upper bound Ri(T)≤4LMT=O(T)R_i(T)\leq 4LMT=O(T). We have explicitly stated this parameter restriction in the revised manuscript.

the typo in corollary 5.3

We thank the reviewer for pointing out the typos in the statement of Corollary 5.3. We have corrected the conditions in the revised manuscript to clarify that the lower bound holds for some agent i∈[n]i\in[n], and that the DD condition should be D≤O(T/(1+VT))D\leq O(T/(1+V_T)).

about experiments

  • ``w=1/3w=1/3 violates the PSD assumption.'': We thank the reviewer for pointing out the issue with our experimental setup. We have corrected ww in the revised manuscript to ensure that the mixing matrix satisfies PSD. Accordingly, the experimental results in the new figure 1b have also been updated.

  • ``how the global gradient at each agent's model is evaluated?'': Figures 2a and 3a strictly follow our definition of individual local regret. Specifically, at each evaluation checkpoint, every agent ii uses its own current xi,tx_{i,t} and the data collected from all agents to evaluate the global gradient: ∇ft(xi,t)=1n∑j=1n∇fj,t(xi,t).\nabla f_t(x_{i,t})=\frac{1}{n}\sum_{j=1}^{n}\nabla f_{j,t}(x_{i,t}). We record the cumulative local regret of each agent and report the maximum across all agents. This evaluation is performed only for measuring performance and does not involve global information exchange during algorithm execution.

  • ``DSGD has smaller cumulative local regret for a substantial portion of training.'': We further clarify that the learning rates are individually tuned for each algorithm to obtain stable and effective performance. In our experiments, a relatively large learning rate (e.g., 10−310^{-3}) causes pronounced oscillations in DSGD. We therefore select 5×10−45\times10^{-4} as its best learning rate, while the best learning rate for ADGT is 10−210^{-2}. The smaller learning rate may partly explain the lower cumulative local regret of DSGD during the early stages, as its iterates tend to evolve more slowly and remain in a relatively stable region. In contrast, ADGT can employ a larger learning rate, allowing more aggressive parameter updates and broader exploration of the optimization landscape.

[1] Hallak N, Mertikopoulos P, Cevher V. Regret minimization in stochastic non-convex learning via a proximal-gradient approach[C]. International Conference on Machine Learning. PMLR, 2021: 4008--4017.

[2] Hazan E, Singh K, Zhang C. Efficient regret minimization in non-convex games[C]. International Conference on Machine Learning. PMLR, 2017: 1433--1441.

[3] Wan Y, Wei T, Song M, et al. Nearly optimal regret for decentralized online convex optimization[C]. The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024: 4862--4888.

Reviewer_jna4OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper proposes a new algorithm for decentralized online non-convex optimization named ADGT, which combines gradient tracking and accelerated gossip communication in a block-wise fashion. The authors present upper bounds on the "local regret" of ADGT, which is defined as the cumulative squared gradient norm for each device. The authors also present lower bounds on the local regret of a broad class of algorithms, showing that they match the upper bounds of ADGT. This match enables the authors' claim for the optimality of ADGT. However, as detailed below, the derivation of bounds seems to contain multiple errors.

Critical strengths
  1. The device-wise cumulative squared gradient norm is a valid performance objective that properly represents the optimization outcome for individual devices.

  2. The attempt to show the optimality of ADGT is non-trivial, although there appear to be multiple errors in the proofs as explained below.

Critical weaknesses
  1. The proof of Theorem 4.1 is questionable. In particular, (28) requires that ∑z=1N∥∇Fτz(Xˉz)∥2≤BRˉ(T)\sum_{z=1}^{N} \|\nabla F_{\tau_z}(\bar{X}_z)\|^2 \leq B \bar{R}(T), which cannot be justified for the condition given under (27).

  2. The proof of Theorem 4.2 is incorrect. In particular, the condition on γ\gamma (re-stated in (59)) does not prevent it from being arbitrarily closed to zero. Thus, in general the right-hand side of (58) can be infinity. It cannot lead to (60).

  3. The proof of Theorem 5.2 is incorrect. On line 1484, ∥∇fi,t(x)∥≤23cK\| \nabla f_{i,t}(x)\| \leq \frac{23c}{\sqrt{K}} is not directly justified by Lemma C.4, whose infinite norm bound only guarantees ∥∇fi,t(x)∥≤23c\| \nabla f_{i,t}(x)\| \leq 23c. Later, on line 1504, it seems ∥∇fi,t(x)∥≤23cK\| \nabla f_{i,t}(x)\| \leq \frac{23c}{\sqrt{K}} is used in 1−pp∥∇fi,t(x)∥2≤σg2\frac{1-p}{p}\| \nabla f_{i,t}(x) \|^2 \leq \sigma_g^2. If ∥∇fi,t(x)∥≤23c\| \nabla f_{i,t}(x)\| \leq 23c is used, then we have 1−pp∥∇fi,t(x)∥2≤Kσg2\frac{1-p}{p}\| \nabla f_{i,t}(x) \|^2 \leq K\sigma_g^2 and Assumption 2.4 is satisfied with σnew:=Kσg2\sigma_{new} := \sqrt{K\sigma_g^2}. Consequently, the lower bound on line 1551 will be Ω​(σnewK(1+VT)T/n\Omega​(\frac{\sigma_{new}}{\sqrt{K}}\sqrt{(1+V_T )T/n}.

  4. The lower bounds in Theorems 5.1 and 5.2 hold for some nodes only. It is unclear how they directly lead to the conclusion in Corollary 5.3, which is a property for every node. In particular, how does one construct a graph to translate the "some node" result to all nodes of this graph?

  5. On line 850, PBP_B is not defined and the selection of θ\theta is not specified. Thus, the contraction inequality ∥PB−J∥2≤λB\| P_B - J \|_2 \leq \lambda_B cannot be verified.

  6. ADGT shares a similar structure with DeTAG (Algorithm 2) of Lu and de Sa (2021). DeTAG also fixes the model within blocks, accumulates gradients, and performs accelerated gossip on model and gradient tracker. Please provide an explicit comparison with DeTAG and identify the new algorithmic ingredients and proof techniques.

Questions for authors
  1. Can the technical errors identified above be corrected?

  2. How is this work different from Lu and de Sa (2021)?

2 comments

We thank the reviewer for the insightful comments. Here are our response.

W1: The proof of Theorem 4.1 is questionable

Thank you for pointing out this unclear step. The inequality follows directly from the Cauchy--Schwarz inequality, independently of the step-size condition below (27). Specifically, since Fτz(x)=∑t∈τzft(x)F_{\tau_z}(x)=\sum_{t\in\tau_z}f_t(x), ∣τz∣=B|\tau_z|=B, and the decisions remain fixed within each block, we have ∑z=1N∥∇Fτz(xˉz)∥2≤B∑z=1N∑t∈τz∥∇ft(xˉz)∥2=BRˉ(T).\sum_{z=1}^{N}\|\nabla F_{\tau_z}(\bar x_z)\|^2 \le B\sum_{z=1}^{N}\sum_{t\in\tau_z}\|\nabla f_t(\bar x_z)\|^2 = B\bar{R}(T). We have revised the proof in the appendix to make this step clearer.

W2: The proof of Theorem 4.2 is incorrect

In this revision, we have corrected (59) by choosing γ=c2min⁡{1−λB2BL(C1C290)1/4,n(1+VT)σg2T}\gamma=c_2\min\{\frac{1-\lambda_B}{2BL}(\frac{C_1C_2}{90})^{1/4},\sqrt{\frac{n(1+V_T)}{\sigma_g^2T}}\}, where c2>0c_2>0 is a sufficiently small fixed constant chosen to satisfy both the stepsize condition γ<1415BL\gamma < \frac{1}{4\sqrt{15}BL} in Lemma B.5 and the condition γ<12BLC113\gamma < \frac{1}{2BL}\sqrt{\frac{C_1}{13}} in Lemma B.6. We have also updated Theorems B.7 and 4.2 accordingly.

W3: The typos in the proof of theorem 5.2

We thank the reviewer for pointing out the errors in our proofs. The error in Line 1484 has been corrected. It was a typo and does not affect the validity of our construction. The error in Line 1504 has also been corrected, as can be seen in Line 1520. This was also a typo, and our construction still satisfies Assumption 2.4.

W4: The typos in corollary 5.3

We thank the reviewer for pointing out the typos in the statement of Corollary 5.3. Our result still establishes that there exists a node ii whose expected regret satisfies the stated lower bound. In addition, the condition on DD contained a typo; the correct condition is D≤O(T/(1+VT))D \leq O(T/(1+V_T)). Both errors have been corrected in the revised version.

W5: PBP_B and θ\theta is not specified.

In this revision, we have explicitly defined PBP_B as the BB-step accelerated-gossip operator:

P_{k+1}=(1+\theta)WP_k-\theta P_{k-1}.$$ and specified $\theta=(1+\sqrt{1-\sigma_2(W)^2})^{-1}$. as Lemma 1 in [1], yields $$\|P_B-J\|_2 \leq \sqrt{14} \left(1-\left(1-\frac{1}{\sqrt{2}}\right)\sqrt{\rho}\right)^B =\lambda_B.$$ We have included these definitions and the supporting reference in Appendix B.2.2. [1] Wan Y, Wei T, Song M, et al. Nearly optimal regret for decentralized online convex optimization[C]. The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024: 4862--4888. > W6 Q2: about the difference from Lu and de Sa (2021) We thank the reviewer for pointing out the similarity between ADGT and DeTAG. However, we claim that the primary contribution of our work lies in the theoretical analysis in the online setting. - First, **individual local regret is not merely a direct online extension of the offline stationarity metric**. It evaluates the stationarity of each agent's own local model w.r.t. the global $f_t$, providing a more meaningful performance measure for decentralized online opt, where agents maintain different local models throughout the learning process. - Second, **the online setting introduces substantial analytical challenges**. In particular, objective functions vary over time, so accumulated gradients within each block may correspond to different objectives. Moreover, establishing individual local regret guarantees requires jointly controlling temporal variation, consensus errors, and gradient-tracking errors at each agent, rather than merely analyzing the global or averaged model. We provide further technical details in our discussion with Reviewer t3Qj. - Finally, we establish both upper and lower bounds for individual local regret, characterizing the effects of temporal variation, stochastic gradient noise, and network topology. These results provide a theoretical framework for understanding the performance limits and guarantees of decentralized online non-convex optimization.

I can confirm that the authors' corrections and revision have addressed my previous concerns. I am no longer strongly against acceptance. However, given the many errors in the initial submission, I am not confident that there are no further errors in this revision (and unfortunately have no time to check). I will raise my rating to 2.

Reviewer_t3QjOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies decentralized online non-convex optimization under exact and stochastic gradient feedback. The authors propose ADGT, which combines block-wise online updates, accelerated gossip, and gradient tracking. They establish individual local regret upper bounds and propose matching lower bounds, supported by synthetic experiments and decentralized CNN training on CIFAR-10.

Critical strengths
  1. The paper considers individual local regret with respect to the global objective, which provides a meaningful measure of node-level stationarity in decentralized online non-convex optimization.
  2. Establishing matching upper and lower bounds that characterize network connectivity, function variation, and stochastic gradient noise would constitute a useful theoretical contribution.
Critical weaknesses

The proposed ADGT algorithm largely combines existing techniques, including block-wise updates, accelerated gossip, and gradient tracking. While the resulting individual local regret guarantees are potentially valuable, it would be helpful to more clearly distinguish the new technical contributions of the upper- and lower-bound analyses from adaptations of existing proof techniques.

Questions for authors
  1. Could the authors clarify which parts of the upper-bound analysis require genuinely new technical insights compared with existing results on centralized online non-convex optimization and decentralized gradient tracking? In particular, what are the main challenges in combining these techniques to obtain the claimed individual local regret bounds?
  2. Could the authors clarify the main technical novelty of the lower-bound proofs relative to prior work, particularly Yuan et al. (2022) and Arjevani et al. (2023)? Which aspects cannot be obtained through a direct adaptation of existing lower-bound arguments?
  3. Could the authors provide some intuition for using the function-value variation VTV_T to characterize gradient-based local regret? For example, adding a time-varying constant to each local loss function can make VTV_T large while leaving the gradients and local regret unchanged.
3 comments

We thank the reviewer for the insightful comments. Here are our response.

W Q2: about the technical novelty of our upper bound

We thank the reviewer for this insightful question. The main challenges are to connect block-level progress to per-round local regret and to control consensus errors tightly enough to guarantee the claimed bounds for every node.

  • From block-level regret to per-round local regret. Gradients within a block may cancel because the objectives change over time. This error vanishes for the fixed objective in Lu and De Sa (2021). In Wan et al. (2024), convex regret is bounded using linearized losses, which can be summed directly across a block. Let Fτz(x)=∑t∈τzft(x)F_{\tau_z}(x)=\sum_{t\in\tau_z}f_t(x). We use
\underset{\mathcal E_{\mathrm{within}}}{\sum_z\sum_{t\in\tau_z}\left\| \nabla f_t(\bar x_z) -\frac{1}{B}\nabla F_{\tau_z}(\bar x_z) \right\|^2}.$$ We express $\mathcal E_{\mathrm{within}}$ through pairwise gradient differences and apply $$\|\nabla f_s(x)-\nabla f_t(x)\|^2 \le 8L\sup_u|f_s(u)-f_t(u)|.$$ The variation budget then gives $\mathcal E_{\mathrm{within}}=O(LBV_T)$ (Lemma B.2). We also control changes between consecutive block objectives because the tracker uses the previous block's gradients. These block and tracking errors are absent from Guan et al. (2024)'s centralized per-round analysis. - **Individual guarantees and tighter consensus bounds.** Our metric, $$R_i(T)=\sum_{t=1}^T\|\nabla f_t(x_{i,t})\|^2,$$ measures each node's own decisions against the original global objectives. A good network-average iterate can hide poor performance at individual nodes, while small local gradients need not imply small global gradients. Using unsmoothed objectives also avoids cancellation across time that can hide large instantaneous gradients. These guarantees require additional control: $$R_i(T) \le 2\bar R(T) +2L^2B\sum_z \|X_z-\mathbf{1}\bar x_z^\top\|_F^2.$$ This consensus penalty has no $1/n$ normalization, unlike the corresponding term in the average-iterate analysis. Under stochastic feedback, we separately bound network-average noise and noise differences entering the tracking recursion. The former benefits from averaging across nodes; the latter creates additional disagreement. Our proof uses gossip accuracy $\lambda_B^2=O(1/n^2)$ to control this disagreement while preserving the term $\sigma_g\sqrt{(1+V_T)T/n}$ for every node (Lemmas B.5--B.6). > W Q2: about the technical novelty of our lower bound We thank the reviewer for this insightful question. We clarify the technical differences between our constructions and existing works. - **Compared with Yuan et al. (2022),** we adopt their ring-lattice graph construction to exploit the favorable relationship between the graph diameter $D$ and $\rho$. However, our deterministic construction uses a simpler and more direct bad-neighborhood construction to establish individual local regret lower bounds. Specifically, we construct a bad neighborhood in which agents have zero local functions and select an agent $i^\star$ whose distance from the informative region is $\Theta(D)$. After each environmental change, $i^\star$ cannot receive informative messages for $\Theta(D)$ rounds and thus incurs constant local regret during this period. Summing these contributions over environmental changes yields $\Omega(D(1+V_T))$. This construction directly captures the interplay between communication delays, environmental variations, and individual local regret. - **Compared with Arjevani et al. (2023),** we adopt their stochastic zero-chain technique as a building block for our stochastic construction. We extend it to the decentralized online setting by jointly designing the temporal block length, chain dimension, and stochastic coordinate revelation probability to satisfy $V_T$ and stochastic oracle constraints. Overall, our contribution lies in developing online lower bound constructions that directly characterize individual local regret under decentralized information constraints, while leveraging existing graph and zero-chain techniques where appropriate.

Q3: about the VTV_T limitation

We thank the reviewer for raising this interesting question, which we fully understand. A toy centralized example is ft(x)=f(x)+ctf_t(x)=f(x)+c_t, where ctc_t can be a simple linearly increasing sequence, such as ct=tc_t=t, resulting in a cumulative variation of VT=Θ(T)V_T=\Theta(T). However, the algorithm cannot detect this linear variation, and its performance is completely unaffected by ctc_t, at least for gradient-based algorithms.

In fact, this illustrates one of the limitations of bounds based on a single environmental variation measure: such a measure may fail to effectively characterize the achievable performance of an algorithm in certain scenarios. Establishing unified upper bounds under multiple environmental variation measures is therefore a meaningful direction for future research in online (decentralized) non-convex opt. For example, this line of research has already been relatively well developed in the centralized convex setting by [1].

[1] Zhao P, Zhang Y J, Zhang L, et al. Dynamic regret of convex and smooth functions[J]. NIPS, 2020.

Thank you for the detailed responses. I appreciate the clarifications regarding the theoretical analysis. Although the algorithmic components are largely based on existing techniques, the paper studies decentralized online non-convex optimization using a meaningful individual local regret measure and provides a relatively comprehensive set of theoretical results. I have increased my overall rating by one point accordingly.

Reviewer_E9J7OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies decentralized online non-convex optimization, where multiple agents collaboratively optimize a sequence of time-varying global objectives using only local gradient feedback and neighbor-to-neighbor communication. The paper evaluates each agent through the individual local regret Ri(T)=∑t=1T∣∇ft(xi,t)∣2R_i(T)=\sum_{t=1}^{T}|\nabla f_t(x_{i,t})|^2, which measures stationarity with respect to the global objective rather than a local or window-smoothed surrogate.

The authors propose Accelerated Decentralized Gradient Tracking, or ADGT. The method partitions the time horizon into blocks, keeps each decision fixed within a block, accumulates gradient feedback, and distributes accelerated-gossip iterations across the online rounds. Gradient tracking is then used to approximate the network-average block gradient. Under exact-gradient feedback, the paper claims Ri(T)=O~!(ρ−1/2(1+VT))R_i(T)=\widetilde O!\left(\rho^{-1/2}(1+V_T)\right). Under stochastic-gradient feedback, it claims E[Ri(T)]=O~!(ρ−1/2(1+VT)+σg(1+VT)Tn).\mathbb E[R_i(T)] =\widetilde O!\left(\rho^{-1/2}(1+V_T)+\sigma_g\sqrt{\frac{(1+V_T)T}{n}}\right).

The paper also develops deterministic and stochastic lower bounds and presents synthetic and CIFAR-10 experiments. The problem is important, the individual local-regret formulation is meaningful, and the deterministic analysis appears largely well structured. My main concern is that the stochastic upper bound uses conditional-unbiasedness and noise-independence properties that are not included in the stated assumptions. This affects Theorem 4.2 and the claimed linear speedup, although the issue may be repairable by strengthening the stochastic-oracle assumptions.

Critical strengths
  1. Meaningful problem formulation. The individual local regret is defined with respect to the global loss ftf_t, rather than each node's local objective. This gives a more informative measure of each agent's performance in the decentralized system. Equation (2) also provides a useful reduction from individual regret to average regret and consensus error.

  2. Communication-compatible algorithmic design. ADGT combines blocking, gradient tracking, and accelerated gossip while retaining one gradient query and one communication step per online round. The idea of distributing the required gossip iterations over the rounds of a block is natural and technically useful.

  3. Clear deterministic proof structure. The deterministic analysis separates temporal variation, averaged-node regret, and network disagreement. In particular, Eqs. (6) and (7), followed by Lemmas B.2 and B.3, make the sources of the final dependence on VTV_T and ρ\rho relatively transparent.

  4. Upper and lower bound perspective. The paper does more than propose an algorithm. It also constructs communication-based and stochastic-oracle lower bounds. The discussion in Appendix C.3 is useful because it explicitly explains why the deterministic lower-bound construction only covers a restricted spectral-gap range.

  5. Relevant experiments. The synthetic experiment directly varies VTV_T and ρ\rho, while the CIFAR-10 experiment compares ADGT with several decentralized baselines under heterogeneous data and distribution shifts.

Critical weaknesses
  1. The stochastic-oracle assumptions do not support the proof of Theorem 4.2. Assumption 2.4 on p. 3 states pointwise unbiasedness and a variance bound, However, the stochastic proof uses stronger properties.

First, Eq. (40) on p. 20 invokes E[ez−1∣Hz−]=0\mathbb E[e_{z-1}\mid\mathcal H_z^-]=0, which requires conditional unbiasedness with respect to the algorithmic history. This does not follow from the unconditional statement in Assumption 2.4.

Second, Eq. (56) on p. 24 uses E∣∑i=1nei,z∣2≤∑i=1nE∣ei,z∣2\mathbb E\left|\sum_{i=1}^{n}e_{i,z}\right|^2 \le \sum_{i=1}^{n}\mathbb E|e_{i,z}|^2 to obtain the (1/n) variance reduction. This inequality is not valid for arbitrarily correlated node noises. For example, if all agents receive the same noise, the left-hand side scales as n2n^2, while the right-hand side scales only as nn. Since each ei,ze_{i,z} also aggregates (B) oracle calls, the claimed Bσg2B\sigma_g^2 block variance requires an appropriate martingale-difference or temporal-independence condition.

This issue directly affects Theorem 4.2 and Remark 4.3. It may be repairable by explicitly assuming that the oracle noise is conditionally unbiased and conditionally independent, or at least uncorrelated, across agents and rounds. The authors should state the exact filtration and derive Eq. (56) from the strengthened assumption.

  1. The scope of the deterministic near-optimality claim should be qualified. Theorem 5.1 only proves the communication lower bound for ρ∈[1−cos⁡(π/n),1]\rho\in[1-\cos(\pi/n),1], which corresponds approximately to ρ=Ω(n−2)\rho=\Omega(n^{-2}). Appendix C.3 acknowledges this limitation and explains why the distance-based construction cannot cover arbitrarily small spectral gaps, but the abstract, Table 1, and conclusion describe the results more broadly as matching or near-optimal. These statements should explicitly specify the spectral-gap range in which matching is established.

  2. Assumption 2.3 requires (W) to be positive semidefinite. In the synthetic experiment, the paper uses a ten-node ring with edge weight w=1/3w=1/3. For the usual ring matrix, W=(1−2w)I+w(P+P⊤)W=(1-2w)I+w(P+P^\top), the eigenvalue associated with frequency (n/2) is (1-4w=-1/3). Thus, the experimental communication matrix is not PSD.

  3. The 1/n1/\sqrt n stochastic term is one of the paper's main theoretical contributions, but the experiments keep (n=10) fixed. A varying-nn experiment would be important for testing the claimed sample-complexity speedup. The paper should also report uncertainty intervals across the five runs and clarify how the global-gradient individual regret in Figures 2 and 3 is evaluated.

The real-data evidence is otherwise limited to one dataset, one relatively small CNN, and two graph families. These experiments support the algorithm qualitatively but do not strongly validate the broader scaling claims.

  1. Several appendix details need clarification: In Eq. (68) on p. 29, the summation appears to end at ((k-1)B+K), although the argument and the right-hand side (c^2B/(2K)) correspond to summing over the (B) rounds of the block. The upper limit appears intended to be (kB). This should be corrected.

The stochastic lower-bound construction also uses coordinates up to approximately (T+K), while Theorem 5.2 only states (d=\Omega(T)). The authors should state the parameter regime ensuring (K=O(T)), or modify the dimension requirement.

There are also several local (B/L) notation slips. For example, Appendix B.1 describes (L) accelerated-gossip steps where Algorithm 1 uses (B), and Appendix B.2.2 states that each block contains (L) loss functions. Since (L) is otherwise the smoothness constant, these occurrences should be corrected carefully.

Questions for authors
  1. Can the authors restate Assumption 2.4 using an explicit filtration and specify the required dependence structure across agents and time? Under those assumptions, does Eq. (56) hold exactly as written?

  2. Does the claimed stochastic linear speedup remain valid if oracle noises are correlated across agents?

  3. In Eq. (68), should the upper summation limit be (kB) rather than ((k-1)B+K)? What exact dimension condition is needed for the zero-chain construction?

2 comments

We thank the reviewer for the insightful comments. Here are our response.

W1 Q1 Q2: The stochastic-oracle assumptions do not support the proof of Theorem 4.2

  • Thank you for pointing out this omission. We have revised Assumption 2.4 to explicitly specify independent oracle sampling across calls and agents and the local loss sequence is oblivious. For all i∈[n]i\in[n], t∈[T]t\in[T] This follows the i.i.d. setting of Hallak et al. [1, Section 4.1] and Hazan et al. [2, Assumption 4.2], extended to independent sampling across agents. These sampling assumptions imply the conditional properties required by the proof. Specifically, let Hz\mathcal H_z denote the history before block zz. Conditional on Hz\mathcal H_z, the query points xi,zx_{i,z} are fixed throughout the block. Thus, for each t∈τzt\in\tau_z, independent sampling and the pointwise moment bounds in Assumption 2.4 give
=\mathbf0, \qquad \mathbb E[\|\xi_{i,t}\|^2 \mid\mathcal H_z]\le\sigma_g^2,$$ where \$\xi_{i,t} =\mathbf g_{i,t}(x_{i,z}) -\nabla f_{i,t}(x_{i,z})\$. Independent sampling across calls and agents gives $$\mathbb E[ \langle\xi_{i,t}, \xi_{j,s}\rangle \mid\mathcal H_z] =0, \qquad (i,t)\ne(j,s),\quad t,s\in\tau_z.$$ Consequently, $\mathbb E[\bar e_{z-1}\mid\mathcal H_{z-1}] =\mathbf0$, which justifies the zero conditional mean used in Eq.(40). $\bar x_z$ and $\bar g_{z-1}^{\mathrm{true}}$ measurable with respect to $\mathcal H_{z-1}$. Moreover, $\mathbb E[\|\mathbf e_{i,z}\|^2\mid\mathcal H_z] \le B\sigma_g^2$ gives the block-noise bound used in Eq.(56), while $\mathbb E[\|\bar e_z\|^2\mid\mathcal H_z] \le B\sigma^2_g/n$ establishes its $1/n$ variance reduction. - We have also corrected the stepsize choices in Theorems 4.1 and 4.2 and their appendix proofs: instead of imposing only upper bounds on $\gamma$, we now specify its required order and check the preceding lemmas' conditions. With these revisions, the stated rates and the linear-speedup conclusion in Remark 4.3 are unchanged. [1] Hallak, Nadav, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via a proximal-gradient approach. International Conference on Machine Learning. PMLR, 2021. [2] Hazan, Elad, Karan Singh, and Cyril Zhang.Efficient regret minimization in non-convex games. International Conference on Machine Learning. PMLR, 2017. > W2: clarification of the $\rho$ regime We thank the reviewer for pointing out the issues with the presentation of our results. We have moved the discussion in Appendix C.3 to the main text as Remark 5.4, revised the relevant statements in the Introduction and Abstract to clarify the $\rho$ range, and added an extra column to Table 1. These revisions are included in the revised manuscript. > W3: $w=1/3$ violates PSD assumption We appreciate the reviewer for identifying the issue with our experimental setup. We have revised $w=1/5$ to ensure that the mixing matrix satisfies PSD assumption. Accordingly, the results in the revised Figure 1b have also been updated. > W4: about the experiments - *``A varying-$n$ experiment...''*: Thank you for this suggestion. We have added CIFAR10 experiments with $n\in\{2,4,8,16\}$ in the revised manuscript. The results show empirical speedup in terms of training loss and test accuracy. - *``The paper should also report uncertainty intervals...''*: Figures 2 and 3 already include shaded bands showing the mean $\pm$ one standard deviation across five independent runs. We have clarified this in the figure captions. - *``How the global-gradient individual regret in Figures 2 and 3 is evaluated?''*: For Figures 2a and 3a, the evaluation uses the global objective gradient at each agent’s own iterate, consistent with our definition of individual local regret. At each evaluation checkpoint, we compute $$\nabla f_t(x_{i,t}) =\frac{1}{n}\sum_{j=1}^{n}\nabla f_{j,t}(x_{i,t}),$$ using data from all agents while evaluating every term at the same local iterate $x_{i,t}$. We accumulate the squared gradient norms separately for each agent and plot the largest cumulative value across agents. This global gradient computation is used solely for evaluation and is not supplied to the algorithms. > W5 Q3: typos, and the dimension condition of lower bound - We thank the reviewer for pointing out the typos. The upper limit of the summation in Eq.(68) has been corrected to $kB$ in the revised manuscript. - We thank the reviewer for raising this question. In the revised construction, we ensure that $K\leq B$, where $B=\lceil T/N\rceil\leq T$. Consequently, $K=O(T)$. Since the stochastic construction requires coordinates up to at most $T+K=O(T)$, the dimension condition $d=\Omega(T)$ is sufficient to accommodate the entire construction. We have clarified this parameter relationship in the revised manuscript.

Thank you for the detailed clarifications and additional comparisons, which address most of my concerns. I intend to adjust the score to 3.

Comments on the paper

1 comment

Dear Reviewers,

Thank you for the sightful comments. We hope that you've read our rebuttals and found answers to your questions. As the discussion phase is approaching its end, we would be happy to have the chance to engage in some discussion if there are remaining concerns / issues.

Thank you for your time!

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.