Blessing of Dimensionality for Approximating Sobolev Classes on Manifolds

• URL: http://arxiv.org/abs/2408.06996v2
• Date: Sat, 03 May 2025 08:47:41 GMT
• Title: Blessing of Dimensionality for Approximating Sobolev Classes on Manifolds
• Authors: Hong Ye Tan, Subhadip Mukherjee, Junqi Tang, Carola-Bibiane Schönlieb,
• Abstract summary: We consider optimal uniform approximations with functions of finite statistical complexity.<n>In particular, we demonstrate that the statistical complexity required to approximate a class of bounded Sobolev functions on a compact manifold is bounded from below.
• Score: 14.183849746284816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The manifold hypothesis says that natural high-dimensional data lie on or around a low-dimensional manifold. The recent success of statistical and learning-based methods in very high dimensions empirically supports this hypothesis, suggesting that typical worst-case analysis does not provide practical guarantees. A natural step for analysis is thus to assume the manifold hypothesis and derive bounds that are independent of any ambient dimensions that the data may be embedded in. Theoretical implications in this direction have recently been explored in terms of generalization of ReLU networks and convergence of Langevin methods. In this work, we consider optimal uniform approximations with functions of finite statistical complexity. While upper bounds on uniform approximation exist in the literature using ReLU neural networks, we consider the opposite: lower bounds to quantify the fundamental difficulty of approximation on manifolds. In particular, we demonstrate that the statistical complexity required to approximate a class of bounded Sobolev functions on a compact manifold is bounded from below, and moreover that this bound is dependent only on the intrinsic properties of the manifold, such as curvature, volume, and injectivity radius.

Related papers

• A Likelihood Based Approach to Distribution Regression Using Conditional Deep Generative Models [6.647819824559201]
  We study the large-sample properties of a likelihood-based approach for estimating conditional deep generative models. Our results lead to the convergence rate of a sieve maximum likelihood estimator for estimating the conditional distribution.
  arXiv  Detail & Related papers  (2024-10-02T20:46:21Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Finite-dimensional approximations of push-forwards on locally analytic functionals [5.787117733071417]
  Our approach is to consider the push-forward on the space of locally analytic functionals, instead of directly handling the analytic map itself. We establish a methodology enabling appropriate finite-dimensional approximation of the push-forward from finite discrete data.
  arXiv  Detail & Related papers  (2024-04-16T17:53:59Z)
• Scaling Riemannian Diffusion Models [68.52820280448991]
  We show that our method enables us to scale to high dimensional tasks on nontrivial manifold. We model QCD densities on $SU(n)$ lattices and contrastively learned embeddings on high dimensional hyperspheres.
  arXiv  Detail & Related papers  (2023-10-30T21:27:53Z)
• Conformal inference for regression on Riemannian Manifolds [49.7719149179179]
  We investigate prediction sets for regression scenarios when the response variable, denoted by $Y$, resides in a manifold, and the covariable, denoted by X, lies in Euclidean space. We prove the almost sure convergence of the empirical version of these regions on the manifold to their population counterparts.
  arXiv  Detail & Related papers  (2023-10-12T10:56:25Z)
• Algebraic and Statistical Properties of the Ordinary Least Squares Interpolator [3.4320157633663064]
  We provide results for the minimum $ell$-norm OLS interpolator. We present statistical results such as an extension of the Gauss-Markov theorem. We conduct simulations that further explore the properties of the OLS interpolator.
  arXiv  Detail & Related papers  (2023-09-27T16:41:10Z)
• Geometric Neural Diffusion Processes [55.891428654434634]
  We extend the framework of diffusion models to incorporate a series of geometric priors in infinite-dimension modelling. We show that with these conditions, the generative functional model admits the same symmetry.
  arXiv  Detail & Related papers  (2023-07-11T16:51:38Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Diffusion Models are Minimax Optimal Distribution Estimators [49.47503258639454]
  We provide the first rigorous analysis on approximation and generalization abilities of diffusion modeling. We show that when the true density function belongs to the Besov space and the empirical score matching loss is properly minimized, the generated data distribution achieves the nearly minimax optimal estimation rates.
  arXiv  Detail & Related papers  (2023-03-03T11:31:55Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Statistical exploration of the Manifold Hypothesis [10.389701595098922]
  The Manifold Hypothesis asserts that nominally high-dimensional data are in fact concentrated near a low-dimensional manifold, embedded in high-dimensional space. We show that rich and sometimes intricate manifold structure in data can emerge from a generic and remarkably simple statistical model. We derive procedures to discover and interpret the geometry of high-dimensional data, and explore hypotheses about the data generating mechanism.
  arXiv  Detail & Related papers  (2022-08-24T17:00:16Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Manifold Hypothesis in Data Analysis: Double Geometrically-Probabilistic Approach to Manifold Dimension Estimation [92.81218653234669]
  We present new approach to manifold hypothesis checking and underlying manifold dimension estimation. Our geometrical method is a modification for sparse data of a well-known box-counting algorithm for Minkowski dimension calculation. Experiments on real datasets show that the suggested approach based on two methods combination is powerful and effective.
  arXiv  Detail & Related papers  (2021-07-08T15:35:54Z)
• Non-Asymptotic Performance Guarantees for Neural Estimation of $\mathsf{f}$-Divergences [22.496696555768846]
  Statistical distances quantify the dissimilarity between probability distributions. A modern method for estimating such distances from data relies on parametrizing a variational form by a neural network (NN) and optimizing it. This paper explores this tradeoff by means of non-asymptotic error bounds, focusing on three popular choices of SDs.
  arXiv  Detail & Related papers  (2021-03-11T19:47:30Z)
• Sample complexity and effective dimension for regression on manifolds [13.774258153124205]
  We consider the theory of regression on a manifold using kernel reproducing Hilbert space methods. We show that certain spaces of smooth functions on a manifold are effectively finite-dimensional, with a complexity that scales according to the manifold dimension.
  arXiv  Detail & Related papers  (2020-06-13T14:09:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.