# Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2014.

## Built on by (most cited first, 30 of 35)

- [It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization](https://mlsanity.com/paper/2504.13173/) (2025)
- [Light-weight probing of unsupervised representations for Reinforcement Learning](https://mlsanity.com/paper/2208.12345/) (2022)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Block Coordinate Plug-and-Play Methods for Blind Inverse Problems](https://mlsanity.com/paper/2305.12672/) (2023)
- [On the Importance of Feature Decorrelation for Unsupervised Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2306.05637/) (2023)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Stochastic Optimization for Spectral Risk Measures](https://mlsanity.com/paper/2212.05149/) (2022)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Convergence of online k-means](https://mlsanity.com/paper/2202.10640/) (2022)
- [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)
- [Bregman Power k-Means for Clustering Exponential Family Data](https://mlsanity.com/paper/2206.10860/) (2022)
- [SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learning](https://mlsanity.com/paper/2405.20127/) (2024)
- [Adversarially-Trained Nonnegative Matrix Factorization](https://mlsanity.com/paper/2104.04757/) (2021)
- [On a class of geodesically convex optimization problems solved via Euclidean MM methods](https://mlsanity.com/paper/2206.11426/) (2022)
- [Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation](https://mlsanity.com/paper/2207.14019/) (2022)
- [The Stochastic Proximal Distance Algorithm](https://mlsanity.com/paper/2210.12277/) (2022)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)
- [SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities](https://mlsanity.com/paper/2210.05994/) (2022)
- [Joint control variate for faster black-box variational inference](https://mlsanity.com/paper/2210.07290/) (2022)
- [Reconstruction of gene regulatory network via sparse optimization](https://mlsanity.com/paper/2211.07375/) (2022)
- [Accelerated Distributed Aggregative Optimization](https://mlsanity.com/paper/2304.08051/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Efficient algorithms for regularized Poisson Non-negative Matrix Factorization](https://mlsanity.com/paper/2404.16505/) (2024)

## Abstract (arXiv)

Majorization-minimization algorithms consist of successively minimizing a sequence of upper bounds of the objective function. These upper bounds are tight at the current estimate, and each iteration monotonically drives the objective function downhill. Such a simple principle is widely applicable and has been very popular in various scientific fields, especially in signal processing and statistics. In this paper, we propose an incremental majorization-minimization scheme for minimizing a large sum of continuous functions, a problem of utmost importance in machine learning. We present convergence guarantees for non-convex and convex optimization when the upper bounds approximate the objective up to a smooth error; we call such upper bounds "first-order surrogate functions". More precisely, we study asymptotic stationary point guarantees for non-convex problems, and for convex ones, we provide convergence rates for the expected objective function value. We apply our scheme to composite optimization and obtain a new incremental proximal gradient algorithm with linear convergence rate for strongly convex functions. In our experiments, we show that our method is competitive with the state of the art for solving machine learning problems such as logistic regression when the number of training samples is large enough, and we demonstrate its usefulness for sparse estimation with non-convex penalties.