Communication-Efficient Federated Non-Linear Bandit Optimization
Preprint
Abstract
Federated optimization studies the problem of collaborative function optimization among multiple clients (e.g. mobile devices or organizations) under the coordination of a central server. Since the data is collected separately by each client and always remains decentralized, federated optimization preserves data privacy and allows for large-scale computing, which makes it a promising decentralized machine learning paradigm. Though it is often deployed for tasks that are online in nature, e.g., next-word prediction on keyboard apps, most works formulate it as an offline problem. The few exceptions that consider federated bandit optimization are limited to very simplistic function classes, e.g., linear, generalized linear, or non-parametric function class with bounded RKHS norm, which severely hinders its practical usage. In this paper, we propose a new algorithm, named Fed-GO-UCB, for federated bandit optimization with generic non-linear objective function. Under some mild conditions, we rigorously prove that Fed-GO-UCB is able to achieve sub-linear rate for both cumulative regret and communication cost. At the heart of our theoretical analysis are distributed regression oracle and individual confidence set construction, which can be of independent interests. Empirical evaluations also demonstrate the effectiveness of the proposed algorithm.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Nonparametric regression using deep neural networks with ReLU activation functionThe Annals of Statistics, 2020
- Design for low‐temperature microwave‐assisted crystallization of ceramic thin filmsApplied Stochastic Models in Business and Industry, 2017
- Taking the Human Out of the Loop: A Review of Bayesian OptimizationProceedings of the IEEE, 2015