Anarchic Federated Bilevel Optimization

Thank you for your comments.

W1: In the experiments, the authors claim the proposed AFBO is the most efficient algorithm. However, more explanation should be added about why the proposed method is more efficient than ADBO in the experiment since the ADBO is also an asynchronous algorithm.

A1: Based on your comment, in the revised paper, we have added more experiment results in Section B.3, Section B.4, Section B.5, and Section B.6. of the supplement material. We conduct experiments on the convergence of different algorithms under different inner and outer loop delays, comparison of AFBO and AFL, and the impact of asynchronous delays, etc., discussed as follows. For the inner loop asynchronous delays experiments, the results show that AFBO performs best among all algorithms. In addition, it shows that all algorithms expect AFBO to suffer an obvious convergence degeneration as there exists an inner loop asynchronous delay. Among them, synchronous algorithms (e.g., SDBO, FedNest, and Prometheus) degenerate much more than AFBO and ADBO. Moreover, we find that convergence degeneration is much more obvious in the non-IID MINIST dataset than in the IID MINIST dataset. This is because the bias of using the most recent update of a client is much larger in the non-IID MINIST dataset case than in the IID MINIST dataset case. Intuitively, a reusing of past gradients inducts a new bias of SGD, as some of the SGD gradients use more than others. Finally, it shows that the convergence degeneration in the Covertype dataset is slighter than in the MINIST dataset. The experiments on comparison between AFBO and AFL shows that AFL performs worse on bilevel tasks than AFBO, but they have a similar convergence rate as they both use the most recent updates to update the global model and achieve a linear speed-up. The experiment on the impact of asynchronous delays on AFBO shows that the test accuracy becomes smaller as the asynchronous delay increases, which matches our theoretical results. In addition, there is little convergence degradation due to the asynchronous delay, which proves the effectiveness and robustness of AFBO. Moreover, it shows that the convergence degradation under the non-IID MINIST dataset is slightly higher than under the IID MINIST dataset. This is because the contribution of all clients is equal in the IID dataset which means the straggler has low effects on the test accuracy, but some clients owning unique datasets under non-IID dataset settings with higher asynchronous delay can cause a larger convergence degradation due to straggler effects.

W2: More experimental results should be added to show the excellent performance of the proposed AFBO.

A2: Based on your comment, in the revised paper, we have added more experiment results in Section B.3, Section B.4, Section B.5, and Section B.6 of the supplement material. Please refer to our response to A1 for detailed discussion of these results.

W3: Lack of analysis for the communication complexity of the proposed method.

A3: Based on your comment, in the revised paper, we have added analysis of the communication complexity of the AFBO algorithm (in Corollary $1$'s Remark, marked in blue): “In addition, we need $T=O(\kappa^5_g\epsilon^{-2}/n)$ to achieve an $\epsilon$-accurate stationary point. Compared with FedNest (Tarzanagh et al., 2022), our complexity has the same dependence on $\kappa$ and $\epsilon$, but a better dependence on $n$ due to the linear speedup."

Dear reviewer: We have added responses to your comments. Could you take a look and let us know if you have any further comment? Thanks.

Thank you for your comments.

W1: The experiment results are limited. Authors are recommended to compare the performance of the proposed algorithm with algorithms such as [1]. In addition, the idea itself is similar to [2]. Authors are therefore recommended to elaborate more on the difference between this work and existing ones in the literature. In addition, in all figures, it is seen that the performance of AFBO is only slightly better than ADBO.

[1] Prometheus: Taming sample and communication complexities in constrained decentralized stochastic bilevel learning. ICML 2023 [2] Anarchic Federated Learning ICML 2022

A1: Based on your comment, in the revised paper, we have added more experiment results in Section B.3, Section B.4, Section B.5, and Section B.6. of the supplement material, discussed as follows. We conduct experiments on the convergence of different algorithms under different inner and outer loop delays, for comparison of AFBO and AFL, and for the impacts of asynchronous delays, etc. For the inner loop asynchronous delays experiments, the results show that AFBO performs best among all algorithms. In addition, it shows that all algorithms expect AFBO to suffer an obvious convergence degeneration as there exists an inner loop asynchronous delay. Among them, synchronous algorithms (e.g., SDBO, FedNest, and Prometheus) degenerate much more than AFBO and ADBO. Moreover, we find that convergence degeneration is much more obvious in the non-IID MINIST dataset than in the IID MINIST dataset. This is because the bias of using the most recent update of a client is much larger in the non-IID MINIST dataset case than in the IID MINIST dataset case. Intuitively, a reusing of past gradients inducts a new bias of SGD, as some of the SGD gradients use more than others. Finally, it shows that the convergence degeneration in the Covertype dataset is slighter than in the MINIST dataset. The experiments on comparison between AFBO and AFL shows that AFL performs worse on bilevel tasks than AFBO, but they have a similar convergence rate as they both use the most recent updates to update the global model and achieve a linear speed-up. The experiment on the impact of asynchronous delays on AFBO shows that the test accuracy becomes smaller as the asynchronous delay increases, which matches our theoretical results. In addition, there is little convergence degradation due to the asynchronous delay, which proves the effectiveness and robustness of AFBO. Moreover, it shows that the convergence degradation under the non-IID MINIST dataset is slightly higher than under the IID MINIST dataset. This is because the contributions of all clients are equal in the IID dataset setting which means the straggler has low effects on the test accuracy, but some clients owning unique datasets under non-IID dataset settings with higher asynchronous delay can cause a larger convergence degradation due to straggler effects.

There are some major differences of this paper compared to [2], discussed as follows (we have added some discussion on the differences compard to [2] in Section 2.1 of the revised paper, marked in blue). While [2] considered conventional single-level learning, the AFBO algorithm of this paper focuses on a bilevel learning problem, which is very different and much more complicated than the single-level learning problem. Specifically, bilevel optimization needs to estimate the hyper-gradient $\nabla \Phi$. In the distributed setting, this is more challenging than for the single-level learning, since we have $\frac1M\sum_{i=1}^M\frac{\partial F_i(x,y)}{\partial y}\frac{\partial y}{\partial x}\neq\frac{\partial F(x,y)}{\partial y}\frac{\partial y}{\partial x}$, so that $\nabla \Phi \neq \frac1n\sum_{i=1}^N \nabla \Phi_i$. As a result, AFBO needs to estimate $\nabla \Phi$ using a distributed estimator, given by $H_i(x^t,y^{t+1})=\triangledown_x f_i(x^t,y^{t+1};\phi_i^t)-\triangledown^2_{xy}g_i(x^t,y^{t+1};\rho_i^t)\times\left[\frac{N}{l_{g,1}}\prod_{l=1}^{N_i}(I-\frac1{l_{g,1}}\triangledown_{yy}^2g_i(x^t,y^{t+1};\zeta_i^t))\right]\times\triangledown_yf_i(x^t,y^{t+1};\xi_i^t)$. Then we can aggregate $H_i(x^t,y^{t+1})$ to estimate $\nabla \Phi$. Therefore, the AFBO algorithm involves two loops: an inner loop that updates the lower-level variable $y^{t,k}$, and an outer loop that updates the upper-level variable $x^t$. This is a very different algorithm structure compared to the AFL algorithm in [2] which only involves one loop. Moreover, the AFBO algorithm allows for maximum freedom for clients by taking into account various anarchic settings: partial participation and asynchronous participation in both the inner and outer loops, and also different local iteration numbers in the inner loop.

Dear reviewer: We have added responses to your comments. Could you take a look and let us know if you have any further comment? Thanks.

Dear Reviewer 3dLq,

The authors have answered your comments. Please read their responses as soon as possible (if you haven't) and reply here if you think the authors have addressed your concerns (maybe some of them). For example, I personally think the setting of [2] is definitely different from this paper and the challenge the authors mention make sense. Of course, I am not sure if the technical analysis (provig technique) is significantly different due to the new challenge, which I expect you to judge as a reviewer. Please update your rating if you have changed your evaluation, or mention that you want to keep your rating.

Thank you so much.

Area Chair

Dear reviewer: We have added responses to your comments. Could you take a look and let us know if you have any further comment? Thanks.

Thank you for your comments!

Q1: This paper used impractical assumptions. In particular, it assumes the gradient of g is upper bounded and g is strongly convex. A strongly convex quadratic function does not satisfy those two assumptions simultaneously.

A1: First, we do not assume that the gradient of the lower-level local objective function $g_i$ is upper bounded. We only assume (in Assumption 4) that the variances of the 1st order and 2nd order stochastic gradients of function $g_i$ is bounded (i.e., $E_{\zeta}\left[ \left\|\triangledown g_i(z; \xi) - \triangledown g_i(z)\right\|^2\right]\le \sigma^2_{g,1}$, $E_{\zeta}\left[ \left\|\triangledown^2 g_i(z; \xi) - \triangledown^2 g_i(z)\right\|^2\right]\le \sigma^2_{g,2}$). This is a common assumption used in existing works on bilevel optimization (BO) including federated bilevel optimization (FBO), such as [1]-[5], [7]-[10]. For clarity, we have renamed Assumption 4 as “Bounded variance of local stochastic gradient”.

Another assumption (Assumption 5) we make for function $g_i$ is that the variance between local gradients and the global gradient is bounded (i.e., $\mathbb{E} \left [\left\|\triangledown g_i(z) - \triangledown g(z)\right\|^2 \right] \le \sigma_g^2$). This is also a widely used assumption in existing works on BO including FBO, such as [1]-[4], [7]-[9].

In addition, in Lemma 6 we show that the second-order moment of the hyper-gradient $H_i$ is upper bounded, i.e., $\mathbb{E}\left[\left\|H_i(x^t,y^{t+1}) \right\|^2|F^t\right] \le \hat{D}_f$. Note that this is not an assumption, but it is a result derived from Assumption 4. This is a widely used result in existing works on BO including FBO, such as [2]-[5], [7]-[10].

Indeed, you are correct that for an arbitrary strongly convex function $g$ such as a quadratic function, its gradient norm cannot be upper bounded. However, our paper does not assume that the gradient norm of the low-level objective function $g$ is bounded, and thus it does not contradict the assumption that $g$ is strongly convex.

Moreover, a few recent works, such as [6], consider a non-strongly-convex lower-level objective function $g$ (which can be non-convex or weakly-convex). In this setting, it is challenging to find the optimal solution of the lower-level optimization problem (there may exist multiple optimal solutions). Therefore, the convergence analysis in these works usually cannot achieve a reasonable performance guarantee. We will explore AFBO for the non-strongly-convex setting in our future work.

[1] "Anarchic Federated Learning", ICML'22

[2] "Achieving Linear Speedup in Non-IID Federated Bilevel Learning", ICML'23

[3] "A Single-Timescale Method for Stochastic Bilevel Optimization", AISTATS'22

[4] "Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems", NeurIPS'21.

[5] "SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning", NeurIPS'23.

[6] "Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond", NeurIPS'21.

[7] "Communication-Efficient Federated Bilevel Optimization with Global and Local Lower Level Problems", NeurIPS'23.

[8] "On the Convergence of Momentum-Based Algorithms for Federated Bilevel Optimization Problems", arxiv.

[9] "Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms", NeurIPS'23.

[10] "Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiation", ICML'23.

Q2: There are some fatal errors. In particular, this paper denotes $\overline{H}(x^t,y^{t+1}) := \mathbb{E}[\frac1m\sum_{i \in \mathcal{M}}\overline{H}_i(x^{t-\tau_i^t}, y^{t-\tau_i^t+1})$. Then, in convergence analysis, the authors directly use $x^t$ rather than $x^{t-\tau_i^t}$, e.g., the second equation when proving lemma 1. This is totally wrong.

A2: The formula does not mean that $x^t=x^{t-\tau_i^t}$. Here $x^t$ and $x^{t-\tau_i^t}$ are the global models of $x$ in outer rounds $t$ and $t-\tau_i^t$, respectively, where $\tau_i^t$ is the asynchronous delay of client $i$ in the outer round $t$. In general, we have $x^t\neq x^{t-\tau_i^t}$, since the server updates the global model $x^t$ in each outer round. Therefore, in the second equation of Lemma 1's proof, we should use $x^t$ rather than $x^{t-\tau_i^t}$. To clarify the meaning, we have revised the formula as $\overline{H}^t := \mathbb{E}[\frac1m\sum_{i\in\mathcal{M}}\overline{H}_i(x^{t-\tau_i^t}, y^{t-\rho_i^t+1})]$. We are sorry for this confusion.

Dear reviewer: We have added responses to your comments. Could you take a look and let us know if you have any further comment? Thanks.

Dear Reviewer PRRM,

The authors have answered your comments. Please read their responses as soon as possible (if you haven't) and reply here that if you still think there is a fatal error. If the authors have addressed your concerns (maybe some of them), please update your rating if you have change your evaluation. Thank you so much.

Thanks, Area Chair