Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization

Julien Mairal

Abstract

Majorization-minimization (MM) algorithms are a versatile class of optimization methods that iteratively minimize a surrogate function bounding the original objective. While popular in statistics and signal processing, traditional MM is a batch process that struggles with massive datasets. This paper introduces a Stochastic Majorization-Minimization (SMM) framework designed for scalability. For convex problems, SMM achieves optimal convergence rates ($O(1/\sqrt{n})$ for general convex and $O(1/n)$ for strongly convex). For non-convex problems, it provides robust guarantees of convergence to stationary points. We demonstrate the framework's efficacy through applications in sparse logistic regression, non-convex sparse estimation, and structured matrix factorization.

Introduction: The Challenge of Scale

The Majorization-Minimization principle is an optimization "meta-algorithm" that simplifies difficult problems by minimizing a sequence of upper-bounding surrogates. This principle encompasses well-known methods such as Expectation-Maximization (EM) and proximal gradient descent. However, the standard MM approach requires a full pass over the dataset to construct each surrogate, making it computationally prohibitive for "Big Data" applications or infinite data streams.

Previous attempts to create incremental MM versions often suffered from memory requirements that scaled linearly with the number of samples ($n$). This paper addresses these limitations by proposing a stochastic version of MM that is both memory-efficient—with requirements independent of $n$—and theoretically grounded with optimal convergence rates.

The Stochastic Majorization-Minimization Framework

The core innovation of SMM lies in how it constructs and updates surrogates using only a single data point (or mini-batch) at each iteration.

Surrogate Averaging and First-Order Surrogates

Rather than building a global surrogate for the entire cost function, SMM selects a surrogate for the loss associated with the current data point. It then maintains an "aggregate surrogate" ($\bar{g}_n$), which is a weighted average of the new surrogate and the aggregate from the previous step. The framework specifically utilizes "first-order" surrogates—functions that match the objective's value and gradient at the current estimate while remaining easy to minimize (e.g., strongly convex functions).

Algorithmic Flexibility

SMM is a flexible framework that can be instantiated into several specialized algorithms:

  • Stochastic Proximal Gradient: Optimized for composite convex problems like $\ell_1$-regularized logistic regression.
  • Online DC Programming: Designed for non-convex problems involving the difference of convex (DC) functions.
  • Online Structured Matrix Factorization: Used for learning dictionaries with specific structural constraints, such as group sparsity.

Experimental Evaluation

The authors evaluated SMM across several large-scale benchmarks, including the rcv1 text categorization dataset (~781k samples), the webspam detection dataset (~250k samples), and the massive kdd2010 educational dataset (~10M samples).

Performance in Convex and Non-Convex Settings

In the context of $\ell_1$-logistic regression, the SMM-based proximal gradient method was compared against LIBLINEAR, a state-of-the-art batch solver. As shown in Figure 1, SMM matches or outperforms the highly optimized batch solver, particularly in low-precision regimes, often reaching a high-quality solution after a single epoch.

Comparison of SMM and LIBLINEAR on large-scale datasets. SMM achieves competitive objective values significantly faster in terms of epochs and computation time.

For non-convex sparse estimation using DC programming, the stochastic nature of SMM provides an additional advantage. Figure 2 illustrates that the Online DC approach (an instance of SMM) not only converges faster than the standard Batch DC version but also tends to find better local minima. This suggests that the inherent noise in stochastic updates helps the algorithm explore the optimization landscape more effectively.

Comparison of Online DC (SMM) and Batch DC. The online approach converges to better local minima more quickly than the batch counterpart.

Key Insights and Future Directions

SMM provides a robust theoretical anchor for stochastic non-convex optimization, proving "almost sure" convergence to stationary points—a notoriously difficult property to establish. Its memory efficiency makes it uniquely suited for streaming data.

While highly effective, the framework currently relies primarily on first-order information. Future work could involve incorporating second-order curvature information (Hessians) to improve performance on ill-conditioned datasets. Additionally, while heuristics for weighting sequences ($w_n$) exist, automated hyperparameter tuning remains an open area for practical refinement.

Conclusion

Stochastic Majorization-Minimization successfully scales a classic optimization principle to the demands of modern large-scale data. By combining optimal theoretical convergence rates with practical memory efficiency and the ability to navigate non-convex landscapes, SMM offers a powerful tool for a wide range of machine learning tasks.

Summary updated

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.
BibTeX
@inproceedings{mairal2013stochastic,
  author = {Julien Mairal},
  title = {{Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=By-Rjdb_-H},
}
Figure