Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Structured penalties

Beyond the ℓ1\ell_1 norm, regreg ships atoms for penalties that encode structure among the coefficients: groups, feature-specific weights, sorted weights, mixtures of these, row structure in coefficient matrices, and low rank. Each is an atom with an exact proximal map, so each can be paired with any smooth loss in rr.simple_problem and solved by FISTA. This page tours them with small least-squares examples.

All examples on this page use the same simulated regression: n=200n = 200 observations, p=30p = 30 features in 10 groups of 3, and a signal in the first two groups (each of which also contains one null coefficient). The columns of XX have roughly unit norm, so that with noise level σ=1\sigma = 1 the noise in each score XjTεX_j^T\varepsilon is roughly standard normal and penalty levels of a few units are natural.

The group lasso

The group lasso penalty is

P(β)=λ∑gwg∥βg∥2,\mathcal{P}(\beta) = \lambda \sum_g w_g \|\beta_g\|_2 ,

where gg ranges over a partition of the coordinates. rr.group_lasso(groups, ...) takes one label per coordinate; any hashable labels work. The weights are given as a dictionary {label: w_g}; groups not in the dictionary get the default wg=∣g∣w_g = \sqrt{|g|}, which makes the penalty comparable across groups of different sizes.

1.7320508075688772 1.7320508075688772
\lambda_{} \sum_g w_g \|\beta[g]\|_2

The dual norm is max⁡g∥ug∥2/wg\max_g \|u_g\|_2 / w_g (rr.group_lasso_dual). Evaluated at the gradient of the loss at zero it gives λmax⁡\lambda_{\max}, the smallest λ\lambda for which β^=0\hat\beta = 0.

7.168678034986893

Fit at a fraction of λmax⁡\lambda_{\max}:

array([7.885, 3.811, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ])

KKT conditions

β^\hat\beta minimizes ℓ(β)+λ∑gwg∥βg∥2\ell(\beta) + \lambda\sum_g w_g\|\beta_g\|_2 if and only if, for every group,

−∇ℓ(β^)g=λwgβ^g∥β^g∥2if β^g≠0,∥∇ℓ(β^)g∥2≤λwgif β^g=0.-\nabla \ell(\hat\beta)_g = \lambda w_g \frac{\hat\beta_g}{\|\hat\beta_g\|_2} \quad \text{if } \hat\beta_g \neq 0, \qquad \|\nabla \ell(\hat\beta)_g\|_2 \le \lambda w_g \quad \text{if } \hat\beta_g = 0 .

That is, the group’s gradient lies in the dual ball of radius λwg\lambda w_g, on its boundary and pointing opposite to β^g\hat\beta_g for active groups. We check both conditions:

group 0: active,   |grad_g| / (lam w_g) = 1.000000, max |-grad_g - lam w_g beta_g/|beta_g|| = 2.4e-12
group 1: active,   |grad_g| / (lam w_g) = 1.000000, max |-grad_g - lam w_g beta_g/|beta_g|| = 4.0e-12
group 2: inactive, |grad_g| / (lam w_g) = 0.464075
group 3: inactive, |grad_g| / (lam w_g) = 0.204392
group 4: inactive, |grad_g| / (lam w_g) = 0.402718
group 5: inactive, |grad_g| / (lam w_g) = 0.437563
group 6: inactive, |grad_g| / (lam w_g) = 0.414932
group 7: inactive, |grad_g| / (lam w_g) = 0.428482
group 8: inactive, |grad_g| / (lam w_g) = 0.128011
group 9: inactive, |grad_g| / (lam w_g) = 0.840270

A solution path, warm-starting each fit from the previous one, shows groups entering the model as λ\lambda decreases:

<Figure size 600x350 with 1 Axes>

Unpenalized groups

A group with weight 0 is not penalized. This is how to always keep a block of variables (an intercept, adjustment covariates, ...) in the model. Even at λ=2λmax⁡\lambda = 2\lambda_{\max}, group 0 is fit, and its gradient is exactly zero (it is solved by least squares given the others):

[ 8.796 -6.902 -1.836  0.     0.     0.   ]
max |gradient| on the unpenalized group: 1.0914602555089914e-12
group 0: unpenalized, max |grad_g| = 1.1e-12
group 1: inactive, |grad_g| / (lam w_g) = 0.307023
group 2: inactive, |grad_g| / (lam w_g) = 0.060595
group 3: inactive, |grad_g| / (lam w_g) = 0.047658
group 4: inactive, |grad_g| / (lam w_g) = 0.074715
group 5: inactive, |grad_g| / (lam w_g) = 0.073159
group 6: inactive, |grad_g| / (lam w_g) = 0.060755
group 7: inactive, |grad_g| / (lam w_g) = 0.070335
group 8: inactive, |grad_g| / (lam w_g) = 0.032791
group 9: inactive, |grad_g| / (lam w_g) = 0.128027

Singleton groups give the lasso

With every coordinate in its own group, wg=1=1w_g = \sqrt{1} = 1 and ∥βg∥2=∣βj∣\|\beta_g\|_2 = |\beta_j|, so the group lasso is the lasso:

max |difference|: 8.253953076575726e-12

Sparse group lasso

The sparse group lasso adds a (weighted) ℓ1\ell_1 term to the group penalty,

P(β)=λ(∑jαj∣βj∣+∑gwg∥βg∥2),\mathcal{P}(\beta) = \lambda\Big(\sum_j \alpha_j|\beta_j| + \sum_g w_g\|\beta_g\|_2\Big),

so that it selects groups and sparsifies within the selected groups. rr.sparse_group_lasso(groups, lasso_weights, weights=..., lagrange=...) takes the feature weights αj\alpha_j (a scalar is broadcast) in addition to the group labels and group weights. Its proximal map is the composition of soft-thresholding (the ℓ1\ell_1 part) followed by group-wise shrinkage:

sparse_group_lasso_dual

Fitted to our data, the sparse group lasso keeps the two signal groups and, unlike the group lasso fit above, also zeros the null coordinate within each of them (rows are groups):

group lasso:
 [[ 6.332 -4.566 -1.112]
 [ 2.693  0.625 -2.623]
 [ 0.     0.     0.   ]
 [ 0.     0.     0.   ]]
sparse group lasso:
 [[ 5.889 -3.885  0.   ]
 [ 2.29   0.    -2.104]
 [ 0.     0.     0.   ]
 [ 0.     0.     0.   ]]
nonzero coordinates: [0 1 3 5]

Weighted ℓ1\ell_1

rr.weighted_l1norm(weights, lagrange=λ) is λ∑jwj∣βj∣\lambda\sum_j w_j|\beta_j| with wj≥0w_j \ge 0; its dual is rr.weighted_supnorm, max⁡j∣uj∣/wj\max_j |u_j|/w_j. Weights of zero leave a coordinate unpenalized. A common use is the adaptive lasso, with wj=1/∣β~j∣w_j = 1/|\tilde\beta_j| for a pilot estimate β~\tilde\beta (here least squares):

nonzero: [ 0  1  3  5  7 23 27]
[ 9.291 -5.586 -0.     5.255  0.    -4.637  0.     0.521]

The conjugate is a bound-form weighted_supnorm. It is parametrized by the reciprocal weights (max⁡jvj∣uj∣\max_j v_j|u_j| with vj=1/wjv_j = 1/w_j, and vj=∞v_j = \infty when wj=0w_j = 0), so the check below compares against 1 / weights:

regreg.atoms.weighted_atoms supnorm 2.0

SLOPE

SLOPE (the sorted ℓ1\ell_1 norm) penalizes the sorted absolute coefficients ∣β∣(1)≥∣β∣(2)≥⋯|\beta|_{(1)} \ge |\beta|_{(2)} \ge \cdots with non-increasing weights,

P(β)=λ∑jwj∣β∣(j),w1≥w2≥⋯≥wp>0.\mathcal{P}(\beta) = \lambda\sum_j w_j |\beta|_{(j)}, \qquad w_1 \ge w_2 \ge \dots \ge w_p > 0 .

With the Benjamini–Hochberg-type weights wj=σ Φ−1(1−qj/(2p))w_j = \sigma\,\Phi^{-1}(1 - qj/(2p)) and an orthogonal design it controls the false discovery rate at level qq. The penalty tends to set coefficients of similar size to exactly equal magnitudes. Only the Lagrange form has a proximal map (computed by isotonic regression); its conjugate is rr.slope_conjugate.

nonzero: [ 0  1  3  5 27]
sorted nonzero magnitudes: [6.4607 3.9479 3.026  2.7468 0.6784]

A quick optimality check: for the sorted ℓ1\ell_1 norm, β^\hat\beta is optimal iff −∇ℓ(β^)-\nabla\ell(\hat\beta) lies in λ∂P(β^)\lambda\partial\mathcal{P}(\hat\beta). A necessary condition, easy to check, is that the dual norm of the gradient equals λ\lambda when β^≠0\hat\beta \ne 0, i.e. the gradient lies on the boundary of the dual ball:

1.0000000000000104

Mixed lasso

rr.mixed_lasso(penalty_structure, lagrange) mixes several treatments in a single atom. penalty_structure gives one label per coordinate: the reserved negative codes in regreg.atoms.mixed_lasso

codeconstanttreatment of βj\beta_j
-1UNPENALIZEDno penalty
-2L1_PENALTYλ∣βj∣\lambda\lvert\beta_j\rvert
-3POSITIVE_PARTλmax⁡(βj,0)\lambda\max(\beta_j, 0)
-4NONNEGATIVEconstraint βj≥0\beta_j \ge 0

and every other (nonnegative) label names a group, penalized by λwg∥βg∥2\lambda w_g\|\beta_g\|_2 with weights from the weights dictionary (default ∣g∣\sqrt{|g|}). Only the Lagrange form is available. The prox acts coordinate- or group-wise:

[ 3.         -3.          2.          0.          2.         -3.
  3.          0.          2.15147186  2.86862915]

The unpenalized coordinates are untouched, the ℓ1\ell_1 ones are soft-thresholded, the nonnegative ones are projected onto [0,∞)[0, \infty), and the group (3,4)(3, 4) is shrunk by λwg=2\lambda w_g = \sqrt{2} in norm. The positive-part coordinates are shifted down by λ\lambda if above it, set to 0 if in [0,λ][0, \lambda], and left unchanged if negative (the penalty is 0 there).

As a fitted example: keep the first group unpenalized, penalize the next two groups as groups, give the remaining features an ℓ1\ell_1 penalty and constrain the last two to be nonnegative.

[ 9.113 -6.427 -1.493  2.663  0.768 -2.526  0.     0.     0.     0.
  0.     0.     0.     0.     0.     0.     0.     0.     0.     0.
  0.     0.     0.     0.     0.     0.     0.     0.716  0.471  0.565]

Block norms for multi-response problems

For a coefficient matrix B∈Rp×qB \in \mathbb{R}^{p\times q} (one column per response), the block norms apply one norm to each row and combine the row norms with another:

atompenaltydual
rr.l1_l2(shape)∑i∣Bi∣2\sum_i |B_i|_2rr.linf_l2
rr.linf_l2(shape)max⁡i∣Bi∣2\max_i |B_i|_2rr.l1_l2
rr.l1_l1(shape)∑i∣Bi∣1\sum_i |B_i|_1rr.linf_linf
rr.linf_linf(shape)max⁡i∣Bi∣∞\max_i |B_i|_\inftyrr.l1_l1

rr.block_sum(atom_cls, shape) and rr.block_max(atom_cls, shape) build the general versions for any row seminorm. l1_l2 is the multi-response (or “multi-task”) group lasso: row ii collects the coefficients of feature ii across responses, so a feature is selected for all responses or none. It is a group lasso on the flattened matrix with row groups and unit weights:

linf_l2((30, 4), bound=1.500000, offset=None)

To fit a multi-response regression, the loss needs a design that acts on p×qp\times q matrices; rr.linear_transform(X, input_shape=(p, q)) gives the map B↦XBB \mapsto XB.

selected rows: [ 0  1  2  3 15 24]

Nuclear norm and low rank

The nuclear norm ∥B∥∗=∑kσk(B)\|B\|_* = \sum_k \sigma_k(B) is the ℓ1\ell_1 norm of the singular values; its dual is the operator norm ∥B∥op=σ1(B)\|B\|_{\mathrm{op}} = \sigma_1(B). The prox soft-thresholds the singular values, so penalized estimates have low rank. With the multi-response design above this is reduced-rank regression:

singular values of the estimate: [16.5622  0.      0.      0.    ]

The KKT conditions for the nuclear norm say that −∇ℓ(B^)=λ(UVT+W)-\nabla\ell(\hat B) = \lambda(U V^T + W), where B^=UDVT\hat B = U D V^T is the reduced SVD, UTW=0U^T W = 0, WV=0W V = 0 and ∥W∥op≤1\|W\|_{\mathrm{op}} \le 1. In particular the singular values of the gradient are at most λ\lambda, with exactly rank⁡(B^)\operatorname{rank}(\hat B) of them equal to λ\lambda:

rank: 1
singular values of gradient / lambda: [1.       0.858565 0.555414 0.472301]

The same atom gives matrix completion when the loss only involves the observed entries, e.g. 12∑(i,j)∈Ω(Bij−Yij)2\frac{1}{2}\sum_{(i,j)\in\Omega}(B_{ij} - Y_{ij})^2.