Optimization via Iterative Surrogate Functions

19 concepts20 papers1 proposal

Many core problems in machine learning and signal processing require optimizing objective functions that are mathematically intractable, non-convex, or non-smooth. Direct optimization of these functions using standard gradient methods often fails because finding the right learning rate is difficult, or because the objective lacks a closed-form gradient.

The Majorization-Minimization (MM) framework—and its counterpart, Minorize-Maximization—bypasses this difficulty. Instead of optimizing the complex target function directly, the MM framework constructs a sequence of simpler, tractable surrogate functions that upper-bound the objective. By iteratively minimizing these surrogates, the algorithm guarantees a monotonic decrease in the original objective function, naturally driving the system toward a local optimum.

The Intuition: The Sandwich Property

To understand why MM works, imagine a complex, jagged cost surface $f(x)$ that we want to minimize. Direct optimization is difficult. In the MM framework, we choose a current estimate $x^k$ and construct a smooth, easily minimized surrogate function $g(x \mid x^k)$ that satisfies two strict conditions:

  1. Majorization (Upper Bound): The surrogate must sit entirely on or above the true objective function: $g(x \mid x^k) \geq f(x)$ for all $x$.
  2. Tangency (Touchpoint): At the current estimate $x^k$, the surrogate must perfectly touch the objective function: $g(x^k \mid x^k) = f(x^k)$.

Once this surrogate is constructed, we find the next iterate $x^{k+1}$ by minimizing $g(x \mid x^k)$.

  Cost
   ^          g(x | x^k) [Surrogate Upper Bound]
   |             \     /
   |              \   /   f(x) [True Objective]
   |               \_/_ .

- - .
   |               /   \       ` .
   |              /     \          `
   +-------------|-------|------------> x
                x^{k+1}  x^k

Why does this guarantee progress? Because of a simple "sandwich" inequality. Since $x^{k+1}$ minimizes the surrogate, we know that $g(x^{k+1} \mid x^k) \leq g(x^k \mid x^k)$. Combining this with our two conditions yields:

$$f(x^{k+1}) \leq g(x^{k+1} \mid x^k) \leq g(x^k \mid x^k) = f(x^k)$$

This chain of inequalities guarantees that the true objective function value $f(x)$ decreases monotonically at every single step. This automatic progress eliminates the need for manual learning rate tuning. As demonstrated by Vojnovic et al. in Convergence Rates of Gradient Descent and MM Algorithms for Bradley-Terry Models, this self-governing step selection allows MM algorithms to achieve reliable linear convergence on complex likelihood surfaces without the risk of divergence seen in poorly tuned gradient descent.

Theoretical Foundations and Convergence

While the intuition behind the monotonic decrease is straightforward, proving that the sequence of iterates actually converges to a valid stationary point requires deeper analysis.

Historically, the theoretical foundations of specific surrogate methods were proven in isolation. For instance, the Concave-Convex Procedure (CCCP)—which splits an objective into a convex and a concave part to linearize the concave component—was widely used before its global convergence properties were fully formalized. Sriperumbudur et al. closed this gap in On the Convergence of the Concave-Convex Procedure by applying Zangwill’s global convergence theory, mapping out exactly how and when these iterative surrogate steps reach true stationary points in both constrained and unconstrained environments.

A unifying perspective on these techniques was established by Mairal in Optimization with First-Order Surrogate Functions. This work formalized a broad class of first-order surrogate functions, showing that many popular optimization techniques are instances of the same underlying majorization principle. By standardizing the asymptotic convergence properties of these approximations, the author introduced MISO, an incremental surrogate framework capable of scaling to massive machine learning datasets where computing a global majorant is too expensive.

Strategies for Constructing Surrogates

The art of applying the MM framework lies entirely in how the surrogate function is designed. A good surrogate must balance two competing demands: it must be mathematically simple to minimize, yet tight enough to the original objective to ensure fast convergence.

Quadratic Majorization

One of the most common strategies is to construct a quadratic surrogate function. If an objective function has a bounded curvature, we can approximate it using a paraboloid that curves upward more sharply than the objective itself.

In A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization, Chi et al. leveraged this approach to solve geometric distance problems. By constructing a quadratic surrogate for non-smooth Euclidean distance terms, the authors replaced complex subgradient steps with an exact, closed-form minimization update.

However, the choice of the quadratic bound matters. As Wang et al. demonstrated in Effective Low-Complexity Optimization Methods for Joint Phase Noise and Channel Estimation in OFDM, loose quadratic approximations can lead to slow, crawling convergence. By designing tight surrogate functions that closely mirror the local curvature of the objective, the authors significantly accelerated convergence speeds for high-dimensional signal estimation.

Separable Surrogates for High Dimensions

When dealing with high-dimensional, non-separable penalties—such as those found in sparsity-promoting regression—the objective function couples all variables together, preventing parallel optimization. MM solves this by constructing separable surrogates, where the upper bound splits into a sum of independent, single-variable functions.

For example, in High-dimensional Fused Lasso Regression using Majorization-Minimization and Parallel Processing, Yu et al. used majorization to decouple the fused penalty terms. This transformed a massive, intertwined optimization problem into a sequence of independent sub-problems that could be solved simultaneously on a GPU. Similarly, Murata et al. applied a majorization framework in Sparse Representation Using Multidimensional Mixed-Norm Penalty With Application to Sound Field Decomposition to upper-bound non-convex, multi-dimensional mixed-norm penalties, achieving a tenfold speedup over traditional sparsity solvers.

Bypassing Intractable Expectations

In statistical tracking and signal processing, the true objective function often involves computing complex expectations or integrals that lack closed-form solutions. In these scenarios, researchers construct tractable majorants to act as proxies.

In Joint Sensor and Relay Power Control in Tracking Gaussian Mixture Targets by Wireless Sensor Networks, Bengua et al. encountered mathematically intractable Mean Squared Error (MSE) formulations when tracking Gaussian mixture targets. By minimizing a tractable majorant function based on Linear Minimum Mean Squared Error (LMMSE), the authors bypassed the intractable integration steps entirely, enabling near-optimal resource allocation with minimal computational overhead.

Scaling Up and Modern Applications

The versatility of the MM framework has led to its adoption across a wide range of modern, large-scale engineering problems, from computer vision to deep learning.

Image Restoration and Parallel Computing

Large-scale inverse problems, such as 3D medical imaging and image restoration, suffer from severe memory bottlenecks. To address this, Cadoni et al. introduced the Block Parallel Majorize-Minimize Memory Gradient (BP3MG) algorithm in A block parallel majorize-minimize memory gradient algorithm. By combining block-coordinate descent with parallel majorization surrogates, the authors enabled massive 3D image restoration tasks to achieve near-linear speedups across multi-core processors without exceeding hardware memory limits. This builds on a broader tradition of using iterative surrogate optimization to solve large-scale inverse problems efficiently, as detailed by Chaâri et al. in OPTIMED : optimisation itérative pour la résolution de problèmes inverses de grande taille.

Deep Learning Integration

Modern architectures increasingly blend classical physics-based reconstruction with deep learning by "unrolling" iterative algorithms into neural network layers. A major challenge in these hybrid networks is maintaining physical data consistency during the inner optimization loops without incurring massive computational costs.

In Momentum-Net: Fast and Convergent Iterative Neural Network for Inverse Problems, Chun et al. solved this by replacing complex inner optimization loops with majorization-minimization steps. By using a surrogate function to upper-bound the data-fit term, the network computes closed-form updates during the data-consistency step. This eliminates the need for expensive sub-iterations while providing mathematical stability guarantees for non-convex data models.

Robust Optimization and Constraints

The MM framework is also highly effective at handling non-smooth, robust loss functions and complex geometric constraints.

  • Robust Loss Functions: Traditional low-rank Semidefinite Programming (SDP) is highly sensitive to outliers due to its reliance on squared loss. In Efficient Low-Rank Semidefinite Programming With Robust Loss Functions, Yao et al. combined MM with the Alternating Direction Method of Multipliers (ADMM) to handle non-convex, outlier-resistant loss functions, simplifying a challenging robust optimization problem into a sequence of easily solvable steps.
  • Geometric Constraints: Optimizing over the intersection of multiple convex sets is notoriously difficult. In Distance majorization and its applications, Chi et al. introduced "distance majorization," leveraging the MM principle alongside quasi-Newton acceleration to efficiently project points onto intersecting sets, outperforming traditional subgradient methods in high-dimensional spaces.
  • Complex Objective Surfaces: Whether maximizing Kullback-Leibler divergence for non-Gaussian visual data features (De la Torre et al., Multimodal oriented discriminant analysis) or designing complex radar sequences with ultra-low autocorrelation sidelobes (Song et al., Sequence Design to Minimize the Weighted Integrated and Peak Sidelobe Levels), substituting a difficult objective with a sequence of majorizing surrogates consistently transforms intractable optimization problems into reliable, monotonic algorithms.

Key Foundational Work

Multimodal oriented discriminant analysis (2005) — contributed 1 concept elements to this direction.
On the Convergence of the Concave-Convex Procedure (2009) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_surrogate_based_optimization_7335b23e,
  title = {surrogate-based optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/surrogate-based-optimization/rdr_7335b23eab5244e38f45295a90c43f25},
  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_surrogate_based_optimization_7335b23e_v1,
  title = {surrogate-based optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/surrogate-based-optimization/rdr_7335b23eab5244e38f45295a90c43f25/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake