Computational and Statistical Limits in Modern Machine Learning – Job Talk

Abstract: Modern machine learning systems operate in regimes that challenge classical learning-theoretic assumptions. Models are highly overparameterized, trained with simple optimization algorithms, and rely critically on how data is collected and curated. Understanding the limits of learning in these settings requires revisiting both the computational and statistical foundations of learning theory. A central question in learning theory asks which functions are tractably learnable. Classical complexity results suggest strong computational barriers, motivating a focus on “learnable subclasses” defined by properties of the target function. In this talk, I argue for a different perspective by emphasizing the role of the training distribution. Fixing the learning algorithm (e.g. stochastic gradient descent applied to neural networks), I show that allowing a “positive distribution shift”, where training data is drawn from a carefully chosen auxiliary distribution while evaluation remains on the target distribution, can render several classically hard learning problems tractable. Beyond computational considerations, I then study statistical limits of learning in modern, overparameterized models using stochastic convex optimization as a theoretical framework. While classical theory often suggests that successful generalization requires avoiding memorization, I show that memorization is in fact unavoidable: achieving high accuracy requires retaining nontrivial information about the training data and can even enable the identification of individual training examples. These results reveal fundamental privacy–accuracy tradeoffs inherent to accurate learning.