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.

Atoms, duality and proximal maps

regreg solves composite problems

min⁡β  ℓ(β)+P(β)\min_\beta \; \ell(\beta) + \mathcal{P}(\beta)

where ℓ\ell is smooth and P\mathcal{P} is nonsmooth but simple: its proximal map can be computed exactly and cheaply. The simple nonsmooth pieces are called atoms. This page explains what an atom is, how its proximal map is parametrized, and how atoms relate to each other through convex duality.

Seminorms in Lagrange and bound form

Most atoms are built from a seminorm hh (the ℓ1\ell_1 norm, the ℓ2\ell_2 norm, the group lasso norm, the nuclear norm, ...). Every seminorm atom comes in two forms, chosen by which keyword is given to the constructor:

Exactly one of the two must be specified.

(l1norm((6,), lagrange=0.500000, offset=None), l1norm((6,), bound=2.000000, offset=None))

The method seminorm evaluates λh(β)\lambda h(\beta) (or hh with a different multiplier, via lagrange=), while nonsmooth_objective evaluates the atom as a function, including any offset and quadratic term attached to it (see below). For a bound-form atom nonsmooth_objective returns 0, or +∞+\infty for infeasible points when check_feasibility=True.

3.25 3.25
3.25
inf 0.0

Besides seminorms there are cone constraints, the indicator functions of convex cones: rr.nonnegative, rr.nonpositive, rr.zero, rr.l2_epigraph (∥β1:p−1∥2≤βp\|\beta_{1:p-1}\|_2 \le \beta_p), and so on. They have no Lagrange parameter.

(nonnegative((6,), offset=None), l2_epigraph((6,), offset=None))

Displaying atoms

Every atom has a latexify() method returning a LaTeX string, and a _repr_latex_ method so that Jupyter renders an atom as mathematics when it is the last expression in a cell. (The empty subscripts _{} are placeholders for an optional index argument idx.)

\lambda_{} \|\beta\|_1
I^{\infty}(\|\gamma\|_1 \leq \delta_{})
Loading...

Proximal maps

The single operation an atom must support is its proximal map. In regreg the proximal map is parametrized by an identity_quadratic,

q(β)=L2∥β−μ∥22+⟨η,β⟩+γ,rr.identity_quadratic(coef=L, center=μ, linear_term=η, constant_term=γ).q(\beta) = \frac{L}{2}\|\beta - \mu\|_2^2 + \langle \eta, \beta \rangle + \gamma, \qquad \texttt{rr.identity\_quadratic(coef=}L\texttt{, center=}\mu\texttt{, linear\_term=}\eta\texttt{, constant\_term=}\gamma\texttt{)}.

atom.proximal(q) returns the minimizer of q(β)+P(β)q(\beta) + \mathcal{P}(\beta). Inside FISTA the quadratic is L2∥β−βk∥2+⟨∇ℓ(βk),β⟩\frac{L}{2}\|\beta - \beta_k\|^2 + \langle \nabla \ell(\beta_k), \beta\rangle, so a proximal gradient step is literally atom.proximal(rr.identity_quadratic(L, beta_k, grad_k, 0)).

Two lower-level methods solve the “standard” problems with no linear term: lagrange_prox(θ, lipschitz=L) returns arg⁡min⁡βL2∥β−θ∥2+λh(β)\arg\min_\beta \frac{L}{2}\|\beta-\theta\|^2 + \lambda h(\beta) and bound_prox(θ) returns the projection arg⁡min⁡β12∥β−θ∥2\arg\min_\beta \frac{1}{2}\|\beta-\theta\|^2 subject to h(β)≤δh(\beta)\le \delta. proximal reduces to one of these by completing the square: the minimizer of qq is θ=μ−η/L\theta = \mu - \eta / L.

For the ℓ1\ell_1 norm the Lagrange prox is soft-thresholding at λ/L\lambda/L.

array([-0.15053958, -0.48775021, 1.38271292, 0.59251097, -0.50970152, 0.45252712])

The bound-form prox is a projection onto the ℓ1\ell_1 ball, which does not depend on LL:

2.0

solve is a convenience for nonsmooth atoms: atom.solve(q) is the same prox, and return_optimum=True also returns the optimal value.

Offsets and attached quadratics

An atom may carry an offset α\alpha, in which case it is evaluated at β−α\beta - \alpha, and a quadratic term that is added to it. With both,

P(β)=λh(β−α)+L02∥β−μ0∥2+⟨η0,β⟩+γ0.\mathcal{P}(\beta) = \lambda h(\beta - \alpha) + \frac{L_0}{2}\|\beta-\mu_0\|^2 + \langle \eta_0, \beta\rangle + \gamma_0 .

These are how regreg represents shifted penalties, ridge terms attached to a penalty, and the linear terms that appear in duals.

Loading...
7.9875 7.9875

The proximal map accounts for both: it minimizes q(β)+P(β)q(\beta) + \mathcal{P}(\beta). Substituting u=β−αu = \beta - \alpha and adding the two quadratics, the minimizer is α\alpha plus a soft-thresholding of the new center.

Conjugates and duals

The convex conjugate of ff is f∗(u)=sup⁡β⟨u,β⟩−f(β)f^*(u) = \sup_\beta \langle u, \beta\rangle - f(\beta). For a seminorm hh with dual norm h∗h_* (here h(β)=sup⁡h∗(u)≤1⟨u,β⟩h(\beta) = \sup_{h_*(u)\le 1} \langle u, \beta \rangle),

(λh)∗=I∞(h∗(⋅)≤λ),(I∞(h(⋅)≤δ))∗=δ h∗,(\lambda h)^* = I^\infty(h_*(\cdot) \le \lambda), \qquad \big(I^\infty(h(\cdot)\le\delta)\big)^* = \delta\, h_*,

so conjugation swaps the norm with its dual norm and the Lagrange form with the bound form. atom.conjugate returns this atom:

supnorm((6,), bound=0.500000, offset=None)
supnorm((6,), lagrange=2.000000, offset=None)
group_lasso_dual(array([0, 0, 1, 1, 1]), bound=1.0, weights={np.int64(0): np.float64(1.4142135623730951), np.int64(1): np.float64(1.7320508075688772)}, offset=None)
operator_norm((4, 3), bound=1.000000, offset=None)
l2norm((6,), bound=1.000000, offset=None)
nonpositive((6,), offset=None)

Offsets and linear terms are exchanged by conjugation: the conjugate of β↦λh(β−α)\beta \mapsto \lambda h(\beta - \alpha) is u↦I∞(h∗(u)≤λ)+⟨α,u⟩u \mapsto I^\infty(h_*(u) \le \lambda) + \langle \alpha, u\rangle.

supnorm((6,), bound=0.500000, offset=None, quadratic=identity_quadratic(0.000000, 0.0, array([1., 1., 1., 1., 1., 1.]), 0.000000))
Loading...

If the atom carries a quadratic with positive coefficient, its conjugate is a smooth function, represented by a smooth_conjugate object (see smoothing below).

The dual property (equivalently get_dual()) returns the pair (linear_transform, conjugate). For a plain atom the transform is the identity; for an atom composed with a linear map DD it is DD. This is what the dual problem solvers use: min⁡βℓ(β)+h(Dβ)\min_\beta \ell(\beta) + h(D\beta) has dual min⁡uℓ∗(−DTu)+h∗(u)\min_u \ell^*(-D^T u) + h^*(u).

(<regreg.affine.identity at 0x7f801044bdd0>, supnorm((6,), bound=0.500000, offset=None))

The Moreau decomposition

The proximal maps of ff and f∗f^* are linked by the Moreau decomposition: for any L>0L > 0,

x=prox⁡f/L(x)+1Lprox⁡Lf∗(Lx).x = \operatorname{prox}_{f/L}(x) + \frac{1}{L} \operatorname{prox}_{L f^*}(L x).

In regreg notation, prox⁡f/L(x)\operatorname{prox}_{f/L}(x) is atom.proximal(rr.identity_quadratic(L, x, 0, 0)) and prox⁡Lf∗(Lx)\operatorname{prox}_{Lf^*}(Lx) is atom.conjugate.proximal(rr.identity_quadratic(1/L, L*x, 0, 0)). For a Lagrange-form seminorm the second term is a projection onto λ⋅{h∗≤1}\lambda \cdot\{h_* \le 1\}, so the decomposition says that soft-thresholding is the residual from projecting onto the dual ball. We check it for a range of atoms, in both forms, including one with an offset:

                seminorms.l1norm <-> seminorms.supnorm                    max |error| = 1.1e-16
                seminorms.l1norm <-> seminorms.supnorm                    max |error| = 1.1e-16
                seminorms.l2norm <-> seminorms.l2norm                     max |error| = 5.6e-17
               seminorms.supnorm <-> seminorms.l1norm                     max |error| = 1.1e-16
           weighted_atoms.l1norm <-> weighted_atoms.supnorm               max |error| = 5.6e-17
         group_lasso.group_lasso <-> group_lasso.group_lasso_dual         max |error| = 0.0e+00
sparse_group_lasso.sparse_group_lasso <-> sparse_group_lasso.sparse_group_lasso_dual max |error| = 2.2e-16
                     slope.slope <-> slope.slope_conjugate                max |error| = 1.1e-16
          svd_norms.nuclear_norm <-> svd_norms.operator_norm              max |error| = 1.3e-15
               block_norms.l1_l2 <-> block_norms.linf_l2                  max |error| = 2.2e-16
               cones.nonnegative <-> cones.nonpositive                    max |error| = 1.1e-16
         seminorms.positive_part <-> seminorms.constrained_max            max |error| = 1.1e-16
                seminorms.l1norm <-> seminorms.supnorm                    max |error| = 1.1e-16

Smoothing an atom

Adding a strongly convex quadratic to the conjugate and conjugating back gives a smooth approximation (Nesterov smoothing):

hμ(β)=sup⁡u  ⟨u,β⟩−h∗(u)−μ2∥u∥22.h_\mu(\beta) = \sup_u \; \langle u, \beta\rangle - h^*(u) - \frac{\mu}{2}\|u\|_2^2 .

hμh_\mu is differentiable with ∇hμ(β)=u^(β)\nabla h_\mu(\beta) = \hat u(\beta), the maximizer, which is 1/μ1/\mu-Lipschitz; and h−μ2sup⁡u∈dom h∗∥u∥2≤hμ≤hh - \frac{\mu}{2}\sup_{u \in \mathrm{dom}\, h^*}\|u\|^2 \le h_\mu \le h. atom.smoothed(rr.identity_quadratic(mu, 0, 0, 0)) returns hμh_\mu as a smooth atom, usable as a loss. For λ∥⋅∥1\lambda\|\cdot\|_1 it is the Huber function, with gradient clip(β/μ,−λ,λ)\mathrm{clip}(\beta/\mu, -\lambda, \lambda).

smooth_conjugate(supnorm((6,), bound=0.500000, offset=None, quadratic=identity_quadratic(0.200000, 0.0, 0.0, 0.000000)),identity_quadratic(0.200000, 0.0, 0.0, 0.000000))
Lipschitz constant of the gradient: 5.0
max |finite difference - gradient|: 3.7420022636069916e-10
True

Composing atoms with linear maps

Many penalties are an atom evaluated at a linear function of β\beta, e.g. the fused lasso λ∥Dβ∥1\lambda \|D\beta\|_1 with DD the first-difference matrix. The class methods

construct these (the same methods exist on every seminorm class). shift returns an ordinary atom with offset −a-a. linear and affine return an affine_atom: it can be evaluated, displayed, dualized and smoothed, but it has no cheap proximal map in general. Such penalties are handled either by smoothing or by solving a dual problem (e.g. rr.dual_problem), in which the conjugate atom, which does have a cheap prox, appears and DTD^T is moved into the smooth part.

Loading...
Loading...
(<regreg.affine.linear_transform at 0x7f8060843ec0>, supnorm((7,), bound=1.000000, offset=None))

Smoothing an affine_atom gives a smooth function of β\beta, β↦hμ(Dβ)\beta \mapsto h_\mu(D\beta), with gradient DTu^(Dβ)D^T \hat u(D\beta):

max |finite difference - gradient|: 9.037055548333228e-10

The smoothed penalty can be added to a loss and minimized with any of the problem containers. Smaller μ\mu gives a closer approximation at the price of a larger Lipschitz constant (∥D∥op2/μ\|D\|_{\mathrm{op}}^2/\mu) and slower convergence.