Computational and Statistical Limits in Modern Machine Learning

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.

Bio

Idan Attias is a postdoctoral researcher at the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), working with Lev Reyzin (University of Illinois Chicago), Nati Srebro, and Avrim Blum (Toyota Technological Institute at Chicago). He obtained his Ph.D. in Computer Science under the supervision of Aryeh Kontorovich (Ben-Gurion University) and Yishay Mansour (Tel Aviv University and Google Research).

His research focuses on the foundations of machine learning theory and data-driven sequential decision-making. His work has been recognized with a Best Paper Award at ICML ’24 and selection as a Rising Star in Data Science (University of California San Diego ’24). His postdoctoral research is supported by an NSF fellowship, and his Ph.D. studies were fully supported by the Israeli Council for Higher Education Scholarship for Outstanding PhD Students in Data Science.