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


“Machine Learning Foundations Accelerate Innovation and Promote Trustworthiness” by Rebecca Willett

Jan 26, 2024

Nightshade: Data Poisoning to Fight Generative AI with Ben Zhao

Jan 23, 2024
In the News

In The News: U.N. Officials Urge Regulation of Artificial Intelligence

"Security Council members said they feared that a new technology might prove a major threat to world peace."
Jul 27, 2023
UChicago CS News

UChicago Computer Scientists Bring in Generative Neural Networks to Stop Real-Time Video From Lagging

Jun 29, 2023
UChicago CS News

Computer Science Displays Catch Attention at MSI’s Annual Robot Block Party

Apr 07, 2023
UChicago CS News

UChicago, Stanford Researchers Explore How Robots and Computers Can Help Strangers Have Meaningful In-Person Conversations

Mar 29, 2023
Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
UChicago CS News

Postdoc Alum John Paparrizos Named ICDE Rising Star

Mar 15, 2023
UChicago CS News

New EAGER Grant to Asst. Prof. Eric Jonas Will Explore ML for Quantum Spectrometry

Mar 03, 2023
UChicago CS News

Assistant Professor Chenhao Tan Receives Sloan Research Fellowship

Feb 15, 2023
UChicago CS News

UChicago Scientists Develop New Tool to Protect Artists from AI Mimicry

Feb 13, 2023
In the News

Professors Rebecca Willett and Ben Zhao Discuss the Future of AI on Public Radio

Jan 26, 2023
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