In the ideal world of optimization, functions are convex and smooth—shaped like a perfect bowl with a single, easily reachable bottom. However, modern machine learning and signal processing tasks, such as dictionary learning, wireless beamforming, and image denoising, often present a "double trouble" scenario: objective functions that are both nonconvex (filled with multiple local minima) and nonsmooth (containing sharp ridges or "kinks" where gradients do not exist).
To navigate these jagged landscapes, researchers have converged on a shared strategy: instead of tackling the difficult objective directly, they solve a sequence of simpler, "locally tight" approximations.
The Core Intuition: Majorization Minimization
The fundamental mechanism driving this research is the Majorization-Minimization (MM) principle. When an objective function $f(x)$ is too complex to minimize, we construct a surrogate function $g(x, x^k)$ that "majorizes" $f$ at the current point $x^k$.
For a surrogate to be effective, it must satisfy two conditions:
- Upper Bound: It must stay above the original function everywhere ($g(x) \ge f(x)$).
- Local Tangency: It must touch the original function exactly at the current point ($g(x^k) = f(x^k)$).
By minimizing this simpler surrogate, we are guaranteed to find a new point $x^{k+1}$ that reduces the value of the original function. As Zhihua Zhang and Wu-Jun Li demonstrate in On the Global Convergence of Majorization Minimization Algorithms for Nonconvex Optimization Problems, this iterative process creates a stable path toward a stationary point, even when the underlying landscape is irregular.
Decomposing Complexity with Block Updates
Many high-dimensional problems, like matrix factorization, have a structure where the objective is difficult to optimize globally but easy to solve if we fix most variables and update only one "block" at a time.
Wotao Yin and Yangyang Xu formalized this in their work on block coordinate update (BCU). By combining block updates with proximal terms—mathematical "anchors" that prevent the update from moving too far from the previous iteration—they ensure that the algorithm "settles down" at a solution rather than oscillating. This framework is further extended by Zhaosong Lu in Sequential Convex Programming Methods, which decomposes non-smooth objectives into manageable convex components without losing theoretical convergence.
Scaling to Big Data: Stochastic Surrogates
In modern applications, we often cannot afford to look at the entire dataset to calculate a single update. This led to the development of Stochastic Successive Upper-bound Minimization (SSUM).
Meisam Razaviyayn, Maziar Sanjabi, and Zhi-Quan Luo introduced this framework in A Stochastic Successive Minimization Method. Instead of minimizing the average of all functions, SSUM minimizes a surrogate of a randomly sampled component. This allows the algorithm to handle "messy" problems like wireless transceiver design with the same efficiency as Stochastic Gradient Descent, but with the robustness required for nonsmooth, nonconvex objectives.
Similarly, the SPRING algorithm, developed by Derek Driggs, Junqi Tang, and Jingwei Liang, integrates variance-reduction techniques into this surrogate framework. SPRING achieves state-of-the-art speed by ensuring that the "noise" from stochastic sampling doesn't derail the convergence in non-convex landscapes.
Adding Momentum to the Search
While surrogate methods are stable, they can sometimes be slow. To accelerate convergence, researchers have integrated "inertial" forces—essentially adding momentum to the optimization path.
The iPiano algorithm by Peter Ochs and Thomas Pock combines the "Heavy-ball" method with proximal gradients. In iPiano: Inertial Proximal Algorithm for Non-Convex Optimization, the authors show that momentum helps the algorithm "glide" over small local irregularities that might otherwise trap a standard solver. This concept was later unified with block coordinate methods in the TITAN framework by Le Thi Khanh Hien and Nicolas Gillis, marking the first successful combination of block updates, majorization, and inertial acceleration for nonsmooth problems.
Why It Works: The Bridge to Convexity
The reason these methods are so effective is that they exploit "hidden" structures within nonconvexity. Many of these problems are weakly convex, meaning they can be made convex by adding a simple quadratic term.
As explored by Xiao Li and Jason D. Lee in Incremental Methods for Weakly Convex Optimization, this property allows us to use proximal point methods to solve a sequence of strongly convex sub-problems. By solving these "easier" versions of the problem, we can rigorously guarantee convergence to a stable solution in environments—like neural network activations or sparse signal recovery—where traditional gradient methods often fail.