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; the reference needs about 120 ms per instance on the authors' machine.
• Evaluation code: the AlgoTune harness (./algotune.sh evaluate in the repository), 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 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
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
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

Source

Imported from AlgoTune task 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.