Distributed Linear Bandits under Communication Constraints
- URL: http://arxiv.org/abs/2211.02212v1
- Date: Fri, 4 Nov 2022 01:42:55 GMT
- Title: Distributed Linear Bandits under Communication Constraints
- Authors: Sudeep Salgia, Qing Zhao
- Abstract summary: 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.
- Score: 14.007471903973391
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider distributed linear bandits where $M$ agents learn collaboratively
to minimize the overall cumulative regret incurred by all agents. Information
exchange is facilitated by a central server, and both the uplink and downlink
communications are carried over channels with fixed capacity, which limits the
amount of information that can be transmitted in each use of the channels. We
investigate the regret-communication trade-off by (i) establishing
information-theoretic lower bounds on the required communications (in terms of
bits) for achieving a sublinear regret order; (ii) developing an efficient
algorithm that achieves the minimum sublinear regret order offered by
centralized learning using the minimum order of communications dictated by the
information-theoretic lower bounds. 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.
Related papers
- Differential error feedback for communication-efficient decentralized learning [48.924131251745266]
We propose a new decentralized communication-efficient learning approach that blends differential quantization with error feedback.
We show that the resulting communication-efficient strategy is stable both in terms of mean-square error and average bit rate.
The results establish that, in the small step-size regime and with a finite number of bits, it is possible to attain the performance achievable in the absence of compression.
arXiv Detail & Related papers (2024-06-26T15:11:26Z) - Distributed Policy Gradient for Linear Quadratic Networked Control with
Limited Communication Range [23.500806437272487]
We show that it is possible to approximate the exact gradient only using local information.
Compared with the centralized optimal controller, the performance gap decreases to zero exponentially as the communication and control ranges increase.
arXiv Detail & Related papers (2024-03-05T15:38:54Z) - A Communication-Efficient Adaptive Algorithm for Federated Learning
under Cumulative Regret [22.80372994021181]
We develop a distributed online learning algorithm that achieves order-optimal cumulative regret with low communication cost measured in the total number of bits transmitted over the entire learning horizon.
arXiv Detail & Related papers (2023-01-21T03:08:18Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints.
We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates.
The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
arXiv Detail & Related papers (2022-09-16T09:38:38Z) - 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 Distributed Learning for Kernelized Contextual
Bandits [58.78878127799718]
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.
arXiv Detail & Related papers (2022-06-10T01:39:15Z) - Settling the Communication Complexity for Distributed Offline
Reinforcement Learning [10.315054389907031]
We study a novel setting in offline reinforcement learning (RL) where a number of distributed machines jointly cooperate to solve the problem.
There is a budget constraint on the total number of information (in terms of bits) that each machine can send out.
For value function prediction in contextual bandits, and both episodic and non-episodic MDPs, we establish information-theoretic lower bounds on the minimax risk.
arXiv Detail & Related papers (2022-02-10T06:27:07Z) - The Enforcers: Consistent Sparse-Discrete Methods for Constraining
Informative Emergent Communication [5.432350993419402]
Communication enables agents to cooperate to achieve their goals.
Recent work in learning sparse communication suffers from high variance training where, the price of decreasing communication is a decrease in reward, particularly in cooperative tasks.
This research addresses the above issues by limiting the loss in reward of decreasing communication and eliminating the penalty for discretization.
arXiv Detail & Related papers (2022-01-19T07:31:06Z) - Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
This work examines adaptive distributed learning strategies designed to operate under communication constraints.
We consider a network of agents that must solve an online optimization problem from continual observation of streaming data.
arXiv Detail & Related papers (2021-12-03T19:23:48Z) - A Linearly Convergent Algorithm for Decentralized Optimization: Sending
Less Bits for Free! [72.31332210635524]
Decentralized optimization methods enable on-device training of machine learning models without a central coordinator.
We propose a new randomized first-order method which tackles the communication bottleneck by applying randomized compression operators.
We prove that our method can solve the problems without any increase in the number of communications compared to the baseline.
arXiv Detail & Related papers (2020-11-03T13:35:53Z)
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.