Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization

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.

accepted for publication for Neural Information Processing Systems (NIPS) 2013. This is the 9-pages version followed by 16 pages of appendices. The title has changed compared to the first technical report

References in corpus (6)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Structured Sparse Principal Component Analysis
• Network Flow Algorithms for Structured Sparsity
• Optimization with First-Order Surrogate Functions
• Proximal Stochastic Dual Coordinate Ascent
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

Cited by in corpus (23)

• MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels
• Meta-Weight-Net: Learning an Explicit Mapping For Sample Weighting
• Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
• Online Nonnegative Matrix Factorization with Outliers
• Dictionary Learning for Massive Matrix Factorization
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Stochastic Subsampling for Factorizing Huge Matrices
• A Random Block-Coordinate Douglas-Rachford Splitting Method with Low Computational Complexity for Binary Logistic Regression
• Online Categorical Subspace Learning for Sketching Big Data with Misses
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Projected support points: a new method for high-dimensional data reduction
• Online matrix factorization for Markovian data and applications to Network Dictionary Learning
• When Naïve Bayes Nearest Neighbours Meet Convolutional Neural Networks
• Block stochastic gradient iteration for convex and nonconvex optimization
• Online Nonnegative Matrix Factorization with General Divergences
• Stochastic Difference-of-Convex Algorithms for Solving nonconvex optimization problems
• Online Sinkhorn: Optimal Transport distances from sample streams
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Efficient Online Minimization for Low-Rank Subspace Clustering
• The Flip Side of the Reweighted Coin: Duality of Adaptive Dropout and Regularization
• Screening for Sparse Online Learning
• Bayesian Projected Calibration of Computer Models
• Parallel Stochastic Optimization Framework for Large-Scale Non-Convex Stochastic Problems