acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Online Exp-Concave Optimization

Abstract

Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of where is the number of agents, is the dimension, is the horizon, and represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded, and achieve logarithmic regret.

Primary area:
learning theory
Keywords:
online learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_ztzoOpenReview ↗
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
  1. 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.
  2. 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.
  3. 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
  1. 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.
  2. 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.
  3. 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.
  4. 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
  1. 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?
  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?
  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?
5 comments

1. 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?

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\frac{\mu}{2}\\|y-x\\|_2^2, where μ\mu 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.

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 NN agents into qq equal-sized clusters along a path. Its mixing matrix has spectral gap ρ=sin⁡2(π/(2q))=Θ(q−2)\rho=\sin^2(\pi/(2q))=\Theta(q^{-2}), independent of the cluster size N/qN/q. Consequently, NN can increase while the spectral gap remains fixed, and the spectral gap can vary at fixed NN through the admissible choices of qq. 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.
  1. 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.
  2. 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 LL used for Algorithm 1 on each of the three graphs in the experiments reported in Table 1?

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

This paper studies decentralized online convex optimization, where the loss function in online convex optimization is decomposed across nodes and communication between nodes is limited. In particular, the authors focus on the setting where the loss function at each node is exp-concave, for which it was previously unknown whether a polylogarithmic regret upper bound could be achieved. A naive application of the online Newton step, a common algorithm for online convex optimization with exp-concave losses, leads to a mismatch between the decision variables appearing in the negative terms of the regret upper bound and those naturally arising in the upper bound obtained through FTRL analysis. This mismatch prevents the negative terms from being effectively exploited to obtain the desired polylogarithmic regret bounds. The authors handle this difficulty by employing a mechanism based on FTRL under delayed feedback. They further extend their approach to decentralized online linear regression.

Critical strengths

One of the strengths of this paper is that it is generally well-written. The problem setting, algorithms, and overall overview of the analysis (particularly how it differs from existing analyses) are clearly explained. Moreover, the authors effectively combine existing techniques to resolve the difficulty of exploiting the negative term arising from the exp-concavity of loss function, succeeding in characterizing the (nearly) minimax-optimal regret for decentralized online exp-concave optimization. The technical arguments also appear to be sound.

Critical weaknesses

I believe that there are no critical major weaknesses in this paper. But there are several weaknesses I would like to point out.

One potential weakness is that both the upper and lower bounds are obtained largely using existing techniques. For example, the proof of the upper bound relies heavily on existing techniques. If I raise a new technical analysis point, Lemma 5 seems to be the difference from previous analyses, but this is not explained in the main text. Similarly, the regret lower bound seems to rely mostly on existing techniques. If there are any new technical challenges, it should be discussed in the main text, but it seems that the current Section 3.3 does not explain the technical difficulties. Nevertheless, combining existing techniques in an appropriate way is valuable in itself, and I do not consider this a major weakness of the paper.

There are also several minor points that I think should be addressed:

  • Definition 1, which concerns the communication matrix PP, should be stated as an assumption rather than a definition. It would also be helpful to discuss whether it is reasonable to assume that PP is symmetric and that the learners know PP (since the algorithm requires σ2(P)\sigma_2(P)).
  • There is a typo, "OCOz," in line 120.
  • In Algorithm 1, is it necessary to define both kxk_x and kgk_g?
  • The problem setting for decentralized online linear regression seems underspecified. For example, the authors should explicitly mention that yt,iy_{t,i} may be generated adversarially.
Questions for authors

The reviewer would like the authors to answer the questions raised in the above weaknesses. In particular, what are the main technical difficulties in proving the regret lower bound? Can the authors validate the assumptions on the communication matrix?

2 comments

1. What are the main technical difficulties in proving the regret lower bound?

Thank you for this question. Our proof builds on classical log-loss lower-bound ideas (Ordentlich and Cover, 1998) and information-propagation arguments (Scaman et al., 2017; Wan et al., 2025). The main technical task is to embed a dimension-dependent exp-concave hard instance into the decentralized feedback model while preserving the loss assumptions and tracking the network dependence.

We construct coordinate-wise logarithmic losses with bounded gradients and place them at nodes sufficiently far from the evaluated agent. Each loss is repeated within a block, during which its information cannot reach that agent. Consequently, the agent's block-averaged decision depends only on past outcomes and its internal randomness. Convexity then transfers the centralized lower bound to global regret against the same fixed comparator, with scaling determined by the number of informative nodes and the block length.

The new Theorem 4 in Appendix D further extends this argument to clustered paths, separating network size from spectral gap over the stated admissible family and strengthening the original cycle-based result.

2. There are also several minor points that I think should be addressed:

  • Definition 1, which concerns the communication matrix PP, should be stated as an assumption rather than a definition. It would also be helpful to discuss whether it is reasonable to assume that PP is symmetric and that the learners know PP (since the algorithm requires σ2(P)\sigma_2(P)).
  • There is a typo, "OCOz," in line 120.
  • In Algorithm 1, is it necessary to define both kxk_x and kgk_g?
  • The problem setting for decentralized online linear regression seems underspecified. For example, the authors should explicitly mention that yt,iy_{t,i} may be generated adversarially.

We have replaced Definition 1 with Assumption 4 and added a discussion of its feasibility and the information required by each learner. The matrix conditions can be satisfied on any fixed connected undirected graph G\mathcal{G} with NN vertices. Let INI_N denote the N×NN\times N identity matrix, LG\mathcal{L}_{\mathcal{G}} the combinatorial Laplacian of G\mathcal{G} (the degree matrix minus the adjacency matrix), and dmax⁡d_{\max} the maximum vertex degree of G\mathcal{G}. For example, the matrix P=IN−LG/[2(dmax⁡+1)]P=I_N-\mathcal{L}_{\mathcal{G}}/[2(d_{\max}+1)] is symmetric, positive semidefinite, and doubly stochastic, respects the graph structure, and satisfies σ2(P)<1\sigma_2(P)<1. We now explicitly assume that σ2(P)\sigma_2(P) is available during network setup, allowing the common gossip parameters to be computed before online learning. Each learner only needs its local mixing weights and these common parameters; full knowledge of PP at every learner is unnecessary.

We also addressed the other concerns in the updated revision, including the typos and a clarification on the setting of decentralized online linear regression. Please see the changes marked in orange in Sections 2 and 4 and in Algorithm 1 of the revised manuscript.

Thank you for your response and for revising the paper. I have no further questions and will maintain my current positive score.

Reviewer_4e2xOpenReview ↗
Rating
1(−1)
Confidence
3(+1)
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies exp-concave optimization in a decentralized online setting. The proposed algorithm combines Online Newton Step with block-based accelerated gossip and establishes a regret bound of O(Nd(1−σ2(P))−1/2log⁡2T)O(Nd(1-\sigma_2(P))^{-1/2}\log^2 T). By analyzing specific loss functions, the authors establish a regret lower bound of Ω(Ndα−1(1−σ2(P))−1/2log⁡(T/(Nd)))\Omega(Nd\alpha^{-1}(1-\sigma_2(P))^{-1/2}\log(T/(Nd))). Finally, the authors extend their approach to decentralized online linear regression without the bounded decision-domain assumption.

Critical strengths

The paper provides the first regret analysis for decentralized online optimization with exp-concave loss functions and establishes a reasonable logarithmic regret bound.

Critical weaknesses

The main contribution of this paper appears to be the extension of existing decentralized online optimization results from strongly convex to exp-concave loss functions. However, the paper provides limited discussion of the distinctive properties and practical applications of exp-concave losses. These aspects are also insufficiently covered in the related work section. More importantly, the authors do not sufficiently clarify the substantial technical challenges introduced by exp-concavity in the decentralized setting. The convergence analysis appears largely similar to existing analyses for decentralized online optimization with strongly convex losses, and centralized online optimization with exp-concave losses. At the algorithmic level, it remains unclear whether the proposed algorithm is specifically designed to exploit exp-concavity or mainly adapts techniques from prior work.

Questions for authors

The lower bound is established only for a specific class of exp-concave loss functions on a cycle graph. Therefore, the claimed near-optimality of the proposed regret bound is not fully convincing.

The final extension to decentralized online linear regression also appears to offer limited additional insights, and its significance as a separate contribution is unclear.

Please add experiments.

5 comments

1. What motivates studying exp-concave losses in decentralized online optimization, particularly their distinctive properties and practical applications, and what specific algorithmic and analytical advances does the proposed method offer beyond existing decentralized strongly convex and centralized exp-concave approaches?

Thank you for this comment. We have revised the Introduction to clarify the distinctive properties and applications of exp-concave losses. We have also revised Section 3.2 to explain how the analysis preserves exp-concave curvature and to clarify the roles of Lemmas 5 and 2. We elaborate on these points below.

Exp-concavity permits fast regret without uniform curvature in every direction. For example, on a bounded full-dimensional domain with bounded features and labels, the squared prediction loss ft(x)=12(ht⊤x−yt)2f_t(x)=\frac12(h_t^\top x-y_t)^2 is exp-concave, but its Hessian htht⊤h_th_t^\top has rank at most one and is not positive definite when d>1d>1. Thus, strongly convex guarantees do not directly cover even this basic regression problem. Relevant applications include online regression across sensor nodes, logistic regression with bounded prediction scores, and portfolio selection with logarithmic losses.

The algorithm explicitly exploits exp-concavity through the gradient-dependent quadratic term β2L⟨gi(s),xi(s)−x⟩2,\frac{\beta}{2L}\langle g_i(s),x_i(s)-x\rangle^2, whose accumulated curvature yields the second-order matrix ηId+βL∑s=1z−2gi(s)gi(s)⊤\eta I_d+\frac{\beta}{L}\sum_{s=1}^{z-2}g_i(s)g_i(s)^\top in the update of x^i(z+1)\widehat{x}_i(z+1). This directional curvature differs from the uniform quadratic curvature used in strongly convex analyses. Gossiping both block gradients and preparatory decisions controls the errors that perturb this term.

The analysis must preserve this curvature through two steps. First, Lemma 5 retains the negative quadratic correction when aggregating gradients evaluated at different agents' decisions and replacing exact averages by gossip estimates. Second, the resulting block-level expression contains a linear term evaluated at the preparatory decision and a quadratic term involving the executed decision. Consequently, a standard ONS regret bound for a single decision sequence cannot be applied verbatim. Lemma 2 verifies the required quadratic cancellation and stability bounds for these distinct decisions.

We explicitly build on existing blocking, accelerated gossip, and delayed ONS techniques, including the local-norm stability and potential arguments of Qiu et al. (2025). We believe that combining established techniques to obtain a new theoretical guarantee is itself a substantial contribution. Here, preserving exp-concave curvature through decentralized communication enables polylogarithmic regret with near-optimal network dependence in the stated worst-case sense.

2. The lower bound is established only for a specific class of exp-concave loss functions on a cycle graph. Therefore, the claimed near-optimality of the proposed regret bound is not fully convincing.

Thank you for this question. 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. This construction shares a similar spirit to the existing literature in decentralized online convex optimization (Wan et al. 2024; Wan et al. 2025).

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 NN agents into qq equal-sized clusters along a path. Its mixing matrix has spectral gap ρ=sin⁡2(π/(2q))=Θ(q−2)\rho=\sin^2(\pi/(2q))=\Theta(q^{-2}), independent of the cluster size N/qN/q. Consequently, NN can increase while the spectral gap remains fixed, and the spectral gap can vary at fixed NN through the admissible choices of qq. 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. The final extension to decentralized online linear regression also appears to offer limited additional insights, and its significance as a separate contribution is unclear.

Its purpose is to demonstrate that the proposed framework can be extended beyond bounded decision domains, where standard bounded-domain ONS analyses cannot be directly applied. In particular, the combination of ridge regularization, sufficient-statistic aggregation, and prediction clipping allows us to establish logarithmic regret in this unbounded-domain setting. We present this result as an extension of our decentralized framework to unbounded-domain regression. The new simulations in Section5 provide an empirical illustration of this extension.

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.

The motivating example is overly simplistic and does not justify the need for exp-concave methods. The proposed technique is straightforward and offers little novelty beyond existing methods for strongly convex losses.

I was very surprised that another reviewer gave this paper a Clear Accept. I initially gave a Weak Reject partly to encourage the students. However, given this situation, I have decided to change my rating to Clear Reject.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.