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.
Introduction
Many fundamental algorithms in statistics and signal processing, such as the Expectation-Maximization (EM) algorithm and proximal gradient methods, are instances of the Majorization-Minimization (MM) principle. MM works by iteratively minimizing a "surrogate" function that upper-bounds the true objective, providing a stable and intuitive path toward an optimum. However, traditional MM is a batch method, requiring a full pass over the dataset to construct the surrogate at every step. This makes it impractical for modern "Big Data" or streaming scenarios.
This paper introduces Stochastic Majorization-Minimization (SMM), a framework that scales the MM principle to massive or infinite datasets. Unlike previous incremental versions that required memory proportional to the dataset size ($n$), SMM maintains a memory load independent of $n$, making it suitable for truly large-scale optimization.
The Stochastic MM Framework
The core of the SMM scheme is a recursive update of an aggregated surrogate function. At each iteration $n$, the algorithm:
- Samples a single data point (or mini-batch) $x_n$.
- Constructs a local first-order surrogate for the loss associated with that sample.
- Aggregates this local surrogate into an approximate global surrogate using a weighted average: $g_n(\theta) = (1 - w_n) g_{n-1}(\theta) + w_n \ell(\theta, x_n)$, where $w_n$ is a step size.
- Minimizes the aggregated surrogate $g_n$ to obtain the next parameter estimate $\theta_n$.
By using a weighted average, the algorithm "remembers" past data without needing to store it. The memory requirement depends only on the number of model parameters ($p$), ensuring scalability.
Theoretical Guarantees
The paper provides rigorous convergence analysis for both convex and non-convex regimes:
- Convex Problems: SMM achieves an expected convergence rate of $O(1/\sqrt{n})$, and $O(1/n)$ for strongly convex functions, matching the theoretical lower bounds for stochastic optimization.
- Non-Convex Problems: The framework provides a strong "almost sure" convergence guarantee to stationary points. This is a significant contribution, as stochastic optimization for non-convex objectives is notoriously difficult to prove.
Experimental Evaluation
Large-Scale $\ell_1$-Logistic Regression
The framework was tested on several large-scale benchmarks, including rcv1 (781k samples), webspam (250k samples), and kdd2010 (10M samples). In these tests, SMM matched or outperformed LIBLINEAR, a highly optimized batch solver, particularly in low-to-medium precision regimes. It often reached a high-quality solution after just a single pass through the data.
Non-Convex Sparse Estimation
For non-convex problems, the stochastic nature of SMM (specifically an online DC programming variant) proved advantageous. The online version consistently found better local minima (lower objective values) than its batch counterpart, suggesting that stochasticity helps the algorithm escape poor stationary points.
Conclusion
Stochastic Majorization-Minimization bridges the gap between the robust MM principle and the requirements of large-scale machine learning. By utilizing first-order surrogates and a memory-efficient aggregation scheme, SMM provides a stable, scalable, and theoretically sound framework for both convex and non-convex optimization. Future work may involve better exploiting second-order curvature information to further accelerate convergence on ill-conditioned problems.
Summary updated