Problems and solvers

Problems and solvers#

regreg.problems.simple#

Problems specified by a smooth function and a single penalty.

This module has a class for specifying a problem from just a smooth function and a single penalty, as well as the gengrad, nesta and tfocs solvers.

class regreg.problems.simple.simple_problem(smooth_atom, proximal_atom)#

Bases: composite

A problem with a smooth part and a single nonsmooth penalty.

The objective is smooth_atom plus proximal_atom, each including its quadratic part.

Parameters:

smooth_atom (regreg.smooth.smooth_atom) – The smooth part of the objective.
proximal_atom (regreg.atoms.atom) – The nonsmooth part of the objective; it must have a proximal map. It is assumed to have 0 for its smooth objective.

smooth_objective(x, mode='both', check_feasibility=False)#

The smooth objective of smooth_atom.

This class explicitly assumes that the proximal_atom has 0 for smooth_objective.

Parameters:

x (ndarray) – Point at which to evaluate.
mode (str, optional) – One of ['func', 'grad', 'both'].
check_feasibility (bool, optional) – Check whether x is feasible?

Returns:

value (float or ndarray or tuple) – Function value, gradient, or both.

nonsmooth_objective(x, check_feasibility=False)#: Nonsmooth objective of proximal_atom plus the quadratics.

proximal(proxq, prox_control=None)#

Proximal map of proximal_atom, with the quadratic parts of smooth_atom and the problem added to proxq.

prox_control, if given, is passed on to proximal_atom.proximal.

static smooth(smooth_atom)#

A problem with no nonsmooth part except possibly the quadratic of smooth_atom.

The proximal function is (almost) a nullop.

Parameters:: smooth_atom (regreg.smooth.smooth_atom) – The smooth objective.
Returns:: problem (simple_problem) – Problem with a zero penalty.

static nonsmooth(proximal_atom)#

A problem with no smooth part.

Parameters:: proximal_atom (regreg.atoms.atom) – The nonsmooth objective.
Returns:: problem (simple_problem) – Problem with a zero smooth part.

latexify(var=None)#: Return a LaTeX representation of the problem.

solve(quadratic=None, return_optimum=False, **fit_args)#

Solve the problem using FISTA.

The final step size is stored as self.final_step.

Parameters:

quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic added to the objective.
return_optimum (bool, optional) – Also return the optimal value?
fit_args (dict) – Keyword arguments passed to regreg.algorithms.FISTA.fit.

Returns:

optimal_value (float) – Only returned if return_optimum is True.
coefs (ndarray) – The solution.

regreg.problems.simple.gengrad(simple_problem, lipschitz, tol=1e-08, max_its=1000, debug=False, coef_stop=False)#

A simple generalized gradient solver.

Parameters:

simple_problem (simple_problem) – Problem to solve.
lipschitz (float) – Lipschitz constant of the gradient; the step size is 1 / lipschitz.
tol (float, optional) – Convergence tolerance.
max_its (int, optional) – Maximum number of iterations.
debug (bool, optional) – Print progress information?
coef_stop (bool, optional) – Stop based on coefficient changes instead of objective value.

Returns:

coef (ndarray) – The solution.

regreg.problems.simple.nesta(smooth_atom, proximal_atom, conjugate_atom, epsilon=None, tol=1e-10, max_iters=100, min_iters=5, coef_tol=1e-08, initial_primal=None, initial_dual=None, coef_stop=False, quadratic=None)#

Solve a problem with the NESTA algorithm.

The objective is the sum of smooth_atom, proximal_atom and conjugate_atom, where conjugate_atom is smoothed by adding a quadratic to its conjugate, with decreasing smoothing parameters epsilon.

Parameters:

smooth_atom (regreg.problems.composite.smooth) – A smooth function, i.e. having a smooth_objective method. May be None.
proximal_atom (regreg.atoms.atom) – An atom with a proximal method. May be None.
conjugate_atom (regreg.atoms.atom) – An atom that will be smoothed, by adding a quadratic to its conjugate.
epsilon (sequence of float, optional) – Smoothing parameters, one per outer iteration (so at most len(epsilon) outer iterations are run). A constant sequence is fine: each outer iteration moves the center of the smoothing term, and the iterates converge to a solution of the unsmoothed problem.
tol (float, optional) – Tolerance (relative change in objective) to which each smoothed problem is solved, passed to simple_problem.solve. It does not depend on epsilon: the smoothing parameter changes how many iterations are needed, not the accuracy of the solution.
max_iters (int, optional) – Maximum number of iterations. If epsilon is not supplied, it is taken to be [1]*max_iters.
min_iters (int, optional) – Minimum number of iterations.
coef_tol (float, optional) – Tolerance for assessing convergence.
initial_primal (ndarray, optional) – Initial condition for the primal variable.
initial_dual (ndarray, optional) – Initial condition for the dual variable.
coef_stop (bool, optional) – Stop based on changes in the dual coefficients instead of the objective value.
quadratic (regreg.identity_quadratic.identity_quadratic, optional) – A quadratic term that is added to the total objective.

Returns:

primal (ndarray) – Primal coefficients.
dual (ndarray) – Dual coefficients.

regreg.problems.simple.tfocs(primal_atom, transform, dual_proximal_atom, epsilon=None, tol=1e-10, max_iters=100, coef_tol=1e-08, quadratic=None)#

Solve a problem with a TFOCS-style smoothed dual method.

This function is based on the setup of problems described in TFOCS. Generally speaking, these are the same type of problems that nesta can handle, though without the additional smooth part.

This solver is suited to solving problems of the form

\[\text{minimize}_v f(v) + h(Dv+a)\]

when both \(f\) and \(h\) (and hence \(f^*\) and \(h^*\)) have simple proximal operators.

Parameters:

primal_atom (regreg.atoms.atom) – The atom \(f\), which will be smoothed, then composed with the transform.
transform (regreg.affine.affine_transform) – The affine transform \(v \mapsto Dv+a\) for the composition.
dual_proximal_atom (regreg.atoms.atom) – The atom \(h^*\), which must have a proximal method.
epsilon (sequence of float, optional) – Smoothing parameters, one per outer iteration (so at most len(epsilon) outer iterations are run). A constant sequence is fine: each outer iteration moves the center of the smoothing term, and the iterates converge to a solution of the unsmoothed problem.
tol (float, optional) – Tolerance (relative change in objective) to which each smoothed problem is solved, passed to simple_problem.solve. It does not depend on epsilon: the smoothing parameter changes how many iterations are needed, not the accuracy of the solution.
max_iters (int, optional) – Maximum number of iterations. If epsilon is not supplied, it is taken to be [1]*max_iters.
coef_tol (float, optional) – Tolerance for assessing convergence of coefficients.
quadratic (regreg.identity_quadratic.identity_quadratic, optional) – A quadratic term that is added to the total objective.

Returns:

primal (ndarray) – Primal coefficients.
dual (ndarray) – Dual coefficients.

Examples

Here is an example for minimum \(\ell_1\) norm reconstruction.

>>> import numpy as np, regreg.api as rr
>>> rng = np.random.default_rng(0)
>>> n, p = 200, 5000

The problem assumes Y=np.dot(X,beta) for some sparse beta.

>>> X = rng.standard_normal((n, p))
>>> beta = np.zeros(p)
>>> beta[:10] = np.arange(10)+1
>>> Y = np.dot(X, beta)

The problem is formally,

\[\text{minimize}_v \|v\|_1 \quad \text{subject to} \quad Y=Xv\]

The \(\ell_1\) norm is described as:

>>> l1 = rr.l1norm(p, lagrange=1)

The constraint is specified as

>>> constraint = rr.zero_constraint.affine(X,-Y)

>>> transform, zero = constraint.dual
>>> epsilon = [0.01]*50 + [0.001]*20
>>> primal_tfocs, dual_tfocs = rr.tfocs(l1, transform, zero, epsilon=epsilon)
>>> bool(np.linalg.norm(primal_tfocs - beta) < 1.e-2 * np.linalg.norm(beta))
True

>>> bool(np.linalg.norm(primal_tfocs[10:]) < 1.e-3 * np.linalg.norm(primal_tfocs))
True

regreg.problems.container#

A container combining several smooth and nonsmooth atoms into one problem.

class regreg.problems.container.container(*atoms, **keywords)#

Bases: composite

A container class for storing/combining atoms.

The objective is the sum of the smooth and nonsmooth atoms. The proximal map is computed by solving a dual problem (see dual_problem) unless the combined transform is an identity or a selector.

Parameters:: atoms (sequence) – Smooth composites (regreg.problems.composite.smooth) and nonsmooth atoms (regreg.problems.composite.nonsmooth, affine atoms or affine cones). At least one smooth atom is required.

smooth_objective(x, mode='both', check_feasibility=False)#

Sum of the smooth objectives of the smooth atoms.

The smooth_objective DOES NOT INCLUDE the identity quadratic of all the smooth atoms.

Parameters:

x (ndarray) – Point at which to evaluate.
mode (str, optional) – One of ['func', 'grad', 'both'].
check_feasibility (bool, optional) – Check whether x is feasible?

Returns:

value (float or ndarray or tuple) – Function value, gradient, or both.

nonsmooth_objective(x, check_feasibility=False)#: Sum of the nonsmooth objectives of all atoms plus the quadratic.

default_solver#: alias of FISTA

proximal(proxq, prox_control=None)#

The proximal function for the primal problem.

Parameters:

proxq (regreg.identity_quadratic.identity_quadratic) – Quadratic term of the proximal problem.
prox_control (dict, optional) – Arguments for FISTA.fit when solving the dual problem.

Returns:

argmin (ndarray) – Minimizer of the proximal problem. If the dual problem is solved and prox_control['return_objective_hist'] is True, a tuple (argmin, objective_hist) is returned.

solve(quadratic=None, return_optimum=False, **fit_args)#

Solve the problem using FISTA.

Parameters:

quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic added to the objective.
return_optimum (bool, optional) – Also return the optimal value?
fit_args (dict) – Keyword arguments passed to regreg.algorithms.FISTA.fit.

Returns:

optimal_value (float) – Only returned if return_optimum is True.
coefs (ndarray) – The solution.

regreg.problems.separable#

Separable penalties built from several atoms acting on disjoint slices.

This module implements the notion of a separable support function / constraint regularizer or penalty.

The penalty is specified by a primal shape, a sequence of atoms and a sequence of slicing objects.

regreg.problems.separable.has_overlap(shape, groups)#

Determine whether the groups, viewed as slices of an array with given shape, have any overlap.

Parameters:

shape (tuple) – A tuple of integers representing a shape for an array.
groups (sequence) – A sequence of objects that can be viewed as slices of an ndarray with shape==shape.

Returns:

res (bool) – True if the slices overlap, else False.

Examples

>>> from regreg.problems.separable import has_overlap
>>> has_overlap((4,5), [slice(2,3), slice(4,5)])
False
>>> has_overlap((4,5), [slice(2,3), [Ellipsis, slice(4,5)]])
True

class regreg.problems.separable.separable(shape, atoms, groups, test_for_overlap=False, shapes=[], initial=None)#

Bases: atom

A separable penalty: a sum of atoms, each applied to a slice of the argument.

\[x \mapsto \sum_i {\cal P}_i(x[g_i])\]

Coordinates not covered by any group are unpenalized.

Parameters:

shape (tuple) – Shape of the argument.
atoms (sequence of regreg.atoms.atom) – The atoms \({\cal P}_i\).
groups (sequence) – Slicing objects \(g_i\), one for each atom.
test_for_overlap (bool, optional) – If True, raise ValueError if the groups overlap.
shapes (sequence, optional) – Shapes to which each slice is reshaped before being passed to its atom; None means no reshaping.
initial (ndarray, optional) – Initial value of coefs. Defaults to zeros.

latexify(var=None, idx='')#: Return a LaTeX representation of the separable penalty.

seminorm(x, lagrange=None, check_feasibility=False)#: Sum of the seminorms of each atom on its slice of x.

constraint(x, bound=None)#: Sum of the constraints of each atom on its slice of x.

nonsmooth_objective(x, check_feasibility=False)#: Sum of the nonsmooth objectives of each atom on its slice of x.

proximal(proxq, prox_control=None)#

Proximal map, computed separately for each atom on its slice.

Coordinates not in any group are mapped by the proximal map of the zero penalty.

property conjugate#

separable in the conjugates of the atoms if there is no quadratic, otherwise a smooth_conjugate.

Type:: The conjugate

property selectors#: Selectors for each group.

class regreg.problems.separable.separable_problem(smooth_atom, shape, atoms, groups, test_for_overlap=False, shapes=[])#

Bases: simple_problem

A simple_problem whose nonsmooth part is a separable penalty.

Parameters:

smooth_atom (regreg.smooth.smooth_atom) – The smooth part of the objective.
shape (tuple) – Shape of the argument.
atoms (sequence of regreg.atoms.atom) – Atoms making up the separable penalty.
groups (sequence) – Slicing objects, one for each atom.
test_for_overlap (bool, optional) – If True, raise ValueError if the groups overlap.
shapes (sequence, optional) – Shapes to which each slice is reshaped; see separable.

static singleton(atom, smooth_f)#: A separable problem with a single atom applied to all coordinates.

static fromatom(separable_atom, smooth_f)#: A separable problem from a separable atom and a smooth function.

property selectors#: Selectors for each group of the separable penalty.

regreg.problems.composite#

Base classes for problems in composite (smooth plus nonsmooth) form.

class regreg.problems.composite.composite(shape, offset=None, quadratic=None, initial=None)#

Bases: object

A generic way to specify a problem in composite form.

A composite objective is the sum of a smooth part (smooth_objective), a nonsmooth part (nonsmooth_objective) and a quadratic (quadratic).

Parameters:

shape (int or tuple) – Shape of the argument of the objective.
offset (ndarray, optional) – Offset subtracted from the argument before evaluation.
quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic part of the objective.
initial (ndarray, optional) – Initial value for coefs. Defaults to zeros.

set_offset(value)#: Set the offset; an offset that is all zeros is ignored.

get_offset()#: Get the offset (None if there is no offset).

property offset#: Get the offset (None if there is no offset).

latexify(var=None, idx='')#

Return a LaTeX representation of the objective.

Parameters:

var (str, optional) – LaTeX name for the argument of the objective. Defaults to self.objective_vars['var'].
idx (str, optional) – Subscript to attach to the parameters.

Returns:

latex (str) – LaTeX string.

nonsmooth_objective(x, check_feasibility=False)#

The nonsmooth part of the objective; here just the quadratic.

Parameters:

x (ndarray) – Point at which to evaluate.
check_feasibility (bool, optional) – Check whether x is feasible (unused here).

Returns:

value (float) – Value of the nonsmooth part.

smooth_objective(x, mode='both', check_feasibility=False)#

The smooth part of the objective and/or its gradient.

Parameters:

x (ndarray) – Point at which to evaluate.
mode (str, optional) – One of ['func', 'grad', 'both'].
check_feasibility (bool, optional) – Check whether x is feasible?

Returns:

value (float or ndarray or tuple) – Function value, gradient, or both.

objective(x, check_feasibility=False)#

Total objective: smooth plus nonsmooth part.

Parameters:

x (ndarray) – Point at which to evaluate.
check_feasibility (bool, optional) – Check whether x is feasible?

Returns:

value (float) – Value of the objective.

proximal_step(quadratic, prox_control=None)#

Compute the proximal optimization.

Parameters:

quadratic (regreg.identity_quadratic.identity_quadratic) – Quadratic term of the proximal problem.
prox_control (dict, optional) – If not None, then a dictionary of parameters for the prox procedure.

Returns:

argmin (ndarray) – Minimizer of the proximal problem.

apply_offset(x)#: If self.offset is not None, return x-self.offset, else return x.

set_quadratic(quadratic)#: Set the quadratic part of the composite.

get_quadratic()#: Get the quadratic part of the composite.

property quadratic#: Quadratic part of the object, instance of regreg.identity_quadratic.identity_quadratic.

smoothed(smoothing_quadratic)#

Smooth the composite by adding a quadratic to its conjugate.

Parameters:: smoothing_quadratic (regreg.identity_quadratic.identity_quadratic) – Quadratic added to the conjugate; its coefficient must be nonzero.
Returns:: smoothed_atom (object) – The conjugate of the smoothed conjugate, a smooth approximation to this composite.

solve(quadratic=None, return_optimum=False, **fit_args)#: Solve the problem. Must be implemented by subclasses.

class regreg.problems.composite.nonsmooth(shape, offset=None, quadratic=None, initial=None)#

Bases: composite

A composite subclass that explicitly returns 0 as smooth_objective.

smooth_objective(x, mode='both', check_feasibility=False)#: The zero function (and its zero gradient).

solve(quadratic=None, return_optimum=False, **fit_args)#

Minimize the objective plus quadratic with a single proximal step.

Parameters:

quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic added to the objective.
return_optimum (bool, optional) – Also return the optimal value?
fit_args (dict) – Ignored.

Returns:

optimal_value (float) – Only returned if return_optimum is True.
coefs (ndarray) – The minimizer.

class regreg.problems.composite.smooth(shape, offset=None, quadratic=None, initial=None)#

Bases: composite

A composite subclass with no nonsmooth part.

The nonsmooth part is just the quadratic, so the proximal map is that of a quadratic.

get_lipschitz()#: Lipschitz constant of the gradient, including the quadratic.

set_lipschitz(value)#: Set the Lipschitz constant of the gradient (excluding the quadratic).

property lipschitz#: Lipschitz constant of the gradient, including the quadratic.

smooth_objective(x, mode='func', check_feasibility=False)#: Evaluate self._smooth_objective; see composite.smooth_objective.

proximal(quadratic)#: Minimizer of self.quadratic plus quadratic.

solve(quadratic=None, return_optimum=False, **fit_args)#

Minimize the objective plus quadratic using FISTA.

Parameters:

quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic added to the objective.
return_optimum (bool, optional) – Also return the optimal value?
fit_args (dict) – Keyword arguments passed to regreg.algorithms.FISTA.fit.

Returns:

optimal_value (float) – Only returned if return_optimum is True.
coefs (ndarray) – The minimizer.

class regreg.problems.composite.smooth_conjugate(atom, smoothing_quadratic=None)#

Bases: smooth

Smooth conjugate of an atom.

Given an atom, compute the conjugate of this atom plus an identity_quadratic, which will be a smooth version of the conjugate of the atom.

Parameters:

atom (regreg.atoms.atom) – The atom to conjugate.
smoothing_quadratic (identity_quadratic, optional) – Quadratic added to the atom. The total quadratic coefficient (the atom’s plus this one) must be nonzero.

Notes

Should we have an argument “collapse” that makes a copy?

get_conjugate()#: The conjugate of the smooth conjugate, i.e. the atom with the quadratics added back in.

property conjugate#: The conjugate of the smooth conjugate, i.e. the atom with the quadratics added back in.

latexify(var=None, idx='')#

Return a LaTeX representation of the smooth conjugate.

Parameters:

var (str, optional) – LaTeX name for the argument.
idx (str, optional) – Subscript to attach to the parameters.

Returns:

latex (str) – LaTeX string.

smooth_objective(x, mode='both', check_feasibility=False)#

Evaluate the smooth conjugate and/or its gradient.

Parameters:

x (ndarray) – Point at which to evaluate.
mode (str, optional) – If 'both', return both function value and gradient; if 'grad', return only the gradient; if 'func', return only the function value.
check_feasibility (bool, optional) – Unused.

Returns:

value (float or ndarray or tuple) – Function value, gradient, or both.

proximal(proxq, prox_control=None)#: Not defined for a smooth conjugate; raises ValueError.

regreg.problems.conjugate#

Convex conjugates of atoms, computed by solving an optimization problem.

class regreg.problems.conjugate.conjugate(atom, quadratic=None, negate=False, **fit_args)#

Bases: composite

The convex conjugate of an atom plus a quadratic.

For an atom \(f\) and quadratic \(Q\) this represents the smooth function

\[v \mapsto \sup_{\beta} \left(\beta^Tv - f(\beta) - Q(\beta)\right)\]

where the atom’s own quadratic is included in \(f\). Its gradient is the maximizer, computed with the atom’s proximal map (or by solving a smooth problem if the atom is smooth).

Parameters:

atom (regreg.atoms.atom or regreg.smooth.smooth_atom) – The function to conjugate. It is copied.
quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic added to the atom; the total quadratic coefficient must be nonzero.
negate (bool, optional) – If True, evaluate the conjugate at \(-v\) instead of \(v\).
fit_args (dict) – Keyword arguments for the solver, used if atom is smooth.

smooth_objective(x, mode='both', check_feasibility=False)#

Evaluate the conjugate function and/or its gradient.

Parameters:

x (ndarray) – Point at which to evaluate.
mode (str, optional) – If 'both', return both function value and gradient; if 'grad', return only the gradient; if 'func', return only the function value.
check_feasibility (bool, optional) – Unused.

Returns:

value (float or ndarray or tuple) – Function value, gradient, or both.

regreg.problems.dual_problem#

Solving composite problems through their duals.

class regreg.problems.dual_problem.dual_problem(f_conjugate, transform, atom)#

Bases: composite

A class for specifying a problem of the form

\[\text{minimize}_{x} f(x) + g(Dx)\]

which will be solved by a dual problem

\[\text{minimize}_{u} f^*(-D^Tu) + g^*(u)\]

while the primal variable is stored in the computation of the gradient of \(f^*\).

Parameters:

f_conjugate (regreg.problems.composite.smooth) – The conjugate \(f^*\).
transform (regreg.affine.affine_transform) – The linear transform \(D\).
atom (regreg.atoms.atom) – The conjugate \(g^*\).

property quadratic#: Zero quadratic; the quadratic is delegated to the individual parts.

static fromprimal(f, *g)#

Construct the dual problem from a primal problem.

Parameters:

f (regreg.problems.composite.composite) – The function \(f\); must have a conjugate attribute.
g (sequence of atoms) – Atoms whose sum is the function \(g(D\cdot)\).

Returns:

problem (dual_problem) – The dual problem.

smooth_objective(x, mode='both', check_feasibility=False)#

The smooth part \(f^*(-D^Tu)\) of the dual objective.

The smooth_objective DOES NOT INCLUDE the identity quadratic of all the smooth atoms. If the gradient is computed, the current primal variable is stored as self.primal.

nonsmooth_objective(x, check_feasibility=False)#: The nonsmooth part \(g^*(u)\) of the dual objective.

proximal(proxq, prox_control=None)#: The proximal function for the dual problem.

solve(quadratic=None, return_optimum=False, **fit_args)#

Solve the dual problem using FISTA, returning the primal solution.

Parameters:

quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Ignored.
return_optimum (bool, optional) – Also return the objective at the primal solution?
fit_args (dict) – Keyword arguments passed to regreg.algorithms.FISTA.fit.

Returns:

optimal_value (float) – Only returned if return_optimum is True.
primal (ndarray) – The primal solution.

latexify(var=None)#: Return a LaTeX representation of the dual problem.

regreg.problems.dual_problem.stacked_dual(shape, *primary_atoms)#

Computes a dual of

\[\sum_i g_i(D_i\beta)\]

under the substitutions \(v_i=D_i\beta\).

That is, it returns the following dual function after minimizing over \((v_i,\beta_i)\):

\[-\sum_i g_i^*(u_i)\]

as well as the transform \(D : \mathbb{R}^p \to \prod_i \mathbb{R}^{m_i}\) where \(p\) is the primal shape and \(m_i\) are the corresponding dual shapes.

Parameters:

shape (tuple) – The primal shape; used only if no atoms are given.
primary_atoms (sequence of atoms) – Objects that have a dual attribute, which is a pair (ltransform, conjugate).

Returns:

transform (regreg.affine.affine_transform) – The stacked transform \(D\).
dual_atom (regreg.atoms.atom or regreg.problems.separable.separable) – The (separable) conjugate atom.

regreg.problems.admm#

Simple ADMM implementation.

class regreg.problems.admm.admm_problem(loss, atom, transform, augmented_param, quadratic=None, fit_args={})#

Bases: object

A problem solved by the alternating direction method of multipliers.

Objective function is the loss plus the atom composed with the transform.

\[\ell(x) + {\cal P}(Dx + \alpha)\]

Our transform is a map \(x \mapsto Dx + \alpha\), and we introduce new variables \(z=Dx+\alpha\) so our affine constraint is \(Dx-z=-\alpha\).

In the ADMM slides (p.14) of https://stanford.edu/class/ee364b/lectures/admm_slides.pdf we have \((A,B,c)=(D,-I,-\alpha)\).

Parameters:

loss (regreg.smooth.smooth_atom) – The smooth loss \(\ell\).
atom (regreg.atoms.atom) – The nonsmooth penalty \({\cal P}\).
transform (regreg.affine.affine_transform) – The affine map \(x \mapsto Dx + \alpha\).
augmented_param (float) – The augmented Lagrangian parameter \(\rho\).
quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Stored, but currently unused.
fit_args (dict, optional) – Keyword arguments for the solver used in the \(x\) update.

update_loss_coefs()#

Update \(x\), the coefficients of the loss.

Minimizes over \(x\)

\[\ell(x) + \frac{\rho}{2} x^TD^TDx + x^T D^T(y - \rho (z - \alpha))\]

update_atom_coefs()#

Update \(z\), the coefficients of the atom.

Minimizes over \(z\)

\[{\cal P}(z) + \frac{\rho}{2} \|z-Dx-\alpha\|^2_2 - z^Ty\]

update_dual_coefs()#: Dual update \(y \leftarrow y + \rho (Dx + \alpha - z)\).

solve(niter=20)#

Run ADMM for a fixed number of iterations.

Parameters:: niter (int, optional) – Number of iterations.

regreg.problems.newton#

A proximal quasi-Newton solver for problems specified by a smooth function and a single penalty.

class regreg.problems.newton.quasi_newton(smooth_atom, proximal_atom, initial_hessian, initial_step=1.0, quadratic=None)#

Bases: object

Minimize an objective using a proximal quasi-Newton algorithm.

The algorithm is described in Lee, Sun and Saunders. Uses BFGS updates.

Parameters:

smooth_atom (regreg.smooth.smooth_atom) – Smooth objective function.
proximal_atom (regreg.atoms.atom) – Nonsmooth part – its proximal map is used in solving inner loop.
initial_hessian (ndarray) – Guess at initial Hessian.
initial_step (float, optional) – Guess at initial stepsize.
quadratic (regreg.identity_quadratic.identity_quadratic, optional) – Quadratic term optionally added to overall objective (e.g. for a ridge penalty).

objective(coefs)#

Total objective.

Parameters:: coefs (ndarray) – Where to evaluate the objective.
Returns:: value (float) – Value of the objective.

update_hessian(old_soln, new_soln, old_grad, new_grad)#

Update current Hessian using the BFGS updating rule.

See BFGS. The update is done in place.

Parameters:

old_soln (ndarray) – Current position.
new_soln (ndarray) – Next position.
old_grad (ndarray) – Current gradient.
new_grad (ndarray) – Next gradient.

smooth_objective(x, mode='both', check_feasibility=False)#

Compute value and / or gradient of our smooth part.

Parameters:

x (ndarray) – Argument to smooth objective.
mode (str, optional) – One of ['func', 'grad', 'both'].
check_feasibility (bool, optional) – Check whether x is feasible?

Returns:

f (float, optional) – Value of smooth objective at x.
g (ndarray, optional) – Gradient of smooth objective at x.

nonsmooth_objective(x, check_feasibility=False)#

Compute value of nonsmooth part, including the quadratic terms.

Parameters:

x (ndarray) – Argument to nonsmooth objective.
check_feasibility (bool, optional) – Check whether x is feasible?

Returns:

f (float) – Value of nonsmooth objective at x.

proximal(proxq)#: Proximal map of proximal_atom, with the quadratic parts added to proxq.

latexify(var=None)#: Return a LaTeX representation of the problem.

solve_inner_loop(return_optimum=False, initial_step=None, **fit_args)#

Inner loop of quasi-Newton.

Given \(x, G, H\) our current position, gradient and Hessian of the smooth part we minimize the (quasi) 2nd order Taylor approximation of the smooth part plus the nonsmooth atom.

\[\Delta \mapsto G^T\Delta + \frac{1}{2} \Delta^TH\Delta + {\cal P}(\Delta + x)\]

Parameters:

return_optimum (bool, optional) – Unused.
initial_step (float, optional) – Unused.
fit_args (dict) – Keyword arguments for the solver of the quadratic subproblem.

Returns:

direction (ndarray) – Search direction \(\Delta\).
grad (ndarray) – Gradient \(G\) of the smooth part at the current position.
quad_soln (ndarray) – Solution \(x + \Delta\) of the quadratic subproblem.

solve(niter=30, maxfun=10, maxiter=5, **fit_args)#

Run quasi-Newton for at most niter steps.

Parameters:

niter (int, optional) – Number of quasi-Newton steps to take.
maxfun (int, optional) – Maximum function evaluations passed to fmin_powell.
maxiter (int, optional) – Maximum iterations passed to fmin_powell.
fit_args (dict) – Keyword arguments for the inner loop solver.

Returns:

coefs (ndarray) – Optimal solution.

converged(old_value, new_value, old_soln, new_soln, old_grad, new_grad)#

Check convergence based on the change in position.

Parameters:

old_value (float) – Current value (unused).
new_value (float) – Next value (unused).
old_soln (ndarray) – Current position.
new_soln (ndarray) – Next position.
old_grad (ndarray) – Current gradient (unused).
new_grad (ndarray) – Next gradient (unused).

Returns:

converged (bool) – True if the maximum absolute change in position is small relative to the norm of new_soln.

backtrack(direction, maxiter=10, maxfun=6)#

Run a simple line search using scipy.optimize.fmin_powell to determine optimal stepsize.

Parameters:

direction (ndarray) – Direction for line search. Found by solving inner optimization problem in quasi-Newton algorithm.
maxiter (int, optional) – Maximum number of iterations in fmin_powell.
maxfun (int, optional) – Maximum number of function evaluations in fmin_powell.

Returns:

stepsize (float) – Optimal stepsize.
value (float) – Objective value at the new position.

regreg.algorithms#

class regreg.algorithms.algorithm(composite)#

Bases: object

Base class for iterative solvers of composite problems.

Parameters:: composite (regreg.problems.composite.composite) – The problem to be solved. It must provide coefs, smooth_objective, nonsmooth_objective and proximal_step.

property output#

The ‘interesting’ part of the composite arguments.

In the regression case, this is the tuple (beta, r).

fit()#: Fit the problem. Abstract method, implemented by subclasses.

class regreg.algorithms.FISTA(composite)#

Bases: algorithm

The FISTA generalized gradient algorithm.

Accelerated proximal gradient descent (Beck and Teboulle, 2009) with backtracking line search and adaptive restarting.

fit(tol=None, min_its=None, max_its=None, FISTA=True, start_step=1.0, restart=inf, coef_stop=False, return_objective_hist=True, monotonicity_restart=True, debug=None, prox_control=None)#

Use the FISTA (or ISTA) algorithm to fit the problem.

Parameters:

tol (float, optional) – Convergence tolerance on the relative change in objective (or coefficients if coef_stop is True). Defaults to self.default_tol.
min_its (int, optional) – Minimum number of iterations. Defaults to self.min_its.
max_its (int, optional) – Maximum number of iterations. Defaults to self.max_its.
FISTA (bool, optional) – Use Nesterov weights? If False, this is just proximal gradient descent (ISTA).
start_step (float, optional) – Used in backtracking. This is the starting value of self.step if no step is available from a previous fit.
restart (int, optional) – Restart Nesterov weights every restart iterations. Default is never (np.inf).
coef_stop (bool, optional) – Stop based on coefficient changes instead of objective value.
return_objective_hist (bool, optional) – Return the sequence of objective values?
monotonicity_restart (bool, optional) – If True, Nesterov weights are restarted every time the objective value increases.
debug (bool, optional) – Resets self.debug, which controls whether convergence information is printed.
prox_control (dict, optional) – A dictionary of arguments for fit(), used when composite.proximal_step itself is a FISTA problem.

Returns:

objective_hist (ndarray) – A vector of objective values. Only returned if return_objective_hist is True.

update_working_coefs(proposed_coefs)#

Update self.working_coefs with a Nesterov momentum step.

Parameters:: proposed_coefs (ndarray) – Coefficients produced by the latest proximal gradient step.

backtrack(itercount)#

Take a proximal gradient step with backtracking line search.

The step size is decreased until the quadratic majorization condition holds at the proposed coefficients.

Parameters:

itercount (int) – Current iteration number.

Returns:

proposed_coefs (ndarray) – Coefficients after the accepted proximal gradient step.
proposed_smooth (float) – Smooth objective evaluated at proposed_coefs.

Problems and solvers

Contents

Problems and solvers#

regreg.problems.simple#

regreg.problems.container#

regreg.problems.separable#

regreg.problems.composite#

regreg.problems.conjugate#

regreg.problems.dual_problem#

regreg.problems.admm#

regreg.problems.newton#

regreg.algorithms#