[Proof Complexity] MIAO seminar Fri Mar 1 at 14:00 CET with Ninad Rajgopal: On the power of interactive proofs for learning

[Jakob Nordström]

Dear all,

On Friday March 1 at 14:00 CET we will have the opportunity to enjoy a seminar with Ninad Rajgopal from the University of Cambridge, who will give a talk titled "On the power of interactive proofs for learning". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at Lund University. Local participants are warmly welcome to seminar room E:2116 at Ole Römers väg 3. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Friday Mar 1 at 14:00 in seminar room E:2116, Ole Römers väg 3, Lund University, and on Zoom
On the power of interactive proofs for learning
(Ninad Rajgopal, University of Cambridge)

We study interactive proof systems for verifying the results of agnostic learning tasks, which was recently initiated by Goldwasser, Rothblum, Shafer and Yehudayoff [GRSY21], as PAC-verification. Here, for a given target hypothesis class H and for any unknown n-variate Boolean function f, the verifier who only gets random example access to f (over the uniform distribution) interacts with an untrusted prover who has query access to f, to output a hypothesis that is as close to f as an optimal hypothesis from H, up to a small error. Such proof systems enable a verifier to delegate an agnostic learning task to an untrusted prover, with the goal being one of verification using much fewer random examples and/or running time, than actually performing learning (using queries) from scratch.

In this talk, I will present delegation proof systems for learning certain Boolean hypothesis classes that are central to the study of learning theory. Firstly, we show an interactive proof for learning all the ε-heavy Fourier coefficients of a function using poly(1/ε) many examples (i.e., Goldreich-Levin theorem), whereas the prover uses poly(n/ε) many membership queries, giving a verification speed-up that is independent of the input length n. Next, we show such interactive proofs for learning the class AC^0[2] building on the work by Carmosino-Impagliazzo-Kabanets-Kolokolova [CIKK17], where the verifier uses quasi-polynomially many random examples. In contrast, this class has been notoriously resistant beyond trivial brute force learning, even for constructing realisable learners (without a prover) using random examples. Finally, we show that if we do not insist on an efficient honest prover, then the model becomes trivial; even P/Poly can be learnt using O(1) many examples.

This is joint work with Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Bahar Salamatian, and Igor Shinkar, and will appear at STOC 2024.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se