The bound in Part 4 leaves one degree of freedom: a unit budget $\v 1^\top\v w=1$ that decides which coefficients receive the strongest update. This final part works out the best possible allocation and shows what it buys.
the optimal weights reach the solution in a fraction of the iterations the baselines need.
The figure compares how quickly several weight policies reduce the optimality gap on the same lasso problem. Each run uses the same MM update. The only thing that changes is how the weight budget is allocated.
Optimality gap $g(\v\gamma^{(t)})-g^*$ on one representative instance. Across 20 replications, median iterations to a $10^{-6}$ gap were: optimal weights 7.5, round-robin 26.5, uniform 30, and random 31.5.
Uniform and random allocations spend most of the budget on coordinates that do not need it. Round-robin eventually visits the right coordinates, but must wait for its turn. The optimal-weight rule instead removes zero coefficients that already satisfy $\tau_j\le\alpha$, then equalizes the marginal value among the eligible coordinates it funds.
drag the white point on the simplex to choose $\v w$ and compare its surrogate with the optimal choice in blue.
Every point on the simplex defines a valid MM surrogate for the same lasso objective. Changing $\v w$ does not touch the objective or the current iterate; it only moves curvature around in the upper bound. That is enough to change the proposed next step. All the surrogates touch the orange objective at the current iterate, but the blue curve, the one built from the optimal weights, has the lowest minimum in the family and hence the strongest guaranteed one-step improvement.
Peach curves sample the surrogate family, blue is the optimal choice, and the dashed curve follows the white simplex point. Every surrogate stays above the orange objective and touches it at the current iterate. Vertical guides mark the current iterate, the optimal MM step, and the selected surrogate's minimum on this slice; the heatmap and bars on the right show each allocation's full guaranteed decrease. The star marks the optimal weight and the open circle the uniform allocation.
choose the allocation that gives the smallest guaranteed upper bound after the next MM step.
Substitute the closed-form update of Part 4 back into the surrogate. The bound then reduces to a sum of coordinate costs $\phi_j(w_j)$, one per coefficient, and the best allocation minimizes that sum over the unit simplex:
$$ \widehat{\v w} =\argmin_{\v w\ge\v0,\;\v1^\top\v w=1} \sum_{j=1}^p\phi_j(w_j). $$At the current iterate write $\tau_j:=|\v x_j^\top \m G(\widetilde{\v\gamma})\v y|$ and $\xi_j:=\alpha-\tau_j$. A zero coordinate with $\xi_j\ge0$ already satisfies its lasso KKT condition, so it is removed before allocation. For every remaining coordinate, define the deactivation threshold
$$ c_j:= \begin{cases} \widetilde\gamma_j\tau_j/\xi_j, & \xi_j>0,\\ +\infty, & \xi_j\le0. \end{cases} $$In this notation, the cost for coordinate $j$ works out to the continuously differentiable convex function
$$ \phi_j(w_j)= \begin{cases} \dfrac{(\widetilde\gamma_j\tau_j)^2}{w_j} +2\widetilde\gamma_j\tau_j^2, & w_j\ge c_j\text{ and }c_j\in(0,1],\\[0.8em] 2\widetilde\gamma_j\alpha\tau_j-w_j\xi_j^2, & \text{otherwise.} \end{cases} $$Before the knot, one unit of weight improves the bound at the constant marginal rate $-\phi_j'(w_j)=\xi_j^2$. At $w_j=c_j$, the next update sets coefficient $j$ to zero; this is the deactivation point. Past it, extra weight cannot change the coefficient's active status, and its marginal value decays as $(\widetilde\gamma_j\tau_j)^2/w_j^2$.
minimize a sum of convex coordinate costs while distributing one unit of weight among them.
This is a general separable resource-allocation problem. Each curve $\phi_j(w_j)$ tells us the surrogate cost remaining after coordinate $j$ receives weight $w_j$. Every curve would prefer more weight, but the coordinates share one budget:
$$ \underset{\v w\ge\v0}{\operatorname{minimize}} \quad \sum_{j=1}^p\phi_j(w_j) \qquad\text{subject to}\qquad \sum_{j=1}^p w_j=1. $$Four actual costs with common $\alpha=5$. Filled circles mark the funded optima $\widehat w_j$; the open circle is an unfunded coordinate. The short dashed tangents at the funded points are parallel because their slopes all equal $-\nu^*$.
The connection to the lasso KKT gap is at the left edge of the plot. For every eligible coordinate, before any budget is allocated,
$$ -\phi_j'(0)=\xi_j^2=(\alpha-\tau_j)^2. $$Thus the squared auxiliary KKT gap is the coordinate's initial marginal value: it is the amount by which an infinitesimal unit of weight lowers the surrogate bound. That value stays flat until $c_j$, then decreases. The optimal-weight procedure simply hands each increment to whichever $-\phi_j'(w_j)$ is currently largest, and stops when $\sum_jw_j=1$. At that point all funded coordinates share the same marginal value $\nu^*$, and every unfunded coordinate starts at or below it.
The KKT conditions for the simplex problem introduce one multiplier $\nu^*$. Every funded coordinate has the same final marginal value, while an eligible but unfunded coordinate starts below it:
$$ -\phi_j'(\widehat w_j)=\nu^*\quad\text{if }\widehat w_j>0, \qquad \xi_j^2\le\nu^*\quad\text{if }\widehat w_j=0. $$Here, channels become eligible coordinates, power becomes the unit budget of MM weights, and transmission-rate gain becomes reduction of the surrogate bound.
Because each $-\phi_j'(w_j)$ starts at height $\xi_j^2$ and only decreases as $w_j$ grows, the KKT conditions above lead to a classic water-filling procedure. Picture one vessel per coordinate whose width at fill height $w_j$ is $-\phi_j'(w_j)$: the base has width $\xi_j^2$, and the vessel narrows past the knot $c_j$. Pour the unit budget into whichever vessel is currently widest. Funded surfaces then always share one common width, the water level $\nu$, and that level only descends. When the budget is exhausted the level rests at $\nu^*$; vessels whose base $\xi_j^2$ never rose above the final level stay dry. Termination lands in one of two cases. Either $\nu^*$ equals some coordinate's base width $\xi_{(k)}^2$ and that pivot coordinate takes the leftover budget, or $\nu^* = (\sum_{j \le k} \widetilde\gamma_j \tau_j)^2$ sits strictly between two base widths and the funded weights split proportionally to $\widetilde\gamma_j \tau_j$. Sorting the $\xi_j^2$ once gives the exact solution in $\c O(p\log p)$ time, a negligible cost next to the linear solve in each MM step.
Each eligible coordinate is now a vessel. Its base width is the squared auxiliary KKT gap $\xi_j^2$, its fill height is the allocated weight $w_j$, and its width at height $w_j$ is the current marginal value $-\phi_j'(w_j)$. The budget always enters the vessel with the widest available surface.
The colored fill rises as the unit budget is allocated. A horizontal white bar marks $c_j$, the point where coefficient $j$ becomes inactive; above it the vessel narrows because additional weight has diminishing marginal value. An empty vessel is not excluded from the model: its base is simply narrower than the current surface width $\nu$, so it has not started receiving budget. Widths are drawn on a square-root scale so that all five vessels remain visible; the labels give the exact squared KKT gaps $\xi_j^2$.
The vessel picture has already supplied the intuition. The animation below keeps only the two views needed to follow the algorithm: the marginal curves show which coordinate should receive the next increment of budget, while the cost curves show the resulting decrease in the separable objective. At each step the algorithm increases a coordinate with the largest available value of $-\phi_j'(w_j)$. It stops when $\sum_j w_j=1$ and the KKT conditions hold. The controls compare the two ways that this stopping point can occur.
The pieces of this series now fit together. The lasso KKT conditions sort coefficients into active ones and zeros that already satisfy optimality; the auxiliary scales turn those conditions into a convex problem over $\bb{R}_+^p$. The matrix bound of Part 4 then gives a closed-form MM update for every coordinate at once, and the weight problem solved here picks out the best member of that surrogate family for $\c O(p\log p)$ extra work per iteration.
With exact linear solves and a unique auxiliary minimizer, the iterates converge globally to the lasso KKT point. The full statements and proofs, along with the implementation and experiments, are in the paper.