PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Bayesian Optimization via Thompson Sampling

Zhongxiang Dai, Kian Hsiang Low, Patrick Jaillet

arXiv:2010.10154v3cs.LGcs.AI

TL;DR

Gradient-free black-box tasks such as DNN hyperparameter tuning are not handled by the first-order optimization typically used in federated learning. The paper introduces FTS, using RFF-based GP approximation and Thompson sampling for federated BO. It reports empirical effectiveness across communication, computation, and practical performance, alongside a convergence guarantee robust to heterogeneous agents.

  • Problem

    Federated learning commonly uses first-order optimization, but tasks such as DNN hyperparameter tuning lack gradients and require black-box optimization while agents retain raw task data.

    Source: §1 · pp. 1–2

  • Method

    FTS approximates GP surrogates with RFF to produce exchangeable parameters and uses Thompson sampling to limit communication while incorporating information from other agents.

    Source: §1 · p. 2

  • Results

    FTS is reported effective in communication efficiency, computational efficiency, and practical performance across three real-world experiments, with an asymptotic no-regret guarantee despite differences between agents.

    Source: §1 · p. 2, §4 · p. 6

  • Takeaways & Limitations

    FTS provides a federated BO approach that exchanges model parameters rather than raw task histories and is designed to remain convergent with heterogeneous agents.

    Source: §1 · p. 2, §4 · p. 6

    Although FTS avoids exchanging raw data, advanced privacy attacks such as inference attacks may still pose privacy-leak risks.

    Source: Broader Impact · p. 10

Abstract

from arXiv · show

Bayesian optimization (BO) is a prominent approach to optimizing expensive-to-evaluate black-box functions. The massive computational capability of edge devices such as mobile phones, coupled with privacy concerns, has led to a surging interest in federated learning (FL) which focuses on collaborative training of deep neural networks (DNNs) via first-order optimization techniques. However, some common machine learning tasks such as hyperparameter tuning of DNNs lack access to gradients and thus require zeroth-order/black-box optimization. This hints at the possibility of extending BO to the FL setting (FBO) for agents to collaborate in these black-box optimization tasks. This paper presents federated Thompson sampling (FTS) which overcomes a number of key challenges of FBO and FL in a principled way: We (a) use random Fourier features to approximate the Gaussian process surrogate model used in BO, which naturally produces the parameters to be exchanged between agents, (b) design FTS based on Thompson sampling, which significantly reduces the number of parameters to be exchanged, and (c) provide a theoretical convergence guarantee that is robust against heterogeneous agents, which is a major challenge in FL and FBO. We empirically demonstrate the effectiveness of FTS in terms of communication efficiency, computational efficiency, and practical performance.

1 Introduction

Federated BO extends collaborative optimization to gradient-free tasks while keeping agents’ raw task data private. FTS uses RFF-based GP approximation and Thompson sampling to address exchangeable representations, communication efficiency, and agent heterogeneity.

1 Introduction

  • BO offers a way to optimize expensive, gradient-free tasks such as DNN hyperparameter tuning, while FL typically relies on first-order optimization.FBO combines BO with collaboration among agents that retain their raw task histories.Source: §1 · pp. 1–2
  • A central FBO challenge is that GP surrogates are nonparametric, leaving no task parameters to exchange without transmitting raw input-output histories.RFF approximates the GP with Bayesian linear regression, yielding communicable parameters; with RFF, these are equivalent to linear-model parameters in standard FL.Source: §1 · p. 2
  • FTS uses Thompson sampling to reduce the number of communicated parameters while maintaining competitive performance, and its convergence guarantee is robust to heterogeneous agents.Heterogeneity means other agents’ objective functions may differ substantially from the target agent’s.Source: §1 · p. 2
  • The paper introduces FTS as the first FBO algorithm and evaluates communication efficiency, computational efficiency, and practical performance in three real-world experiments.The experiments cover landmine detection and activity recognition using Google Glasses and mobile-phone sensors.Source: §1 · p. 2

2 Background

The background frames BO as sequential black-box optimization guided by a GP surrogate and explains how random Fourier features provide an approximate, finite-dimensional representation. It also specifies the shared-feature and smoothness assumptions used to formulate FBO.

2 Background

  • BO sequentially queries a noisy black-box objective to seek its global maximizer, with regret used to characterize optimization performance.The supplied passage defines cumulative regret and states that sublinear cumulative regret implies simple regret tends to zero asymptotically.Source: §2 · pp. 2–3
  • A GP surrogate guides BO’s query selection, but its O(t^3) time cost motivates approximation methods such as RFF.RFF approximates kernel values by inner products of sampled random features; increasing the feature count improves approximation quality.Source: §2 · p. 3
  • With RFF, the approximate GP can be represented as Bayesian linear regression over features, and its posterior is characterized by parameters that define predictive beliefs.The passage identifies the feature-weight posterior and states that its parameters fully define the approximate GP posterior or predictive belief.Source: §2 · p. 3
  • The FBO setting treats one agent as the target and assumes shared random features, a common discrete domain, and bounded RKHS norms for the objective functions.The maximum objective difference d_n characterizes similarity to the target; larger d_n indicates greater agent heterogeneity.Source: §2 · p. 3

3 Federated Bayesian Optimization (FBO)

FTS shares compact posterior samples from agents and mixes their sampled functions with the target agent’s own Thompson-sampling choices. The section also contrasts FTS with adapted meta-learning methods, emphasizing its smaller messages and lower per-iteration computation.

3.1 Federated Thompson Sampling (FTS)

  • Each agent uses its observations and shared random features to sample an M-dimensional weight vector from its approximate GP posterior and sends that vector to the target.The target can receive the message directly or through a central server.Source: §3.1 · p. 4
  • At each iteration, FTS selects the target agent’s sampled-function maximizer with probability p_t, or samples another agent according to P_N and selects that agent’s sampled-function maximizer.The target then queries the selected input, observes its noisy output, and updates its GP posterior.Source: §3.1 · p. 4
  • FTS is a Thompson-sampling variant over a mixture of GPs that gradually converges to the target GP as p_t approaches one.The schedule controls use of other agents’ information, while P_N sets agent preferences; assigning a straggler probability zero excludes it from sampling.Source: §3.1 · p. 4
  • In the single-message setting, an agent is removed from P_N after its message is used; repeated sampling can instead be supported with additional communication rounds.The paper expects similar performance between these settings when the agent count is large and preferences are similar or equal.Source: §3.1 · p. 4

3.2 Comparison with Other BO Algorithms Modified for the FBO Setting

  • RGPE and TAF can be adapted to FBO by combining RFF approximation with their per-agent GP surrogates, but they lack FTS’s theoretical convergence guarantee for heterogeneous agents.The paper reports that FTS outperforms both methods in several major aspects, including communication and computational efficiency and practical performance.Source: §3.2 · p. 5
  • For fixed M, FTS sends one M-dimensional vector per agent, whereas RGPE and TAF need M + M^2 parameters; their per-iteration computation also grows linearly with the number of agents.FTS’s agent-sampled maximization uses the communicated vector directly, while the comparison methods repeatedly calculate each agent’s GP posterior mean and variance.Source: §3.2 · p. 5

4 Theoretical Results

FTS’s regret guarantee is designed to remain valid with heterogeneous agents, rather than to establish faster convergence than standard Thompson sampling. Under the stated conditions, its cumulative regret grows sublinearly, yielding asymptotic no regret.

4 Theoretical Results

  • Under the stated conditions, FTS has sublinear cumulative regret and achieves asymptotic no regret regardless of differences between agents’ objective functions.The guarantee uses a monotonically increasing p_t sequence approaching 1 and the stated SE-kernel information-gain condition.Source: §4 · pp. 5–6
  • Smaller p_t uses information from other agents more, but raises the worst-case regret bound through its 1/p_1 and (1 − p_t) terms.Source: §4 · p. 6
  • The bound worsens as other agents’ objective mismatch d_n or observation count t_n grows, reflecting increased worst-case error.A larger mismatch increases objective-function differences, while more observations accumulate individual errors in the bound.Source: §4 · p. 6
  • Larger M tightens the bound when t_n is sufficiently large; with few observations, better RFF approximation may bring negligible gains despite greater communication bandwidth.The benefit of more random features is amplified when other agents have more observations.Source: §4 · p. 6

5 Experiments and Discussion

The experiments evaluate FTS on synthetic and three real-world optimization tasks, examining regret, communication, computation, and performance. FTS benefits from information from similar agents and performs well across heterogeneous real-world tasks, while faster decay of other agents’ influence can address slower convergence in a heterogeneous synthetic setting.

5.1 Optimization of Synthetic Functions

  • With similar agent objectives, FTS performs better than standard TS; increasing M helps when agents have many observations, while its effect is negligible with few observations.When agents are heterogeneous, FTS remains comparable to TS, and faster growth of p_t lets it match TS in the adverse setting.Source: §5.1 · p. 7, Figure 1 · p. 7

5.2 Real-world Experiments

  • The real-world tests use landmine detection and activity recognition data, with target agents optimized using information from other agents that have completed 50 BO iterations.The three experiments use landmine fields, Google Glasses participants, and mobile-phone subjects; performance is measured by AUC for landmine detection and validation error for activity recognition.Source: §5.2 · pp. 7–8
  • FTS outperforms RGPE and TAF in performance and communication efficiency across three real-world experiments, and converges fastest among the compared methods.The comparison after 50 iterations favors FTS despite its completing those iterations in significantly less time; results use six target agents, each averaged over five initializations.Source: Figure 2 · p. 8, §5.2 · pp. 8–9, Figure 3 · p. 8
  • Increasing the number of agents has minimal effect on FTS runtime in landmine detection, while RGPE and TAF incur growing computational cost.The runtime comparison uses the landmine detection experiment.Source: Figure 3 · p. 8, §5.2 · p. 9

6 Related Works

The related work situates FTS among federated learning, Thompson sampling, and several Bayesian optimization approaches. It distinguishes FTS by addressing heterogeneous objectives and the communication and privacy constraints of federated BO.

6 Related Works

  • Unlike parallel or distributed BO methods that usually optimize one objective, FTS considers potentially heterogeneous objectives across agents.The paper also relates FTS to multi-fidelity BO, interpreting agent similarity to the target as a measure of fidelity.Source: §6 · p. 9
  • Prior meta-learning methods for BO can be adapted to federated BO, but the cited works do not provide theoretical convergence guarantees or address raw-data transmission and communication efficiency.The paper reports that adapted variants were outperformed by FTS in communication efficiency, computational efficiency, and practical performance.Source: §6 · p. 9
  • The paper’s theoretical analysis draws on prior Thompson-sampling regret analyses in BO.The related work also places TS among methods used for multi-armed bandits [47] and BO.Source: §6 · p. 9

7 Conclusion and Future Works

The paper presents FTS as a theoretically grounded and empirically effective approach to federated BO. It identifies several extensions for future work, including improved agent selection, privacy protection, and broader optimization settings.

7 Conclusion and Future Works

  • FTS is presented as the first FBO algorithm with a convergence guarantee robust to heterogeneous agents and empirical effectiveness across three real-world experiments.The experiments assess communication efficiency, computational efficiency, and practical performance.Source: §7 · p. 9
  • Future work could learn agent similarity to the target for sampling, explore GP approximations beyond RFF, and share GP hyperparameters across agents.The current experiments learn the target agent’s GP hyperparameters by maximizing marginal likelihood.Source: §7 · p. 9
  • The current algorithm avoids raw-data sharing but may remain susceptible to advanced privacy attacks; differential privacy is proposed as a direction for addressing this boundary.Other proposed directions include incentivizing collaboration and extending FBO to nonmyopic and high-dimensional BO.Source: §7 · p. 9
  • Results across different agents cannot be averaged because their output scales vary significantly.Source: §7 · p. 9

Broader Impact

The broader-impact discussion describes possible benefits of more efficient mobile black-box optimization alongside residual privacy risks. The appendices explain how FTS constructs and shares random Fourier features and how those features approximate GP posterior beliefs.

Broader Impact

  • More efficient black-box optimization on mobile phones could improve application efficacy, user experience, and productivity, but advanced privacy attacks may still pose risks.The paper identifies differential privacy as a promising direction for addressing these risks.Source: Broader Impact · p. 10

A Construction of Random Fourier Features

  • For the squared exponential kernel, RFF uses sampled frequency vectors and phases to construct M-dimensional features, with the feature parameters shared across agents.The frequencies are sampled from a D-dimensional Gaussian distribution and the phases from a uniform distribution over [0, 2π]; the features are normalized to the signal variance.Source: A Construction of Random Fourier… · p. 14

B GP Posterior/Predictive Belief with Random Fourier Features Approximation

C Proof of Theorem 1

The proof builds high-probability bounds for sampled functions and instantaneous regret, then uses a supermartingale concentration argument to bound cumulative regret. Its analysis assumes a discrete domain and also covers communication rounds in which agents may collect further observations.

C Proof of Theorem 1

  • The analysis extends to communication before every iteration, including settings where agents collect additional observations between rounds.The proof denotes the changing message and sampled function by ω_n,t and ĝ_n,t.Source: C Proof of Theorem 1 · p. 15
  • The concentration argument is stated for a discrete domain, unlike the compact-domain setting of the cited prior result.The proof also defines saturated inputs as points whose function values differ substantially from the global maximum.Source: C Proof of Theorem 1 · p. 15
  • The sampled function stays concentrated around its posterior mean, and sampled functions are related to the agents’ objective functions through uniform bounds.These bounds support the subsequent instantaneous-regret analysis.Source: C Proof of Theorem 1 · pp. 15–17
  • Lemma 11 gives a high-probability upper bound on cumulative regret in terms that include the maximum information gain γ_T.The proof obtains the cumulative bound by applying Azuma-Hoeffding concentration to a supermartingale.Source: C Proof of Theorem 1 · p. 20

D Further Experimental Details and Results

The appendix reports experimental computing resources and details how synthetic objective functions and agents’ observations are generated for FTS.

D Further Experimental Details and Results

D.1 Optimization of Synthetic Functions

  • Synthetic objectives are sampled from a Gaussian process on a 1,000-point discrete domain in [0, 1], with outputs normalized to [0, 1] and observation noise variance 0.01.Other agents’ objectives are generated by adding or subtracting their maximum deviation d_n from the target objective at each input.Source: §D.1 · pp. 21–22
  • Each agent uses its own t_n noisy observations to form RFF approximation parameters and sample the ω_n message sent to the target agent.The target begins FTS after receiving messages from the other agents.Source: §D.1 · p. 22

D.2.1 Results in the Most General Setting with Increasing tn

The appendix evaluates FTS when agents can send updated information before each iteration and may collect further observations between rounds. FTS outperforms standard Thompson sampling in both communication settings across all three real-world experiments, though increasing observations does not help uniformly.

D.2.1 Results in the Most General Setting with Increasing tn

  • In the evaluated general setting, each agent begins with 50 BO iterations and sends an updated RFF-based message before every FTS iteration.Agents run one additional BO iteration between messages, so t_n increases by one each round.Source: §D.2.1 · p. 22
  • FTS outperforms standard TS in both communication settings across landmine detection, Google Glasses, and mobile-phone sensor experiments.With increasing t_n, activity-recognition performance improves while landmine-detection performance is comparable to the simpler setting.Source: §D.2.1 · p. 23
  • More observations from heterogeneous agents may hurt FTS because their information can be harmful to the target agent’s BO task.The passage contrasts this with potentially useful information from agents whose objectives are similar to the target’s.Source: §D.2.1 · p. 23

D.2.2 More Experimental Details

The appendix details three real-world hyperparameter-tuning experiments, specifying their datasets, predictive models, and train-validation splits.

D.2.2 More Experimental Details

  • Landmine detection uses data from 29 fields to tune two SVM hyperparameters, with half of each field’s examples reserved for validation.Because positive labels are rare, performance is evaluated with AUC rather than validation error.Source: §D.2.2 · p. 23
  • The Google Glasses experiment uses sensor windows from 38 participants to tune three logistic-regression hyperparameters, with 100 windows per participant for validation.Each window is represented by 57 sensor-statistic features.Source: §D.2.2 · p. 23
  • The mobile-phone experiment tunes logistic-regression hyperparameters for six-activity classification using sensor data from 30 subjects.Each subject’s examples are split equally between training and validation; its tuned hyperparameters and ranges match the Google Glasses experiment.Source: §D.2.2 · pp. 23–24
  • Figure 5 reports additional landmine-detection results for five other target agents using M = 100.Source: Figure 5 · p. 24

D.2.3 Additional Results for More Agents

Across the additional target agents in the real-world experiments, FTS performs better than TS for some agents and comparably for others.

D.2.3 Additional Results for More Agents

  • FTS performs better than TS for some additional target agents and comparably with TS for others.The results use agents 2–6 as targets; the main-text results use agent 1.Source: §D.2.3 · p. 24
  • Figure 6 reports additional results for the five other target agents in Google-glasses activity recognition with M = 100.Source: Figure 6 · p. 25
  • Figure 7 reports additional results for the five other target agents in mobile-phone-sensor activity recognition with M = 100.Source: Figure 7 · p. 25

Related papers

Loading 2010.10154v3…