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.
168,657 papers · 148 categories
Trend · papers per month
48 results for “SGD algorithm”
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…
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.
Layered SGD: A Decentralized and Synchronous SGD Algorithm for Scalable Deep Neural Network Trainingcs.LG
Stochastic Gradient Descent (SGD) is the most popular algorithm for training deep neural networks (DNNs). As larger networks and datasets cause longer training times, training on distributed systems is common and distributed SGD variants, mainly asynchronous and synchronous SGD, are widely used. Asynchronous SGD is com…
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.
Bias-Variance Tradeoff in a Sliding Window Implementation of the Stochastic Gradient Algorithmstat.ML
This paper provides a framework to analyze stochastic gradient algorithms in a mean squared error (MSE) sense using the asymptotic normality result of the stochastic gradient descent (SGD) iterates. We perform this analysis by taking the asymptotic normality result and applying it to the finite iteration case. Specific…
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.
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.
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.
Distributed stochastic gradient descent (SGD) is essential for scaling the machine learning algorithms to a large number of computing nodes. However, the infrastructures variability such as high communication delay or random node slowdown greatly impedes the performance of distributed SGD algorithm, especially in a wir…
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 .
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.
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)…
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.
With the increase in the amount of data and the expansion of model scale, distributed parallel training becomes an important and successful technique to address the optimization challenges. Nevertheless, although distributed stochastic gradient descent (SGD) algorithms can achieve a linear iteration speedup, they are l…
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.
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.
In this work, we consider the resilience of distributed algorithms based on stochastic gradient descent (SGD) in distributed learning with potentially Byzantine attackers, who could send arbitrary information to the parameter server to disrupt the training process. Toward this end, we propose a new Lipschitz-inspired c…
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…
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.
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…
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.
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 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.
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 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.
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.
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.
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.
Stochastic Gradient Descent with a constant learning rate (constant SGD) simulates a Markov chain with a stationary distribution. With this perspective, we derive several new results. (1) We show that constant SGD can be used as an approximate Bayesian posterior inference algorithm. Specifically, we show how to adjust …
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.
Machine learning, especially deep neural networks, has been rapidly developed in fields including computer vision, speech recognition and reinforcement learning. Although Mini-batch SGD is one of the most popular stochastic optimization methods in training deep networks, it shows a slow convergence rate due to the larg…
MindFlayer SGD improves parallel SGD for heterogeneous, random compute times.
problem Minimizing nonconvex functions with heterogeneous, random compute times.
method MindFlayer SGD, designed for stochastic and heterogeneous delays.
result MindFlayer SGD outperforms existing methods in environments with heavy-tailed noise.
Paper improves privacy in SGD with low noise, achieving optimal risk rates.
problem Privacy-preserving machine learning with good performance.
method Differentially private SGD with low-noise analysis.
result Achieves optimal excess risk rates for non-smooth losses.
Paper improves learning rates for SGD and NAG.
problem Generalization performance of stochastic optimization algorithms.
method Establishes new learning rates for SGD and NAG.
result Improved guarantees in some settings or comparable rates under weaker assumptions.