DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.29

Agnostically Learning Boolean Functions with Finite Polynomial Representation

Authors: Ning Ding

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

Agnostic learning is an extremely hard task in computational learning theory. In this paper we revisit the results in [Kalai et al. SIAM J. Comput. 2008] on agnostically learning boolean functions with finite polynomial representation and those that can be approximated by the former. An example of the former is the class of all boolean low-degree polynomials. For the former, [Kalai et al. SIAM J. Comput. 2008] introduces the l_1-polynomial regression method to learn them to error opt+epsilon. We present a simple instantiation for one step in the method and accordingly give the analysis. Moreover, we show that even ignoring this step can bring a learning result of error 2opt+epsilon as well. Then we consider applying the result for learning concept classes that can be approximated by the former to learn richer specific classes. Our result is that the class of s-term DNF formulae can be agnostically learned to error opt+epsilon with respect to arbitrary distributions for any epsilon in time poly(n^d, 1/epsilon), where d=O(\sqrt{n}\cdot s\cdot \log s\log^2(1/epsilon)).

Cite as

Ning Ding. Agnostically Learning Boolean Functions with Finite Polynomial Representation. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 29:1-29:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ding:LIPIcs.ISAAC.2017.29,
  author =	{Ding, Ning},
  title =	{{Agnostically Learning Boolean Functions with Finite Polynomial Representation}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{29:1--29:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.29},
  URN =		{urn:nbn:de:0030-drops-82726},
  doi =		{10.4230/LIPIcs.ISAAC.2017.29},
  annote =	{Keywords: Agnostic Learning, Boolean Functions, Low-Degree Polynomials}
}

Search Results

Documents authored by Ding, Ning

Agnostically Learning Boolean Functions with Finite Polynomial Representation

Abstract

Cite as

Thanks for your feedback!

Could not send message