Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization

Julien Mairal 1, *
* Auteur correspondant
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : Majorization-minimization algorithms consist of iteratively minimizing a majorizing surrogate of an objective function. Because of its simplicity and its wide applicability, this principle has been very popular in statistics and in signal processing. In this paper, we intend to make this principle scalable. We introduce a stochastic majorization-minimization scheme which is able to deal with large-scale or possibly infinite data sets. When applied to convex optimization problems under suitable assumptions, we show that it achieves an expected convergence rate of $O(1/\sqrt{n})$ after $n$ iterations, and of $O(1/n)$ for strongly convex functions. Equally important, our scheme almost surely converges to stationary points for a large class of non-convex problems. We develop several efficient algorithms based on our framework. First, we propose a new stochastic proximal gradient method, which experimentally matches state-of-the-art solvers for large-scale $\ell_1$-logistic regression. Second, we develop an online DC programming algorithm for non-convex sparse estimation. Finally, we demonstrate the effectiveness of our approach for solving large-scale structured matrix factorization problems.
Type de document :
Communication dans un congrès
C.J.C. Burges and L. Bottou and M. Welling and Z. Ghahramani and K.Q. Weinberger. NIPS 2013 - Advances in Neural Information Processing Systems, Dec 2013, South Lake Tahoe, United States. pp.2283-2291, 2013, Advances in Neural Information Processing Systems 26.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00835840
Contributeur : Julien Mairal <>
Soumis le : mardi 10 septembre 2013 - 14:03:46
Dernière modification le : mercredi 11 avril 2018 - 01:58:42
Document(s) archivé(s) le : jeudi 6 avril 2017 - 16:59:25

Fichiers

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

Identifiants

  • HAL Id : hal-00835840, version 2
  • ARXIV : 1306.4650

Collections

Citation

Julien Mairal. Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization. C.J.C. Burges and L. Bottou and M. Welling and Z. Ghahramani and K.Q. Weinberger. NIPS 2013 - Advances in Neural Information Processing Systems, Dec 2013, South Lake Tahoe, United States. pp.2283-2291, 2013, Advances in Neural Information Processing Systems 26. 〈hal-00835840v2〉

Partager

Métriques

Consultations de la notice

722

Téléchargements de fichiers

2606