- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2(+1)
Read review
Paper summary
The paper considers decentralized nonconvex nonsmooth opitmization and proposes an online to nonconvex conversion algorithm with client data sampling using multinomial distribution along with Chebyshev acceleration. The paper shows analytically that the proposed method can achieve an (,)-Goldstein stationary point with efficient complexity and communication bounds. Numerical results have been provided to show the performance of the proposed method.
Critical strengths
Decentralized nonconvex and nonsmooth optimization is a highly compelling topic that arises in various practical applications (e.g., machine learning). Developing efficient methods for such problems is therefore essential. The paper presents an algorithm with a thorough analytical convergence analysis to a (δ,ϵ)-Goldstein stationary point, with derived bounds on communication and computation complexity.
Critical weaknesses
-
The proposed algorithm appears to be a combination of existing methods : client data sampling in known in Federated Learning literature, chebyshev acceleration is also known as well as online to nonconvex conversion.
-
The client data sampling cannot be considered as decentralized : an entity doing the client sampling is required.
-
It is not clear how this method is specifically tailored to nonsmooth optimization: the analysis in the paper is conducted mainly for the smooth case, and the extension to the nonsmooth setting relies on a result from Sahinoglu & Shahramour 2024. Moreover, the smooth-case analysis follows standard tools, and the specific challenge involved in proving the results is not made explicit.
-
The numerical results are insufficient to demonstrate superiority over prior work. An improvement shown only on MNIST is not convincing, and it is unclear whether the experiments use IID or non-IID data distributions across clients (non-IID being more common in practice). Results on additional datasets (e.g., CIFAR) are needed. Furthermore, an ablation study is required: since the proposed algorithm combines client data sampling and Chebyshev acceleration, the ablation study must show the gain achieved by each component.
Questions for authors
-
The paper should discuss further how the client data sampling can be implemented in a decentralized way.
-
The challenges involved in proving the results in Lemmas 3, 4, 5, and 7 must be highlighted, as the proofs appear to follow standard tools.
4 comments
Official Comment by Authors (2/2)
W3: It is not clear how this method is specifically tailored to nonsmooth optimization: the analysis in the paper is conducted mainly for the smooth case, and the extension to the nonsmooth setting relies on a result from Sahinoglu & Shahramour 2024. Moreover, the smooth-case analysis follows standard tools, and the specific challenge involved in proving the results is not made explicit.
R3: We emphasize that the algorithm and analysis of Sahinoglu & Shahramour [3] results an an explicit dependence in the complexity bound (see Table 1). In contrast, we introduce a new proposed scheme by coupling FastGossip with a shared interpolation coefficient across all clients (Lines 5–6 of Algorithm 1), achiving the logarithmic dependence on . Please refer to paragraph Logarithmic dimension dependence and the shared interpolation coefficient in R1 for details.
W4-1: The numerical results are insufficient to demonstrate superiority over prior work. An improvement shown only on MNIST is not convincing, and it is unclear whether the experiments use IID or non-IID data distributions across clients (non-IID being more common in practice). Results on additional datasets (e.g., CIFAR) are needed.
R4-1: We conduct experiments under a heterogeneous (non-IID) data setting. Specifically, we partition the dataset among clients according to class labels, each client contains at most data of one label. For the examples of MNIST and Fashion-MNIST (10 classes), we assigned one class of data to each of the 10 client.
We also provide additional experimental results on the CIFAR-10 dataset in Appendix F (1215–1241). The results in Figure 4 shows that the proposed DOC$^2$S outperforms the baseline method on all three metrics, which is consistent with our theoretical results.
W4-2: Furthermore, an ablation study is required: since the proposed algorithm combines client data sampling and Chebyshev acceleration, the ablation study must show the gain achieved by each component.
R4-2: We conduct ablation studies on the Fashion-MNIST dataset to evaluate the gain achieved by FastGossip and client-data sampling in Appendix G (1242–1276). Specifically, we compare our DOC$^2$S with mini-batch size with two baselines: DOC$^2$S by replacing FastGossip with ordinary mixing (DOC$^2$S-Mix) and ME-DOL by replacing ordinary mixing with FastGossip (ME-DOL-FG).
We present the experimental results in terms of sample complexity, computation rounds, and communication rounds in Figure 5. We can observe that FastGossip improves performance across all tested batch sizes. Additionally, with an appropriate mini-batch size, client–data sampling also outperforms the baseline ME-DOL-FG.
Q1: The paper should discuss further how the client data sampling can be implemented in a decentralized way.
A1: The client-data sampling is can be implemented in a decentralized way by using a shared random seed across all clients. Please refer to R2 for details.
Q2: The challenges involved in proving the results in Lemmas 3, 4, 5, and 7 must be highlighted, as the proofs appear to follow standard tools.
A2:
The main technical challenge arises in the proof of Lemma 7, which shows that the number of consensus steps only has logarithmic dependence on dimension .
As discussed in R1, our algorithm uses an identical interpolation coefficient shared by all clients, whereas existing method ME-DOL [3] draws independent for each client .
We greatly thank the reviewer's insightful suggestion. In our rebuttal revision, we have highlighted our novelty in lines 207–212 and 1176–1211.
References
[1] Quoc Tran Dinh, Nhan H. Pham, Dzung Phan, and Lam Nguyen. FedDR – randomized Douglas-Rachford splitting algorithms for nonconvex federated composite optimization. NeurIPS 2021.
[2] Krishna Pillutla, Yassine Laguel, Jérôme Malick, and Zaid Harchaoui. Federated learning with superquantile aggregation for heterogeneous data. Machine Learning 2024.
[3] Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. In ICML 2024.
[4] Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In ICML 2020.
[5] Weichao Mao, Lin F. Yang, Kaiqing Zhang, and Tamer Başar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In ICML 2022.
[6] Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Optimal gradient tracking for decentralized optimization. Mathematical Programming 2024.
Thank you for your detailed responses. I agree that shared randomness can be used to make the algorithm decentralised (thank you for this clarification). I noticed also that you have provided additional results using CIFAR-10 dataset. Regarding W1 and your reply: I maintain that the algorithm (not the analysis) is a combination of existing methods.
- client sampling is used in FL. The fact that it has been applied under some specific objective structures does not imply that using it in the context of this paper makes the method itself novel.
- The proposed algorithm is a combination of existing methods: online to nonconvex conversion., fast gossip, client data sampling.
- I believe the value of this paper is in showing numerically and analytically that this combination yields improvements as compared to prior work. I'll carefully re-read the proofs this week (especially Lemma 7) and compare them with the previous works (e.g [3]) to provide a final fair recommendation. I will increase the score if I see differences in the proof.
Thank you again for your efforts in replying to my comments.
Thank you for your careful reading and insightful response. We are pleased that you acknowledged our clarification of shared randomness and our additional experiments on CIFAR-10. However, we think it is inappropriate to regard our method as a combination of existing methods. We would like to further emphasize the novelty of our work in the following respects.
Q3: Client sampling is used in FL. The fact that it has been applied under some specific objective structures does not imply that using it in the context of this paper makes the method itself novel.
A3: Our method has the following essential difference from existing algorithms for FL in the specific nonsmooth nonconvex setting.
-
Note that existing methods for FL in specific nonsmooth nonconvex setting only include client sampling [1, 2], rather than client-data sampling. In other words, these methods require each client to access the exact local gradient, which is expensive in large-scale applications (In the specific weakly convex setting, paper [2] states that their method can use local stochastic gradients; however, no theoretical analysis is provided). In contrast, our method iterates with the more practical inexact local gradients, so that it includes an additional step of data sampling (line 229) after the step of client sampling (line 225) to construct local gradient estimates.
-
The proposed client-data sampling strategy is novel, which is based on multinomial batch allocation . This scheme guarantees each client receives samples in expectation. In the case of , our scheme is more computation efficient than the standard uniform sampling, i.e., all clients have the identical number of samples in each iteration. Note that in the case of , the uniform sampling requires each client receives sample (rather than ), resulting all clients receive sample in total. In contrast, our strategy still guarantees that each client receives samples in expectation and all clients receive sample in total. Please refer to A2-1 and A2-2 to Reviewer T9pn for details.
-
The use of shared interpolation coefficient is specific to the algorithm design for general nonsmooth nonconvex setting, which is novel and has not been proposed by previous works [1–3].
Q4: The proposed algorithm is a combination of existing methods: online to nonconvex conversion, fast gossip, client data sampling.
A4: As we mentioned in above responses, our method includes the new proposed client-data sampling strategy (see A3.1 and A3.2) and the shared interpolation coefficient (see R1.2 and A3.3), which are not introduced in previous works [1, 2, 3]. Hence, we think our method cannot be regarded as a combination of existing methods.
References
[1] Quoc Tran Dinh, Nhan H. Pham, Dzung Phan, and Lam Nguyen. FedDR – randomized Douglas-Rachford splitting algorithms for nonconvex federated composite optimization. In NeurIPS 2021.
[2] Krishna Pillutla, Yassine Laguel, Jérôme Malick, and Zaid Harchaoui. Federated learning with superquantile aggregation for heterogeneous data. Machine Learning 2024.
[3] Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. In ICML 2024.
Official Comment by Authors (1/2)
We thank the reviewer yQ8t for the detailed and helpful comments.
R1: The proposed algorithm is not a combination of existing techniques. We clarify the novelty of our method as follows.
The general nonsmooth nonconvex setting. To the best of our knowledge, existing algorithms with client(-data) sampling for nonsmooth nonconvex optimization require that the objective has some specific structure, e.g., the composite objective (smooth loss + nonsmooth regularization) [1] or weakly convexity [2]. In contrast, our method address the general nonsmooth nonconvex problem, which is more challenging.
Logarithmic dimension dependence and the shared interpolation coefficients.
We emphasize that our communication upper bound depends only logarithmically on the dimension d, while that of the baseline method ME-DOL [3] contains an explicit d dependence (see Table 1). This improvement comes from our new proposed scheme, that is, coupling FastGossip with a shared interpolation coefficient st across all clients, which can be implemented by using a shared random seed (see R2 for details).
Specifically our DOC$^2$S takes the shared st∼Unif([0,1]) across all clients (line 6 of Algorithm 1), which implies wt,i=xt−1,i+stvt,i and wˉt=xˉt−1+stvˉt. This results E[∣∣wt,i−wˉt∣∣]=E[∣∣xt−1,i−xˉt−1+st(vt,i−vˉt)∣∣]≤E[∣∣xt−1,i−xˉt−1∣∣]+E[st∣∣vt,i−vˉt∣∣]≤2ϵ′, where the last step uses Lemma 2 and Lemma 1 to bound the consensus error ∣∣xt−1,i−xˉt−1∣∣ and ∣∣vt,i−vˉt∣∣, respectively. According to the analysis in lines 1040–1050, we take H=O(Ld/μ) and require ϵ′=O(Hϵ)=O(Ldμϵ). Based on Lemma 1, the accuracy ϵ′=O(μϵ/(Ld)) can be achieved by setting the number of consensus steps as R=O(γ1/2log(1/ϵ′))=O(γ1/2log(Ld/(μϵ))), which only contains the logarithmic dependence on d.
On the other hand, existing method ME-DOL [1] takes independent st,i∼Unif([0,1]) across all clients, which implies wt,i=xt−1,i+stvt,i and wˉt=xˉt−1+(1/n)∑j=1nst,jvt,i. This results
\leq \mathbb{E}[||\mathbf{x}_{t-1,i}-\bar{\mathbf{x}}_{t-1}||] + \mathbb{E}\Big[\Big|\Big|s_{t,i}\mathbf{v}_{t,i}-\frac{1}{n}\sum_{j=1}^n s_{t,j}\mathbf{v}_{t,j}\Big|\Big|\Big].$$ Note that we cannot guarantee the term $||s_{t,i}\mathbf{v}_{t,i}-(1/n)\sum_{j=1}^n s_{t,j}\mathbf{v}_{t,j}||$ be arbitrary small even if $\mathbf{v}_{t,i}=\bar{\mathbf{v}}_t$ for every $i$, since the clients have different $s_{t,i}$. Hence, the upper bounds of ME-DOL include additional polynomial dependence on $d$, which cannot be avoided even by involving the Chebyshev acceleration. > **W2:** The client data sampling cannot be considered as decentralized: an entity doing the client sampling is required. **R2:** Our client-data sampling is indeed decentralized because each client can **locally** computes its own batch size by multinomial distribution from **a shared random seed**. In fact, the use of shared randomness is very popular in decentralized algorithms, e.g., Section 6 (page 9, paragraph "More efficient Moniqua") of [4], Section 2 (page 3, paragraph "Correlated policy") of [5], and Section 3 (page 9, after Remark 3) of [6]. Similarly, achieving the shared interpolation coefficient $s_t$ also can be implemented in this way. We greatly thank the reviewer for point this out. In our rebuttal revision, we have provided a discussion on the shared randomness in Remark 3 (line 259–263).