We study local SGD (also known as parallel SGD and federated averaging), a natural and frequently used stochastic distributed optimization method. Its theoretical foundations are currently lacking and we highlight how all existing error guarantees in the convex setting are dominated by a simple baseline, minibatch SGD.…
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 “SGD methods”
Stochastic gradient descent~(SGD) and its variants have become more and more popular in machine learning due to their efficiency and effectiveness. To handle large-scale problems, researchers have recently proposed several parallel SGD methods for multicore systems. However, existing parallel SGD methods cannot achieve…
Paper bridges statistical inference for DP-SGD, a privacy-preserving machine learning method.
problem Asymptotic statistical inference for Differentially Private Stochastic Gradient Descent (DP-SGD).
method Established asymptotic properties of SGD under randomized subsampling, extended to DP-SGD, proposed methods for constructing valid confidence intervals.
result Valid confidence intervals for DP-SGD output achieve nominal coverage rates while maintaining privacy.
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.
Untuned SGD converges but with an exponential dependence on smoothness, adaptive methods prevent this.
problem The exponential dependence on smoothness in untuned SGD's convergence rate.
method Untuned SGD with arbitrary stepsize η, adaptive methods like NSGD, AMSGrad, and AdaGrad.
result Adaptive methods prevent the exponential dependence on smoothness in SGD.
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.
Ringmaster ASGD improves Asynchronous SGD's efficiency under varying worker times.
problem Suboptimal performance of Asynchronous SGD under heterogeneous worker computation times.
method Ringmaster ASGD, a novel Asynchronous SGD method with optimal time complexity.
result Ringmaster ASGD achieves optimal time complexity under arbitrary worker heterogeneity.
Due to its efficiency and ease to implement, stochastic gradient descent (SGD) has been widely used in machine learning. In particular, SGD is one of the most popular optimization methods for distributed learning. Recently, quantized SGD (QSGD), which adopts quantization to reduce the communication cost in SGD-based di…
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…
This work characterizes the benefits of averaging schemes widely used in conjunction with stochastic gradient descent (SGD). In particular, this work provides a sharp analysis of: (1) mini-batching, a method of averaging many samples of a stochastic gradient to both reduce the variance of the stochastic gradient estima…
Nesterov SGD is widely used for training modern neural networks and other machine learning models. Yet, its advantages over SGD have not been theoretically clarified. Indeed, as we show in our paper, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceleration o…
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.
SGD methods fail to converge to global minimizers in deep neural networks with ReLU activation.
problem Failure of SGD methods to converge to global minimizers in deep neural networks.
method Stochastic Gradient Descent (SGD) and its variants like Adam, RMSProp, etc.
result SGD methods fail to converge to global minimizers with high probability in deep neural networks with ReLU activation.
The paper analyzes the variance of different shuffling methods in stochastic gradient descent.
problem Understanding the variance of different shuffling methods in stochastic gradient descent.
method Power spectral density analysis to study the noise sequences of stochastic gradients.
result The stationary variances of iterates decrease in the order of SGD, SGD-RR, and SGD-SO.
Enhanced ROOT-SGD optimizes stochastic optimization with diminishing stepsizes.
problem Improving statistical efficiency in stochastic optimization.
method Integrates a diminishing stepsize strategy into ROOT-SGD.
result Achieves optimal convergence rates with improved stability and precision.
Derives effective continuous dynamics for adaptive SGD methods.
problem Analyzing noise in adaptive SGD methods.
method Stochastic modified equations framework and Malladi's scaling rules.
result Sampling-induced noise in SGD limits to independent Brownian motions.
To reduce the long training time of large deep neural network (DNN) models, distributed synchronous stochastic gradient descent (S-SGD) is commonly used on a cluster of workers. However, the speedup brought by multiple workers is limited by the communication overhead. Two approaches, namely pipelining and gradient spar…
Stochastic Gradient Descent (SGD) has become one of the most popular optimization methods for training machine learning models on massive datasets. However, SGD suffers from two main drawbacks: (i) The noisy gradient updates have high variance, which slows down convergence as the iterates approach the optimum, and (ii)…
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.
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.
Local SGD outperforms conventional methods in LLM training.
problem Training large language models on distributed devices.
method Local SGD algorithm applied to distributed training.
result Local SGD achieves competitive results in LLM training.
New insights into using momentum for non-convex optimization.
problem Improving training of non-convex models like deep neural networks.
method Developed a Lyapunov analysis of SGD with momentum using stochastic primal averaging.
result Precise conditions under which SGD+M outperforms SGD and optimal hyper-parameter schedules.
We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent~(SGD) methods. To reduce the computation costs pertaining to the projections, we pro…
Uncertainty quantification by block bootstrap for differentially private stochastic gradient descentstat.ML
New method for uncertainty quantification in private SGD.
problem Uncertainty quantification for differentially private SGD.
method Block bootstrap for SGD under local differential privacy.
result Valid method for uncertainty quantification in private 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…
Cheap methods improve uncertainty in SGD solutions.
problem Uncertainty quantification in SGD solutions.
method Two resampling-based methods: parallel resampling with replacement and online resampling.
result Significantly reduced computation effort in constructing confidence intervals.
We revisit the choice of SGD for training deep neural networks by reconsidering the appropriate geometry in which to optimize the weights. We argue for a geometry invariant to rescaling of weights that does not affect the output of the network, and suggest Path-SGD, which is an approximate steepest descent method with …
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…
Unified analysis of SGD variants for nonconvex federated optimization.
problem Performance of stochastic gradient methods in nonconvex optimization.
method Proposed a unified assumption for modeling stochastic gradient second moment, leading to a single convergence analysis for various methods.
result Unified convergence analysis for a wide range of SGD variants and distributed methods.
Stochastic Gradient Descent (SGD) is widely used in machine learning problems to efficiently perform empirical risk minimization, yet, in practice, SGD is known to stall before reaching the actual minimizer of the empirical risk. SGD stalling has often been attributed to its sensitivity to the conditioning of the probl…
MDA optimizer performs similarly to SGD+M in CV and Adam in NLP.
problem Performance degradation due to choosing the wrong optimizer.
method Modernized Dual Averaging (MDA) optimizer, inspired by dual averaging.
result MDA performs as well as SGD+M in CV and as Adam in NLP.
In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respecti…
Study reveals convergence properties of SGD with random learning rate.
problem Analyzing convergence of SGD with random learning rate in non-convex optimization.
method Introduced Poisson SGD with random learning rate and used stationary distribution analysis.
result Poisson SGD converges to a stationary distribution and finds global minima in non-convex optimization.
A new method SEBS optimizes SGD batch size for better performance.
problem Optimizing batch size for SGD to balance training speed and generalization.
method SEBS method uses a multi-stage geometric batch size enlargement scheme.
result SEBS reduces parameter updates without increasing generalization error.
We present a novel method for frequentist statistical inference in -estimation problems, based on stochastic gradient descent (SGD) with a fixed step size: we demonstrate that the average of such SGD sequences can be used for statistical inference, after proper scaling. An intuitive analysis using the Ornstein-Uhlen…
The minimization of the loss function is of paramount importance in deep neural networks. On the other hand, many popular optimization algorithms have been shown to correspond to some evolution equation of gradient flow type. Inspired by the numerical schemes used for general evolution equations we introduce a second o…
Proposes Stochastic-Sign SGD for federated learning with theoretical guarantees.
problem Developing efficient, private, and resilient parameter estimation methods for federated learning.
method Introduces Stochastic-Sign SGD, a novel method based on SIGNSGD, which addresses convergence and communication efficiency.
result Demonstrates the effectiveness of Stochastic-Sign SGD through experiments on MNIST and CIFAR-10 datasets.
RS-NSGD improves SGD convergence for heavy-tailed noise.
problem Nonconvex optimization with heavy-tailed noise.
method Integrates direction normalization into subspace updates.
result Achieves better oracle complexity than full-dimensional normalized SGD.
In this paper, we propose a simple variant of the original stochastic variance reduction gradient (SVRG), where hereafter we refer to as the variance reduced stochastic gradient descent (VR-SGD). Different from the choices of the snapshot point and starting point in SVRG and its proximal variant, Prox-SVRG, the two vec…
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.
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.
DReg boosts large-batch SGD's generalization and convergence.
problem Large-batch SGD struggles with generalization in deep learning.
method DReg replicates a layer to encourage parameter diversity.
result DReg improves generalization and convergence with large-batch SGD.
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…
The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in…
This paper analyzes Local SGD for federated learning, achieving both statistical and communication efficiency.
problem Statistical estimation and inference in federated learning with decentralized data.
method Local SGD, a multi-round estimation procedure using intermittent communication.
result Local SGD achieves both statistical efficiency and communication efficiency.
Balls-and-Bins sampling improves DP-SGD privacy and utility.
problem Improving privacy and utility in DP-SGD implementations.
method Introducing Balls-and-Bins sampling as an alternative to shuffling in DP-SGD.
result Balls-and-Bins sampling achieves utility comparable to shuffling while offering better privacy amplification.
SNGM improves large-batch training accuracy.
problem Improving generalization in large-batch training.
method Stochastic Normalized Gradient Descent with Momentum.
result SNGM achieves better test accuracy than MSGD and other large-batch methods.
Unified analysis for decentralized SGD across various topologies and updates.
problem Analysis of decentralized SGD methods with changing topologies and local updates.
method Unified convergence analysis covering local SGD updates and adaptive network topology.
result Universal convergence rates for smooth problems, interpolating between heterogeneous and iid-data settings.