Iterative Nonconvex Optimization via Surrogate Functions

62 concepts65 papers1 proposal

Many foundational problems across machine learning, signal processing, and statistics require optimizing functions that are stubbornly non-convex, non-smooth, or constrained by complex physical boundaries. Standard gradient descent often falters in these landscapes, getting trapped in poor local minima, oscillating wildly near non-differentiable points, or struggling to satisfy intricate constraints.

The Majorization-Minimization (MM) framework offers an elegant way out. Instead of directly navigating a rugged, intractable objective landscape, MM iteratively constructs a well-behaved, globally bounding surrogate function around the current estimate. Minimizing this simpler surrogate guarantees a step that reduces the original objective, transforming a daunting global optimization problem into a sequence of manageable sub-problems.

The Core Mechanism: Why Surrogates Guarantee Progress

Let $f(x)$ be the difficult objective function we wish to minimize. At any iteration $t$ with a current estimate $x_t$, we construct a surrogate function $g(x | x_t)$ that satisfies two crucial properties:

  1. Tangency: The surrogate matches the true objective exactly at the current point: $g(x_t | x_t) = f(x_t)$.
  2. Dominance (Majorization): The surrogate acts as a global upper bound: $g(x | x_t) \ge f(x)$ for all $x$.

Once this surrogate is constructed, the next update is found by minimizing it: $x_{t+1} = \arg\min_x g(x | x_t)$.

Why does this simple swap guarantee progress? The mathematical intuition is beautifully straightforward:

$$f(x_{t+1}) \le g(x_{t+1} | x_t) \le g(x_t | x_t) = f(x_t)$$

The first inequality comes from the dominance property (the surrogate is always above or equal to the true function). The second inequality arises because $x_{t+1}$ is explicitly chosen to minimize $g(x | x_t)$, meaning $g(x_{t+1} | x_t)$ must be less than or equal to the value at the starting point $g(x_t | x_t)$. The final equality is the tangency property.

This chain proves that every single step is guaranteed to monotonically decrease (or keep constant) the true objective function, ensuring stable convergence to a stationary point. (The inverse applies to maximization problems, where a lower-bounding surrogate is maximized—a variant known as Minorization-Maximization).

Objective f(x)  :   \       /^\       /
Surrogate g(x)  :    \_____/   \_____/   <- Globally upper-bounds f(x)
                           ^
                        Touches at current point x_t

Taming Nonconvex Penalties and Sparsity

A classic application of this framework is recovering sparse or low-rank structures where standard convex relaxations (like the $\ell_1$ norm) fail to capture true sparsity accurately. For instance, Yue Deng 0001 et al. utilize a non-convex log-sum heuristic to approximate sparsity more closely than the $\ell_1$ norm. They use a first-order Taylor expansion to construct a convex surrogate, transforming a non-convex global problem into a sequence of manageable convex sub-problems.

Similarly, in graph learning, Jiaxi Ying et al. address non-convex logarithmic penalties by majorizing them into a sequence of weighted $\ell_1$-norm sub-problems. By replacing the non-convex penalty with a linear or quadratic upper bound, the complex objective is reduced to standard convex optimization steps that can be solved efficiently using off-the-shelf solvers.

Handling Complex Hardware and Physical Constraints

The utility of MM extends far beyond unconstrained loss functions; it is highly effective at handling difficult geometric constraints. In wireless communications and signal processing, hardware often imposes strict constraints, such as the unit-modulus constraint (where signal phases can change, but their magnitudes must remain constant).

For example, in phase retrieval, Tianyu Qiu et al. design the PRIME framework to recover complex signals from magnitude-only measurements. Instead of relying on expensive semidefinite relaxations or matrix lifting, they construct surrogate functions that yield low-complexity, closed-form updates. This strategy is echoed by Jiezhi Zhang et al. in the context of Intelligent Reflecting Surfaces (IRS), where non-convex unit-modulus constraints are replaced by a simpler surrogate majorizer to bypass high computational costs and deliver closed-form updates.

Decoupling Ratios and High-Order Polynomials

Another powerful trick within the MM playbook is the ability to decouple variables that are tangled up in fractions or high-order polynomials. In wireless networks, maximizing the signal-to-interference-plus-noise ratio (SINR) or energy efficiency involves optimizing sums of multiple ratios—a notoriously non-convex problem.

Wei Yu 0001 et al. demonstrate that the quadratic transform, a widely used technique for fractional programming, is mathematically equivalent to an MM procedure. By introducing auxiliary variables, the transform constructs a surrogate that decouples the numerator from the denominator, allowing for alternating, closed-form updates.

When dealing with quartic (fourth-order) objectives, such as those found in financial portfolio design, Ziping Zhao et al. show that MM can break down these complex landscapes into a sequence of simple quadratic surrogate subproblems, drastically reducing computational overhead and ensuring stable convergence.

Scaling to Large Datasets

While the classic MM framework updates all variables simultaneously, modern large-scale machine learning demands incremental or coordinate-wise updates to remain computationally viable. Julien Mairal introduced a unifying framework for first-order surrogate functions, showing how MM principles can be embedded within an incremental algorithm (MISO). By updating surrogates based on individual data points or mini-batches rather than the entire dataset, the method achieves fast convergence to stationary points while gracefully handling non-smooth regularizers.

Key Foundational Work

Iterative Thresholding for Sparse Approximations (2008) — contributed 1 concept elements to this direction.
Predictive Matrix-Variate t Models (2007) — 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_function_optimization_b65e7bdf,
  title = {surrogate function optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/surrogate-function-optimization/rdr_b65e7bdf6e314cd8885de0c6bd739822},
  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_function_optimization_b65e7bdf_v1,
  title = {surrogate function optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/surrogate-function-optimization/rdr_b65e7bdf6e314cd8885de0c6bd739822/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