# Importance Sampling for Nonlinear Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 72 references that are in the map.
- First posted on arXiv 18 May 2025.

## Builds on (most cited first, 30 of 34)

- [AffectNet: A Database for Facial Expression, Valence, and Arousal Computing in the Wild](https://mlsanity.com/paper/1708.03985/) (2017)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [A Neural Representation of Sketch Drawings](https://mlsanity.com/paper/1704.03477/) (2017)
- [Challenges in Representation Learning: A report on three machine learning contests](https://mlsanity.com/paper/1307.0414/) (2013)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Efficient training of physics-informed neural networks via importance sampling](https://mlsanity.com/paper/2104.12325/) (2021)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Derivative-Informed Projected Neural Networks for High-Dimensional Parametric Maps Governed by PDEs](https://mlsanity.com/paper/2011.15110/) (2020)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Safe Adaptive Importance Sampling](https://mlsanity.com/paper/1711.02637/) (2017)
- [Lectures on Randomized Numerical Linear Algebra](https://mlsanity.com/paper/1712.08880/) (2017)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [IS-COUNT: Large-scale Object Counting from Satellite Images with Covariate-based Importance Sampling](https://mlsanity.com/paper/2112.09126/) (2021)
- [Black-box Importance Sampling](https://mlsanity.com/paper/1610.05247/) (2016)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)

## Abstract (arXiv)

While norm-based and leverage-score-based methods have been extensively studied for identifying "important" data points in linear models, analogous tools for nonlinear models remain significantly underdeveloped. By introducing the concept of the adjoint operator of a nonlinear map, we address this gap and generalize norm-based and leverage-score-based importance sampling to nonlinear settings. We demonstrate that sampling based on these generalized notions of norm and leverage scores provides approximation guarantees for the underlying nonlinear mapping, similar to linear subspace embeddings. As direct applications, these nonlinear scores not only reduce the computational complexity of training nonlinear models by enabling efficient sampling over large datasets but also offer a novel mechanism for model explainability and outlier detection. Our contributions are supported by both theoretical analyses and experimental results across a variety of supervised learning scenarios.