Document Open Access Logo

Improper Learning by Refuting

Authors Pravesh K. Kothari, Roi Livni

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.55.pdf
  • Filesize: 0.48 MB
  • 10 pages

Document Identifiers

Author Details

Pravesh K. Kothari
Roi Livni

Cite As Get BibTex

Pravesh K. Kothari and Roi Livni. Improper Learning by Refuting. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 55:1-55:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.55

Abstract

The sample complexity of learning a Boolean-valued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexity of efficient agnostic learning. 

We introduce refutation complexity, a natural computational analog of Rademacher complexity of a Boolean concept class and show that it exactly characterizes the sample complexity of efficient agnostic learning. Informally, refutation complexity of a class C is the minimum number of  example-label pairs required to efficiently distinguish between the case that the labels correlate with the evaluation of some member of C (structure) and the case where the labels are i.i.d. Rademacher random variables (noise). The easy direction of this relationship was implicitly used in the recent framework for improper PAC learning lower bounds of Daniely and co-authors via connections to the hardness of refuting random constraint satisfaction problems. Our work can be seen as making the relationship between agnostic learning and refutation implicit in their work into an explicit equivalence. 
In a recent, independent work, Salil Vadhan discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.

Subject Classification

Keywords
  • learning thoery
  • computation learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to refute a random CSP. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science - FOCS 2015, pages 689-708. IEEE Computer Soc., Los Alamitos, CA, 2015. Google Scholar
  2. Boaz Barak and Ankur Moitra. Tensor prediction, rademacher complexity and random 3-xor. CoRR, abs/1501.06521, 2015. Google Scholar
  3. Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002. URL: http://www.jmlr.org/papers/v3/bartlett02a.html.
  4. Quentin Berthet and Philippe Rigollet. Computational lower bounds for sparse PCA. CoRR, abs/1304.0828, 2013. Google Scholar
  5. Venkat Chandrasekaran and Michael I. Jordan. Computational and statistical tradeoffs via convex relaxation. Proceedings of the National Academy of Sciences, 110(13):E1181-E1190, 2013. URL: http://dx.doi.org/10.1073/pnas.1302293110.
  6. Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 105-117. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897520.
  7. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. More data speeds up training time in learning halfspaces over sparse vectors. In NIPS, pages 145-153, 2013. Google Scholar
  8. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In STOC, pages 441-448. ACM, 2014. Google Scholar
  9. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 441-448. ACM, 2014. Google Scholar
  10. Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf’s. In COLT, pages 815-830, 2016. Google Scholar
  11. Scott E. Decatur, Oded Goldreich, and Dana Ron. Computational sample complexity. SIAM J. Comput., 29(3):854-879, 1999. Google Scholar
  12. Uriel Feige. Relations between average case complexity and approximation complexity. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 534-543. ACM, 2002. URL: http://dx.doi.org/10.1145/509907.509985.
  13. Uriel Feige. Refuting smoothed 3cnf formulas. In FOCS, pages 407-417. IEEE Computer Society, 2007. Google Scholar
  14. Vitaly Feldman. Distribution-specific agnostic boosting. In Andrew Chi-Chih Yao, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 241-250. Tsinghua University Press, 2010. URL: http://conference.itcs.tsinghua.edu.cn/ICS2010/content/papers/20.html.
  15. Yoav Freund and Robert E Schapire. A desicion-theoretic generalization of on-line learning and an application to boosting. In European conference on computational learning theory, pages 23-37. Springer, 1995. Google Scholar
  16. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. Google Scholar
  17. Adam Kalai and Varun Kanade. Potential-based agnostic boosting. In Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta, editors, Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada., pages 880-888. Curran Associates, Inc., 2009. URL: http://papers.nips.cc/paper/3676-potential-based-agnostic-boosting.
  18. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777-1805, 2008. URL: http://dx.doi.org/10.1137/060649057.
  19. Daniel M. Kane, Adam R. Klivans, and Raghu Meka. Learning halfspaces under log-concave densities: Polynomial approximations and moment matching. In Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 522-545. JMLR.org, 2013. URL: http://jmlr.org/proceedings/papers/v30/Kane13.html.
  20. Adam R. Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning geometric concepts via gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 541-550. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.64.
  21. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. J. ACM, 35(4):965-984, 1988. Google Scholar
  22. Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random csps below the spectral threshold. CoRR, abs/1605.00058, 2016. Google Scholar
  23. Robert E. Schapire. The strength of weak learnability. Machine Learning, 5:197-227, 1990. URL: http://dx.doi.org/10.1007/BF00116037.
  24. Shai Shalev-Shwartz, Ohad Shamir, and Eran Tromer. Using more data to speed-up training time. In Neil D. Lawrence and Mark A. Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, April 21-23, 2012, volume 22 of JMLR Proceedings, pages 1019-1027. JMLR.org, 2012. URL: http://jmlr.csail.mit.edu/proceedings/papers/v22/shalev-shwartz12.html.
  25. Salil Vadhan. On learning vs. refutation. In Conference on Learning Theory, pages 1835-1848, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact