| dc.description.abstract | Lasso is an optimization problem that is favored by both statisticians and data scientists, and algorithms for solving it is offered in most statistical computing and machine learning software. However, new research into the fundamental barriers in the theory of computation shows that several optimization methods, including lasso, are generally non-computable. It has been shown that, when the input matrices are assumed to have more columns than rows, the following phenomenon occurs: (1) For any K≥1, one can construct an input class for lasso such that any algorithm will fail to compute K or more correct digits of the true solution for at least one input. This means that lasso is non-computable in the traditional Turing sense. (2) There is an algorithm that computes K−1 correct digits for the same input class, but any such algorithm requires an arbitrarily long time to do so. (3) There is an algorithm that computes K−2 correct digits, which is polynomial in the number of variables in the inputs. Similar results to (1), (2), and (3) are shown for randomized algorithms as well. This thesis establishes the impossibility results outlined above, for lasso in the form typical of regression situations, where the input matrices are assumed to have more rows than columns. The impossibility results are then generalized to hold for a continuous error ε≥ 0 instead of the number of correct digits K. This leads to phase transitions for lasso that are reminiscent of the phase transitions that appear in hardness of approximation. We call the values where the phase transitions occur for a given lasso input class the strong breakdown-epsilon, and the weak breakdown-epsilon. Specifically, for a given input class, solutions with error less than the strong breakdown-epsilon are non-computable in general. Solutions with error less than the weak breakdown-epsilon are computable, but require an arbitrary amount of time in the worst case. Solutions with error greater than the weak breakdown-epsilon are computable in polynomial time (in the number of input variables). We extend the results to hold for randomized algorithms as well, and establish the values of the probabilistic versions of the breakdown-epsilons for the same input class. These results show that it is sometimes impossible to compute solutions to lasso by use of algorithms. | eng |