Importance Sampling for Nonlinear Models

Prakash Palanivelu Rajmohan, Fred Roosta

Abstract

Importance sampling is a cornerstone of efficient training for linear models, yet its application to nonlinear models has lacked rigorous theoretical foundations. This paper introduces the nonlinear adjoint operator, a mathematical framework that generalizes leverage scores to nonlinear settings. By representing nonlinear mappings as inner-product structures, the authors provide strong approximation guarantees and demonstrate superior performance across diverse regression and classification tasks.

Introduction

Training machine learning models on massive datasets is computationally expensive. To mitigate this, Randomized Numerical Linear Algebra (RandNLA) has historically employed techniques like leverage score sampling to identify the most informative data points. While these tools are well-established for linear settings, their extension to nonlinear models—the foundation of modern deep learning—has been largely heuristic, often lacking strong theoretical guarantees.

The primary challenge lies in the absence of a systematic framework to capture the "nonlinear component" of an objective function while preserving the approximation properties inherent in linear algebra. This paper addresses this gap by introducing a rigorous mathematical bridge between linear and nonlinear importance sampling.

The Nonlinear Adjoint Operator

The core innovation presented is the Nonlinear Adjoint Operator. Utilizing the integral form of the mean value theorem, the authors demonstrate that any continuously differentiable nonlinear mapping $f(\theta)$ can be represented as an inner product: $f(\theta) = \langle \theta, \mathbf{f}^\star(\theta) \rangle$, where $\mathbf{f}^\star(\theta)$ is the adjoint operator.

This transformation allows for the definition of Nonlinear Leverage Scores and Nonlinear Norm Scores by treating the adjoint operator as a "dual matrix" $\mathbf{F}^\star(\theta)$. Unlike standard RandNLA which relies on the data matrix $\mathbf{X}$, this framework utilizes the nonlinear dual matrix to provide "subspace embedding" guarantees. This ensures that the loss calculated on a small, intelligently selected subset of data closely approximates the loss on the full dataset with predictable error bounds.

Experimental Results

The framework was validated across several regression and image classification tasks. In regression experiments using the California Housing, Medical Insurance, and Diamonds datasets, nonlinear importance sampling consistently outperformed uniform sampling and traditional linear leverage scores.

Log relative error across regression datasets comparing nonlinear adjoint-based sampling (RN-A, LS-A) against linear (RN-L, LS-L) and uniform (UN) baselines.

As shown in the figure above, the adjoint-based methods (RN-A and LS-A) achieve lower mean squared error (MSE) with significantly fewer samples. The theoretical tightness of this approach is a key highlight; unlike previous methods with large hidden constants, this framework provides guarantees where the subset model is nearly as accurate as the full-data model.

Diagnostic Utility and Insights

Beyond computational speedups, nonlinear leverage scores serve as powerful diagnostic tools. High scores effectively identify "difficult" samples, such as mislabeled data or unique patterns that are most informative to the model. In classification tasks like FER-2013 (facial expression recognition), the authors observed that "important" samples evolve during training: the model initially prioritizes extreme expressions before focusing on subtler features like tears or aging lines.

Furthermore, the authors address the "chicken-and-egg" problem of needing optimal parameters to calculate scores. For common architectures like ReLU networks, they demonstrate that these scores can be estimated using only input data, making the approach practically viable.

Conclusion

While the nonlinear adjoint operator provides a robust foundation for importance sampling, challenges remain regarding computational overhead and full generalization to non-squared loss functions. Future work will focus on making these methods entirely parameter-agnostic for arbitrary nonlinear models.

Summary updated

BibTeX
@inproceedings{rajmohan2025importance,
  author = {Prakash Palanivelu Rajmohan and Fred Roosta},
  title = {{Importance Sampling for Nonlinear Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=fY7KjywLK1},
}
Figure