Document Open Access Logo

Uniform Brackets, Containers, and Combinatorial Macbeath Regions

Authors Kunal Dutta , Arijit Ghosh, Shay Moran

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.59.pdf
  • Filesize: 0.62 MB
  • 10 pages

Document Identifiers

Author Details

Kunal Dutta
  • Department of Informatics, University of Warsaw, Poland
Arijit Ghosh
  • Indian Statistical Institute, Kolkata, India
Shay Moran
  • Technion – Israel Institute of Technology, Haifa, Israel
  • Google Research, Tel Aviv, Israel

Funding

  • Dutta, Kunal: Supported by the Polish NCN SONATA Grant no. 2019/35/D/ST6/04525.
  • Moran, Shay: Shay Moran is a Robert J. Shillman Fellow and his research is supported by the ISF, grant no. 1225/20, by an Azrieli Faculty Fellowship, and by BSF grant 2018385.

Cite AsGet BibTex

Kunal Dutta, Arijit Ghosh, and Shay Moran. Uniform Brackets, Containers, and Combinatorial Macbeath Regions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 59:1-59:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.59

Abstract

We study the connections between three seemingly different combinatorial structures - uniform brackets in statistics and probability theory, containers in online and distributed learning theory, and combinatorial Macbeath regions, or Mnets in discrete and computational geometry. We show that these three concepts are manifestations of a single combinatorial property that can be expressed under a unified framework along the lines of Vapnik-Chervonenkis type theory for uniform convergence. These new connections help us to bring tools from discrete and computational geometry to prove improved bounds for these objects. Our improved bounds help to get an optimal algorithm for distributed learning of halfspaces, an improved algorithm for the distributed convex set disjointness problem, and improved regret bounds for online algorithms against σ-smoothed adversary for a large class of semi-algebraic threshold functions.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • communication complexity
  • distributed learning
  • emperical process theory
  • online algorithms
  • discrete geometry
  • computational geometry

Metrics

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

Related Versions

References

  1. Terrence M. Adams and Andrew B. Nobel. Uniform Convergence of Vapnik–Chervonenkis Classes under Ergodic Sampling. Ann. Probab., 38(4):1345-1367, 2010. Google Scholar
  2. Noga Alon, David Haussler, and Emo Welzl. Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension. In Proceedings of the 3rd Annual Symposium on Computational Geometry, SoCG, pages 331-340, 1987. Google Scholar
  3. Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 852-860, 2019. Google Scholar
  4. Boris Aronov, Esther Ezra, and Micha Sharir. Small-size epsilon-nets for axis-parallel rectangles and boxes. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC, pages 639-648, 2009. Google Scholar
  5. Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 786-805, 2020. Google Scholar
  6. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. On the Combinatorial Complexity of Approximating Polytopes. Discrete & Computational Geometry, 58(4):849-870, 2017. Google Scholar
  7. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal Approximate Polytope Membership. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 270-288, 2017. Google Scholar
  8. Sunil Arya, David M. Mount, and Jian Xia. Tight Lower Bounds for Halfspace Range Searching. Discrete & Computational Geometry, 47(4):711-730, 2012. Google Scholar
  9. Maria-Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. Distributed Learning, Communication Complexity and Privacy. In Proceedings of 25th Annual Conference on Learning Theory, COLT, volume 23, pages 26.1-26.22, 2012. Google Scholar
  10. József Balogh, Robert Morris, and Wojciech Samotij. Independent Sets in Hypergraphs. Journal of the American Mathematical Society, 28(3):669-709, 2015. Google Scholar
  11. Imre Bárány. The Technique of M-Regions and Cap-Coverings: A Survey. Rend. Circ. Mat. Palermo, 65:21-38, 2000. Google Scholar
  12. Imre Bárány. Extremal Problems for Convex Lattice Polytopes: A Survey. Contemp. Math., 453:87-103, 2008. Google Scholar
  13. Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic Online Learning. In Proceedings of the 22nd Annual Conference on Learning Theory, COLT, 2009. Google Scholar
  14. Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh R. Saxena. Near Optimal Distributed Learning of Halfspaces with Two Parties. In Proceedings of the 34th Annual Conference on Learning Theory, COLT, volume 134, pages 724-758, 2021. Google Scholar
  15. Hervé Brönnimann, Bernard Chazelle, and János Pach. How hard is half-space range searching. Discrete & Computational Geometry, 10:143-155, 1993. Google Scholar
  16. Mark Bun, Roi Livni, and Shay Moran. An Equivalence Between Private Classification and Online Prediction. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 389-402, 2020. Google Scholar
  17. Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted Capacitated, Priority, and Geometric Set Cover via Improved Quasi-Uniform Sampling. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1576-1585, 2012. Google Scholar
  18. Edward Y. Chang, Kaihua Zhu, Hao Wang, Hongjie Bai, Jian Li, Zhihuan Qiu, and Hang Cui. Parallelizing Support Vector Machines on Distributed Computers. In Proceedings of the 21st Annual Conference on Neural Information Processing Systems, NIPS, pages 257-264, 2007. Google Scholar
  19. Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning. Discrete & Computational Geometry, 61(4):756-777, 2019. Google Scholar
  20. Kunal Dutta, Arijit Ghosh, and Shay Moran. Uniform Brackets, Containers, and Combinatorial Macbeath Regions. CoRR, abs/2111.10048, 2021. URL: http://arxiv.org/abs/2111.10048.
  21. Pedro A. Forero, Alfonso Cano, and Georgios B. Giannakis. Consensus-Based Distributed Support Vector Machines. Journal of Machine Learning Research, 11:1663-1707, 2010. Google Scholar
  22. Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. Google Scholar
  23. Hal Daumé III, Jeff M. Phillips, Avishek Saha, and Suresh Venkatasubramanian. Efficient Protocols for Distributed Classification and Optimization. In Proceedings of 23rd International Conference on Algorithmic Learning Theory, ALT, volume 7568, pages 154-168, 2012. Google Scholar
  24. Daniel Kane, Roi Livni, Shay Moran, and Amir Yehudayoff. On Communication Complexity of Classification Problems. In Proceedings of the 32nd Annual Conference on Learning Theory, COLT, volume 99, pages 1903-1943, 2019. Google Scholar
  25. Nick Littlestone. Learning Quickly when Irrelevant Attributes Abound: A New Linear-threshold Algorithm. Machine Learning, 2:285-318, 1988. Google Scholar
  26. A. M. Macbeath. A Theorem on Non-Homogeneous Lattices. Annals of Mathematics, 56:269-293, 1952. Google Scholar
  27. Ryan T. McDonald, Keith B. Hall, and Gideon Mann. Distributed Training Strategies for the Structured Perceptron. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 2-4, 2010, Los Angeles, California, USA, pages 456-464, 2010. Google Scholar
  28. N. H. Mustafa and S. Ray. ε -Mnets: Hitting Geometric Set Systems with Subsets. Discrete & Computational Geometry, 57(3):625-640, 2017. Google Scholar
  29. Nabil H. Mustafa, Kunal Dutta, and Arijit Ghosh. A Simple Proof of Optimal Epsilon-nets. Combinatorica, 38(5):1269-1277, 2018. Google Scholar
  30. Nabil H. Mustafa and Kasturi R. Varadarajan. Epsilon-approximations and epsilon-nets. CoRR, abs/1702.03676, 2017. URL: http://arxiv.org/abs/1702.03676.
  31. F. Roosenblatt. A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review, pages 65-386, 1958. Google Scholar
  32. David Saxton and Andrew Thomason. Hypergraph Containers. Inventiones Mathematicae, 201(3):925-992, 2015. Google Scholar
  33. Daniel A. Spielman and Shang-Hua Teng. Smoothed Analysis of Algorithms: Why the Simplex Algorithm usually takes Polynomial Time. Journal of the ACM, 51(3):385-463, 2004. Google Scholar
  34. Ramon van Handel. The Universal Glivenko–Cantelli Property. Probability Theory and Related Fields, 155:911-934, 2013. Google Scholar
  35. V. N. Vapnik and A. Y. Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971. Google Scholar
  36. Kasturi R. Varadarajan. Weighted Geometric Set Cover via Quasi-Uniform Sampling. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pages 641-648, 2010. Google Scholar
  37. Santosh S. Vempala, Ruosong Wang, and David P. Woodruff. The Communication Complexity of Optimization. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1733-1752, 2020. 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 Imprint Privacy Contact