- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2(+1)
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies decentralized online optimization with exp-concave losses, where agents observe only local gradients and communicate with their neighbors. It proposes a decentralized Online Newton Step algorithm that combines block-based updates, accelerated gossip, and delayed second-order optimization to achieve polylogarithmic regret. The paper also establishes a nearly matching lower bound on cycle networks and extends the framework to decentralized online linear regression over an unbounded parameter domain using ridge regression and clipped predictions.
Critical strengths
- The paper investigates whether exp-concavity can yield polylogarithmic regret under decentralized communication. It complements existing results for convex and strongly convex losses and addresses an open question identified in prior work.
- In addition to the algorithm and regret upper bound, the paper establishes a lower bound on a particular family of networks, demonstrating near-optimality on the corresponding hard instances.
- The proof separates consensus errors, the reduction to block-level surrogate regret, and the analysis of delayed second-order updates. This structure makes the argument relatively easy to follow and clarifies how communication errors affect the regret guarantee.
Critical weaknesses
- The proposed approach largely combines existing block-based communication, accelerated gossip, and delayed second-order online learning techniques. Although the analysis addresses the mismatch between preparatory and executed decisions, it relies primarily on standard consensus bounds, stability arguments, and potential analysis. The paper does not clearly establish a substantial technical advance beyond adapting these tools to the exp-concave setting.
- The lower bound is established only for a particular family of cycle networks, where the network size and spectral gap are coupled. It therefore supports near-optimality on these hard instances, but does not establish that the network dependence is tight for general topologies.
- The extension exploits the aggregation of sufficient statistics and combines ridge regression with prediction clipping. While technically sound in its design, its additional conceptual contribution appears limited.
- The paper provides no empirical evaluation of the proposed algorithms. Although experiments are not essential for a theoretical contribution, they would help assess the effects of block-induced delays, second-order computation, and matrix-valued communication in the regression extension.
Questions for authors
- Could the authors clarify the precise technical advance over prior work? In particular, which step in the exp-concave reduction requires an argument beyond adapting the existing block-based gossip framework and delayed ONS analysis?
- Can the network dependence be justified beyond cycle graphs? Since network size and spectral gap are coupled in the lower-bound construction, is it possible to establish a lower bound for a broader family of topologies, or clarify the scope of the near-optimality claim?
- Is the additional logarithmic factor inherent or an artifact of the analysis? Could a different communication schedule or a less stringent consensus accuracy remove it?
5 comments
2. Can the network dependence be justified beyond cycle graphs? Since network size and spectral gap are coupled in the lower-bound construction, is it possible to establish a lower bound for a broader family of topologies, or clarify the scope of the near-optimality claim?
Our lower bound is a worst-case result over networks satisfying our assumptions. Constructing one admissible hard graph family is sufficient to establish such a lower bound. It need not hold for every topology. The cycle construction therefore provides a valid worst-case lower bound.
To further address your concern about the coupling between network size and spectral gap, we have added Theorem 4 and its complete proof in Appendix D, ``Lower Bound Beyond Cycle Graphs.'' The new construction arranges agents into equal-sized clusters along a path. Its mixing matrix has spectral gap , independent of the cluster size . Consequently, can increase while the spectral gap remains fixed, and the spectral gap can vary at fixed through the admissible choices of . Under the conditions stated in the theorem, for every possibly randomized decentralized algorithm, there exists a sequence of admissible losses such that
\ge \frac{Nd}{32\alpha\sqrt{\rho}} \log\frac{T}{qd}.$$ This matches the upper bound up to logarithmic factors on a broader, two-parameter graph family. We also clarify that our near-optimality claim concerns this worst-case sense, rather than a matching lower bound for every topology or every independently prescribed pair $(N,\rho)$. >**3. Is the additional logarithmic factor inherent or an artifact of the analysis? Could a different communication schedule or a less stringent consensus accuracy remove it?** We thank the reviewer for this insightful question. The additional logarithmic factor arises from the interaction between the block-based communication schedule and the delayed ONS analysis: the latter contributes an $O(\log T)$ term, while controlling accumulated consensus errors requires a block length of $O((1-\sigma_2(P))^{-1/2}\log T)$. Simply relaxing consensus accuracy does not immediately remove this factor, since larger consensus errors may accumulate and deteriorate the regret bound. A more adaptive communication schedule or a sharper stability analysis may potentially reduce it and we leave this improvement as an interesting open direction. >**4. On experiments.** We have added two synthetic studies in **Section 5 (page. 10)**, comparing D-ONS and D-OLR with D-OGD (Yan et al., 2013) and AD-FTGL (Wan et al., 2024) on grid, complete, and ring graphs. Table 1 reports the mean final worst-node cumulative regret over 20 paired test streams. In these simulations, both proposed methods achieve lower mean final regret than both baselines on all three graphs. The corresponding learning curves are provided in **Appendix E, Figure 1 (page. 31)**. The added experimental text and captions are highlighted in orange in the revised manuscript. > **5. The extension exploits the aggregation of sufficient statistics and combines ridge regression with prediction clipping. While technically sound in its design, its additional conceptual contribution appears limited.** We agree that sufficient-statistic aggregation, ridge regression, and prediction clipping are established tools. The contribution of this extension is to show that polylogarithmic regret remains achievable in decentralized online regression over an **unbounded parameter domain**, where each agent observes only its local features and labels, and the labels may be chosen adversarially. **This setting is not directly covered by our bounded-domain exp-concave result**, since squared loss is not globally exp-concave over $\mathbb{R}^d$. The analysis controls both the communication delay and the effect of approximate covariance and label-feature statistics on the ridge predictor. Clipping bounds the resulting prediction losses without imposing a bounded parameter domain, yielding the guarantee in Theorem 3 for every fixed comparator in $\mathbb{R}^d$. We therefore view this result as a complementary contribution: it establishes that the framework extends beyond bounded-domain exp-concave optimization and identifies how the structure of regression makes this possible.- The response clarifies the technical contribution. I nevertheless retain reservations about the extent of the advance over the existing decentralized framework and delayed ONS analysis.
- The additional lower-bound construction and proof are convincing and address my concern about the coupling between network size and spectral gap.
I have a question about the new experiments: Could the authors specify the actual block length used for Algorithm 1 on each of the three graphs in the experiments reported in Table 1?
Thank you for this question. The specific additional argument is in Lemma 5: converting the local exp-concave quadratic corrections into a block-level correction expressed using the gossiped gradients, while controlling the errors introduced by decentralized communication. Lemma 2 then verifies that the resulting expression is compatible with the delayed ONS update. We explain the distinction from the two prior analyses below.
Lemma 5: comparison with Wan (2025, Theorem 1). In the strongly convex reduction, curvature provides a uniform quadratic correction 2μ∣y−x∣22, where μ is the strong-convexity parameter. For exp-concave losses, the correction instead depends on the local gradient direction and the decision at which that gradient is evaluated. Consequently, the uniform-curvature surrogate construction does not directly supply the correction needed by our second-order update.
Specifically, Lemma 5 establishes
\sum_{t\in\mathcal T_z}\sum_{k=1}^N \left\langle \nabla f_{t,k}(x_k(z)),x_k(z)-x \right\rangle^2 \le -\frac{\beta}{2L}\sum_{j=1}^N \left\langle g_j(z),x_j(z)-x\right\rangle^2 +\varepsilon_z,$$ where $|\mathcal T_z|=L$ and, under our gossip parameters, $\sum_z\varepsilon_z=O(\beta G^2D^2/(NT))$. The left-hand side involves gradients evaluated at different agents' executed decisions. The right-hand side must retain the negative quadratic correction using the locally available estimates $g_j(z)$ of the network-averaged block gradient. To see the additional argument, write $a_{t,k}=\langle\nabla f_{t,k}(x_k(z)),x_k(z)-x\rangle$. Jensen's inequality first gives $-\sum_{t,k}a_{t,k}^2\le-(\sum_{t,k}a_{t,k})^2/(NL)$. Decision consensus then allows us to replace the local executed decisions inside this squared aggregate by their network average. Gradient consensus allows us to replace the averaged block gradient by each local estimate and return to the corresponding executed decision. Using $|a^2-b^2|=|a-b||a+b|$, we bound the resulting perturbations while retaining the coefficient $\beta/(2L)$ needed by the subsequent analysis. The averaging and perturbation inequalities are standard; the additional verification is that these replacements preserve the exp-concave correction with a controlled cumulative error. **Lemma2: comparison with Qiu et al. (2025, Theorem 4.1).** The reduction in Lemma 5 leads, for each agent $j$, to $$S_j(x)=\sum_{z=1}^{T/L} \left( \left\langle g_j(z),\widehat{x}_j(z)-x\right\rangle -\frac{\beta}{2L} \left\langle g_j(z),x_j(z)-x\right\rangle^2 \right).$$ Two features prevent a direct invocation of a standard single-decision ONS guarantee. First, $g_j(z)$ approximates an aggregate of gradients evaluated at different local executed decisions; it need not be the gradient of the network-averaged block loss at a common decision. Second, the linear term uses the preparatory decision $\widehat{x}_j(z)$, whereas the quadratic term uses the executed decision $x_j(z)$. Thus, the expression generally differs from the usual ONS surrogate, which uses the same decision in both terms. We adapt the delayed ONS analysis of Qiu et al. (2025), using its local-norm stability and elliptical-potential tools, including the stability comparison in Lemma A.2. A regularized-leader comparison produces a positive quadratic sum that cancels the negative correction in $S_j(x)$. The remaining difference between the delayed preparatory decision and the current regularized leader is controlled in the adaptive norm induced by $$A_j(z)=\eta I_d+\frac{\beta}{L} \sum_{s=1}^{z}g_j(s)g_j(s)^\top.$$ Lemma 2 verifies this cancellation and stability argument for the two distinct decision sequences. We do not claim a new general stability inequality or an independently novel delayed ONS principle. The technical contribution is therefore the curvature-preserving decentralized reduction and the verification that its output can be controlled by the adapted delayed second-order analysis. Together, these steps yield the stated $O(Nd(1-\sigma_2(P))^{-1/2}\log^2 T)$ regret bound. The value of combining the established tools lies in making this decentralized guarantee possible. We have clarified these roles in Section 3.2, with the complete derivation in Appendix B.