Document Open Access Logo

Sample-Based High-Dimensional Convexity Testing

Authors Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.37.pdf
  • Filesize: 0.73 MB
  • 20 pages

Document Identifiers

Author Details

Xi Chen
Adam Freilich
Rocco A. Servedio
Timothy Sun

Cite As Get BibTex

Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-Based High-Dimensional Convexity Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.37

Abstract

In the problem of high-dimensional convexity testing, there is an unknown set S in the n-dimensional Euclidean space which is promised to be either convex or c-far from every convex body with respect to the standard multivariate normal distribution. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set S as possible.

In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples (x,S(x)) where each x is independently drawn from the normal distribution. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant c, our results show that the sample complexity of one-sided convexity testing is exponential in n, while for two-sided convexity testing it is exponential in the square root of n.

Subject Classification

Keywords
  • Property testing
  • convexity
  • sample-based testing

Metrics

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

References

  1. Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In Advances in Neural Information Processing Systems 28 (NIPS), pages 3591-3599, 2015. Google Scholar
  2. Michal Adamaszek, Artur Czumaj, and Christian Sohler. Testing monotone continuous distributions on high-dimensional real cubes. In SODA, pages 56-65, 2010. Google Scholar
  3. N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing Reed-Muller Codes. IEEE Transactions on Information Theory, 51(11):4032-4039, 2005. Google Scholar
  4. Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 496-505, 2007. Google Scholar
  5. Noga Alon, Rani Hod, and Amit Weinstein. On active and passive testing. Combinatorics, Probability & Computing, 25(1):1-20, 2016. Google Scholar
  6. Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 21-30, 2012. Google Scholar
  7. K. Ball. The Reverse Isoperimetric Problem for Gaussian Measure. Discrete and Computational Geometry, 10:411-420, 1993. Google Scholar
  8. Keith Ball. An elementary introduction to modern convex geometry. In Flavors of Geometry, pages 1-58. MSRI Publications, 1997. Google Scholar
  9. Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the 36th Symposium on Theory of Computing, pages 381-390, 2004. Google Scholar
  10. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The power and limitations of uniform samples in testing properties of figures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, pages 45:1-45:14, 2016. Google Scholar
  11. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing convexity of figures under the uniform distribution. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 17:1-17:15, 2016. Google Scholar
  12. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant testers of image properties. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 90:1-90:14, 2016. Google Scholar
  13. Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. Testing monotonicity of distributions over general partial orders. In ICS, pages 239-252, 2011. Google Scholar
  14. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pages 488-497, 2010. Google Scholar
  15. Eric Blais. Testing juntas nearly optimally. In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), pages 151-158, 2009. URL: http://dx.doi.org/10.1145/1536414.1536437.
  16. Eric Blais and Yuichi Yoshida. A characterization of constant-sample testable properties. CoRR, abs/1612.06016, 2016. URL: http://arxiv.org/abs/1612.06016.
  17. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47:549-595, 1993. Earlier version in STOC'90. Google Scholar
  18. Artur Czumaj and Christian Sohler. Property testing with geometric queries. In Algorithms - ESA 2001, 9th Annual European Symposium, pages 266-277, 2001. Google Scholar
  19. Artur Czumaj, Christian Sohler, and Martin Ziegler. Property testing in computational geometry. In Algorithms - ESA 2000, 8th Annual European Symposium, pages 155-166, 2000. Google Scholar
  20. O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. Combinatorica, 20(3):301-337, 2000. Google Scholar
  21. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45:653-750, 1998. Google Scholar
  22. Oded Goldreich and Dana Ron. On sample-based testers. TOCT, 8(2):7:1-7:54, 2016. Google Scholar
  23. Oded Goldreich and Madhu Sudan. Locally testable codes and pcps of almost-linear length. J. ACM, 53(4):558-655, 2006. Google Scholar
  24. P.M. Gruber and J.M. Wills, editors. Handbook of convex geometry, Volume A. Elsevier, New York, 1993. Google Scholar
  25. Iain M. Johnstone. Chi-square oracle inequalities. In State of the art in probability and statistics, pages 399-418. Institute of Mathematical Statistics, 2001. Google Scholar
  26. Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 403-412, 2008. Google Scholar
  27. M. Kearns and D. Ron. Testing problems with sub-learning sample complexity. Journal of Computer and System Sciences, 61:428-456, 2000. Google Scholar
  28. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric type theorems. To appear in FOCS, 2015. Google Scholar
  29. A. Klivans, R. O'Donnell, and R. Servedio. Agnostically learning convex sets via perimeter. manuscript, 2007. Google Scholar
  30. Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, and Chenggang Wu. Testing surface area. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1204-1214, 2014. Google Scholar
  31. K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. Testing halfspaces. SIAM J. on Comput., 39(5):2004-2047, 2010. Google Scholar
  32. F. Nazarov. On the maximal perimeter of a convex set in Rⁿ with respect to a Gaussian measure. In Geometric aspects of functional analysis (2001-2002), pages 169-187. Lecture Notes in Math., Vol. 1807, Springer, 2003. Google Scholar
  33. Joe Neeman. Testing surface area with arbitrary accuracy. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 393-397, 2014. Google Scholar
  34. M. Parnas, D. Ron, and A. Samorodnitsky. Testing Basic Boolean Formulae. SIAM J. Disc. Math., 16:20-46, 2002. URL: https://citeseer.ifi.unizh.ch/parnas02testing.html.
  35. Luis Rademacher and Santosh Vempala. Testing geometric convexity. In FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science: 24th International Conference, Chennai, India, December 16-18, 2004. Proceedings, pages 469-480, 2005. Google Scholar
  36. Sofya Raskhodnikova. Approximate testing of visual properties. In Proceedings of RANDOM, pages 370-381, 2003. Google Scholar
  37. R. Rubinfeld and R. Servedio. Testing monotone high-dimensional distributions. In Proc. 37th Annual ACM Symposium on Theory of Computing (STOC), pages 147-156, 2005. Google Scholar
  38. Ronitt Rubinfeld and Ning Xie. Testing non-uniform k-wise independent distributions over product spaces. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, pages 565-581, 2010. Google Scholar
  39. Stanislaw J. Szarek. Convexity, complexity, and high dimensions. In Proceedings of the International Congress of Mathematicians, Madrid, Spain, pages 1599-1621. European Mathematical Society, 2006. 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 About DROPS Imprint Privacy Contact