# When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation

arXiv: https://arxiv.org/abs/2312.11425 · HTML: https://mlsanity.com/paper/2312.11425/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 59 references that are in the map.
- First posted on arXiv 18 Dec 2023.

## Builds on (most cited first, 11 of 11)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Deep Convolutional Neural Network for Inverse Problems in Imaging](https://mlsanity.com/paper/1611.03679/) (2016)
- [Learning a Variational Network for Reconstruction of Accelerated MRI Data](https://mlsanity.com/paper/1704.00447/) (2017)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [A Review of Convolutional Neural Networks for Inverse Problems in Imaging](https://mlsanity.com/paper/1710.04011/) (2017)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [A formal proof of the Kepler conjecture](https://mlsanity.com/paper/1501.02155/) (2015)
- [The troublesome kernel -- On hallucinations, no free lunches and the accuracy-stability trade-off in inverse problems](https://mlsanity.com/paper/2001.01258/) (2020)
- [The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learning](https://mlsanity.com/paper/2110.15734/) (2021)
- [Generalised hardness of approximation and the SCI hierarchy -- On determining the boundaries of training algorithms in AI](https://mlsanity.com/paper/2209.06715/) (2022)

## Built on by (most cited first, 2 of 2)

- [Do stable neural networks exist for classification problems? -- A new view on stability in AI](https://mlsanity.com/paper/2401.07874/) (2024)
- [The radius of statistical efficiency](https://mlsanity.com/paper/2405.09676/) (2024)

## Abstract (arXiv)

The arrival of AI techniques in computations, with the potential for hallucinations and non-robustness, has made trustworthiness of algorithms a focal point. However, trustworthiness of the many classical approaches are not well understood. This is the case for feature selection, a classical problem in the sciences, statistics, machine learning etc. Here, the LASSO optimisation problem is standard. Despite its widespread use, it has not been established when the output of algorithms attempting to compute support sets of minimisers of LASSO in order to do feature selection can be trusted. In this paper we establish how no (randomised) algorithm that works on all inputs can determine the correct support sets (with probability > 1/2) of minimisers of LASSO when reading approximate input, regardless of precision and computing power. However, we define a LASSO condition number and design an efficient algorithm for computing these support sets provided the input data is well-posed (has finite condition number) in time polynomial in the dimensions and logarithm of the condition number. For ill-posed inputs the algorithm runs forever, hence, it will never produce a wrong answer. Furthermore, the algorithm computes an upper bound for the condition number when this is finite. Finally, for any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer. Our impossibility results stem from generalised hardness of approximation -- within the Solvability Complexity Index (SCI) hierarchy framework -- that generalises the classical phenomenon of hardness of approximation.