Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Stochastic Majorization-Minimization Optimization with First-Order Surrogate Functions

Julien Mairal 1, *
* Corresponding author
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
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 and study 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 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 derive from our framework several efficient algorithms. First, we propose a new stochastic proximal gradient method, which experimentally matches state-of-the-art solvers for large-scale l1-logistic regression. Second, we develop an online DC programming algorithm for non-convex sparse estimation. Finally, we demonstrate the effectiveness of our technique for solving large-scale structured matrix factorization problems.
Complete list of metadata

https://hal.inria.fr/hal-00835840
Contributor : Julien Mairal Connect in order to contact the contributor
Submitted on : Wednesday, June 19, 2013 - 7:37:39 PM
Last modification on : Tuesday, October 19, 2021 - 11:13:04 PM
Long-term archiving on: : Friday, September 20, 2013 - 4:08:27 AM

Files

online_surrogate.pdf
Files produced by the author(s)

Identifiers

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

Citation

Julien Mairal. Stochastic Majorization-Minimization Optimization with First-Order Surrogate Functions. 2013. ⟨hal-00835840v1⟩

Share

Metrics

Les métriques sont temporairement indisponibles