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

2013/10/07 by Hemant Tyagi, Volkan Cevher, Tyagi, Hemant +1 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematical Approximation and Integration #Microwave Imaging and Scattering Analysis #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1310.1826

openalex publication_date 2013/10/07 · openalex created_date 2022/08/07 · openalex updated_date 2026/08/01

Abstract

We consider the problem of learning multi-ridge functions of the form f(x) =\ng(Ax) from point evaluations of f. We assume that the function f is defined on\nan l₂-ball in R^d, g is twice continuously differentiable almost everywhere,\nand A \∈ R^{k \× d} is a rank k matrix, where k << d. We propose a\nrandomized, polynomial-complexity sampling scheme for estimating such\nfunctions. Our theoretical developments leverage recent techniques from low\nrank matrix recovery, which enables us to derive a polynomial time estimator of\nthe function f along with uniform approximation guarantees. We prove that our\nscheme can also be applied for learning functions of the form: f(x) =\n\∑_i=1^k g_i(a_i^T x), provided f satisfies certain smoothness conditions\nin a neighborhood around the origin. We also characterize the noise robustness\nof the scheme. Finally, we present numerical examples to illustrate the\ntheoretical bounds in action.\n

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Robust principal component analysis?
• Minimax-optimal rates for sparse additive models over kernel classes via convex programming
• Guaranteed Rank Minimization via Singular Value Projection

Cited by

• Nonlinear Dimensionality Reduction Techniques for Bayesian Optimization
• On the Neural Feature Ansatz for Deep Neural Networks

Related

• Learning Functions of Few Arbitrary Linear Parameters in High Dimensions
• Local Minimax Learning of Approximately Polynomial Functions
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation
• Robust Learning of Multi-index Models via Iterative Subspace Approximation
• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations