Lasso regression

Overview

The Lasso minimises ½‖y − Xβ‖₂² + λ‖β‖₁ over β, where X has N rows and p feature columns 1211.3966 eq. 1. The L1 term drives the coefficients of unhelpful features to exactly zero, so the fit uses a subset of the features. The smallest penalty that gives β = 0 is λmax = max_i |x_iᵀy| [arxiv:1211.3966 eq. 7].

Model selection solves the Lasso along a decreasing grid of penalties, which is slow for large p 1211.3966 §1 §2.2. Screening rules are a pre-step for this. Before a penalty is solved, a rule proves that some feature has a zero coefficient at that penalty, and the feature is dropped from the problem 1211.3966 §2.1. Heuristic rules such as the strong rule can discard active features, so they need a KKT check afterwards. Safe rules guarantee that every discarded feature is inactive 1211.3966 §1. The screening variants below are all safe rules. Their test is a ball, around a dual point computed from a nearby penalty, that must lie entirely in a region where |x_iᵀθ| < 1 1211.3966 §2.1. A smaller ball discards more features.

This page covers two uses of the Lasso. The screening variants come from the squared-loss path problem 1211.3966 eq. 1. The binomial variant comes from a study that uses the Lasso as a feature selector in a classification task 2407.03646 §2.2. The screening rules do not apply to the second use.

Variants

Solver only (no screening)

Solve the Lasso on all features at each grid point. This is the reference cost. With the SLEP solver the paper reports 121.41 s for a 100-point path on the Prostate data, 629.94 s on PIE and 2566.26 s on MNIST [arxiv:1211.3966 tab. 1]. The hardware is not stated.

Basic DPP

Uses λ₀ = λmax. At that penalty the dual optimum is known to be y/λmax, so no earlier solution is needed 1211.3966 §2.2 eq. 9. Feature i is discarded when |x_iᵀ(y/λmax)| < 1 − ‖y‖ ‖x_i‖ |1/λ − 1/λmax| [arxiv:1211.3966 Thm. 3] [Cor. 4]. The paper's basic-version rejection ratios appear only as figure data 1211.3966 fig. 2.

Sequential DPP

Uses the previous grid point λ_k as λ₀, with its dual point (y − Xβ*(λ_k))/λ_k 1211.3966 Cor. 5. Each step therefore needs the solution at the previous penalty.

Improvement 1: ray projection

Uses a projection onto a ray to shrink the DPP ball. The new ball is inside the DPP ball 1211.3966 §2.3.1 [Thm. 7]. The proof needs ⟨v₁, v₂⟩ ≥ 0 [arxiv:1211.3966 Thm. 7 proof]. The rule is in 1211.3966 Thm. 11. Ratio of solver-only to Improvement 1 time from 1211.3966 tab. 1: about 19× on Prostate, 56× on PIE and 68× on MNIST, computed from the table values.

Improvement 2: firm nonexpansiveness

Uses that projections are firmly nonexpansive. The resulting ball has half the radius of the DPP ball 1211.3966 Thm. 13. The rule is in 1211.3966 Thm. 14. Ratio from 1211.3966 tab. 1: about 7× on Prostate and 11× on PIE and MNIST.

EDPP (enhanced DPP)

Combines both improvements. The resulting ball is the smallest of the three 1211.3966 Thm. 15 §2.3.3. The rule is in 1211.3966 Thm. 16, and the sequential form is in 1211.3966 Cor. 17. Ratio from 1211.3966 tab. 1: about 33× on Prostate, 152× on PIE and 231× on MNIST. The paper also pairs EDPP with the LARS solver 1211.3966 tab. 4. Card: Lasso Screening Rules via Dual Polytope Projection.

Group Lasso extension

Penalises groups with λ Σ_g √n_g ‖β_g‖₂ 1211.3966 §3.1. The same ideas give a ball for groups 1211.3966 Thm. 19 and a group rule 1211.3966 Thm. 20. The proof uses the spectral norm of each group matrix 1211.3966 §3.2. Against the strong rule only, EDPP with the solver is 84×, 120× and 163× faster than the solver alone for 10000, 20000 and 40000 groups 1211.3966 tab. 5. The paper gives no safe group baseline to compare with 1211.3966 §4.2.

Binomial Lasso for feature selection (no screening)

A Lasso with the binomial family, α = 1, fitted with glmnet to choose text measures that separate AI from human essays 2407.03646 §2.2. One model is fitted per linguistic domain (phonology, morphology, syntax, lexicon), with AI versus human as the outcome. The penalty is the λ that minimises cross-validated classification error, and the non-zero coefficients at that λ are the selected features. The features are not scaled [arxiv:2407.03646 §2.2]. The reported models have 13 non-zero coefficients across the four domains, for example about −269.2 for primary stress and about +122.5 for alveolar 2407.03646 tab. 3. This is not a screening rule. The screening rules above are derived for the squared-loss Lasso 1211.3966 eq. 1 and do not apply to it. Card: Differentiating Between Human-Written and AI-Generated Texts Using Automatically Extracted Linguistic Features.

When to use which

Constraints that change the choice:

• Scaling. The rules assume ½‖y − Xβ‖² + λ‖β‖₁ 1211.3966 eq. 1. A solver with another loss scale or penalty convention must be mapped to this λ first, or the rules are wrong.
• Sample size. The binomial study uses ten texts, five per source 2407.03646 §2.1. The authors call the study exploratory 2407.03646 §1.2. Treat each selected feature as a hypothesis.
• Feature scale. The binomial model uses unscaled features, so its coefficients depend on each measure's units and cannot be ranked by size 2407.03646 §2.2 tab. 3.
• Degenerate directions. The projection divides by ‖v₁‖² [arxiv:1211.3966 Thm. 7]. The paper does not discuss zero columns, ties in the argmax, or sign(x*ᵀy) = 0.
• Normalisation. Unit-length features are stated only for the basic-version comparison 1211.3966 §4.1.1. The paper does not state it for the path experiments §4.1.2 or the group experiments §4.2.
• Timing. The paper does not say whether the "+solver" times include screening time. Compare the screening columns and the solver columns separately 1211.3966 tab. 1 tab. 3.

Implementation sketch

Sequential EDPP along a decreasing grid, condensed from the card's pseudocode 1211.3966 §2.3.3 [Cor. 17]. The solver is a black box.

# Sequential EDPP along a decreasing penalty grid  [arxiv:1211.3966 Cor. 17]
# Input: X (N, p), y (N,), lambdas (decreasing, all below lambda_max)
# Output: kept[k] = feature indices to solve at lambdas[k]

def edpp_path(X, y, lambdas):
    # lambda_max = max_i |x_i^T y|, where beta* = 0  [arxiv:1211.3966 eq. 7]
    corr = X.T @ y                                    # (p,)
    best = argmax(abs(corr))
    path = [abs(corr[best])] + list(lambdas)
    # The dual optimum at lambda_max is y / lambda_max  [arxiv:1211.3966 eq. 9]
    theta_prev = y / path[0]                          # (N,)
    kept = []
    for k in range(len(path) - 1):
        lam_prev, lam = path[k], path[k + 1]
        # Ray direction at lambda_prev  [arxiv:1211.3966 Thm. 7]
        if k == 0:
            v1 = sign(corr[best]) * X[:, best]        # (N,)
        else:
            v1 = y / lam_prev - theta_prev            # (N,)
        v2 = y / lam - theta_prev                     # (N,)
        # Keep only the part of v2 orthogonal to v1  [arxiv:1211.3966 Thm. 7]
        v2_perp = v2 - (v1 @ v2) / (v1 @ v1) * v1
        # Ball with half the radius, centred halfway  [arxiv:1211.3966 Thm. 15]
        centre = theta_prev + 0.5 * v2_perp
        radius = 0.5 * norm(v2_perp)
        # Discard i if |x_i^T centre| < 1 - radius * ||x_i||
        #                                    [arxiv:1211.3966 Thm. 16]
        scores = abs(X.T @ centre)                    # (p,)
        keep = scores >= 1 - radius * column_norms(X) # (p,) bool
        kept.append(nonzero(keep))
        # Solve on the kept columns, then rebuild the dual point
        #                                    [arxiv:1211.3966 eq. 3]
        beta = lasso_solve(X[:, keep], y, lam)
        theta_prev = (y - X[:, keep] @ beta) / lam    # (N,)
    return kept

Contradictions

None known across papers. The two cards use the Lasso for different jobs, a squared-loss path with screening and binomial selection on ten texts, so their numbers are not comparable 1211.3966 eq. 1 2407.03646 §2.2. Within the screening paper, the text and the tables disagree on some numbers:

• Prostate speed-up for EDPP: the text says 30× 1211.3966 §4.1.2, and the table ratio is about 33× 1211.3966 tab. 1.
• Leukemia sample count: the text says 52 1211.3966 §4.1.2, and the matrix is 55 × 11225 1211.3966 fig. 4.
• Synthetic 2 design: the text gives both i.i.d. Gaussian entries and pairwise correlation 0.5^|i−j| 1211.3966 §4.1.2. The construction is not stated.

The screening-paper items above are reported as found, and none is resolved here. Within the binomial study, the text says primary stress did not differ significantly, yet it has the largest-magnitude LASSO coefficient 2407.03646 tab. 2 tab. 3 §4. The paper does not reconcile the two.

Papers

• Lasso Screening Rules via Dual Polytope Projection: safe screening rules DPP and EDPP for the Lasso, and a group extension.
• Differentiating Between Human-Written and AI-Generated Texts Using Automatically Extracted Linguistic Features: a binomial Lasso, with AI versus human as the outcome, that selects linguistic features from ten essays.