PAC Verification of Statistical Algorithms

Saachi Mutreja, Jonathan Shafer
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5021-5043, 2023.

Abstract

Goldwasser et al. (2021) recently proposed the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objective is verified using an interactive proof. In this paper we develop this notion further in a number of ways. First, we prove a lower bound of Ω(√d/ε2) i.i.d. samples for PAC verification of hypothesis classes of VC dimension d. Second, we present a protocol for PAC verification of unions of intervals over R that improves upon their proposed protocol for that task, and matches our lower bound’s dependence on d. Third, we introduce a natural generalization of their definition to verification of general statistical algorithms, which is applicable to a wider variety of settings beyond agnostic PAC learning. Showcasing our proposed definition, our final result is a protocol for the verification of statistical query algorithms that satisfy a combinatorial constraint on their queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-mutreja23a, title = {PAC Verification of Statistical Algorithms}, author = {Mutreja, Saachi and Shafer, Jonathan}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {5021--5043}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/mutreja23a/mutreja23a.pdf}, url = {https://proceedings.mlr.press/v195/mutreja23a.html}, abstract = {Goldwasser et al. (2021) recently proposed the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objective is verified using an interactive proof. In this paper we develop this notion further in a number of ways. First, we prove a lower bound of $\Omega(\sqrt{d}/\varepsilon^2)$ i.i.d. samples for PAC verification of hypothesis classes of VC dimension $d$. Second, we present a protocol for PAC verification of unions of intervals over $\mathbb{R}$ that improves upon their proposed protocol for that task, and matches our lower bound’s dependence on $d$. Third, we introduce a natural generalization of their definition to verification of general statistical algorithms, which is applicable to a wider variety of settings beyond agnostic PAC learning. Showcasing our proposed definition, our final result is a protocol for the verification of statistical query algorithms that satisfy a combinatorial constraint on their queries.} }
Endnote
%0 Conference Paper %T PAC Verification of Statistical Algorithms %A Saachi Mutreja %A Jonathan Shafer %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-mutreja23a %I PMLR %P 5021--5043 %U https://proceedings.mlr.press/v195/mutreja23a.html %V 195 %X Goldwasser et al. (2021) recently proposed the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objective is verified using an interactive proof. In this paper we develop this notion further in a number of ways. First, we prove a lower bound of $\Omega(\sqrt{d}/\varepsilon^2)$ i.i.d. samples for PAC verification of hypothesis classes of VC dimension $d$. Second, we present a protocol for PAC verification of unions of intervals over $\mathbb{R}$ that improves upon their proposed protocol for that task, and matches our lower bound’s dependence on $d$. Third, we introduce a natural generalization of their definition to verification of general statistical algorithms, which is applicable to a wider variety of settings beyond agnostic PAC learning. Showcasing our proposed definition, our final result is a protocol for the verification of statistical query algorithms that satisfy a combinatorial constraint on their queries.
APA
Mutreja, S. & Shafer, J.. (2023). PAC Verification of Statistical Algorithms. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:5021-5043 Available from https://proceedings.mlr.press/v195/mutreja23a.html.

Related Material