Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Paper considers distributed online convex optimization over an N-agent network. In particular, the authors consider three settings: full-feedback, where agents have access to the loss function, and (single- and two-point) bandit feedback, where agents only possess the values of the loss at points around the decision.

This work extends the DAOL method to accommodate compressed communication, and provides the first no-regret guarantees for w-contracted compressed distributed online optimization.

Gossip occurs over undirected networks with doubly-stochastic mixing. Numerical results provided for the diabetes detection dataset, using a simple online logistic-regressor with l2-regularization. 
strengths_and_weaknesses: Strengths:
Originality & Significance: while the proposed method is highly incremental, the analysis in this work is sufficiently original, and to the best of my knowledge, provides the first no-regret guarantees for w-contracted compressed distributed online optimizers.

Clarity & Quality: the work is clear, well written, and technically sound. Additionally, numerical results support theoretical intuition (i.e., that full-feedback and double-point bandit feedback have similar regrets, which are significantly better than single-point banding feedback). Additionally, advantage of proposed method compared to exact communication DAOL is well-established, improved convergence with respect to transmitted bits, at the cost of slightly worse time-horizon convergence.

Weaknesses:
Incremental algorithm: Method is an extension of DAOL to allow for compressed communication using standard compression schemes. Moreover, the method for dealing with compression is directly borrowed from the error-feedback framework.

Assumptions: For the full-feedback setting: requires the bounded gradient assumption in the convex setting (however this can be eliminated it for strongly-convex objectives).

Unfortunately, the experiments do not directly demonstrate the advantage of sparse communication topologies on the convergence speed, as the fully-connected network in Figure 3 still exhibits the best regret with respect to the transmitted bits.


questions: * Should certainly cite [1] when discussing difference compression schemes for distributed optimization. Also note that randomized gossip is typically used to refer to the classic pair-wise averaging with random edge activation of Boyd et al. [2].

* The numerical results are interesting, but do not directly convey the advantage of decentralized learning, since fully-connected topologies still achieve the best regret with respect to the number of transmitted bits. It was shown in [3] that time-varying directed graphs can be used to improve the mixing speed of decentralized optimization algorithms over undirected graphs. Please discuss extensions to this setting, and I would be curious if push-sum based gossip (column stochastic) could be used instead of the doubly stochastic mixing to improve the numerical results in Figure 3.

[1] Karimireddy et al., Error Feedback Fixes SignSGD and other Gradient Compression Schemes, ICML 2019.
[2] Boyd et al., Randomized gossip algorithms, IEEE transactions on information theory 2006.
[3] Assran et al., Stochastic Gradient Push for Distributed Deep Learning, ICML 2019.
limitations: Limitations are addressed in the conclusion (namely the dependence on the compression ratio in the regret bounds).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper applies the data compression scheme to the GD-based distributed online algorithms. Three algorithms are proposed and analyzed with difference-compressed communication schemes. Explicit regret bounds are derived in closed form. 
strengths_and_weaknesses: The idea of the paper is simple, while the algorithm design and analysis are complicated. The paper is well written. 

The paper claims that "algorithm design and theoretical principle are challenging since the compression error, projection error, and consensus error will be coupled", which is not very clear yet. For example, distributed convex optimization with compressed communication has been studied recent years; what is the challenge when moving from convex optimization to convex online optimization with compressed communication? 
questions: 1. Distributed convex optimization with compressed communication has been recently studied. What is the key difference/novelty in algorithm design for online optimization problems when compressed communication is applied?

2. Without compressed communication, distributed convex online optimization has been well studied for time-varying graphs. Is it hard to extend from a fixed graph to a time-varying graph for the current algorithms?

3. Stepsizes in the paper are designed with constant parameters given in the assumptions. It is usually not needed for standard single agent cases, nor distributed convex (online) optimization without compressed communication. Such parameter involvement requires the machines know more about the underlying problem, which is sometimes unavailable. Is this because of the purpose of analysis? 
limitations: NA
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes compressed distributed online convex optimization algorithms with full information feedback, one-point, and two-points bandit feedback.
strengths_and_weaknesses: The paper proves the convergence of the proposed methods and provides computational evidence for the methods. 
questions: Unfortunately, the paper is out of my area of research and expertise. 
limitations: No limitations are found.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This work is an augmentation of distributed online gradient descent that uses an update-difference based compression scheme to reduce the communications load. Sublinear regret is proved for the case that objective functions are convex and strongly convex. Numerical evaluations establish the practicalities of the proposed approach.
strengths_and_weaknesses: 
The numerical experiments only consider weak baselines, in the sense that they do not compare against ADMM or primal-dual method. Perhaps this is not the point, as the authors would like to underscore that the difference based compression is the best among a collection of alternatives. However, ECD-AMSGrad is a weak comparator, and many communication-efficient versions of ADMM or primal-dual method are available in the literature. See, for instance:

Ling, Qing, Yaohua Liu, Wei Shi, and Zhi Tian. "Weighted ADMM for fast decentralized network optimization." IEEE Transactions on Signal Processing 64, no. 22 (2016): 5930-5942.

Bedi, A. S., Koppel, A., & Rajawat, K. (2019). Asynchronous saddle point algorithm for stochastic optimization in heterogeneous networks. IEEE Transactions on Signal Processing, 67(7), 1742-1757.

Lines 29-38: The authors only talk about local and global regret. However, in this setting, one should also talk about the tradeoff between global regret and constraint violation in the sense of consensus error, so as to make the link with primal-dual method and ADMM, which have rigorous and extensive theoretical support that they are superior to distributed gradient descent-based techniques. That this line of literature is overlooked completely so that a DOGD based development can be pursued is evidence to me that the paper exhibits some substantial gaps between the proposed algorithm and the state of the art. 

Koppel, A., Jakubiec, F. Y., & Ribeiro, A. (2015). A saddle point algorithm for networked online convex optimization. IEEE Transactions on Signal Processing, 63(19), 5149-5164.

Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, 3(1), 1-122.

Moreover, there are specific corrections of DGD that close the gap between it and approaches based on duality, which are also overlooked:

Shi, Wei, et al. "Extra: An exact first-order algorithm for decentralized consensus optimization." SIAM Journal on Optimization 25.2 (2015): 944-966.


Line 41: There are much more related works than [7]-[9] in the study of decentralized online convex optimization. Moreover, references [8] and [9] appear to be about constrained settings which are not particularly pertinent here. 

questions: How do the developed regret bounds here compare against the tightest possible bounds in the literature? How is the compression ratio related to error in the gradient estimation error of the Lagrangian of the consensus-constrained optimization problem? How is it related to the error bound condition that is well-known in the mathematical programming literature (see many of Paul Tseng's works)? 

Luo, Z. Q., & Tseng, P. (1993). Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 46(1), 157-178.

Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010). Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4), 922-938.
limitations: 
The authors propose to employ difference compression together with DGD in order to come up with a communication-efficient algorithm. What I do not see is any technical novelty beyond applying this compression technique to a previously existing setting. Put more succinctly, there is no specific algorithmic innovation beyond applying a previously compression technique to a previously existing setting, and analyzing the error incurred by compression. For this reason, I do not believe this paper meets the bar for technical creativity/novelty required for NeurIPS.
review_title: null

Meta-review: metareview: This paper studies a decentralized online learning algorithm that uses compressed communication and achieves the same regret (order-wise) as an analogous method which would not use any compressed communication. Several reviewers noted that the idea and formulation are straightforward, but the analysis is technically involved. It is this analysis that constitutes the main contribution of this work. After discussion with the reviewers, I am of the opinion that the contributions of this paper are sufficiently relevant and the work contains sufficient technical novelty to justify acceptance to NeurIPS.

The responses to reviewers helped to clarify several points of concern in the initial reviews. Please make sure to revise your paper for the camera ready deadline taking these suggestions into account. In particular,
* Several reviewers noted relevant related work that ought to be cited
* Clarify the differences with the error-feedback framework
* Limitations and future work regarding how sparsity of the topology impacts overall communication overhead
* Discuss potential extensions to time-varying graphs
confidence: Less certain
Decision: Accept