Document Open Access Logo

Active Learning a Convex Body in Low Dimensions

Authors Sariel Har-Peled, Mitchell Jones, Saladi Rahul

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.64.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Sariel Har-Peled
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA
Mitchell Jones
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA
Saladi Rahul
  • Dept. of Computer Science and Automation, Indian Institute of Science, Bangalore, India

Funding

  • Har-Peled, Sariel: Supported in part by NSF AF award CCF-1907400.
  • Jones, Mitchell: Supported in part by NSF AF award CCF-1907400.

Cite As Get BibTex

Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. Active Learning a Convex Body in Low Dimensions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.64

Abstract

Consider a set P ⊆ ℝ^d of n points, and a convex body C provided via a separation oracle. The task at hand is to decide for each point of P if it is in C using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using O(⬡_P log n) queries, where ⬡_P is the largest subset of points of P in convex position. In 2D, we provide an algorithm which efficiently generates these adaptive queries.
Furthermore, we show that in two dimensions one can solve this problem using O(⊚(P,C) log² n) oracle queries, where ⊚(P,C) is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if C contains all points of P.
As an application of the above, we show that the discrete geometric median of a point set P in ℝ² can be computed in O(n log² n (log n log log n + ⬡(P))) expected time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Approximation algorithms
  • computational geometry
  • separation oracles
  • active learning

Metrics

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

Related Versions

References

  1. G. Ambrus and I. Bárány. Longest convex chains. Rand. Struct. & Alg., 35(2):137-162, 2009. URL: https://doi.org/10.1002/rsa.20269.
  2. Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1987. URL: https://doi.org/10.1007/BF00116828.
  3. Imre Bárány and Zoltán Füredi. Computing the volume is difficulte. Discrete Comput. Geom., 2:319-326, 1987. URL: https://doi.org/10.1007/BF02187886.
  4. T. M. Chan. An optimal randomized algorithm for maximum Tukey depth. In J. Ian Munro, editor, Proc. 15th ACM-SIAM Sympos. Discrete Algs. (SODA), pages 430-436. SIAM, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982853.
  5. Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Daniel Wichs and Yishay Mansour, editors, Proc. 48th ACM Sympos. Theory Comput. (STOC), pages 9-21. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897647.
  6. David A. Cohn, Les E. Atlas, and Richard E. Ladner. Improving generalization with active learning. Machine Learning, 15(2):201-221, 1994. URL: https://doi.org/10.1007/BF00993277.
  7. Esther Ezra and Micha Sharir. A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. Discrete Comput. Geom., 61(4):735-755, 2019. URL: https://doi.org/10.1007/s00454-018-0043-8.
  8. Juan Ferrera. An introduction to nonsmooth analysis. Academic Press, Boston, 2013. URL: https://doi.org/10.1016/C2013-0-15234-8.
  9. Yuhong Guo and Russell Greiner. Optimistic active-learning using mutual information. In Proc. 20th Int. Joint Conf. on AI (IJCAI), pages 823-829, 2007. URL: http://ijcai.org/Proceedings/07/Papers/132.pdf.
  10. S. Har-Peled, M. Jones, and S. Rahul. An animation of the greedy classification algorithm in 2d. URL: https://www.youtube.com/watch?v=IZX0VQdIgNA.
  11. S. Har-Peled, N. Kumar, D. M. Mount, and B. Raichel. Space exploration via proximity search. Discrete Comput. Geom., 56(2):357-376, 2016. URL: https://doi.org/10.1007/s00454-016-9801-7.
  12. Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. Active learning a convex body in low dimensions. CoRR, abs/1903.03693, 2019. URL: http://arxiv.org/abs/1903.03693.
  13. David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. URL: https://doi.org/10.1007/BF02187876.
  14. Daniel M. Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In Proc. 58th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 355-366, 2017. URL: https://doi.org/10.1109/FOCS.2017.40.
  15. Andrey Kupavskii. The vc-dimension of k-vertex d-polytopes. CoRR, abs/2004.04841, 2020. URL: http://arxiv.org/abs/2004.04841.
  16. J. Matoušek and U. Wagner. New constructions of weak epsilon-nets. In Proceedings of the nineteenth annual symposium on Computational geometry, pages 129-135. ACM, 2003. Google Scholar
  17. Kurt Mehlhorn and Stefan Näher. Dynamic fractional cascading. Algorithmica, 5(2):215-241, 1990. URL: https://doi.org/10.1007/BF01840386.
  18. F. Panahi, A. Adler, A. F. van der Stappen, and K. Goldberg. An efficient proximity probing algorithm for metrology. In Int. Conf. on Automation Science and Engineering, CASE 2013, pages 342-349, 2013. URL: https://doi.org/10.1109/CoASE.2013.6653995.
  19. Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, 1985. URL: https://doi.org/10.1007/978-1-4612-1098-6.
  20. Natan Rubin. An improved bound for weak epsilon-nets in the plane. In Mikkel Thorup, editor, Proc. 59th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 224-235. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00030.
  21. Burr Settles. Active learning literature survey. Technical Report #1648, Computer Science, Univ. Wisconsin, Madison, January 2009. URL: https://minds.wisconsin.edu/bitstream/handle/1793/60660/TR1648.pdf?sequence=1&isAllowed=y.
  22. V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971. Google Scholar
  23. Wolfgang Weil, editor. Random Polytopes, Convex Bodies, and Approximation, pages 77-118. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. URL: https://doi.org/10.1007/978-3-540-38175-4_2.
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