We study the problem of regret minimization for distributed bandits learning, in which agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Logarithmic Communication”
A decentralized policy achieves logarithmic regret for multi-agent MAB problems with communication constraints.
problem Decentralized policy for multi-agent MAB problems with option availability and communication constraints.
method Upper Confidence Bound (UCB) algorithms with non-stationary stochastic communication protocol.
result Guaranteed logarithmic regret for non-fully connected spatial graphs with communication constraints.
Paper proposes FedQ-Advantage for federated Q-learning with near-optimal regret and low communication cost.
problem Near-optimal federated Q-learning with low communication cost.
method Reference-advantage decomposition for variance reduction, synchronization between agents and server, policy update.
result Achieves almost optimal regret and near-linear regret speedup compared to single-agent learning.
New batched Langevin Thompson Sampling reduces communication costs for sequential decision making.
problem Efficiently learning unknown reward distributions and transition dynamics in batched settings.
method Langevin Thompson Sampling with logarithmic communication costs.
result Order-optimal regret guarantees for stochastic MABs and RL.
Study hypothesis testing under quantized samples with communication constraints, achieving near-optimal sample complexity.
problem Optimizing hypothesis testing with quantized samples and communication constraints.
method Developed a polynomial-time algorithm achieving near-optimal sample complexity under communication constraints.
result Achieved near-optimal sample complexity under communication constraints, with a logarithmic factor increase over unconstrained setting.
Study on individual regret in cooperative MAB with agents communicating over a graph.
problem Individual regret in cooperative stochastic multi-armed bandits with communication constraints.
method Analyzed COOP-SE algorithm, derived individual regret bounds under various communication constraints.
result First to show an individual regret bound in cooperative stochastic MAB independent of graph diameter.
In this short communication we introduce the quick clustering algorithm (QUIST), an efficient hierarchical clustering algorithm based on sorting. QUIST is a poly-logarithmic divisive clustering algorithm that does not assume the number of clusters, and/or the cluster size to be known ahead of time. It is also insensiti…
Two non-communicating players minimize regret in a multi-armed bandit game.
problem Optimal regret in non-communicating multi-armed bandit players.
method Proposed a strategy with no collisions, achieving near-optimal regret.
result Near-optimal regret of with very high probability.
Federated Q-Learning achieves linear regret speedup with low communication cost.
problem Achieving linear regret speedup in federated reinforcement learning without high communication costs.
method Proposed two federated Q-Learning algorithms: FedQ-Hoeffding and FedQ-Bernstein, using event-triggered synchronization, novel step size selection, and concentration inequalities.
result Total regrets achieve linear speedup compared to single-agent counterparts with logarithmic communication cost.
This paper presents a novel spectral algorithm with additive clustering designed to identify overlapping communities in networks. The algorithm is based on geometric properties of the spectrum of the expected adjacency matrix in a random graph model that we call stochastic blockmodel with overlap (SBMO). An adaptive ve…
We introduce the community exploration problem that has many real-world applications such as online advertising. In the problem, an explorer allocates limited budget to explore communities so as to maximize the number of members he could meet. We provide a systematic study of the community exploration problem, from off…
Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningstat.ML
New RL algorithms reduce costs for single-agent and federated learning.
problem Minimizing costs in RL and federated RL settings.
method Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost algorithms.
result First algorithms to achieve low burn-in and logarithmic switching costs.
Distributed-OMP recovers sparse vectors with low communication costs.
problem High-dimensional sparse linear regression with limited computation and communication.
method Distributed orthogonal matching pursuit (OMP) scheme.
result Support of the regression vector can be recovered with linear communication per machine and logarithmic in dimension.
New algorithm reduces sample and communication complexities in federated Q-learning.
problem Optimal Q-function learning in federated Q-learning with limited communication.
method Introduced Fed-DVR-Q algorithm for order-optimal sample and communication complexities.
result Complete characterization of sample-communication complexity trade-off.
Algorithm reduces regret in multi-player bandits with unknown collision rewards.
problem Reducing regret in multi-player multi-armed bandits with unknown collision rewards.
method Proposes an algorithm that combines a modified successive elimination strategy with a communication protocol to estimate suboptimality gaps and coordinate among players.
result Achieves logarithmic regret for the problem when collision reward is unknown.
We propose a novel, efficient approach for distributed sparse learning in high-dimensions, where observations are randomly partitioned across machines. Computationally, at each round our method only requires the master machine to solve a shifted ell_1 regularized M-estimation problem, and other workers to compute the g…
Polynomial-time algorithm for near-optimal community detection in graphs.
problem Node-private community estimation in stochastic block models.
method Explicit Lipschitz surrogate and accept-reject algorithm for sampling community labels.
result Achieves minimax rates for exact recovery with polynomial-time runtime and logarithmic privacy parameter.
SCAFFLSA reduces communication complexity for federated learning with heterogeneous clients.
problem Quantifying and reducing communication complexity in federated learning with heterogeneous clients.
method Proposes SCAFFLSA, a variant of FedLSA using control variates to correct for client drift.
result SCAFFLSA achieves logarithmic communication complexity for statistically heterogeneous agents, scaling with the inverse of the desired accuracy.
Novel compression method preserves privacy while reducing communication costs.
problem Reducing communication costs in differential privacy mechanisms.
method Poisson private representation (PPR) for compressing and simulating local randomizers.
result Achieves compression within a logarithmic gap from theoretical lower bound.
Motivated by cognitive radio networks, we consider the stochastic multiplayer multi-armed bandit problem, where several players pull arms simultaneously and collisions occur if one of them is pulled by several players at the same stage. We present a decentralized algorithm that achieves the same performance as a centra…
We consider the problem of estimating community memberships of nodes in a network, where every node is associated with a vector determining its degree of membership in each community. Existing provably consistent algorithms often require strong assumptions about the population, are computationally expensive, and only p…
To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The geometric block model generalizes the random geometric graphs in the same way that the well-studied stochastic block model generalizes the …
In distributed statistical learning, samples are split across machines and a learner wishes to use minimal communication to learn as well as if the examples were on a single machine. This model has received substantial interest in machine learning due to its scalability and potential for parallel speedup. Howev…
We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the machines receives data points from a -dimensional Gaussian distribution with unknown mean w…
We consider learning of fundamental properties of communities in large noisy networks, in the prototypical situation where the nodes or users are split into two classes according to a binary property, e.g., according to their opinions or preferences on a topic. For learning these properties, we propose a nonparametric,…
Two new algorithms optimize decentralized convex optimization with reduced communication rounds.
problem Decentralized minimization of smooth strongly convex functions in a network.
method Proposes two new algorithms based on accelerated Forward Backward methods.
result First algorithm is optimal in terms of communication rounds and gradient computations.
Paper tackles community recovery in binary symmetric SBM graphs.
problem Community detection in binary symmetric SBM graphs.
method Proposes a two-stage iterative method using projected power iterations and orthogonal iterations.
result Proposed method can exactly recover communities with high probability in logarithmic sparsity regime.
A new algorithm reduces regret in multi-player bandits without collision info.
problem Decentralized multi-player multi-armed bandits with no collision info.
method EC-SIC algorithm using optimal error correction coding for reward statistics.
result Regret approaches that of centralized with collision info.
Federated learning supports exact support recovery with minimal communication.
problem Learning the exact support of sparse linear regression in federated learning.
method One-shot communication algorithm for exact support recovery without optimization.
result Polynomial sample complexity and logarithmic number of clients required.
New method recovers radar and communication signals from overlaid data.
problem Recover radar and communication signals from overlaid data with unknown parameters.
method Propose minimizing the sum of multivariate atomic norms (SoMAN) for multi-antenna receiver.
result Minimum number of samples and antennas required for perfect recovery is logarithmically dependent on the maximum of radar targets and communications paths.
A distributed algorithm reduces communication cost in linear bandits to near-optimal levels.
problem Cooperative linear bandit optimization with stochastic contexts.
method DisBE-LUCB algorithm, DecBE-LUCB algorithm, sharing information through a central server or immediate neighbors.
result Communication cost of DisBE-LUCB matches information-theoretic lower bound up to logarithmic factors.
Paper closes the gap in MP-MAB problems with novel adaptive communication and exploration.
problem Closing the gap between decentralized MP-MAB and natural centralized lower bound.
method BEACON: Batched Exploration with Adaptive COmmunicatioN, incorporating ADC and batched exploration.
result Proves logarithmic regret for a generalized MP-MAB problem.
Study quantile reward identification with 1-bit feedback constraints.
problem Best arm identification with quantile reward and 1-bit communication.
method Proposes an algorithm using noisy binary search for quantile reward estimation.
result Derives upper and lower bounds on sample complexity for 1-bit feedback.
Study on limits of LLM-based multi-agent planning reliability.
problem Reliability limits of LLM-based multi-agent planning.
method Modeling LLM-based multi-agent architecture as a decision network, showing dominance by centralized Bayes decision maker.
result Optimizing multi-agent directed acyclic graphs under communication budget is equivalent to choosing a constrained experiment.
The false discovery rate (FDR)---the expected fraction of spurious discoveries among all the discoveries---provides a popular statistical assessment of the reproducibility of scientific studies in various disciplines. In this work, we introduce a new method for controlling the FDR in meta-analysis of many decentralized…
A distributed bootstrap method for high-dimensional data reduces communication rounds efficiently.
problem Simultaneous inference on massive, high-dimensional data stored across many machines.
method Distributed bootstrap based on de-biased lasso with efficient cross-validation tuning.
result Theoretical lower bound on communication rounds for statistical accuracy and efficiency.
We study agents communicating over an underlying network by exchanging messages, in order to optimize their individual regret in a common nonstochastic multi-armed bandit problem. We derive regret minimization algorithms that guarantee for each agent an individual expected regret of $\widetilde{O}\left(\sqrt{\left(…
While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This leads to defining weakly-communicating or multi-chain MDPs. In this…
This paper sets communication complexity bounds for distributed RL.
problem Establishing minimum communication requirements for distributed RL.
method Information-theoretic lower bounds and algorithm development.
result Developed algorithms achieving optimal risk up to logarithmic factors.
Federated learning for combinatorial multi-agent bandits reduces regret and speeds up with fewer communications.
problem Online combinatorial optimization with noisy feedback and cooperation.
method Transforms offline algorithms into online multi-agent algorithms with sublinear regret and communication efficiency.
result Achieves sublinear regret and linear speedup with more agents, communication-efficient.
The paper improves regret lower bounds for communicating MDPs.
problem Regret lower bounds for communicating MDPs.
method Lower bound proof and optimization problem formulation.
result Regret lower bound becomes significantly more complex in communicating MDPs.
A new algorithm reduces communication costs for collaborative decision-making across clients.
problem Collaborative decision-making with sparse rewards and heterogeneous contexts.
method Federated Lasso algorithm for sparse linear contextual bandits.
result Achieves near-optimal regret with logarithmic communication costs.
Study on statistical estimation over Gaussian MAC, comparing analog and digital schemes.
problem Distributed minimax statistical estimation over a Gaussian MAC.
method Developed analog joint estimation-communication schemes and derived information-theoretic lower bounds.
result Achieved risk within a logarithmic factor of information-theoretic lower bounds.
Interneurons accelerate learning dynamics in recurrent neural networks for statistical adaptationq-bio.NC
Interneurons improve learning in neural networks by accelerating convergence.
problem Rapid adaptation to changing input statistics in neural networks.
method Two mathematically tractable recurrent linear neural networks were compared: one with direct recurrent connections and the other with interneurons that mediate recurrent communication.
result The network with interneurons converges more quickly than the network with direct recurrent connections, scaling logarithmically with initialization spectrum.
We study model-based reinforcement learning in an unknown finite communicating Markov decision process. We propose a simple algorithm that leverages a variance based confidence interval. We show that the proposed algorithm, UCRL-V, achieves the optimal regret up to logarithmic factors…
Efficient algorithm for graph matching in correlated stochastic block models.
problem Graph matching in correlated stochastic block models with balanced communities.
method Extends previous work on centered subgraph counts to handle estimation errors and edge correlation.
result First efficient algorithm for graph matching in the logarithmic average degree regime, matching all but a vanishing fraction of vertices with high probability.
Algorithm optimizes multi-player learning with noisy rewards without direct communication.
problem Cooperative multi-player learning with noisy rewards and no communication.
method Upper and lower confidence bounds algorithm for optimal action selection.
result Achieves logarithmic and regret.
Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the …