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 part derives the optimal allocation and shows why it improves the MM step.
the optimal allocation reaches the solution in fewer iterations than the baseline allocations.
Consider an ordinary lasso with $p=12$ correlated, standardized predictors and $n=300$ observations. Three coefficients generate the response; at $\lambda=0.45\lambda_{\max}$, two remain active in the representative solution. The MM update is identical in every run; only the weight policy changes.
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$ leaves the objective and current iterate fixed, but redistributes the curvature of the upper bound and therefore changes the proposed next step. All the surrogates touch the orange objective at the current iterate. The blue curve uses the optimal weights: its minimum is the lowest in the family, so it gives 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. 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 into the surrogate and minimize 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} $$The cost contributed by coordinate $j$ is 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, so $c_j$ is its deactivation point. Beyond that point, additional weight no longer changes its active status and has diminishing marginal value, $(\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. As weight is added, that marginal value stays flat until $c_j$ and then decreases. The optimal-weight procedure repeatedly gives the next increment to the currently largest $-\phi_j'(w_j)$. It stops when $\sum_jw_j=1$; at that point all funded coordinates have the same marginal value $\nu^*$, while 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)$ — base width $\xi_j^2$, narrowing 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$ — which 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$ (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)$ — negligible 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 lasso KKT conditions identify which coefficients are active and which zero coefficients already satisfy optimality. The auxiliary scales turn those conditions into a convex problem over $\bb{R}_+^p$. The matrix bound supplies a concurrent closed-form MM update, and the optimal-weight procedure selects the member of that surrogate family with the smallest one-step upper bound in $\c O(p\log p)$ time.
With exact linear solves and a unique auxiliary minimizer, the theory gives global convergence to the lasso KKT point. The full theory, implementation and experiments are in the paper.