| Abstract: |
| This talk examines when and how machine learning models can learn to execute algorithms. Such reasoning underpins core tasks such as arithmetic and sorting, which are often used as testbeds for algorithmic reasoning. I present both lower and upper bound results. On the negative side, I show that end-to-end training can be inefficient for learning algorithms, while step-by-step supervision enables efficient learnability. On the positive side, I demonstrate that neural networks can be trained to execute algorithms and general computer instructions exactly. Finally, I quantify their ensemble complexity, which provides a lower bound on the number of independent training runs required to achieve zero error. These results indicate when algorithmic behavior is learnable in practice and when structural barriers make it provably hard. |
|