PaperlayerView exact revision on arXiv

Source-linked AI summary

Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems

Laurent El Ghaoui, Vivian Viallon, Tarek Rabbani

arXiv:1009.4219v2cs.LGeess.SYmath.OC

TL;DR

High-dimensional LASSO problems can be too slow or too large for existing solvers. The paper proposes SAFE, a duality-based screening method that removes only features guaranteed to have zero optimal coefficients before optimization. It is especially aggressive at large penalty values, where experiments report order-of-magnitude-or-more variable reductions, and it is extended to broader convex problems.

  • Problem

    Existing LASSO algorithms can become slow with many variables, and some feature matrices are too large to load into memory.

  • Method

    SAFE uses task-specific loss and data to identify coefficients guaranteed to be zero before solving the full LASSO or related convex problem.

  • Results

    SAFE typically removes variables by an order of magnitude or more on the targeted large text-data problems, reducing computational time and memory requirements.

  • Takeaways & Limitations

    SAFE can reduce the problem size before optimization while preserving the full problem's solution for the eliminated features.

  • Takeaways & Limitations

    The derived threshold λ0 need not be the smallest penalty value for which the zero solution is optimal.

Abstract

from arXiv · show

We describe a fast method to eliminate features (variables) in l1 -penalized least-square regression (or LASSO) problems. The elimination of features leads to a potentially substantial reduction in running time, specially for large values of the penalty parameter. Our method is not heuristic: it only eliminates features that are guaranteed to be absent after solving the LASSO problem. The feature elimination step is easy to parallelize and can test each feature for elimination independently. Moreover, the computational effort of our method is negligible compared to that of solving the LASSO problem - roughly it is the same as single gradient step. Our method extends the scope of existing LASSO algorithms to treat larger data sets, previously out of their reach. We show how our method can be extended to general l1 -penalized convex problems and present preliminary results for the Sparse Support Vector Machine and Logistic Regression problems.

1. Introduction

The paper introduces SAFE, a task-specific screening method that identifies guaranteed-zero LASSO coefficients before optimization, reducing problem size for high-dimensional data. Its conservative elimination is especially useful at large penalty values, where experiments report order-of-magnitude variable reductions.

  • LASSO uses ℓ1 regularization to produce sparse coefficients that identify features useful for predicting the response.
  • Existing LASSO algorithms can become slow as the number of variables grows, and some feature matrices cannot be loaded into memory.
  • SAFE identifies zeros in the optimal coefficient vector before solving LASSO and removes the corresponding feature columns from the optimization problem.
  • Unlike generic screening procedures, SAFE uses the supervised learning problem's loss and data, while guaranteeing that eliminated features are absent from the full solution.
  • At large penalty values, SAFE typically removes variables by an order of magnitude or more, reducing computational time and memory requirements.

2. The SAFE method for the LASSO

SAFE derives a duality-based test that encloses the unknown dual optimum in a tractable set and eliminates a feature when the entire set lies inside its associated dual slab. The resulting theorem gives a safe, pre-solution screening rule applicable to LASSO and related formulations.

  • Dual problem and optimality conditions: SAFE uses LASSO duality and optimality conditions to determine whether coefficients must be zero.
  • Dual problem and optimality conditions: The dual problem constrains the dual variable by feature-dependent slabs, and its optimum satisfies θ⋆ = Xw⋆ − y.
  • Basic idea: SAFE replaces the unknown dual optimum in the zero-coefficient test with a set Θ that is guaranteed to contain it.
  • Constructing Θ: The set Θ is constructed as Θ1 ∩ Θ2 using dual objective optimality and a first-order condition at a known solution for λ0.
  • Extensions: The SAFE-LASSO theorem also extends through transformations to intercept and elastic-net formulations.
  • SAFE-LASSO theorem: If the entire set Θ lies strictly inside the slab for feature xk, then the corresponding optimal coefficient is zero and that feature can be safely eliminated before solving LASSO.
  • SAFE-LASSO theorem: For scaled data, the test ranks features like correlation-based selection while retaining a guarantee that eliminated features are absent from the full sparse solution.

3. Using SAFE

SAFE reduces LASSO problem size before optimization by identifying features that can be eliminated, including under memory constraints and across sequences of penalty values.

  • Memory-limited problems: SAFE can find a penalty value that leaves at most M features, enabling LASSO solutions when loading the full feature matrix exceeds the memory limit.Bisection targets LF ∈ [M − ϵF, M], where LF is the number of features remaining after SAFE.
  • Memory-limited problems: The memory-limited procedure applies SAFE, adjusts the penalty if necessary, and solves the reduced LASSO problem using only the surviving columns.The resulting solution is assembled by combining the reduced solution on E^c with zeros on E.
  • SAFE workflow: SAFE searches for features to eliminate before solving LASSO, then solves the reduced problem with zero coefficients assigned to eliminated features.The remaining feature set is denoted E^c, while eliminated features E receive w⋆(E)=0.
  • Penalty sequences: For decreasing penalty sequences, recursive SAFE reuses the previous solution while eliminating features before each successive LASSO solve.The paper presents this as a way to reduce feature counts and potentially improve runtime across a sequence of problems.

4. SAFE applied to general ℓ1-regularized convex problems

The SAFE framework extends from LASSO to l1-regularized convex losses through duality and sufficient elimination tests, with specialized constructions for sparse SVMs and logistic-type losses.

  • General convex problems: SAFE generalizes from LASSO to l1-regularized convex problems whose loss is closed, convex, and non-negative.LASSO is recovered with the squared loss, while hinge and logistic losses provide classification and regression examples.
  • Computational scope: For the generalized test, evaluating all feature tests has complexity O(nm), with effective dimension reduced to the number of nonzero elements for sparse inputs.The paper also presents preliminary SAFE constructions for logistic loss within the same convex framework.
  • Dual SAFE construction: The generalized method derives a dual problem and uses dual feasibility, strong duality, and optimality conditions to certify zero primal coefficients.A feature is associated with a zero coefficient when its dual constraint is strict at optimum.
  • Dual SAFE construction: A feasible dual point and a lower bound γ on the optimal value define a sufficient feature-elimination test through the auxiliary quantity P(γ, xk).The test becomes more aggressive as γ approaches the optimal value because P(γ, xk) decreases when γ increases.
  • Sparse SVM: For hinge-loss sparse SVMs, SAFE uses the specialized dual constraints and can compute the feature-test quantity in O(m log m), or less with sparse data.The construction uses the scaled feasible dual point and a closed-form expression for the relevant quantity.
  • Sparse SVM: The SVM extension removes all features when λ exceeds λmax under the stated choice λ0 = λmax and γ0 = γmax.The paper also reports a closed-form G(z) computation in O(d log d), where d is the number of nonzero elements in z.

5. Numerical results

The experiments evaluate SAFE for reducing memory requirements and computational time across large text-derived LASSO problems and a synthetic intercept setting. They use multiple LASSO solvers and sequence-based procedures under explicit memory limits.

  • SAFE experiments target memory reduction and computational-time savings when solving LASSO problems.The numerical study explicitly separates these two benefits.
  • Solvers: The study compares IPM, GLMNET, TFOCS, FISTA, and Homotopy, noting that some solvers do not return exact zeros.Thresholding issues for evaluating solution cardinality are discussed separately.
  • Memory-limited problems: The PubMed matrix contains 1,000,000 abstracts and 127,025 word features, with 82,209,586 nonzero entries.
  • Memory-limited problems: PubMed cannot be loaded into memory for current solvers, so SAFE uses a 1,000-feature memory limit while targeting solutions with about 100 nonzeros.The memory limit is approximately two orders of magnitude smaller than the original feature count.
  • Computational savings: For NYT headlines, SAFE is evaluated across λ from 0.03λmax to λmax using a matrix with 38,377 features and 192,182 headlines.Figure 4 reports computational-time savings and the number of retained features after SAFE.
  • Intercept problem: The intercept experiment uses synthetic data with m = 500, n = 10^6, sparsity density d = 0.1, and 50 nonzero generated coefficients.GLMNET is used, and the data can be generated but solving the full problem causes memory problems.
  • Intercept problem: The intercept solution at λ = 0.33λmax is obtained through a sequence of 352 smaller problems under a stated feature-memory limit.

Appendix A. Expression of P(γ, xk) (LASSO)

The appendix reformulates the quantity P(γ, x_k) in dual form and derives its computation through scalar optimization conditions. These steps exploit duality and derivatives of the resulting objective.

  • Problem (6) is expressed in dual form as a convex optimization problem with two scalar variables, μ1 and μ2.
  • The derivation solves for μ2 by differentiating the relevant expression with respect to μ2 and setting the derivative to zero.
  • The displayed derivation includes an expression involving x_k and Ψ_k D̃ as part of the resulting formulation.
  • The corresponding step for μ1 differentiates the same expression with respect to μ1 and sets the derivative to zero.
  • The appendix states that P(γ, x) has an equivalent dual expression as a consequence of duality.

Appendix C. SAFE test for SVM

This appendix section studies optimization problems involving polyhedral functions in one or two variables that arise in SAFE computations for LASSO and SVM.

  • The appendix examines one- and two-variable optimization problems involving polyhedral functions for computing Φ(γ, x) and the SAFE-SVM theorem.

C.1 Computing Phi(γ, x)

The appendix computes Φ(γ, x) through a piecewise-linear function built from sorted positive and negative components. Its interpolation and breakpoint structure reduce the optimization to candidate values determined by integer indices.

  • The computation assumes labeled data y ∈ {−1, 1}^m, partitions x into x+ and x−, and sorts both parts in descending order.The class-index sets and class counts define the two subvectors.
  • Piecewise-linear construction: The function F is defined through a dual form on 0 ≤ h ≤ p, with boundary behavior yielding F(h, x) = −∞ outside that interval.
  • Piecewise-linear construction: For 1 ≤ h < p, writing h = q + r uses the integer part q and fractional remainder r to construct the relevant interpolation value.
  • Piecewise-linear construction: F(h, x) is the piecewise-linear interpolation of the sums of the h largest elements of x at integer breakpoints.
  • Optimization domain: The combined function F(·, x+) + F(·, x−) is evaluated over a domain beginning at γ/2 and bounded by the class counts.
  • Optimization domain: The maximizer can be located using the breakpoints of the piecewise-linear components.
  • Computing Φ: Φ(·, −x) linearly interpolates values at even integer γ values, and its computation is expressed using F for the positive and negative subvectors.
  • Computing Φ: When 0 ≤ h < 1, the combined expression equals the positive part of h(x+_1 + x−_1).

C.3 SAFE-SVM test

The SAFE-SVM test evaluates a function G(z) by partitioning z by sign and handling boundary cases before checking candidate breakpoints. Its evaluation complexity is O(k + h log h), below O(d log d) for d nonzero elements.

  • Index-set cases: The test partitions z into positive, negative, and zero index sets with cardinalities k, h, and l.When either the positive or negative set is empty, the minimization simplifies using the corresponding boundary case.
  • Candidate minimizers: The minimization checks κ = 0, κ = 1, and breakpoints 1/(1 − z_j) for negatively ordered elements of z.At κ = 0 and κ = 1, the original objective takes values S+ and p, respectively.
  • Complexity: The algorithm evaluates G(z) in O(k + h log h), which is less than O(d log d) for d nonzero elements.The procedure identifies index sets, orders negative elements when needed, and evaluates the resulting candidates.

Appendix D. Computing Plog(γ, x) via an interior-point method

The logistic-loss computation uses an interior-point method that exploits the dual function’s decomposable structure. Each Newton iteration solves a linear system whose matrix is diagonal plus two rank-one modifications.

  • Interior-point formulation: A generic interior-point method solves the logistic-loss problem through a sequence of linearly constrained subproblems.The method uses a variant of Newton’s method and exploits the decomposable structure of Glog.
  • Newton system: Each iteration solves Hδ = h, where H is a diagonal matrix modified by two rank-one terms.The matrix is written as H = D − ggT − vvT, with D diagonal.

Appendix E. On thresholding methods for LASSO

The appendix compares KKT thresholding with a rule that controls objective perturbation after thresholding. The proposed rule trades more feature removal against a relative-accuracy bound, and is more robust to loose duality gaps in the reported experiments.

  • Motivation: Sparse classifiers may contain many small nonzero coefficients, requiring a thresholding rule to decide which coefficients become zero.The appendix motivates a new rule because the original IPM Logistic thresholding rule can behave poorly.
  • KKT thresholding: The KKT rule sets coefficient w_k to zero using an optimality condition involving X(X^T w − y).The paper names this procedure the KKT rule.
  • Duality-gap sensitivity: Changing ε from 10^-4 to 10^-6 increased computational time by 30% to 40%, while changing it to 10^-8 increased time by 50% to 100%.The experiments therefore identify a direct computational cost for using smaller duality gaps with the KKT approach.
  • Alternative thresholding: The proposed rule controls the objective perturbation induced by replacing w* with a thresholded vector.It chooses the largest threshold allowed by condition (39), using a line search.
  • Accuracy-sparsity trade-off: Increasing α permits more coefficients to be zeroed but bounds the new relative accuracy by αε.The rule also depends on the duality-gap parameter ε; α = 2 is reported to work well in practice.

E.1 Real data examples

The real-data experiments compare thresholding rules on synthetic and NYT headline data under different duality gaps. Across these settings, the proposed rules are reported as less sensitive to the duality gap than the KKT or earlier rule.

  • Synthetic data: Figure 6 compares six thresholding rules on synthetic data across two matrix sizes and duality gaps 10^-4 and 10^-8.Curves show normalized differences in active-feature counts relative to glmnet.
  • Synthetic data: For α ∈ (2, 5), the proposed rule is less sensitive to the IPM-LASSO duality gap than Koh et al.’s rule.This comparison is based on normalized active-feature-count differences from glmnet.
  • NYT data: Figure 7 compares KKT with four proposed rules on NYT headlines for the topic China in 1985.The panels use duality gaps 10^-4 and 10^-8, with the reference active-feature count obtained from KKT at 10^-10.
  • NYT data: At λ = λmax/1000, KKT returned 1758 active features at duality gap 10^-4 and 2357 at 10^-8.The example illustrates sensitivity of the KKT active-feature count to the duality gap.
  • NYT data: On the NYT data, the proposed rule significantly improved upon KKT when the duality gap was 10^-4.The proposed rule slightly underestimated the true active-feature count at the lowest λ values in this high-dimensional setting.
Loading 1009.4219v2…