Deep learning has seen tremendous growth in the last decade with applications across almost all fields of science and technology. In the pursuit of making deep learning methods more efficient and adaptable, there is an increasing need to design better algorithms and architectures. In this talk, I will give an overview of my research efforts towards advancing the statistical and computational foundations of deep learning with the goal of designing new principled algorithms and models. I will show how techniques originally developed for classical learning theory and convex optimization can be combined and extended for the era of deep learning. I will highlight this through two main contributions:

(1) New algorithms for training basic deep learning architectures that are simple, computationally efficient, and provably succeed even when the standard pipelines fail,
(2) A statistical characterization of state-of-the-art attention architectures, like Transformers, that gives new insights on their ability to capture long-range dependencies.