Majorization Minimization for Non-Convex Optimization

This direction is split into other directions: surrogate function optimization, surrogate-based optimization. Its last version stays readable and citable here.

Version 1 of 1422 papers484 conceptsfrozen 2026-10-04

In many real-world engineering problems, the functions we want to optimize are "well-behaved" only in theory. In practice, they are often non-convex, non-differentiable, or plagued by complex hardware constraints. Standard tools like gradient descent often struggle here, requiring tedious manual tuning of step sizes or getting stuck in poor local minima.

Majorization-Minimization (MM) is a powerful optimization framework that bypasses these issues by solving a sequence of simpler, surrogate problems. Instead of tackling a difficult objective function $f(x)$ directly, MM constructs a "surrogate" function $g(x)$ that acts as a local upper bound. By iteratively minimizing this easier surrogate, we are guaranteed to move toward a local optimum of the original, harder problem.

The Core Intuition: The Surrogate Sandwich

The beauty of MM lies in its simplicity. At each iteration $k$, we find a surrogate function $g(x | x_k)$ that satisfies two conditions:

  1. Majorization: The surrogate stays above the original function everywhere: $g(x | x_k) \geq f(x)$.
  2. Tangency: The surrogate touches the original function at the current point: $g(x_k | x_k) = f(x_k)$.

When we minimize this surrogate to find the next point $x_{k+1}$, we are mathematically guaranteed that the original objective $f(x)$ will either decrease or stay the same. This "monotonic convergence" is a hallmark of the framework, as noted by Claudia Soares and João Xavier in their work on network localization. Because the surrogate is chosen to be easy to solve—often a simple quadratic or a convex function—we can frequently derive closed-form update rules that require zero parameter tuning.

Taming Hardware and Signal Constraints

MM is particularly effective in signal processing, where hardware often imposes strict, non-convex constraints. For example, in MIMO (Multiple-Input Multiple-Output) systems, researchers like Zhongju Wang and Daniel P. Palomar use MM to design training sequences that must have a constant amplitude (unimodularity).

By applying a "double majorization" strategy, Junxiao Song and colleagues showed in Optimization Methods for Designing Sequences with Low Autocorrelation Sidelobes that a complex quartic objective can be reduced to a series of simple phase-rotation updates. Similarly, the PRIME algorithm developed by Tianyu Qiu uses MM to solve the phase retrieval problem—recovering signals from magnitude-only data—achieving faster and more reliable convergence than heuristic gradient methods like Wirtinger Flow.

Robustness to Noise and Outliers

Standard optimization often relies on least-squares (L2) objectives, which are sensitive to "glitchy" data. MM allows researchers to swap these for more robust but "messier" functions, like the L1 norm or non-convex $l_p$ penalties.

In Making Tensor Factorizations Robust to Non-Gaussian Noise, Eric C. Chi demonstrates how MM can optimize non-differentiable L1 loss functions by replacing them with a sequence of weighted least-squares sub-problems. This makes tensor decomposition resilient to massive outliers. In the realm of sparse recovery, Zhaosong Lu uses MM to handle non-convex $l_p$ regularizers, providing a stable path to finding sparse solutions that traditional convex approximations might miss.

Scaling to Modern Machine Learning

While MM has deep roots in classical signal processing, it is increasingly relevant for large-scale machine learning. Julien Mairal unified many first-order optimization methods under the surrogate function lens, introducing incremental algorithms like MISO that handle non-smooth regularizers efficiently.

The framework is also being applied to stabilize deep learning and complex statistical models:

  • Low-Rank Training: Ipsita Ghosh and Christian Kümmerle introduced Q3R, which uses quadratic MM to make low-rank pre-training of neural networks stable and computationally tractable.
  • Hyperparameter Optimization: He Chen and Anthony Man-Cho So developed LDMMA, which reformulates bilevel programs (like tuning a Lasso model) into single-level problems solved via MM.
  • Clustering: Adithya Vellal and Jason Q. Xu extended clustering to the exponential family using Bregman Power k-Means, leveraging MM to derive closed-form updates that avoid the pitfalls of gradient descent.

Why It Works: Stability and Structure

The primary reason MM succeeds where other methods fail is its structural awareness. Instead of treating the objective function as a "black box" and only looking at its local slope (gradient), MM allows us to exploit the specific mathematical structure of the problem—whether it's a log-likelihood, a trigonometric term in subspace estimation, or a free-discontinuity problem in image segmentation as explored by Rachel Ward.

By carefully choosing a surrogate that captures the curvature of the original function, MM provides a principled, stable, and often faster route to optimization in the complex landscapes of modern data science.

Papers in this version

Showing 60 of 422 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_majorization_minimization_for_non_convex_94348715,
  title = {Majorization Minimization for Non-Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/majorization-minimization-for-non-convex-optimization/rdr_943487159c344b688cd85a68f34293e2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_majorization_minimization_for_non_convex_94348715_v1,
  title = {Majorization Minimization for Non-Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/majorization-minimization-for-non-convex-optimization/rdr_943487159c344b688cd85a68f34293e2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}