# Faster Lasso regression

Fit a sparse linear model by Lasso on a wide random design faster than scikit-learn, reaching the same objective value. The Lasso is a workhorse of high-dimensional statistics, signal recovery and feature selection.

## Task

Input: a design $X\in\mathbb{R}^{m\times d}$ with independent standard normal entries and responses $y=X\beta+0.01\,\varepsilon$, where $m=5n$, $d=10n$, $\beta$ has $n$ standard normal non-zeros at random positions and $\varepsilon$ is standard normal; in the benchmark $n=398$, so $X$ is $1990\times3980$. Output: a coefficient vector $w\in\mathbb{R}^d$ for

$$\min_w\ f(w)=\frac{1}{2m}\lVert y-Xw\rVert_2^2+0.1\,\lVert w\rVert_1.$$

An output is accepted when $f(w)\le f(w^{\mathrm{ref}})+10^{-5}$. The reference solver is scikit-learn's `Lasso(alpha=0.1, fit_intercept=False)`, a coordinate-descent method.

Score: the reference's run time divided by the candidate's, averaged over the test instances; it is 1 if any output fails the check, and speed-ups below 1 count as 1. Higher is better.

## Background

The Lasso of Tibshirani (1996) adds an $\ell_1$ penalty that sets many coefficients exactly to zero. Cyclic coordinate descent, popularized for this problem by Friedman, Hastie and Tibshirani (2010), is the method inside scikit-learn and glmnet. Because acceptance only requires matching the reference objective to $10^{-5}$, faster solvers may use screening rules, active-set strategies or different algorithms, as long as the objective is as low.

## Data and evaluation

- **Instances:** 100 test and 100 development instances from the task's generator at $n=398$, in the [AlgoTune dataset](https://huggingface.co/datasets/oripress/AlgoTune); the reference needs about 120 ms per instance on the authors' machine.
- **Evaluation code:** the AlgoTune harness (`./algotune.sh evaluate` in the [repository](https://github.com/oripress/AlgoTune)), which runs the task's checker on every output.
- **Hardware:** speed-ups depend on the machine, so reference and candidate are timed in the same environment. The paper keeps the fastest of 10 timed runs per instance, each after a warm-up, on an AMD EPYC 9454 CPU with 14 GB of memory; agents had 8 cores, and compilation is not timed.

## What is known

- Best on the [AlgoTune leaderboard](https://algotune.io) as of 2026-10-20: 3.19×, by the AlgoTuner agent driven by Gemini 3 Pro Preview, ahead of Qwen3 Coder (1.73×) and DeepSeek R1 (1.57×).
- In the paper's failure analysis, a Claude Opus 4 run rewrote the Lasso in pure Python with Numba, stayed slower than scikit-learn (reported as 0.33×) and was scored 1×.
- Press et al. (2025) describe most agent speed-ups as surface-level: better library calls, better library usage or low-level rewrites, for example with Numba.

## What would count as progress

- A solver beating 3.19× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
- A comparison of coordinate descent with screening, proximal-gradient and homotopy methods on these instances, with timings.

## References

1. O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. [arXiv:2507.15887](https://arxiv.org/abs/2507.15887)
2. R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B 58, 267–288 (1996). [doi:10.1111/j.2517-6161.1996.tb02080.x](https://doi.org/10.1111/j.2517-6161.1996.tb02080.x)
3. J. Friedman, T. Hastie, R. Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software 33(1) (2010). [doi:10.18637/jss.v033.i01](https://doi.org/10.18637/jss.v033.i01)

## Source

Imported from [AlgoTune task lasso](https://github.com/oripress/AlgoTune/tree/main/AlgoTuneTasks/lasso), curated by Ori Press and the AlgoTune contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.