# Hybrid least squares for learning functions from highly noisy data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 54 references that are in the map.
- First posted on arXiv 3 Jul 2025.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [The Random Feature Model for Input-Output Maps between Banach Spaces](https://mlsanity.com/paper/2005.10224/) (2020)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Differential Machine Learning](https://mlsanity.com/paper/2005.02347/) (2020)
- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [Structure-preserving function approximation via convex optimization](https://mlsanity.com/paper/2008.08223/) (2020)

## Abstract (arXiv)

Motivated by the need for efficient estimation of conditional expectations, we consider a least-squares function approximation problem with heavily polluted data. Existing methods that are effective in the small-noise regime are suboptimal when large noise is present. To address this issue, we propose a hybrid approach that combines Christoffel sampling with optimal experimental design. We show that the proposed algorithm enjoys appropriate optimality properties for both sample point generation and noise mollification, leading to improved computational efficiency and sample complexity compared to existing methods. We also extend the algorithm to convexity-constrained settings with similar theoretical guarantees. When the target function is defined as the expectation of a random field, we further extend our approach to leverage adaptive random subspaces and establish results on the approximation capacity of the adaptive procedure. Our theoretical findings are supported by numerical studies on both synthetic data and on a more challenging stochastic simulation problem in computational finance.