# Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 54 references that are in the map.
- First posted on arXiv 19 Dec 2024.

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

- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Deep Learning for Audio Signal Processing](https://mlsanity.com/paper/1905.00078/) (2019)
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [First- and Second-Order Bounds for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2305.00832/) (2023)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Smooth Bandit Optimization: Generalization to H"older Space](https://mlsanity.com/paper/2012.06076/) (2020)
- [Second Order Bounds for Contextual Bandits with Function Approximation](https://mlsanity.com/paper/2409.16197/) (2024)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs](https://mlsanity.com/paper/2405.06363/) (2024)
- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [On the Estimation of Derivatives Using Plug-in Kernel Ridge Regression Estimators](https://mlsanity.com/paper/2006.01350/) (2020)
- [Polynomial spline regression: Theory and Application](https://mlsanity.com/paper/2212.14777/) (2022)
- [Derivative Principal Component Analysis for Representing the Time Dynamics of Longitudinal and Functional Data](https://mlsanity.com/paper/1707.04360/) (2017)

## Abstract (arXiv)

We address the problem of learning an unknown smooth function and its derivatives from noisy pointwise evaluations under the supremum norm. While classical nonparametric regression provides a strong theoretical foundation, traditional kernel-based estimators often incur high computational costs and memory requirements that scale with the sample size, limiting their utility in real-time applications such as reinforcement learning. To overcome these challenges, we propose a parametric approach based on a finite-dimensional representation that achieves minimax-optimal uniform convergence rates. Our method enables lightweight inference without storing all samples in memory. We provide sharp finite-sample bounds under sub-Gaussian noise, derive second-order Bernstein-type guarantees, and prove matching lower bounds, thereby confirming the optimality of our approach in both estimation error and memory efficiency.