PaperlayerView exact revision on arXiv

Source-linked AI summary

Screening Tests for Lasso Problems

Zhen James Xiang, Yun Wang, Peter J. Ramadge

arXiv:1405.4897v2cs.LGstat.ML

TL;DR

Large or high-dimensional lasso problems can be computationally burdensome. This survey develops a geometric framework for understanding dictionary screening and reviews its methods and trade-offs. It reports benefits from more complex and sequential screening, while noting that the exact active-set partition is impractical to obtain.

  • Problem

    Large dictionaries, high-dimensional data, and repeated dictionary iterations can make solving lasso problems a computational bottleneck.

    Source: §1 · p. 1

  • Method

    The survey uses a geometric framework to explain lasso screening tests, their architectures and parameter choices, and trade-offs among test complexity, rejection, and computation.

    Source: §1 · p. 2

  • Results

    More complex region tests improve rejection and speedup over simpler tests across important λ/λmax ranges, while sequential screening extends useful performance to a wider range.

    Source: §8 · p. 17

  • Takeaways & Limitations

    Online sequential screening can reduce large dictionaries to a manageable size and may enable solving lasso problems that would otherwise exceed constrained computational resources.

    Source: §8 · p. 17

    The exact active-set partition is impractical because knowing the dual solution would make screening and problem reduction unnecessary.

    Source: §3 · p. 4

Abstract

from arXiv · show

This paper is a survey of dictionary screening for the lasso problem. The lasso problem seeks a sparse linear combination of the columns of a dictionary to best match a given target vector. This sparse representation has proven useful in a variety of subsequent processing and decision tasks. For a given target vector, dictionary screening quickly identifies a subset of dictionary columns that will receive zero weight in a solution of the corresponding lasso problem. These columns can be removed from the dictionary prior to solving the lasso problem without impacting the optimality of the solution obtained. This has two potential advantages: it reduces the size of the dictionary, allowing the lasso problem to be solved with less resources, and it may speed up obtaining a solution. Using a geometrically intuitive framework, we provide basic insights for understanding useful lasso screening tests and their limitations. We also provide illustrative numerical studies on several datasets.

1 INTRODUCTION

The lasso supports sparse representations but can become a computational bottleneck with large dictionaries, high-dimensional data, or repeated dictionary iterations. The survey presents a geometric framework for understanding screening tests and reviews their trade-offs, composite forms, and sequential use.

1 INTRODUCTION

  • Large dictionaries, high-dimensional data, and repeated dictionary iterations can make solving the lasso a computational bottleneck.Source: §1 · p. 1
  • Dictionary screening guarantees that identified features receive zero weight, so they can be removed before solving a smaller lasso problem without changing the solution.Screening is computed for a given target vector and regularization parameter.Source: §1 · p. 1
  • Screening may reduce dictionary memory needs and solution time, and it can be used with existing lasso solvers.The paper notes that even small speed gains can matter when many lasso problems must be solved.Source: §1 · p. 1
  • The survey's geometric framework unifies lasso screening tests and separates a test's architecture from the choice of its parameters.Source: §1 · p. 2
  • More half-space constraints can increase rejection but also execution time; the survey derives a sphere-plus-two-half-spaces test to examine that trade-off.Source: §1 · p. 2
  • The survey also reviews sequential screening and composite tests, including carefully selected dome regions, and reports that online sequential use can reduce large dictionaries to manageable size and speed overall computation.It identifies a fundamental limitation of the composite approach but does not specify it in this passage.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries frame lasso screening through the dual problem's feasible geometry and the relationship between primal and dual solutions. They also establish scaling conventions and notation used to describe the problem and its solutions.

2 PRELIMINARIES

  • The dictionary has nonzero feature columns, and each problem instance is specified by a target vector and regularization parameter.A dictionary is normalized when its features have unit norm.Source: §2 · p. 2
  • The paper uses λ/λmax as a scale-invariant measure of regularization because solver scaling can change the numerical value of λ.λmax is defined using the largest absolute feature-target correlation.Source: §2 · p. 3
  • The dual feasible set is an intersection of half-spaces; for the lasso it is symmetric about the origin.Source: §2 · p. 3
  • The dual solution is the projection of y/λ onto the feasible set, while the primal lasso solution may not be unique.Source: §2 · p. 3
  • When λ is at least λmax, the zero vector is a primal solution; below λmax, the dual solution lies on the feasible-set boundary and the primal solution is nonzero.Source: §2 · p. 3
  • The paper's notation distinguishes subsetting a vector or dictionary to selected indices from upsampling a vector with zeros at all other indices.Source: §2 · p. 3

3 SCREENING

Screening partitions features into selected and rejected sets, aiming to retain a reduced dictionary whose solution extends to an optimal solution of the original problem. The exact active-set partition establishes this guarantee but is impractical because it requires knowing the dual solution.

3 SCREENING

  • In general, solving the reduced problem and upsampling its solution does not guarantee an original-problem solution unless the selected set meets the screening condition.Source: §3 · pp. 3–4
  • Screening is evaluated by rejection fraction and by speedup that accounts for both screening time and reduced-problem solving time.Source: §3 · p. 4
  • The exact active-set partition is impractical: knowing the dual solution would already make solving the primal problem straightforward, removing the need for screening.Source: §3 · p. 4
  • If the selected set contains the dual solution's active set, solving the reduced problem and upsampling its solution yields a solution of the original problem.Every original solution can be represented this way.Source: §3 · p. 4

4 REGION TESTS

The section surveys region-based lasso screening tests that bound the optimal dual vector and reject dictionary features using those bounds. It covers sphere, dome, two-halfspace, two-hyperplane, and composite dome tests, including bound selection and refinement and trade-offs between screening power and computational cost.

4 REGION TESTS

  • A compact region containing the optimal dual vector induces a safe dictionary partition; adding halfspaces can increase rejection potential but also makes tests more complex and time-consuming.For the nonnegative lasso, the test uses the upper inner-product bound; for the lasso, it must account for both signs of each feature.Source: §4 · p. 5, §4.1 · p. 5

4.2 Sphere Tests

  • A sphere bound gives a simple, efficient screening test and serves as a building block for more complex region tests.A dual feasible point yields the default sphere centered at y/λ with radius ∥θF − y/λ∥2.Source: §4.2 · p. 5, §4.2.1 · p. 6

4.2.1 Parameter selection

  • Choosing a sphere’s center and radius trades the computation needed to obtain a tighter bound against its potential for better screening.The paper describes using additional homotopy steps or a previously solved instance to obtain alternative bounds.Source: §4.2 · pp. 5–6, §4.2.1 · p. 6

4.2.2 Connections with the Literature

  • Several existing rules can be expressed as sphere tests, but the Strong Rule’s smaller-than-safe sphere can cause false rejections, and SIS corresponds to a default sphere test for a selected lasso parameter.The paper also identifies SAFE-LASSO, ST1–ST3, and a test based on a previously solved instance as sphere tests [22].Source: §4.2.2 · p. 6

4.3 Sphere Plus Halfspace Tests

  • A dome intersects a sphere with one halfspace and can reject additional features beyond its underlying sphere test.For unit-norm features, the test uses their inner products with the sphere center and halfspace normal; increasing alignment with the normal lowers the rejection threshold for a fixed positive center inner product.Source: §4.3 · pp. 6–7

4.3.1 Parameter selection

  • A dual-feasible halfspace can be combined with a sphere to form a dome, and prior SAFE-LASSO work uses a dome bound for screening instances along the regularization path [32].The paper also relates a default dome bound to a feature most correlated with the sphere center when features have unit norm.Source: §4.3.1 · pp. 7–8, §4.3.2 · p. 8

4.4 Iteratively Refined Bounds

  • When a bounding halfspace cuts off the sphere center, the dome’s circumsphere is strictly smaller than the original sphere and can iteratively tighten the bound.A greedy refinement chooses a feature to minimize the next sphere’s radius; for equal-norm features, this maximizes alignment with the current center estimate.Source: §4.4 · pp. 8–9

4.5 Are More Half Spaces Worthwhile?

  • The section defines a Two Hyperplane Test by intersecting a sphere with two halfspaces to assess whether added screening power justifies added computational effort.The excerpt specifies conditions for a nonempty, proper intersection and states that the associated maximization can be solved in closed form; it does not provide comparative results here.Source: §4.5 · p. 9
  • The Two Hyperplane Test uses three correlations per feature and has O(pn) time complexity.Its general test bounds the dual solution using a sphere and two hyperplane constraints.Source: §4.5 · p. 9

4.5.1 Parameter selection

  • D-THT selects the first feature to minimize dome radius, then repeats the construction on the resulting bounding sphere to select a second.When all features have equal norm, the selections maximize b^T q and then b^T q(1) over features not already selected.Source: §4.5.1 · pp. 9–10

4.5.2 Connections with the Literature

  • The proved THT generalizes the earlier unit-norm formulation in to arbitrary sphere and hyperplane bounds, including the feature constraint in.Source: §4.5.2 · p. 10

4.6 Composite Tests

  • IRDT is very competitive with Dictionary-based THT on the datasets in the numerical studies.A disjunction of region tests trades rejection performance for simplicity and ease of implementation; the marginal cost of increasing the number of iterative domes by one is one additional inner product per feature tested.Source: §4.6 · p. 10

4.6.1 Connections with the Literature

  • Prior methods include the unit-norm spherical refinement ST3 in and a sequential two-term disjunction using ellipsoidal bounds in.Ellipsoids can provide tighter bounds than spheres, but require a center and a shape-and-orientation matrix, which may impede use when the feature dimension is large.Source: §4.6.1 · pp. 10–11

5 SEQUENTIAL SCREENING

Sequential screening uses solutions from earlier lasso instances to screen later ones. Data-Adaptive Sequential Screening (DASS) adds feedback to choose the sequence and its stopping point, controlling how tightly each dome bounds the dual solution.

5 SEQUENTIAL SCREENING

  • One-shot tests can perform poorly at small λ/λmax because obtaining a tight bound on the dual solution is challenging.They often perform well at moderate to large λ/λmax.Source: §5 · p. 11
  • Earlier dual solutions can bound the next instance’s dual solution, enabling sequential screening along descending regularization values.Recursive-SAFE uses this approach; other schemes use fixed open-loop choices of N and the λ sequence.Source: §5 · p. 11
  • Homotopy can use a breakpoint solution to screen a later instance, but its breakpoints may number O(3^p) in the worst case.This approach also relinquishes control of the intermediate λ values to the homotopy breakpoints.Source: §5 · p. 11
  • A previous instance’s dual solution defines a sphere and half-space whose intersection forms a dome bounding the next instance’s dual solution.The dome encapsulates information about the next dual solution supplied by the previous instance.Source: §5 · p. 11, Figure 4 · p. 11
  • DASS uses feedback to select λ values and stop without a predetermined N, while a selectable R ensures each later dome has diameter at most R.This provides direct control over how tightly the dome bounds the dual solution.Source: §5 · p. 11

6 ALGORITHMS

The algorithms implement region tests and sequential screening using dictionary passes and dual-solution information. THT and IRDT provide one-shot screening options, while DASS repeatedly screens and solves instances with feedback-selected regularization values.

6 ALGORITHMS

  • For sparse features with average sparsity s, one-shot screening has time complexity O(sp), compared with O(np) for general features.The critical computations are inner products involving y and the features, and the screening algorithms can operate online with few features stored at once.Source: §6 · p. 12
  • THT accepts an optional dual solution or feasible point, using the dual solution to select its first half-space and the feasible point to select its sphere radius.The remaining half-spaces use dictionary-based selection; the algorithm returns a rejection decision for each feature.Source: §6 · p. 12
  • IRDT applies a disjunction of dome tests sequentially, testing later domes only on features that survive earlier tests.It uses at most s iterations and passes through the dictionary at most s + 1 times, with early termination possible.Source: §6 · p. 13
  • DASS starts at λ1 = 0.95λmax, then uses feedback to select descending λ values until reaching the target λt, screening and solving at each step.The sequence length N is determined by the feedback rule, and an external lasso solver handles each screened instance.Source: §6 · p. 13

7 NUMERICAL EXAMPLES

The experiments compare one-shot and sequential screening across several datasets, solvers, and lasso settings. Sequential screening performs strongly at low regularization values and in classification tasks, while one-shot performance weakens there; DASS also reduces the memory footprint on a very large dataset.

7 NUMERICAL EXAMPLES

  • The experiments used Feature-sign and FISTA, measuring rejection percentage and speedup across seven datasets, with results averaged over 1,200 instances for most datasets.RCV1 used 496 instances and NYT used six targets; Table 1 summarizes the datasets and reports λmax averaged over solved instances.Source: §7 · pp. 13–14, Table 1 · p. 13

7.1 The performance of one-shot screening

  • One-shot tests weakened as λ/λmax fell, becoming ineffective around 0.2 and below; D-THT generally led rejection, while better spherical bounds showed room for improvement.On RAND at λ/λmax = 0.5, D-THT gave a 400% rejection improvement over DT, with about 5X speedup versus less than 2X for DT.Source: Figure 8 · p. 14, Figure 9 · p. 14, §7.1 · p. 15

7.2 The performance of sequential screening

  • At λ/λmax around 0.1 or lower, DASS rejected 98% of the dictionary while maintaining speedup greater than 1 on MNIST and YALEBXF.With R = 0.2, performance was robust across tested λt values.Source: Figure 10 · p. 15, §7.2 · p. 15

7.3 Sequential screening and classification

  • Over 50% of dataset-method experiments achieved at least 10X speedup; DASS reached 28X, 16X, and 18X on COIL, GTZAN, and RCV1, respectively.Those DASS results average 21X; with only three datasets and no per-method tuning, the authors cannot conclude that one method is always better.Source: Figure 11 · p. 16, §7.3 · p. 16
  • For SRC, the authors selected λt/λmax by cross-validation and matched average path lengths across DASS and three open-loop schemes on COIL, GTZAN, and RCV1.The selected ratios were 0.15, 0.1, and 0.2, respectively; the open-loop step counts were 5, 15, and 4.Source: §7.3 · p. 16

7.4 Sequential screening on a large dataset

  • On NYT, DASS held fewer than 1,000 features (0.33%) in memory at once, versus fewer than 10,000 (3.3%) under fixed geometric spacing.The usual speedup metric could not be evaluated because these lasso problems could not be solved without screening; DASS automatically selected N and the λ steps.Source: §7.4 · p. 16

8 DISCUSSION AND CONCLUSION

The survey separates screening-test structure from parameter selection to clarify connections among tests and support development of new tests. Its studies find benefits from more complex one-shot tests and sequential screening, including DASS, while identifying memory-constrained large dictionaries as an important use case.

8 DISCUSSION AND CONCLUSION

  • The survey distinguishes test architecture from parameter selection, unifying many existing tests and clarifying screening more generally.The authors hope this separation will help develop new tests and parameter-selection methods.Source: §8 · pp. 16–17
  • More complex THT region tests improved rejection and speedup over simpler tests across important λ/λmax ranges, though one-shot performance remained inadequate at small values.The default spherical bound also lagged the best bound at the same center, indicating value in additional computation to improve the bound.Source: §8 · p. 17
  • Sequential screening such as DASS extended useful screening performance across a wider range of λ/λmax values and selected both N and the sequence {λk}N.The NYT figure plots surviving feature counts after THT screening for six problems, comparing open-loop geometric spacing with DASS at R = 0.3.Source: §8 · p. 17, Figure 12 · p. 17
  • DASS was demonstrated on an NYT dictionary of dimension 102,660 by 299,000; the authors say screening is, to their knowledge, the only way to solve problems this size with constrained resources.Screening is critical when the dictionary will not fit in available memory.Source: §8 · p. 17
  • The surveyed concepts provide a foundation for screening beyond lasso, with examples including elastic net, logistic regression, graphical and group lasso, generalized sparse models, and other applications.The discussion also names Boolean compressed sensing, nuclear-norm regularized least squares, sparse representation classification, and music genre tagging.Source: §8 · p. 17

APPENDIX A PROOFS §2

The proof derives the lasso dual by introducing a residual constraint, applying subdifferential optimality conditions, and eliminating primal variables.

APPENDIX A PROOFS §2

  • Introducing z = y − Bw rewrites the lasso as a constrained problem, with z linked to the target and coefficient vector.The Lagrangian adds multiplier µ to the constraint y−Bw−z = 0.Source: Appendix A · p. 17
  • Subdifferential conditions yield µ = ẑ and the dual constraints |µT bi| ≤ λ for each dictionary feature.These conditions permit eliminating z and w from the Lagrangian.Source: Appendix A · p. 17
  • Eliminating the primal variables gives the dual objective, and scaling θ = µ/λ yields problem (3), with primal and dual solutions related by (4).Source: Appendix A · p. 17

APPENDIX B PROOFS §3

The appendix notes that the lasso theorem’s proof is already given and that the nn-lasso changes only the active-set definition; its corollary follows from an inclusion in the proof.

APPENDIX B PROOFS §3

  • The lasso proof appears before Theorem 1, while the nn-lasso proof requires only changing the active-set definition.Source: Appendix B · p. 17
  • The appendix directs readers to the preceding proof for both Theorem 1 and Corollary 1 rather than reproducing their arguments here.Source: Appendix B · p. 17
  • Corollary 1 follows because the proof establishes that i ∈ ¯S implies ẇi = 0.The stated inclusion is ¯S ⊆ ¯A(ˆθ).Source: Appendix B · p. 17

APPENDIX C PROOFS §4

The appendix proves that a screening region contained in another region rejects at least the features rejected by the larger region.

APPENDIX C PROOFS §4

  • Corollary 2 is proved above the corollary, and Lemma 1 supplies the region-containment argument.Source: Appendix C · pp. 17–18
  • If R1 ⊆ R2, then µR1(b) ≤ µR2(b), so any feature rejected using R2 is also rejected using R1.For lasso rejection, the inequalities apply to both bi and −bi.Source: Appendix C · p. 18
  • The nested-region result establishes the ordering TR2 ⪯ TR1, with the nn-lasso proof described as similar.The proof treats the empty R1 case separately before considering a nonempty region.Source: Appendix C · p. 18

APPENDIX D PROOFS §4.2

The proofs bound each dictionary column’s score over a ball and use that bound to derive screening conditions. For the lasso, the condition is symmetric in the column and its negation.

APPENDIX D PROOFS §4.2

  • Cauchy–Schwarz bounds θ^T b over S(q, r) by r∥b∥2 + q^T b, with equality when θ − q is aligned with b and lies at distance r.This gives the maximum score over the ball.Source: Appendix D · p. 18
  • For the nn-lasso, reject b_i when q^T b_i < 1 − r∥b_i∥2.Source: Appendix D · p. 18
  • For the lasso, reject b_i when |q^T b_i| < 1 − r∥b_i∥2, equivalent to both signed-column tests being below 1.Source: Appendix D · p. 18

APPENDIX E PROOFS §4.3

The proof reduces the m = 1 problem to a Lagrangian optimization and derives screening thresholds from its solution. The resulting tests use a score bound that depends on the column’s projection onto n and its norm.

APPENDIX E PROOFS §4.3

  • Solving (16) with m = 1 is equivalent to solving the Lagrangian problem, whose optimization yields the bound used in the screening test.The proof sets the derivative with respect to θ to zero and minimizes over nonnegative multipliers.Source: Appendix E · p. 18
  • For the nn-lasso, reject b when q^T b < Vu(n^T b, ∥b∥2), where Vu = 1 − M1(n^T b, ∥b∥2).Source: Appendix E · p. 18
  • For the lasso, reject b when q^T b lies between Vl(n^T b, ∥b∥2) and Vu(n^T b, ∥b∥2), with the bounds defined using M1 at n^T b and −n^T b.Source: Appendix E · p. 18

APPENDIX F PROOFS §4.4

These appendices establish geometric bounds and screening-test properties. They derive a circumsphere for D, solve a two-constraint optimization by cases, and show how intersecting regions relates to combining tests.

APPENDIX F PROOFS §4.4

  • When 0 < ψ_d ≤ 1, equivalent to q ∉ D, the set D has a circumsphere centered at q_d with radius r_d.The proof shows the sphere contains every boundary point and that its diameter is 2r_d.Source: Appendix F · p. 18

APPENDIX G PROOFS §4.5

  • For m = 2, the proof solves the Lagrangian in cases and extends the resulting μ_R(b) expressions to general b by homogeneity.The case conditions depend on t_1, t_2, ψ_1, ψ_2, and τ.Source: Appendix G · pp. 18–19

APPENDIX H PROOFS §4.6

  • If either test rejects b_i using R_1 or R_2, the test using R_1 ∩ R_2 also rejects it; thus the intersection test is at least as strong as either individual test.Source: Appendix H · p. 19
Loading 1405.4897v2…