Armijo line-search speeds up gradient descent for various functions.
problem Improving convergence rate of gradient descent.
method Applying Armijo line-search to adjust step-size in gradient descent.
result GD with Armijo line-search converges faster than GD with a fixed step-size.
SGD generalizes better than GD with similar number of iterations.
problem Generalization performance of SGD vs GD in convex optimization.
method Comparison of SGD and GD in stochastic convex optimization model.
result GD requires more iterations to match SGD's generalization performance.
New research shows many batch selection methods for training work just as well as full batch training.
problem Finding optimal batch selection methods for training.
method Analysis of mini-batch Gradient Descent (GD) and Stochastic GD (SGD) with various batch selection rules.
result All mini-batch schedules, including deterministic ones, generalize optimally for smooth Lipschitz-convex/nonconvex/strongly-convex loss functions.
Study on GD and SGD over diagonal networks, focusing on stepsizes and regularisation.
problem Understanding the impact of stochasticity and large stepsizes on gradient descent and SGD solutions.
method Investigation of GD and SGD over diagonal linear networks with macroscopic stepsizes, proving convergence and characterizing solutions.
result Large stepsizes consistently benefit SGD for sparse regression problems, but can hinder GD recovery of sparse solutions, especially in the edge of stability regime.
GD outperforms ridge regression and SGD in linear regression problems.
problem Comparing the risks of GD, ridge regression, and SGD in linear regression problems.
method Instance-wise finite-sample risk analysis of GD, ridge regression, and SGD.
result GD outperforms ridge regression and is incomparable with SGD in some cases.
Momentum improves deep learning generalization by stabilizing noise and learning features.
problem Improving generalization in deep learning models.
method Empirical and theoretical analysis of gradient descent with momentum (GD+M) vs. gradient descent (GD) in binary classification tasks.
result GD+M outperforms GD in generalization, especially in datasets with shared features and varying margins.
Deep linear ResNets converge globally with certain transformations.
problem Global convergence of training deep linear ResNets.
method Gradient descent and stochastic gradient descent for training L-hidden-layer linear ResNets. result GD and SGD can converge to global minimum for deep linear ResNets with specific transformations.
Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in convex optimization problems, the most notable successes in machine learning have involved nonconvex optimization, and a gap has…
Differentiable learning via SGD and GD can simulate various learning problems, depending on precision and minibatch size.
problem Understanding the power of differentiable learning via SGD and GD compared to statistical query (SQ) learning.
method Comparing the learning power of SGD and GD on population and empirical losses with statistical query learning.
result The learning power of SGD and GD depends on the precision of gradient calculations relative to the minibatch size or sample size.
This study tightens bounds on how GD and SGD generalize in smooth convex optimization problems.
problem Understanding how GD and SGD generalize in smooth stochastic convex optimization problems.
method Provided tight excess risk lower bounds for GD and SGD under different conditions.
result Lower bounds suggest overfitting occurs and gaps remain in some cases.
In this note we give a simple proof for the convergence of stochastic gradient (SGD) methods on μ-convex functions under a (milder than standard) L-smoothness assumption. We show that for carefully chosen stepsizes SGD converges after T iterations as $O\left( LR^2 \exp \bigl[-\fracμ{4L}T\bigr] + \frac{σ^2}{μT} \r…
Accelerates ERM problems with LPI-GD and improved oracle complexity.
problem Empirical Risk Minimization (ERM) problems with strong convexity and smoothness.
method Local Polynomial Interpolation-based Gradient Descent (LPI-GD) and accelerated methods.
result Oracle complexity improved to $ ilde{O}\left(\sqrtσ m^d \log(1/\varepsilon)
ight)$.
This study explains how different training methods affect the minimizer of neural networks.
problem How training methods influence the minimizer of neural networks.
method Explains how initialization size, adaptive optimization (AdaGrad), and stochastic mini-batch training affect the minimizer.
result Different training methods lead to different minimizers, even in overparameterized networks.
Max-affine regression method converges linearly using GD and SGD.
problem Regression of max-affine models in signal processing and statistics.
method Gradient descent and mini-batch stochastic gradient descent analysis.
result GD and SGD converge linearly to a neighborhood of the ground truth under sub-Gaussian assumptions.
This work examines the stability of GD and SGD near minima, revealing nonlinear dynamics that differ from linear analysis.
problem The stability of optimization algorithms like GD and SGD near minima is not well understood.
method The authors derive an exact criterion for stable oscillations of GD near minima in the multivariate setting, considering high-order derivatives.
result Nonlinear dynamics can diverge in expectation even if a single batch is unstable, challenging linear analysis.
Large stepsize GD for logistic regression converges faster than expected.
problem Optimizing logistic regression with large step sizes.
method Gradient descent with large stepsize applied to logistic regression.
result GD converges to a lower loss in fewer steps than expected.
The paper analyzes stability and generalization of shallow neural networks using gradient methods.
problem Understanding the generalization of overparameterized shallow neural networks.
method The paper uses gradient descent and stochastic gradient descent to study shallow neural networks, developing consistent excess risk bounds.
result The analysis improves on existing methods by providing a refined estimation of iterates and Hessian eigenvalues, leading to better excess risk bounds.
Gradient methods struggle with high dimensions in convex optimization.
problem The generalization performance of gradient methods in high-dimensional stochastic convex optimization.
method Construction of learning problems in high dimensions to analyze gradient methods' performance.
result Gradient methods require exponentially more training examples in high dimensions to achieve non-trivial test error.
We establish novel generalization bounds for learning algorithms that converge to global minima. We do so by deriving black-box stability results that only depend on the convergence of a learning algorithm and the geometry around the minimizers of the loss function. The results are shown for nonconvex loss functions sa…
Local Gradient Descent with local steps converges to the centralized model in the interpolation regime.
problem Understanding the implicit bias of Local Gradient Descent in the interpolation regime.
method Analyzing the implicit bias of Local Gradient Descent for classification tasks with linearly separable data.
result The aggregated global model from Local-GD converges exactly to the centralized model in the interpolation regime.
Gradient descent with chaotic perturbations improves generalization.
problem Improving generalization of gradient descent.
method Introducing chaotic perturbations to gradient descent to achieve improved generalization.
result Gradient descent with chaotic perturbations converges to a heavy-tailed SDE, leading to improved generalization.
Stochastic Gradient Descent shows directional bias with moderate learning rates, impacting optimization outcomes.
problem Understanding the bias of SGD with moderate learning rates in practical scenarios.
method Analyzing SGD and GD on an overparameterized linear regression problem.
result SGD converges along large eigenvalue directions, GD along small ones, affecting early stopping outcomes.
New algorithm improves gradient-based ERM for smooth convex losses.
problem Empirical risk minimization of smooth, strongly convex loss functions.
method Iterative gradient-based method with local polynomial regression.
result Oracle complexity of O((pε−1)d/(2η)) for our algorithm. SGD outperforms GD in high dimensions via implicit conditioning, revealed by asymptotic analysis.
problem Understanding why SGD outperforms GD in high-dimensional convex problems.
method Asymptotic analysis of multi-pass SGD on high-dimensional convex quadratics, establishing an equivalence to HSGD.
result SGD's efficiency is explained by implicit conditioning, not regularization.
The main aim of this paper is to provide an analysis of gradient descent (GD) algorithms with gradient errors that do not necessarily vanish, asymptotically. In particular, sufficient conditions are presented for both stability (almost sure boundedness of the iterates) and convergence of GD with bounded, (possibly) non…
New algorithm improves learning efficiency in multi-task contextual bandits.
problem Improving learning efficiency in multi-task contextual bandits.
method Alternating projected gradient descent (GD) and minimization estimator for low-rank feature matrix recovery.
result Proved regret bound for multi-task learning algorithm.
What enables Stochastic Gradient Descent (SGD) to achieve better generalization than Gradient Descent (GD) in Neural Network training? This question has attracted much attention. In this paper, we study the distribution of the Stochastic Gradient Noise (SGN) vectors during the training. We observe that for batch sizes …
Full-batch GD outperforms one-pass SGD in learning a single-index model with quadratic activation.
problem Learning a single-index model with quadratic activation using gradient descent.
method Full-batch gradient descent compared to one-pass stochastic gradient descent (SGD) on a correlation loss.
result Full-batch GD requires only n≃d samples for strong recovery, while one-pass SGD requires n≳dlogd samples. 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.
Gradient descent and SGD solve nonlinear inverse problems efficiently.
problem Solving nonlinear inverse problems with random design.
method Gradient descent and SGD with mini-batching, under classical assumptions.
result Achieves optimal convergence rates in RKHS framework.
Full-batch GD achieves generalization close to any stationary point with fewer assumptions.
problem Generalization and excess risk bounds for smooth losses, including non-Lipschitz and nonconvex cases.
method Path-dependent analysis of GD's generalization error, focusing on optimization error and stability.
result Generalization error is tightly bound in terms of optimization error and iteration count, bypassing common assumptions.
Early stopping improves logistic regression's calibration and consistency in high dimensions.
problem Improving the statistical performance of gradient descent in overparameterized logistic regression.
method Investigates the effects of early stopping on gradient descent in logistic regression.
result Early-stopped gradient descent is well-calibrated and statistically consistent, while asymptotic gradient descent is not.
This paper analyzes multi-pass SGD for least squares, improving generalization bounds.
problem Improving generalization bounds for multi-pass SGD in the least squares problem.
method Develops an instance-dependent excess risk bound for least squares in the interpolation regime.
result SGD performs worse than GD instance-wise but saves computational time.
Studied how SGD's stability regularization affects generalization in neural networks.
problem Understanding why SGD often generalizes better than GD in neural networks.
method Analyzed stability of SGD and GD through Frobenius norm and trace of Hessian, and compared their generalization properties.
result Stable minima of SGD generalize well, while GD's stability-induced regularization is too weak.
SGD benefits from a directional bias in kernel regression models.
problem Improving generalization in kernel regression models.
method Generalized directional bias property of SGD in kernel regression.
result SGD converges along the eigenvector of the largest eigenvalue of the Gram matrix.
Stochastic Gradient Descent phases explained for deep networks.
problem Understanding the different regimes of SGD in deep learning.
method Teacher-student perceptron model, phase diagram analysis.
result SGD phases separated by batch size B∗, scaling with training set size P. Gradient-based methods introduce noise that penalizes models sensitive to weight perturbations.
problem Noise in gradient-based optimization methods.
method Analysis of Gradient Descent (GD) and Stochastic Gradient Descent (SGD) updating all parameters simultaneously.
result Noise introduced by simultaneous parameter updates penalizes models sensitive to weight perturbations.
Adam avoids simplicity bias in neural networks, leading to better generalization.
problem Simplicity bias in neural networks trained with SGD.
method Comparison of Adam and GD on binary classification tasks with Gaussian data.
result Adam leads to richer and more diverse features, improving generalization.
DP-GD improves CNN training accuracy with privacy, especially with low signal-to-noise ratios.
problem Privacy-preserving training of neural networks with crowdsourced data.
method Differentially private gradient descent (DP-GD) algorithm applied to two-layer CNNs.
result DP-GD can achieve superior generalization performance compared to GD, especially with low signal-to-noise ratios.
GD at EoS edge minimizes logistic loss without monotonic convergence.
problem Understanding GD's implicit bias at the edge of stability.
method Theoretical analysis of logistic regression with constant stepsize GD.
result GD with any constant stepsize minimizes logistic loss over long time scales.
GD with large, adaptive stepsizes achieves optimal risk in logistic regression.
problem Optimizing logistic regression with large stepsizes.
method Gradient Descent with adaptive stepsizes.
result GD achieves minimax optimal convergence in logistic regression.
New stability bounds for GD in overparameterised shallow nets without NTK assumptions.
problem Generalisation and excess risk bounds for shallow neural networks.
method Oracle inequalities and stability analysis of GD without kernelisation.
result Oracle type bounds reveal GD's generalisation is controlled by an interpolating network with shortest GD path.
CEM-GD combines CEM and gradient descent for efficient model-based RL.
problem Efficient planning in continuous control settings with large prediction horizons.
method Combines CEM for exploration and gradient descent for exploitation.
result Achieves better performance with fewer samples and less computation time.
Adam can lead to worse test errors than GD in deep learning, especially with over-parameterized networks.
problem Adam's inferior generalization performance compared to GD in deep learning optimization.
method Theoretical analysis of Adam and gradient descent in over-parameterized two-layer convolutional neural networks.
result Adam and GD can converge to different global solutions with different generalization errors in nonconvex optimization landscapes.
The expectation-maximization (EM) algorithm has been widely used in minimizing the negative log likelihood (also known as cross entropy) of mixture models. However, little is understood about the goodness of the fixed points it converges to. In this paper, we study the regions where one component is missing in two-comp…
Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The server receives all its information about the problem instance from the wo…
Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for stochastic strongly convex minimization, which achieves the optimal convergence rate of O(1/T) with T iterative updates for the {\it objective gap}. However, its extension to solving stochastic min-max pr…
Adaptive optimization methods, which perform local optimization with a metric constructed from the history of iterates, are becoming increasingly popular for training deep neural networks. Examples include AdaGrad, RMSProp, and Adam. We show that for simple overparameterized problems, adaptive methods often find drasti…