Stochastic Composite Least-Squares Regression with convergence rate O(1/n)

Nicolas Flammarion 1, 2 Francis Bach 1, 2
2 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, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : We consider the minimization of composite objective functions composed of the expectation of quadratic functions and an arbitrary convex function. We study the stochastic dual averaging algorithm with a constant step-size, showing that it leads to a convergence rate of O(1/n) without strong convexity assumptions. This thus extends earlier results on least-squares regression with the Euclidean geometry to (a) all convex regularizers and constraints, and (b) all geome-tries represented by a Bregman divergence. This is achieved by a new proof technique that relates stochastic and deterministic recursions.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01472867
Contributeur : Nicolas Flammarion <>
Soumis le : mardi 21 février 2017 - 13:57:32
Dernière modification le : jeudi 11 janvier 2018 - 06:28:04
Document(s) archivé(s) le : lundi 22 mai 2017 - 15:24:03

Fichiers

hal-mdh.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01472867, version 1
  • ARXIV : 1702.06429

Collections

Citation

Nicolas Flammarion, Francis Bach. Stochastic Composite Least-Squares Regression with convergence rate O(1/n). 2017. 〈hal-01472867〉

Partager

Métriques

Consultations de la notice

339

Téléchargements de fichiers

519