We provide tight finite-time convergence bounds for gradient descent and stochastic gradient descent on quadratic functions, when the gradients are delayed and reflect iterates from rounds ago. First, we show that without stochastic noise, delays strongly affect the attainable optimization error: In fact, the error…
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 “gradient delay”
AB dynamically scales gradients to mitigate asynchronous training delays.
problem Gradient delay in asynchronous training reduces model performance.
method Adaptive Braking (AB) dynamically scales gradients based on alignment.
result AB enables training with up to 32 update steps of delay without accuracy loss.
We present ErasureHead, a new approach for distributed gradient descent (GD) that mitigates system delays by employing approximate gradient coding. Gradient coded distributed GD uses redundancy to exactly recover the gradient at each iteration from a subset of compute nodes. ErasureHead instead uses approximate gradien…
Understanding the convergence performance of asynchronous stochastic gradient descent method (Async-SGD) has received increasing attention in recent years due to their foundational role in machine learning. To date, however, most of the existing works are restricted to either bounded gradient delays or convex settings.…
We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stochastic term which is not affected by the delay, and (ii) a higher …
This paper deals with bandit online learning problems involving feedback of unknown delay that can emerge in multi-armed bandit (MAB) and bandit convex optimization (BCO) settings. MAB and BCO require only values of the objective function involved that become available through feedback, and are used to estimate the gra…
Enhances SGLD for log-concave posteriors with asynchronous computation.
problem Sampling log-concave posterior distributions efficiently.
method Integrates asynchronous computation into SGLD with delayed gradients.
result Convergence in measure is not significantly affected by delayed gradient information.
We analyze the convergence of gradient-based optimization algorithms that base their updates on delayed stochastic gradient information. The main application of our results is to the development of gradient-based distributed optimization algorithms where a master node performs parameter updates while worker nodes compu…
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.
We study distributed stochastic convex optimization under the delayed gradient model where the server nodes perform parameter updates, while the worker nodes compute stochastic gradients. We discuss, analyze, and experiment with a setup motivated by the behavior of real-world distributed computation networks, where the…
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…
We develop and analyze an asynchronous algorithm for distributed convex optimization when the objective writes a sum of smooth functions, local to each worker, and a non-smooth function. Unlike many existing methods, our distributed algorithm is adjustable to various levels of communication cost, delays, machines compu…
New algorithm reduces distributed optimization time with stochastic delays.
problem Optimizing distributed data with stochastic delays.
method Developed ADSAGA, a variant of SAGA for distributed-data settings with stochastic delays.
result ADSAGA converges in $ ilde{O}\left(\left(n + \sqrt{m}κ
ight)\log(1/ε)
ight)$ iterations under mean delay .
We consider the problem of strongly-convex online optimization in presence of adversarial delays; in a T-iteration online game, the feedback of the player's query at time t is arbitrarily delayed by an adversary for d_t rounds and delivered before the game ends, at iteration t+d_t-1. Specifically for \algo{online-gradi…
New method speeds up training of large kernel models.
problem Scaling kernel machines to large datasets and model sizes.
method Delayed projections in Preconditioned Stochastic Gradient Descent (PSGD).
result Significant training speed up over existing methods.
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.
Delayed rejection HMC improves sampling efficiency for multiscale distributions.
problem Hamiltonian Monte Carlo struggles with wide-ranging distributions, especially in high-curvature areas.
method Introduces a delayed rejection variant of HMC, using geometrically smaller step sizes for retries.
result Up to five-fold performance gains in effective sample size per gradient evaluation.
New algorithms handle online prediction with bandit and delayed feedback, improving regret bounds.
problem Achieving finite bounds on surrogate regret with limited feedback.
method Proposed algorithms for bandit and delayed feedback, including inverse-weighted gradient and pseudo-inverse matrix estimators.
result Achieved improved surrogate regret bounds of and .
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…
FSGLD improves federated data sampling by correcting noisy gradients.
problem Noisy gradients and delayed communication in federated data.
method Conductive gradients to correct noisy gradients in distributed SGLD.
result FSGLD converges to true posterior even with delayed communication.
Time-continuous dimensional descriptions of emotions (e.g., arousal, valence) allow researchers to characterize short-time changes and to capture long-term trends in emotion expression. However, continuous emotion labels are generally not synchronized with the input speech signal due to delays caused by reaction-time, …
New RL algorithm handles delayed feedback with posterior sampling.
problem Challenges of delayed feedback in reinforcement learning with linear function approximation.
method Posterior sampling with delayed feedback for value-based RL.
result Achieves optimal regret guarantee with improved computational efficiency.
Improved online convex optimization with delayed feedback using curvature.
problem Online convex optimization with curved losses and delayed feedback.
method Variant of follow-the-regularized-leader and Online Newton Step algorithm with adaptive learning rate.
result Regret bounds of order for exp-concave losses.
Paper analyzes high probability convergence of adaptive SGD with momentum.
problem Theoretical understanding of adaptive SGD with momentum in nonconvex settings is incomplete.
method High probability analysis under weak assumptions.
result First high probability convergence proof for gradients to zero in Delayed AdaGrad with momentum.
In the present scenario of domestic flights in USA, there have been numerous instances of flight delays and cancellations. In the United States, the American Airlines, Inc. have been one of the most entrusted and the world's largest airline in terms of number of destinations served. But when it comes to domestic flight…
OMGD algorithm optimizes online convex optimization with switching costs and delayed gradients.
problem Optimizing online convex optimization with switching costs and delayed gradients.
method Proposed an online multiple gradient descent (OMGD) algorithm for quadratic and linear switching costs.
result OMGD achieves optimal dynamic regret in the limited information setting.
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.
New projection techniques reduce the frequency of projections in solving LCPs.
problem Solving linearly constrained problems efficiently with reduced projection frequency.
method Delayed projection technique to call a projection less frequently.
result Theoretical and practical improvements in convergence rates and efficiency.
Cyclic Data Parallelism reduces memory usage and balances gradient communications.
problem Training large deep learning models requires efficient parallelism to scale.
method Cyclic Data Parallelism shifts micro-batches from simultaneous to sequential execution, balancing memory and gradient communications.
result Cyclic Data Parallelism reduces total memory usage and balances gradient communications.
In this paper, we give a delay estimate of scalar curvature for a complete non-compact expanding (or steady) gradient Ricci soliton with nonnegative Ricci curvature. As an application, we prove that any complete non-compact expanding (or steady) gradient Kähler-Ricci solitons with positively pinched Ricci curvature sho…
Background: Recent developments have made it possible to accelerate neural networks training significantly using large batch sizes and data parallelism. Training in an asynchronous fashion, where delay occurs, can make training even more scalable. However, asynchronous training has its pitfalls, mainly a degradation in…
Performance of distributed optimization and learning systems is bottlenecked by "straggler" nodes and slow communication links, which significantly delay computation. We propose a distributed optimization framework where the dataset is "encoded" to have an over-complete representation with built-in redundancy, and the …
This paper explores a simple regularizer for reinforcement learning by proposing Generative Adversarial Self-Imitation Learning (GASIL), which encourages the agent to imitate past good trajectories via generative adversarial imitation learning framework. Instead of directly maximizing rewards, GASIL focuses on reproduc…
Grokking occurs at numerical stability edge, requiring regularization to prevent.
problem Delayed generalization in deep learning models.
method Identified Softmax Collapse (SC) as the cause of grokking without regularization.
result Mitigating SC enables grokking without regularization.
This paper proposes a new algorithm for learning guidance rewards in RL.
problem Long-term temporal credit assignment in sparse or delayed reward environments.
method Surrogate RL objective with trajectory-space smoothing to learn guidance rewards.
result Guidance rewards can be learned without additional neural networks and have intuitive interpretation.
New method for distributed online learning with communication constraints reduces joint regret.
problem Joint regret minimization in a distributed online learning setting with communication constraints.
method Adaptive graph partitioning and comparator-adaptive online convex optimization with delayed gradient information.
result Optimal graph partition selection for adversarial activations and gradients reduces joint regret.
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 …
Develops a stochastic approach to financial market delays.
problem Modeling delays in financial markets with multiple assets.
method Introduces a general stochastic framework for information and order execution delays.
result Delayed markets maintain fundamental asset pricing theorems and no asymptotic free lunch condition.
Paper tackles action delays in reinforcement learning, proposing a delay-aware framework.
problem Action delays degrade reinforcement learning performance in real-world systems.
method Formal definition of delay-aware MDP, transformation into standard MDP with augmented states, delay-aware model-based reinforcement learning framework.
result Proposed framework is more efficient in training and transferable between systems with various delay durations.
New algorithm tackles delayed feedback in Lipschitz bandits with sublinear regret.
problem Delayed feedback in Lipschitz bandits.
method Design of algorithms for bounded and unbounded stochastic delays.
result Sublinear regret guarantees for both bounded and unbounded delays.
New algorithms ensure fair selection in combinatorial semi-bandit with unrestricted delays.
problem Fair selection in stochastic combinatorial semi-bandit with delayed feedback.
method Introduced merit-based fairness constraints and new bandit algorithms for reward and fairness.
result Achieved sublinear expected reward and fairness regrets with dependence on delay distribution quantiles.
This work provides formal guarantees for heuristic optimization methods in machine learning.
problem Lack of theoretical understanding of heuristic optimization methods in machine learning.
method Analysis and formal guarantees for AdaGrad, SGD with exponential and cosine step sizes, and momentum methods.
result First formal guarantees for AdaGrad and SGD variants, including convergence and adaptivity to noise.
Banker-OMD improves online learning with delayed feedback.
problem Handling delayed feedback in online learning.
method Generalized Online Mirror Descent (OMD) framework.
result Achieves nearly-optimal performance in three bandit scenarios.
Distributed descent-based methods are an essential toolset to solving optimization problems in multi-agent system scenarios. Here the agents seek to optimize a global objective function through mutual cooperation. Oftentimes, cooperation is achieved over a wireless communication network that is prone to delays and erro…
New algorithm handles delayed feedback robustly, reducing regret without knowing delay bounds.
problem Bandits with variably delayed feedback, especially excessive delays.
method Implicit exploration scheme, adaptive skipping, drifted regret control.
result Can tolerate arbitrary excessive delays up to order T, reducing regret.
Paper tackles delays in multi-agent reinforcement learning, improving performance.
problem Challenges in reinforcement learning due to delays in real-world systems.
method Proposes a novel framework for multi-agent reinforcement learning with delays, using Delay-Aware Markov Games and centralized-decentralized training.
result Demonstrates significant improvement in performance with delay-aware multi-agent reinforcement learning.
Synchronization in a market model with time delaysphysics.soc-ph
Study on synchronization in financial markets with time delays.
problem Understanding market dynamics and synchronization in financial systems with time delays.
method Examined a system of coupled non-linear delay-differential equations, linearized for small delays, and analyzed collective dynamics using bifurcation diagrams and numerical solutions.
result Demonstrated that limit cycles can be maintained in coupled N-asset models with appropriate parameterization, leading to market synchronization.
New algorithm tackles stochastic bandits with varying arm-dependent delays.
problem Applying existing algorithms to stochastic delayed bandit settings is restricted by strong assumptions on delay distributions.
method Proposes a simple UCB-based algorithm called PatientBandits that weakens assumptions on delay distributions.
result Provides bounds on regret and performance lower bounds for the PatientBandits algorithm.