Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Foundations of Computational Mathematics
Published in:

11-10-2022

Adversarial Manifold Estimation

Authors: Eddie Aamari, Alexander Knop

Published in: Foundations of Computational Mathematics | Issue 1/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper studies the statistical query (SQ) complexity of estimating d-dimensional submanifolds in \({\mathbb {R}}^n\). We propose a purely geometric algorithm called manifold propagation, that reduces the problem to three natural geometric routines: projection, tangent space estimation, and point detection. We then provide constructions of these geometric routines in the SQ framework. Given an adversarial \(\mathrm {STAT}(\tau )\) oracle and a target Hausdorff distance precision \(\varepsilon = \Omega (\tau ^{2 / (d + 1)})\), the resulting SQ manifold reconstruction algorithm has query complexity \({\tilde{O}}(n \varepsilon ^{-d / 2})\), which is proved to be nearly optimal. In the process, we establish low-rank matrix completion results for SQ’s and lower bounds for randomized SQ estimators in general metric spaces.
next article The Bubble Transform and the de Rham Complex

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
As the present paper uses \(\varepsilon \) for precision, we use \(\delta \) as the privacy parameter, contrary to the standard notation.
 
Literature
1.
Ery Arias-Castro, Gilad Lerman, and Teng Zhang. Spectral clustering based on local PCA. J. Mach. Learn. Res., 18:Paper No. 9, 57, 2017.
2.
Ery Arias-Castro and Bruno Pelletier. On the convergence of maximum variance unfolding. J. Mach. Learn. Res., 14:1747–1770, 2013.MathSciNet
3.
4.
Eddie Aamari and Alexander Knop. Statistical query complexity of manifold estimation. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 116–122, New York, NY, USA, 2021. Association for Computing Machinery.
5.
Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman. Estimating the reach of a manifold. Electron. J. Stat., 13(1):1359–1399, 2019.MathSciNetCrossRef
6.
Eddie Aamari and Clément Levrard. Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction. Discrete Comput. Geom., 59(4):923–971, 2018.MathSciNetCrossRef
7.
Eddie Aamari and Clément Levrard. Nonasymptotic rates for manifold, tangent space and curvature estimation. Ann. Statist., 47(1):177–204, 2019.MathSciNetCrossRef
8.
9.
10.
Dmitri Burago, Yuri Burago, and Sergei Ivanov. A course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001.
11.
Shai Ben-David and Eli Dichterman. Learning with restricted focus of attention. J. Comput. Syst. Sci., 56(3):277–298, 1998.MathSciNetCrossRef
12.
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94, page 253–262, New York, NY, USA, 1994. Association for Computing Machinery.
13.
Jean-Daniel Boissonnat and Arijit Ghosh. Manifold reconstruction using tangential Delaunay complexes. Discrete Comput. Geom., 51(1):221–267, 2014.MathSciNetCrossRef
14.
Clément Berenfeld, John Harvey, Marc Hoffmann, and Krishnan Shankar. Estimating the reach of a manifold via its convexity defect function. Discrete Comput. Geom., 67(2):403–438, 2022.MathSciNetCrossRefPubMed
15.
Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken. Sampling and Meshing Submanifolds in High Dimension. working paper or preprint, November 2019.
16.
Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. J. Appl. Comput. Topol., 3(1-2):29–58, 2019.MathSciNetCrossRefPubMedPubMedCentral
17.
Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994, New Brunswick, NJ, USA, July 12-15, 1994, pages 340–347, 1994.
18.
Antonio Cuevas and Ricardo Fraiman. A plug-in approach to support estimation. Ann. Statist., 25(6):2300–2312, 1997.MathSciNetCrossRef
19.
Manfredo Perdigão do Carmo. Riemannian geometry. Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the second Portuguese edition by Francis Flaherty.
20.
Tamal K. Dey. Curve and surface reconstruction: algorithms with mathematical analysis, volume 23 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2007.
21.
Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, and Karl Wimmer. Approximate resilience, monotonicity, and the complexity of agnostic learning. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 498–511. SIAM, 2015.
22.
23.
24.
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 73–84. IEEE Computer Society, 2017.
25.
Giuseppe De Marco, Gianluca Gorni, and Gaetano Zampieri. Global inversion of functions: an introduction. NoDEA Nonlinear Differential Equations Appl., 1(3):229–248, 1994.MathSciNetCrossRef
26.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, volume 3876 of Lecture Notes in Comput. Sci., pages 265–284. Springer, Berlin, 2006.
27.
John Dunagan and Santosh S. Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program., 114(1):101–114, 2008.MathSciNetCrossRef
28.
29.
Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 211–222. ACM, 2003.
30.
Maryam Fazel, Emmanuel Candès, Benjamin Recht, and Pablo Parrilo. Compressed sensing and robust recovery of low rank matrices. In in Proc. 40th Asilomar Conf. Signals, Systems and Computers, 2008.
31.
32.
Herbert Federer. Geometric measure theory. Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag New York Inc., New York, 1969.
33.
Vitaly Feldman. A general characterization of the statistical query complexity. In Proceedings of Machine Learning Research, volume 65, pages 785–830, Amsterdam, Netherlands, 2017.
34.
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2):8:1–8:37, 2017.MathSciNetCrossRef
35.
Vitaly Feldman, Cristóbal Guzmán, and Santosh Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. Math. Oper. Res., 46(3):912–945, 2021.MathSciNetCrossRef
36.
Charles Fefferman, Sergei Ivanov, Matti Lassas, and Hariharan Narayanan. Fitting a manifold of large reach to noisy data. arXiv:​1910.​05084, October 2019.
37.
Vitaly Feldman, Will Perkins, and Santosh S. Vempala. On the complexity of random satisfiability problems with planted solutions. SIAM J. Comput., 47(4):1294–1338, 2018.MathSciNetCrossRef
38.
Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman. Manifold estimation and singular deconvolution under Hausdorff loss. Ann. Statist., 40(2):941–963, 2012.MathSciNetCrossRef
39.
Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman. Minimax manifold estimation. J. Mach. Learn. Res., 13:1263–1291, 2012.MathSciNet
40.
Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002.
41.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. Springer Series in Statistics. Springer, New York, second edition, 2009. Data mining, inference, and prediction.
42.
43.
Noah M. Johnson, Joseph P. Near, and Dawn Song. Towards practical differential privacy for SQL queries. Proc. VLDB Endow., 11(5):526–539, 2018.CrossRef
44.
45.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793–826, 2011.MathSciNetCrossRef
46.
Arlene K. H. Kim and Harrison H. Zhou. Tight minimax rates for manifold estimation under Hausdorff loss. Electron. J. Stat., 9(1):1562–1582, 2015.MathSciNetCrossRef
47.
William E. Lorensen and Harvey E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’87, page 163–169, New York, NY, USA, 1987. Association for Computing Machinery.
48.
Yi-Kai Liu. Universal low-rank matrix recovery from pauli measurements. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., Red Hook, 2011.
49.
John A. Lee and Michel Verleysen. Nonlinear dimensionality reduction. Information Science and Statistics. Springer, New York, 2007.
50.
Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39(1-3):419–441, 2008.MathSciNetCrossRef
51.
Nikita Puchkin and Vladimir Spokoiny. Structure-adaptive manifold estimation. Journal of Machine Learning Research, 23(40):1–62, 2022.MathSciNet
52.
Sam T. Roweis and Lawrence K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000.ADSCrossRefPubMed
53.
Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. Linkedin’s audience engagements API: A privacy preserving data analytics system at scale. CoRR, abs/2002.05839, 2020.
54.
55.
Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 1490–1516. JMLR.org, 2016.
56.
Joshua B. Tenenbaum. Mapping a manifold of perceptual observations. In Michael I. Jordan, Michael J. Kearns, and Sara A. Solla, editors, Advances in Neural Information Processing Systems 10, [NIPS Conference, Denver, Colorado, USA, 1997], pages 682–688. The MIT Press, Cambridge, 1997.
57.
Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984.CrossRef
58.
Karsten A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Mark A. Fulk and John Case, editors, Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990, University of Rochester, Rochester, NY, USA, August 6-8, 1990, pages 314–326. Morgan Kaufmann, Burlington, 1990.
59.
Martin J. Wainwright. Constrained forms of statistical minimax: computation, communication, and privacy. In Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, pages 273–290. Kyung Moon Sa, Seoul, 2014.
60.
Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965.CrossRefPubMed
61.
62.
Bin Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997.
63.
Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102(2):315–323, 2015.MathSciNetCrossRef
Metadata
Title
Adversarial Manifold Estimation
Authors
Eddie Aamari
Alexander Knop
Publication date
11-10-2022
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 1/2024
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-022-09588-2

Other articles of this Issue 1/2024

Covariance’s Loss is Privacy’s Gain: Computationally Efficient, Private and Accurate Synthetic Data

  • Open Access

The Bubble Transform and the de Rham Complex

Most Probable Paths for Anisotropic Brownian Motions on Manifolds

An Atlas for the Pinhole Camera

Efficient Computation of the Zeros of the Bargmann Transform Under Additive White Noise

  • Open Access

Functional Equivariance and Conservation Laws in Numerical Integration

Premium Partner

    Image Credits