On the Necessity of Collaboration for Online Model Selection with Decentralized Data

We are grateful to the reviewer for taking the time to evaluate our paper and for providing encouraging feedback. We will continue our research in this area to make more controbutions.

We thank the reviewer for detailed comments and valuable suggestions. The suggestions will make our presentation more clear. Next we answer the questions.

[Question 1] The motivation for federated learning in the context of OMS-DecD is not clearly articulated. It would be beneficial to provide more details to justify the need for federated learning for practical applications.

[Answer] In many real-world scenarios, data are generated at the edge (e.g., smartphones, IoT devices). Transmitting vast amounts of data to a central server violates the privacy concerns. Federated Learning (FL) mitigates this by only sharing model updates, thereby perserving data privacy.

In computing scenarios with limited computational resources (e.g.,constrained memory and processing power), online algorithms deployed a single device could only perform approximate model selection and model updating, thereby leading suboptimal solutions. FL aggregates information from various clients without inducing significant additional computational cost on each client, and thus have the potentials to improve the performance. Our work further theoretically demonstrate that FL is necessary for OMS-DecD when the computational resources available on each client are limited.

[Question 2] In the Introduction part, why the communication cost is $o(K)$ instead of the exact $O(MJ\log(K))$. How to choose the value of $J$.

[Answer] As stated in Section 4.5, if $J$ is of the same order as $K$, i.e., $J=\Theta(K)$, then there is no need to use federated learning for OMS-DecD, and consequently, communication is unnecessary. In the case of $J=o(K)$, federated learning is necessary. In this case, the communication of our algorithm is also $o(K)$. Therefore, for convinence of presentation, we state that our algorithm has a $o(K)$ communication cost in the Introduction.

As stated in Section 5, setting $J=2$ is sufficient to achieve the desired improvement in the regret bound, time complexity, or communication complexity compared to previous algorithms. Actually, our algorithm explicitly balances the regret and computational cost by adjusting $J$. The larger the value of $J$, the smaller the regret bound becomes, while the larger the computational complexity increases.

[Question 3] The paper does not sufficiently discuss the difference from previous works on federated online bandits. Both settings involve selection among $K$ options (arms or hypothesis spaces), and a detailed comparison would highlight the unique aspects of this work.

[Answer] This paper focused on the work most related to OMS-DecD. We are happy to discuss federated bandits, such as federated $K$-armed bandits [1] and federated linear contextual bandits [2], in our revision. Next we detail the differences between federated bandits and OMS-DecD.

(1) For OMS-DecD, we do not require the examples $({\bf x}^{(j)}_t,y^{(j)}_t)$, $t=1,…,T$, on each client to be i.i.d. (independent and identically distributed), in contrast, the rewards $r^{(j)}_t$, $t=1,...,T$, in both federated $K$-armed bandits or federated linear contextual bandits must be i.i.d. The assumption of i.i.d. rewards makes collaboration effective for federated bandits (similar to federated stochastic optimization); however, this may not hold true for OMS-DedD. Therefore, it is a unique problem of OMS-DecD to study whether collaboration is effective.

(2) The challenges posed by the two problems are distinctly different. The hypothesis space $\mathcal{F}_i$, such as a RKHS, enjoys a complex structure, while an arm (or action) does not has a structure. We can measure the complexity of $\mathcal{F}_i$ by $\mathfrak{C}_i>0$, while there is not a complexity defined for an arm. Thus algorithms for OMS-DecD must adapt to the complexity of individual hypothesis spaces, posing unique challenges on algorithm design and theoretical analysis.

[Question 4] When considering setting $K=1$, [3] achieves the $O(M\sqrt{T}+\mathrm{poly}(d)\sqrt{MT})$ result for federated adversarial linear bandits, which has a similar form compared to the result of this work. It would be better to discuss the technical challenges in the proof.

[Answer] (1) Our regret bounds necessitate an analysis for both federated online gradient descent (F-OGD) and federated exponential gradient descent (F-EGD). However, the proof in [3] focuses exclusively on F-OGD, but is not applicable to F-EGD. The first technical challenge is to analyze the regret of F-EGD. To this end, our proofs offer a template for analyzing federated online mirror descent, which can be applied to both F-OGD and F-EGD. It is interesting that we decouple the regret bound into two parts: the first part cannot be reduced by federated averaging, while the second part highlights the benefits of federated averaging (see Theorem 1).

(2) Regarding the dependence on problem-specific constants, the regret bound in [3] differs significantly from our results. As elucidated in the answer for Question 3, algorithms for OMS-DecD must adapt to the complexity of individual hypothesis spaces. Thus the second technical challenge is the derivation of a high-probability regret bound that adapts to the complexity of individual hypothesis spaces. To address this issue, we establish a new Bernstein’s inequality for martingale.

We will incorporate the discussion in the revision. Thanks for the suggestion.

[Question 5] How does this work specifically differ from and improve upon federated online bandit algorithms? What are the unique challenges introduced with the online model selection setting?

[Answer] Please refer to the answer for Question 3.

Reference

[1] Wang et al. Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication. ICLR, 2020.

[2] Huang et al. Federated Linear Contextual Bandits. NeurIPS, 2021.

[3] Patel, K. K., et al. Federated online and bandit convex optimization. ICML, 2023.

We thank the reviewer for valuable comments and suggestions. Next we answer the questions.

[Question 1] The proposed algorithm improves the regret of online multi-kernel learning by constant. Maybe adding some assumptions can help to achieve tighter regret bounds. Finding such conditions can be an interesting direction for future research.

[Answer] We appreciate the reviewer’s valuable suggestion. It is interesting to explore conditions under which we can explicitly compare the constants.

[Question 2] The paper states that some algorithms suffer from $O(K)$ download cost. Can the authors explain the importance of download cost?

[Answer] This is a good question. There are algorithms that enjoy $O(\log{K})$ upload cost, but suffer from $O(K)$ download cost, such as POF-MKL[1]. If $K$ is sufficiently large such that the speed of download is less than $K$ times of the speed of upload, then the download cost becomes the bottleneck in communication. Therefore, it is important to reduce the download cost for such algorithms.

Reference

[1] Pouya M. Ghari and Yanning Shen. Personalized online federated learning with multiple kernels. NeurIPS, 2022.

We thank the reviewer for offering valuable comments and suggestions. Next we answer the questions.

[Question 1] The paper is difficult to follow at times due to the mathematical density. It would be better presented by motivating the actual theorems in the paper.

[Answer] We will provide more insights into the theorems. We appreciate the reviewer’s valuable suggestions.

[Question 2] It was a bit difficult to follow the connection between FOMD-No-LU and FOMD-OMS and why the authors promoted the first algorithm.

[Answer] At a high level, FOMD-No-LU is a federated algorithmic framework that establishes the update rules in a general form, from which we derive FOMD-OMS. To be specific, FOMD-OMS updates hypotheses by federated online gradient descent (F-OGD), and updates sampling probabilities by federated exponential gradient descent (F-EGD). Both F-OGD and F-EGD can be derived from FOMD-No-LU, which is a federated mirror descent framework.

Therefore, in order to provide more concise presentations and theoretical analyses, we introduce FOMD-No-LU and establish a general regret bound for it. We believe that both FOMD-No-LU and the general regret bound might be of independent interest.

[Question 3] Are these regret bounds in Table 1 not to be compared as they might be due to different function classes? It seems like the FOMD-OMS is adding an additional term and can potentially have poorer regret if $\mathfrak{C}$ and $\mathfrak{C}_i$ are comparable.

[Answer] Thanks for raising the question. Indeed, the regret bounds in Table 1 are comparable. Recalling that, for each $i=1,...,K$, we define $\mathfrak{C}_i=\Theta(U_i G_i+C_i)$ where $U_i$, $G_i$ and $C_i$ are problem-dependent constants, and $\mathfrak{C}=\max_i\mathfrak{C}_i$. We have $\mathcal{C}_i\leq \mathcal{C}$. Next we separately compare FOMD-OMS with POF-MKL [1] and eM-KOFL [2].

FOMD-OMS vs POF-MKL.

From Table 1, it can be verified that

Thus the regret bound of FOMD-OMS is better than that of POF-MKL.

FOMD-OMS vs eM-KOFL.

(1) In the case of $K\leq\mathfrak{C}M/\mathfrak{C}_i\cdot\ln{K}$, we have

where we use the notation $\lesssim$ to hide constant factors. Thus the regret bound of FOMD-OMS is better than that of eM-KOFL.

(2) In the csae of $K\geq\mathfrak{C}M/\mathfrak{C}_i\cdot\ln{K}$, we have

Thus the regret bound of FOMD-OMS is worse than that of eM-KOFL. If $K$ is sufficiently large, the regret bound of eM-KOFL is better than that of FOMD-OMS by a factor of $O(\sqrt{K})$.

From Table 1, we observe that FOMD-OMS significantly improves the computational complexity of POF-MKL and eM-KOFL (by a factor of $O(K)$), either maintaining a better regret bound or incurring only a small expense in the regret bound.

Furthermore, the collaboration is ineffective in POF-MKL and eM-KOFL, while it is effective in FOMD-OMS.

Reference

[1] Pouya M. Ghari and Yanning Shen. Personalized online federated learning with multiple kernels. NeurIPS, 2022.

[2] Songnam Hong and Jeongmin Chae. Communication-efficient randomized algorithm for multi-kernel online federated learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.