The Lasso and MM Algorithms - 3 of 5

Part 3: Majorize-Minimize Algorithms

Anant Mathur · July 2026

1 · Lasso + CD 2 · Auxiliary KKT 3 · MM Algorithms 4 · A Separable Bound 5 · Optimal Weights

Majorize-minimize is a general recipe for designing algorithms rather than a single update formula. Its surrogate viewpoint includes EM and connects to proximal-gradient and Newton-like quadratic-majorization schemes; see Hunter and Lange (2004) and Lange (2016). The recipe is simple: replace a difficult objective by an upper bound that touches it at the current iterate, improve that surrogate, and repeat.

The majorize-minimize principle

To minimize an objective $g(\v\gamma)$, an MM algorithm replaces it at the current iterate $\widetilde{\v\gamma}$ by a simpler surrogate $h(\v\gamma,\widetilde{\v\gamma})$ satisfying

$$ \begin{aligned} g(\widetilde{\v\gamma})&=h(\widetilde{\v\gamma},\widetilde{\v\gamma}), \\ g(\v\gamma)&\le h(\v\gamma,\widetilde{\v\gamma}) \quad\text{for every }\v\gamma. \end{aligned} $$

Minimize the surrogate and repeat. If $\v\gamma^{(t+1)}\in\argmin_{\v\gamma}h(\v\gamma,\v\gamma^{(t)})$, then

$$ \begin{aligned} g(\v\gamma^{(t+1)}) &\le h(\v\gamma^{(t+1)},\v\gamma^{(t)})\\ &\le h(\v\gamma^{(t)},\v\gamma^{(t)}) =g(\v\gamma^{(t)}). \end{aligned} $$
01Touch The surrogate agrees with the objective at the current iterate.
02Stay above Its minimum is a computable upper bound on the next objective value.
03Minimize Each step descends without a line search or hand-tuned step size.

Watch MM work

Consider the smooth one-dimensional objective

$$ g(x)=\cos x,\qquad 0\le x\le2\pi. $$

On this interval the unique minimizer is $\widehat x=\pi$, where $g(\widehat x)=-1$. Because $g''(x)=-\cos x\le1$, the quadratic upper-bound principle gives the smooth majorizer

$$ h(x,x^{(t)}) =\cos x^{(t)}-\sin x^{(t)}(x-x^{(t)}) +\frac12(x-x^{(t)})^2 \;\ge\;\cos x. $$

The bound touches $g$ and has the same slope at $x^{(t)}$. Its minimum gives the closed-form MM update

$$ x^{(t+1)}=x^{(t)}+\sin x^{(t)}. $$

Starting farther away at $x^{(0)}=0.2$ gives a longer visible sequence: $0.2000\to0.3987\to0.7869\to1.4950\to2.4921\to3.0969\to\cdots\to\pi$. The animation settles numerically at the displayed global minimum after seven MM updates.

Example. This quadratic-majorization example follows Kenneth Lange's Examples of MM Algorithms slides.

Orange is the objective and the dashed peach curve is the current surrogate. The white dot marks $x^{(t)}$; the peach vertical guide and dot mark the surrogate minimum selected for the next step. Past iterates remain on the objective so the monotone descent is visible. Dashed vertical guides retain every iterate location, with the current iterate drawn more strongly. The guide at $\widehat x=\pi$ marks the true minimum.

What makes a useful majorizer?

Majorization guarantees descent, but it does not guarantee speed. The choice of majorizer is therefore both a mathematical and computational decision. Common constructions use tangent inequalities for concave terms, quadratic curvature bounds for smooth terms, Jensen's inequality for latent-variable objectives, or matrix inequalities for coupled inverse problems. The mathematics changes from problem to problem; the touch, majorize, improve pattern does not.

MM is an algorithmic architecture. EM, iteratively reweighted methods, proximal-gradient updates, and many coordinate-separable schemes can all be read as MM algorithms once their implicit upper bounds are written down.

Exact and generalized MM

Exact MM minimizes the surrogate at every iteration. That is sufficient but not necessary. A generalized MM step only needs to improve the surrogate:

$$ h(\v\gamma^{(t+1)},\v\gamma^{(t)}) \le h(\v\gamma^{(t)},\v\gamma^{(t)}). $$

The same two-line argument still gives $g(\v\gamma^{(t+1)})\le g(\v\gamma^{(t)})$. This permits partial inner solves, coordinate updates, or damped steps when the exact surrogate minimum is expensive.

Descent is not the whole convergence theorem. Monotone objective values do not by themselves prove that the iterates reach a minimizer. Stationarity requires the surrogate to share the appropriate first-order behaviour of the objective, together with regularity and compactness assumptions. For a convex objective, every stationary point is global; uniqueness is an additional question.

The auxiliary lasso as an MM problem

Part 2 left us with the convex auxiliary objective

$$ \begin{aligned} g(\v\gamma) &=\v y^\top \left(\m I+\sum_{j=1}^p\gamma_j\v x_j\v x_j^\top\right)^{-1}\v y\\ &\quad+\alpha^2\v 1^\top\v\gamma. \end{aligned} $$

The inverse couples all $p$ scales, so the obvious objective is not separable. The MM design problem is therefore precise: find an upper bound that touches this inverse term at the current iterate, separates across $\gamma_j$, and remains tight enough to make a useful concurrent step.

From framework to construction. Part 4 supplies the matrix inequality and derives the resulting separable surrogate. Part 5 then chooses the best member of that surrogate family by solving the optimal-weight problem.
← Part 2: Auxiliary KKT Conditions Part 4: A Separable Bound →