The bound in Part 4 leaves one design choice: how to split a unit budget $\v 1^\top\v w=1$, which 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. The dots on the dashed line mark the iteration at which each policy first reaches the $10^{-6}$ target. The inset bars grow with the race and stop at each policy's median iteration count to that target over 20 replications: optimal weights 7.5, round-robin 26.5, uniform 30, random 31.5. On this particular instance uniform and random do not reach the target within 60 iterations.
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. Vertical guides mark the current iterate, the optimal MM step and the selected surrogate's minimum on this slice. On the right, the heatmap and bars show each allocation's full guaranteed decrease; the star marks $\widehat{\v w}$ 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 classic separable resource-allocation problem. Each curve $\phi_j(w_j)$ is the surrogate cost left after coordinate $j$ receives weight $w_j$. Every curve would prefer more weight, but the coordinates share one unit of budget.
Four of the five coordinates from the running example ($\alpha=5$), the same instance animated in the vessel and KKT-allocation views below. 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 KKT conditions for the simplex problem introduce one multiplier $\nu^*$. Every funded coordinate ends with marginal value exactly $\nu^*$, and every eligible but unfunded coordinate starts at or 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. $$Each marginal value is flat at $\xi_j^2$ until the knot $c_j$ and only decreases after it, so these conditions can be met greedily: hand each small increment of budget to whichever coordinate currently has the largest $-\phi_j'(w_j)$, and stop when $\sum_jw_j=1$.
Here, channels become eligible coordinates, power becomes the unit budget of MM weights, and transmission-rate gain becomes reduction of the surrogate bound.
That greedy rule is water-filling. 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 budget into whichever vessel is currently widest. Funded surfaces always share one common width, the water level $\nu$, which only descends; when the budget runs out it rests at $\nu^*$, and vessels whose base never exceeded that level stay dry. The procedure stops in one of two ways. 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.
Here is that procedure on the running example, one vessel per eligible coordinate.
The colored fill rises as the budget is poured. A white bar marks the knot $c_j$, where coefficient $j$ becomes inactive and the vessel starts to narrow. An empty vessel is still eligible: its base is narrower than the current level $\nu$, so it has not yet received budget. Widths use a square-root scale so all five vessels stay visible; the labels give the exact $\xi_j^2$.
The last animation follows the same allocation in two views: panel (a) shows the marginal values that decide where the next increment goes, and panel (b) shows the costs $\phi_j$ falling as weight arrives. The case buttons compare the two ways the procedure can stop. The collapsed derivation collects every formula from this section in one place.
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.