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.

Constraints and linear transforms

Many structured estimators are a smooth loss plus a penalty or constraint applied not to β\beta itself but to a linear image DβD\beta: the fused lasso penalizes differences, isotonic regression constrains them to be nonnegative, an equality constraint pins down AβA\beta. This page covers the cone constraints in regreg, the affine transforms in regreg.affine, how atoms are composed with linear maps, and how problems with several such terms are solved.

Cone constraints

A convex cone KK gives the constraint β∈K\beta \in K, represented by its indicator function IK(β)I_K(\beta), which is 0 on KK and +∞+\infty off it. The proximal map of IKI_K is Euclidean projection onto KK, and the conjugate of IKI_K is the indicator of the polar cone K∘={u:uTβ≤0 ∀β∈K}K^\circ = \{u : u^T\beta \le 0 \ \forall \beta \in K\}. regreg has

atomconstraintconjugate
rr.nonnegative(p)β≥0\beta \ge 0nonpositive
rr.nonpositive(p)β≤0\beta \le 0nonnegative
rr.zero_constraint(p)β=0\beta = 0zero (the zero function)
rr.zero(p)none (the function 0)zero_constraint
rr.l2_epigraph(p+1)∣β1:p∣2≤βp+1|\beta_{1:p}|_2 \le \beta_{p+1}l2_epigraph_polar
rr.l1_epigraph(p+1)∣β1:p∣1≤βp+1|\beta_{1:p}|_1 \le \beta_{p+1}l1_epigraph_polar
rr.linf_epigraph(p+1)∣β1:p∣∞≤βp+1|\beta_{1:p}|_\infty \le \beta_{p+1}linf_epigraph_polar

For the epigraph cones the last coordinate holds the bound on the norm of the other coordinates.

nonpositive((5,), offset=None)
zero((5,), offset=None)
l2_epigraph_polar((5,), offset=None)

Projection is proximal with a quadratic 12∥β−x∥22\frac{1}{2}\|\beta - x\|_2^2, written rr.identity_quadratic(1, x, 0, 0). Moreau’s decomposition says x=PK(x)+PK∘(x)x = P_K(x) + P_{K^\circ}(x) with the two pieces orthogonal; we check this for the second-order cone.

in K:       True

Nonnegative least squares

A cone constraint is an atom like any other, so nonnegative least squares,

minimizeβ≥0 12∥Y−Xβ∥22,\text{minimize}_{\beta \ge 0} \ \frac{1}{2}\|Y - X\beta\|_2^2,

is a simple_problem whose proximal step is the projection β↦max⁡(β,0)\beta \mapsto \max(\beta, 0). We compare it with the active-set solver scipy.optimize.nnls.

number of zeros: 8
max |regreg - scipy|: 2.1915620984636064e-09

Affine transforms

Everything in regreg.affine implements the same small interface for a map x↦Dx+αx \mapsto Dx + \alpha: linear_map(x) computes DxDx, affine_map(x) computes Dx+αDx + \alpha, adjoint_map(u) computes DTuD^Tu, and the attributes input_shape, output_shape and affine_offset describe it. The linear part may be a dense array, a sparse matrix or another transform, so operators that are never formed explicitly (differences, wavelets, convolutions) work as well as matrices.

(3,) (4,) None

rr.astransform casts an array or sparse matrix to a linear_transform and returns transforms unchanged; most functions that accept a transform call it for you. Transforms compose with rr.affine_composition (the rightmost is applied first), the adjoint of the linear part is T.T (an instance of regreg.affine.adjoint), and rr.power_L estimates ∥D∥22\|D\|_2^2, the Lipschitz constant of β↦12∥Dβ∥22\beta \mapsto \frac{1}{2}\|D\beta\|_2^2, by power iteration.

linear_transform True
power_L: 12.250354265544214  ||A||_2^2: 12.25035426578375

A selector indexes its input before (optionally) applying another transform, which is how penalties are restricted to a subset of coordinates.

[0. 1. 2.]
[1. 1. 1. 0. 0. 0.]

Composing atoms with linear maps

Every atom class has two constructors that compose it with a transform: atom.linear(D, ...) represents P(Dβ){\cal P}(D\beta) and atom.affine(D, alpha, ...) represents P(Dβ+α){\cal P}(D\beta + \alpha). The remaining arguments (lagrange= or bound=) are those of the atom. Thus λ∥Dβ∥1\lambda\|D\beta\|_1 is rr.l1norm.linear(D, lagrange=lam), the constraint Dβ≥0D\beta \ge 0 is rr.nonnegative.linear(D), and the equality constraint Aβ=cA\beta = c is rr.zero_constraint.affine(A, -c).

affine_atom(l1norm((3,), lagrange=2.000000, offset=None), array([[-1.,  1.,  0.,  0.],
       [ 0., -1.,  1.,  0.],
       [ 0.,  0., -1.,  1.]]))
affine_cone

The proximal map of P(Dβ){\cal P}(D\beta) is not available in closed form, so these composed atoms are used inside a rr.container, which takes a smooth loss and any number of nonsmooth terms. The proximal step of a container is computed by solving its dual, in which each composed atom contributes a dual variable uju_j with constraint or penalty Pj∗(uj){\cal P}_j^*(u_j) and the transforms enter only through DjD_j and DjTD_j^T (see the solvers page).

As a first example, least squares under an equality constraint Aβ=cA\beta = c has a closed-form solution from the KKT system $$

(XTXATA0)\begin{pmatrix} X^TX & A^T \\ A & 0 \end{pmatrix}
(βν)\begin{pmatrix} \beta \\ \nu \end{pmatrix}
(XTYc)\begin{pmatrix} X^TY \\ c \end{pmatrix}

$$

max |A beta - c|: 2.9814906099545624e-09
max |regreg - KKT|: 6.237207900855468e-07

The fused lasso and total-variation denoising

For a signal YY observed along a line, total-variation denoising (the one-dimensional fused lasso signal approximator) solves

minimizeβ 12∥Y−β∥22+λ∑i=1n−1∣βi+1−βi∣,\text{minimize}_\beta \ \frac{1}{2}\|Y - \beta\|_2^2 + \lambda \sum_{i=1}^{n-1} |\beta_{i+1} - \beta_i| ,

that is, λ∥Dβ∥1\lambda\|D\beta\|_1 with DD the (n−1)×n(n-1) \times n first-difference matrix. regreg.affine.fused_lasso.difference_transform(x, order=k) returns the sparse matrix of kk-th order divided differences on sorted knots xx (for equally spaced knots and k=1k = 1 this is just βi+1−βi\beta_{i+1} - \beta_i); trend_filter(x, order=k) wraps the same operator as a transform for trend filtering.

csr_matrix (499, 500)
(498,)

The dual of this problem is a box-constrained least-squares problem,

maximize∥u∥∞≤λ 12∥Y∥22−12∥Y−DTu∥22,\text{maximize}_{\|u\|_\infty \le \lambda} \ \frac{1}{2}\|Y\|_2^2 - \frac{1}{2}\|Y - D^Tu\|_2^2 ,

with β^=Y−DTu^\hat\beta = Y - D^T\hat u. Solving it separately as a simple_problem with a supnorm bound gives a lower bound on the optimal value, so the duality gap certifies the container’s solution.

primal 869.691045  dual 869.690616  relative gap 4.9e-07

Adding an ℓ1\ell_1 penalty gives the sparse fused lasso. For the signal approximator its solution is the soft-thresholded total-variation solution (Friedman et al., 2007), which gives another check on a container with two nonsmooth terms. The container’s proximal map is itself computed by an inner dual solve, so the agreement is to about 10-4 rather than to machine precision, and the exact digits vary slightly across platforms; the objective values agree much more closely.

max |container - soft(TV)|: 0.0003731997063010084
relative objective gap: 8.678139891029898e-09
<Figure size 800x400 with 1 Axes>

Isotonic regression

Isotonic regression is least squares under the constraint that the fit is nondecreasing, Dβ≥0D\beta \ge 0:

minimizeβ:β1≤β2≤⋯≤βn 12∥Y−β∥22.\text{minimize}_{\beta : \beta_1 \le \beta_2 \le \dots \le \beta_n} \ \frac{1}{2}\|Y - \beta\|_2^2 .

In regreg the constraint is rr.nonnegative.linear(D). We compare with the pool-adjacent-violators solution from sklearn.isotonic.

max |regreg - sklearn|: 1.1800824140095756e-07

Nearly-isotonic regression

Nearly-isotonic regression (Tibshirani, Hoefling and Tibshirani, 2011) replaces the hard constraint with a penalty on decreases,

minimizeβ 12∥Y−β∥22+λ∑i=1n−1(βi−βi+1)+,\text{minimize}_\beta \ \frac{1}{2}\|Y - \beta\|_2^2 + \lambda \sum_{i=1}^{n-1} (\beta_i - \beta_{i+1})_+ ,

i.e. rr.positive_part.linear(-D, lagrange=lam). At λ=0\lambda = 0 the fit is YY; for λ\lambda large enough it is the isotonic fit.

A container builds its dual problem when it is constructed, so changing the lagrange of one of its atoms afterwards does not change the problem being solved (gh-104); build a new container for each value of λ\lambda.

max |nearly isotonic (lambda=1000) - isotonic|: 9.659481037260775e-08
<Figure size 800x400 with 1 Axes>

Several penalties on disjoint blocks: separable

When different penalties act on disjoint blocks of coordinates, the proximal map splits into the proximal maps of the blocks, so no dual problem is needed. rr.separable(shape, atoms, groups) builds such a penalty from a list of atoms and a matching list of index objects (slices, integer arrays or boolean masks); coordinates in no group are left unpenalized. rr.separable_problem(loss, shape, atoms, groups) is the corresponding simple_problem.

Here an ℓ1\ell_1 penalty acts on the first ten coefficients and a group (ℓ2\ell_2 norm) penalty on the last ten. The same problem written as a container with two selector-composed atoms, solved through the dual, gives the same answer.

[ 1.035  0.737  0.865  0.693  0.685  0.072 -0.     0.067  0.    -0.
  0.197  0.204  0.142  0.045  0.125  0.045 -0.043 -0.037 -0.005  0.068]
max |separable - container|: 1.869700037016031e-06

The choice between the two is a matter of cost: a separable penalty has an exact, cheap proximal map, while a container handles arbitrary (overlapping, non-identity) linear maps at the price of an inner iterative solve of the dual at every proximal step. That inner solve is also what limits the container’s accuracy: here the separable solution is exact to machine precision, while the container agrees with it to about 10-6.