Research map / Learning theory and algorithms / Prediction and decision losses
Importance Sampling for Nonlinear Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes norm-based and leverage-score importance sampling to nonlinear models via a nonlinear adjoint operator, giving subspace-embedding-style guarantees for nonlinear least squares and experiments on regression and image classification.
Problem
Importance sampling with approximation guarantees is well developed for linear least squares but lacks a systematic extension to nonlinear models, where existing guarantees carry large constants.
Approach
Define a nonlinear adjoint operator so that f(θ) = <θ̂, f̂*(θ)> holds, turning nonlinear least squares into a linear-looking matrix product; then define nonlinear leverage and norm scores from the rows of the resulting dual matrix and sample accordingly, with closed-form adjoints for generalized linear and ReLU networks.
Key results
- Nonlinear importance sampling reaches lower MSE with fewer training points than uniform and linear leverage/row-norm sampling on regression datasets (reported on log relative error scale).
- Theorem gives a (1±ε)-type guarantee with constant C=1 for nonlinear least squares under sampling scores with beta-approximation, sample size O((p log(p/δ)+p^2 log(p/ε))/(βε^2)), improving the constant C>>1 of prior single-neuron results.
- Nonlinear leverage scores highlight harder and mislabeled/outlier images in SVHN, NotMNIST, QD and FER, whereas linear scores select less informative samples (qualitative).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| sample using nonlinear importance scores instead of uniform or linear importance scores | single-index regression models · California Housing Prices, Medical Insurance, and Diamonds | training MSE | Helped |
| sample using nonlinear leverage scores instead of linear leverage scores or uniform sampling | classification models · SVHN (1 vs. 0) | training MSE | Helped |
| sample using nonlinear leverage scores instead of linear leverage scores or uniform sampling | classification models · QD (Fish vs. Car) | training MSE | Helped |
| use nonlinear rather than linear leverage scores to identify important samples | classification models · SVHN, FER-2013, NOTMNIST, and QD | sample informativeness | Helped |
| use nonlinear leverage scores to identify outliers | classification models · SVHN, FER-2013, NOTMNIST, and QD | outlier identification | Helped |
Surprising findings
- Scores are computed at the unknown optimal parameters, so the practical method uses scores from a trained model, making the sampling only approximately parameter-agnostic.
Limitations
- The guarantee for the constrained subproblem depends on the unknown optimal parameter through the bounded set C and the Lipschitz constant, so sampling is not fully parameter-agnostic.
- Theory is stated for squared loss; extension to general losses is only sketched for positively homogeneous maps.
- Sample complexity has quadratic dependence on dimension p; experiments are small-scale (10x10 images, 10-neuron MLP).
Experimental setup
Datasets: California Housing Prices Medical Insurance dataset Diamonds dataset SVHN FER-2013 NotMNIST Quick, Draw
Benchmarks: California Housing Prices Medical Insurance dataset Diamonds dataset SVHN FER-2013 NotMNIST Quick, Draw
Metrics: median log relative MSE error training MSE top-scoring image inspection
Baselines: uniform sampling linear leverage score sampling linear row-norm sampling
Builds on: leverage score sampling one-shot active learning for single-neuron models matrix multiplication sampling in RandNLA
Closest papers by meaning
- Improved Active Learning via Dependent Leverage Score Sampling (ICLR 2024 · similarity 0.84)
- From Matrix Inversion to Constraints: Provably Tighter Confidence Regions for Importance Weights in Label Shift (NeurIPS 2026 · similarity 0.84)
- Structural-Entropy-Based Sample Selection for Efficient and Effective Learning (ICLR 2025 · similarity 0.84)
- Kernel-based guarantees for nonlinear parametric models in Bayesian optimization (NeurIPS 2026 · similarity 0.84)
- Robust Sampling for Active Statistical Inference (NeurIPS 2025 · similarity 0.84)
- High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.