article

Learning complexity vs communication complexity

Authors:

Adi ShraibmanAuthors Info & Claims

Combinatorics, Probability and Computing, Volume 18, Issue 1-2

Pages 227 - 245

https://doi.org/10.1017/S0963548308009656

Published: 01 March 2009 Publication History

Abstract

This paper has two main focal points. We first consider an important class of machine learning algorithms: large margin classifiers, such as Support Vector Machines. The notion of margin complexity quantifies the extent to which a given class of functions can be learned by large margin classifiers. We prove that up to a small multiplicative constant, margin complexity is equal to the inverse of discrepancy. This establishes a strong tie between seemingly very different notions from two distinct areas.

In the same way that matrix rigidity is related to rank, we introduce the notion of rigidity of margin complexity. We prove that sign matrices with small margin complexity rigidity are very rare. This leads to the question of proving lower bounds on the rigidity of margin complexity. Quite surprisingly, this question turns out to be closely related to basic open problems in communication complexity, e.g., whether PSPACE can be separated from the polynomial hierarchy in communication complexity.

Communication is a key ingredient in many types of learning. This explains the relations between the field of learning theory and that of communication complexity [6, l0, 16, 26]. The results of this paper constitute another link in this rich web of relations. These new results have already been applied toward the solution of several open problems in communication complexity [18, 20, 29].

References

[1]

Aho, A. V., Ullman, J. D. and Yannakakis, M. (1983) On notions of information transfer in VLSI circuits. In Proc. 15th ACM STOC, pp. 133-139.

Digital Library

[2]

Alon, N. (1995) Tools from higher algebra. In Handbook of Combinatorics, Vol. 1, North-Holland, pp. 1749-1783.

Digital Library

[3]

Alon, N., Frankl, P. and Rödl, V. (1985) Geometrical realizations of set systems and probabilistic communication complexity. In Proc. 26th Symposium on Foundations of Computer Science, IEEE Computer Society Press, pp. 277-280.

Digital Library

[4]

Alon, N. and Naor, A. (2004) Approximating the cut-norm via Grothendieck's inequality. In Proc. 36th ACM STOC, pp. 72-80.

Digital Library

[5]

Babai, L., Frankl, P. and Simon, J. (1986) Complexity classes in communication complexity. In Proc. 27th IEEE Symposium on Foundations of Computer Science, pp. 337-347.

Digital Library

[6]

Ben-David, S., Eiron, N. and Simon, H. U. (2002) Limitations of learning via embeddings in Euclidean half spaces. J. Machine Learning Research 3 441-461.

Digital Library

[7]

Chazelle, B. (2000) The Discrepancy Method: Randomness and Complexity, Cambridge University Press.

Digital Library

[8]

Cristianini, N. and Shawe-Taylor, J. (1999) An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge University Press. New York.

Digital Library

[9]

Forster, J. (2001) A linear lower bound on the unbounded error probabilistic communication complexity. In SCT: Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, pp. 100-106.

Digital Library

[10]

Forster, J., Krause, M., Lokam, S. V., Mubarakzjanov, R., Schmitt, N. and Simon, H. U. (2001) Relations between communication complexity, linear arrangements, and computational complexity. In Proc. 21st Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 171-182.

Digital Library

[11]

Forster, J., Schmitt, N. and Simon, H. U. (2001) Estimating the optimal margins of embeddings in Euclidean half spaces. In Proc. 14th Annual Conference on Computational Learning Theory (COLT 2001) and 5th European Conference on Computational Learning Theory (EuroCOLT 2001), Vol. 2111 of Lecture Notes in Computer Science, Springer, Berlin, pp. 402-415.

Digital Library

[12]

Forster, J. and Simon, H. U. (2006) On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theor. Comput. Sci. 350 40-48.

Digital Library

[13]

Jameson, G. J. O. (1987) Summing and Nuclear Norms in Banach Space Theory, London Mathematical Society Student Texts, Cambridge University Press.

[14]

Johnson, W. B. and Lindenstrauss, J. (1984) Extensions of Lipshitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, AMS, Providence, RI, pp. 189-206.

[15]

Kashin, B. and Razborov, A. (1998) Improved lower bounds on the rigidity of Hadamard matrices. Mathematical Notes 63 471-475.

[16]

Kremer, I., Nisan, N. and Ron, D. (1995) On randomized one-round communication complexity. In Proc. 35th IEEE FOCS, pp. 596-605.

Digital Library

[17]

Kushilevitz, E. and Nisan, N. (1997) Communication Complexity, Cambridge University Press.

Digital Library

[18]

Lee, T., Shraibman, A. and ¿palek, R. (2008) A direct product theorem for discrepancy. In Annual IEEE Conference on Computational Complexity, pp. 71-80.

Digital Library

[19]

Linial, N., Mendelson, S., Schechtman, G. and Shraibman, A. (2007) Complexity measures of sign matrices. Combinatorica 27 439-463.

Digital Library

[20]

Linial, N. and Shraibman, A. (2007) Lower bounds in communication complexity based on factorization norms. In Proc. 39th ACM STOC, pp. 699-708.

Digital Library

[21]

Lokam, S. V. (1995) Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity. In IEEE Symposium on Foundations of Computer Science, pp. 6-15.

Digital Library

[22]

Matou¿ek, J. (1999) Geometric Discrepancy: An Illustrated Guide, Vol. 18 of Algorithms and Combinatorics, Springer.

[23]

Matou¿ek, J. (2002) Lectures on Discrete Geometry, Vol. 212 of Graduate Texts in Mathematics, Springer.

Digital Library

[24]

Mendelson, S. (2005) Embeddings with a Lipschitz function. Random Struct. Alg. 27 25-45.

Digital Library

[25]

Mendelson, S. (2005) On the limitations of embedding methods. In Proc. 18th Annual Conference on Learning Theory (COLT05), Vol. 3559 of Lecture Notes in Computer Science, Springer, pp. 353-365.

Digital Library

[26]

Paturi, R. and Simon, J. (1986) Probabilistic communication complexity. J. Comput. Syst. Sci. 33 106- 123.

Digital Library

[27]

Pisier, G. (1986) Factorization of Linear Operators and Geometry of Banach Spaces, Vol. 60 of CBMS Regional Conference Series in Mathematics, Published for the Conference Board of the Mathematical Sciences, Washington, DC.

[28]

Pudlák, P. and Rödl, V. (1994) Some combinatorial-algebraic problems from complexity theory. Discrete Math. 136 253-279.

Digital Library

[29]

Sherstov, A. A. (2008) Communication complexity under product and nonproduct distributions. In Annual IEEE Conference on Computational Complexity, pp. 64-70.

Digital Library

[30]

Shokrollahi, M. A., Spielman, D. A. and Stemann, V. (1997) A remark on matrix rigidity. Inform. Process. Lett. 64 283-285.

Digital Library

[31]

Tarui, J. (1993) Randomized polynomials, threshold circuits and polynomial hierarchy. Theoret. Comput. Sci. 113 167-183.

Digital Library

[32]

Valiant, L. G. (1977) Graph-theoretic arguments in low level complexity. In Proc. 6th MFCS, Vol. 53 of Lecture Notes in Computer Science, Springer, pp. 162-176.

[33]

Vapnik, V. N. (1999) The Nature of Statistical Learning Theory, Springer, New York.

Digital Library

[34]

Yao, A. (1983) Lower bounds by probabilistic arguments. In Proc. 15th ACM STOC, pp. 420-428.

Digital Library

Cited By

Zhu XTian YHuang ZBaeza-Yates RBonchi F(2024)Distributed Thresholded Counting with Limited InteractionProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671868(4664-4675)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671868
Fang YHambardzumyan LHarms NHatami PMohar BShinkar IO'Donnell R(2024)No Complete Problem for Constant-Cost Randomized CommunicationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649716(1287-1298)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649716
Gál ASyed R(2024)Upper Bounds on Communication in Terms of Approximate RankTheory of Computing Systems10.1007/s00224-023-10158-468:5(1109-1123)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00224-023-10158-4
Show More Cited By

Index Terms

Learning complexity vs communication complexity
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms

Recommendations

Learning Complexity vs. Communication Complexity
CCC '08: Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity

This paper has two main focal points. We first consider an important class of machine learning algorithms - large margin classifiers, such as Support Vector Machines. The notion of {\emmargin complexity} quantifies the extent to which a given class of ...
The Landscape of Communication Complexity Classes

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$P and $${\mathsf{PSPACE}}$$PSPACE, short of proving lower bounds ...
From average case complexity to improper learning complexity
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are effficiently learnable. There is presently a dearth of results showing hardness of learning problems. Moreover, the existing lower bounds ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Combinatorics, Probability and Computing

Combinatorics, Probability and Computing Volume 18, Issue 1-2

March 2009

301 pages

ISSN:0963-5483

Issue’s Table of Contents

Publisher

Cambridge University Press

United States

Publication History

Published: 01 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu XTian YHuang ZBaeza-Yates RBonchi F(2024)Distributed Thresholded Counting with Limited InteractionProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671868(4664-4675)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671868
Fang YHambardzumyan LHarms NHatami PMohar BShinkar IO'Donnell R(2024)No Complete Problem for Constant-Cost Randomized CommunicationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649716(1287-1298)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649716
Gál ASyed R(2024)Upper Bounds on Communication in Terms of Approximate RankTheory of Computing Systems10.1007/s00224-023-10158-468:5(1109-1123)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00224-023-10158-4
Hatami HHosseini KMeng XSaha BServedio R(2023)A Borsuk-Ulam Lower Bound for Sign-Rank and Its ApplicationsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585210(463-471)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585210
Gál ASyed R(2021)Upper Bounds on Communication in Terms of Approximate RankComputer Science – Theory and Applications10.1007/978-3-030-79416-3_7(116-130)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-79416-3_7
Hatami HHosseini KLovett SAceto L(2020)Sign rank vs discrepancyProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.18(1-14)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.18
Dagan YFeldman VMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Interaction is necessary for distributed learning with privacy or communication constraintsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384315(450-462)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384315
Daniely AFeldman VWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Locally private learning without interaction requires separationProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455630(15001-15012)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455630
Göös MPitassi TWatson T(2018)The Landscape of Communication Complexity ClassesComputational Complexity10.1007/s00037-018-0166-627:2(245-304)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00037-018-0166-6
Alman JWilliams RHatami HMcKenzie PKing V(2017)Probabilistic rank and matrix rigidityProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055484(641-652)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055484
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents