Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors present an application of Douglas-Rachford for consensus optimization in federated learning. Their algorithm, unlike in prior work, explicitly handles subsampled clients, bounded delays, and also provides guarantees under for hypoconvex problems (smooth but not necessarily convex). 

main_review: 
The authors present a version of Douglas-Rachford that supports bounded delays and client subsampling for federated optimization. The techniques (stochastic approximation of the DR operator via client subsampling, and dealing with bounded delays) are more or less standard, and the results are not surprising.

Questions/comments:
- The authors claim that FedSplit and FedPD do not allow for sub-sampling among clients (e.g. ll. 53-54, ll 66-67, of the submission). However, it is unclear to me that FedSplit and FedPD are non-convergent under client subsampling; are the authors claiming that if these algorithms are modified to allow random sub-selection of devices/agents/users/clients on each round, that these algorithms will not converge? 
- ll.103-104 is technically incorrect, FedSplit is an application of Peaceman-Rachford, not Douglas-Rachford; although similar, the latter is an "averaged" version of Peaceman-Rachford. 
- Can the authors comment on the convergence properties of FedDR with random subsampling of the clients/users under more standard complexity assumptions (e.g. F is convex (but not necessarily strongly convex) and smooth / F is strongly convex and smooth; in the latter case, FedDR should be able to attain linear convergence in expectation)? 
- It would be useful to state a corollary of Theorem 3.1 in the case alpha = 1, eta = c/L, and p_i = 1/n (uniform sampling), which corresponds to standard Douglas-Rachford with uniformly sampling and the optimal selection of the step-size. 
limitations_and_societal_impact: See the questions & comments section above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a new method for federated learning with a nonconvex but smooth objective function. The proposed method is based on Douglas Rachford Splitting to decompose the objective and randomized coordinate methodology to allow a random selection of users to update at each iteration. An extension to asynchronous settings is presented, allowing modeling of communication delays and similar practical considerations. The convergence of these methods (potential using inexact proximal calculations) is bounded by the typical O(\epsilon^-2) rate. Reasonable numerics are given showing the potential effectiveness of such a scheme on synthetic and real datasets.
main_review: -The use of $G_\beta(\tilde x)$ in Definition 2.2 as a stochastic quantity is confusing. In (4), $G_\beta(x)$ is defined deterministically. Is this definition meaning that a stochastic approximation of $G_\beta(x)$ generated by some algorithm is small? Or is $\tilde x$ not a point in the domain of $F$ but rather a random variable that tends to have small $G_\beta(\tilde x)$?

-The intuition for each $x_i$ and $y_i$ used in FedDR rely on the series of reformulations presented in Appendix A. Including some interpretation of these quantities in the main text would help readability.

-It is interesting that the different components do not need to be sample uniformly in Assumption 3.1. Some intuition on how varied $p_i\neq p_j$ is handled without leading to bias would be helpful.

-Deferring the full statement of convergence results to the appendix is disappointing. Guarantees under inexact proximal evaluations are one of the works claimed contributions but do not appear anywhere in the main text.
In particular, a full description of the cost of an inexact method would include the cost of the SGD subroutine employed to approximate each strongly convex subproblem. This cost seems particularly important to include since the $\epsilon_{i,k}$ choice recommended in the appendix is quite small (namely, $\epsilon/(k+1)$). Including such costs would likely lead to a runtime worse than the claimed $O(\epsilon^-2)$ rate.
limitations_and_societal_impact: The paper discusses the important challenges to federated learning in terms of privacy concerns and homogeneity assumptions upfront. The work makes some modest progress towards designing methods around these societal impacts but is primarily focused on computational advances rather than societal ones.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 
This paper proposes FedDR and asyncFedDR for FL, which combines DRS and the randomized BCD strategy. Detailed convergence guarantees are also provided, which seems clear and correct to me. The authors also provide numerical results to support their theoretical claims.
main_review: 
Major concerns:

1. My first concern is regarding the inexactness evaluations of \prox_{\eta f_i}.

   (1) First, in theorems 3.1 and 4.1, it would be much better if that fact that the error tolerances \eps_{i, k} should be square summable (which is stated in the proof in the appendix). 

   (2) Secondly, in order to have square summable error tolerances, more and more inner loops (e.g., SGD or other solvers) are needed to solve these subproblems. This would make the total stochastic gradient complexity to be quite high. Note that what's presented in theorems 3.1 and 4.1 is the outer iteration complexity. 

   (3) A possible remedy is to apply warm-start on each subproblem and only solve it for a fixed number of iterations. Then, there will be a "bounded relative error", which will not hurt the overall 1/K convergence rate. 

This idea has been applied in the following analysis of inexact preconditioned PDHG (or equivalently, ADMM). More specifically, please refer to Theorem 4 of this paper: 

Liu, Yanli, Yunbei Xu, and Wotao Yin. "Acceleration of Primal–Dual Methods by Preconditioning and Simple Subproblem Procedures." Journal of Scientific Computing 86.2 (2021): 1-34.

Since the analysis in the above paper also depends on a Lyapunov function, which looks quite similar to this work (Lemma A.5 and Lemma B.1). I think that this may help improve the overall stochastic gradient complexity of this work.

(4) In the experiments, it should also be mentioned how many inner loops of SGD are applied in FedDR, asyncFedDR, as well as other algorithms. And a comparison of stochastic gradient complexity should be provided, in addition to the communication complexity presented. 

Minor concerns:
1. The analysis also looks similar to those of ARock ([33] in this paper), where the bounded delay is also assumed and a Lyapunov type analysis is done, would you please provide some comparisons? 
2. On line 63, [nonsmooth] seems to be a typo.
3. On line 79, early should be earliest. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes FedDR, which extends FedSplit by allowing non-convex objective, partial participation and convex composite regularizers. This work also studies the asynchronous variant of FedDR. Detailed proofs and experiments are provided.
main_review: I would like to express my appreciation for your submission to NeurIPS 2021. This paper is overall well-written and I enjoyed reading it. This paper proposes FedDR which differs from existing works FedSplit, FedPD by allowing non-convex objective, partial participation and convex composite regularizers.  My main concerns are as follows:

1. The algorithm FedDR requires an inner solver to compute the proximal operator of f. Although the authors kindly provide an inexact variant that allows for inexact approximation of prox_f, the additional inner computation is still not factored into the overall complexity. Therefore, it is hard to calibrate the complexities of FedDR with other first-order canonical algorithms such as FedAvg. (I acknowledge the same complain could apply to other prior works along this line such as FedPD and FedSplit.)

2. This paper is mostly compared with the FedSplit and FedPD literature. However, as noted on line 128, the composite federated optimization has been explored by [45, Federated Composite Optimization] for the convex case. Though I agree with the author’s claim that FedDR is different from the algorithms in [45], this paper misses necessary comparisons with [45] either theoretically or empirically. For example, how does FedDR compare with [45] (theoretically and empirically) when the objective f is convex? 

3. The theorem 3.1 is somewhat concerning as the constant C still depends on the hyperparameter $\alpha$ and $\eta$. Is it possible to state a cleaner bound with specific variables $\alpha, \eta$ so that the dependency can be eliminated? 

limitations_and_societal_impact: See the main review section for limitations that needs improvement.
review_title: null

Meta-review: Federated learning algorithms based on operator splitting or ADMM are more sophisticated than simple algorithms such as FedAvg or FedProx, and they bring more flexibility and rigor in algorithm design. The proposed FedDR method and its asynchronous versions extends the classical Douglas-Rachford splitting method, combining with randomized block-coordinate updates, to the federated learning setting with nonconvex loss functions. 

The idea of applying operator splitting methods to federated learning has been proposed in a few recent works, but the reviewers are supportive of the generality and technical results obtained in this paper. They make solid contribution to the Federated Learning literature. 
Decision: Accept (Poster)