Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model

Grzegorz Gluch, Khashayar Barooti, Rüdiger Urbanke
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:11457-11488, 2023.

Abstract

A new model for adversarial robustness was introduced by Goldwasser et al. in [GKKM20]. In this model the authors present a selective and transductive learning algorithm which guarantees a low test error and low rejection rate wrt to the original distribution. Moreover, a lower bound in terms of the VC-dimension, the standard risk and the number of samples is derived. We show that this lower bound can be broken in the quantum world. We consider a new model, influenced by the quantum PAC-learning model introduced by [BJ95], and similar in spirit to the one in [GKKM20]. In this model we give an interactive protocol between the learner and the adversary (at test-time) that guarantees robustness. This protocol, when applied, breaks the lower bound from [GKKM20]. From the technical perspective, our protocol is inspired by recent advances in delegation of quantum computation, e.g. [Mah18]. But in order to be applicable to our task, we extend the delegation protocol to enable a new feature, e.g. by extending delegation of decision problems, i.e. BQP, to sampling problems with adversarially chosen inputs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-gluch23a, title = {Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model}, author = {Gluch, Grzegorz and Barooti, Khashayar and Urbanke, R\"udiger}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {11457--11488}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/gluch23a/gluch23a.pdf}, url = {https://proceedings.mlr.press/v206/gluch23a.html}, abstract = {A new model for adversarial robustness was introduced by Goldwasser et al. in [GKKM20]. In this model the authors present a selective and transductive learning algorithm which guarantees a low test error and low rejection rate wrt to the original distribution. Moreover, a lower bound in terms of the VC-dimension, the standard risk and the number of samples is derived. We show that this lower bound can be broken in the quantum world. We consider a new model, influenced by the quantum PAC-learning model introduced by [BJ95], and similar in spirit to the one in [GKKM20]. In this model we give an interactive protocol between the learner and the adversary (at test-time) that guarantees robustness. This protocol, when applied, breaks the lower bound from [GKKM20]. From the technical perspective, our protocol is inspired by recent advances in delegation of quantum computation, e.g. [Mah18]. But in order to be applicable to our task, we extend the delegation protocol to enable a new feature, e.g. by extending delegation of decision problems, i.e. BQP, to sampling problems with adversarially chosen inputs.} }
Endnote
%0 Conference Paper %T Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model %A Grzegorz Gluch %A Khashayar Barooti %A Rüdiger Urbanke %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-gluch23a %I PMLR %P 11457--11488 %U https://proceedings.mlr.press/v206/gluch23a.html %V 206 %X A new model for adversarial robustness was introduced by Goldwasser et al. in [GKKM20]. In this model the authors present a selective and transductive learning algorithm which guarantees a low test error and low rejection rate wrt to the original distribution. Moreover, a lower bound in terms of the VC-dimension, the standard risk and the number of samples is derived. We show that this lower bound can be broken in the quantum world. We consider a new model, influenced by the quantum PAC-learning model introduced by [BJ95], and similar in spirit to the one in [GKKM20]. In this model we give an interactive protocol between the learner and the adversary (at test-time) that guarantees robustness. This protocol, when applied, breaks the lower bound from [GKKM20]. From the technical perspective, our protocol is inspired by recent advances in delegation of quantum computation, e.g. [Mah18]. But in order to be applicable to our task, we extend the delegation protocol to enable a new feature, e.g. by extending delegation of decision problems, i.e. BQP, to sampling problems with adversarially chosen inputs.
APA
Gluch, G., Barooti, K. & Urbanke, R.. (2023). Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:11457-11488 Available from https://proceedings.mlr.press/v206/gluch23a.html.

Related Material