Distributing Neural Network training is of particular interest for several reasons including scaling using computing clusters, training at data sources such as IOT devices and edge servers, utilizing underutilized resources across heterogeneous environments, and so on. Most contemporary approaches primarily address sca…
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 “gossip”
Floating Gossip improves continuous machine learning in a decentralized manner.
problem Continuous learning in infrastructure-less environments.
method Mean field approach to analyze the impact of communication and computing in Floating Gossip.
result Floating Gossip can effectively incorporate large amounts of data into machine learning models.
Paper proposes robust gossip algorithms for mean and trimmed mean estimation.
problem Vulnerability of mean-based gossip algorithms to malicious nodes.
method Developed extsc{GoRank} for rank estimation and extsc{GoTrim} for trimmed mean estimation.
result Established convergence rates for rank and trimmed mean estimation.
The paper gives bounds for how long it takes for gossip protocols to spread information in networks.
problem Understanding the diffusion time in asynchronous gossip protocols.
method Provides non-asymptotic bounds for the number of messages needed for consensus in asynchronous gossip protocols.
result Explicit formula and approximation for the number of messages needed for consensus in different types of graphs.
AsylADMM improves gossip-based learning for non-smooth objectives.
problem Efficient and robust decentralized learning on edge devices.
method Asynchronous gossip algorithm for non-smooth optimization.
result AsylADMM converges faster on non-smooth problems.
New gossip algorithms improve robustness of rank-based statistics in decentralized systems.
problem Ensuring robustness in decentralized AI and edge intelligence systems, especially in the presence of corrupted or adversarial data.
method Developed asynchronous gossip algorithms for computing rank-based statistics.
result First convergence rate bound for asynchronous gossip-based rank estimation.
On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimizationcs.LG
Multiple gossip steps improve decentralized optimization convergence.
problem Efficiently optimizing large-scale machine learning models with limited communication.
method Integrates multiple gossip steps between gradient descent iterations in compressed decentralized optimization.
result Convergence to within ε of the optimal value for smooth non-convex objectives.
A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipmath.OC
Continuized Nesterov acceleration accelerates stochastic gradient descent and gossip algorithms.
problem Improving the convergence rate of stochastic gradient descent and gossip algorithms.
method Introducing a continuized variant of Nesterov acceleration, which mixes variables continuously and takes gradient steps at random times.
result The continuized Nesterov acceleration achieves convergence rates similar to Nesterov's original acceleration but with random parameters.
Decentralized ranking consensus via gossip for robust and scalable systems.
problem Achieving reliable and resilient consensus on collective rankings in a decentralized setting.
method Random gossip communication for decentralized computation of global rankings.
result Robust and scalable consensus on collective rankings achieved through decentralized, local interactions.
We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communication bottleneck, the nodes compress (e.g. quantize or sparsi…
Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the netwo…
This paper proposes a gossip-based algorithm for distributed bilevel optimization over networks.
problem Distributed bilevel optimization over networks with limited communication.
method Gossip-based distributed bilevel learning algorithm.
result Achieves optimal sample complexities for general and strongly convex objectives.
We address the issue of speeding up the training of convolutional neural networks by studying a distributed method adapted to stochastic gradient descent. Our parallel optimization setup uses several threads, each applying individual gradient descents on a local variable. We propose a new way of sharing information bet…
Multi-simulator training has contributed to the recent success of Deep Reinforcement Learning by stabilizing learning and allowing for higher training throughputs. We propose Gossip-based Actor-Learner Architectures (GALA) where several actor-learners (such as A2C agents) are organized in a peer-to-peer communication t…
Unified framework for Byzantine robust gossip algorithms with guaranteed performance.
problem Vulnerability of decentralized machine learning to misbehaving devices.
method Introduces F-RG framework and CS+ robust aggregation rule for Byzantine resilience.
result CS+-RG has near-optimal breakdown tolerance and outperforms existing methods.
We address the issue of speeding up the training of convolutional networks. Here we study a distributed method adapted to stochastic gradient descent (SGD). The parallel optimization setup uses several threads, each applying individual gradient descents on a local variable. We propose a new way to share information bet…
In the era of big data, an important weapon in a machine learning researcher's arsenal is a scalable Support Vector Machine (SVM) algorithm. SVMs are extensively used for solving classification problems. Traditional algorithms for learning SVMs often scale super linearly with training set size which becomes infeasible …
We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two no…
Paper tightens lower bounds on decentralized training complexity.
problem Understanding and optimizing iteration complexity in decentralized training.
method Proved a tight lower bound on iteration complexity and proposed DeTAG algorithm.
result DeTAG achieves the theoretical lower bound with only a logarithmic gap.
The emerging concern about data privacy and security has motivated the proposal of federated learning, which allows nodes to only synchronize the locally-trained models instead their own original data. Conventional federated learning architecture, inherited from the parameter server design, relies on highly centralized…
GOAT learns multiple node representations from graph structure alone.
problem Context-free graph representation learning limits model performance.
method Inspired by gossip and mutual attention, GOAT learns multiple node representations.
result GOAT outperforms 12 SOTA baselines on link prediction and clustering tasks.
Efficient and robust algorithms for decentralized estimation in networks are essential to many distributed systems. Whereas distributed estimation of sample mean statistics has been the subject of a good deal of attention, computation of -statistics, relying on more expensive averaging over pairs of observations, is…
In decentralized networks (of sensors, connected objects, etc.), there is an important need for efficient algorithms to optimize a global cost function, for instance to learn a global model from the local data collected by each computing unit. In this paper, we address the problem of decentralized minimization of pairw…
A new approach corrects bias in federated learning due to varying communication links.
problem Bias in federated learning due to non-uniform and time-varying communication links.
method Proposes Federated Postponed Broadcast (FedPBC) to correct bias in Federated Average (FedAvg).
result FedPBC converges to a stationary point of the global objective, overcoming bias caused by varying communication links.
In this paper, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master/slave) algorithms, we show that distributing Nesterov's accelerated gradient descent is optimal and…
Novel algorithm for decentralized optimization in time-varying networks with delays.
problem Decentralized optimization in networks with communication delays.
method DT-GO algorithm, applicable to general directed graphs, converges to same complexity as centralized SGD.
result Algorithm DT-GO achieves convergence rates for convex and non-convex objectives, similar to centralized SGD.
RelaySum improves decentralized deep learning by uniformly distributing data across workers.
problem Handling data heterogeneity in decentralized deep learning.
method RelaySum uses spanning trees to distribute information exactly uniformly across all workers with finite delays.
result RelaySum is independent of data heterogeneity and scales to many workers, enabling highly accurate decentralized deep learning.
This paper examines ADMM for network averaging, revealing its convergence rates and network topology impacts.
problem Efficiently averaging local information over a network using ADMM.
method Comparative analysis of ADMM and other algorithms on a canonical distributed averaging problem.
result Characterization of ADMM convergence and optimal parameter tuning based on network spectral properties.
Stochastic gradient descent is a simple approach to find the local minima of a cost function whose evaluations are corrupted by noise. In this paper, we develop a procedure extending stochastic gradient descent algorithms to the case where the function is defined on a Riemannian manifold. We prove that, as in the Eucli…
Paper develops Byzantine-resilient algorithms for decentralized learning.
problem Vulnerability of distributed learning to Byzantine attacks.
method Dual approach for decentralized optimization.
result Convergence guarantees and experimental validation of the proposed algorithm.
Distributed data-parallel algorithms aim to accelerate the training of deep neural networks by parallelizing the computation of large mini-batch gradient updates across multiple nodes. Approaches that synchronize nodes using exact distributed averaging (e.g., via AllReduce) are sensitive to stragglers and communication…
We consider a set of learning agents in a collaborative peer-to-peer network, where each agent learns a personalized model according to its own learning objective. The question addressed in this paper is: how can agents improve upon their locally trained model by communicating with other agents that have similar object…
This paper develops efficient federated learning and unlearning methods in Bayesian models.
problem Managing epistemic uncertainty and legal right to be forgotten in decentralized networks.
method Develops federated variational inference solutions based on decentralized local free energy minimization.
result Demonstrates efficient unlearning mechanisms in federated learning and unlearning.
In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiase…
A novel fully asynchronous scheme for distributed reinforcement learning over networks.
problem Policy evaluation in distributed reinforcement learning over networks.
method Design of a stochastic average gradient (SAG) based distributed algorithm and push-pull augmented graph approach.
result The proposed algorithm converges at a linear rate of \(\mathcal{O}(c^k)\) with \(c\in(0,1)\) and \(k\) increasing by one per node update.
We propose and analyze a new stochastic gradient method, which we call Stochastic Unbiased Curvature-aided Gradient (SUCAG), for finite sum optimization problems. SUCAG constitutes an unbiased total gradient tracking technique that uses Hessian information to accelerate con- vergence. We analyze our method under the ge…
Unified analysis for decentralized SGD across various topologies and updates.
problem Analysis of decentralized SGD methods with changing topologies and local updates.
method Unified convergence analysis covering local SGD updates and adaptive network topology.
result Universal convergence rates for smooth problems, interpolating between heterogeneous and iid-data settings.
In this paper we present an optimization-based view of distributed parameter estimation and observational social learning in networks. Agents receive a sequence of random, independent and identically distributed (i.i.d.) signals, each of which individually may not be informative about the underlying true state, but the…
Distributed optimization is essential for training large models on large datasets. Multiple approaches have been proposed to reduce the communication overhead in distributed training, such as synchronizing only after performing multiple local SGD steps, and decentralized methods (e.g., using gossip algorithms) to decou…
Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To this end, several communication-reduction techniques, such as non-blocking communication, quantization, and local steps, have been explored i…
Improves decentralized learning by teleporting active nodes for better convergence.
problem Decentralized learning's convergence rate degrades with large node numbers.
method Activates a subset of nodes, fetches parameters from previous active nodes, updates, and performs gossip averaging on a small topology.
result Teleportation completely alleviates convergence rate degradation with proper node activation.
DESTRESS optimizes decentralized nonconvex optimization with optimal IFO complexity and efficient communication.
problem Decentralized nonconvex finite-sum optimization in multi-agent systems.
method DESTRESS uses stochastic recursive gradient updates, gradient tracking, and careful hyper-parameter choices to achieve optimal IFO complexity with efficient communication.
result DESTRESS matches the optimal IFO complexity of centralized algorithms while maintaining communication efficiency.
Stochastic gradient descent achieves polynomial convergence rates for noiseless linear models.
problem Convergence analysis of stochastic gradient descent in noiseless linear models.
method Fixed step-size stochastic gradient descent on least-square risk.
result Polynomial convergence rates depend on the regularities of the optimum and feature vectors.
New asynchronous algorithms improve speed in decentralized optimization networks.
problem Hard convergence analysis for asynchronous decentralized optimization.
method Continuized framework to analyze heterogeneous delays in event-driven updates.
result Achieves asynchronous speedup with convergence rate controlled by eigengap weighted by local delays.
We analyse the learning performance of Distributed Gradient Descent in the context of multi-agent decentralised non-parametric regression with the square loss function when i.i.d. samples are assigned to agents. We show that if agents hold sufficiently many samples with respect to the network size, then Distributed Gra…
Bayesian algorithms minimize cumulative regret in decentralized multi-agent bandits.
problem Minimizing cumulative regret in a decentralized multi-agent multi-armed bandit problem.
method Proposed decentralized Bayesian multi-armed bandit framework, including Thompson Sampling and Bayes-UCB algorithms.
result Regret scales logarithmically with constants matching those of an optimal centralized agent.
In this paper, we introduce a distributed version of the classical stochastic Multi-Arm Bandit (MAB) problem. Our setting consists of a large number of agents that collaboratively and simultaneously solve the same instance of armed MAB to minimize the average cumulative regret over all agents. The agents can co…
New algorithm for decentralized online convex optimization with unknown delays.
problem Decentralized online convex optimization with unknown, time-varying feedback delays.
method Proposes a novel algorithm that incorporates adaptive learning rates and gossip-based delay estimation.
result Achieves improved regret bounds of O(N √d tot + N √T (1-σ^2)^(1/4)) and O(N δmax ln T α) for different settings.