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.

Solvers

Every problem in regreg is put in composite form,

minimizeβ f(β)+g(β),\text{minimize}_\beta \ f(\beta) + g(\beta),

with ff smooth (its gradient is Lipschitz) and gg convex with a cheap proximal map

proxg/L(z)=argminβ L2∥β−z∥22+g(β).\text{prox}_{g/L}(z) = \text{argmin}_\beta \ \frac{L}{2}\|\beta - z\|_2^2 + g(\beta).

The main solver is FISTA, the accelerated proximal gradient method of Beck and Teboulle (2009). Each iteration takes a gradient step on ff from an extrapolated point and then applies the proximal map of gg. This page describes the problem containers and solver options, how to plug in your own problem, and the alternatives for problems that do not fit this pattern directly: dual solves for container, ADMM, TFOCS/NESTA-style smoothing, and a proximal quasi-Newton method.

simple_problem: one smooth part, one atom

rr.simple_problem(loss, atom) pairs a smooth loss with a single atom whose proximal map is known exactly. Its solve method runs FISTA and returns the solution; keyword arguments go to FISTA.fit:

The step size is chosen by backtracking: it is decreased by a factor 1.1 until the usual quadratic upper bound on ff holds, and tentatively increased every 100 iterations. After solve, the history of objective values is in problem.solver_results and the final step in problem.final_step. Because the backtracking condition is only checked along the iterates, the accepted step reflects the local curvature of ff and can be much larger than 1/L1/L, where LL is the global Lipschitz constant of ∇f\nabla f. In the example below L=∥X∥22L = \|X\|_2^2 is dominated by the factor shared by all columns, and the final step is about ten times 1/L1/L.

iterations: 545
final step: 0.000276   1/L: 2.58e-05
nonzero coefficients: 35

Using FISTA directly

rr.FISTA(problem) creates the solver; fit takes the same arguments as above and returns the vector of objective values, one per iteration. The solution is written into problem.coefs (FISTA modifies the problem’s coefficients in place, so a second fit warm starts from the previous solution).

Momentum matters. With correlated columns the problem is badly conditioned and ISTA converges at rate O(1/k)O(1/k), against O(1/k2)O(1/k^2) for FISTA. Without adaptive restart FISTA’s objective is not monotone and it oscillates; restarting the momentum whenever the objective increases (the default) removes the oscillation and typically converges fastest.

FISTA (default)    iterations:  654   f - f*: -8.4e-07
FISTA, no restart  iterations: 2000   f - f*: 1.7e-02
ISTA               iterations: 2000   f - f*: 3.4e+00
<Figure size 700x400 with 1 Axes>

Fixed step size

Backtracking costs extra evaluations of ff. If the Lipschitz constant is known, set solver.perform_backtrack = False and give the problem a lipschitz attribute; FISTA then uses step 1/L1/L throughout. rr.power_L(X) estimates ∥X∥22\|X\|_2^2, which is LL for least squares. For this problem the global constant is pessimistic, and the fixed step needs more iterations than backtracking.

iterations: 1475   f - f*: 1.2e-05

Defining your own problem: the composite interface

FISTA only needs four things from a problem: a coefs array (the starting point, overwritten with the solution), smooth_objective(x, mode) returning the value (mode='func'), gradient ('grad') or both ('both') of ff, nonsmooth_objective(x) returning g(x)g(x), and proximal(q). The argument q of proximal is an rr.identity_quadratic, the function β↦L2∥β−μ∥22+ηTβ+γ\beta \mapsto \frac{L}{2}\|\beta - \mu\|_2^2 + \eta^T\beta + \gamma, and proximal must return the minimizer of q(β)+g(β)q(\beta) + g(\beta). Its attribute q.true_center is μ−η/L\mu - \eta / L, so the proximal map is evaluated at q.true_center with step 1/L1/L where LL is q.coef.

Subclassing rr.composite provides coefs, objective and the plumbing. As an example, here is least squares under box constraints ℓ≤β≤u\ell \le \beta \le u, whose proximal map is clipping, compared with scipy.optimize.lsq_linear.

[ 0.2   -0.082 -0.2    0.196  0.2   -0.085  0.2    0.2   -0.2    0.2  ]
max |regreg - lsq_linear|: 8.318296051967877e-11

regreg’s own atoms and smooth losses implement the same interface (with the quadratic term handled for you), so they can be mixed with hand-written pieces: for instance rr.simple_problem(my_smooth, atom) works for any object with smooth_objective and coefs.

container: several atoms, solved through the dual

rr.container(loss, atom_1, ..., atom_k) minimizes f(β)+∑jPj(Djβ+αj)f(\beta) + \sum_j {\cal P}_j(D_j\beta + \alpha_j) where the atoms are possibly composed with affine maps (see constraints and linear transforms). The proximal map of the sum has no closed form, so at every FISTA step the container solves the dual of the proximal problem,

minimizeβ L2∥β−z∥22+∑jPj(Djβ+αj)  ⟺  minimizeu1,…,uk 12L∥∑jDjTuj−Lz∥22−∑jαjTuj+∑jPj∗(uj),\text{minimize}_\beta \ \frac{L}{2}\|\beta - z\|_2^2 + \sum_j {\cal P}_j(D_j\beta + \alpha_j) \iff \text{minimize}_{u_1, \dots, u_k} \ \frac{1}{2L}\Big\|\sum_j D_j^Tu_j - Lz\Big\|_2^2 - \sum_j \alpha_j^T u_j + \sum_j {\cal P}_j^*(u_j),

by an inner FISTA run (with fixed step from power_L of the stacked DjD_j), and recovers β=z−∑jDjTuj/L\beta = z - \sum_j D_j^Tu_j / L. The conjugates Pj∗{\cal P}_j^* are again atoms with exact proximal maps. The inner solver can be controlled by passing prox_control, a dictionary of fit arguments (defaults tol=1e-14, max_its=5000), to solve or fit. Because the inner solve is iterative, the outer solve is accurate only to roughly the precision of the inner one.

Below is a generalized lasso, 12∥Y−Xβ∥22+λ∥Dβ∥1\frac{1}{2}\|Y - X\beta\|_2^2 + \lambda\|D\beta\|_1 with a random DD.

container: 5.53s, objective 2317.844370

ADMM

The alternating direction method of multipliers handles the same generalized problem ℓ(β)+P(Dβ+α)\ell(\beta) + {\cal P}(D\beta + \alpha) by splitting z=Dβ+αz = D\beta + \alpha and alternating

β←argminβ ℓ(β)+ρ2∥Dβ+α−z+y/ρ∥22,z←proxP/ρ(Dβ+α+y/ρ),y←y+ρ(Dβ+α−z).\beta \leftarrow \text{argmin}_\beta \ \ell(\beta) + \frac{\rho}{2}\|D\beta + \alpha - z + y/\rho\|_2^2, \qquad z \leftarrow \text{prox}_{{\cal P}/\rho}(D\beta + \alpha + y/\rho), \qquad y \leftarrow y + \rho(D\beta + \alpha - z).

regreg.problems.admm.admm_problem(loss, atom, D, rho) implements this; the β\beta-update is a smooth problem solved by FISTA (with arguments from fit_args), and solve(niter) runs a fixed number of iterations. The primal iterate is loss_coefs. Each iteration is cheap but ADMM converges slowly to high accuracy; here 200 iterations agree with the container to about 10-5.

ADMM: 1.71s, objective 2317.844436
max |ADMM - container|: 1.3045302673653225e-06

Smoothing: TFOCS and NESTA

Some problems have no smooth part at all. Two examples are basis pursuit (Chen, Donoho and Saunders, 1998),

minimizeβ ∥β∥1subject toXβ=Y,\text{minimize}_\beta \ \|\beta\|_1 \quad \text{subject to} \quad X\beta = Y,

and the Dantzig selector (Candès and Tao, 2007), minimize ∥β∥1\text{minimize} \ \|\beta\|_1 subject to ∥XT(Y−Xβ)∥∞≤δ\|X^T(Y - X\beta)\|_\infty \le \delta. Both have the form

minimizeβ h(β)+k(Aβ+a),\text{minimize}_\beta \ h(\beta) + k(A\beta + a),

where hh and kk have simple proximal maps but neither is smooth: for basis pursuit h=∥⋅∥1h = \|\cdot\|_1, A=XA = X, a=−Ya = -Y and kk is the indicator of {0}\{0\}. Two ways of making such a problem amenable to FISTA are to smooth the dual (TFOCS) or to smooth kk (NESTA). In both, the smoothing term has a center that is moved from one outer iteration to the next, so that the iterates converge to a solution of the original problem rather than of a smoothed one.

TFOCS: smoothing the dual

Add a proximal term to hh: with hϵ(β)=h(β)+ϵ2∥β−β0∥22h_\epsilon(\beta) = h(\beta) + \frac{\epsilon}{2}\|\beta - \beta_0\|_2^2, consider minimizeβ hϵ(β)+k(Aβ+a)\text{minimize}_\beta \ h_\epsilon(\beta) + k(A\beta + a) (Becker, Candès and Grant, 2011). Writing k(z)=sup⁡uuTz−k∗(u)k(z) = \sup_u u^Tz - k^*(u) and exchanging the min and the max gives the dual problem

minimizeu hϵ∗(−ATu)−aTu+k∗(u).\text{minimize}_u \ h_\epsilon^*(-A^Tu) - a^Tu + k^*(u).

Because hϵh_\epsilon is ϵ\epsilon-strongly convex, its conjugate hϵ∗h_\epsilon^* is differentiable, with gradient

∇hϵ∗(v)=argminβ h(β)+ϵ2∥β−β0∥22−vTβ=proxh/ϵ(β0+v/ϵ),\nabla h_\epsilon^*(v) = \text{argmin}_\beta \ h(\beta) + \frac{\epsilon}{2}\|\beta - \beta_0\|_2^2 - v^T\beta = \text{prox}_{h/\epsilon}\big(\beta_0 + v/\epsilon\big),

which is Lipschitz with constant 1/ϵ1/\epsilon (Nesterov, 2005). So the dual is a smooth function, with Lipschitz constant ∥A∥22/ϵ\|A\|_2^2/\epsilon, plus k∗k^*, which has a proximal map: a simple_problem for FISTA. Its solution u^\hat u gives the primal solution β^=∇hϵ∗(−ATu^)\hat\beta = \nabla h_\epsilon^*(-A^T\hat u) of the regularized problem.

The outer loop sets β0←β^\beta_0 \leftarrow \hat\beta and repeats. This is the proximal point method (Rockafellar, 1976) applied to h+k(A⋅+a)h + k(A\cdot + a), so for any fixed ϵ\epsilon the iterates converge to a solution of the original problem; rr.tfocs also extrapolates the center, as in Güler’s (1992) accelerated proximal point method. The value of ϵ\epsilon trades the two loops against each other. A small ϵ\epsilon makes each outer step nearly a full step towards the solution, so few outer iterations are needed, but makes the inner problem worse conditioned (Lipschitz constant ∥A∥22/ϵ\|A\|_2^2/\epsilon). A large ϵ\epsilon does the reverse. It changes how long the solve takes, not the accuracy of the answer, which is set by the inner tolerance tol and the outer tolerance coef_tol.

rr.tfocs(h, transform, k_conjugate, epsilon=[...]) runs this scheme, with at most one outer iteration per entry of epsilon. The pair (transform, k_conjugate) is the dual attribute of the composed atom k(Aβ+a)k(A\beta + a): transform is β↦Aβ+a\beta \mapsto A\beta + a and k_conjugate is k∗k^*. For basis pursuit we check the result against a linear-programming solve, for several values of ϵ\epsilon.

eps 10     0.45s  max |tfocs - LP| = 3.9e-08  max |X beta - Y| = 1.1e-07
eps 1      0.29s  max |tfocs - LP| = 2.4e-08  max |X beta - Y| = 1.5e-07
eps 0.1    0.10s  max |tfocs - LP| = 3.1e-09  max |X beta - Y| = 1.2e-08

The Dantzig selector’s constraint is rr.supnorm.affine(X.T @ X, -X.T @ Y, bound=delta), so here A=XTXA = X^TX and the inner problem has Lipschitz constant ∥XTX∥22/ϵ\|X^TX\|_2^2/\epsilon, much larger than for basis pursuit (printed below). The inner problems are therefore slower; for harder instances (a smaller δ\delta, more active constraints) a larger ϵ\epsilon or more outer iterations may be needed.

||X^T X||^2 = 5.06e+05,  ||X||^2 = 711
Dantzig selector: 0.88s
||X^T(Y - X beta)||_inf / delta: 1.00000
l1 norm: tfocs 34.61098   LP 34.61098
max |tfocs - LP|: 1.3115681962716508e-07

NESTA: smoothing the constraint

The other option keeps the proximal map of hh and smooths kk instead, by adding a quadratic to its conjugate (the atom method smoothed):

kϵ(z)=sup⁡u uTz−k∗(u)−ϵ2∥u−u0∥22,∇kϵ(z)=argmaxu (⋯ )=proxϵk∗(u0+ϵz).k_\epsilon(z) = \sup_u \ u^Tz - k^*(u) - \frac{\epsilon}{2}\|u - u_0\|_2^2, \qquad \nabla k_\epsilon(z) = \text{argmax}_u \ (\cdots) = \text{prox}_{\epsilon k^*}(u_0 + \epsilon z).

kϵk_\epsilon is smooth with Lipschitz constant 1/ϵ1/\epsilon (Nesterov, 2005), so h(β)+kϵ(Aβ+a)h(\beta) + k_\epsilon(A\beta + a) is a smooth function plus an atom, a simple_problem. For an equality constraint k∗=0k^* = 0, and

kϵ(Aβ+a)=u0T(Aβ+a)+12ϵ∥Aβ+a∥22,k_\epsilon(A\beta + a) = u_0^T(A\beta + a) + \frac{1}{2\epsilon}\|A\beta + a\|_2^2,

the augmented Lagrangian with multiplier u0u_0 and penalty 1/ϵ1/\epsilon. The outer loop sets u0←∇kϵ(Aβ^+a)u_0 \leftarrow \nabla k_\epsilon(A\hat\beta + a), the method of multipliers (Hestenes, 1969; Powell, 1969), which is the proximal point method applied to the dual (Rockafellar, 1976). As for TFOCS, the iterates converge for any fixed ϵ\epsilon, and ϵ\epsilon affects the speed only. NESTA itself (Becker, Bobin and Candès, 2011) smooths hh rather than the constraint, with continuation in the smoothing parameter; rr.nesta is an accelerated augmented-Lagrangian method in the same spirit, and also allows an extra smooth term.

rr.nesta(smooth, h, k_atom, epsilon=[...]) takes the composed atom k(Aβ+a)k(A\beta + a) itself, and smooth (which may be None) is an additional smooth term in the objective.

eps 10     0.06s  max |nesta - LP| = 1.5e-06
eps 1      0.09s  max |nesta - LP| = 9.1e-07
eps 0.1    0.19s  max |nesta - LP| = 8.3e-08

References

Proximal quasi-Newton

For smooth losses with strong curvature, such as logistic regression, proximal Newton methods (Lee, Sun and Saunders, 2014) take fewer, more expensive steps. At each step they minimize the quadratic model of ff plus gg, ∇f(β)TΔ+12ΔTHΔ+g(β+Δ)\nabla f(\beta)^T\Delta + \frac{1}{2}\Delta^TH\Delta + g(\beta + \Delta), and then line search along Δ\Delta. regreg.problems.newton.quasi_newton does this with BFGS updates of HH, starting from a user-supplied initial_hessian. The quadratic subproblems are solved by FISTA, and the keyword arguments of solve are passed to that inner solver.

quasi-Newton steps: 11
max |quasi-Newton - FISTA|: 6.841502411623207e-07

Which solver?

For a smooth loss plus one atom (possibly separable), use simple_problem, whose proximal step is exact. Add atoms composed with linear maps through container, which is convenient but solves a dual problem at every step. ADMM is an alternative when the β\beta-update is cheap or can be reused. For problems with no smooth part, such as constrained ℓ1\ell_1 minimization, use TFOCS- or NESTA-style smoothing.