# Spectral Algorithms on Manifolds through Diffusion

arXiv: https://arxiv.org/abs/2403.03669 · HTML: https://mlsanity.com/paper/2403.03669/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 40 references that are in the map.
- First posted on arXiv 6 Mar 2024.

## Builds on (most cited first, 9 of 9)

- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms](https://mlsanity.com/paper/1801.07226/) (2018)
- [Analyzing the discrepancy principle for kernelized spectral filter learning algorithms](https://mlsanity.com/paper/2004.08436/) (2020)
- [Reproducing kernel Hilbert spaces on manifolds: Sobolev and Diffusion spaces](https://mlsanity.com/paper/1905.10913/) (2019)
- [Sample complexity and effective dimension for regression on manifolds](https://mlsanity.com/paper/2006.07642/) (2020)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)

## Built on by (most cited first, 1 of 1)

- [Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds](https://mlsanity.com/paper/2410.14539/) (2024)

## Abstract (arXiv)

The existing research on spectral algorithms, applied within a Reproducing Kernel Hilbert Space (RKHS), has primarily focused on general kernel functions, often neglecting the inherent structure of the input feature space. Our paper introduces a new perspective, asserting that input data are situated within a low-dimensional manifold embedded in a higher-dimensional Euclidean space. We study the convergence performance of spectral algorithms in the RKHSs, specifically those generated by the heat kernels, known as diffusion spaces. Incorporating the manifold structure of the input, we employ integral operator techniques to derive tight convergence upper bounds concerning generalized norms, which indicates that the estimators converge to the target function in strong sense, entailing the simultaneous convergence of the function itself and its derivatives. These bounds offer two significant advantages: firstly, they are exclusively contingent on the intrinsic dimension of the input manifolds, thereby providing a more focused analysis. Secondly, they enable the efficient derivation of convergence rates for derivatives of any k-th order, all of which can be accomplished within the ambit of the same spectral algorithms. Furthermore, we establish minimax lower bounds to demonstrate the asymptotic optimality of these conclusions in specific contexts. Our study confirms that the spectral algorithms are practically significant in the broader context of high-dimensional approximation.