The extended Smale's 9th problem - on computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs, and learning

Authors

Alexander Bastounis, Anders Christian Hansen, and Verner Vlačić

Reference

in preparation.

Abstract

Linear and semidefinite programming (LP, SDP), regularisation through basis pursuit (BP) and Lasso, as well as neural networks in deep learning have seen great success in mathematics, statistics, data science, and computer-assisted proofs. The success and performance of LP is traditionally attributed to the fact that it is polynomially solvable (colloquially, “in P”) for rational inputs. On the other hand, in his list of problems for the 21st century S. Smale calls for “[Computational] models which process approximate inputs and which permit round-off computations". Indeed, since e.g. the square root and the exponential function do not have exact representations, inaccurate data input is a daily encounter. The relevance of such a model is further emphasised by the fact that even a rational number such as 1/3 is stored only approximately when using floating-point arithmetic, a situation faced by most software. This model allowing inaccurate input of arbitrary precision, which we call the extended model, leads to extended versions of fundamental problems such as: “Are LP and other aforementioned problems in P?” We settle this problem in both the negative and the positive, revealing two surprises: (1) In mathematics, sparse regularisation, statistics, and learning, one successfully computes with non-computable problems (e.g., in compressed sensing, for which we provide a detailed account). The same happens also in computer-assisted proofs, for example in the famous proof of Kepler’s conjecture; (2) In order to mathematically characterise this phenomenon, one needs an intricate complexity theory for, seemingly paradoxically, non-computable problems.

Keywords

Existence of algorithms, convex and non-convex problems, Smale’s 9th,18th problems, complexity of non-computable problems, Solvability Complexity Index hierarchy, computer-assisted proofs, compressed sensing.

Download this document:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.