acceptodds
Under review as a conference paper at ICLR 2027

Gradient-Variation and Small-Loss Regret for Decentralized Online Convex Optimization

Abstract

We study decentralized online convex optimization over a fixed network of learners with spectral gap , where learners communicate only with their neighbors. Existing algorithms achieve nearly optimal worst-case regret bounds, but do not adapt to benign loss sequences, such as those with small gradient variation or small comparator loss. To address this limitation, we propose Decentralized Optimistic Follow-the-Regularized-Leader with Gradient Tracking (DOFTRL-GT), which combines delay-compensated optimism with two-level gradient tracking via accelerated gossip. DOFTRL-GT achieves regret bounds of for convex losses and for strongly convex losses, up to additive terms independent of , , and . Here, denotes the gradient variation, the cumulative loss of the best fixed comparator, and hides logarithmic factors in and . We establish lower bounds that match the corresponding upper bounds up to logarithmic factors in their respective problem-dependent regimes, showing that convex gradient-variation and small-loss guarantees necessarily incur distinct and , respectively. Finally, applications to offline optimization and stochastic-adversarial learning further demonstrate its ability to exploit benign loss sequences.

Primary area:
learning theory
Keywords:
online learning, gradient-variation regret, small loss

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_2tkYOpenReview ↗
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
  1. 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.
  2. 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
  1. The optimality claims need qualification. All lower bounds use a cycle graph with ρ=sin⁡2(π/N)\rho=\sin^2(\pi/N), so they establish hardness for this network family rather than characterize arbitrary networks.
  2. The convex guarantee does not explicitly retain the optimal worst-case rate. When VT=Θ(T)V_T=\Theta(T), the variation branch has worse network dependence than existing worst-case bounds, while the small-loss branch requires FTF_T to remain sufficiently small.
Questions for authors
  1. Can the same algorithm also guarantee O~(Nρ−1/4T)\widetilde O(N\rho^{-1/4}\sqrt T) without assuming bounded loss values?
  2. 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?
  3. Could you provide experiments to support results?
2 comments

Q1: The optimality claims need qualification. All lower bounds use a cycle graph with ρ=sin⁡2(π/N)\rho=\sin^2(\pi/N), so they establish hardness for this network family rather than characterize arbitrary networks.

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 ρ=sin⁡2(π/N)\rho=\sin^2(\pi/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.

Q2: The convex guarantee does not explicitly retain the optimal worst-case rate. When VT=Θ(T)V_T = \Theta(T), the variation branch has worse network dependence than existing worst-case bounds, while the small-loss branch requires FTF_T to remain sufficiently small.

A: Although the VTV_T-dependent bound has worse network dependence when VT=Θ(T)V_T=\Theta(T), DOFTRL-GT can still achieve the nearly optimal O~(Nρ−1/4T)\widetilde{O}(N\rho^{-1/4}\sqrt{T}) worst-case regret bound for convex losses without requiring FTF_T 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 V^Z≤4G2Z\widehat V_Z\le 4G^2Z, where Z=T/BZ=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)\widetilde{O}(N\min\\{\rho^{-1/4}\sqrt{T},\rho^{-3/4}\sqrt{V_T}\\}), up to additive terms independent of TT and VTV_T.

Q3: Can the same algorithm also guarantee O~(Nρ−1/4T)\widetilde{O}(N\rho^{-1/4}\sqrt{T}) without assuming bounded loss values?

A: Our DOFTRL-GT can achieve the O~(Nρ−1/4T)\widetilde{O}(N\rho^{-1/4}\sqrt{T}) 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 V^Z≤4G2Z\widehat V_Z\le 4G^2Z, where Z=T/BZ=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.

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 log⁡T\log T. This additional log⁡T\log T dependence was already noted in Section 1.1 (Related Work) of our original manuscript. Specifically, [1] requires the consensus errors to be sufficiently small (O(1/T)O(1/T)) to prevent their accumulation over the horizon, leading to a block length of L=Θ(ρ−1/2log⁡(TN))L=\Theta(\rho^{-1/2}\log(T\sqrt{N})). 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 B=Θ(ρ−1/2log⁡N)B=\Theta(\rho^{-1/2}\log N).

Consequently, combining the reduction in [1] with standard worst-case guarantees for centralized optimistic learners yields bounds of order O~(Nρ−1/4Tlog⁡T)\widetilde{O}(N\rho^{-1/4}\sqrt{T\log T}) for convex losses and O~(Nρ−1/2(log⁡T)2)\widetilde{O}(N\rho^{-1/2}(\log T)^2) for strongly convex losses. More importantly, the reduction does not directly yield guarantees in terms of the original VTV_T and FTF_T. In contrast, our method establishes regret bounds depending on the smaller of the VTV_T-dependent and FTF_T-dependent terms without additional horizon-dependent logarithmic factors. This distinction is particularly significant for strongly convex losses, where our guarantee depends on log⁡(2+min⁡VT,FT)\log(2+\min\\{V_T,F_T\\}) rather than log⁡T\log T, 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 FTF_T and VTV_T at a fixed time horizon. On ECL, we vary FTF_T while keeping VTV_T nearly unchanged (Table 2). On MNIST, we vary VTV_T while keeping FTF_T fixed (Table 3). In both cases, regret increases as the corresponding quantity grows, highlighting the practical relevance of both FTF_T and VTV_T 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.

Reviewer_HPxrOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a new algorithm for decentralized online convex optimization, named DOFTRL-GT, and provides static regret bounds for it that account for cumulative loss FTF_T and cumulative gradient variation VTV_T. The paper also provides general lower bounds on the static regret using FTF_T and VTV_T. The proposed algorithm combines existing methods including delay-compensated optimism, block-wise updating, and accelerated gossip and gradient tracking. A main contribution is in observing that such combination can lead to interesting regret bounds.

Critical strengths
  1. The DOFTRL-GT algorithm is non-trivial. It combines optimistic learning and gradient tracking techniques to obtain regret guarantees that account for cumulative loss and cumulative gradient variation.

  2. The analysis of DOFTRL-GT regret is interesting. Even though similar proofs exist in centralized online convex optimization, their extension to decentralized optimization is non-trivial.

  3. The derived regret lower bounds are important and have utility beyond the proposed algorithm.

Critical weaknesses
  1. This work provides analysis only on the static regret. Since the loss function in decentralized optimization can change dramatically over time, a static optimizer is a rather weak comparator. Even though FTF_T and VTV_T represent a valid attempt to capture the dynamics of the system, a static regret bound with them is still quite far from a proper dynamic regret bound.

  2. The paper could provide more motivation on why using FTF_T and VTV_T can provide more meaningful or useful regret bounds than using TT alone. Are FTF_T and VTV_T likely to be small in decentralized optimization?

  3. The motivation of the algorithm design can be more detailed to help the readers to understand the research gap. The proposed algorithm is complicated with many ingredients. It is not straightforward to see why introducing these ingredients enables the derived regret bounds, and why existing algorithms may not achieve similar bounds.

  4. Theorem 6 provides a lower bound only for FTF_T that satisfies M32≤ρFTαR2≤3πM128\frac{M}{32}\leq \frac{\sqrt{\rho}F_T}{\alpha R^2} \leq \frac{3\pi M}{128}. Since small-loss is an explicit motivation for this work, it would be interesting to know what happens when FT<MαR232ρF_T < \frac{M \alpha R^2}{32\sqrt{\rho}}. In that regime does DOFTRL-GT still provide nearly regret-optimal performance?

Questions for authors
  1. Is it possible to provide dynamic regret bounds for DOFTRL-GT?

  2. Can you demonstrate the practical benefit of these new regret bounds with FTF_T and VTV_T, in comparison with existing bounds using only TT?

  3. Is it possible for existing decentralized online convex optimization algorithms to also have static regret bounds with FTF_T and VTV_T?

4 comments

Q1: Why focus on static regret with FTF_T and VTV_T under time-varying losses, and is it possible to provide dynamic regret bounds for DOFTRL-GT?

A: Our work focuses on problem-dependent static regret, which remains meaningful for time-varying losses, while our current analysis does not directly establish dynamic regret bounds for DOFTRL-GT.

Specifically, Section 5 shows that our gradient-variation guarantee yields an O(1/T)O(1/T) ergodic rate for decentralized offline optimization when VT=0V_T=0, and our SEA results further exploit stochastic variance and temporal variation. Moreover, our newly added MNIST experiments vary only the arrival order of the same images, keeping FTF_T unchanged while producing different VTV_T and substantial differences in static regret (Table 3 on page 10 and Figure 3 on page 42 of the revised manuscript). These results demonstrate the benefit of exploiting benign loss sequences even with a fixed comparator.

Extending DOFTRL-GT to dynamic regret is an interesting direction but presents additional challenges. Our optimistic FTRL analysis relies on a fixed comparator, whereas time-varying comparators introduce path-length terms PTP_T that affect learning-rate selection. Furthermore, the doubling trick in Appendix F adapts to observed block-gradient variation but does not directly accommodate the generally unknown PTP_T. Controlling these additional terms together with decentralized tracking errors may require further algorithmic and analytical developments. We have already identified dynamic and adaptive regret as future directions in the original Conclusion.

Q2: Why can FTF_T and VTV_T provide more meaningful regret bounds than TT alone, are they likely to be small in decentralized optimization, and can their practical benefits be demonstrated?

A: Our FTF_T- and VTV_T-dependent bounds can provide tighter guarantees than horizon-dependent bounds because these quantities can be much smaller than TT in benign decentralized environments. Specifically, VT=0V_T=0 for stationary local objectives, even when the objectives differ across agents, while FTF_T can be small when a common fixed predictor achieves low cumulative loss across the network. Although these quantities need not be small for arbitrary loss sequences, they capture favorable properties that TT alone cannot reflect.

To demonstrate their practical benefits, we conduct controlled experiments on ECL and MNIST. On ECL, we vary FTF_T while keeping VTV_T nearly unchanged and observe increasing regret as FTF_T grows (Table 2 and Figure 2). On MNIST, we change only the arrival order of the same images, keeping FTF_T fixed while varying VTV_T. Smaller VTV_T leads to substantially lower regret (Table 3 and Figure 3). Since TT remains fixed in both experiments, these differences cannot be captured by bounds depending only on the time horizon.

Furthermore, the applications in Section 5 demonstrate the theoretical benefits of our problem-dependent guarantees. For decentralized offline optimization, VT=0V_T=0 yields an O(1/T)O(1/T) ergodic convergence rate, improving upon the O(T−1/2)O(T^{-1/2}) rate implied by worst-case static regret bounds. In the SEA setting, our guarantees exploit cumulative stochastic variance and adversarial variation instead of relying solely on TT. To better illustrate these benefits, we have added the controlled experiments in Section 6 (pages 9-10) and Appendix H.1 of the revised manuscript.

Q3: Is it possible for existing decentralized online convex optimization algorithms to also have static regret bounds with FTF_T and VTV_T?

A: Obtaining regret bounds governed by FTF_T and VTV_T rather than TT from existing D-OCO methods is difficult without algorithmic modifications and more refined analysis. Methods such as DOGD [1], DODA [2], and AD-FTGL [3] typically rely on gradient magnitudes in their analyses, leading to horizon-dependent regret bounds. Simply introducing optimism is insufficient, since network disagreement and decision movement may still introduce terms accumulating with TT.

Another possible approach is to combine Wan's [4] black-box reduction from D-OCO to centralized delayed OCO with a centralized optimistic learner. However, as noted in Section 1.1 (Related Work) of our original manuscript, this reduction requires the consensus errors to be sufficiently small (O(1/T)O(1/T)) to prevent their accumulation over the horizon, leading to a gossip length of B=Θ(ρ−1/2log⁡(TN))B=\Theta(\rho^{-1/2}\log(T\sqrt{N})). Thus, even with a centralized optimistic learner, the reduction introduces additional log⁡T\log T dependence and does not directly yield guarantees in terms of the original VTV_T and FTF_T. This is particularly significant for strongly convex losses, where our goal is logarithmic dependence on VTV_T or FTF_T.

In contrast, our designed delay-compensated optimism and difference-based two-level gradient tracking jointly control prediction errors and network disagreement through block-gradient variation V^Z\widehat V_Z, using a horizon-independent block length B=Θ(ρ−1/2log⁡N)B=\Theta(\rho^{-1/2}\log N). Moreover, negative stability absorbs decision movement in the convex case, while growing curvature controls it in the strongly convex case. This enables us to relate V^Z\widehat V_Z to the original VTV_T or FTF_T without introducing additional horizon-dependent terms.

References.

[1] 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.
[2] S. Hosseini, A. Chapman, and M. Mesbahi. Online Distributed Optimization via Dual Averaging. IEEE CDC, pp. 1484–1489, 2013.
[3] 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.
[4] Y. Wan. Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments. COLT, pp. 5605–5631, 2025.

Q4: The motivation of the algorithm design could be more detailed, given its complexity and the unclear role of its ingredients in achieving the regret bounds.

A: We have revised Section 3 (pages 4–8) to better explain the motivation behind our algorithm design and how its components lead to the regret guarantees.

The main challenges are that blockwise communication delays network-wide gradient information, making standard optimistic predictions unavailable, while existing D-OCO analyses bound gradient-estimation errors through gradient magnitudes rather than temporal differences. To address these challenges, we design delay-compensated optimism to handle delayed gradients and difference-based two-level gradient tracking to estimate both block and cumulative gradients. These mechanisms jointly control prediction errors and network disagreement through block-gradient variation, enabling regret bounds that adapt to VTV_T and FTF_T, unlike existing magnitude-based analyses.

To clarify these connections, we have refined the opening discussion of Section 3 to better articulate the technical challenges and limitations of existing approaches. We have also revised the explanations of the two coupled mechanisms and the step-by-step description of Algorithm 1 to clarify their respective roles and how they work together. Finally, we have refined the proof sketch in Section 3.2 to make the connections between the proposed mechanisms, block-gradient variation, and the resulting problem-dependent regret bounds easier to follow.

Q5: Theorem 6 provides a lower bound only for FTF_T that satisfies M32≤nFTαR2≤3πM128\frac{M}{32} \leq \frac{\sqrt{n} F_T}{\alpha R^2} \leq \frac{3 \pi M}{128}. Since small-loss is an explicit motivation for this work, it would be interesting to know what happens when FT<Mα2R232nF_T < \frac{M \alpha^2 R^2}{32\sqrt{n}}. In that regime does DOFTRL-GT still provide nearly regret-optimal performance?

A: DOFTRL-GT retains its small-loss regret guarantee for all FT≥0F_T\geq 0, although Theorem 6 does not establish near-optimality for arbitrarily small FTF_T. This restriction concerns only our strongly convex lower-bound construction. In contrast, Theorem 5 establishes the convex small-loss lower bound for any budget f≥0f\geq 0.

Specifically, our strongly convex construction in Appendix D.3 uses MM active blocks followed by a stationary tail. The heterogeneous quadratic losses create communication-induced hardness while incurring a positive comparator loss in each active block. Consequently, Equation (83) shows that FT=Θ(MαR2/ρ)F_T=\Theta(M\alpha R^2/\sqrt{\rho}), which explains the range in Theorem 6. Importantly, MM is a freely chosen construction parameter, so choosing smaller MM allows the lower bound to cover smaller small-loss scales.

For FTF_T below the range covered by this construction, Theorem 2 still guarantees O~(Nρ−1/2log⁡(2+FT))\widetilde O(N\rho^{-1/2}\log(2+F_T)) regret, up to additive terms independent of TT and FTF_T. Thus, the algorithm continues to benefit from small comparator loss. However, our current lower bound does not establish matching optimality in this extreme regime. We therefore restrict our near-optimality claim to the problem-dependent regimes covered by Theorem 6.

I would like to thank the authors for responding to my questions. Although I remain somewhat critical about using static regret as a performance metric, I am positive about this work and will maintain my current score.

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

The paper studies decentralized online convex optimization (D-OCO) under benign loss sequences. Motivated by the limitation of existing works only analyzing worst-case regret bounds, the authors leverage delay-compensated optimism and two-level gradient tracking via accelerated gossip to boost D-OCO for applications like small gradient variation or small comparator loss. The authors carry out rigorous theoretical analysis of their approach, obtaining regret bounds and lower bounds for it when the loss is strongly-convex or convex.d

Critical strengths

Inspired by advances in centralized classical online convex optimization (OCO), where it has been shown that gradient variation bounds yield improved guarantees when the gradients change slowly over time, while small-loss bounds improve when the best fixed comparator incurs a small cumulative loss, the authors aim to extend these algorithmic improvement to decentralized networks (D-OCO). This extension appears to be timely in the literature, and the theoretical analysis appears rigorous.

Critical weaknesses
  1. The paper is not accompanied by any numerical experiments, and it is hard to appreciate the significance of the regret guarantees and the lower bounds without them.

  2. The main theoretical contributions of the paper in Secs. 3 and 4 are hard to follow.

Questions for authors
  1. How is the arg⁡min⁡x∈X\arg\min_{x\in\mathcal{X}} in Line 4 for Alg. 1 solved at every iteration? What is its time complexity?

  2. Can you provide references for the choices in Eq. (4), which are mentioned to be common?

  3. Have there been attempts to relax some of the assumptions in Sec. 2 in the literature? D-OCO papers seem to require restrictive assumptions, i.e., (i) bounded parameter space ∣x∣2≤R\lvert x \rvert_2 \le R, (ii) bounded gradients ∣∇ft,i(x)∣2≤G\lvert \nabla f_{t,i}(x) \rvert_2 \le G, and (iii) μ\mu-strong convexity. This is while many other directions on (offline) decentralized optimization do not require any of those assumptions.

5 comments

Q1: Lack of numerical experiments

A: We thank the reviewer for this valuable comment. To better illustrate the significance of our theoretical results, 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.

More importantly, to illustrate the significance of exploiting benign loss sequences, we design controlled experiments to examine the effects of FTF_T and VTV_T at a fixed time horizon. On ECL, we vary FTF_T while keeping VTV_T nearly unchanged (Table 2). On MNIST, we vary VTV_T while keeping FTF_T fixed (Table 3). In both cases, regret increases as the corresponding quantity grows. These findings highlight the relevance of both quantities in characterizing benign loss sequences and provide empirical support for considering the smaller of the FTF_T-dependent and VTV_T-dependent regret bounds, allowing our method to benefit from either favorable regime.

Furthermore, we conduct additional MNIST experiments in the decentralized offline optimization and stochastically extended adversarial (SEA) settings, further demonstrating the benefits of exploiting benign environmental structures.

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.

Q2: The main theoretical contributions of the paper in Secs. 3 and 4 are hard to follow.

A: We thank the reviewer for this helpful suggestion. We have revised Sections 3 and 4 of the manuscript to make the theoretical contributions and the ideas behind them easier to follow.

In Section 3 (pages 4--8), we have clarified the technical challenges motivating the algorithm design and explained how delay-compensated optimism and two-level gradient tracking address them. We have also revised the step-by-step explanation of Algorithm 1 to clarify what each tracking mechanism estimates, how the two mechanisms interact, and how their outputs support the optimistic update. In addition, the revised proof sketch explains how prediction errors and network disagreement are controlled through block-gradient variation and how this quantity is subsequently related to VTV_T and FTF_T.

In Section 4 (pages 8--9), we have added an opening explanation of the lower-bound constructions, highlighting how they exploit communication delays while controlling VTV_T or FTF_T. We have also revised the discussions following the theorems to clarify their implications, particularly the different network dependencies and the problem-dependent regimes in which the lower bounds nearly match our upper bounds.

Q3: How is the arg⁡min⁡x∈X\arg\min_{x\in\mathcal X} in Line 4 for Alg. 1 solved at every iteration? What is its time complexity?

A: Thank you for the question. At the start of each block zz, each agent solves the constrained arg⁡min⁡\arg\min in Line 4 of Algorithm 1 by rewriting it as an equivalent Euclidean projection. The per-update time complexity is that of one standard Euclidean projection onto X\mathcal X, as in distributed online gradient descent [1,2]. Each agent performs one decision update per block, for a total of T/BT/B updates.

Specifically, the first-order optimality condition and the definition of the normal cone NX(x)N_{\mathcal X}(x) yield the following equivalences:

&x=x_i(z)=\arg\min_{u\in\mathcal{X}} \left\\{ \left\langle s_i(z-2)+2y_i(z-2),u\right\rangle +\frac{z\alpha+2h}{2}\lVert u\rVert_2^2 \right\\}\\\\ &\quad\Longleftrightarrow\quad 0\in s_i(z-2)+2y_i(z-2)+(z\alpha+2h)x+N_{\mathcal{X}}(x)\\\\ &\quad\Longleftrightarrow\quad -\frac{s_i(z-2)+2y_i(z-2)}{z\alpha+2h} \in (I+N_{\mathcal{X}})(x)\\\\ &\quad\Longleftrightarrow\quad x=\Pi_{\mathcal{X}}\\!\left( -\frac{s_i(z-2)+2y_i(z-2)}{z\alpha+2h} \right). \end{aligned}$$ Here, the second equivalence uses $z\alpha+2h>0$ and the fact that $N_{\mathcal X}(x)$ is a cone. The last follows from the resolvent identity $\Pi_{\mathcal X}=(I+N_{\mathcal X})^{-1}$. *References.* [1] 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. [2] Z. Tu, X. Wang, Y. Hong, L. Wang, D. Yuan, and G. Shi. Distributed Online Convex Optimization with Compressed Communication. *NeurIPS*, 35, pp. 34492–34504, 2022. >**Q4: Can you provide references for the choices in Eq. (4), which are mentioned to be common?** **A:** The "common" choice mainly refers to the mixing coefficient $\theta$, which follows the accelerated gossip method of Liu and Morse [1] and the contraction result of Ye et al. [2, Proposition 1], and is also adopted in [3–5]. The block length $B=\Theta(\rho^{-1/2}\log N)$ has the same order as in Wan et al. [3,4], while its specific constants are chosen to ensure the contraction $q\le(14N)^{-1/2}$ required by our two-level gradient-tracking analysis (Appendix B, Eq. (26)). We have added the relevant citations before Eq. (3) (originally Eq. (4)) in the revised manuscript. *References.* [1] J. Liu and A. S. Morse. Accelerated Linear Iterations for Distributed Averaging. *Annual Reviews in Control*, 35(2), pp. 160–165, 2011. [2] H. Ye, L. Luo, Z. Zhou, and T. Zhang. Multi-Consensus Decentralized Accelerated Gradient Descent. *JMLR*, 24(306), pp. 1–50, 2023. [3] Y. Wan, T. Wei, M. Song, and L. Zhang. Nearly Optimal Regret for Decentralized Online Convex Optimization. *COLT*, pp. 4862–4888, 2024. [4] 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. [5] H. Qiu, M. Zhang, and N. Cesa-Bianchi. Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach. *COLT*, 2026.

Q5: Have there been attempts to relax some of the assumptions in Sec. 2 in the literature? D-OCO papers seem to require restrictive assumptions, i.e., (i) bounded parameter space ∥x∥2≤R\lVert x\rVert_2 \leq R, (ii) bounded gradients ∥∇fi,t(x)∥2≤G\lVert\nabla f_{i,t}(x)\rVert_2 \leq G, and (iii) μ\mu-strong convexity. This is while many other directions on (offline) decentralized optimization do not require any of those assumptions.

A: Offline decentralized optimization and decentralized OCO address different problem settings. The former optimizes a fixed objective, whereas we study cumulative regret under potentially adversarially changing losses, with each decision made before the current loss is revealed. The bounded-domain and bounded-gradient assumptions are standard in online convex optimization [1–4] and are widely adopted in existing decentralized OCO studies. We also clarify that strong convexity is not required by DOFTRL-GT. Theorem 1 covers general convex losses (α=0\alpha=0), while Theorem 2 addresses strongly convex losses (α>0\alpha>0).

There have also been efforts to relax standard assumptions in online learning. In particular, Yan et al. [5] show that global LL-smoothness can be relaxed to smoothness on the (G/L)(G/L)-neighborhood of X\mathcal X. All our results remain valid under this relaxed assumption, as we have explicitly clarified after Assumption 3 in the revised manuscript. Recent advances in online learning have explored relaxing bounded-domain and bounded-gradient assumptions [6,7]. We have also included parameter-free decentralized OCO as a future research direction in the Conclusion of the revised manuscript.

References.

[1] E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, 2(3–4), pp. 157–325, 2016.
[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.
[3] Y.-H. Yan, P. Zhao, and Z.-H. Zhou. Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach. NeurIPS, pp. 37682–37715, 2023.
[4] C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu. Online Optimization with Gradual Variations. COLT, pp. 6.1–6.20, 2012.
[5] Y.-H. Yan, P. Zhao, and Z.-H. Zhou. A Simple and Optimal Approach for Universal Online Learning with Gradient Variations. NeurIPS, pp. 11132–11163, 2024.
[6] A. Jacobsen and A. Cutkosky. Unconstrained Online Learning with Unbounded Losses. ICML, pp. 14590–14630, 2023.
[7] H. Qiu, A. Jacobsen, E. Esposito, and M. Zhang. Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory. ICML, pp. 102119–102146, 2026.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.