Stochastic gradient MCMC (SG-MCMC) has played an important role in large-scale Bayesian learning, with well-developed theoretical convergence properties. In such applications of SG-MCMC, it is becoming increasingly popular to employ distributed systems, where stochastic gradients are computed based on some outdated par…
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,694 papers · 148 categories
Trend · papers per month
48 results for “gradient staleness”
Cloud computing is becoming increasingly popular as a platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is non-dedicated, as is common in cloud computing. Asynchronous SGD (ASGD) methods are i…
Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characteriz…
Asynchronous SGD can speed up training with a trade-off of gradient staleness.
problem Asynchronous SGD suffers from gradient staleness, affecting convergence error.
method Theoretical analysis of the error-runtime trade-off considering random straggling delays.
result A method of gradually varying synchronicity in distributed SGD is proposed and demonstrated.
Faster Asynchronous SGDstat.ML
Asynchronous distributed stochastic gradient descent methods have trouble converging because of stale gradients. A gradient update sent to a parameter server by a client is stale if the parameters used to calculate that gradient have since been updated on the server. Approaches have been proposed to circumvent this pro…
HPSGD speeds up DNN training by paralleling data sync with local training.
problem Low cluster utilization in distributed deep neural network training.
method Hierarchical Parallel SGD (HPSGD) with improved model updating for stale gradients.
result Significantly boosts distributed DNN training and reduces stale gradients.
Many distributed machine learning (ML) systems adopt the non-synchronous execution in order to alleviate the network communication bottleneck, resulting in stale parameters that do not reflect the latest updates. Despite much development in large-scale ML, the effects of staleness on learning are inconclusive as it is …
This paper presents Rudra, a parameter server based distributed computing framework tuned for training large-scale deep neural networks. Using variants of the asynchronous stochastic gradient descent algorithm we study the impact of synchronization protocol, stale gradient updates, minibatch size, learning rates, and n…
Although distributed computing can significantly reduce the training time of deep neural networks, scaling the training process while maintaining high efficiency and final accuracy is challenging. Distributed asynchronous training enjoys near-linear speedup, but asynchrony causes gradient staleness - the main difficult…
DG separates successes and failures by gating updates with advantage and surprisal.
problem Negative learning from surprising data in distributed reinforcement learning.
method DG gates each update with the product of advantage and surprisal, suppressing failures and preserving successes.
result DG outperforms other methods in various challenging reinforcement learning tasks.
Data parallelism has become the de facto standard for training Deep Neural Network on multiple processing units. In this work we propose DC-S3GD, a decentralized (without Parameter Server) stale-synchronous version of the Delay-Compensated Asynchronous Stochastic Gradient Descent (DC-ASGD) algorithm. In our approach, w…
This work addresses the instability in asynchronous data parallel optimization. It does so by introducing a novel distributed optimizer which is able to efficiently optimize a centralized model under communication constraints. The optimizer achieves this by pushing a normalized sequence of first-order gradients to a pa…
Most stochastic optimization methods use gradients once before discarding them. While variance reduction methods have shown that reusing past gradients can be beneficial when there is a finite number of datapoints, they do not easily extend to the online setting. One issue is the staleness due to using past gradients. …
Unified proof for scalable personalized federated learning.
problem Personalized federated learning under asynchronous updates.
method Unified proof for asynchronous federated learning with bounded staleness applied to MAML and ME personalization frameworks.
result Unified proof for convergence to first-order stationary point for smooth and non-convex functions.
Training the deep convolutional neural network for computer vision problems is slow and inefficient, especially when it is large and distributed across multiple devices. The inefficiency is caused by the backpropagation algorithm's forward locking, backward locking, and update locking problems. Existing solutions for a…
Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updatescs.LG
New insights explain speedup saturation in distributed learning with large batches and delays.
problem Understanding and optimizing speedup in distributed learning with large batches and delays.
method Theoretical analysis of strongly convex, convex, and non-convex settings, considering data sparsity.
result Identification of a data-dependent parameter explaining speedup saturation in both batch size and gradient staleness.
We make policy optimization algorithms batch size-invariant by decoupling proximal and behavior policies.
problem Some policy optimization algorithms do not have batch size-invariance, leading to inefficiencies.
method We decouple the proximal policy from the behavior policy to achieve batch size-invariance.
result Our approach makes policy optimization algorithms more efficient and allows them to use stale data more effectively.
Asynchronous computation and gradient compression have emerged as two key techniques for achieving scalability in distributed optimization for large-scale machine learning. This paper presents a unified analysis framework for distributed gradient methods operating with staled and compressed gradients. Non-asymptotic bo…
We consider parallel asynchronous Markov Chain Monte Carlo (MCMC) sampling for problems where we can leverage (stochastic) gradients to define continuous dynamics which explore the target distribution. We outline a solution strategy for this setting based on stochastic gradient Hamiltonian Monte Carlo sampling (SGHMC) …
Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneitycs.LG
Rescaled ASGD optimizes distributed learning under heterogeneous data.
problem Vanilla ASGD biases towards a frequency-weighted average of local objectives.
method Rescale worker stepsizes by their computation times.
result Rescaled ASGD converges to the correct global objective in fixed-computation model.
We propose Zeno++, a new robust asynchronous Stochastic Gradient Descent~(SGD) procedure which tolerates Byzantine failures of the workers. In contrast to previous work, Zeno++ removes some unrealistic restrictions on worker-server communications, allowing for fully asynchronous updates from anonymous workers, arbitrar…
LASG: Lazily Aggregated Stochastic Gradients for Communication-Efficient Distributed Learningmath.OC
This paper targets solving distributed machine learning problems such as federated learning in a communication-efficient fashion. A class of new stochastic gradient descent (SGD) approaches have been developed, which can be viewed as the stochastic generalization to the recently developed lazily aggregated gradient (LA…
FedBuff improves federated learning scalability with asynchronous updates.
problem Limited scalability of federated learning with synchronous updates.
method Introduces asynchronous updates (staleness) in federated learning.
result Theoretical analysis shows improved convergence rate with boundedness removed.
A new correction term improves sample efficiency in deep reinforcement learning.
problem Momentum accumulation in TD learning leads to doubly stale gradients.
method Proposed a correction term to address the issue of doubly stale gradients.
result Improves sample efficiency in policy evaluation.
New asynchronous SGD algorithms achieve optimal performance in distributed learning.
problem Asynchronous training introduces staleness, complicating optimization analysis.
method Developed rigorous framework for asynchronous first order stochastic optimization.
result Asynchronous SGD can achieve optimal time complexity, matching synchronous methods.
This paper develops a communication-efficient algorithm to solve the stochastic optimization problem defined over a distributed network, aiming at reducing the burdensome communication in applications such as distributed machine learning.Different from the existing works based on quantization and sparsification, we int…
Asynchronous federated modeling improves spatial data sharing without centralizing raw data.
problem Privacy and bandwidth constraints in distributed spatial data.
method Asynchronous federated modeling using low-rank Gaussian process approximations with block-wise optimization and adaptive strategies.
result Asynchronous federated modeling achieves synchronous performance and outperforms it in heterogeneous settings.
Deep learning is a popular machine learning technique and has been applied to many real-world problems. However, training a deep neural network is very time-consuming, especially on big data. It has become difficult for a single machine to train a large model over large datasets. A popular solution is to distribute and…
Asynchronous distributed machine learning solutions have proven very effective so far, but always assuming perfectly functioning workers. In practice, some of the workers can however exhibit Byzantine behavior, caused by hardware failures, software bugs, corrupt data, or even malicious attacks. We introduce \emph{Karda…
Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient s…
It is inevitable to train large deep learning models on a large-scale cluster equipped with accelerators system. Deep gradient compression would highly increase the bandwidth utilization and speed up the training process but hard to implement on ring structure. In this paper, we find that redundant gradient and gradien…
Gradient-based methods introduce noise that penalizes models sensitive to weight perturbations.
problem Noise in gradient-based optimization methods.
method Analysis of Gradient Descent (GD) and Stochastic Gradient Descent (SGD) updating all parameters simultaneously.
result Noise introduced by simultaneous parameter updates penalizes models sensitive to weight perturbations.
Momentum SGD fails to track nonstationary optima due to drift amplification.
problem Tracking nonstationary optima in stochastic optimization.
method Theoretical analysis of SGD and momentum variants under strong convexity and smoothness.
result Momentum incurs a drift-amplification penalty that diverges as the momentum parameter approaches 1, leading to systematic lag.
Triangle Feesq-fin.MF
Triangle fees adjust fees based on trade size and price movement, improving price accuracy and revenue.
problem Price staleness and low fee revenue in AMMs.
method Decreasing marginal fees proportional to price movement, creating incentives for price accuracy.
result Triangle fees strictly improve the Pareto frontier of price accuracy versus losses.
New framework allows selective removal of stale data in option calibration.
problem Inability to remove old data from calibrated option pricing models without full retraining.
method Introduces operator-theoretic Gauss-Newton framework for selective forgetting.
result Provides stability guarantees and perturbation bounds for selective data removal.
Large scale machine learning is increasingly relying on distributed optimization, whereby several machines contribute to the training process of a statistical model. In this work we study the performance of asynchronous, distributed settings, when applying sparsification, a technique used to reduce communication overhe…
This paper analyzes error feedback in compressed federated learning for non-convex optimization problems.
problem Reducing communication cost in federated learning with biased gradient compression.
method Proposes Fed-EF, a compressed federated learning scheme with error feedback, and analyzes its convergence rate and performance under partial client participation.
result Fed-EF can match the convergence rate of full-precision FL under data heterogeneity with a linear speedup and no extra slow-down factor due to stale error compensation.
CWGD measures gradient diversity weighted by curvature, improving SGD convergence.
problem Gradient noise in high-curvature directions is underestimated by standard methods.
method CWGD weights gradient diversity by the inverse square root of the Hessian.
result CWGD-Cosine reduces optimization error by up to 20% compared to standard cosine annealing.
A new algorithm removes stale observations in dynamic Bayesian optimization.
problem Optimizing functions that change over time, keeping track of the optimum.
method Wasserstein distance-based criterion to quantify relevancy, removing stale observations.
result W-DBO maintains good predictive performance and high sampling frequency.
In machine learning, asynchronous parallel stochastic gradient descent (APSGD) is broadly used to speed up the training process through multi-workers. Meanwhile, the time delay of stale gradients in asynchronous algorithms is generally proportional to the total number of workers, which brings additional deviation from …
Unified analysis of asynchronous-SGD algorithms for distributed learning.
problem Analyzing asynchronous-SGD in heterogeneous settings with varying speeds and data distributions.
method Unified convergence theory for non-convex smooth functions, including pure asynchronous SGD and its modifications.
result Unified convergence rates for various asynchronous algorithms, including novel methods.
New TVBO algorithm optimizes time-varying functions with varying sampling frequencies.
problem Optimizing time-varying, expensive, noisy functions with constant frequency assumption.
method Formulated practical recommendations and derived upper regret bound for varying sampling frequencies.
result BOLT algorithm outperforms state-of-the-art TVBO algorithms in experiments.
This paper introduces Selective-Backprop, a technique that accelerates the training of deep neural networks (DNNs) by prioritizing examples with high loss at each iteration. Selective-Backprop uses the output of a training example's forward pass to decide whether to use that example to compute gradients and update para…
A fast method for estimating radar amplitude density parameters.
problem Accurate estimation of amplitude density function parameters in radar applications.
method Projecting amplitude data onto horizontal and vertical axes, then using MLE for -stale distribution parameters.
result The average of computed MLEs based on two projections is a fast and accurate estimator for amplitude distribution parameters.
This paper investigates Shampoo's heuristics and decouples preconditioner updates.
problem Improving Shampoo's heuristics for training neural networks.
method Decomposing preconditioner updates, correcting eigenvalues, and adapting eigenbasis computation frequency.
result Principled techniques to remove Shampoo's heuristics and improve training algorithms.
New model learning objective improves continuous control tasks.
problem Challenges in solving continuous control tasks using model-based reinforcement learning.
method Derived a novel value-aware model learning objective and identified and addressed stale value estimates issue.
result Value-aware objectives can be successfully deployed in solving continuous control tasks without tuning hyper-parameters.
Ringmaster LMO accelerates training in distributed systems by asynchronously updating neural networks.
problem Asynchronous training in distributed systems where workers compute gradients at different speeds.
method Introduces an asynchronous LMO-based momentum method for unconstrained stochastic nonconvex optimization.
result Establishes convergence guarantees and time complexity bounds for asynchronous LMO-based updates.
Machine learning (ML) training algorithms often possess an inherent self-correcting behavior due to their iterative-convergent nature. Recent systems exploit this property to achieve adaptability and efficiency in unreliable computing environments by relaxing the consistency of execution and allowing calculation errors…