Date & Time:
February 15, 2021 3:00 pm – 4:00 pm
Live Stream
02/15/2021 03:00 PM 02/15/2021 04:00 PM America/Chicago Steve Hanneke (TTIC) – Machine Learning Theory Beyond Uniform Convergence Live Stream

Machine Learning Theory Beyond Uniform Convergence

Watch via live stream

For over 50 years, statistical learning theory has developed largely based on the “uniform convergence” principle: for any model that is not too complex, a learner's performance on the training data is a good indicator of its expected performance on future yet-unseen examples. Uniform convergence motivates a natural learning strategy, known as Empirical Risk Minimization (ERM), where an algorithm simply optimizes over the model parameters to fit the training data as well as possible. While these ideas have led to powerful and beautiful theories, recent works have revealed limitations of uniform convergence for understanding the performance of certain learning algorithms, and of ERM as a viable approach to achieving certain desirable performance criteria. These observations reveal a need for new approaches to the design and analysis of machine learning algorithms. In this talk, I present a few examples from my recent work.

As a first example, we consider rates of convergence of an algorithm's generalization error as a function of number of training examples. Our work provides a complete characterization of the optimal rates of convergence. However, the rates achievable by general ERM learners can be suboptimal by an arbitrarily large gap. Rather than uniform convergence, our optimal learner is based on solutions of a game-theoretic interpretation of the learning problem.

As another example, it is known that many learning algorithms are unstable, in the sense that even if they are correct on a given test example, an adversary can change the learner's prediction by perturbing the example an imperceptible amount. Our work reveals that the natural ERM approach to addressing this, known as “adversarial training”, can fail spectacularly. However, approaching the problem from a different perspective, not relying on uniform convergence, we propose a new learning algorithm that is provably robust to such adversarial attacks. 

I will conclude with some ongoing work toward a general theory of data-dependent generalization bounds, yielding performance guarantees for certain learning algorithms where there is no corresponding bounded-capacity hypothesis class to which traditional uniform convergence arguments could be applied.

Based on various joint works with Olivier Bousquet, Omar Montasser, Shay Moran, Nathan Srebro, Ramon van Handel, and Amir Yehudayoff.

Host: Rebecca Willett

Steve Hanneke

Research Assistant Professor, Toyota Technological Institute at Chicago

Steve Hanneke is a Research Assistant Professor at the Toyota Technological Institute at Chicago. His research explores the theory of machine learning, with a focus on reducing the number of training examples sufficient for learning. His work develops new approaches to supervised, semi-supervised, active, and transfer learning, and also revisits the basic probabilistic assumptions at the foundation of learning theory. Steve earned a Bachelor of Science degree in Computer Science from UIUC in 2005 and a Ph.D. in Machine Learning from Carnegie Mellon University in 2009 with a dissertation on the theoretical foundations of active learning.

Related News & Events

UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 CS Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
UChicago CS News

UChicago CS Faculty Receive Industry Grants From J.P. Morgan, Google

Jul 19, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022

Is it Ethical to Use Facial Imaging in Decision-Making?

Jun 28, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

Two Incoming UChicago CS PhD Students Receive Department of Energy Fellowship

Jun 16, 2022

Data Science Institute Summit

Jun 15, 2022
UChicago CS News

DSI Summer Lab Returns In-Person With 49 Students From Across the U.S.

Jun 14, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube