PaperlayerView exact revision on arXiv

Source-linked AI summary

Lasso Screening Rules via Dual Polytope Projection

Jie Wang, Peter Wonka, Jieping Ye

arXiv:1211.3966v3cs.LGstat.ML

TL;DR

Large-scale Lasso is challenging because high-dimensional data can exceed available memory, creating a need for efficient screening. The paper proposes DPP and enhanced DPP rules based on dual projection geometry, extends them to group Lasso, and reports stronger inactive-feature identification than existing state-of-the-art Lasso rules.

  • Problem

    Solving Lasso remains challenging at very large feature and sample scales because the data matrix may not fit in main memory.

  • Method

    The paper develops DPP screening rules using projection properties of the dual feasible polytope, with sequential and enhanced variants and an extension to inactive groups in group Lasso.

  • Results

    Experiments on synthetic and real data demonstrate effective inactive-feature screening, with enhanced DPP reported as more effective than existing state-of-the-art rules.

  • Takeaways & Limitations

    DPP rules can reduce the size of Lasso optimization problems, and enhanced DPP can substantially improve solver efficiency on high-dimensional data.

  • Takeaways & Limitations

    The paper focuses on cases with λ ∈(0, λmax).

Abstract

from arXiv · show

Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve the efficiency of solving large-scale Lasso problems, El Ghaoui and his colleagues have proposed the SAFE rules which are able to quickly identify the inactive predictors, i.e., predictors that have $0$ components in the solution vector. Then, the inactive predictors or features can be removed from the optimization problem to reduce its scale. By transforming the standard Lasso to its dual form, it can be shown that the inactive predictors include the set of inactive constraints on the optimal dual solution. In this paper, we propose an efficient and effective screening rule via Dual Polytope Projections (DPP), which is mainly based on the uniqueness and nonexpansiveness of the optimal dual solution due to the fact that the feasible set in the dual space is a convex and closed polytope. Moreover, we show that our screening rule can be extended to identify inactive groups in group Lasso. To the best of our knowledge, there is currently no "exact" screening rule for group Lasso. We have evaluated our screening rule using synthetic and real data sets. Results show that our rule is more effective in identifying inactive predictors than existing state-of-the-art screening rules for Lasso.

1 Introduction

Large-scale Lasso remains difficult because data may not fit in memory, motivating screening methods that safely remove inactive features. The paper develops geometry-based DPP rules, sequential variants, and enhanced rules evaluated against existing approaches.

  • Motivation: Large feature and sample dimensions can make Lasso difficult to solve because the data matrix may not fit in main memory.
  • Motivation: Screening identifies features with zero solution coefficients and removes them, reducing computational cost and memory usage.
  • Existing and proposed screening: Heuristic screening may mistakenly discard active features, whereas the paper's DPP rules are designed to guarantee that active features are retained.
  • Existing and proposed screening: DPP estimates the dual optimum through projection geometry, while enhanced DPP improves this estimate to detect more inactive features.
  • Sequential screening: Sequential DPP rules address tuning-parameter selection by screening across a grid of decreasing λ values using a previously computed solution.
  • Evaluation: Experiments on synthetic and real data report that the rules discard inactive features more effectively than existing state-of-the-art methods and can yield several-orders-of-magnitude solver speedups.

2 Screening Rules for Lasso via Dual Polytope Projections

The paper develops safe Lasso screening rules by projecting the scaled response onto the dual feasible polytope and using increasingly accurate regions containing the dual optimum. The enhanced DPP rule combines two improvements, yielding stronger feature rejection and substantial computational speedups.

  • Dual geometric basis: A region containing the dual optimum yields a safe rule: if the region satisfies the relaxed dual constraint test, the corresponding feature is discarded.Smaller regions provide more accurate dual estimates and can identify more inactive features.
  • Dual geometric basis: The dual optimum is the projection of y/λ onto a nonempty closed, convex polytope, enabling projection-based safe screening.The KKT conditions imply that a feature is inactive when its dual constraint is strictly inactive.
  • DPP and its improvements: EDPP combines both improvements and uses the smallest estimation ball, making it more effective at discarding inactive features than DPP, Improvement 1, and Improvement 2.The paper also gives basic and sequential forms, using a known solution at λ0 to screen features at smaller λ values.
  • Empirical evaluation: For three real data sets, EDPP rejection ratios are very close to 100% for most parameter values and produce about 150× and 230× speedups on PIE and MNIST.On MNIST, solving 100 problems took 2566.26 seconds without screening versus 11.12 seconds with EDPP; screening overhead was negligible.

3 Extensions to Group Lasso

The paper extends DPP screening from Lasso to group Lasso by exploiting the projection structure of its dual problem. It develops sequential and enhanced rules that identify inactive groups using regions containing the unknown dual optimum.

  • Basic group screening rule: Because the exact dual optimum is unknown, screening estimates a region Θ containing it and maximizes the group correlation over that region.A smaller Θ yields a more accurate dual estimate and a more effective screening rule.
  • Dual formulation and geometry: The group Lasso dual optimum is the projection of y/λ onto a nonempty closed convex feasible set.Unlike the Lasso feasible set, this set is an intersection of ellipsoids rather than a polytope.
  • Parameter range: For group Lasso, λmax is the smallest parameter value whose optimal solution is zero, and subsequent analysis restricts λ to (0, λmax).This parameter also initializes the sequential screening sequence.
  • Sequential DPP rules: Projection-operator properties provide estimates of the group Lasso dual optimum from a known solution at a reference parameter λ0.Theorem 19 gives an estimate for λ ∈ (0, λ0] based on the known dual solution at λ0.
  • Sequential DPP rules: The sequential construction applies along λmax = λ0 > λ1 > . . . > λK, using the solution at one parameter to screen groups at the next.Theorem 20 and Corollary 21 provide the enhanced DPP rule for discarding inactive groups.

4 Experiments

Experiments on synthetic and real data evaluate EDPP against SAFE, DOME, and strong rules using rejection ratios, speedup, and solver running time. EDPP generally discards inactive features effectively while retaining safety, with especially large speedups on large problems.

  • Basic versions: EDPP significantly outperforms SAFE, DOME, and strong rule on five of six real data sets; EDPP and DOME perform similarly on PIE.On PIE, both EDPP and DOME significantly outperform SAFE and strong rule.
  • Synthetic data sets: Strong rule and EDPP have comparable rejection ratios on Synthetic 1, and both discard more inactive features than SAFE.EDPP provides better speedup because strong rule requires KKT checking to correct possible false discards.
  • Synthetic data sets: EDPP remains robust across variations in intrinsic data structure and ground-truth sparsity on the two synthetic data sets.Synthetic 2 exhibits patterns similar to Synthetic 1.
  • Sequential versions: EDPP and strong rule achieve comparable rejection ratios and higher speedups than SAFE on six real data sets.EDPP’s safety avoids the KKT checks required by strong rule, producing higher speedup.
  • Sequential versions: EDPP speedup reaches about 10, 17, and 30 times on small data sets, versus two orders of magnitude on PIE, MNIST, and SVHN.For SVHN, solving 100 Lasso problems falls from about 3 hours without screening to less than 1 minute with EDPP.
  • Group Lasso: For group Lasso, EDPP discards more inactive groups and is more robust than strong rule as the number of groups increases.With 10,000, 20,000, and 40,000 groups, EDPP improves solver efficiency by about 80, 120, and 160 times, respectively.

5 Conclusion

The paper develops DPP screening rules for Lasso using projection properties, extends them to group Lasso, and reports effectiveness on synthetic and real data.

  • DPP screening rules use projection operators onto closed convex sets to identify inactive Lasso predictors.The enhanced DPP rule is reported as more effective than the basic DPP rule at discarding inactive features.
  • The DPP framework can identify inactive groups in group Lasso.The authors state that this generalization addresses a setting where they are unaware of an exact screening rule.
  • Synthetic and real-data experiments demonstrate the effectiveness of the proposed screening rules.The rules can be combined with any Lasso solver as a speedup tool.

Appendix A.

The appendix provides a detailed derivation of the Lasso dual problem.

  • Appendix A derives the dual problem of Lasso in detail.
  • The appendix focuses specifically on the dual formulation of Lasso.
  • The derivation supplies background for the paper’s dual-based analysis.

A1. Dual Formulation

The appendix derives Lasso’s dual formulation by introducing residual variables, forming a Lagrangian, and optimizing over the primal variables before rescaling the dual variables.

  • The standard Lasso problem is posed with data matrix X ∈ R^N×p.
  • Introducing z = y − Xβ converts the unconstrained formulation into an equivalent constrained problem.
  • Dual variables η ∈ R^N are introduced to form the Lagrangian and dual function.
  • The dual function is obtained by separately minimizing over the primal variables β and z.
  • The nonsmooth ℓ1 term is handled through a subgradient v satisfying ∥v∥∞ ≤ 1 and v^Tβ = ∥β∥1.
  • The resulting dual problem is obtained by combining the optimized components and rescaling η to θ.

A2. The KKT Conditions

The KKT analysis uses convexity, affine constraints, and strong duality to characterize optimal primal and dual variables through subgradient conditions.

  • Convexity and affine constraints allow strong duality under Slater’s condition when the constrained problem is feasible.
  • At optimality, the Lagrangian’s subgradient with respect to β must contain zero.
  • The subgradient representation uses v with ∥v∥∞ ≤ 1 and v^Tβ* = ∥β*∥1.
  • The KKT relations imply |θ_i*| ≤ 1 for every feature index i.
  • They also imply (θ*)^T Xβ* = ∥β*∥1.

Appendix B.

Appendix B presents a detailed derivation of the group Lasso dual problem.

  • Appendix B contains the detailed derivation of the group Lasso dual problem.
  • The derivation focuses on the dual problem for group Lasso.
  • This appendix develops the dual formulation rather than introducing a new optimization objective.

B1. Dual Formulation

This section derives the group Lasso dual formulation by introducing Lagrange variables, separating group-wise subproblems, and rescaling the resulting dual variables.

  • Dual-variable construction: The derivation introduces dual variables η ∈ R^N and forms the Lagrangian and dual function.
  • Group-wise minimization: Group-wise minimization uses the convex, nonsmooth objective −η^T X_g β_g + λ√n_g∥β_g∥_2 and its subgradient.
  • Group-wise minimization: Because the β_g variables are independent, the optimization separates into a set of group subproblems.
  • Dual formulation: The derivation bounds the subgradient norm and obtains a constraint on η before stating the group Lasso dual formulation.
  • Dual formulation: A simple rescaling, θ = η/λ, transforms the dual problem into an equivalent formulation.

B2. The KKT Conditions

This section uses convexity, Slater’s condition, and KKT conditions to characterize optimal primal and dual variables for the group Lasso formulation.

  • Strong duality: The primal problem is convex with affine constraints, so feasibility together with Slater’s condition yields strong duality.
  • KKT conditions: The KKT stationarity condition relates each group’s dual design term to a subgradient of the group norm.
  • KKT conditions: The subsequent relations derive consequences from the KKT equations and establish group-wise conditions involving X_g^T θ*.
Loading 1211.3966v3…