Back

Train faster, generalize better: Stability of stochastic gradient descent

Moritz HardtBenjamin RechtYoram Singer

article2015ICML1,473 citations

Proves that stochastic gradient descent is algorithmically stable, providing theoretical bounds that explain why faster training and fewer iterations prevent overfitting in both convex optimization and deep neural networks.

Listen

In modern machine learning, complex models such as deep neural networks often contain more parameters than available training samples, yet they routinely generalize well to unseen data without explicit regularization. Traditional statistical learning theories often fail to explain this success, especially when algorithms perform multiple passes over the training data. The article addresses this gap by evaluating the algorithmic stability of the stochastic gradient method—the core optimization algorithm used in machine learning—to establish a formal link between optimization speed and generalization performance.

The main objective of the article is to demonstrate that any parametric model trained with the stochastic gradient method within a reasonable time achieves small generalization error across both convex and non-convex settings. To evaluate this, the authors develop theoretical stability bounds based on the sensitivity of iterative update rules to single-sample perturbations in the dataset. They complement this mathematical framework with empirical experiments across standard machine learning benchmarks, including LeNet on MNIST, convolutional networks on CIFAR-10, AlexNet on ImageNet, and recurrent long short-term memory networks on the Penn Treebank dataset.

The article establishes several key findings. First, the stochastic gradient method is uniformly stable for convex loss functions, yielding generalization errors that vanish as the sample size increases when the number of iterations scales linearly with the data. Second, for non-convex optimization, the algorithm maintains stability provided the step sizes decay appropriately and the number of iterations does not excessively exceed the sample size; this stability is aided by a random burn-in period where the algorithm typically avoids encountering perturbed data points early on. Third, common deep learning techniques—such as weight decay, gradient clipping, dropout, and model averaging—are formally proven to act as stability-promoting operations that systematically reduce generalization error. Fourth, empirical evaluations confirm that model parameter divergence and generalization error grow sub-linearly with training iterations, and cutting the step size in half approximately halves the generalization error.

These findings have direct practical implications for model deployment, computing costs, and risk management. They demonstrate that fast training time is not merely a computational convenience but a direct safeguard against overfitting. Practitioners do not need to choose between computational efficiency and model accuracy; instead, designing architectures and training regimes that converge quickly inherently limits generalization risk. The results also explain why standard heuristic techniques succeed in deep learning and validate the common practice of running multiple training epochs without sacrificing real-world accuracy.

Organizations developing machine learning solutions should prioritize architectures and hyperparameter configurations that achieve rapid convergence. Teams should also adopt stability-inducing mechanisms like weight decay, gradient clipping, and dropout as standard procedures to directly reduce generalization risk. Additionally, hyperparameter optimization strategies can use fast convergence rates as a guiding heuristic for model selection.

The authors note that their theoretical bounds are derived in expectation rather than high-probability confidence intervals, and the existing non-convex theoretical bounds remain somewhat pessimistic compared to real-world empirical performance. Nonetheless, the theoretical and empirical results consistently support the conclusion that limiting stochastic gradient training time effectively prevents overfitting.

GoogleUniversity of California Berkeleygradient algorithmoptimizationstochasticstochastic gradient descentalgorithmic stabilityuniform stability
arXiv: 1509.01240
  • Paper: Stability and Generalization, Olivier Bousquet et al. (2002). This seminal paper introduces the uniform algorithmic stability framework that directly underpins the source's derivation of generalization error bounds for stochastic gradient methods.
  • Paper: The Tradeoffs of Large Scale Learning, Léon Bottou et al. (2007). It formalizes the trade-offs between computation time, optimization error, and generalization in large-scale learning, motivating the source's focus on fast-converging stochastic gradient algorithms.
  • Paper: Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi et al. (2013). It provides fundamental convergence and complexity bounds for stochastic gradient methods on smooth non-convex objectives under standard Lipschitz assumptions utilized in the source's analysis.
  • Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). It introduces foundational online convex programming and iterative gradient projection bounds that serve as essential background for analyzing multi-epoch stochastic gradient descent.
Cover for Train faster, generalize better: Stability of stochastic gradient descent

Abstract

We show that parametric models trained by a stochastic gradient method (SGM) with few iterations have vanishing generalization error. We prove our results by arguing that SGM is algorithmically stable in the sense of Bousquet and Elisseeff. Our analysis only employs elementary tools from convex and continuous optimization. We derive stability bounds for both convex and non-convex optimization under standard Lipschitz and smoothness assumptions.

Applying our results to the convex case, we provide new insights for why multiple epochs of stochastic gradient methods generalize well in practice. In the non-convex case, we give a new interpretation of common practices in neural networks, and formally show that popular techniques for training large deep models are indeed stability-promoting. Our findings conceptually underscore the importance of reducing training time beyond its obvious benefit.

Topics

gradient algorithmoptimizationstochasticstochastic gradient descent

Keywords

stochastic gradient descentalgorithmic stabilityuniform stabilitygeneralization boundsempirical risk minimizationconvex optimizationstochastic optimization

Table of Contents

  • 1 Introduction
  • 1.1 Our contributions
  • 1.2 Related work
  • 2 Stability of randomized iterative algorithms
  • 2.1 Properties of update rules
  • 3 Stability of Stochastic Gradient Method
  • 3.1 Proof idea: Stability of stochastic gradient method
  • 3.2 Expansion properties of stochastic gradients
  • 3.3 Convex optimization
  • 3.4 Strongly Convex Optimization
  • 3.5 Non-convex optimization
  • 4 Stability-inducing operations
  • 5 Convex risk minimization
  • 6 Experimental Evaluation
  • 6.1 Convolutional neural nets on Cifar
  • 6.2 Convolutional neural nets on MNIST
  • 6.3 Convolutional neural nets on ImageNet
  • 6.4 Recurrent neural networks with LSTM
  • 7 Future Work and Open Problems
  • References
  • A Elementary properties of convex functions

Knowls

  1. Knowl 1 — Uniform Stability of Stochastic Gradient Method on Non-Convex Objectives

    theoretical result

    Let the loss function f(w;z)∈[0,1]f(w; z) \in [0, 1] be LL-Lipschitz and β\beta-smooth with respect to ww for every example z∈Zz \in \mathcal{Z}. Consider running the stochastic gradient method (SGM) for TT steps on a dataset S=(z1,…,zn)S = (z_1, \dots, z_n) of size nn using a monotonically non-increasing step size schedule αt≤c/t\alpha_t \le c / t for a constant c>0c > 0.

    Then SGM satisfies uniform stability with parameter: ϵstab≤1+1βcn−1(2cL2)1βc+1Tβcβc+1\epsilon_{\mathrm{stab}} \le \frac{1 + \frac{1}{\beta c}}{n - 1} \left(2c L^2\right)^{\frac{1}{\beta c + 1}} T^{\frac{\beta c}{\beta c + 1}}

    In particular, suppressing constants depending on β,c,\beta, c, and LL, the stability bound scales as: ϵstab=O(T1−1βc+1n)\epsilon_{\mathrm{stab}} = O\left(\frac{T^{1 - \frac{1}{\beta c + 1}}}{n}\right)

    This bound relies on a "burn-in period" property: for any step index t0∈{1,…,n}t_0 \in \{1, \dots, n\}, the probability that SGM encounters the single differing example between two adjacent datasets S,S′S, S' at or before step t0t_0 is at most t0/nt_0 / n. As a result, the number of steps TT can grow as npn^p for an exponent p>1p > 1 (provided p<1+1/(βc)p < 1 + 1/(\beta c)) while maintaining a vanishing generalization error as n→∞n \to \infty.

  2. Knowl 2 — Uniform Stability of Stochastic Gradient Method on Convex Objectives

    theoretical result

    Let the loss function f(w;z)f(w; z) be convex, β\beta-smooth, and LL-Lipschitz with respect to w∈Ωw \in \Omega for all examples z∈Zz \in \mathcal{Z}. Suppose the stochastic gradient method (SGM) is executed for TT iterations on a dataset S=(z1,…,zn)S = (z_1, \dots, z_n) of size nn with step sizes αt≤2/β\alpha_t \le 2/\beta, selecting example indices either uniformly at random with replacement or via random permutations.

    Then SGM satisfies uniform stability with: ϵstab≤2L2n∑t=1Tαt\epsilon_{\mathrm{stab}} \le \frac{2 L^2}{n} \sum_{t=1}^T \alpha_t

    Consequently, the expected generalization error is directly controlled by the sum of step sizes and vanishes as O(1/n)O(1/n) when the sum of learning rates is bounded.

  3. Knowl 3 — Uniform Stability of Projected Stochastic Gradient Method on Strongly Convex Objectives

    theoretical result

    Let Ω\Omega be a compact convex domain, and assume that for all z∈Zz \in \mathcal{Z}, the loss function f(w;z)f(w; z) is γ\gamma-strongly convex and β\beta-smooth with subgradient norms bounded by L=sup⁡w∈Ω,z∥∇f(w;z)∥L = \sup_{w \in \Omega, z} \|\nabla f(w; z)\|. Consider the projected stochastic gradient method: wt+1=ΠΩ(wt−αt∇f(wt;zit))w_{t+1} = \Pi_\Omega\left(w_t - \alpha_t \nabla f(w_t; z_{i_t})\right) where ΠΩ(v)=arg⁡min⁡w∈Ω∥w−v∥\Pi_\Omega(v) = \arg\min_{w \in \Omega} \|w - v\| is the Euclidean projection onto Ω\Omega.

    1. Constant step size: If SGM is run with constant step size α≤1/β\alpha \le 1/\beta for TT steps on a sample of size nn, the uniform stability satisfies: ϵstab≤2L2γn\epsilon_{\mathrm{stab}} \le \frac{2 L^2}{\gamma n} which is completely independent of the number of steps TT.

    2. Decaying step size: If f(w;z)∈[0,1]f(w; z) \in [0, 1] and SGM is run with decaying step sizes αt=1γt\alpha_t = \frac{1}{\gamma t}, the uniform stability satisfies: ϵstab≤2L2+βργn\epsilon_{\mathrm{stab}} \le \frac{2 L^2 + \beta \rho}{\gamma n} where ρ=sup⁡w∈Ω,zf(w;z)\rho = \sup_{w \in \Omega, z} f(w; z).

  4. Knowl 4 — Excess Risk and Multi-Epoch Generalization Bound for Convex SGM

    theoretical result

    The expected population risk of a model ww produced by a learning algorithm A\mathcal{A} decomposes into empirical risk minimization error and uniform stability error: E[R[w]]≤E[RS[wS∗]]+ϵopt(w)+ϵstab\mathbb{E}[R[w]] \le \mathbb{E}\left[R_S\left[w_S^*\right]\right] + \epsilon_{\mathrm{opt}}(w) + \epsilon_{\mathrm{stab}} where R[w]=Ez∼D[f(w;z)]R[w] = \mathbb{E}_{z \sim \mathcal{D}}[f(w; z)] is the population risk, RS[w]=1n∑i=1nf(w;zi)R_S[w] = \frac{1}{n}\sum_{i=1}^n f(w; z_i) is the empirical risk on dataset SS, wS∗=arg⁡min⁡wRS[w]w_S^* = \arg\min_w R_S[w] is the empirical risk minimizer, and ϵopt(w)=E[RS[w]−RS[wS∗]]\epsilon_{\mathrm{opt}}(w) = \mathbb{E}[R_S[w] - R_S[w_S^*]]. The expected minimal empirical risk never exceeds the minimal population risk: E[RS[wS∗]]≤R[w∗]\mathbb{E}[R_S[w_S^*]] \le R[w^*], where w∗=arg⁡min⁡wR[w]w^* = \arg\min_w R[w].

    For a β\beta-smooth convex loss function ff with ∥∇f(w;z)∥≤L\|\nabla f(w; z)\| \le L and starting point w0w_0 satisfying ∥w0−wS∗∥≤D\|w_0 - w_S^*\| \le D, running TT steps of SGM with constant step size: α=DnLT(n+2T)\alpha = \frac{D \sqrt{n}}{L \sqrt{T(n + 2T)}} and averaging the iterates wˉT=1T∑t=1Twt\bar{w}_T = \frac{1}{T}\sum_{t=1}^T w_t achieves the expected population risk bound: E[R[wˉT]]≤E[RS[wS∗]]+DLnn+2TT\mathbb{E}[R[\bar{w}_T]] \le \mathbb{E}\left[R_S\left[w_S^*\right]\right] + \frac{DL}{\sqrt{n}} \sqrt{\frac{n + 2T}{T}}

    When training for a single epoch (T=nT = n), the excess risk term is bounded by 3DLn\frac{\sqrt{3}DL}{\sqrt{n}}. As T→∞T \to \infty (infinitely many epochs), the excess risk approaches 2DLn\frac{\sqrt{2}DL}{\sqrt{n}}, demonstrating that multi-epoch training does not lead to overfitting.

  5. Knowl 5 — Uniform Stability and Generalization in Expectation for Randomized Algorithms

    theoretical result

    Let Z\mathcal{Z} be the sample space, D\mathcal{D} an unknown data distribution, and S=(z1,…,zn)∈ZnS = (z_1, \dots, z_n) \in \mathcal{Z}^n a dataset of nn examples drawn i.i.d. from D\mathcal{D}. Let f(w;z)f(w; z) denote the loss of model parameters ww on example zz, and define the empirical risk RS[w]=1n∑i=1nf(w;zi)R_S[w] = \frac{1}{n} \sum_{i=1}^n f(w; z_i) and population risk R[w]=Ez∼D[f(w;z)]R[w] = \mathbb{E}_{z \sim \mathcal{D}}[f(w; z)].

    Definition (Uniform Stability): A randomized algorithm A\mathcal{A} is ϵ\epsilon-uniformly stable if for all datasets S,S′∈ZnS, S' \in \mathcal{Z}^n differing in at most one example: sup⁡z∈ZEA[∣f(A(S);z)−f(A(S′);z)∣]≤ϵ\sup_{z \in \mathcal{Z}} \mathbb{E}_\mathcal{A}\left[ |f(\mathcal{A}(S); z) - f(\mathcal{A}(S'); z)| \right] \le \epsilon where the expectation is taken solely over the internal randomness of A\mathcal{A}. The infimum over all such ϵ\epsilon is denoted ϵstab(A,n)\epsilon_{\mathrm{stab}}(\mathcal{A}, n).

    Theorem (Generalization in Expectation): If a randomized algorithm A\mathcal{A} is ϵ\epsilon-uniformly stable, its expected generalization error is bounded by ϵ\epsilon: ∣ES,A[RS[A(S)]−R[A(S)]]∣≤ϵ\left| \mathbb{E}_{S, \mathcal{A}}\left[ R_S[\mathcal{A}(S)] - R[\mathcal{A}(S)] \right] \right| \le \epsilon

  6. Knowl 6 — Growth Recursion for Iterative Update Rules under Dataset Perturbation

    theoretical result

    Let Ω\Omega be a parameter domain. An update rule G:Ω→ΩG: \Omega \to \Omega is:

    • η\eta-expansive if sup⁡u,v∈Ω∥G(u)−G(v)∥∥u−v∥≤η\sup_{u, v \in \Omega} \frac{\|G(u) - G(v)\|}{\|u - v\|} \le \eta.
    • σ\sigma-bounded if sup⁡w∈Ω∥w−G(w)∥≤σ\sup_{w \in \Omega} \|w - G(w)\| \le \sigma.

    Let G1,…,GTG_1, \dots, G_T and G1′,…,GT′G'_1, \dots, G'_T be two sequences of update rules corresponding to runs on datasets SS and S′S'. Starting from identical initialization w0=w0′∈Ωw_0 = w'_0 \in \Omega, let wt+1=Gt(wt)w_{t+1} = G_t(w_t) and wt+1′=Gt′(wt′)w'_{t+1} = G'_t(w'_t), with parameter distance δt=∥wt′−wt∥\delta_t = \|w'_t - w_t\|. Then δ0=0\delta_0 = 0 and the recursion satisfies: δt+1≤{ηδtif Gt=Gt′ is η-expansivemin⁡(η,1)δt+2σif Gt,Gt′ are σ-bounded and Gt is η-expansive\delta_{t+1} \le \begin{cases} \eta \delta_t & \text{if } G_t = G'_t \text{ is } \eta\text{-expansive} \\ \min(\eta, 1)\delta_t + 2\sigma & \text{if } G_t, G'_t \text{ are } \sigma\text{-bounded and } G_t \text{ is } \eta\text{-expansive} \end{cases}

    Additionally, the second case admits the alternative upper bound δt+1≤ηδt+2σ\delta_{t+1} \le \eta \delta_t + 2\sigma.

  7. Knowl 7 — Expansiveness and Boundedness Properties of Gradient Updates

    theoretical result

    Let f:Ω→Rf: \Omega \to \mathbb{R} be a differentiable objective function on Ω⊆Rd\Omega \subseteq \mathbb{R}^d, and define the gradient update operator Gf,α(w)=w−α∇f(w)G_{f, \alpha}(w) = w - \alpha \nabla f(w) with step size α≥0\alpha \ge 0.

    1. Boundedness: If ff is LL-Lipschitz (∥∇f(w)∥≤L\|\nabla f(w)\| \le L for all w∈Ωw \in \Omega), then Gf,αG_{f, \alpha} is (αL)(\alpha L)-bounded: sup⁡w∈Ω∥w−Gf,α(w)∥≤αL\sup_{w \in \Omega} \|w - G_{f, \alpha}(w)\| \le \alpha L.
    2. Smoothness: If ff is β\beta-smooth (∥∇f(u)−∇f(v)∥≤β∥u−v∥\|\nabla f(u) - \nabla f(v)\| \le \beta \|u - v\|), then Gf,αG_{f, \alpha} is (1+αβ)(1 + \alpha\beta)-expansive.
    3. Convex Smoothness: If ff is convex and β\beta-smooth, then for any α≤2/β\alpha \le 2/\beta, Gf,αG_{f, \alpha} is 11-expansive (non-expansive): ∥Gf,α(u)−Gf,α(v)∥≤∥u−v∥\|G_{f, \alpha}(u) - G_{f, \alpha}(v)\| \le \|u - v\|
    4. Strong Convexity: If ff is γ\gamma-strongly convex and β\beta-smooth, then for any α≤2β+γ\alpha \le \frac{2}{\beta + \gamma}, Gf,αG_{f, \alpha} is (1−αβγβ+γ)\left(1 - \frac{\alpha \beta \gamma}{\beta + \gamma}\right)-expansive. In particular, for α≤1/β\alpha \le 1/\beta, Gf,αG_{f, \alpha} is (1−αγ)(1 - \alpha \gamma)-expansive (strictly contractive).

  8. Knowl 8 — Stability-Inducing Operations: Weight Decay, Dropout, Proximal Steps, and Model Averaging

    theoretical result

    Common algorithmic modifications and regularizers enhance the stability of stochastic gradient updates:

    1. Weight Decay (ℓ2\ell_2-Regularization): For a β\beta-smooth function ff, the update with weight decay at rate μ>0\mu > 0, defined as Gf,μ,α(w)=(1−αμ)w−α∇f(w)G_{f, \mu, \alpha}(w) = (1 - \alpha \mu)w - \alpha \nabla f(w), is (1+α(β−μ))(1 + \alpha(\beta - \mu))-expansive. When μ>β\mu > \beta, the update becomes contractive.

    2. Dropout: Let D:Ω→ΩD: \Omega \to \Omega be a randomized dropout operator with rate s∈[0,1]s \in [0, 1] satisfying E[∥Dv∥]=s∥v∥\mathbb{E}[\|D v\|] = s\|v\|. For an LL-Lipschitz loss ff, the dropout gradient update DGf,α(v)=v−αD(∇f(v))DG_{f, \alpha}(v) = v - \alpha D(\nabla f(v)) is (sαL)(s \alpha L)-bounded in expectation, scaling down the effective Lipschitz parameter to sLsL.

    3. Proximal Steps and Projections: For any convex function ff, the proximal update operator Pf,α(w)=arg⁡min⁡v12∥w−v∥2+αf(v)P_{f, \alpha}(w) = \arg\min_v \frac{1}{2}\|w - v\|^2 + \alpha f(v) is 11-expansive. This implies that Euclidean projections onto arbitrary convex sets are 11-expansive.

    4. Model Averaging: For convex, LL-Lipschitz, and β\beta-smooth objectives with step size αt≤α≤2/β\alpha_t \le \alpha \le 2/\beta, the averaged iterate wˉT=1T∑t=1Twt\bar{w}_T = \frac{1}{T}\sum_{t=1}^T w_t satisfies uniform stability: ϵstab≤α(T+1)L2n\epsilon_{\mathrm{stab}} \le \frac{\alpha(T + 1)L^2}{n} improving the uniform stability bound of the final iterate by approximately a factor of 2.

  9. Knowl 9 — Empirical Dynamics of SGM Parameter Divergence and Generalization Error

    empirical result

    Experiments evaluating neural networks trained with stochastic gradient descent across diverse domains (LeNet on MNIST, cuda-convnet on CIFAR-10, AlexNet on ImageNet, and a 2-layer LSTM on Penn Treebank) yield the following empirical findings regarding stability and generalization:

    1. Linear step-size scaling: Halving the step size α\alpha roughly halves the generalization error (measured either as the gap between train and test classification error or train and test loss), confirming a linear relationship between learning rate and generalization error.
    2. Sublinear parameter divergence: The Euclidean distance ∥wt−wt′∥\|w_t - w'_t\| between parameters of identical networks trained from the same seed on datasets differing by a single example substitution grows sublinearly with epochs, indicating that theoretical worst-case exponential bounds for non-convex optimization are pessimistic.
    3. Trajectory divergence correlates with generalization: The parameter divergence ∥wt−wt′∥\|w_t - w'_t\| and the empirical generalization error track each other closely and evolve in tandem across epochs.
    4. Burn-in delay effect: Artificially placing a perturbed training example at the first step of SGM causes model parameters to diverge significantly faster than encountering the substitution later in training, validating the role of the "burn-in" delay in stabilizing early iterations.

Coverage note — None was omitted; all theoretical stability bounds (convex, strongly convex, non-convex), optimization error decompositions, stability-inducing modifications, and empirical results were fully captured.

References

  1. 1.S. Arora, R. Ge, T. Ma, and A. Moitra. Simple, efficient, and neural algorithms for sparse coding. In Proceedings of the Conference on Learning Theory (COLT), 2015.
  2. 2.L. Bottou. Online algorithms and stochastic approximations. In D. Saad, editor, Online Learning and Neural Networks. Cambridge University Press, Cambridge, UK, 1998.
  3. 3.L. Bottou and O. Bousquet. The tradeoffs of large scale learning. In Neural Information Processing Systems, 2008.
  4. 4.O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499–526, 2002.
  5. 5.J. Bucklew, T. G. Kurtz, and W. Sethares. Weak convergence and local stability properties of fixed step size recursive algorithms. IEEE Transactions on Information Theory, 39(3):966–978, 1993.
  6. 6.P. L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling and Simulation, 4(4):1168–1200, 2005.
  7. 7.O. Devolder, F. Glineur, and Y. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1-2):37–75, 2014.
  8. 8.L. P. Devroye and T. Wagner. Distribution-free performance bounds for potential function rules. Information Theory, IEEE Transactions on, 25(5):601–604, Sep 1979.
  9. 9.A. Elisseeff, T. Evgeniou, and M. Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6:55–79, 2005.
  10. 10.Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296, 1999.
  11. 11.R. Frostig, R. Ge, S. M. Kakade, and A. Sidford. Competing with the empirical risk minimizer in a single pass. In Conference on Learning Theory (COLT), 2015.
  12. 12.S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
  13. 13.E. Hazan, A. Kalai, S. Kale, and A. Agarwal. Logarithmic regret algorithms for online convex optimization. In Proceedings of the 19th Annual Conference on Learning Theory, 2006.
  14. 14.E. Hazan and S. Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489–2512, 2014.
  15. 15.K. Jamieson and A. Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. Preprint available at arXiv:1502.07943v1, 2015.
  16. 16.M. Janzamin, H. Sedghi, and A. Anandkumar. Generalization bounds for neural networks through tensor factorization. Preprint available at arXiv:1506.08473, 2015.
  17. 17.Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), 2013.
  18. 18.M. J. Kearns and D. Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural Computation, 11(6):1427–1453, 1999.
  19. 19.A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Proc. NIPS, pages 1097–1105, 2012.
  20. 20.A. Krogh and J. A. Hertz. A simple weight decay can improve generalization. In Proc. NIPS, pages 950–957, 1992.
  21. 21.H. J. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer-Verlag, New York, second edition, 2003.
  22. 22.G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1-2):365–397, 2012.
  23. 23.L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. To appear in SIAM Journal on Optimization. Preprint available at arxiv:1408.3595., 2014.
  24. 24.R. Livni, S. Shalev-Shwartz, and O. Shamir. On the computational efficiency of training neural networks. In Advances in Neural Information Processing Systems, pages 855–863, 2014.
  25. 25.M. P. Marcus, M. A. Marcinkiewicz, and B. Santorini. Building a large annotated corpus of English: The Penn Treebank. Computational linguistics, 19(2):313–330, 1993.
  26. 26.S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.
  27. 27.A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
  28. 28.A. Nemirovski and D. B. Yudin. On Cezari’s convergence of the steepest descent method for approximating saddle point of convex-concave functions. In Soviet Mathetmatics Doklady, volume 19, 1978.
  29. 29.A. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley Interscience, 1983.
  30. 30.Y. Nesterov. Introductory lectures on convex optimization, volume 87 of Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004. A basic course.
  31. 31.B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In In Proc. 3rd ICLR, 2015.
  32. 32.K. Nissim and U. Stemmer. On the generalization properties of differential privacy. Preprint available at arXiv:1504.05800, 2015.
  33. 33.N. Parikh and S. P. Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3):123–231, 2013.
  34. 34.B. T. Polyak. Introduction to optimization. Optimization Software, Inc., 1987.
  35. 35.A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Conference on Machine Learning, 2012. Extended version at arxiv:1109.5647.
  36. 36.R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877–898, 1976.
  37. 37.L. Rosasco and S. Villa. Learning with incremental iterative regularization. Preprint available at arXiv:1405.0042v2, 2014.
  38. 38.D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. In Parallel Distributed Processing–Explorations in the Microstructure of Cognition, pages 318–362. MIT Press, Cambridge, MA, 1986.
  39. 39.S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11:2635–2670, 2010.
  40. 40.N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1):1929–1958, 2014.
  41. 41.C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Proceedings of the 2015 Conference on Computer Vision and Pattern Recognition, 2015.
  42. 42.W. Zaremba, I. Sutskever, and O. Vinyals. Recurrent neural network regularization. Technical report, 2014. Preprint available at arxiv:1409.2329.

Citation

MLA
Hardt, M., et al. “Train Faster, Generalize Better: Stability of Stochastic Gradient Descent”. arXiv, 2015, http://arxiv.org/abs/1509.01240v2.
APA
Hardt, M., Recht, B., & Singer, Y. (2015). Train faster, generalize better: Stability of stochastic gradient descent. arXiv. http://arxiv.org/abs/1509.01240v2
Chicago
Hardt, M., B. Recht, and Y. Singer. 2015. “Train Faster, Generalize Better: Stability of Stochastic Gradient Descent”. arXiv. http://arxiv.org/abs/1509.01240v2.
Harvard
Hardt, M., Recht, B. and Singer, Y. (2015) “Train faster, generalize better: Stability of stochastic gradient descent”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1509.01240v2.
Vancouver
1. Hardt M, Recht B, Singer Y (2015) Train faster, generalize better: Stability of stochastic gradient descent. arXiv

BibTeX

@article{hardt2015train,
  title = {Train faster, generalize better: Stability of stochastic gradient descent},
  author = {Hardt, Moritz and Recht, Benjamin and Singer, Yoram},
  year = {2015},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1509.01240v2},
  eprint = {1509.01240}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Published with permission