Communication-Efficient Federated Non-Linear Bandit Optimization

[Q1] Discussion on assumptions and their practical implications

Please find our answer to CQ1 in the common response for discussions about the assumptions made in our paper.

Here we want to emphasize that the function class defined by Assumptions 1-3 generalizes the parametric function classes studied in existing federated bandit papers (Wang et. al. 2020; Li and Wang, 2022a; He et. al., 2022; Li and Wang, 2022b), and also covers additional nonlinear, nonconvex functions that have not been considered in existing works in federated bandits. We want to emphasize that this is already a nontrivial improvement.

In terms of applicability in real-world scenarios, it is worth noting that linear and generalized linear models (both are special cases of ours) have already been shown to perform well in applications like news recommendation (Li et. al., 2010), and our generalization offers even more flexibility in the modeling choices during federated optimization, i.e., any parametric functions, including neural networks, that satisfy our local strongly convexity assumption.

[Q2] Comparison with decentralized machine learning methods

Thanks for the suggestion. We have added a section in Appendix B to discuss existing works in offline federated learning / decentralized machine learning to help further highlight the contribution of our paper.

However, we want to clarify that, due to the fundamental differences in the problem formulation and learning objectives between federated bandit learning and decentralized machine learning, direct comparison in theoretical analysis and experiments is not possible. Specifically, the focus of decentralized machine learning is to collaboratively learn a good point estimate over a fixed dataset, i.e., convergence to the minimizer with fewer communications/iterations, while federated bandit learning requires collaborative confidence set estimation for efficient regret reduction over a finite time horizon $T$.

One perspective to understand their relation is that federated bandit learning studies decision making over the whole time horizon $T$, while decentralized machine learning aims to solve the optimization problem on the dataset collected up to a fixed time step $t \in [T]$, i.e., the latter can be viewed as a component of the former. For example, in our Fed-GO-UCB algorithm, we can adopt any decentralized machine learning method as the Oracle to optimize Equation (2), but we still need the other components, e.g., confidence set construction (line 4) and OFU principle (line 3) for effective decision making. Therefore, these two are not directly comparable.

[Q3] The need for occasional communications may lead to inefficiencies or delays

We definitely agree with the reviewer that such communication “may lead to potential inefficiencies or delays”, but as discussed in our response to CQ2, in order to avoid the suboptimal regret $\tilde O(N \sqrt{T})$, communication among clients is necessary.

This is why we need a well-designed federated bandit optimization method like Fed-GO-UCB to attain a good tradeoff between the conflicting objectives of regret minimization and communication efficiency, i.e., we wish to have the most regret reduction per communication. We have shown both theoretically and empirically, that our Fed-GO-UCB algorithm achieved this goal for the federated bandit optimization of nonlinear functions.

[Q1] Novelty

As mentioned in the Technical novelties paragraph in Section 1, the approximation method from centralized non-linear bandit optimization (Liu and Wang, 2023) cannot be applied to the federated setting. Specifically, the confidence sets for the optimal parameter $\omega^\star$ constructed in (Liu and Wang, 2023) is $\{\omega: \lVert \omega - \hat \omega_t \rVert_{\Sigma_{t}} \leq \beta_{t}\}$, where $\Sigma_t =\lambda \mathbf{I} + \sum_{s=1}^{t} \nabla f_{x_s}(\hat \omega_{s}) \nabla f_{ x_s}(\hat \omega_{s})^\top$ and $b_t =\sum_{s=1}^{t} \nabla f_{x_s}(\hat \omega_{s}) \bigl[\nabla f_{ x_s}(\hat \omega_{s})^\top \hat \omega_{s} + y_s - f_{x_s}(\hat \omega_{s}) \bigr]$, where the gradients $\nabla f_{x_s}(\hat \omega_{s})$ have to be calculated w.r.t. the model $\hat \omega_{s}$ at step $s$.

Due to local model updates in federated settings, now each client $i$ has a different sequence of local models $\hat \omega_{s,i}$ for $s=1,2,\dots,t$. By directly aggregating the statistics $\Sigma_{t,i}$ and $b_{t,i}$ computed based on such $N$ different sequences of local models, one cannot obtain a valid confidence set. To address this issue, we improve the analysis of Liu and Wang (2023), and show that we can construct a valid confidence set using the gradients w.r.t. a common initial model $\hat \omega_0$, instead of clients’ locally updated ones.

Therefore, after obtaining $\hat \omega_0$ at the end of Phase I, the clients can collaborate on confidence set estimation via a common embedding function defined by the gradient $\nabla f_{x_s}(\hat \omega_{0})$. This is why we are able to utilize the communication protocol designed for federated linear bandits (Wang et. al. 2020). We want to emphasize that being able to utilize communication protocols designed for federated linear bandits for nonlinear functions via our novel confidence set construction is already non-trivial and may be of independent interest for future research. For example, one can also extend our method to asynchronous protocols (Li and Wang, 2022a; He et. al, 2022), as well as heterogeneous clients setting (Liu et. al. 2022). Moreover, as discussed in our response to CQ2, this new algorithm design helps us improve upon FedGLB-UCB (Li and Wang, 2022b) by a factor of $d_x \sqrt{N}$ for federated optimization of nonlinear functions, because in Phase II we are able to use the efficient closed-form update as federated linear bandits, instead of the expensive iterative optimization as FedGLB-UCB.

[Q2] Improvement compared with federated generalized linear bandits (Li & Wang, 2022b)

Yes, our paper has an $\tilde O(d_x \sqrt{N})$ improvement on communication cost thanks to the new algorithm design. Please see our answer to CQ2 in the general response for more details about how this is achieved.

[Q3] Tightness of communication cost upper bound

Please see our answer to CQ2 in the common response for discussions on the tightness of our communication cost upper bound in terms of $N$ and $T$.

Additional References

• Xutong Liu, Haoru Zhao, Tong Yu, Shuai Li, and John CS Lui. "Federated online clustering of bandits." In Uncertainty in Artificial Intelligence, pp. 1221-1231. PMLR, 2022.

[Q1] Additional discussions on related works

We agree with Reviewer emcJ that more detailed and comprehensive discussions on related works would better highlight the contribution of our paper, so in Appendix B we have added a section to discuss related works in federated bandit learning and offline federated learning, as well as a table summarizing existing federated bandit algorithms. Please also see our answer to CQ2 in the common response for a detailed discussion about theoretical comparison with existing works on federated bandit learning.

[Q2] Challenges of nonlinear function optimization

We want to clarify that the unique challenge addressed in this paper is bandit optimization of nonlinear functions under federated settings. We cannot view them separately as suggested by the reviewer. Specifically, federated setting requires communication efficiency, and bandit optimization of nonlinear functions requires construction of confidence sets. Therefore, the unique question answered in our paper is, how to construct confidence sets for the nonlinear functions collaboratively by all clients in a communication efficient manner, which cannot be addressed by prior works.

As mentioned in the Technical novelties paragraph in Section 1 of our paper, the approximation method we propose is a non-trivial extension of (Liu and Wang, 2023), i.e., their method cannot be applied to federated settings as their approximation relies on a sequence of continuously updated models $\hat \omega_{s}$ for $s=1,2,\dots,t$. But in federated settings, each client has a different sequence of locally updated models, which leads to difficulty in aggregating local statistics (see also our answer to Q1 of Reviewer yBxF). This problem does not exist for federated linear bandits, since the confidence set for linear models can be directly constructed using feature vector $x$, instead of gradient $\nabla f_{ x_s}(\hat{\omega}_{s})$.

To address this issue, we propose a new approximation procedure with improved analysis over Liu and Wang (2023), such that the statistics computed by all clients are now based on a common embedding function $\nabla f_{x_s}(\hat{\omega}_{0})$, i.e., the gradient w.r.t. the shared model $\hat \omega_0$. Note that $\hat \omega_0$ is obtained at the end of Phase I and then always remains fixed.

Compared with prior works in federated linear bandits, which conveniently enjoys closed-form solutions, nonlinear function faces another challenge, i.e., it requires iterative optimization for each model update, which is expensive in federated settings. As mentioned in our answer to CQ2, prior work that studies generalized linear models [Li and Wang 2022b] needs to call the distributed regression oracle during each global synchronization to execute such an expensive iterative optimization procedure. We alleviate this issue by only executing the iterative optimization at the end of Phase I, and then resorting to approximated function value during Phase II, so that more efficient communication is enabled thanks to its closed-form update.

[Q3] Lemma 6 and Lemma 8

Yes, Lemma 6 and Lemma 8 are the main technical contributions of this paper. We currently name them as Lemmas instead of Propositions, because they will be invoked as intermediate steps to prove Theorem 5, instead of being standalone technical results.

As mentioned in Section 5.1, prior work in centralized nonlinear bandit optimization (Liu and Wang, 2023) assumes the distributed regression oracle outputs the exact minimizer of Equation (2). However, this is unreasonable in a federated setting, since finding the exact minimizer would require an infinite number of iterations, which is not communication efficient. Therefore, when deriving Lemma 6, we need to take into account the additional approximation error $\epsilon$ in optimizing Equation (2), and analyze the number of iterations required to attain $\epsilon$ (this is needed in the communication cost analysis later).

For the difficulty in constructing the confidence sets in Lemma 8, please see our response to Q2.

[Q4] Tightness of the communication cost upper bound

Please see CQ2 in the common response for discussions on tightness of the communication cost bound.

I appreciate the authors' response to my questions and the revisions in their paper.

[Q1] Whether the assumptions hold in common situations and how to determine the values of the parameters

Please find our answer to CQ1 in the common response for discussions about the assumptions made in our paper.

Here we want to emphasize that, though still with its limitations, the function class defined by Assumptions 1-3 generalizes the parametric function classes studied in existing federated bandit papers (Wang et. al. 2020; Li and Wang, 2022a; He et. al., 2022; Li and Wang, 2022b), and also covers additional nonlinear, nonconvex functions that have not been considered in prior works. It is worth noting that linear and generalized linear models (both are special cases of ours) have already been shown to perform well in real-world applications like news recommendation (Li et. al., 2010), and our generalization offers even more flexibility in the modeling choices during federated optimization.

Moreover, we want to clarify that, Fed-GO-UCB algorithm does not need to know the values of the constants appearing in Assumptions 1-3, except for the bound of function value $F$ and the strong convexity parameter $\mu$ in order to set the width of the confidence set $\beta$ (as given in Lemma 8). Both constants are assumed to be known in bandit learning literature, e.g. linear bandits (Abbasi-yadkori, 2011; Wang et. al., 2020), logistic bandits (Faury et. al., 2020), and generalized linear bandits (Filippi et. al., 2010; Li and Wang, 2022b), so we are not introducing any additional assumption on the knowledge of these constants compared with prior works.

In practical applications, since these two constants, and the standard deviation $\sigma$ of reward noise that also appears in $\beta$, are unknown before observing the data, people typically directly tune the value of $\beta$ when applying bandit algorithms under different scenarios. But we agree that it would be an interesting future direction to investigate whether one can design no-regret bandit algorithms that do not require such knowledge as input, i.e., automatically adapt the strength of exploration to these unknown constants in an online manner.

[Q2] Tightness of communication cost upper bound and comparison with prior works

Please find our answer to CQ2 in the common response about the communication lower bound and detailed comparison with prior works.

Specifically, we want to clarify that, the mentioned $O(\log(T))$ rate is attained by prior works on federated linear bandits (Wang et. al., 2020; Li and Wang, 2022a; He et al., 2022; Min et al. 2023), and federated kernelized bandits (Li et al., 2022; Li et al., 2023), where closed-form solutions are available, so that only one round of communication is needed to aggregate the local sufficient statistics for model update.

In comparison, our work is more similar to (Li and Wang, 2022b) that studies federated generalized linear bandits, in the sense that, both consider nonlinear functions with no closed-form solution, and thus iterative optimization is needed to compute model update. This is intrinsically more expensive, because at least $\Omega(\sqrt{NT})$ rounds of communication is needed to collect and aggregate local gradients/models when calling the distributed regression oracle (see the discussions in Section 4.1 and 4.2 of Li and Wang (2022b), as well as the lower bound result of Arjevani and Shamir (2015)). Moreover, as discussed in our answer to CQ2, we strictly improve upon the result of Li and Wang (2022b) by a factor of $d_x \sqrt{N}$, since we only need to call the regression oracle once at the end of Phase I, instead of at each global synchronization as Li and Wang (2022b). As shown in the table in CQ2, Fed-GO-UCB is currently the most communication efficient solution for federated bandit optimization of nonlinear function, which is already a nontrivial contribution to the literature.

Continue to answer CQ2

Apart from Wang et. al. (2020), He et. al. (2022), and Min et. al. (2023) who study linear models, where only one round of communication is required to compute each closed-form model update via aggregating local sufficient statistics, FedGLB-UCB (Li and Wang, 2022b) considers nonlinear models (generalized linear models) for federated bandits, where closed-form solutions do not exist and thus iterative optimization is required, which is similar to the challenge we are facing. It is worth noting that their communication cost $\tilde O(N^2 \sqrt{T})$ also has a $\sqrt{T}$ term caused by the iterative optimization procedure of the regression oracle (i.e., it requires $O(\sqrt{NT})$ iterations of gradient aggregations), which is similar to our Fed-GO-UCB algorithm. Moreover, as pointed out in their Section 4.2, as long as iterative optimization is used to compute model update, the $O(\sqrt{NT})$ factor is unavoidable (otherwise the obtained model is too far away from the minimizer of the loss function).

Though we cannot further reduce the number of iterations required when calling the regression oracle, we still managed to improve upon the communication cost of FedGLB-UCB by a factor of $\tilde O(d_x \sqrt{N})$, since we only need to call the regression oracle once at the end of Phase I, instead of calling the oracle during each global synchronization as FedGLB-UCB (and there are $\tilde O(d_x \sqrt{N})$ global synchronizations in total). That being said, due to the lack of tighter lower bound analysis for federated bandits as we discussed earlier, it is still not clear whether the $\sqrt{T}$ dependence can be further reduced for nonlinear functions. However, we argue that it is already a nontrivial contribution to strictly improve the communication cost of FedGLB-UCB for federated optimization of nonlinear functions. Moreover, it is also safe to hypothesize that, unless one can completely remove the need of iterative optimization for nonlinear functions, our Fed-GO-UCB algorithm already attains the optimal rate as it only requires calling the distributed regression oracle once.

In the following table, we have summarized the theoretical guarantees of the aforementioned works in federated bandits. Hopefully this would provide a clearer picture of our contribution.

Additional References

• Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. "Contextual bandits with linear payoff functions." In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
• Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. "Practical contextual bandits with regression oracles." In International Conference on Machine Learning, pp. 1539-1548. PMLR, 2018.
• Elad Hazan. "Introduction to online convex optimization." Foundations and Trends® in Optimization 2, no. 3-4 (2016): 157-325.
• Dongruo Zhou, Lihong Li, and Quanquan Gu. "Neural contextual bandits with ucb-based exploration." In International Conference on Machine Learning, pp. 11492-11502. PMLR, 2020.
• Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. "Neural thompson sampling." arXiv preprint arXiv:2010.00827, 2020.
• Yifei Min, Jiafan He, Tianhao Wang, and Quanquan Gu. "Multi-agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation." arXiv preprint arXiv:2305.06446, 2023.

[CQ2] Tightness of Communication Cost Upper bound (Reviewer rFun, emcJ, yBxF)

We agree with the reviewers that discussions about the tightness of communication cost upper bound can provide more insights into the efficiency of Fed-GO-UCB algorithm. In the following paragraphs, we will discuss the known communication lower bound result, as well as comparison with existing works in detail.

First, we should note that, for federated bandit optimization, comparison on communication cost is only meaningful when fixing certain constraints on regret. The following two extreme cases are of particular interests:

1. run $N$ instances of an optimal bandit algorithm, e.g. LinUCB (Abbasi-yadkori et. al. 2011) for linear functions and GO-UCB (Liu and Wang, 2023) for generic nonlinear functions in our problem, separately on each client with no communication, which leads to $\tilde O(N\sqrt{T})$ regret and $0$ communication cost;

2. run one instance of the optimal bandit algorithm over the data of all $N$ clients, which leads to $\tilde O(\sqrt{NT})$ regret and communication cost $O(N^2 T)$.

The regret upper bound in case 2 is optimal, since it already matches the regret lower bound for a centralized bandit problem with $NT$ interactions. Therefore, the typical goal of federated bandit optimization is to attain the optimal regret of $\tilde O(\sqrt{NT})$, while having a communication cost sub-linear in $T$ (this is what “efficient communication” means).

The main contribution of our paper is to propose the first algorithm that achieves such a goal for federated bandit optimization with generic nonlinear objective functions. The lower bound analysis for the communication cost of federated bandits is highly non-trivial, and it still remains an open problem to close the gap between the communication upper bound attained by existing works and the known lower bound.

To the best of our knowledge, the only communication lower bound result available states that, in order to have $o(N\sqrt{T})$ regret, an $\Omega(N)$ communication cost is necessary (Wang et. al., 2020; He et. al., 2022; Min et. al., 2023). It was originally derived for the context-free bandits (Theorem 2 of (Wang et. al., 2020)), but as shown in Theorem 5.3 of (He et. al., 2022), it also applies to federated linear bandits, and thus applies to our problem as well. And as mentioned by Reviewer rFun, Min et. al. (2023) further applied this analysis to linear MDPs. However, none of these existing works can close the gap with the $\Omega(N)$ communication lower bound. Specifically, to obtain the optimal $\tilde O(\sqrt{NT})$ regret, DisLinUCB (Wang et. al., 2020) requires $\tilde O(N^{1.5})$ communication cost, and FedLinUCB (He et. al., 2022) requires $\tilde O(N^{2})$ communication cost, with the former one having the same rate in $N$ as our Fed-GO-UCB. This indicates that, in terms of dependence on $N$, our result is already on par with the state of the art. It is an important future direction to this line of research to further close this gap, e.g., with a tighter lower bound analysis showing the necessary amount of communication for the optimal $\tilde O(\sqrt{NT})$ regret.