Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
TL;DR
This paper introduces a stochastic version of the Majorization-Minimization (MM) framework, enabling it to scale to massive or even infinite datasets. By iteratively minimizing a weighted average of local surrogate functions, the proposed algorithm achieves optimal convergence rates for convex problems and guaranteed convergence to stationary points for non-convex problems, all while maintaining a memory footprint independent of the dataset size.
The Challenge of Scaling Majorization-Minimization
Majorization-Minimization (MM) is a powerful optimization principle underlying famous algorithms like Expectation-Maximization (EM) and Difference of Convex (DC) programming. It works by creating a "surrogate" function that upper-bounds the difficult objective and then minimizing that surrogate instead.
However, traditional MM is a "batch" method—it requires processing the entire dataset to build the surrogate. Previous "incremental" versions attempted to solve this but required storing information for every single data point, leading to a memory cost of $O(pn)$ (where $p$ is the number of variables and $n$ is the number of data points). For modern "big data" applications where $n$ is in the millions and $p$ is in the tens of millions, this memory overhead is computationally impossible. This paper seeks to make MM truly scalable.
The Stochastic Majorization-Minimization Scheme
The author proposes a Stochastic Majorization-Minimization (SMM) scheme. Instead of building a surrogate for the entire empirical cost, the algorithm operates iteratively:
- Draws a single data point (or mini-batch) at each iteration.
- Constructs a local surrogate function for that specific point.
- Updates an aggregate surrogate $\bar{g}_n$, which is a weighted average of the current local surrogate and the previous aggregate.
- Minimizes this aggregate surrogate to find the next estimate.
The key innovation is the use of first-order surrogate functions. These surrogates approximate the objective up to a smooth error, allowing the algorithm to handle non-smooth objectives (like those with $\ell_1$ regularization). Crucially, the memory load is independent of $n$, as the algorithm only needs to store the parameters of the aggregate surrogate.
Key Insights and Theoretical Guarantees
- Optimal Convergence: For convex functions, the algorithm achieves an expected convergence rate of $O(1/\sqrt{n})$, and $O(1/n)$ for strongly convex functions. This matches the theoretical limits of stochastic gradient descent.
- Non-Convex Robustness: One of the most significant contributions is the proof that the method almost surely converges to stationary points in non-convex settings. This is a rare and valuable guarantee in stochastic non-convex optimization.
- Flexibility: The framework is highly general. It can be specialized into a new stochastic proximal gradient method, an online DC programming algorithm, or an online structured matrix factorization tool.
Experimental Results
The paper evaluates the algorithm on several large-scale datasets, including rcv1 (~781k samples, 47k features), webspam (250k samples, 16M features), and kdd2010 (10M samples, 28M features).
Efficiency in $\ell_1$-Logistic Regression
In $\ell_1$-logistic regression tasks, the SMM algorithm outperformed the state-of-the-art LIBLINEAR solver in "low-precision" regimes. It reached a "good enough" solution much faster, often in just one pass over the data, and successfully handled the massive 28-million-feature kdd2010 dataset where many incremental methods fail due to memory constraints.
Escaping Local Minima in Non-Convex Problems
In experiments with non-convex DC programming (sparse estimation), the stochastic approach actually found better solutions with lower objective values than the batch version. This suggests that the stochastic noise inherent in the SMM scheme helps the algorithm navigate complex landscapes and avoid poor local minima.
Structured Dictionary Learning
Beyond regression, the method was applied to learn sparse, structured dictionaries from 400,000 natural image patches. It accomplished this in just a few minutes on a single CPU core, demonstrating its practical utility for computer vision tasks.
Limitations and Future Work
- Parameterization: The algorithm is only practical if the aggregate surrogate $\bar{g}_n$ can be represented by a small number of variables. If the surrogate becomes too complex to store or minimize, the efficiency gains are lost.
- Curvature: The current first-order surrogates do not fully exploit the second-order curvature (Hessian) of the objective function. Developing surrogates that account for curvature could help deal with "badly conditioned" datasets where standard first-order methods struggle.
- Hyperparameters: Like most stochastic methods, performance depends on the choice of weights, which may require some tuning, though the paper provides heuristics that perform well in practice.
Summary updated