How well behaved is finite dimensional Diffusion Maps?

• URL: http://arxiv.org/abs/2412.03992v2
• Date: Fri, 21 Mar 2025 20:28:31 GMT
• Title: How well behaved is finite dimensional Diffusion Maps?
• Authors: Wenyu Bo, Marina Meilă,
• Abstract summary: We derive a series of properties that remain valid after finite-dimensional and almost isometric Diffusion Maps (DM)<n>We quantify the error between the estimated tangent spaces and the true tangent spaces over the submanifolds after the DM embedding.<n>These results offer a solid theoretical foundation for understanding the performance and reliability of DM in practical applications.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Under a set of assumptions on a family of submanifolds $\subset {\mathbb R}^D$, we derive a series of geometric properties that remain valid after finite-dimensional and almost isometric Diffusion Maps (DM), including almost uniform density, finite polynomial approximation and reach. Leveraging these properties, we establish rigorous bounds on the embedding errors introduced by the DM algorithm is $O\left((\frac{\log n}{n})^{\frac{1}{8d+16}}\right)$. Furthermore, we quantify the error between the estimated tangent spaces and the true tangent spaces over the submanifolds after the DM embedding, $\sup_{P\in \mathcal{P}}\mathbb{E}_{P^{\otimes \tilde{n}}} \max_{1\leq j \angle (T_{Y_{\varphi(M),j}}\varphi(M),\hat{T}_j)\leq \tilde{n}} \leq C \left(\frac{\log n }{n}\right)^\frac{k-1}{(8d+16)k}$, which providing a precise characterization of the geometric accuracy of the embeddings. These results offer a solid theoretical foundation for understanding the performance and reliability of DM in practical applications.

Related papers

• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning.<n>We provide the first high-probability, finite-sample analysis of vanilla TD(0) on mixing Markov data.
  arXiv  Detail & Related papers  (2025-02-08T22:01:02Z)
• Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein Minimization [0.0]
  This paper focuses on the complexity of estimating translation translation $boldsymbolmu in mathbbRl$ and shrinkage $sigma in mathbbR_++$ parameters.<n>We highlight that while the problem is NP-hard for Maximum Likelihood Estimation (MLE), it is possible to obtain $varepsilon$-approxs for arbitrary $varepsilon > 0$ within $textpoly left( frac1varepsilon )$ time using the
  arXiv  Detail & Related papers  (2025-01-17T13:07:52Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  We introduce a novel approach to estimating $m_1(mathbbR2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus. Our experimental results supported by theoretical justifications of proposed method demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound.
  arXiv  Detail & Related papers  (2024-11-20T12:07:19Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• On the $O(\rac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  This paper considers the RMSProp and its momentum extension and establishes the convergence rate of $frac1Tsum_k=1T.<n>Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$.<n>Our convergence rate can be considered to be analogous to the $frac1Tsum_k=1T.
  arXiv  Detail & Related papers  (2024-02-01T07:21:32Z)
• Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Products [12.047053875716506]
  We consider the problem of sufficient dimension reduction for multi-index models. We show that a fast parametric convergence rate of form $C_d cdot n-1/2$ is achievable.
  arXiv  Detail & Related papers  (2023-12-24T12:28:07Z)
• Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
  We give the first approximation algorithm for MDS with quasi-polynomial dependency on $Delta.<n>Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP.
  arXiv  Detail & Related papers  (2023-11-29T17:42:05Z)
• Superfluid weight in the isolated band limit within the generalized random phase approximation [0.0]
  The superfluid weight of a generic lattice model with attractive Hubbard interaction is computed analytically in the isolated band limit. It is found that the relation obtained in [https://link.aps.org/doi103/PhysRevB.106.014518] between the superfluid weight in the flat band limit and the so-called minimal quantum metric is valid even at the level of the generalized random phase approximation.
  arXiv  Detail & Related papers  (2023-08-21T15:11:32Z)
• 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)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Diffusion Maps : Using the Semigroup Property for Parameter Tuning [1.8782750537161608]
  Diffusion maps (DM) are used to reduce data lying on or close to a low-dimensional manifold embedded in a much larger dimensional space. We address the problem of setting a diffusion time t when constructing the diffusion kernel matrix by using the semigroup property of the diffusion operator. Experiments show that this principled approach is effective and robust.
  arXiv  Detail & Related papers  (2022-03-06T03:02:24Z)
• Exponential Convergence of Deep Operator Networks for Elliptic Partial Differential Equations [0.0]
  We construct deep operator networks (ONets) between infinite-dimensional spaces that emulate with an exponential rate of convergence the coefficient-to-solution map of elliptic second-order PDEs. In particular, we consider problems set in $d$-dimensional periodic domains, $d=1, 2, dots$, and with analytic right-hand sides and coefficients. We prove that the neural networks in the ONet have size $mathcalO(left|log(varepsilon)right|kappa)$ for some $kappa
  arXiv  Detail & Related papers  (2021-12-15T13:56:28Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
  We consider the problem of estimating a $d$ dimensional sub-manifold of $mathbbRD$ from a finite set of noisy samples. We show that the estimation yields rates of convergence of $n-frack2k + d$ for the point estimation and $n-frack-12k + d$ for the estimation of tangent space.
  arXiv  Detail & Related papers  (2021-05-11T02:29:33Z)
• A Unifying and Canonical Description of Measure-Preserving Diffusions [60.59592461429012]
  A complete recipe of measure-preserving diffusions in Euclidean space was recently derived unifying several MCMC algorithms into a single framework. We develop a geometric theory that improves and generalises this construction to any manifold.
  arXiv  Detail & Related papers  (2021-05-06T17:36:55Z)
• Multiscale regression on unknown manifolds [13.752772802705978]
  We construct low-dimensional coordinates on $mathcalM$ at multiple scales and perform multiscale regression by local fitting. We analyze the generalization error of our method by proving finite sample bounds in high probability on rich classes of priors. Our algorithm has quasilinear complexity in the sample size, with constants linear in $D$ and exponential in $d$.
  arXiv  Detail & Related papers  (2021-01-13T15:14:31Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)
• General state transitions with exact resource morphisms: a unified resource-theoretic approach [2.28438857884398]
  We formulate conditions that guarantee the existence of an $mathsfF$-morphism between two density matrices. While we allow errors in the transition, the corresponding map is required to be an exact $mathsfF$-morphism. We show how, when specialized to some situations of physical interest, our general results are able to unify and extend previous analyses.
  arXiv  Detail & Related papers  (2020-05-19T03:20:39Z)
• Learning Theory for Estimation of Animal Motion Submanifolds [0.0]
  This paper describes the formulation and experimental testing of a novel method for the estimation and approximation of submanifold models of animal motion. Experiments generate a finite sets $(s_i,x_i)_i=1msubset mathbbZm$ of samples that are generated according to an unknown probability density.
  arXiv  Detail & Related papers  (2020-03-30T20:54:51Z)

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.