Sample complexity and effective dimension for regression on manifolds
Authors: Andrew McRae, Justin Romberg, Mark Davenport
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our first key contribution is to establish a novel nonasymptotic version of the Weyl law from differential geometry. From this we are able to show that certain spaces of smooth functions on a manifold are effectively finite-dimensional, with a complexity that scales according to the manifold dimension rather than any ambient data dimension. Finally, we show that given (potentially noisy) function values taken uniformly at random over a manifold, a kernel regression estimator (derived from the spectral decomposition of the manifold) yields minimax-optimal error bounds that are controlled by the effective dimension. Section 4 contains our main theoretical results. The proofs are in the appendices in the supplementary material. |
| Researcher Affiliation | Academia | Andrew D. Mc Rae Justin Romberg Mark A. Davenport School of Electrical and Computer Engineering Georgia Institute of Technology Atlanta, GA 30332 admcrae@gatech.edu, jrom@ece.gatech.edu, mdav@gatech.edu |
| Pseudocode | No | The paper does not contain STRUCTURED PSEUDOCODE OR ALGORITHM BLOCKS (clearly labeled algorithm sections or code-like formatted procedures). |
| Open Source Code | No | The paper does not provide CONCRETE ACCESS TO SOURCE CODE (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and discusses 'samples' of functions for theoretical analysis, but it does not use or provide access to publicly available datasets for empirical training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and defines parameters for its mathematical models (e.g., regularization parameter alpha, constants Kp and Rp, manifold properties like sectional curvature), but it does not provide experimental setup details such as hyperparameters or training configurations for empirical experiments. |