- 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 , where . 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 where is the spectral gap of the communication matrix and 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 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 . 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 is not specified, and Theorems 4.1 and 4.2 impose only upper bounds on , but the proof contains term like . 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 , but the direct Euclidean bound after scaling from the infinity norm should instead be . This impacts the justification of the stochastic oracle variance. The stochastic bound also needs parameter restrictions: for example, boundedness and smoothness imply , so the stated noise-dependent lower bound cannot hold uniformly for arbitrarily large . The regime and the coordinate-block construction when 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 to . 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 and yield the claimed rates, and which of , , and 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 and cases, and reconcile the result with .
-
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 and its smallest eigenvalue for the ten-node ring is at , 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
about experiments
-
`` violates the PSD assumption.'': We thank the reviewer for pointing out the issue with our experimental setup. We have corrected 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 uses its own current and the data collected from all agents to evaluate the global gradient: 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., ) causes pronounced oscillations in DSGD. We therefore select as its best learning rate, while the best learning rate for ADGT is . 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.
We thank the reviewer for the insightful comments. Here are our response.
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 VT. 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 denote the history before block z. 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/n variance reduction in Eq.(56). We have updated the corresponding appendix explanations.
``The accelerated-gossip parameter θ is not specified.'' We now specify θ=(1+1−σ22(W))−1, following Wan et al. [3, Lemma 1].
``Theorems 4.1 and 4.2 impose only upper bounds on γ.'' We have revised the stepsize choices to γ=Θ(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)/γ terms. The stochastic tuning requires T, VT, and σg; the deterministic tuning does not. The stated regret rates and the linear-speedup conclusion in Remark 4.3 remain unchanged.
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 ∣∣⋅∣∣∞ norm.
about p=1 and K>B: In the revised manuscript, we consider two cases and adopt different constructions accordingly. When σg is sufficiently large, we retain the stochastic zero-chain construction, with K=Θ(cnB/σg) and p=(23c)2/(Kσg2). The lower threshold on σg ensures both K≤B and p<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 is sufficiently small, we instead adopt an exact-gradient construction by setting p=1 and K=B. This yields a lower bound of \Omega(1+V_T). \tag{2} We make this modification because, for sufficiently small σ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., Ω(max1+VT,σgn(1+VT)T) The detailed derivations and parameter choices are provided in the revised appendix, in the proof of Theorem 5.2.
about Ri(T)≤4LMT: We clarify that our lower bound is not claimed to hold for arbitrarily large σg. Under the upper bound imposed in Theorem 5.2, we have σgn(1+VT)T=O(T). Thus, the stochastic lower bound grows at most linearly with T, which is consistent with the universal upper bound Ri(T)≤4LMT=O(T). We have explicitly stated this parameter restriction in the revised manuscript.
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], and that the D condition should be D≤O(T/(1+VT)).