--- kind: concept slug: lasso-regression title: Lasso regression summary: >- Lasso regression is an L1-penalised linear model that sets some coefficients to exactly zero. Safe screening rules (DPP, with EDPP the tightest) discard features that are provably zero before each penalty on a grid is solved. A binomial Lasso that selects text features for AI-versus-human classification is a separate, small-sample use. Speed-ups are author-reported. tags: [sparse-regression, screening-rules, lasso, convex-optimization, feature-selection] papers: ["1211.3966", "2407.03646"] related: [feature-selection, safe-screening, ai-generated-text-detection] status: draft updated_at: 2026-11-01 --- ## Overview The Lasso minimises ½‖y − Xβ‖₂² + λ‖β‖₁ over β, where X has N rows and p feature columns [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1211.3966 eq. 1]. The binomial variant comes from a study that uses the Lasso as a feature selector in a classification task [arxiv: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 [arxiv: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 [arxiv:1211.3966 fig. 2]. ### Sequential DPP Uses the previous grid point λ_k as λ₀, with its dual point (y − Xβ*(λ_k))/λ_k [arxiv: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 [arxiv:1211.3966 §2.3.1] [Thm. 7]. The proof needs ⟨v₁, v₂⟩ ≥ 0 [arxiv:1211.3966 Thm. 7 proof]. The rule is in [arxiv:1211.3966 Thm. 11]. Ratio of solver-only to Improvement 1 time from [arxiv: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 [arxiv:1211.3966 Thm. 13]. The rule is in [arxiv:1211.3966 Thm. 14]. Ratio from [arxiv: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 [arxiv:1211.3966 Thm. 15] [§2.3.3]. The rule is in [arxiv:1211.3966 Thm. 16], and the sequential form is in [arxiv:1211.3966 Cor. 17]. Ratio from [arxiv:1211.3966 tab. 1]: about 33× on Prostate, 152× on PIE and 231× on MNIST. The paper also pairs EDPP with the LARS solver [arxiv:1211.3966 tab. 4]. Card: [Lasso Screening Rules via Dual Polytope Projection](/papers/1211.3966). ### Group Lasso extension Penalises groups with λ Σ_g √n_g ‖β_g‖₂ [arxiv:1211.3966 §3.1]. The same ideas give a ball for groups [arxiv:1211.3966 Thm. 19] and a group rule [arxiv:1211.3966 Thm. 20]. The proof uses the spectral norm of each group matrix [arxiv: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 [arxiv:1211.3966 tab. 5]. The paper gives no safe group baseline to compare with [arxiv: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 [arxiv: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 [arxiv:2407.03646 tab. 3]. This is not a screening rule. The screening rules above are derived for the squared-loss Lasso [arxiv:1211.3966 eq. 1] and do not apply to it. Card: [Differentiating Between Human-Written and AI-Generated Texts Using Automatically Extracted Linguistic Features](/papers/2407.03646). ## When to use which | Situation | Use | Why | |---|---|---| | One penalty value, no earlier solution available | Basic DPP | The dual point at λmax is known, so no solve is needed first [arxiv:1211.3966 §2.2] | | Penalty grid, solves can run in grid order | Sequential EDPP | Smallest ball of the family. Largest reported speed-ups on the paper's data [arxiv:1211.3966 tab. 1] [tab. 3] | | Groups of features, not single features | Group extension | Rule for whole groups [arxiv:1211.3966 Thm. 20] | | Solutions are only approximate | None covered | The theorems take the exact dual point as input, and the paper does not analyse approximate solutions [arxiv:1211.3966 Thm. 3] [Cor. 5] | | Heuristic screens are acceptable | Strong rule (not in this paper's variants) | It is a baseline here, not a variant. It can discard active features and needs a KKT check [arxiv:1211.3966 §1] | | Binary outcome, small sample, sparse selection to read by hand | Binomial Lasso, λ by cross-validation | This is how the classification study uses it, on ten texts [arxiv:2407.03646 §2.1] [§2.2]. The paper states neither folds nor seed, so its selection cannot be reproduced exactly from the text [arxiv:2407.03646 §2.2] | | Binomial loss on a penalty grid, with screening | None covered | The screening rules assume the squared loss [arxiv:1211.3966 eq. 1]. No screening rule for the binomial loss is in these cards | Constraints that change the choice: - **Scaling.** The rules assume ½‖y − Xβ‖² + λ‖β‖₁ [arxiv: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 [arxiv:2407.03646 §2.1]. The authors call the study exploratory [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1211.3966 tab. 1] [tab. 3]. ## Implementation sketch Sequential EDPP along a decreasing grid, condensed from the card's pseudocode [arxiv:1211.3966 §2.3.3] [Cor. 17]. The solver is a black box. ```pseudocode # 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 [arxiv:1211.3966 eq. 1] [arxiv: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× [arxiv:1211.3966 §4.1.2], and the table ratio is about 33× [arxiv:1211.3966 tab. 1]. - Leukemia sample count: the text says 52 [arxiv:1211.3966 §4.1.2], and the matrix is 55 × 11225 [arxiv:1211.3966 fig. 4]. - Synthetic 2 design: the text gives both i.i.d. Gaussian entries and pairwise correlation 0.5^|i−j| [arxiv: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 [arxiv:2407.03646 tab. 2] [tab. 3] [§4]. The paper does not reconcile the two. ## Papers - [Lasso Screening Rules via Dual Polytope Projection](/papers/1211.3966): 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](/papers/2407.03646): a binomial Lasso, with AI versus human as the outcome, that selects linguistic features from ten essays.