Abstract
We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose there exist functions \(\phi_1,\ldots,\phi_r:\{-1,1\}^n\to\Re\) with the property that every disjunction f on n variables has \(\|f-\sum_{i=1}^r\alpha_i\phi_i\|_\infty\leq 1/3\) for some reals α 1,...,α r . We prove that then \(r \geq 2^{\Omega(\sqrt{n})}.\) This lower bound is tight. We prove an incomparable lower bound for the concept class of linear-size DNF formulas. For the concept class of majority functions, we obtain a lower bound of Ω(2n/n), which almost meets the trivial upper bound of 2n for any concept class.
These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi and show that the regression-based agnostic learning algorithm of Kalai et al. is optimal. Our techniques involve a careful application of results in communication complexity due to Razborov and Buhrman et al.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N.: Problems and results in extremal combinatorics, Part I. Discrete Mathematics 273(1-3), 31–53 (2003)
Ben-David, S., Eiron, N., Simon, H.U.: Limitations of learning via embeddings in Euclidean half spaces. J. Mach. Learn. Res 3, 441–461 (2003)
Bshouty, N.H., Tamon, C.: On the Fourier spectrum of monotone functions. J. ACM 43(4), 747–770 (1996)
Buhrman, H., de Wolf, R.: Communication complexity lower bounds by polynomials. In: Conference on Computational Complexity (CCC), pp. 120–130 (2001)
Buhrman, H., Vereshchagin, N.K., de Wolf, R.: On computation and communication with small bias. In: 22nd IEEE Conference on Computational Complexity (2007)
Decatur, S.E.: Statistical queries and faulty PAC oracles. In: COLT, pp. 262–268 (1993)
Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci. 65(4), 612–625 (2002)
Forster, J., Simon, H.U.: On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theor. Comput. Sci. 350(1), 40–48 (2006)
Golub, G.H., Loan, C.F.V.: Matrix computations, 3rd edn. Johns Hopkins University Press, Baltimore, MD, USA (1996)
Jackson, J.C.: The harmonic sieve: A novel application of Fourier analysis to machine learning theory and practice. PhD thesis, Carnegie Mellon University (1995)
Kalai, A., Klivans, A., Mansour, Y., Servedio, R.: Agnostically learning halfspaces. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2005)
Kashin, B., Razborov, A.A.: Improved lower bounds on the rigidity of Hadamard matrices (In Russian). Matematicheskie zamet 63(4), 535–540 (1998)
Kearns, M.: Efficient noise-tolerant learning from statistical queries. In: STOC ’93: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp. 392–401. ACM Press, New York (1993)
Kearns, M., Li, M.: Learning in the presence of malicious errors. SIAM Journal on Computing 22(4), 807–837 (1993)
Kearns, M.J., Shapire, R.E., Sellie, L.M.: Toward efficient agnostic learning. Machine Learning 17(2–3), 115–141 (1994)
Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA (1994)
Klivans, A.R., O’Donnell, R., Servedio, R.A.: Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci. 68(4), 808–840 (2004)
Klivans, A.R., Servedio, R.: Learning DNF in time \(2^{\tilde{O}(n^{1/3})}\). In: STOC ’01: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 258–265. ACM Press, New York (2001)
Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. SIAM J. Comput. 22(6), 1331–1348 (1993)
Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)
Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. J. ACM 40(3), 607–620 (1993)
Linial, N., Mendelson, S., Schechtman, G., Shraibman, A.: Complexity measures of sign matrices. Combinatorica, (2006) To appear, Manuscript at http://www.cs.huji.ac.il/ñati/PAPERS/complexity_matrices.ps.gz
Linial, N., Shraibman, A.: Learning complexity vs. communication complexity. (December 2006) Manuscript at http://www.cs.huji.ac.il/ñati/PAPERS/lcc.pdf
Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. (December 2006) Manuscript at http://www.cs.huji.ac.il/~nati/PAPERS/ccfn.pdf
Lokam, S.V.: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. J. Comput. Syst. Sci. 63(3), 449–473 (2001)
Mansour, Y.: An O(n loglogn) learning algorithm for DNF under the uniform distribution. In: COLT ’92: Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 53–61. ACM Press, New York, USA (1992)
Mansour, Y., Parnas, M.: On learning conjunctions with malicious noise. In: ISTCS, pp. 170–175 (1996)
O’Donnell, R., Servedio, R.A.: Extremal properties of polynomial threshold functions. In: IEEE Conference on Computational Complexity, pp. 3–12 (2003)
Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions. In: STOC: ACM Symposium on Theory of Computing (STOC) (1992)
Razborov, A.A.: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, Mathematics 67, 145–159 (2002)
Rudin, W.: Principles of Mathematical Analysis, 3rd edn. McGraw-Hill, New York (1976)
Sherstov, A.A.: Halfspace matrices. In: Proc. of the 22nd Conference on Computational Complexity (CCC) (2007)
Sherstov, A.A.: Separating AC0 from depth-2 majority circuits. In: Proc. of the 39th Symposium on Theory of Computing (STOC) (2007)
Valiant, L.G.: Learning disjunctions of conjunctions. California 1, 560–566 (1985)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Klivans, A.R., Sherstov, A.A. (2007). A Lower Bound for Agnostically Learning Disjunctions. In: Bshouty, N.H., Gentile, C. (eds) Learning Theory. COLT 2007. Lecture Notes in Computer Science(), vol 4539. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72927-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-72927-3_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72925-9
Online ISBN: 978-3-540-72927-3
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
