- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies gradient-variation and small-loss regret in decentralized online convex optimization. It proposes an optimistic FTRL algorithm with two-level gradient tracking and accelerated gossip, proves bounds for convex and strongly convex losses, and provides corresponding lower bounds on a cycle network.
Critical strengths
- The different network dependence of convex gradient-variation and small-loss bounds is an interesting finding. The lower bounds make this distinction more convincing than an upper-bound analysis alone.
- The analysis controls prediction and tracking errors through the same block-gradient variation. The decentralized restart scheme also removes prior knowledge of the difficulty measures without adding communication rounds.
Critical weaknesses
- The optimality claims need qualification. All lower bounds use a cycle graph with , so they establish hardness for this network family rather than characterize arbitrary networks.
- The convex guarantee does not explicitly retain the optimal worst-case rate. When , the variation branch has worse network dependence than existing worst-case bounds, while the small-loss branch requires to remain sufficiently small.
Questions for authors
- Can the same algorithm also guarantee without assuming bounded loss values?
- What bound follows from combining an existing decentralized delayed-OCO reduction with a centralized optimistic learner, and where does it fall short of your result?
- Could you provide experiments to support results?
2 comments
Q4: What bound follows from combining an existing decentralized delayed-OCO reduction with a centralized optimistic learner, and where does it fall short of your result?
A: Combining the decentralized delayed-OCO reduction [1] with a centralized optimistic learner introduces additional dependence on . This additional dependence was already noted in Section 1.1 (Related Work) of our original manuscript. Specifically, [1] requires the consensus errors to be sufficiently small () to prevent their accumulation over the horizon, leading to a block length of . In contrast, our two-level gradient tracking controls the accumulated prediction and consensus errors through block-gradient variation, requiring only a horizon-independent block length of .
Consequently, combining the reduction in [1] with standard worst-case guarantees for centralized optimistic learners yields bounds of order for convex losses and for strongly convex losses. More importantly, the reduction does not directly yield guarantees in terms of the original and . In contrast, our method establishes regret bounds depending on the smaller of the -dependent and -dependent terms without additional horizon-dependent logarithmic factors. This distinction is particularly significant for strongly convex losses, where our guarantee depends on rather than , allowing substantially smaller regret bounds for benign loss sequences.
References.
[1] Y. Wan. Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments. COLT, pp. 5605–5631, 2025.
Q5: Could you provide experiments to support the results?
A: We thank the reviewer for this valuable suggestion. To provide empirical support for our theoretical findings, we have added an Experiments section (pages 9–10 of the revised manuscript), with complete experimental details and additional results in Appendix H.
Specifically, we evaluate DOFTRL-GT on two real-world datasets, ECL [1] and MNIST [2], under both general convex and strongly convex settings. Comparisons with three representative decentralized online algorithms, DOGD [3], DODA [4], and AD-FTGL [5], demonstrate that DOFTRL-GT consistently achieves lower cumulative static regret (Figure 1).
More importantly, to investigate the benefits of exploiting benign loss sequences, we design controlled experiments to examine the effects of and at a fixed time horizon. On ECL, we vary while keeping nearly unchanged (Table 2). On MNIST, we vary while keeping fixed (Table 3). In both cases, regret increases as the corresponding quantity grows, highlighting the practical relevance of both and in characterizing sequence-dependent regret.
Furthermore, we conduct additional experiments on MNIST to evaluate the two applications discussed in the paper, namely decentralized offline optimization and the stochastically extended adversarial (SEA) model. The results further demonstrate the effectiveness of DOFTRL-GT in exploiting benign environmental structures (Appendix H.2).
References.
[1] R. Godahewa, C. Bergmeir, G. Webb, R. Hyndman, and P. Montero-Manso. Electricity Hourly Dataset. Zenodo, 2020.
[2] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-Based Learning Applied to Document Recognition. Proceedings of the IEEE, 86(11), pp. 2278–2324, 1998.
[3] F. Yan, S. Sundaram, S. V. N. Vishwanathan, and Y. Qi. Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties. IEEE TKDE, 25(11), pp. 2483–2493, 2013.
[4] S. Hosseini, A. Chapman, and M. Mesbahi. Online Distributed Optimization via Dual Averaging. IEEE CDC, pp. 1484–1489, 2013.
[5] Y. Wan, T. Wei, B. Xue, M. Song, and L. Zhang. Optimal and Efficient Algorithms for Decentralized Online Convex Optimization. JMLR, 26(135), pp. 1–43, 2025.
A: Our lower bounds establish worst-case optimality rather than optimality for every fixed network. As in existing lower-bound studies on decentralized OCO, including Wan et al. [1,2], the standard approach is to construct a hard instance consisting of a specific network and loss sequence, showing that any algorithm must incur the stated regret. Our cycle-graph construction with ρ=sin2(π/N) follows this approach. Since our upper bounds hold for all admissible networks, these constructions establish worst-case tightness for the considered network family, up to logarithmic factors. We have clarified this scope in Section 4 of the revised manuscript.
References.
[1] Y. Wan, T. Wei, M. Song, and L. Zhang. Nearly Optimal Regret for Decentralized Online Convex Optimization. COLT, pp. 4862–4888, 2024.
[2] Y. Wan, T. Wei, B. Xue, M. Song, and L. Zhang. Optimal and Efficient Algorithms for Decentralized Online Convex Optimization. JMLR, 26(135), pp. 1–43, 2025.
A: Although the VT-dependent bound has worse network dependence when VT=Θ(T), DOFTRL-GT can still achieve the nearly optimal O(Nρ−1/4T) worst-case regret bound for convex losses without requiring FT to be small. To make this result explicit, we have added Corollary 11 and its proof in the new Appendix G (pages 40–41 of the revised manuscript). Specifically, under the bounded-gradient assumption, the block-gradient variation satisfies VZ≤4G2Z, where Z=T/B. Combining this estimate with the existing regret analysis in the proof of Theorem 1 yields the regret bound O(Nminρ−1/4T,ρ−3/4VT), up to additive terms independent of T and VT.
A: Our DOFTRL-GT can achieve the O(Nρ−1/4T) worst-case regret bound without assuming bounded loss values. To make this result explicit, we have added Corollary 11 and its proof in the new Appendix G (pages 40–41 of the revised manuscript). This follows by bounding the block-gradient variation as VZ≤4G2Z, where Z=T/B, under the bounded-gradient assumption and applying the existing regret analysis in the proof of Theorem 1. The same corollary also establishes the corresponding worst-case guarantee for strongly convex losses.