When can you trust feature selection? -- I: A condition-based analysis
  of LASSO and generalised hardness of approximation
Alexander Bastounis Felipe Cucker Anders C. Hansen
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.