Communication-efficient SGD algorithms, which allow nodes to perform local updates and periodically synchronize local models, are highly effective in improving the speed and scalability of distributed SGD. However, a rigorous convergence analysis and comparative study of different communication-reduction strategies rem…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “SGD algorithms”
Stochastic gradient descent (SGD) is a popular stochastic optimization method in machine learning. Traditional parallel SGD algorithms, e.g., SimuParallel SGD, often require all nodes to have the same performance or to consume equal quantities of data. However, these requirements are difficult to satisfy when the paral…
Layered SGD: A Decentralized and Synchronous SGD Algorithm for Scalable Deep Neural Network Trainingcs.LG
LSGD improves deep learning training efficiency by synchronizing and decentralizing SGD.
problem Asynchronous SGD's accuracy issues and synchronous SGD's communication inefficiency.
method LSGD divides nodes into subgroups with centralized communication and decentralized computation.
result LSGD achieves better accuracy and efficiency than synchronous and asynchronous SGD.
New bounds for M-SGD show its error distribution is nearly Gaussian.
problem Understanding the error distribution of M-SGD.
method Proved non-asymptotic bounds for M-SGD in Wasserstein distance.
result Error distribution of M-SGD is approximately Gaussian.
Overlap-Local-SGD improves distributed SGD by overlapping communication and computation.
problem High communication delay and node slowdown in distributed SGD.
method Adding an anchor model to synchronize local updates and pull them towards the anchor model.
result Overlap-Local-SGD speeds up distributed training and mitigates straggler effects.
Communication-Efficient, 2D Parallel Stochastic Gradient Descent for Distributed-Memory Optimizationcs.DC
HybridSGD improves SGD performance by balancing computation and communication.
problem Limited scalability and performance of SGD due to communication costs.
method 2D parallel SGD method (HybridSGD) that trades off between 1D -step SGD and 1D Federated SGD (FedAvg).
result HybridSGD achieves better convergence than FedAvg at similar processor scales and up to 121x speedup over FedAvg.
SQuARM-SGD improves decentralized SGD efficiency with momentum.
problem Efficient decentralized training of large-scale models over networks.
method Fixed local SGD steps with Nesterov's momentum, sparsified and quantized updates, locally computed triggering criterion.
result Convergence rate matches vanilla SGD, momentum improves test performance.
Bias-Variance Tradeoff in a Sliding Window Implementation of the Stochastic Gradient Algorithmstat.ML
The paper analyzes SW-SGD for MSE in biased and variance-reduced gradient estimators.
problem Analyzing MSE of SW-SGD in biased and variance-reduced gradient estimators.
method Using asymptotic normality, the paper characterizes SW-SGD's mean and variance, proving convergence and showing SW-SGD's superiority over SGD.
result SW-SGD incurs lower MSE than SGD on quadratic and convex problems.
Paper explores using bootstrap methods to improve SGD's stability and robustness.
problem Improving the stability and robustness of SGD.
method Investigates empirical bootstrap approaches for SGD from algorithmic stability and statistical robustness perspectives.
result Demonstrates construction of purely distribution-free confidence intervals using bootstrap SGD.
AdaCliP reduces noise in private SGD training.
problem Privacy preserving machine learning over user data.
method Adaptive clipping of gradients to reduce noise in private SGD.
result AdaCliP adds less noise and improves model accuracy.
A new algorithm speeds up deep learning training by decoupling computation and communication.
problem High communication cost limits the speedup of distributed SGD.
method CoCoD-SGD: runs computation and communication in parallel.
result Linear time speedup with respect to hardware resources.
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.
Adaptive step-size method improves compressed SGD performance in machine learning.
problem Communication bottleneck in distributed and decentralized optimization.
method Developed an adaptive step-size method for compressed SGD.
result Order-optimal convergence rates for various objective functions.
Stochastic Gradient Descent (SGD) is an important algorithm in machine learning. With constant learning rates, it is a stochastic process that, after an initial phase of convergence, generates samples from a stationary distribution. We show that SGD with constant rates can be effectively used as an approximate posterio…
A new algorithm combines SGD and Thompson Sampling for contextual bandits.
problem Finding efficient algorithms for contextual bandits with low time and memory complexity.
method Online Stochastic Gradient Descent (SGD) combined with Thompson Sampling.
result Achieves regret with linear time complexity in and .
While significant progress has been made separately on analytics systems for scalable stochastic gradient descent (SGD) and private SGD, none of the major scalable analytics frameworks have incorporated differentially private SGD. There are two inter-related issues for this disconnect between research and practice: (1)…
Smoothed SGD improves quantile estimation without crossing curves.
problem Estimating quantiles without crossing estimated curves.
method Smoothed SGD algorithm with Bahadur representation and Gaussian approximation.
result Smoothed SGD provides non-asymptotic tail probability bounds and a Gaussian approximation for quantile estimates.
An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biasstat.ML
SGD's uncertainty quantified in non-convex learning problems.
problem Uncertainty quantification in non-convex learning problems.
method Asymptotic normality of SGD iterates and bias characterization.
result SGD iterates are asymptotically normally distributed around the expected value of the invariant distribution.
Most commonly used distributed machine learning systems are either synchronous or centralized asynchronous. Synchronous algorithms like AllReduce-SGD perform poorly in a heterogeneous environment, while asynchronous algorithms using a parameter server suffer from 1) communication bottleneck at parameter servers when wo…
Making SGD Parameter-Freemath.OC
Develops a parameter-free SGD algorithm with optimal convergence rate.
problem Optimizing parameters in stochastic convex optimization.
method A novel parameter-free algorithm for SGD with high-probability guarantees and adaptive properties.
result Achieves optimal convergence rate with only a double-logarithmic factor increase compared to known-parameter settings.
ARFF reduces spectral bias in SGD-trained neural networks.
problem Spectral bias in two-layer neural networks.
method Comparison of SGD and ARFF on spectral bias and robustness.
result ARFF yields a closer to zero spectral bias compared to SGD.
This paper improves Minibatch SGD convergence through typicality sampling.
problem Slow convergence of Minibatch SGD due to large gradient noise.
method Typicality sampling for more efficient batch selection.
result Typical batch SGD outperforms conventional Minibatch SGD in convergence.
ROOT-SGD solves convex optimization problems with optimal nonasymptotic and near-optimal asymptotic performance.
problem Solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms.
method ROOT-SGD: Recursive One-Over-T SGD, averaging past stochastic gradients.
result Achieves state-of-the-art performance in both nonasymptotic and asymptotic senses.
New insights into SGD and SGD-M in high dimensions.
problem Understanding and comparing SGD and SGD-M in high-dimensional settings.
method Developed high-dimensional scaling limits for SGD-M and online SGD, examining their dynamics and performance.
result SGD-M amplifies high-dimensional effects, potentially degrading performance compared to online SGD.
One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a…
New algorithm resists up to half of Byzantine workers in distributed learning.
problem Resilience of distributed SGD in the presence of Byzantine attackers.
method Lipschitz-inspired coordinate-wise median approach (LICM-SGD).
result LICM-SGD can resist up to half of Byzantine workers in non-convex settings.
Sketched SGD reduces communication in distributed SGD by sketching gradients.
problem Limited communication in large-scale distributed training of neural networks.
method Introducing Sketched SGD, an algorithm that communicates sketches of gradients instead of full gradients.
result Sketched SGD reduces communication from or to , achieving up to 40x reduction in total communication cost.
This paper improves convergence guarantees for SGD algorithms in non-convex smooth functions.
problem Theoretical convergence properties of SGD algorithms for non-convex smooth functions.
method Analysis of SGD algorithms with arbitrary data ordering for non-convex smooth functions.
result Enhanced convergence guarantees for incremental gradient and single shuffle SGD, improving the optimization term of convergence guarantee.
New algorithm reduces privacy loss in SGD without learning rate tuning.
problem Locally differentially private stochastic optimization with high privacy loss.
method BANCO (Betting Algorithm for Noisy COins) for -LDP SGD.
result Matches convergence rate of tuned SGD without learning rate tuning.
A distributed SGD method for heterogeneous networks with hubs and workers.
problem Learning in heterogeneous multi-level networks with worker heterogeneity and varying communication.
method Multi-Level Local SGD: distributed SGD with hub-and-spoke paradigm and hub averaging.
result The method converges with error dependent on worker heterogeneity, hub network topology, and iterations.
New algorithm optimizes linear system estimation from single trajectory.
problem Estimating LTI systems from a single trajectory.
method SGD with Reverse Experience Replay ()
result Optimal guarantees for parameter and prediction errors.
Two new covariance estimators for ROOT-SGD improve statistical inference.
problem Uncertainty measurement for ROOT-SGD's normal distribution estimator.
method Developed two covariance estimators: plug-in and Hessian-free.
result Hessian-free estimator is asymptotically consistent and Hessian-free.
New stability bounds for SGD on nonsmooth convex losses.
problem Understanding stability of SGD on nonsmooth convex losses.
method Sharp upper and lower bounds for SGD and full-batch GD on nonsmooth convex losses.
result SGD can be less stable but still useful for generalization bounds.
Stochastic Gradient Descent (SGD) is one of the most widely used techniques for online optimization in machine learning. In this work, we accelerate SGD by adaptively learning how to sample the most useful training examples at each time step. First, we show that SGD can be used to learn the best possible sampling distr…
SGD in linear regression overfits but performs well due to bias-variance trade-off.
problem Understanding overfitting in SGD for linear regression.
method Constant-stepsize SGD with iterate averaging or tail averaging, analyzing full eigenspectrum of data covariance matrix.
result Sharp excess risk bounds revealing bias-variance decomposition for SGD in linear regression.
New algorithm improves distributed SGD with random sparsification for better convergence and generalization.
problem Communication bottleneck in distributed deep learning.
method Proposes detached error feedback (DEF) algorithm to improve convergence and generalization of communication-efficient distributed SGD.
result Shows better convergence and generalization bounds than existing methods.
New framework limits SGD for multi-index models, addressing SQ framework shortcomings.
problem Limitations of SGD for multi-index models beyond SQ framework.
method Developed a new non-SQ framework to study SGD limitations for single-index and multi-index models.
result Applies to broad settings and architectures, including neural networks.
Paper analyzes D-SGD convergence with heterogeneous data and proposes topology learning.
problem Efficiently dealing with data heterogeneity in decentralized learning.
method Revisits D-SGD analysis, introduces neighborhood heterogeneity, and proposes topology learning.
result Formulates topology learning as a tractable optimization problem and demonstrates its effectiveness.
Stochastic gradient descent (SGD) is a ubiquitous algorithm for a variety of machine learning problems. Researchers and industry have developed several techniques to optimize SGD's runtime performance, including asynchronous execution and reduced precision. Our main result is a martingale-based analysis that enables us…
New algorithms optimize without tuning, matching tuned SGD performance.
problem Optimizing machine learning models without manual hyperparameter tuning.
method Formalizes tuning-free algorithms for matching SGD performance with loose hints.
result Tuning-free algorithms can match SGD performance, but not optimal convergence rates.
SGD implicitly regularizes linear regression problems better than ridge regression for many cases.
problem Understanding implicit regularization in linear regression problems.
method Comparing SGD and ridge regression on a broad class of least squares problems.
result SGD generalizes no worse than ridge regression for many problem instances, sometimes better.
Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysiscs.LG
Continuous-time analysis shows SGD with noise prefers flat minima.
problem Optimizing neural networks using SGD with noise.
method Continuous-time model for SGD with noise analysis.
result Optimization prefers flat minima in certain noise regimes.
SGD improves generalization by using gradient variability as a proxy for data randomness.
problem Improving generalization in machine learning models trained with stochastic gradient descent.
method Bootstrap perspective on SGD, analyzing gradient variability and algorithmic variability.
result SGD avoids spurious solutions and improves generalization by implicitly regularizing the trace of the gradient covariance matrix.
Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglerscs.LG
Adaptive distributed SGD reduces delay in slow workers.
problem Minimizing delay in distributed SGD with stragglers.
method Adaptive policy for varying to optimize error-runtime trade-off.
result Numerical simulations confirm the effectiveness of the adaptive approach.
S-SGD: Symmetrical Stochastic Gradient Descent with Weight Noise Injection for Reaching Flat Minimacs.LG
S-SGD adds symmetrical noise to weights to avoid sharp minima in deep learning.
problem SGD does not always converge to a flat minimum, leading to poor generalization.
method Symmetrical weight noise injection in SGD.
result S-SGD outperforms conventional SGD and weight-noise injection methods in large batch training.
Paper shows local SGD outperforms mini-batch SGD under certain conditions.
problem Proving local SGD's superiority in distributed learning with heterogeneous data.
method New lower and upper bounds for local SGD under first-order heterogeneity assumptions.
result Local SGD is min-max optimal under certain conditions, resolving understanding of distributed optimization.
This research explains why SGD generalizes better than ADAM in deep learning.
problem Understanding the generalization gap between SGD and ADAM in deep learning.
method Analyzing local convergence behaviors through Levy-driven stochastic differential equations (SDEs).
result SGD is more locally unstable and better escapes from sharp minima to flatter ones, leading to better generalization.
New SGD algorithm finds critical points faster with second-order corrections.
problem Finding critical points in non-convex optimization efficiently.
method Uses Hessian-vector products to correct momentum bias in SGD.
result Finds -critical points in time.