Communication-Efficient Federated Non-Linear Bandit Optimization
Chuanhao Li Chong Liu Yu-Xiang Wang
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.