Generalized Resource-Aware Distributed Minimax Optimization

We thank the reviewer Wn7T for the time and valuable feedback! We would try our best to address the comments one by one.

Response to Weakness1 & Question1:

Thank you for your insightful comments. We would like to clarify that both Eq. 1 and Eq. 2 represent distributed minimax optimization problems. In Eq. 1 (page 1), we present the general formulation of the distributed minimax problem, which aims to minimize the maximum average loss across all clients. Building on this, Eq. 2 (page 2) incorporates resource constraints and extends the formulation to a general global model optimization. The constraint in Eq. 2 is specifically designed to address the limited resources available at the local client level, while from a global perspective, the optimization goal remains to solve a distributed minimax problem. And we admit that SubDisMO is a solution for solving a distributed minimax optimization problem.

Response to Weakness2:

Thank you very much for the insightful and valuable comments.

(1) In Section 3, we define that the resource-aware adaptive mask $m_{q,n}$ is generated from policy $P(\theta_q; R_n)$, where $R_n$ represents the resource constraints of client $n$.

(2) From the theoretical aspect, resource budget affects the minimum covering rate $\mathcal{C}^*$ and the noise induced from the mask bounded by $l$. As shown in Corollary 1, $\frac{1}{Q}\sum_{q=1}^Q \sum_{i \in \mathcal{K} _ q} \mathbb{E}\left[\|\nabla f^i(\theta _ q)\|^2\right] \leq \mathcal{O}\left(\frac{A _ 0}{\sqrt{QT\mathcal{C}^*}} + \frac{l^2 B _ 0}{\mathcal{C}^*} + \frac{\sigma _ g^2}{\mathcal{C}^*} + \frac{\sigma _ l^2}{TQ} + \frac{1}{\sqrt{TQ\mathcal{C}^*}}\right)$, high budgets lead to more clients training larger submodels, so that $\mathcal{C}^*$ is larger, and $l$ is smaller, which will speed up the model convergence.

(3) From the empirical experimental aspect, we evaluate the impact of varying resource budgets. Section 5.3 presents the impact of $\mathcal{C}^*$. And when the resource budgets across clients are high, all clients train bigger submodel, so $\mathcal{C}^*$ is larger, and vice versa. Figure 4 shows when the resource budget is high, the larger $\mathcal{C}^*$ is, the performance and convergence rate are both improved.

Response to Weakness3:

We are sorry for our unclear presentations. We improve the presentation of the experiment figures and the modified ones are presented in the revised paper.

Response to Question2:

Thanks for your detailed comments.

(1) In our method design, we give the random mask as a mask policy example and present the theoretical analysis. It shows the superior convergence rate and generalization error bound of the proposed method in solving the general distributed minimax optimization problem. And based on SubDisMO, we can change to any submodel construction method.

(2) Following your advice, we change the policy to a rolling mask, and the results are shown as follows. We can see that although we changed the rolling mask policy, the performance is not absolutely better. The rolling step and the overlap rate also impact the performance of the global model. When the new local submodel overlaps 50% from the last one, the performance is better than no overlap. That's because different policies lead to different $\mathcal{C}^*$, and as we present in Corollary 1, a larger $\mathcal{C}^*$ leads to a better convergence rate, which further effects the model performance.

If there are any further questions, we are happy to clarify and try to address them.

Dear Reviewer Wn7T,

Thanks a lot for your time in reviewing and reading our response and the revision. Thanks very much for your valuable comments. We sincerely understand you're busy. But as the window for discussion is closing, would you mind checking our responses and confirming whether you have any further questions? We look forward to answering more questions from you.

Best, Authors

Thanks for your response. The results of rolling masking and random masking are confusing to me. In [1], the rolling masking is better than the random masking. Besides, in their experiments, they did not consider the ratio of overlapping. Can authors make further explanations about this?

[1] Alam, Samiul, et al. "Fedrolex: Model-heterogeneous federated learning with rolling sub-model extraction." Advances in neural information processing systems 35 (2022): 29677-29690.

First, we sincerely thank you very much for your recognition of our work. We would try our best to improve our work following the comments.

Response to Weakness1&Question1:

Thank you very much for the insightful comments. Considering that each deep network includes multiple operations and computations, we commonly use the amount of computation (FLOPS) to analyze the time complexity and the number of parameters to analyze the space complexity. The results of each process are shown as follows. In comparison to state-of-the-art distributed learning algorithms, where each client needs to train the full model, our proposed method allows each client to train only a submodel. This significantly reduces both the computational load and the number of parameters, thereby improving efficiency in terms of both computation and storage.

Response to Weakness2&Question2:

Thank you very much for the insightful comments. Here we explore the scalability of our proposed algorithm SubDisMO. In these experiments, we test scenarios with 100 and 1000 clients. We repartition the data for each client under Dir($\alpha=1.0$) on CIFAR-10. To compare scalability performance, we conduct the same experiments on RAM-Fed. The figure about the convergence curve is added on Page 21 in the revised paper. And the numerical results are shown as follows. It's noticed that as the number of clients increases, the performance decreases. The reason is that as the number of clients increases, the number of data in each client will decrease, which further affects the performance of the local model. In summary, it demonstrates that our proposed SubDisMO can scale well in extremely large-scale distributed systems.

If there are any further questions, we are happy to clarify and try to address them.

We thank the reviewer haCk for the time and valuable feedback! We would try our best to address the comments one by one.

Response to Weakness1:

Thank you very much for the insightful comments. We carefully revised the proof of Theorem 1 and noticed that in Appendix C the proof of Theorem 1 on page 14, the scaling of the inequality is indeed inappropriate, which leads to your first concern. And we attentively adjust the inequality and derive the learning rate conditions. Detailed process can be found on pages 14-19 of the revised manuscript. Thus, we can conclude that when the learning rates satisfy the following conditions, and the assumption of constant $L$ can be cancelled.

$\begin{aligned} 16\eta_l^2L^2T^2\leq1\Rightarrow\eta_l\leq\frac{1}{4LT}\\\\ 32\eta_l^2T^2\frac{N}{\mathcal{C}^*}L^2\leq \frac{1}{16} \Rightarrow \eta_l\leq\frac{\sqrt{\mathcal{C}^*}}{16TL\sqrt{N}}\\\\ 96L^3\eta_l^3\eta_gT^3\frac{N}{\mathcal{C}^*}\leq \frac{1}{16} \Rightarrow \eta_g\leq\frac{2\sqrt{N}}{\sqrt{\mathcal{C}^*}}\\\ 3L\eta_l\eta_g T\leq \frac{1}{16} \Rightarrow \eta_l\eta_g\leq\frac{1}{48TL} \end{aligned}$

About your second concern, based on the above modified conditions of learning rates, we carefully choose $\eta_l = \frac{1}{\sqrt{Q}}$ and $\eta_g = \frac{\sqrt{\mathcal{C}^*}}{\sqrt{T}}$, and perturbation radius $\delta$ proportional to the learning rate, e.g., $\delta = \frac{1}{\sqrt{Q}}$, the convergence rate can be expressed as follows $\frac{1}{Q}\sum_{q=1}^Q \sum_{i \in \mathcal{K} _ q} \mathbb{E}\left[\|\nabla f^i(\theta _ q)\|^2\right] \leq \mathcal{O}\left(\frac{A _ 0}{\sqrt{QT\mathcal{C}^*}} + \frac{l^2 B _ 0}{\mathcal{C}^*} + \frac{\sigma _ g^2}{\mathcal{C}^*} + \frac{\sigma _ l^2}{TQ} + \frac{1}{\sqrt{TQ\mathcal{C}^*}}\right)$ where $A _ 0 = \mathbb{E}[f(\theta_1)]$, $B _ 0 = \frac{1}{Q}\sum_{q=1}^Q \mathbb{E}[f(\theta _ q)]$. The main term of the revised bound is identical to the original Corollary 1.

So, we can find that the convergence rate is identical to that of the original manuscript, $\mathcal{O}(\frac{1}{\sqrt{QT\mathcal{C}^*}})$. We have highlighted all the changes in the revised version, and we sincerely hope that you can find our response satisfactory.

Response to Weakness2:

Thank you very much for the insightful comments. As we mentioned on Page 3, the proposed SubDisMO gives a new insight into solving distributed minimax optimization, especially under resource-limited scenarios. When $\mathcal{C}^*=N$ that is all the clients train the full model, SubDisMO achieves the same convergence rate $\mathcal{O}(1/\sqrt{QTN})$ as FedSAM. That is FedSAM is a special case of our SubDisMO when each client trains the full model. And the results of FedSAM are reported in the Page 8, Table 1 from the original manuscript.

Response to Question1:

Thank you very much for your comments. (1) Indeed, as stated in Theorem 1, a smaller value of $\delta$ leads to a tighter bound. However, it is important to note that this bound is about the averaged gradient. A smaller averaged gradient does not necessarily imply better experimental performance. Instead, it indicates that the algorithm can converge more quickly to a critical point. (2) Furthermore, in Section 5.3, we explore the impact of $\delta$, and give the empirical results. It can be seen that the performance would not definitely improve as $\delta$ gets smaller, varying with different datasets. Thus, it is necessary to select the appropriate $\delta$ through empirical experiments.

Thank you very much for the insightful comments.

(1) First, the original paper of FedAvg and FedSAM that you mentioned all utilized the convolution architecture model, such as CNN and ResNet, whose model architecture is quite different from ours (ViT, Transformer models). In our work, we employed ViT-small and ViT models on CIFAR-10 and CIFAR-100. We newly conduct experiments using ResNet18 on CIFAR-10 with Non-IID data distribution Dir($\mu=1.0$). The new results are shown as follows and our proposed method SubDisMO achieves 76.34% accuracy and outperforms all the baselines with submodels.

(2) Additionally, we have trained using both transformer-based architectures and convolution-like model ResNet in a centralized way, which can be considered as the upper bound of the experimental performance. We can see that our proposed method SubDisMO can achieve a satisfactory level compared with the centralized models.

If there are any further questions, we are happy to clarify and try to address them. Thank you again and your recognition means a lot for our work.