Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

Mark Schmidt 1, 2 Nicolas Le Roux 1, 2
1 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider optimizing a function smooth convex function $f$ that is the average of a set of differentiable functions $f_i$, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient $f_i'$ is bounded by a linear function of the norm of the average gradient $f'$. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an $O(1/k)$ convergence rate, and has a linear convergence rate if $g$ is strongly-convex.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00855113
Contributeur : Mark Schmidt <>
Soumis le : mercredi 28 août 2013 - 21:20:24
Dernière modification le : jeudi 11 janvier 2018 - 06:23:26
Document(s) archivé(s) le : lundi 2 décembre 2013 - 08:52:11

Fichiers

smallResidual.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00855113, version 1
  • ARXIV : 1308.6370

Collections

Citation

Mark Schmidt, Nicolas Le Roux. Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition. 2013. 〈hal-00855113〉

Partager

Métriques

Consultations de la notice

318

Téléchargements de fichiers

565