Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2211-2239, 2023.

Abstract

We study the problem of PAC learning γ-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoffsuggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms. Concretely, the sample complexity of the problem is ˜Θ(1/(γ2ϵ)). We start by giving a simple efficient algorithm with sample complexity ˜O(1/(γ2ϵ2)). Our main resultis a lower bound for Statistical Query (SQ) algorithms and low-degree polynomial tests suggesting that the quadratic dependence on 1/ϵ in the sample complexity is inherent for computationally efficient algorithms.Specifically, our results imply a lower bound of ˜Ω(1/(γ1/2ϵ2)) on the sample complexity of any efficient SQ learner or low-degree test.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-diakonikolas23a, title = {Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise}, author = {Diakonikolas, Ilias and Diakonikolas, Jelena and Kane, Daniel M. and Wang, Puqian and Zarifis, Nikos}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {2211--2239}, 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/diakonikolas23a/diakonikolas23a.pdf}, url = {https://proceedings.mlr.press/v195/diakonikolas23a.html}, abstract = {We study the problem of PAC learning $\gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoffsuggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms. Concretely, the sample complexity of the problem is $\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. We start by giving a simple efficient algorithm with sample complexity $\widetilde{O}(1/(\gamma^2 \epsilon^2))$. Our main resultis a lower bound for Statistical Query (SQ) algorithms and low-degree polynomial tests suggesting that the quadratic dependence on $1/\epsilon$ in the sample complexity is inherent for computationally efficient algorithms.Specifically, our results imply a lower bound of $\widetilde{\Omega}(1/(\gamma^{1/2} \epsilon^2))$ on the sample complexity of any efficient SQ learner or low-degree test.} }
Endnote
%0 Conference Paper %T Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise %A Ilias Diakonikolas %A Jelena Diakonikolas %A Daniel M. Kane %A Puqian Wang %A Nikos Zarifis %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-diakonikolas23a %I PMLR %P 2211--2239 %U https://proceedings.mlr.press/v195/diakonikolas23a.html %V 195 %X We study the problem of PAC learning $\gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoffsuggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms. Concretely, the sample complexity of the problem is $\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. We start by giving a simple efficient algorithm with sample complexity $\widetilde{O}(1/(\gamma^2 \epsilon^2))$. Our main resultis a lower bound for Statistical Query (SQ) algorithms and low-degree polynomial tests suggesting that the quadratic dependence on $1/\epsilon$ in the sample complexity is inherent for computationally efficient algorithms.Specifically, our results imply a lower bound of $\widetilde{\Omega}(1/(\gamma^{1/2} \epsilon^2))$ on the sample complexity of any efficient SQ learner or low-degree test.
APA
Diakonikolas, I., Diakonikolas, J., Kane, D.M., Wang, P. & Zarifis, N.. (2023). Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:2211-2239 Available from https://proceedings.mlr.press/v195/diakonikolas23a.html.

Related Material