A parametric algorithm is optimal for non-parametric regression of smooth functions
This work addresses the problem of efficient regression for smooth functions, offering a parametric solution that improves computational efficiency over existing nonparametric methods, though it is incremental in optimizing sample and space complexities.
The paper tackles the nonparametric regression problem for smooth functions by introducing PADUA, a parametric algorithm that achieves optimal sample complexity up to constant or logarithmic factors and optimal space complexity in prediction, with experiments on audio data showing comparable performance to state-of-the-art methods while using less computational time.
We address the regression problem for a general function $f:[-1,1]^d\to \mathbb R$ when the learner selects the training points $\{x_i\}_{i=1}^n$ to achieve a uniform error bound across the entire domain. In this setting, known historically as nonparametric regression, we aim to establish a sample complexity bound that depends solely on the function's degree of smoothness. Assuming periodicity at the domain boundaries, we introduce PADUA, an algorithm that, with high probability, provides performance guarantees optimal up to constant or logarithmic factors across all problem parameters. Notably, PADUA is the first parametric algorithm with optimal sample complexity for this setting. Due to this feature, we prove that, differently from the non-parametric state of the art, PADUA enjoys optimal space complexity in the prediction phase. To validate these results, we perform numerical experiments over functions coming from real audio data, where PADUA shows comparable performance to state-of-the-art methods, while requiring only a fraction of the computational time.