Regularization paths

Regularization paths#

regreg.paths#

Generic machinery for computing regularization paths.

This module defines the grouped_path base class, which specific path classes (LASSO, group LASSO, etc.) subclass, as well as the path algorithms strong_rules and warm_start that operate on such objects.

regreg.paths.subsample_columns(X, columns)#

Extract columns of a (possibly implicit) design matrix.

Parameters:

X (ndarray or regreg.affine.affine_transform) – Design matrix with one-dimensional input shape.
columns (sequence of int) – Columns to extract.

Returns:

cols (ndarray) – Array of shape X.output_shape + (len(columns),) holding the selected columns.

class regreg.paths.grouped_path(saturated_loss, X, lasso_weights, elastic_net_param=None, alpha=1.0)#

Bases: object

Base class for regularization paths over groups of variables.

Subclasses implement the methods used by strong_rules and warm_start (e.g. check_KKT, strong_set, solve_subproblem).

full_loss()#: Saturated loss composed with the design matrix self.X.

subsample_columns(X, columns)#

Extract columns of X into ndarray or regreg transform.

Parameters:

X (object) – Representation of design matrix.
columns (sequence of int) – Columns to extract.

Returns:

cols (ndarray or regreg.affine.affine_transform) – The selected columns.

full_gradient(saturated_loss, linear_predictor)#

Gradient of saturated loss composed with self.X.

Parameters:

saturated_loss (regreg.smooth.smooth_atom) – Loss as a function of the linear predictor.
linear_predictor (ndarray) – Linear predictor at which to evaluate the gradient.

Returns:

gradient (ndarray) – Gradient with respect to the coefficients.

linpred(coef, X, test)#

Form linear predictor for given set of coefficients.

Typical use case will have coef of shape (l,p) for univariate response regressions and (l,q,p) for multiple response regressions (e.g. multinomial with q classes) where l is the number of Lagrange parameters.

Parameters:

coef (ndarray) – A set of coefficients.
X (object) – Representation of design matrix, usually self.X – subclasses may not assume this is actually an array.
test (index) – Indices of X.dot(coef.T) to return.

Returns:

linpred (ndarray) – Matrix of linear predictors.

subsample(case_idx)#

Create a new path, by subsampling cases of self.saturated_loss.

Case weights are computed with self.saturated_loss.subsample.

Parameters:: case_idx (index) – An index-like object used to specify which cases to include in the subsample.
Returns:: subsample_path (path object) – A path object with a modified smooth part reflecting the subsampling.

check_KKT(grad_solution, solution, lagrange, penalty=None, kkt_tol=None)#

Check KKT conditions over the groups in the path.

Determines which groups are failing the KKT conditions (these could be active groups or inactive groups).

Parameters:

grad_solution (ndarray) – Candidate for gradient of smooth loss at Lagrange value lagrange.
solution (ndarray) – Candidate for solution to problem at Lagrange value lagrange.
lagrange (float) – Lagrange value for penalty.
penalty (object, optional) – A penalty. If None, defaults to self.penalty.
kkt_tol (float, optional) – Relative tolerance for the groups at zero: such a group fails if its dual norm exceeds lagrange * (1 + kkt_tol). If None, defaults to self.kkt_tol.

Returns:

failing_A (ndarray) – Boolean indicator of active groups failing the KKT conditions.
failing_I_ranks (ndarray) – For inactive groups, the rank of each failing group (by the size of its violation), with -1 for groups that do not fail.

regreg.paths.default_lagrange_sequence(penalty, null_solution, lagrange_proportion=0.05, nstep=100, alpha=1)#

Default decreasing, log-spaced sequence of Lagrange parameters.

Parameters:

penalty (regreg.atoms.atom) – Penalty for the path.
null_solution (ndarray) – Gradient of the loss at the null solution. The largest Lagrange parameter is the dual seminorm of this value.
lagrange_proportion (float, optional) – Ratio of the smallest to the largest Lagrange parameter.
nstep (int, optional) – Number of Lagrange parameters.
alpha (float, optional) – Elastic net mixing parameter; the sequence is divided by alpha.

Returns:

lagrange_seq (ndarray) – Decreasing sequence of Lagrange parameters.

regreg.paths.strong_rules(path_obj, lagrange_seq, initial_data, inner_tol=1e-05, verbose=False, initial_step=None, check_active=False, max_tries=20, kkt_tol=None)#

Compute a regularization path using strong rules screening.

Parameters:

path_obj (grouped_path) – Path object describing the problem.
lagrange_seq (sequence of float) – Decreasing sequence of Lagrange parameters.
initial_data (tuple) – Pair (solution, grad_solution) at lagrange_seq[0].
inner_tol (float, optional) – Tolerance for each subproblem.
verbose (bool, optional) – Print progress information?
initial_step (float, optional) – Initial step size for the solver. If None, it is estimated from the Lipschitz constant of path_obj.X.
check_active (bool, optional) – Also check KKT conditions for active groups?
max_tries (int, optional) – Maximum number of attempts at each Lagrange parameter.
kkt_tol (float, optional) – Relative tolerance of the KKT check for groups at zero. If None, path_obj.kkt_tol is used.

Returns:

output (dict) – Dictionary with keys 'dev explained', 'lagrange' and 'beta' (the solutions along the path).

regreg.paths.warm_start(path_obj, lagrange_seq, initial_data, inner_tol=1e-05, verbose=False, initial_step=None, solve_args=None)#

Compute a regularization path using warm starts.

Each problem along the path is solved with all variables, starting from the solution at the previous Lagrange parameter.

Parameters:

path_obj (grouped_path) – Path object describing the problem.
lagrange_seq (sequence of float) – Sequence of Lagrange parameters.
initial_data (tuple) – Pair (solution, grad_solution); only solution is used, as the initial warm start.
inner_tol (float, optional) – Tolerance for each problem.
verbose (bool, optional) – Print progress information?
initial_step (float, optional) – Initial step size for the solver. If None, it is estimated from the Lipschitz constant of path_obj.X.
solve_args (dict, optional) – Extra arguments passed to simple_problem.solve.

Returns:

output (dict) – Dictionary with keys 'devratio', 'lagrange' and 'beta' (the solutions along the path).

regreg.paths.lasso#

Regularization paths for the (weighted) LASSO and elastic net.

class regreg.paths.lasso.lasso_path(saturated_loss, X, lasso_weights, elastic_net_param=None, alpha=1.0)#

Bases: grouped_path

Regularization path for the weighted LASSO / elastic net.

The problem at Lagrange parameter \(\lambda\) is

\[\ell(X\beta) + \lambda \alpha \sum_j w_j |\beta_j| + \frac{1 - \alpha}{2} \sum_j \lambda_j c_j \beta_j^2\]

where \(\ell\) is saturated_loss, \(w\) is lasso_weights, \(c\) is elastic_net_param, and \(\lambda_j=\lambda\) for penalized variables, \(\lambda_j=1\) for unpenalized ones.

Parameters:

saturated_loss (regreg.smooth.glm.glm) – Loss as a function of the linear predictor.
X (ndarray or regreg.affine.affine_transform) – Design matrix.
lasso_weights (ndarray) – Weights for the L1 penalty; variables with weight 0 are unpenalized.
elastic_net_param (ndarray, optional) – Ridge weights for each variable. Defaults to all ones.
alpha (float, optional) – Elastic net mixing parameter; 1 is the LASSO.

enet_loss(lagrange, candidate_set=None)#

Ridge (elastic net) part of the objective.

Parameters:

lagrange (float) – Lagrange parameter.
candidate_set (index, optional) – Restrict the ridge term to these variables.

Returns:

loss (regreg.smooth.quadratic.quadratic_loss) – Diagonal quadratic loss.

subsample(case_idx)#

Create a new path, by subsampling cases of self.saturated_loss.

Case weights are computed with self.saturated_loss.subsample.

Parameters:: case_idx (index) – An index-like object used to specify which cases to include in the subsample.
Returns:: subsample_path (path object) – A path object with a modified smooth part reflecting the subsampling.

check_KKT(grad_solution, solution, lagrange, penalty=None, kkt_tol=None)#

Check KKT conditions over the groups in the path.

Determines which groups are failing the KKT conditions (these could be active groups or inactive groups).

Parameters:

grad_solution (ndarray) – Candidate for gradient of smooth loss at Lagrange value lagrange.
solution (ndarray) – Candidate for solution to problem at Lagrange value lagrange.
lagrange (float) – Lagrange value for penalty.
penalty (object, optional) – A weighted L1 penalty. If None, defaults to self.penalty.
kkt_tol (float, optional) – Relative tolerance for the groups at zero: such a group fails if its dual norm exceeds lagrange * (1 + kkt_tol). If None, defaults to self.kkt_tol.

Returns:

failing_active (ndarray) – Boolean indicator of active (or unpenalized) groups failing the KKT conditions.
inactive_ranks (ndarray) – For inactive groups failing the KKT conditions, the rank of the size of the violation; -1 for all other groups.

strong_set(lagrange_cur, lagrange_new, grad_solution)#

Compute the strong set at lagrange_new.

Parameters:

lagrange_cur (float) – Current Lagrange parameter.
lagrange_new (float) – Next Lagrange parameter.
grad_solution (ndarray) – Gradient at the solution for lagrange_cur.

Returns:

strong (ndarray) – Indices of variables in the strong set.
strong_bool (ndarray) – Boolean indicator of the strong set.
strong_vars (ndarray) – Indices of variables in the strong set (same as strong).

active_set(solution)#: Boolean indicator of nonzero coefficients in solution.

restricted_penalty(subset)#: Weighted L1 penalty restricted to subset (all variables if None).

solve_subproblem(solution, candidate_set, lagrange_new, **solve_args)#

Solve the problem restricted to a candidate set of variables.

Parameters:

solution (ndarray) – Current solution, used as a warm start.
candidate_set (index) – Variables to include in the subproblem.
lagrange_new (float) – Lagrange parameter.
solve_args (dict) – Keyword arguments passed to simple_problem.solve.

Returns:

final_step (float) – Final step size of the solver.
sub_grad (ndarray) – Gradient of the restricted smooth loss at sub_soln.
sub_soln (ndarray) – Solution of the subproblem.
sub_linear_pred (ndarray) – Linear predictor at sub_soln.
candidate_bool (ndarray) – Boolean indicator of the candidate set.

enet_grad(solution, penalized, lagrange_new, subset=None)#

Gradient of the ridge (elastic net) part of the objective.

Parameters:

solution (ndarray) – Coefficients.
penalized (ndarray) – Boolean indicator of penalized variables; for these the ridge term is multiplied by lagrange_new.
lagrange_new (float) – Lagrange parameter.
subset (index, optional) – Restrict to these variables.

Returns:

G (ndarray) – Gradient of the ridge term.

updated_ever_active(index_obj, group_ids=False)#

Indices of variables that are ever active, with index_obj added.

Parameters:

index_obj (index) – Variables to add to the ever-active set.
group_ids (bool, optional) – Ignored.

Returns:

ever_active (list) – Sorted indices of ever-active variables.

property unpenalized#

Unpenalized variables.

Returns:

groups (ndarray) – Indices of variables with weights equal to 0.
variables (ndarray) – Boolean indicator that is True if no penalty on that variable.

regreg.paths.lasso.logistic(X, Y, *args, **keyword_args)#

Construct a lasso_path for the logistic regression loss with binary response Y.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.probit(X, Y, *args, **keyword_args)#

Construct a lasso_path for the probit regression loss with binary response Y.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.cloglog(X, Y, *args, **keyword_args)#

Construct a lasso_path for the complementary log-log regression loss with binary response Y.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.gaussian(X, Y, *args, **keyword_args)#

Construct a lasso_path for the Gaussian (squared error) loss with response Y.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.cox(X, T, S, *args, **keyword_args)#

Construct a lasso_path for the Cox partial likelihood with event times T and status S.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.poisson(X, Y, *args, **keyword_args)#

Construct a lasso_path for the Poisson regression loss with count response Y.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.huber(X, Y, smoothing_parameter, *args, **keyword_args)#

Construct a lasso_path for the Huber loss with response Y and smoothing parameter smoothing_parameter.

Remaining arguments are passed to lasso_path.

regreg.paths.lasso.huber_svm(X, Y, smoothing_parameter, *args, **keyword_args)#

Construct a lasso_path for the smoothed (Huberized) hinge loss with binary response Y and smoothing parameter smoothing_parameter.

Remaining arguments are passed to lasso_path.

regreg.paths.group_lasso#

Regularization paths for the group LASSO and group elastic net.

class regreg.paths.group_lasso.group_lasso_path(saturated_loss, X, groups, weights={}, elastic_net_param=None, alpha=1.0)#

Bases: grouped_path

Regularization path for the group LASSO / group elastic net.

The problem at Lagrange parameter \(\lambda\) is

\[\ell(X\beta) + \lambda \alpha \sum_g w_g \|\beta_g\|_2 + \frac{1 - \alpha}{2} \sum_j \lambda_j c_j \beta_j^2\]

where \(\ell\) is saturated_loss, \(w\) are the group weights, \(c\) is elastic_net_param, and \(\lambda_j=\lambda\) for penalized variables, \(\lambda_j=1\) for unpenalized ones.

Parameters:

saturated_loss (regreg.smooth.glm.glm) – Loss as a function of the linear predictor.
X (ndarray or regreg.affine.affine_transform) – Design matrix.
groups (ndarray) – Group label for each variable.
weights (dict, optional) – Weight for each group; see regreg.atoms.group_lasso.group_lasso. Groups with weight 0 are unpenalized.
elastic_net_param (ndarray, optional) – Ridge weights for each variable. Defaults to all ones.
alpha (float, optional) – Elastic net mixing parameter; 1 is the group LASSO.

enet_loss(lagrange, candidate_groups=None)#

Ridge (elastic net) part of the objective.

Parameters:

lagrange (float) – Lagrange parameter.
candidate_groups (sequence, optional) – Restrict the ridge term to variables in these groups.

Returns:

loss (regreg.smooth.quadratic.quadratic_loss) – Diagonal quadratic loss.

subsample(case_idx)#

Create a new path, by subsampling cases of self.saturated_loss.

Case weights are computed with self.saturated_loss.subsample.

Parameters:: case_idx (index) – An index-like object used to specify which cases to include in the subsample.
Returns:: subsample_path (path object) – A path object with a modified smooth part reflecting the subsampling.

check_KKT(grad_solution, solution, lagrange, penalty=None, kkt_tol=None)#

Check KKT conditions over the groups in the path.

Determines which groups are failing the KKT conditions (these could be active groups or inactive groups).

Parameters:

grad_solution (ndarray) – Candidate for gradient of smooth loss at Lagrange value lagrange.
solution (ndarray) – Candidate for solution to problem at Lagrange value lagrange.
lagrange (float) – Lagrange value for penalty.
penalty (object, optional) – A group LASSO penalty. If None, defaults to self.penalty.
kkt_tol (float, optional) – Relative tolerance for the groups at zero: such a group fails if its dual norm exceeds lagrange * (1 + kkt_tol). If None, defaults to self.kkt_tol.

Returns:

failing_active (ndarray) – Boolean indicator of active (or unpenalized) groups failing the KKT conditions.
inactive_ranks (ndarray) – For inactive groups failing the KKT conditions, the rank of the size of the violation; -1 for all other groups.

strong_set(lagrange_cur, lagrange_new, grad_solution)#

Compute the strong set of groups at lagrange_new.

Parameters:

lagrange_cur (float) – Current Lagrange parameter.
lagrange_new (float) – Next Lagrange parameter.
grad_solution (ndarray) – Gradient at the solution for lagrange_cur.

Returns:

strong (ndarray) – Group ids in the strong set.
strong_bool (ndarray) – Boolean indicator (over groups) of the strong set.
strong_vars (ndarray) – Indices of variables in groups in the strong set.

solve_subproblem(solution, candidate_groups, lagrange_new, **solve_args)#

Solve the problem restricted to a candidate set of groups.

Parameters:

solution (ndarray) – Current solution, used as a warm start.
candidate_groups (sequence) – Groups to include in the subproblem.
lagrange_new (float) – Lagrange parameter.
solve_args (dict) – Keyword arguments passed to simple_problem.solve.

Returns:

final_step (float) – Final step size of the solver.
sub_grad (ndarray) – Gradient of the restricted smooth loss at sub_soln.
sub_soln (ndarray) – Solution of the subproblem.
sub_linear_pred (ndarray) – Linear predictor at sub_soln.
candidate_bool (ndarray) – Boolean indicator of variables in the candidate groups.

enet_grad(solution, penalized, lagrange_new, subset=None)#

Gradient of the ridge (elastic net) part of the objective.

Parameters:

solution (ndarray) – Coefficients.
penalized (ndarray) – Boolean indicator of penalized variables; for these the ridge term is multiplied by lagrange_new.
lagrange_new (float) – Lagrange parameter.
subset (index, optional) – Restrict to these variables.

Returns:

G (ndarray) – Gradient of the ridge term.

updated_ever_active(index_obj, group_ids=True)#

Groups that are ever active, with index_obj added.

Parameters:

index_obj (index) – Index into the (sorted) groups to add to the ever-active set.
group_ids (bool, optional) – If True, return group ids, otherwise return indices into the sorted groups.

Returns:

ever_active (list) – Ever-active groups.

property unpenalized#

Unpenalized groups.

Returns:

groups (list) – Group ids with weights equal to 0.
group_idx (ndarray) – Boolean indicator (over sorted groups) that is True if no penalty on that group.

active_set(solution)#: Boolean indicator of groups with nonzero coefficients in solution.

restricted_penalty(var_subset)#: Group LASSO penalty restricted to var_subset (all variables if None).

regreg.paths.group_lasso.logistic(X, Y, *args, **keyword_args)#

Construct a group_lasso_path for the logistic regression loss with binary response Y.