# Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization

arXiv: https://arxiv.org/abs/1306.4650 · HTML: https://mlsanity.com/paper/1306.4650/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2013.

## Built on by (most cited first, 28 of 28)

- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Fine-grained Recognition with Learnable Semantic Data Augmentation](https://mlsanity.com/paper/2309.00399/) (2023)
- [RAT: Adversarial Attacks on Deep Reinforcement Agents for Targeted Behaviors](https://mlsanity.com/paper/2412.10713/) (2024)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [The Flip Side of the Reweighted Coin: Duality of Adaptive Dropout and Regularization](https://mlsanity.com/paper/2106.07769/) (2021)
- [Adaptive Mixing of Auxiliary Losses in Supervised Learning](https://mlsanity.com/paper/2202.03250/) (2022)
- [Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling](https://mlsanity.com/paper/2105.01853/) (2021)
- [Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering](https://mlsanity.com/paper/2211.01877/) (2022)
- [Target-based Surrogates for Stochastic Optimization](https://mlsanity.com/paper/2302.02607/) (2023)
- [Learning low-rank latent mesoscale structures in networks](https://mlsanity.com/paper/2102.06984/) (2021)
- [Universal Majorization-Minimization Algorithms](https://mlsanity.com/paper/2308.00190/) (2023)
- [Screening for Sparse Online Learning](https://mlsanity.com/paper/2101.06982/) (2021)
- [Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates](https://mlsanity.com/paper/2201.01652/) (2022)
- [Exponentially Convergent Algorithms for Supervised Matrix Factorization](https://mlsanity.com/paper/2311.11182/) (2023)
- [MIO : Mutual Information Optimization using Self-Supervised Binary Contrastive Learning](https://mlsanity.com/paper/2111.12664/) (2021)
- [Supervised Dictionary Learning with Auxiliary Covariates](https://mlsanity.com/paper/2206.06774/) (2022)
- [Communication-Efficient Federated Linear and Deep Generalized Canonical Correlation Analysis](https://mlsanity.com/paper/2109.12400/) (2021)
- [Formal guarantees for heuristic optimization algorithms used in machine learning](https://mlsanity.com/paper/2208.00502/) (2022)
- [Online Learning Under A Separable Stochastic Approximation Framework](https://mlsanity.com/paper/2305.07484/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Adaptive Stochastic Gradient Descents on Manifolds with an Application on Weighted Low-Rank Approximation](https://mlsanity.com/paper/2503.11833/) (2025)
- [Dynamic Perturbed Adaptive Method for Infinite Task-Conflicting Time Series](https://mlsanity.com/paper/2505.11902/) (2025)
- [Enhancing Kernel Power K-means: Scalable and Robust Clustering with Random Fourier Features and Possibilistic Method](https://mlsanity.com/paper/2511.10392/) (2025)
- [Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts](https://mlsanity.com/paper/2601.19811/) (2026)
- [Fast Model Selection and Stable Optimization for Softmax-Gated Multinomial-Logistic Mixture of Experts Models](https://mlsanity.com/paper/2602.07997/) (2026)
- [Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization](https://mlsanity.com/paper/2610.00558/) (2026)

## Abstract (arXiv)

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/√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 ℓ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.