Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary: 
The paper considers a distributed variant of online convex optimization problem over multiple players, where, at each trial t, convex loss_l_t.i is revealed to player i and but evaluated by sum of loss functions sum_i=1^n l_t,i. The players can communicate with their neighborhood and share their decisions. Under the problems setting and some assumption on the neighborhood graph structure, the authors prove regret bounds for convex/strongly-convex losses and full-info/bandit settings. Specifically, the paper allows the algorithm to violate domain constraints but the sum of violation has to be sublinear in the number of trials. They also show the violation bounds simultaneously. 


Comments:
The key assumption is Assumption 4, that the players share a doubly-stochastic matrix which is used to mix neighbors’ decisions. This assumption allows to mix all players’ decisions in a long run and the derived regret bounds make sense. The theoretical results are non-trivial. 

As a summary, I feel the results are beyond standard previous work and has certain values. Note that I have not evaluated correctness of the results, but the results are likely under Assumption 4. 

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: The authors study distributed online convex optimization where the distributed system consists of various computing units connected by a time varying graph. The authors prove optimal regret bounds for a proposed decentralized algorithm and experimentally evaluate the performance of their algorithms on distributed online regularized linear regression problems.

The paper seems well written and well researched and places itself well in context of current literature. The authors also improve the state of the art in the field. The main weakness of the paper is the limited experimental evaluation and applicability of the assumptions and the theoretical setting that underpins this work.

[Edit: After going through the other reviews, I have downgraded my score. The revised version of the paper the authors uploaded is 23 pages long with the main paper body being 10 pages. The CFP instructs reviewers to apply a higher standard to judge such long papers. I  am not convinced that the paper is solving an important problem that merits such a long paper.]
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper considers distributed online convex optimization with long-term constraints, which extends Yuan & Lamperski (2018)’s work to decentralized case with time-varying directed network. The authors propose DOCO frameworks (full-information and one-point bandit feedback) based on augmented Lagrangian functions. They also provide the corresponding regret bounds for both strongly and non-strongly convex cases. The experiments on synthetic data validate the effectiveness of proposed algorithms.

The problem setting of this paper is interesting and the theoretical contribution is nice, but the empirical studies could be improved:

1. It is prefer to append some experiments on real-world applications.

2. Although the regret bound of DOCO is better, the projection step is expensive. Can you compare the running time of DOCO with projection-free algorithms?

review_title: Official Blind Review #2

Meta-review: The paper proposes  a decentralized algorithm with regret for distributed online convex optimization problems. The reviewers worry about the assumptions and the theoretical settings, they also find that the experimental evaluation  is insufficient.
Decision: Reject