Communication Efficient Distributed Learning for Kernelized Contextual Bandits

• URL: http://arxiv.org/abs/2206.04835v1
• Date: Fri, 10 Jun 2022 01:39:15 GMT
• Title: Communication Efficient Distributed Learning for Kernelized Contextual Bandits
• Authors: Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang
• Abstract summary: We tackle the communication efficiency challenge of learning kernelized contextual bandits in a distributed setting. We consider non-linear reward mappings, by letting agents collaboratively search in a reproducing kernel Hilbert space. We rigorously proved that our algorithm can attain sub-linear rate in both regret and communication cost.
• Score: 58.78878127799718
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle the communication efficiency challenge of learning kernelized contextual bandits in a distributed setting. Despite the recent advances in communication-efficient distributed bandit learning, existing solutions are restricted to simple models like multi-armed bandits and linear bandits, which hamper their practical utility. In this paper, instead of assuming the existence of a linear reward mapping from the features to the expected rewards, we consider non-linear reward mappings, by letting agents collaboratively search in a reproducing kernel Hilbert space (RKHS). This introduces significant challenges in communication efficiency as distributed kernel learning requires the transfer of raw data, leading to a communication cost that grows linearly w.r.t. time horizon $T$. We addresses this issue by equipping all agents to communicate via a common Nystr\"{o}m embedding that gets updated adaptively as more data points are collected. We rigorously proved that our algorithm can attain sub-linear rate in both regret and communication cost.

Related papers

• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning [50.382793324572845]
  Distributed computing involves communication between devices, which requires solving two key problems: efficiency and privacy. In this paper, we analyze a new method that incorporates the ideas of using data similarity and clients sampling. To address privacy concerns, we apply the technique of additional noise and analyze its impact on the convergence of the proposed method.
  arXiv  Detail & Related papers  (2024-09-22T00:49:10Z)
• Semantic Communication for Cooperative Perception using HARQ [51.148203799109304]
  We leverage an importance map to distill critical semantic information, introducing a cooperative perception semantic communication framework. To counter the challenges posed by time-varying multipath fading, our approach incorporates the use of frequency-division multiplexing (OFDM) along with channel estimation and equalization strategies. We introduce a novel semantic error detection method that is integrated with our semantic communication framework in the spirit of hybrid automatic repeated request (HARQ)
  arXiv  Detail & Related papers  (2024-08-29T08:53:26Z)
• High-Dimensional Distributed Sparse Classification with Scalable Communication-Efficient Global Updates [50.406127962933915]
  We develop solutions to problems which enable us to learn a communication-efficient distributed logistic regression model. In our experiments we demonstrate a large improvement in accuracy over distributed algorithms with only a few distributed update steps needed.
  arXiv  Detail & Related papers  (2024-07-08T19:34:39Z)
• Gossiped and Quantized Online Multi-Kernel Learning [39.057968279167966]
  We show that distributed and online multi- kernel learning provides sub-linear regret as long as every pair of nodes in the network can communicate. This letter expands on these results to non-fully connected graphs, which is often the case in wireless sensor networks. We propose a gossip algorithm and provide a proof that it achieves sub-linear regret.
  arXiv  Detail & Related papers  (2023-01-24T07:12:40Z)
• Distributed Linear Bandits under Communication Constraints [14.007471903973391]
  We consider distributed linear bandits where $M$ agents learn to minimize the overall cumulative regret incurred by all agents. For sparse linear bandits, we show a variant of the proposed algorithm offers better regret-communication trade-off by leveraging the sparsity of the problem.
  arXiv  Detail & Related papers  (2022-11-04T01:42:55Z)
• Fundamental Limits of Communication Efficiency for Model Aggregation in Distributed Learning: A Rate-Distortion Approach [54.311495894129585]
  We study the limit of communication cost of model aggregation in distributed learning from a rate-distortion perspective. It is found that the communication gain by exploiting the correlation between worker nodes is significant for SignSGD.
  arXiv  Detail & Related papers  (2022-06-28T13:10:40Z)
• Communication Efficient Federated Learning for Generalized Linear Bandits [39.1899551748345]
  We study generalized linear bandit models under a federated learning setting. We propose a communication-efficient solution framework that employs online regression for local update and offline regression for global update. Our algorithm can attain sub-linear rate in both regret and communication cost.
  arXiv  Detail & Related papers  (2022-02-02T15:31:45Z)
• Federated Reinforcement Learning at the Edge [1.4271989597349055]
  Modern cyber-physical architectures use data collected from systems at different physical locations to learn appropriate behaviors and adapt to uncertain environments. This paper considers a setup where multiple agents need to communicate efficiently in order to jointly solve a reinforcement learning problem over time-series data collected in a distributed manner. An algorithm for achieving communication efficiency is proposed, supported with theoretical guarantees, practical implementations, and numerical evaluations.
  arXiv  Detail & Related papers  (2021-12-11T03:28:59Z)
• Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits [35.47147821038291]
  We propose a general framework with asynchronous model update and communication for a collection of homogeneous clients and heterogeneous clients. Rigorous theoretical analysis is provided about the regret and communication cost under this distributed learning framework.
  arXiv  Detail & Related papers  (2021-10-04T14:01:32Z)
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond [73.03743482037378]
  Distributed learning has become a critical direction of the massively connected world envisioned by many. This article discusses four key elements of scalable distributed processing and real-time data computation problems. Practical issues and future research will also be discussed.
  arXiv  Detail & Related papers  (2020-01-14T14:11:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.