PaperlayerView exact revision on arXiv

Source-linked AI summary

Gap Safe screening rules for sparsity enforcing penalties

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

arXiv:1611.05780v4stat.MLcs.LGmath.OCstat.CO

TL;DR

High-dimensional regularized regression poses a computational burden, motivating screening rules that exploit expected sparsity. The paper develops Gap Safe rules based on duality gaps, and reports practical speed-ups over previously known safe rules alongside faster variable identification.

  • Problem

    Solving high-dimensional regularized regression problems with sparsity-enforcing penalties carries substantial computational burden.

    Source: §1 · p. 1

  • Method

    Gap Safe screening rules use duality-gap computations to unify sequential and dynamic safe rules for sparsity-regularized learning problems.

    Source: §1 · p. 2

  • Results

    Gap Safe rules improve practical speed-ups over previously known safe rules and identify the equicorrelation set faster.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework is presented as flexible across regression and classification settings and applies to popular sparse estimators.

    Source: §7 · p. 29

    The models omit an intercept for simplicity, though the framework can handle one with more technical details.

    Source: §5.6 · p. 21

Abstract

from arXiv · show

In high dimensional regression settings, sparsity enforcing penalties have proved useful to regularize the data-fitting term. A recently introduced technique called screening rules propose to ignore some variables in the optimization leveraging the expected sparsity of the solutions and consequently leading to faster solvers. When the procedure is guaranteed not to discard variables wrongly the rules are said to be safe. In this work, we propose a unifying framework for generalized linear models regularized with standard sparsity enforcing penalties such as $\ell_1$ or $\ell_1/\ell_2$ norms. Our technique allows to discard safely more variables than previously considered safe rules, particularly for low regularization parameters. Our proposed Gap Safe rules (so called because they rely on duality gap computation) can cope with any iterative solver but are particularly well suited to (block) coordinate descent methods. Applied to many standard learning tasks, Lasso, Sparse-Group Lasso, multi-task Lasso, binary and multinomial logistic regression, etc., we report significant speed-ups compared to previously proposed safe rules on all tested data sets.

1. Introduction

High-dimensional regularized regression creates computational challenges, and coordinate descent is an efficient strategy for many general formulations. The paper introduces Gap Safe screening rules and reports improved speed-ups over previously known safe rules.

1. Introduction

  • Gap Safe screening can be inserted into existing solvers and is particularly suited to coordinate descent, which can ignore screened coordinates.The stated objective is to speed up any iterative solver for these learning problems.Source: §1 · p. 2
  • Strong rules can discard relevant features and require post-processing, while sequential safe rules rely on an exact prior dual optimum that practitioners typically cannot obtain.The paper notes that using an approximate prior dual solution can wrongly eliminate variables.Source: §1 · p. 2
  • The rules are proved safe and unify sequential and dynamic screening strategies, relying on duality-gap computations.The paper presents them as a synthesis of earlier methods for Lasso, ℓ1/ℓ2 norms, and Sparse-Group Lasso.Source: §1 · p. 2
  • Gap Safe rules improve practical speed-ups over previously known safe rules and identify the equicorrelation set faster.The authors specify that the faster identification concerns the equicorrelation set (Theorem 14).Source: §1 · p. 2
  • The work situates dual-gap methods among earlier applications to feature-and-sample screening, constrained convex problems, and working-set methods.Its experiments span four learning problems with dense or sparse data and report systematic computation-time gains.Source: §1 · p. 3

2. Notation and Background on Optimization

This section establishes notation for the data, feature groups, and norms used in the paper. It also recalls convex-analysis concepts used in the following sections.

2. Notation and Background on Optimization

  • The data are represented by an observation vector y and a design matrix X, with features arranged in groups that partition the feature indices.The notation distinguishes each group’s restricted coefficient vector and corresponding submatrix of X.Source: §2 · p. 3
  • The background defines the Fenchel-Legendre transform and the dual norm, and notes that a group-decomposable norm’s dual is expressed through its group dual norms.The conjugate is defined by maximizing the inner product minus the original function; the dual norm maximizes the inner product over the unit ball.Source: §2 · pp. 3–4
  • The section recalls the subdifferential of a norm, Fermat’s rule for convex minimization, and the soft-thresholding operator.Soft-thresholding is defined coordinatewise at a nonnegative level τ.Source: §2 · pp. 3–4

3. Gap Safe Framework

The framework covers convex learning problems with differentiable losses and group-decomposable sparsity penalties. It constructs safe regions from dual-feasible points and the duality gap, then uses them to screen variables and accelerate a pathwise solver.

3.1 Safe Screening Rules

  • Safe screening removes a group only when the optimal coefficient is guaranteed to be zero, while smaller safe regions can permit more groups to be screened.The framework requires safe regions to contain the optimal dual solution and screening tests to be inexpensive.Source: §3.1 · p. 5

3.2 Gap Safe Regions

  • Sphere regions bound the optimal dual solution and enable group screening through a test on the dual norm over the region.The framework uses a ball as a simple geometric safe region.Source: §3.2 · p. 6

3.2.1 Finding a Center

  • Rescaling the generalized residual −G(Xβ)/λ produces a dual-feasible center candidate for a safe sphere.The rescaling guarantees that the resulting point belongs to the dual feasible set.Source: §3.2.1 · p. 6

3.2.2 Finding a Radius

  • The duality gap supplies a safe sphere radius when the loss has a Lipschitz gradient, and the framework requires dual strong convexity plus group-separable norms.A primal-dual pair with a sufficiently small gap also certifies an ε-accurate primal solution.Source: §3.2.2 · pp. 6–7

3.2.3 Safe Active Set

  • Evaluating the dual gap over the safe active set costs O(nq), where q is its size, so screening also reduces stopping-criterion computation.The safe active set contains variables not yet eliminated by the associated safe rule.Source: §3.2.3 · pp. 7–8

3.3 Outline of the Algorithm

  • The pathwise algorithm combines an active warm start based on support estimates with dynamic Gap Safe screening that tightens regions during optimization.It uses a numerical solver that can accept a primal warm start.Source: §3.3 · p. 8

4. Screening strategies and theoretical analysis

This section presents static safe screening before optimization and a pathwise solver procedure. The static sphere rule has a regularization threshold below which its screening test cannot succeed.

4.1 Static Safe Rules

  • The static safe rule screens variables before computation using a sphere fixed in advance.The rule was introduced by El Ghaoui et al. (2012).Source: §4.1 · pp. 8–9

4. Screening strategies and theoretical analysis

  • The solver procedure computes a dual variable and duality gap periodically, then updates the solution on the current safe active set.The experiments focus on (block) coordinate descent solvers.Source: §4.1 · pp. 8–9

4.1 Static Safe Rules

  • Below a threshold λcritic, the static sphere test can never be satisfied.The threshold can have a closed form in simple cases, including a stated Group Lasso example.Source: §4.1 · p. 9

4.2 Sequential Safe Rules

Sequential screening reuses information from a previous regularization parameter to initialize and screen the next problem. Using an approximate previous dual optimum as though it were exact can make the screening unsafe.

4.2 Sequential Safe Rules

  • Warm starts use the previous approximate primal solution to initialize optimization at the next regularization parameter.This is described as a popular strategy in the literature.Source: §4.2 · p. 9
  • Sequential screening can also reuse prior dual information when screening at a new regularization parameter.The method is motivated for computing solutions along a regularization path.Source: §4.2 · p. 10
  • Treating an approximate previous dual optimum as exact can wrongly discard true-support variables and prevent convergence without a posteriori checks.The exact previous optimum is unavailable from an iterative solver, except at λ0 = λmax.Source: §4.2 · p. 10

4.3 Dynamic Safe Rules

Dynamic safe screening applies tests during optimization, using a current dual-feasible point to refine the safe region. Gap Safe regions converge to the optimal dual solution, though computing the duality gap can be costly.

4.3 Dynamic Safe Rules

  • Dynamic screening applies a safe-sphere rule during optimization using the current dual-feasible point and its distance from the Lasso center.The dynamic rule described by Bonnefoy et al. (2014, 2015) uses center y/λ and radius ∥y/λ − θk∥.Source: §4.3 · p. 10
  • Duality-gap computation can cost nearly a full coordinate-descent pass, so the rule is evaluated only every few passes in practice.The experiments set the screening frequency parameter to 10.Source: §4.3 · p. 10
  • Unlike Bonnefoy et al. (2014, 2015), Gap Safe regions converge to the singleton optimal dual solution.The comparison is illustrated in Figure 1.Source: §4.3 · p. 10, Figure 1 · p. 11

4.4 Active Warm Start

Active warm starts use the previous safe active set to constrain a new approximate primal solution. The method retains a standard warm-start initialization and can also use an unsafe strong active set.

4.4 Active Warm Start

  • The active warm start uses the previous safe active set as a support constraint when finding an approximate minimizer for the next regularization parameter.The constrained minimizer of P_λt becomes the new primal warm start point.Source: §4.4 · p. 11
  • The strategy retains the previous primal solution as a standard initialization, with the same inner-loop count or accuracy as before.This avoids adding more parameters for users to set.Source: §4.4 · p. 11
  • An unsafe strong active set can replace the safe set in practice, using the Strong rules for the active warm start.This is the strong warm start strategy.Source: §4.4 · p. 11

4.5 Theoretical Analysis

When primal estimates converge, their associated dual estimates converge as well, and Gap Safe regions shrink toward the optimal dual point. Converging safe regions identify the equicorrelation set in finite time, which can be larger than the optimal support.

4.5 Theoretical Analysis

  • Dynamic Gap Safe screening increases the number of variables screened as iterations proceed by sharpening dual regions and accelerating support identification.The dual sequence also converges to the same dual optimum when the primal solution is non-unique.Source: §4.5 · p. 12
  • A converging primal sequence yields converging dual estimates, and the associated Gap Safe spheres shrink to the optimal dual point as the duality gap vanishes.The sphere radius is defined from the duality gap; this makes the Gap Safe sphere asymptotically optimal.Source: §4.5 · p. 12
  • The optimal support is contained in the equicorrelation set, which is itself contained in the safe active set; the equicorrelation set may strictly exceed the optimal support.Figure 2 illustrates these set inclusions.Source: §4.5 · p. 12, Figure 2 · p. 13
  • Any sequence of safe regions with diameters tending to zero identifies the equicorrelation set E_λ after finitely many iterations.The active set then equals E_λ at every iteration beyond some finite index.Source: §4.5 · pp. 12–13

4.6 Alternative Strategies: a Brief Survey

Section 4.6 surveys alternative screening approaches, from safe regions based on prior solutions or geometric bounds to heuristic Strong rules and correlation-based selection.

4.6.1 The Seminal Safe Regions

  • Earlier safe regions use the optimal dual solution at a prior regularization parameter; in regression, this yields a safe sphere centered using that prior solution.The seminal region contains dual points whose objective is at least the objective at the previous optimum.Source: §4.6.1 · p. 13

4.6.2 ST3 and Dynamic ST3

  • ST3 refines a safe sphere using dual-space geometry, while dynamic ST3 updates its center from the current dual iterate during optimization.The original ST3 uses y/λmax as its center; dynamic ST3 uses θk.Source: §4.6.2 · p. 14

4.6.3 Dual Polytope Projection

  • Projection-based regions require the regression identity θ̂(λ)=ΠΔX(y/λ), limiting their scope, and their radii do not shrink to zero even dynamically.Their fixed center may also be far from θ̂(λ) for small λ, making them unsuitable for dynamic screening.Source: §4.6.3 · p. 14

4.6.4 Strong rules

  • Strong rules screen more aggressively by relaxing safety, but can discard active features and require a posteriori KKT checks.The proposed active or strong warm-start strategy does not require post-processing.Source: §4.6.4 · p. 15

4.6.5 Correlation Based Rule

  • Sure Independence Screening selects variables using feature-response correlations; it is a marginal method that can be recast as a static sphere test in linear regression.Iterative screening has similarities to dynamic sphere safe tests.Source: §4.6.5 · pp. 15–16

5. Gap Safe Rule for Popular Estimators

The paper specializes Gap Safe screening to popular sparse estimators, including regression and classification models. The rules adapt to each penalty’s structure, including two-level screening for Sparse-Group Lasso.

5. Gap Safe Rule for Popular Estimators

  • Gap Safe rules apply to supervised-learning problems with smooth data-fitting terms and separable sparsity-enforcing penalties.The section summarizes the learning tasks addressed by the framework.Source: §5 · p. 16

5.1 Lasso

  • For the Lasso, least-squares fitting is paired with an ℓ1 penalty that enforces feature-level sparsity.The loss is the standard squared-error term.Source: §5.1 · p. 16

5.2 Group Lasso

  • Group Lasso uses the same least-squares fitting term as Lasso but replaces its penalty with a weighted ℓ1/ℓ2 norm to enforce group sparsity.The group weights are positive.Source: §5.2 · pp. 16–17

5.3 Sparse-Group Lasso

  • Sparse-Group Lasso combines feature- and group-level sparsity, and its safe rules can screen both whole groups and individual features within remaining groups.Efficient screening requires geometric bounds and an explicit dual norm formulation.Source: §5.3 · pp. 17–18

Proposition 19 (Safe screening rule for the Sparse-Group Lasso)

  • For Sparse-Group Lasso, safe regions with diameters tending to zero identify the optimal group- and feature-level active sets in finite time.The group- and feature-level active sets are defined separately.Source: Proposition 19 (Safe screening rule… · p. 19

5.4 ℓ1 Regularized Logistic Regression

  • Binary ℓ1-regularized logistic regression is formulated with labels in {0,1}, a logistic loss, and an ℓ1 penalty.The paper uses this label convention to align with its multinomial formulation.Source: §5.4 · pp. 19–20

5.5 ℓ1/ℓ2 Multi-task Regression

  • Multi-task Lasso jointly selects shared features across regression tasks and can be rewritten as a Group Lasso problem.The presented formulation assumes the explanatory variables are shared across tasks, though the framework also applies to non-shared designs.Source: §5.5 · p. 20

5.6 ℓ1/ℓ2 Multinomial Logistic Regression

  • The multinomial ℓ1/ℓ2 logistic model encodes class labels with a one-hot response matrix; the models omit an intercept for simplicity.An intercept can be represented by adding a constant design column, which is then regularized.Source: §5.6 · p. 21

6. Experiments

Across Lasso, binary logistic, multi-task Lasso, and Sparse-Group Lasso experiments, dynamic Gap Safe screening improves runtime or screening performance, with gains varying by task and strategy. The experiments also expose a limitation of strong rules on coarse regularization grids.

6. Experiments

  • The experiments use coordinate descent and compare Gap Safe variants with existing rules, adding approximated KKT post-processing for methods that require a previous exact dual optimum.The comparison includes known safe rules and, for Lasso, Blitz.Source: §6 · p. 22

6.1 ℓ1 Lasso Regression

  • Dynamic Gap Safe is the only compared rule reported to significantly improve Lasso running time; screening improves with more iterations and estimates closer to the minimum.The Leukemia experiment examines screening from 2 to 29 iterations for each λ.Source: Figure 4 · p. 22, §6.1 · pp. 23–24
  • On the coarse 10-value λ grid, strong rules select all variables and become useless; larger gaps between grid points reduce active-warm-start benefits.The grid runs from λmax to λmax/10^3 with 2λt < λt−1.Source: Figure 5 · p. 23, §6.1 · p. 25
  • For financial Lasso with 1,562 active variables, active warm start speeds computation on both coarse and dense grids; Blitz also achieves gains of the same order as dynamic Gap Safe.The benchmark stops at λmax/20.Source: Figure 6 · p. 24, §6.1 · pp. 24–25

6.2 ℓ1 Binary Logistic Regression

  • Up to 30× faster than the sequential rule and 50× faster than no screening, dynamic Gap Safe with strong warm start speeds binary logistic regression.The comparison is on the Leukemia data set.Source: §6.2 · p. 25, Figure 7 · p. 26

6.3 ℓ1{ℓ2 Multi-task Regression

  • Gap Safe screens out more variables than the compared dynamic safe rule and significantly reduces multi-task computation time across duality-gap tolerances from 10^-2 to 10^-8.The runtime benefit is especially notable when accurate estimates are required.Source: §6.3 · p. 25, Figure 8 · p. 27

6.4 Sparse-Group Lasso Regression

  • Dynamic Gap Safe screening significantly speeds Sparse-Group Lasso computation, and active warm start improves the gain further.The prediction error degrades increasingly for λ ≤ λmax/10^2.5.Source: Figure 9 · p. 28, §6.4 · p. 28

7. Conclusion

The paper presents Gap Safe screening as a unified approach for speeding sparse-regularized supervised learning solvers. Experiments on real high-dimensional data demonstrate its efficiency across multiple estimators and motivate its usefulness for speeding solvers.

7. Conclusion

  • Gap Safe rules unify screening for supervised-learning estimators with Lipschitz-gradient data fitting and separable sparsity-enforcing regularizers.The framework spans regression and classification settings.Source: §7 · p. 29
  • The method is more flexible than previously known safe rules and applies across regression and classification settings.The conclusion describes the approach as a unified presentation for popular estimators.Source: §7 · p. 29
  • Experiments on real high-dimensional data demonstrate the efficiency of Gap Safe rules and warm-start strategies across multiple estimators.The paper concludes that these rules are useful for speeding solvers targeting sparse regularization.Source: §7 · p. 29
Loading 1611.05780v4…