# Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2013.

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

- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [High-Dimensional Bayesian Optimization via Semi-Supervised Learning with Optimized Unlabeled Data Sampling](https://mlsanity.com/paper/2305.02614/) (2023)
- [Gradient Descent for Low-Rank Functions](https://mlsanity.com/paper/2206.08257/) (2022)
- [On the Neural Feature Ansatz for Deep Neural Networks](https://mlsanity.com/paper/2510.15563/) (2025)
- [CobBO: Coordinate Backoff Bayesian Optimization with Two-Stage Kernels](https://mlsanity.com/paper/2101.05147/) (2021)
- [Nonlinear Dimensionality Reduction Techniques for Bayesian Optimization](https://mlsanity.com/paper/2510.15435/) (2025)

## Abstract (arXiv)

We consider the problem of learning multi-ridge functions of the form f(x) = g(Ax) from point evaluations of f. We assume that the function f is defined on an l2-ball in Rd, g is twice continuously differentiable almost everywhere, and A ∈ Rk × d is a rank k matrix, where k << d. We propose a randomized, polynomial-complexity sampling scheme for estimating such functions. Our theoretical developments leverage recent techniques from low rank matrix recovery, which enables us to derive a polynomial time estimator of the function f along with uniform approximation guarantees. We prove that our scheme can also be applied for learning functions of the form: f(x) = sumi=1k gi(aiT x), provided f satisfies certain smoothness conditions in a neighborhood around the origin. We also characterize the noise robustness of the scheme. Finally, we present numerical examples to illustrate the theoretical bounds in action.