Interactive Proofs for Verifying Machine Learning

Interactive Proofs for Verifying Machine Learning (via Zoom)

Abstract: In the agnostic PAC model of supervised learning, the objective is to learn a classifier that is “ɛ-good” (i.e., has accuracy at most ɛ worse than the best classifier in some fixed set of classifiers).

This talk will address the following question: in what cases does learning an ɛ-good hypothesis require more resources than verifying that a hypothesis proposed by someone else is ɛ-good? If verification is significantly cheaper than learning, that could have implications for delegation of machine learning tasks.

We will explain the intuition and formal details of our verification setting, and discuss some of the following observations: (1) There exists a set of classifiers for which verification requires quadratically less random samples than are required for learning; (2) The previous result is tight, namely, for any set of classifiers the gap between learning and verification is at most quadratic; (3) There exists a set of classifiers with no gap, namely the numbers of random samples required for learning and for verification are equal; (4) The set of Fourier-sparse functions can be efficiently verified using random samples only, even though it is believed to be impossible to efficiently learn this set from random samples alone; (5) Directions for future work.

This is joint work with Shafi Goldwasser (UC Berkeley), Guy Rothblum (Weizmann Institute of Science), and Amir Yehudayoff (Technion). 

Bio: Jonathan is a PhD student at UC Berkeley, advised by Shafi Goldwasser. He has a broad interest in theoretical computer science, and especially fascinated with computational learning theory. Jonathan holds an MSc from Tel Aviv University, where he was advised by Amir Shpilka and Amir Yehudayoff. As an undergraduate Jonathan studied at the Lautman Interdisciplinary Program.