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 …
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,657 papers · 148 categories
Trend · papers per month
48 results for “staleness”
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…
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.
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…
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.
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…
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.
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…
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…
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…
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…
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.
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 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…
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.
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.
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.
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.
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.
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. …
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.
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.
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.
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.
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…
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…
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…
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) …
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.
New formula identifies and quantifies costs for automated market makers.
problem Adverse selection costs faced by liquidity providers in automated market makers.
method Derives a Black-Scholes-like formula for AMMs and identifies loss-versus-rebalancing cost.
result Closed-form expressions for LVR applicable to all automated market makers.
We introduce a reinforcement learning framework for retail robo-advising. The robo-advisor does not know the investor's risk preference, but learns it over time by observing her portfolio choices in different market environments. We develop an exploration-exploitation algorithm which trades off costly solicitations of …
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.
MLtuner automatically tunes settings for training tunables (such as the learning rate, the momentum, the mini-batch size, and the data staleness bound) that have a significant impact on large-scale machine learning (ML) performance. Traditionally, these tunables are set manually, which is unsurprisingly error-prone and…
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.
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…
Every day, hundreds of millions of new Tweets containing over 40 languages of ever-shifting vernacular flow through Twitter. Models that attempt to extract insight from this firehose of information must face the torrential covariate shift that is endemic to the Twitter platform. While regularly-retrained algorithms can…
We present two sampled quasi-Newton methods (sampled LBFGS and sampled LSR1) for solving empirical risk minimization problems that arise in machine learning. Contrary to the classical variants of these methods that sequentially build Hessian or inverse Hessian approximations as the optimization progresses, our proposed…
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…
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…
We consider the sequential Bayesian optimization problem with bandit feedback, adopting a formulation that allows for the reward function to vary with time. We model the reward function using a Gaussian process whose evolution obeys a simple Markov model. We introduce two natural extensions of the classical Gaussian pr…
We consider the problem of efficiently constructing cheap and novel round trip flight itineraries by combining legs from different airlines. We analyse the factors that contribute towards the price of such itineraries and find that many result from the combination of just 30% of airlines and that the closer the departu…
Using the most comprehensive, commercially-available dataset of trading activity in U.S. equity markets, we catalog and analyze quote dislocations between the SIP National Best Bid and Offer (NBBO) and a synthetic BBO constructed from direct feeds. We observe a total of over 3.1 billion dislocation segments in the Russ…
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…