A Theory of Learning with Autoregressive Chain of Thought

Explore the theoretical foundations of autoregressive chain-of-thought learning in this machine learning lecture presented by Gal Vardi from the Weizmann Institute of Science. Delve into a formal PAC-learning framework that analyzes how language models generate intermediate reasoning steps to solve complex tasks, examining both scenarios where the chain-of-thought is observable and when it remains latent during training with only prompt-answer pairs. Discover the sample and computational complexity considerations in these learning settings, and examine a simple class of models that enables efficient universal chain-of-thought learning. Gain insights into cutting-edge theoretical machine learning research with particular focus on deep learning theory and the mathematical underpinnings of how modern language models approach multi-step reasoning tasks.