Importance Sampling for Nonlinear Models
Authors: Prakash Palanivelu Rajmohan
Fred Roosta
Venue: ICML 2025 poster (2025)
Keywords: Importance Sampling
Nonlinear Adjoint
Leverage Scores
Active Learning
Primary area: general_machine_learning

Abstract: 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.

Importance Sampling for Nonlinear Models
Prakash P. Rajmohan
Fred Roosta" 2.
Abstract
out this paper, we make the umbrella assumption that n p.
i.., operate in the underparameterized setting.
While norm-based and evverag-scoorebasel methods have been extensively studied for iden- tifying "important" data points in linear models. analogous tools for nonlinear models remain sig- nificantly underdeveloped. By introducing the concept of the adjoint operator of a nonlinear map, we address this gap and generalize norm-based and leverage-score score-baecd importance sampling nonlinear settings. We demonstrate that sampling based on these generalized notions of norm and leverage scores provides approximation guaran- tees for the underlying nonlinear mapping, similar to linear subspace embeddings. As direct appli- cations, these nonlinear scores not only reduce the computational complexity of training nonlin- car 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.
For example, in the simple linear regression, fi(0) (0, x.) - yi. where (xi, yi is the 1th input-output pair. Us- ing the squared loss E(t) = t² gives rise to the familiar linear least-squares problem L = || yll?, where X E Raxd is the input data matrix whose 8th row is x,, and y E R" is the output vector whose 7th component is y/-
The growth of ML over the past decade has been largely driven by the explosion in the availability of data. How- ever, this exponential increase in data volume presents sig- nificant computational challenges, particularly in solving (I) and developing diagnostic tools for post-traue post-training anal- ysis. These challenges have been extensively studied and addressed in simpler linear settings. In this context, random- ized numerical linear algebra (RandNLA) has emerged as powerful paradigm for approximating underlying matri- ces and accelerating computations. RandNLA has led to significant advancements in algorithms for fundamental ma- trix problems, including matrix multiplication, least-squares problems, least-absolute deviation, and low-rank matrix ap- proximation, among others. For further reading, see the lecture notes and surveys on this topie, such as Mahoney et al. (2011); Woodruff al. (2014); Drineas & Mahoney (2018); Martinsson & Tropp (2020); Murray et al. (2023); Dereziński & Mahoney (2024).
1. Introduction
The process of training in machine learning (ML) typically boils down to solving an optimization problem of the form
Arguably, linear least-squares problems have been among the most well-studied problems in RandNLA (Sarlos, 2006; Nelson & Nguyên, 2013; Meng & Mahoney, 2013; Clark- son & Woodruff, 2017). Various randomized approximation techniques, ranging from data-independent oblivious meth- ods (c.g.. sketching and projections) to data-dependent non- oblivious sampling methods (e.g., non-uniform leverage score or row-norm sampling). have emerged as powerful tools to speed up computations directly (Woodruff et al., 2014) or to construct preconditioners for downstream linear algebra subroutines (Avron et al., 2010). While these tools have proven remarkably successful in accelerating computa- tions for linear least-squares problems, extending them to more general problems of the form (1) remains challenging. Efforts to push these boundaries into the nonlinear realm often remain ad hoc and limited in scope (Gajjar & Musco, 2021; Erdélyi et al., 2020; Avron et al., 2019; 2017). A key
((())-
Σ ((R(O))
min OERP
(I)
where é a loss function, and fa: IRP R is a potentially nonlinear mapping, parametrized by 0, that represents the ML model evaluated at the 2h training data point. Through-
'School of Electrical Engineering and Computer Science, University of Queensland, Brisbane, Australia. "School of Mathematics and Physics. University of Queensland, Brisbane, Australia. *ARC Training Centre for Information Resilience (CIRES). Brisbane, Australia. Correspondence to: Prakash Rajmohan <p.palanivelurajmohaned net.auu Fred Roosta rorsa. uq edu
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Importance Sampling for Nonlinear Models
gap lies in the lack of systematic framework to capture and embed the "nonlinear component" of the objective func- tion while preserving the critical approximation properties well-established in linear embeddings.
2. Background and Related Work
Importance Sampling in Linear Models. In linear set- tings, importance sampling has been widely used for var- ious linear algebra tasks such as matrix multiplication (Drineas al., 2006a), least-squares regression (Drineas et al., 2006b), and low-rank approximation (Cohen et al., 2017). It approximates large data matrices by prioritizing data points with high "information", reducing computational (Clarkson & Woodruff, 2017; Nelson & Nguyên, 2013) and storage costs (Iwen et al., 2021; Meng & Mahoney, 2013) while ensuring strong guarantees for downstream tasks.
In this paper, we aim to bridge this gap to some extent. Specifically, we focus on non-uniform sampling in (1), Let- ting 0* and 0% denote the optimal parameters obtained from training the model over the full dataset and a, potentially non-uniformly, sampled subset of data, respectively, our goal is to ensure that, for any small e, the samples are se- lected such that
Formally, let X Rn n > d, be data matrix with row vectors E Rd. Each row is assigned a nonnegative weight 9i 2 0 through an importance sampling scheme, with sampling probability Ti = :r>=:/>> q:/En= Qj- Consider se- lecting s < n rows of X independently at random, with replacement, according to {T=}. Let Xs E Rexd be the sub-sampled matrix, where the 7th row is x; /8T. If {mi} is constructed appropriately. Xs preserves key spectral and geometrie properties of X with high probability, acting as dwver-dimensional approximation. This is captured by a linear subspace embedding guarantee: for all v E IRd
((03) S +0
Recent work by (Gajjar et al., 2023; 2024) has made progress toward this goal by proposing a one-shot active learning strategy using leverage scores of the data for certain classes of single-neuron predictors. Here, we take a step further by introducing the concept of the adjoint operator of nonlinear map. This allows us to generalize norm-based and leverage-score basee- importance sampling to nonlinear settings, thereby obtaining approximation guarantees of the form (2) in many settings.
(1 s) |xv12 S |X S (1+ |xv|
(3)
Contributions. Our contributions are as follows:
Two common approaches for constructing { are based on the norms and leverage scores of the rows of X. In row- norm sampling, we set q: = ||x:||. meaning rows that con- tribute more to the overall fz-energy, |X = Σm= ||x: 12.122 are sampled more frequently. Leverage scores quantify the influence of each row x; on the row space of X and are defined as
1. By introducing the nonlinear adjoint operator, we pro- vide systematic framework for constructing importance sampling scores for (1). While numerical integration can generally approximate these scores, we show that for specific nonlinear models, they can be derived directly.
2. We further show that, under certain assumptions, im- portance sampling based on these scores achieves (2). To our knowledge, this is the first work to extend such guarantees to NNs.
9i = Xx'x)) = min
|all subject to X'a = x,. acR"
Thus, the 5th leverage score captures the "importance" of x; in spanning the data subspace.
3. To validate the theoretical results, we present experi- ments for several supervised learning tasks. We show that, beyond redueing computational costs, our frame- work can be used post hoc for diagnostics, such as iden- tifying important samples and detecting anomalies.
These importance sampling schemes are particularly effec- tive when the data exhibits high coherence (Paschou et al., 2007: Mahoney & Drineas, 2009; Gittens & Mahoney, 2013; Fan al., 2011; 1; Eshragh et al., 2022). It has been well estab- lished that, for any & E (0, 1). as long as the sample size s is sufficiently luggespecifficllly. proximation in (3) holds with high probability (Martinsson & Tropp, 2020). These bounds are tight (up to logarithmic factors) (Woodruff et al., 2014; Chen & Price, 2019).
E O (d In d/e") ap-
Notation. Vectors and matrices are denoted by bold lower- case and bold uppercase letters, respectively. The 8th row of a data matrix X E Ra is denoted by x; E Idd, The pseudoinverse of X is denoted by Xi, and the 7th standard basis vector in " is denoted by e,, The spectral norm and Frobenius norm of matrix are denoted by || l|2 and ||. [|e. respectively. The inner product between two vectors is de- noted by (). We use ((-) for Big-O complexity and (-) to omit logarithmic factors. The sub-sampled data matrix is represented by Xs E Rxdd where s is the number of sub- sampled points.
The linear subspace embedding guarantee in (3) forms the foundation for approximating linear least-squares problems (Woodruff et al., 2014). However, for loss functions beyond least-squares, simple linear subspace embedding may not provide the desired guarantees. In such cases, alternative tools like importance sampling scores (c.g.. Lewis weights (Apers et al., 2024; Johnson & Schechtman, 2001; Bourgain
2

---

Importance Sampling for Nonlinear Models
al., 1989 Cohen & Peng, 2015)) or coresets (Feldman, 2020; Mirzasoleiman al., 2020; Lucic al., 2018; Har- Peled & Mazumdar, 2004) are commonly used.
proportional the linear leverage scores of X, to guarantee solution 0 satisfying, with high probability, the bound
In particular for coresets, Langberg & Schulman (2010) introduced a sensitivity sampling framework that provides foundational coreset guarantees for broad classes of objec- tives. This approach (akin to importance sampling) assigns each data point sampling probability proportional to its worst-case influence (sensitivity) on the objective function, yielding a coreset that achieves a (1 + s) approximation for all queries. Subsequent work has refined this idea for specific loss functions; for instance, Tremblay et al. (2019) combine sensitivity scores with determinantal point pro- cesses (DPP) to reduce redundant draws and thus promote diversity among the selected points. For logistic regression, Munteanu et al. (2018) prove that although no sublinear-sizz coreset exists in the worst case, sensitivity-based scheme can yield the first provably sublinear approximation coreset when the dataset's complexity measure (xX) is bounded. These results, position cearrtaccessampiigg coresets as the natural extension of linear embeddings when moving be- yond least-squares.
((0%) SC. [(C)
(4)
for some sufficiently large constant C. > 0. They also argued that such additive error bounds are necessary, as achieving a pure multiplicative error bound would require exponentially many samples in d.
By using intricate tools from high-dimensional probability, subsequent work by Gajjar et al. (2024) improved the sample complexity to (d/==), matching the linear benchmark up to polylogarithmic terms. Furthermore, they extended the analysis to the setting where & is Lipschitz but unspecified by employing a meticulous "sampling-aware" discretization of the function class.
While the results in Gajjar et al. (2023; 2024) represent significant contributions toward achieving (2) for nonlinear models, they have notable drawback: the guarantees in Gajjar et al. (2023; 2024) take the form (4), which involves an undesirable constant C >> (exceeding 1,000 in Gajjar et al. (2024)). Such large constants undermine the practical utility of the approximation guarantee in (4). We show that, under certain assumptions, it is possible to obtain the more desirable guarantee (2) (where C 1).
For more general loss functions f, some works have tended approximation guarantees similar to (2) to specific problems, such as logistic regression (Samadian et al., 2020; Huggins et al., 2016; Tolochinksy et al., 2022), linear pre- dictor models with hinge-like loss (Mai et al., 2021). 6p regression (Chen & Derezinski, 2021; Musco et al., 2022), and kernel regression (Erdélyi et al., 2020).
3. Nonlinear Approximation: Our Approach
Importance Sampling in Nonlinear Models. Importance sampling techniques have long played a crucial role in mod- ern large-scale machine learning tasks, serving as tools to identify the most important samples and accelerating opti- mization procedures (Katharopoulos & Fleuret, 2018; Stich et al., 2017; Nabian et al., 2021; Canévet et al., 2016; Liu & Lee, 2017; Meng et al., 2022; Xu et al., 2016; Liu et al., 2024). However, their use in obtaining approximation guar- antees of the form (2) has been very limited.
The core structure enabling the use of the subspace em- bedding property (3) in approximating linear least-squares problems is the linear inner product. Specifically, for f(0) (0, x) -8- y, the least-squares model can be expressed as
((,xx,) - -1)²² (X),X0). Σ 1=1 1=1
10)
To our knowledge, Gajjar et al. (2023; 2024) are among the first to consider non-linear function families and analyze leverage-score baade- sampling scheme (also referred to as a one-shot active learning sampling scheme) in the context of single-index (or "single neuron") models, where & is the squared loss and (0) = (((0. (000,))) x;)) for some scalar non-linearity Φ: + F. For their derivations, the authors employ intricate tools from high-dimensional probability, as the mapping + (w) introduces non-linearity that invalidates the straightforward matrix Chernoff arguments typically used in linear settings.
where X = X -y] E Rex(d+1) and 0 = 0 1] E Rd+11
This structure allows the subspace embedding property (3) to be applied, enabling the approximation of the original least-squares objective using a carefully chosen subsample of the data.
Using the notion of the nonlineur adjoint operator, we now derive an analogous "inner-rroduttlikke" representation for nonlinear mappings. This representation captures the non- linearity in a novel way, enabling the derivation of nonlinear embeddings similar to (3).
Gajjar et al. (2023) showed that if ó is L-Lipschitz, one can collect O(P//e)) labels, sampled with probabilities
3

---

Importance Sampling for Nonlinear Models
3.1. Nonlinear Adjoint Operator
homogeneous of degree a R. iee, h(10) 19)(() for any t 0. Then
Consider mapping f()): Rº + R that is continuously dif-
ferentiable. By the integral form of the mean value theorem,
g(((0)) ((h(0)))9(0)) -9(0) a (n(0))
0 h(0), if((0) +0,
00
f(0) ((0)= + //' <
f (10) 0)
dt
(0)
00
(1(0)
00 h()).
if 0.
0
=(0) + 0.
(10)dt)
00
Proof. The proof can be found in Appendix A.I.
The above relation is an equation involving functions of 0. The second term includes an inner product between the parameter 0 and a vector-valued map, reminiscent of the role of dual operators in Banach spaces. This observation motivates the following definition, which extends beyond continuously differentiable functions.
Example 3.1 (Generalized Linear Predictors). Consider
generalized linear predictor models, often called single index" models, where I [()) o ((00, x)) for some function Φ R R and data point E R.. These models are foundational in studying complex nonlinear predictors in high dimensions (Hristache et al., 2001; Härdle et al., 2004; Kakade et al., 2011; Bietti et al., 2022). By limiting net- works to a single hidden unit, they provide a controllable instance of neural network architecture while retaining sim- plicity (Goel et al., 2017). In scientific machine learning, such models underpin efficient surrogate methods for para- metric partial differential equations, where the cost of la- beled queries can be prohibitive (Cohen & DeVore, 2015; O' Leoaarrryyeerryy et al., 2022).
Definition 3.1 (Adjoint Operator). The adjoint operator of f: + R is the vector valued map I* RP - IR,
(0) & f 0 00 dto)
(5)
for all O E TRP such that the function @ : [0, 1] - IR defined as (t)) & f(t0) is absolutely continuous on [0, 1].
Note that the absolute continuity condition relaxes the quirement for differentiability to that of being differentiable almost everywhere.
Note that here f(0) g(h(O)) where g(t) = d(t) and h(0) 10, x). Since the positive homogeneity degree of h is a = 1, we have
With the above definition, we can more compactly write
(6((0,)))- -8(0) (0,x)
(*(0)=
(7)
((0) = (0)
(6a)
(0) A notable example is the 5(0)
We also get (0)0)
where
logistic function where e(t) 1/(1 + exp(-t)), where
[0) [(()]
and 0 0 0
(0))
(6b)
(tanh((0.x) /2)
(* = 2 (0)
x.
The term nonlinear adjoint operator is motivated by cases where f()) = 0. In such cases, the above expression sim- plifies to f())= = (0, (0)). which can be viewed as a nonlinear analogue of the Riesz representation theorem in linear settings; see, for example, Burýšková (1998); Scher- pen & Gray (2002).
Example 3.2 (Rel.U Neural Networks). Suppose r(0) (((()) where ò R + R. and (b P a max maxx(b,,3) x). for E and f = [a. b) E Rd+1 Here, the positive homogeneity degree of vp is a = 2. Hence,
In the simplest case of linear regression, i.e., f(0)= (0, x) y. we have (0) x. that is, the input data con- stitutes the space of adjoint operators. Beyond simple linear settings, the explicit calculation of (5) involves evaluating an integral. Naturally, this integral can be approximated using numerical methods, such as quadrature schemes. For- tunately, for many machine learning models, the following property enables the direct computation of (5).
1.'
a élaa max ((Ib, x), 00) dt 20
())
(8)
max {(b, ,0
sla max (bb, x) 03) 2())
m
max { (b, x)x 00
a x 1 ((bx)>))
In the typical case where ((z) 2, this simplifies to
Proposition 3.1. Let f = g o h = 9(h) where g IR + and h. : R -> TR. Also, assume that h is positively
1 mmxx { (b, x) 03] r' 2 a x1 (b,x)>>0}

---

Importance Sampling for Nonlinear Models
Now, consider a two-layer neural network with m hidden neurons, ReLU activation, and single output:
Definition 3.4 (Nonlinear Norm Scores). Nonlinear norm score of fa is defined as
1(0)
Σ 1=1
TR
r r(0))
Σ Maz max {(b,, 0)),
m
F (0) 2 [ [F)
r0
==1
where 0j = -aaj bز] and = , We have
0ml
m
0))
Σ
(la; max {(1bj, x), )dl
It is easy to verify that, for both Definitions 3.3 and 3.4, the values (T((0) ) form a probability distribution, i.e., 7; T0)) 2 0 and Σ: T, (0)=
o 00
j=1
m
= Σ 9 & (0))
Remark 3.1. Definitions 3.3 and 3.4 generalize their lin- ear counterparts. Specifically, for linear models where [(0) (0, x), these definitions reduce to the standard linear leverage and row norm scores. To the best of our knowledge, this represents the first systematic extension of these concepts from linear to nonlinear settings.
= [[r((0))) (02))
[T
where @ denotes the Kronecker product and (0₂) given
(0)
in (8). Finally, we get (0) m (0)
Remark 3.2. While Example 3.1 and Example 3.2 illustrate explicit computations of the adjoint operator via Propo- sition 3.1, our approach conceptually extends to broader classes of nonlinear functions through its general Defini- tion 3.1. When an explicit adjoint form is available, impor- lance scores (row-norm leverage) are computed directly from the nonlinear dual matrix via standard linear alge- bra routines (e.g., QR or SVD factorizations). In scenarios where the adjoint lacks a closed-form expression, we can approximate it numerically using Definition 3.1; the result- ing dual matrix is then factorized similarly, with QR or SVD methods.
3.2. Parameter-dependent Approximations
The "inner-product-lkee" representatiin of nonlinear func- tion in (6) enables the development of sampling strategies for approximating general loss functions beyond linear least- squares and extends the concept of linear subspace embed- dings to nonlinear settings. We focus on nonlinear least- squares problems, where {t)) = t², and (I) is expressed as [()) = Σm= (O)))), with extensions to more general nonlinear losses discussed in Appendix A.3.
Definition 3.2 (Nonlinear Dual Matrix). Given the nonlin- maps f: IP + R. nn. the nonlinear dual matrix operator, F* RP + _2xx, is defined as
Let S be the index set of samples, obtained by randomly sampling
data points with replacement, using prob- abilities defined by one of the sampling distributions in Definitions 3.3 and 3.4. Note that S depends on the choice of 0 (this is addressed later in Section 3.3.1). The loss on the sampled data is defined as
F* (0) e (0) (0)
(
Using (6b), also define
(0) A (0) (0)
;:(0)''
(fi(0))2 (T:
With (6) and Definition 3.2, we can now write
Cs(
iES
(()) Σ (1((0))= n 0, ( (9)
which is an unbiased estimator of the true loss. Similar to the derivation of (9), we have
This formulation resembles the ordinary least-squares setup, with the nonlinear dual matrix F-(0) (0) replacing the original input data matrix. This motivates the following notions of importance sampling scores, which generalize standard leverage scores or row-norms to those based on the rows of the dual matrix F().
(s = (
where (0) Rexp is subset of F*(0), consisting of rows indexed by S, with the ith row scaled by (/))).(O).
The representation in (9), which related the output of nonlinear function to the norm of matrix- prod- uet, enables the use of existing results on approximate ma- trix multiplication and linear subspace embedding to de- rive an approximation bound on Ls()); see, for example, Woodruff et al. (2014); Drineas & Mahoney (2018); Mar- tinsson & Tropp (2020). Specifically, for a fixed and
Definition 3.3 (Nonlinear Leverage Scores). Nonlinear leverage score of ft is defined as
e (0) [0) e;
(0) A
Rank (0)
5

---

Importance Sampling for Nonlinear Models
any of the sampling distributions mentioned, if the sam- ple size is O (plog(p/0)/e²), then with probability at least
constants 0 < < u do for which I S ((1//12 S u for all t T, where TT is some set of interest. An example is the Swish-type activation function given by
1-6, for all v E R (1 - [) [|
(1 + e) F* (0)yvl which in turn implies, with probability at least 1 1 6,
<(t)= =1 1::0=1--aa (vV (V02 (Ve2- va) 1+
(1 (1- (1-e) & Ls( ()))
(10)
for some 0 S c1 < c2 and Ç E R. 1fa > we can take
3.3. Parameter-independent Approximation
= Vo and Voz- For 01 = 0, i.e. the typical Swish function, we can still define 0 < 1 & min (t)/e provided EET
The relation (10) and the optimality of 0% with respect to (.(() allow us to take initial steps towards (2) as
that T is a bounded set.
(0)) S Ls( S (1 + C))))))
(11)
Consider leverage score sampling according to Defini- tion 3.3. Suppose X E Raxd and (0) E Rx are both full column rank. Since
However, the key missing component is that the left-hand side of (2) involves the loss evaluated over the full dataset, whereas the left-hand side of (11) is restricted to the loss over the sampled subset. The chain of inequalities to obtain (2) would be complete if we could find sensible lower bound for (5())) in terms of L(03)- Additionally, (11) requires evaluating the importance sampling scores defined in Definitions 3.3 and 3.4 at 0", which is inherently un- known. Therefore, to achieve (2), we must address two critical challenges:
2( 0(100x
FF) FO)
Σ
x,x,,
(0,
it follows that, as long as C1 0or 0 for some bounded
set C, we have 0- x 1. X = (0)) F (0) 3 u. X Hence,
d d-T:(0)-
(0)) (F((O)[FF(()) r())
1. Approximating the nonlinear scores defined in Defini- tions 3.3 and 3.4 with quantities that are independent of the parameter O.
(F)(), (xxx) -1 -'((()) " 7 (x (x"x) -1 -1x d a The
2. Establishing meaningful lower bound for Ls(03) in terms of ((3)).
Our next tasks involve addressing these challenges.
where TÚ is the linear leverage score. This implies 3 = 1/u. Example 3.4 (ReLU Neural Networks). Revising the NN model in Example 3.2, we consider row norm sampling according to Definition 3.4. Suppose @ is such that such that e S (Ø(() - (0)) /12 S 02 for some 0 < C1 S C2 < Do and for all t E T for some set of interest T, e.g., Swish- type or linear output layer. Recall that 0 0 0...... 6ml where 0, [a.j by]. Also denote 0* = -i..... 0% where
3.3.1. ESTIMATING SAMPLING SCORES
The relation in (11) requires calculating the scores from Definitions 3.3 and 3.4 for 0*, which is infeasible since 0* is unknown. A solution is to approximate these nonlinear scores with ones independent of O.
Sampling with near-optimal probabilities has been stud- ied in RandNLA (Drineas & Mahoney, 2018; Woodruff et al., 2014), where is known that if leverage or row-norm scores, } are approximated by } such that (r, S f, the subspace embedding property (3) holds with sample size (ploogpp/))/ (Ste)))))) If nonlinear scores can be similarly approximated in manner independent of 0, we can sam- ple according to the approximate scores and still obtain a guarantee of the form (10) for any 0-
0 [aj. bj]. Suppose aj & for all j E 1, m. Let
> 0 be such that min,(a;)² 2 2 l and 0
oo be such
that ΣØ- (11b:12 + (a3))) I u. Define the set
C { [a,, bi,.bi.... am bml
min (az)² 2 L
-=I...,m
Σ (1bb)) + (az)²) S
Within the context of the specific models considered in Examples 3.1 and 3.2, we demonstrate that leveraging the structure of the nonlinear adjoint operators enables the esti- mation of the nonlinear scores.
Clearly, by construction, O" E C. After some algebraic manipulations (see Appendix for any x; and any 0 E C. we have
Example 3.3 (Generalized Linear Predictors). Consider the class of generalized linear predictor models from Exam- ple 3.1 with any activation function & such that there exist
dd |x, 2 [0)) < ozu |x
6

---

Importance Sampling for Nonlinear Models
where E7 (0) is the adjoint operator of
Also, let Og E E be such that 1033 loss of generality, wise we can simply increase the size of the net inside C' by O ((VE)) From Lipschitz continuity and (10), we get
eR. Without
can assume 0g- Ne n C as other-
m
(((0) Σ
diaag max 0)).
(()3) - [())) + +eR L(J,X, R2)
This implies that
P (0) 2
< 1 - &
(s()n) + + L(f. X. R)
maxfequ, 13
00)
Th min (ij,1,,211)
x, R)) + + DER-L(f... X, R), $ I - & (Cs(0))+ER L(J.X,
F (
which gives the lower bound
where Tú is the norm score for the tth row of
Ls Os 2 (1 ()3') 5(2 -,,, Rt).
]'
X
mmi(()
X1
X2 mé² (0)
mon (0)
Xx
E [=x((++))
Combining this with (11), we get
This implies 3 = minf 1 max(cuu.
- L(f ((,, RR).
[(0)) 1-5 1- (2-
E
3.3.2. LOWER BOUNDING (s))))
The culmination of the above discussions and derivations leads to the main result of this paper.
Let 0" denote a solution to (1), and consider ball with radius R. chosen large enough contain 0", denoted by Bi For any E (0, 1), we pick discrete subset S R such that, for every 0 E Bi there exists at least one 0' E No satisfying 10-0001 12 < ER. The size of this set can be shown to be NN1l E 2 (1/e²). This construction is well-known and is commonly referred to as an e-net; see Appendix A.4.
Theorem 3.1 (Main Result). Suppose 0 E EC is a solution
to (1) with squared loss E(t) = 12 and for some 0 < 3 S 1, we have (T) S Ti forf i = 1, ..... n and for all Consider random sampling according to Tq with a sample S of size at least O ((p log(p/ 0) + p² log(p/E)) /(B=)) for some E E (0, 1) and 8 E (0, 1). Let O'g be defined as in (12). Then (2) holds with probability at least 1 - 8.
C.
This s-net construction enables a union bound argument to control the probability of (10) for all 0 E We. Suppose S can be sampled according to uniform estimate of the nonlinear scores, as described in Section 3, so that S no longer depends on the choice of 0. If, for a given 0, (10) fails to hold with a probability of at most 8', then a union bound ensures that the overall failure probability of (10) for all 0 E NV cannot exceed [N[]8'. By choosing 8' = 8/ I dsP, we ensure (10) holds with success probability of at least 1 - 5 for all 0 e NN..
Remark 3.3. Theorem 3.1 applies to more generally than single index models. However, when adapted to Example 3.3, it provides a result similar to Gajjar et al. (2024). While both works have the same dependence on E, our result has quadratic dependence on the dimension, while theirs is linear. Additionally, our approach involves constrained optimization subproblem (12), whereas the subproblems of Gajjar et al. (2024) are unconstrained. In contrast, Gajjar el al. (2024) provided a guarantee of the form (4) with a potentially large constant C >> 1, while Theorem 3.1 provides more desirable guarantee of the form (2).
Suppose Ls(.) is continuous on Bi which is almost always guaranteed for many loss functions in MI. The compactness of the ball implies that Cs(.) is also Lipchitz continuous with respect to A on B i.e., for any set of samples S, there exists a constant 0 < L(S, X, S, R)- 0o such that for any 0,6 0 B. ((') < T(S,X,S, S, R)] 0 0' ||2- Note that the Lipschitz continuity constant may depend X, S, f. and the radius of the ball B Define L(f, X, R) & maxs [.( X, S, R). Note that this is a maximization over a finite collection of numbers' and hence L(f, X, Rt) < co.
4. Experiments
We conduct a series of experiments to demonstrate the effec- tiveness and versatility of the proposed nonlinear importance scores. First, we evaluate our approach on several bench- marking regression datasets, including California Housing Prices (Pace & Barry, 1997), Medical Insurance dataset (Lantz, 2019), and Diamonds dataset (Wickham & Sievert, 2009). As proof of concept, we demonstrate that our im- portance sampling method outperforms traditional linear and uniform sampling strategies by achieving lower train- ing error using fewer samples. Second, we consider image classification using four standard datasets: SVHN (Street View House Numbers) (Netzer et al., 2011) FER-2013
Now, suppose C S B with 0 C. and let
0 E arg min (0). dEc
(12)
'The total number of possible unordered samples of any size from n object with replacement is given by Σx=1 (n+a-1) 1).
7

---

Importance Sampling for Nonlinear Models
(Facial Expression Recognition) (Goodfellow al., 2013), NOTMNIST (Bulatov, 2011), and QD (Quick, Draw) (Ha & Eck, 2018). Here, we demonstrate that our proposed non- linear leverage scores in Definition 3.3 serve as a powerful diagnostic tool, identifying the most "important" points in training complex models and detecting anomalies by isolat- ing outliers. We employ both single-index models and neu- ral networks validate our findings across varying model complexities and architectures. Additional experimental details are provided in Appendix A.5, The code is available here.
0.5
Log Relative Error
0.0
RN-A
-0.5-
-1.0
-1.5-
-2.0-
-2.5
2
4
6
Percentage of Dataset
(a) California Housing Dataset
Regression Tasks. We compare the efficacy of three sam- pling methods: uniform sampling, linear importance sam- pling (based on leverage scores and row-norms of the origi- nal dataset), and nonlinear importance sampling as defined in Definitions 3.3 and 3.4. While computing nonlinear im- portance scores directly is impractical in real-world scenar- ios, these experiments serve to validate that such scores effectively identify critical samples. As shown in Figure 1, nonlinear importance sampling more effectively identifies impactful samples, achieving lower MSE with fewer train- ing points compared uniform and linear sampling. The Y-axis for regression tasks reports relative error on loga- small vertical shifts represent substan-
AN
Log Relative Error
-0.5
-1.0-
-1.5
-2.0-
2
8
Percentage of Dataset
rithmic scale, tial absolute improvements.
(b) Medical Insurance Dataset
1.0
RN-
Classification Tasks. We convert the datasets into binary classification tasks, comparing visually similar ("like") and dissimilar ("unlike") classes, in SVAN and NotMNT ST. "like" classes are those that are harder to distinguish without prior knowledge, while "unlike" classes are more easily sep- arable. In SVHN, examine two scenarios: distinguishing the clearly distinct digits "1" vs. "0" and the more visually similar "1" vs. "7." Similarly, in NOTMNIST, we consider letter pairs (A vs. B) and (B vs. D). We also analyze more complex, noisy datasets like QD, where we distinguish be- tween "Fish" and "Car." For FER, which groups expressions by valence (positive vs. negative) based on (Mollahosseini al., 2017), we track the evolution of important samples the model approaches optimal parameters (x55% at initial- ization, x65%, and =55% accuracy at termination).
0.5
Log Relative Error
UN
-0.5
-1.0
-1.5
0.3
0.4
Percentage of Dataset
(c) Diamonds dataset
Figure 1. Comparison of sampling strategies. The Y-axis shows log ((C(0)) - L(( [(0") against sample size (as a percent- age of total data), where 03 is the optimal parameter from training on sampled data. "RN", "LS", and "UN" denote Row Norm, Lever- age Scores, and Uniform Sampling, respectively, with "L" and "A" indicating linear and adjoint- -hased nonlinear variants. Nonlinear importance scores consistently outperform all other alternatives.
Figure 2 presents images with the highest (most unique) and lowest (easiest to classify) nonlinear leverage scores for each binary task. The results clearly show that samples with higher nonlinear leverage scores contain distinct patterns and are harder to classify, while those with lower scores are straightforward. In contrast, standard linear leverage scores select more random and less meaningfuu/insihhtuul samples. Notably, our method identifies mislabeled and noisy samples with high scores, which represent the outliers. In FER, under-trained models highlight blank or extreme valence, whereas trained models detect subtler emotions and facial characteristics such as accessories, tears, and ag- ing. To demonstrate that nonlinear scores also yield robust
quantitative evidence for our classification experiments, we provide additional numerical results in Appendix A.6. Addi- tional images supporting Figure for all datasets are given in Appendix A.7.
8

---

Importance Sampling for Nonlinear Models
16
18
108
312
0
312
7
383
170
712
7 7
1
0
14
0
0 p0 KO 31
1
1
12
7
1
7
SVHN High
0)
(h) SVHN Low (1
SVHN High
7)
(d) SVHN Low (1
BBBBB
BDBBD
K
P
B A
AHOB
B
d
B
B
(e) NOTMNIST High (A vs B)
(I) NOTMNIST Low (A vs B)
(g) NOTMNIST High (B vs D) (h) NOTMNIST Low (B vs D)
(i QD High
(i) QD Low
(k) FER High
(1) FER Low
Figure 2. Comparisons of high and low linear/nonlinear leverage scores across multiple datasets. "High" and "Low" refer to images with the highest and lowest scores, respectively. In subfigures (a)-()), the top row shows images selected using nonlinear leverage (Definition 3.3), while the bottom row uses lincar leverage scores. Samples with higher nonlinear scores contain distinct patterns and are harder to classify, while lower scores correspond straightforward samples. In contrast, lincar scores select less insightful samples. Notably, our method identifies mislabeled and noisy samples (outliers) with high scores. In FER, the top three rows represent the scores calculated at 75% (final), =65%, and =555% (initial) training accuracy, while the bottom row uses linear scores. Under trained models highlight extreme expressions, while fully trained models detect subtler emotions and facial features like accessories, tears, and aging.
5. Conclusions and Further Thoughts
Although Appendix A.3 outlines preliminary steps toward extending the theoretical guarantees beyond squared loss objectives, fully generalizing them remains an avenue for future work. By estimating nonlinear importance scores without the model parameters, we substantially reduce the classic schicken-and-egge coupling between sampling and estimation. The subsequent constrained optimization still introduces mild dependence the unknown solution, leav- ing open challenges for fully parameter-agnosti importance sampling in nonlinear settings.
We introduced unifying framework that extends impor- tance sampling from linear to more general nonlinear mod- els, through the notion of the adjoint operator of nonlin- ear map. This perspective yields sampling schemes with approximation guarantees analogous to linear subspace em- beddings. yet it is applicable to a wide range of models. Our theoretical analysis shows that these generalized scores of- fer strong performance bounds and our experiments demon- strate concrete benefits in reduced training costs, improved diagnostics, and outlier detection.
As shown, in many cases the computational cost of approx- imating our nonlinear importance scores is comparable to that of existing sampling techniques in the linear regime, as both rely on similar fundamental operations. In such cases, the only additional overhead typically stems from comput- ing the nonlinear dual matrix. Thus, our framework in many cases does not introduce any fundamentally new compu- tational bottleneck beyond those already present in linear importance sampling methods. As result, the practical run- time overhead is largely governed by implementation-lewe factors, such as the choice of optimization algorithm and hyperparameter settings.
While we did not explicitly address active learning or trans- fer learning scenarios in this paper, our nonlinear importance sampling approach can naturally be utilized in such contexts. In particular, the method of subsampling based on nonlinear scores can be viewed as one-shot active learning strategy, where selecting the most informative samples significantly reduces labeling costs. Similarly, these nonlinear scores could also be beneficial in analyzing transfer learning, by effectively identifying samples from source domain that best represent the characteristies of a target domain.

---

Importance Sampling for Nonlinear Models
Acknowledgments
Chen, X. and Derezinski, M. Query complexity of least absolute deviation regression via robust uniform conver- gence. In Conference Learning Theory, pp. 1144- 1179. PMLR, 2021.
We sincerely thank Cameron Musco for their valuable feed- back and discussions. This research was partially supported by the Australian Research Council through an Industrial Transformation Training Centre for Information Resilience (IC200100022).
Chen, X. and Price, E. Active regression via linear-sample sparsification. In Conference on Learning Theory, pp. 663-695. PMLR, 2019.
Impact Statement
Clarkson, K. L. and Woodruff, D. P. Low-rank approxima- tion and regression in input sparsity time. Journal of the ACM (JACM), (3(6):1-45 2017.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Cohen, A. and Vorere R. Approximation of high- dimensional parametric pdes. Acta Numerica, 24:1-159, 2015.
References
Apers, S.. Gribling, S., and Sidford, A. On com- puting approximate lewis weights. arXiv preprint arXiv:2404.02881, 2024.
Cohen, M. B. and Peng, R. Lp row sampling by lewis weights. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 183 192, 2015.
Avron, H., Maymounkov, P., and Toledo, S. Blendenpik: Su- percharging lapack's least-squares solver. SIAM Journal on Scientific Computing, 32(3): 2010.
Cohen, M. B., Musco, C., and Musco, C. Input sparsity time low-rank approximation via ridge leverage score sampling. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposhum on Discrete Algorithmss, pp. 1758- 1777. SIAM, 2017.
Avron, H., Kapralov, M., Musco, C., Musco, C., Velingker, A.. and Zandieh, A. Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In International conference on machine learn- ing, pp. 253 253-2622222222222222 262. PMLR, 2017.
Dereziáski, M. and Mahoney, M. W. Recent and upcoming developments in randomized numerical linear algebra for machine learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 6470-6479, 2024.
Avron, H., Kapralov, M., Musco, C., Musco, C., Velingker, A., and Zandieh, A. universal sampling method for reconstructing signals with simple fourier transforms. In Proceedings of the 51st Annual ACM SIGACT'S Symposium on Theory of Computing. pp. 1051-1063, 2019.
Drineas, P. and Mahoney, M. W. Lectures on randomized numerical lincar algebra. The Mathematics of Data, 25 (1), 2018.
Bietti, A., Bruna, J., Sanford, C., and Song, M. Learn- ing single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35: 2022.
Drineas, P., Kannan, R., and Mahoney, M. W. Fast monte carlo algorithms for matrices Approximating matrix multiplication. SIAM Journal on Computing, 36(1):132- 157, 2006a.
Bourgain, J., Lindenstrauss, J., and Milman, V. Approxima- tion of zonoids by zonotopes. Acta Mathematica, 162:73
Drineas, P., Mahoney, M. W. and Muthukrishnan, Sam- pling algorithms for lo regression and applications. In Proceedings of the seventeenth annual ACM-SIAM sym- posium on Discrete algorithm, pp. 1127-1136, 2006b.
- 141, 1989.
Bulatov, Y. Notmnist dataset. Google (Books/OCR), Tech. Rep. (enlinel Available: http://yaroslavvb. blogspot. i1/201 1/09/nottmisttoaoiiiionoo
html, 2:4, 2011.
Erdélyi, T., Musco, C., and Musco, C. Fourier sparse lever- age scores and approximate kernel learning. Advances in Neural Information Processing Systems, 33:109-122, 2020.
Buryšková, V. Some properties of nonlinear adjoint opera- tors. The Rocky Mountain journal of mathematics, 28(1): 41-59, 1998.
Canévet, O., Jose, C., and Fleuret, F. Importance sampling tree for large-scale empirical expectation. In Interna- tional Conference on Machine Learning, pp. 1454-1462. PMLR, 2016.
Eshragh, A., Roosta, F., Nazari, A., and Mahoney, M. W. Lsar: efficient leverage score sampling algorithm for the analysis of big time series data. Journal of Machine Learning Research, 23(22):1-36, 2022.
10

---

Importance Sampling for Nonlinear Models
Fan, J., Liao, Y., and Mincheva, M. High-dimensional variance matrix estimation in approximate factor 1odels1. Annals of statistics, 2011.
Hristache, M., Juditsky, A., and Spokoiny, V. Direct esti- mation of the index coefficient in single-index model. Annals of Statistics, pp. 395-623, 2001.
Feldman, D. Core-sets: Updated survey. Sampling tech- niques for supervised or unsupervised lasks, pp. 23-44, 2020.
Huggins, J., Campbell, T., and Broderick, T. Coresets for scalable bayesian logistic regression. Advances in neural information processing systems, 29, 2016.
Gajjar, A. and Musco, C. Subspace embeddings under non- linear transformations. In Algorithmic Learning Theory, pp. 656-672. PMLR, 2021.
Iwen, M. A., Needell, D., Rebrova, E., and Zare, A. Lower memory oblivious (tensor) subspace embeddings with fewer random bits: modewise methods for least squares. SIAM Journal on Matrix Analysis and Applications, 42 (1):376-416, 2021.
Gajjar, A., Musco, C., and Hegde, C. Active learning for single neuron models with lipschitz non- linearrisssss In International Conference on Artificial Intelligence and Statistics, pp. 4101-4113, PMLR, 2023.
Johnson, W. B. and Schechtman, G. Finite dimensional subspaces of lp. Handbook of the geometry of Banach spaces, 1:837-870, 2001. 2001.
Gajjar, A., Tai, W. M., Xingyu, X., Hegde, C., Musco, C., and Li, Agnostic active learning of single index models with linear sample complexity. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1715-1754. PMLR. 2024.
Kakade, S. M., Kanade, V., Shamir, O., and Kalai, A. Ef- ficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011.
Katharopoulos, A. and Fleuret, Not all samples are cre- ated equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525- 2534. PMLR, 2018.
Gittens, A. and Mahoney, M. Revisiting the nystrom method for improved large-scale machine learning. In Interna- tional Conference on Machine Learning, pp. 567-575. PMLR, 2013.
Langberg. M. and Schulman, L. Universal e- approximators for integrals. In Proceedings of the twenty- first annual ACM-SIAM symposiun Discrete Algo- rithuns, pp. 598-5988-988 SIAM, 2010.
Goel, S., Kanade, V., Klivans, A., and Thaler, J. Reliably learning the relu in polynomial time. In Kale, S. and Shamir, O. (eds.), Proceedings of the 2017 Conference on Learning T'heory volume 65 of Proceedings of Machine Learning Research, pp. 1004 1042. PMLR, 07-10 Jul 2017. URL https: http///ccediii// ngs mlr. .tt.psssss.////////mmpm.m.m../ss v 25t5//ee17a.... html.
Langley, Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Goodfellow, J., Erhan, D., Carrier, P. L., Courville, A., Mirza, M., Hamner, B., Cukierski, W., Tang, Y., Thaler, D., Lee, D.-H., et al. Challenges in representation learn- ing: A report on three machine learning contests. In Neural information processing: 20th international con- ference, ICONIP 2013, daegu, korea, november 3-7, 2013. Proceedings, Part III 20, pp. 117-124. Springer, 2013.
Lantz, B. Machine learning with R: expert techniques for predictive modeling. Packt publishing Itd, 2019.
Liu, Q. and Lee, J. Black-box importance sampling. In Artificial Intelligence and Statistics, pp. 952-961. PMLR, 2017.
Liu, Z., Wang, G., Zhong, S. H., Xu, Z., Zha, D., Tang. R., Jiang, Z. S., Zhou, K., Chaudhary, V., Xu, S., et al. Winner-take column row sampling for memory effi- cient adaptation of language model. Advances in Neural Information Processing Systems, 36. 2024.
Ha, D. and Eck, D. A neural representation of sketch draw- ings. In International Conference on Learning Represen- tations, 2018.
Har-Peled, S. and Mazumdar, S. On coresets for k-means and k-median clustering. In Proceedings of the thirty- sixth annual ACM symposium on Theory of computing, pp. 291-300, 2004.
Lucic, M., Faulkner, M., Krause, A., and Feldman, D. Train- ing gaussian mixture models scale via coresets. Journal of Machine Learning Research, 18(160):1-2 150,, 2018.
Härdle, W., Müller, M., Sperlich, S., Werwatz, A., et al. Nonparametric and semiparametric models, volume Springer, 2004.
Mahoney, M. W. and Drineas, P. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):697-702, 2009.

---

Importance Sampling for Nonlinear Models
Mahoney, M. W. al. Randomized algorithms for matrices and data. Foundations and Trends@ Machine Learning, 3(2):123-224, 2011.
Nelson, and Nguyên, H. L. Osnap: Faster numerical lin- ear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pp. 117-126. IEEE, 2013.
Mai, T., Musco, C., and Rao, A. Coresets for classification- simplified and strengthened. Advances in Neural Infor- mation Processing Systems, 34: 14:11643-1165, 2021.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., Ng, A. Y., et al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop on deep learning and unsupervised feature learning, volume 2011, pp. 4. Granada, 2011. URL http:://tfltt s www.noordddd///ousseeeeeee
Martinsson, P.-G. and Tropp. J. A. Randomized numer- ical linear algebra: Foundations and algorithms. Acta Numerica, 29:403-572, 2020.
Meng, C., Liu, E., Neiswanger, W., Song, J., Burke, M., Lobell, D., and Ermon, S. Is-count: Large-scale ob- ject counting from satellite images with covariate-based importance sampling. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 36, pp. 12034- 12042, 2022.
O'l L'reey-Rosebrrry. T., Villa, U., Chen, P., and Ghattas, O. Derivative-infoomeed projected neural networks for high- dimensional parametric maps governed by pdes. Com- puter Methods in Applied Mechanics and Engineering, 388: 1 14199, 2022.
Pace, R. K. and Barry, R. Sparse spatial autoregressions. Statistics & Probubility Letlers, 33(3):291-297, 1997.
Meng, X. and Mahoney, M. W. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fitth annual ACM symposium on Theory of computing, pp- 91-100, 2013.
Paschou, P. Ziv, E., Burchard, E. G., Choudhry, S., Rodriine W., Mahoney, M. W., and Drineas, P. Pca-correlated snps for structure identification in world- wide human populations. PLOS genetics, 3(9)=1660) 2007.
Mirzasoleiman, B., Bilmes, J., and Leskovec, J. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp- 6950-6960. PMLR, 2020.
Samadian, A., Pruhs, K., Moseley, B., Im, S., and Curtin, R. Unconditional coresets for regularized loss minimization. International Conference on Artificial Intelligence and Statistics, pp. 482-492. PMLR, 2020.
Mollahosseini, A., Hasani, B., and Mahoor, M. H. Affectnet: A database for facial expression, valence, and arousal computing in the wild. IEEE Transactions on Affective Computing, 10(1):18-31, 2017.
Sarlos, T. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS'06), pp. 143 152. IEEE, 2006.
Munteanu, A.. Schwiegelshohn, C., Sohler, C., and Woodruff, D. On coresets for logistic regression. Ad- vances in Neural Information Processing Systems, 31, 2018.
Schechter, E. Handbook of Analysis and Foundations. Academic Press, 1996.
Scherpen, J. M. and Gray, W. Nonlinear hilbert adjoints: Properties and applications to hankel singular value analy- sis. Nonlinear Analysis: Theory, Methods & Applications, 51(5):883 901, 2002.
Murray, R., Demmel, J., Mahoney, M. W., Erichson, N. B., Melnichenko, M., Malik, O. A., Grigori, L., Luszezek, P., Dereziński, M., Lopes, M. E., et al. Randomized numerical linear algebra: A perspective on the field with an eye to software. arXiv preprint arXiv:2302. 1474, 2023.
Stich, S. U., Raj, A., and Jaggi. M. Safe adaptive importance sampling. Advances in Neural Information Processing Systems, 30, 2017.
Musco, C., Musco, C., Woodruff, D. P., and Yasuda, T. Active linear regression for <, norms and beyond. In 2022 IEEE 63rd Anmual Symposium on Foundations of Computer Science (FOCS), pp. 744-753. IEFE, 2022.
Tolochinksy, E., Jubran, I., and Feldman, D. Generic coreset for scalable learning of monotonic kernels: Logistic re- gression, sigmoid and more. In International Conference on Machine Learning, pp. 21520-215417 PMLR, 2022.
Nabian, M. A., Gladstone, R. J., and Mcidani, H. Efficient training of physics-ifformed neural networks via impor- tance sampling. Computer- Civil and Infrastructure Engineering, 36(8):962-977 2021.
Tremblay, N., Barthelmé, S., and Amblard, P.-O. Determi- nantal point processes for coresets. Journal of Machine Learning Research, 20(168): 2019.
12

---

Importance Sampling for Nonlinear Models
Vershynin, R. figh-dimensional probability: An introduc- fion with applications in data science, volume 47. Cam- bridge university press, 2018.
Wickham, H. and Sievert, C. ggplot2: elegant graphics for data analysis, volume 10. springer New York, 2009,
Woodruff, D. P. et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2)11-177, 2014.
Xu, P., Yang, J., Roosta, F., Ré, C., and Mahoney, M. W. Sub-sampled newton methods with non-uniform sam- pling. Advances in Neural Information Processing Sys- tems, 29, 2016.
13

---

Importance Sampling for Nonlinear Models
A. Appendix
A.I. Proof of Proposition 3.1
Proof. We first note that by Euler's homogeneous function theorem, the gradient of & is positively homogeneous of degree i..,
h(tt) 10-1 2 h(0),
Vt
00
00
We have,
f(t dt //'
a h(t0) (h(t0))
(0)
00
0
//"
1-o 0
a ( (( = (L. e- (-)
00 h0).
(13)
00
Now letting
1/a
t
h(0)
gives
/aaa)/a
1
8
ds.
ah(O)
h(())
It follows that
(h)
(a-1)/a
8 (1-a\/a
0
(0) =
g((s)ds
ae (0)
h(0)
ah(O)
h(0))
ah(0)
ph(0)
(())ds)
ah(O)
and hence,
f" (0) g(h(()) ( 9(0)
8
00 h(0).
a (h(0))
is such that h0)) = 0, then from (13), we get
(0)
(0)
00 h())
A.2. Norm Score Approximation for Example 3.4
Consider Example 3.2 with such that such that e₁ S (Ø(1) - (0))2/12 S 02 for some 0 < ci I 02 < oo and for all t e T for some set of interest T. e.g., Swish-type or linear output layer. Recall that 0 [0....., @m] where O, [a, by]. Also denote 0+ (ii.... 0% where 0j = bū). We get
f (0)1 = Σ
r (0,)11 = Σ 23 (Imax (b),,)) + ||x|| ((00)))00))
1=1
Ø=1
where
R' A ø(a, max { {b,,, x)) 6(0)
2az max ((b,, x).0}
14

---

Importance Sampling for Nonlinear Models
For any X,, denote
m
f:(0) Σ (0,)
Σ sz max {(b,, xs), 0}).
Suppose for some j E (1,2,.... .., m.) (by: x1) > 0, otherwise (7) O. We have,
m
Σ 1j (1bbb + :oo)) 1xx,12
m
a |x|||
[(ba ((b, x,),,x)),,0 011² + az -|xx1| 1(())))))0)) -
By assumption on o, it follows that
m
m
||x|| 2
[Imax x(b,,x)),00 xi) xH) + a² ||x/|| 1 (()))))))))
S C2
Σ [/b)] + xo)) |xx|||
i=1
Assume aj * 0 for all; j 1,2..... m. Let I
0 be such that miny(a3)? I and 0 oo be such that
Σラ (lbb]l + (az)2) S u. Define the set
c
[al, bi,.b...... Om, bm] min
(at)² 21, 1 Σ [1b;](+(a3})) suf
Clearly, by construction, 0t C. It follows that that for any 0 E C, have
eil ||x| 11 < (0)]² S czu |x:| 11
which in turn gives
min(cal,1} (|xx/] + m² m0))) < [0) | s maxfczu, 13 (IIx/ 11x + =m²)(
This implies that
(0)
(max(c2u, 1}
|x: || + m²)?((0)
mmax feax((221) (c2u,
7; (0)
(0)
S
minfcr1,13
X
+ m² 03=10((0)
min [cil, 1]
Ti.
F
where 7i is the norm score for the 7th row of
x mΦ (0)
moz(0)
x
(d+1)
x]
mon (0)
This allows us to pick min(cil, 1)/max//22/0 1) Theorem 3.1.
A.3. Beyond Nonlinear Least-squares.
Going beyond nonlinear least-squares settings, it turns out that an extension of our adjoint based approach still applies as long as the map f has suitable homogeneity properties. More precisely, consider (1) and suppose E a nonnegative loss and f is positively homogeneous of degree a, e.g., ReLU and varaints such Leaky ReLU. Since l is nonnegative loss function, define
(()) 2 VE(F()).
"Reaall that function s positively homogeneous of degree a if vi(1)) (0)) for any >> 0: see (Schechter, 1996) for details on positive homogeneity.
15

---

Importance Sampling for Nonlinear Models
Analogously to Definition 3.1, for any given and 0, we define
a (10)dl
h0) -
00
1/² 2
((T(10))
(t0)ddt
(V((((tO))
00
f()
a dt d0 (0,x)
ta-1
V((I=)(O))
where the last equality follows from Euler's homogeneous function theorem. Now, letting =t=s(0), have ds at- f(0)dtt which gives
(1,00)
((0) (()) ds
h-(0)= af(()
00 f(0)
Ve(+)
VE(F(O)) Ve(0)
00 (
af(
Since h(0)= = h(0) + (b)(0), 0), we can define
(0) = [h)(0)
h(0)
get
C(0) = Σ ((((O)) = ーΣ (h)
=11
2=1
Σ ((:(0)) 2 = 0
where (0) is defined analogously to Definition 3.2. Now, similar to the case of nonlinear least-squares, importance
sampling according to leverage scores or norms of (h;(0), give sampling approximations of the form (10).
A.4. Construction of the e-Net in Section 3.3.2
Let 0* denote solution to (1), and consider a compact ball with radius Rt chosen large enough to contain 0-. Let B denote this ball. For any E E (0, 1), we pick discrete subset N S B3 such that, for every Big there exists at least one 0' Mr satisfying
0 0'1 S eR.
The construction of an s-net reduces an uncountable continuous set a finite covering set; see Figure For completeness, we provide some details here. The reader encouraged to consult references such as Woodruff al. (2014); Vershynin (2018) for further discussions and details.
To find an upper bound the cardinality of the set [Wel. one can use standard volume and covering number arguments. Recall that the volume of B is
Tp/2 R T [ +1
Vol(Br)
where I' is Fuler's gamma function. A bound on WWel can be obtained as the number of small balls with radius e RR/2 that cover the larger ball of radius (1 + R) which is given by the ratio of their respective volumes:
(1 + " R
(1+2)
))²²
2 p E
WE >
1
2
16

---

Importance Sampling for Nonlinear Models
(1 (1+2/2)R
R
ER/2
BR
Figure Illustration an e-net covering BR. The larger circle has radius (1 + e/2)R, while Bh has radius Blue dots denote the e-nel, and dashed circles of radius eR/2 cover all points.
A.5. Further Details for Section 4
Classification Experiments. To carry out the experiment an under-parameterized setting, the dataset was balanced, and the images were resized to 10 x 10 dimensions with a grayscale background. A fully connected MLP was trained with a linear 100-input layer connected a hidden layer with 10 neurons and a ReLU activation unit, followed by a sigmoid output transformation function. The optimal weights were computed using PyTorch, with the Adam optimizer for 1000-5000 These optimal weights were then used to calculate the
epochs (depending on the dataset) and BCEWithLogits nonlinear leverage scores in Definition 3.3 for each data point.
Regression Experiments. Here, we train a single-index model using bounded output transformation function described Example 3.3, with e = 1 and C2 = After training for 30,000 epochs, we obtaín the optimal parameters and compute the nonlinear importance scores for each data point, as well as the classical linear leverage/row-nont norm scores using the original data matrix. We then sample training instances using a stratified strategy, proportional these scores, and evaluate how well each sampling strategy preserves the training performance. Specifically, we solve the subproblem outlined in (12). The experiment is repeated multiple times, and measure the median log relative error between the MSE of the parameter 0' on the full dataset and the optimal MSE obtained by training on the full dataset, i.e., ((g()(03) ((0*))/L(() as function of the number of samples selected (the number of samples were chosen depending on the total size of the dataset).
A.6. Quantitative performance for Qualitative datasets
In this section, we show that the datasets presented in Figure 2 serve not only as qualitative illustrations but also as quantitative evidence that sampling based on nonlinear scores helps reduce the training mean squared error (MSE) loss more effectively than alternatives. This reduction is more clearly observed when the loss is plotted on a logarithmic scale. We support this result with experiments on two datasets, SVHN (digits vs. 0) and QD, comparing nonlinear leverage score sampling to linear leverage score sampling and uniform sampling.
17

---

Importance Sampling for Nonlinear Models
4.8
UN
5,4
LS
L5
Log MSE
4.6
Log MSE
5.2
5.0
4.4
4.8
4.2
4.6
0.0
0.5
1.0
1.5
Percentage of Dataset
Percentage of Dataset
(a) SVHN vs 0) Dataset
(b) Quick Draw dataset
Figure 4. Illustration of quantitative results datasets used in Figure 2, SVHN & QD. The Y-axis shows Log(MSE) training data against sample size (in percentage of total data). "LS" and "UN" denote Leverage Scores and Uniform Sampling schemas, respectively, with "L" and "A" indicating linear and adjoint-based nonlinear variants.
A.7. Additional images from Section
To facilitate further comparisons, we provide an additional 50 images with the highest and lowest leverage scores for each dataset from the classification experiments Section 4.
0
1
60t
1421
5000 0
51
21
21
407
117515112
19
50
18
312
11650
303
166'1
11
205
50031
81
118
0
41
V
905
61
502
14
160
50
20
108
514
3C2
(a) SVHN High (1 0) Nonlinear Leverage Scores
(b) SVHN Low (1 vs 0) Nonlinear Leverage Scores
14
0
0
140
0
0
0 0
0
10.00
0
20 0 0 10803
0
0
10
0
0
100
10
10
140
40
50 1
1000
13
0
16
13
1
160
1444
10
1
10
101
10810711
181
10
1
303
0
18
100
11(
1000
20330
19
1100000
00000
30 20
100
17
0
1
11
10
1
O
0 0
0
0
0
20
09 0
10327
(c) SVHN High (1
Linear Leverage Scores
(d) SVHN Low vs 0) Linear Leverage Scores
18

---

Importance Sampling for Nonlinear Models
3/2170
7
07
383
172
419
57
7
7
7
7
7
7
7
7
+
7
640
2/3
5157
712
212
7
7
7
7
7
27
7 57377
322
13
176
786
7
7
17
5
7
7
7
7441
57
25 71
1124
1621457
77 7
7 7
7
7
7
7
7 7
27
67541
Z1S 1927
17451
110
(7
7
7
1
7
7
7
(c) SVEN High (1 vs 7) Nonlinear Leverage Scores
(f) SVHN Low (1 vs 7) Nonlinear Leverage Scores
74
1
1
7
1
27
4
575
7
1
7
7
11
77
6767
7
21
51.1
1
7
711
1
1
7
7
2
51
175
7
11
107
77
2
72
27
21
BZ
715
3.7
74
7
7
5Z.51
ST
$1
[101
17
7
12
7
Z
7 7
87
1 OZ
7022
215
7
121
7 (721
7
19
7
7
Z
27
7
7
7
7
7
|7
187
15
(g) SVIN High (1 vs 7) Linear Leverage Scores
(h) SVHN Low vs 7) Linear Leverage Scores
Figure 5. Top 50 images with the highest and lowest nonlinear leverage scores in each grouping for the SVHN dataset.
9
B
BEEBBEEBBE BBBBBEBBBB
5
D
B
O
BBBEBBBEBB
O
O
H
BBB
A
A
S
ABG
c
BBREBBREBB
(a) NOTMNIST High (A vs B) Nonlinear Leverage Scores
(b) NOTMNIST Low (A vs B) Nonlinear Leverage Scores
A
AAAAARRTEE DARAL POAPAAD
O
BO
B
A R
O
A
E
B
B
O
0A B
BOAT
TA
A
RAAL
B
BD
BA
- A AA
3
=
AAA
(c) NOTMNIST High (A vs B) Linear Leverage Scores
(d) NOTMNIST Low (A vs B) Linear Leverage Scores
19

---

Importance Sampling for Nonlinear Models
B
BBB
B
B
B
B
B
BB
D
BBB
B
B B
B
B
B
D
B B B
B
BBBDD
D B
B
(e) NOTMNIST High (B D) Nonlinear Leverage Scores
(f) NOTMNIST Low
D) Nonlinear Leverage Scores
BBBBEBBEBB d BLEBBEBBBBE
d2
B
B
B
B
C
B
B BI B B
WORR
BBBBBBBI B
B
B
D
BBB
B B
B
B
(g) NOTMNIST High (B vs D) Linear Leverage Scores
(h) NOTMNIST Low (B vs D) Linear Leverage Scores
Figure 6. Top 50 images with the highest and lowest nonlinear leverage scores in each grouping for the NOTMNIST dataset.
K
1
8
8
$)
$
8
4
5
6
60
04
(a) QD High Nonlinear Leverage Scores
(b) QD Low Nonlincar Leverage Scores
88
D
2+2
AA
(c) QD High Linear Leverage Scores
(d) QD Low Lincar Leverage Scores
Figure 7. Top 50 images with the highest and lowest nonlinear leverage scores for the QD dataset.
20

---

Importance Sampling for Nonlinear Models
(a) FER 75% High Nonlinear Leverage Scores
(b) FER 75% Low Nonlinear Leverage Scores
(c) FER 65% High Nonlinear Leverage Scores
(d) FER
65% Low Nonlinear Leverage Scores
(e) FER 55% Nonlinear Lever- age Scores.
n FER High Linear Leverage Scores
(g) FER Low Linear Leverage Scores
Figure 8. Top 50 (trained and linear settings) and 16 (under-trained setting) images with the highest and lowest nonlinear leverage scores for valence expression on FER dataset. (e) only 16 images had non-zero scores at initialization.
21


Reviews:
[{"review_id": "szIFKt2Yuc", "reviewer": "Reviewer_Nx6D", "summary": "This paper introduces a novel family of distributions that extends leverage score distributions—widely used in subset selection for linear models—to nonlinear models. The key component of this construction is a newly defined nonlinear adjoint operator, which satisfies the identity:\n\n$L(\\theta) = \\|\\|\\hat{F}^{*}(\\theta) \\hat{\\theta}\\|\\|^2,$\nwhere $\\hat{\\theta}:= [\\theta|1]$.\nThis mirrors the classical case in linear regression, where the loss function satisfies:\n\n$L(\\theta) = \\|\\|X \\theta - y\\|\\|^2 = \\|\\| \\hat{X} \\hat{\\theta}\\|\\|^2,$\nwhere $\\hat{X}:= [X|-y]$.\n\nLeveraging this formulation, the paper explores importance sampling based on these newly introduced nonlinear leverage scores. Specifically, it investigates conditions under which the following bound holds with high probability:\n\n$L(\\theta_S) \\leq L(\\theta^*) + O(\\epsilon)$\n\nwhere $S$ is the index set of $s$ samples drawn via probability weights determined by the nonlinear leverage scores, also referred to as nonlinear norm scores.\n\nThe authors focus on two classes of nonlinear models: generalized linear predictors and ReLU neural networks. In both cases, they demonstrate that nonlinear leverage scores can be upper bounded by linear leverage scores. Furthermore, they establish necessary conditions for the high-probability validity of the above bound when using the quadratic loss in a regime where the sample size scales nearly linearly with the dimension.\n\nFinally, numerical simulations illustrate the advantages of sampling based on nonlinear leverage score distributions over traditional linear leverage score distributions.\n\n## Update after rebuttal\nI would like to thank the authors for their response. I increase the score from 2 to 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Nx6D, we are grateful for the time and effort you devoted to reviewing our paper. We sincerely hope to address your comments and questions in detail below.\n### Scope of Theoretical Guarantees\n1. Thank you for your observation. While the examples in the paper (single-index models, ReLU networks) illustrate how the adjoint operator can be computed explicitly from Proposition 3.1, we would like to clarify that the\nmethod extends conceptually to broader classes of functions via its natural definition (Definition 3) through\nnumerical integration.\n2. While our approach can conceptually extend to broader\nnonlinear models, we agree that our current theoretical\nguarantees focus on squared losses. Appendix A.3 outlines initial steps toward more general losses, but fully\ndeveloping the theory in this setting remains an open\nchallenge we are pursuing. We will make sure to clearly\nstate these limitations in the revised version.\n### Numerical Experimentation (Figure 1)\n1. We agree that incorporating additional datasets would enhance the quality of our empirical evaluations. To address this, we have now included two additional datasets–one for classification & one for regression [(Please see here)](https://anonymous.4open.science/r/ICML2025Review/NewDatasets.pdf).\n2. We believe our method can offer substantial performance gains in many cases. The perception otherwise\nmay stem from our choice of axis scales, which make the graphs appear less visually impressive. In our numerical experiments, we used a log-scale on the Y-axis. However, we should have better highlighted that even a small shift on\na log-scale can represent a significant absolute difference. For example, in the California Housing Prices dataset,\ncomparing linear row-norm with non-linear row-norm, the shift from −0.75 to −2 in log-scale corresponds to a\nrelative error reduction from 18% to 1%. We will clarify this more clearly in the text.\n### Qualitative Interpretation of Classification Tasks (Figure 2)\nWe agree that our current results for the classification task rely on qualitative interpretation rather\nthan quantitative analysis. Our main goal was to\ndemonstrate the perceptual interpretability and diagnostic power of our framework, highlighting that our nonlinear scores capture meaningful information about the data\nthat would otherwise be unavailable. To our knowledge,\nthis is the first approach of its kind, introducing a new\ninterpretability & diagnostics paradigm for classification\nwith nonlinear models. However, we fully agree that incorporating quantitative\nmetrics would strengthen our work. To address this, we\nhave added two additional figures that compare the quantitative performance on two existing datasets, namely\nSVHN & QD [(Please see here)](https://anonymous.4open.science/r/ICML2025Review/Fig2Quant.pdf).\n### Fundamental Challenges\nOur theoretical guarantees are flexible in that the underlying sampling distribution only requires approximations to the nonlinear scores that are independent of the parameter being optimized. In many cases, as demonstrated in Examples 3.3 and 3.4, such parameter-independent estimates can be obtained, making our approach less susceptible to the “chicken-and-egg” problem you mentioned.  \n\nHowever, obtaining a solution $\\theta_{S}^{\\star}$ that satisfies (2) requires solving a constrained optimization problem, where the constraint set must be large enough to contain the true solution $\\theta^{\\star}$. Hence, while our approach relaxes the dependency of the sampling distribution on the parameters being optimized, it still relies on a constraint that implicitly assumes some prior knowledge of $\\theta^{\\star}$. As a result, the core issue you highlighted remains an inherent challenge.  \n\nAddressing this “chicken-and-egg” problem in broader nonlinear contexts remains an open problem. We will ensure that these limitations are discussed more prominently.\n### Literature on Coresets\nThank you for pointing this out, and we apologize for\nthe oversight. Although we briefly mentioned the idea\nof coresets and their applicability beyond linear embeddings on page 2, we will ensure that the final version\nincludes a dedicated related work section on coreset\nframeworks.\n### Strengthening Theorem 3.1\nThank you for the thoughtful question. Our approach\naims to construct a sampling distribution that is independent of the parameter being optimized. Accordingly,\nour theory allows for an approximation of $\\tau_i(\\theta)$ in the\nform of $\\tau_i$, which serves as a uniform bound for all $\\theta$. As you noted, this can lead to conservative guarantees, potentially requiring a larger sample size than necessary.\nIn our experiments (Figure 2 (k, i)), we observe that importance scores become more informative as the model nears optimality. Motivated by this, we are exploring how to replace the uniform bound with one at the optimal point, $\\tau_i(\\theta^{\\star})$, and its implications for theory. A full development is left for future work.", "claims_and_evidence": "- While the claims about the novelty of the construction are valid. The claims about the theoretical guarantees are overstated, since they are only valid for the squared loss, and they are only applicable for a limited family of nonlinear models. \n\n- The claims about the numerical performance are barely substantiated by the shown results: while we can observe that the use of nonlinear leverage scores leads to an improvement compared to the use of the classical leverage scores, the improvement is marginale and barely noticeable (e.g., Figure 1-b). Moreover, for the classification task, the comparison between non linear leverage scores and linear leverage scores is at best qualitative.", "methods_and_evaluation_criteria": "A quantitative evaluation of the methods was only conducted for two datasets. The rest of the experimental section is based on a qualitative comparison that is not relevant to illustrate the theoretical guarantees established in Section 3.", "theoretical_claims": "All proofs were examined, but not carefully checked, and no glaring mistakes were identified.", "experimental_designs_or_analyses": "See Methods/Evaluation criteria.", "relation_to_broader_scientific_literature": "The use of importance sampling to build coresets for linear models has been extensively studied in recent years, leading to the development of a new subfield at the intersection of machine learning and randomized linear algebra. While linear leverage scores provide a robust solution to the subsampling problem from both theoretical and empirical perspectives, extending this framework beyond linear models has remained a persistent challenge for the community. Indeed, unlike in the linear case—where the leverage score distribution is independent of the optimal solution to the underlying optimization problem—existing approaches for non-linear models typically involve a chicken-and-egg problem, as the sampling distribution depends on the very parameter being optimized. While the proposed construction of the non-linear adjoint operator is elegant, it does not resolve this fundamental issue.", "essential_references_not_discussed": "Existing literature on coresets is missing from the section dedicated to related work (section 2). For instance:\n* Determinantal Point Processes for Coresets https://jmlr.org/papers/volume20/18-167/18-167.pdf\n* On Coresets for Logistic Regression https://arxiv.org/abs/1805.08571\n\nOverall the comparison with sensitivity sampling schemes is missing in the line of [Langberg and Schulman 2010].\n\nLangberg, M. and Schulman, L.J., 2010, January. Universal $\\epsilon$-approximators for integrals. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms (pp. 598-607). Society for Industrial and Applied Mathematics.", "other_strengths_and_weaknesses": "The article is well written, and it is easy to follow for someone who is familiar with the litterature. The construction of the nonlinear adjoint operator is elegant, and the study of this operator would be of interest per se. \n\nA notable weakness is the lack of an extensive empirical validation. The comparison with linear leverage scores was restricted to two datasets, and the observed advantage of the newly introduced scores remains unclear.", "other_comments_or_suggestions": "-", "questions_for_authors": "1) Is there a way to strengthen Theorem 3.1. by assuming that sampling is done according to the $\\tau_i(\\theta)$ and not $\\tau_i$? \n\n2) Could you provide an empirical comparison, similar to Figure 1, for a task other than regression?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8JXYjiWkhH", "reviewer": "Reviewer_Z4FF", "summary": "The paper proposed a sampling method for important data by extend the norm and leverage scores in linear models to nonlinear models and reduce the computational complexity.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Z4FF, we sincerely appreciate the time you took to review our work. To the best of our ability, we aim to address your comments and questions in detail below.\n\n### Experiments with High-dimensional Data\nThank you for your observations and feedback. As mentioned at the outset in the introduction, we make the assumption that $n \\geq p$, i.e., the **underparameterized** setting. While the construction of our Adjoint Operator in Definition 3.1 remains\nvalid for all dimensions, the nonlinear scores in Definitions 3.3 and 3.4 only provide useful information when\n$n \\geq p$. Otherwise, if $p \\geq n$, the nonlinear leverage\nscores for all data points would be the same, meaning\nthat all data points are considered equally important in\nfitting the model. In this case, our sampling distributions imply a uniform sampling scheme rather than a\nnon-uniform importance sampling scheme.\n\nThis inherent limitation is also present across the field\nof randomized numerical linear algebra (RandNLA) and\nwidely used importance sampling methods such as leverage scores [1]. In fact, for many of the theoretical guarantees in RandNLA to be meaningful, the number of data\npoints must often be exponentially larger than the dimension. Unfortunately, extending importance sampling methods like leverage scores in a meaningful way to overparameterized settings, even in the linear case, remains an open problem.\n\nIn this light, we would like to clarify that in our setting,\n“high dimensional” is interpreted in terms of the number of observations rather than the number of features.\nWhile many of the datasets considered in our experiment\ncontain large numbers of observations, the underparameterized regime limits us from using more conventional\ndatasets that would result in overparameterization and\nlarge number of features.\n\n[1] Woodruff, D. P. (2014). Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1–2), 1-157.\n\n### Improving Convergence of Model Training\nThank you so much for your suggestion. We note that our main focus in the paper and our theoretical results concentrate on\nsampling complexity and its effect on loss approximation\nrather than the convergence speed of a given optimization\nmethod used for training. As you agree, convergence\nspeed can be influenced by many factors, such as the\nchoice of the optimization algorithm, selection of hyper-parameters, computing/network architecture, etc. While\nour results are not concerned with these factors, to address your question, we have provided a plot showing\ntraining time (in seconds) and relative error with respect\nto sample size for subsampling using nonlinear leverage\nscore (the results are consistent across different nonlinear sampling methods), offering insight into the tradeoff\n[(please see here)](https://anonymous.4open.science/r/ICML2025Review/Convergence.pdf). As shown, training a model sampled according\nto nonlinear leverage scores achieves $10^{−2}$ relative error\nfaster than the time it takes to train the model on the\nentire dataset. This speedup, coupled with the reduction\nin the cost of labeling the additional data, showcases the\nadvantages of our nonlinear scores in reducing overall\ncosts of training.\n\n### Additional Links\n1. New Datasets (Numerical Experimentation): [Please see here](https://anonymous.4open.science/r/ICML2025Review/NewDatasets.pdf)\n2. Existing Classification Dataset (Numerical Experimentation): [Please see here](https://anonymous.4open.science/r/ICML2025Review/Fig2Quant.pdf)", "claims_and_evidence": "The proposed methods for important data points in nonlinear models offer several advantages, such as reduced computational complexity, enhanced explainability, and improved outlier detection. These claims are supported by both theoretical analyses and experimental results.", "methods_and_evaluation_criteria": "The paper evaluates the proposed method on four standard datasets, but these datasets are relatively small, and the image sizes are quite tiny. While the results on these smaller datasets are useful for demonstrating the method's functionality, they may not fully represent the challenges of real scenario. The evaluation on larger datasets with higher-dimensional data would provide stronger evidence for the proposed approach.", "theoretical_claims": "The theoretical aspects of the paper are reasonable and well-justified.", "experimental_designs_or_analyses": "see Methods And Evaluation Criteria", "relation_to_broader_scientific_literature": "The paper effectively bridges the gap between existing methods used for linear models to nonlinear models.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper extends the concept of importance sampling from linear models to nonlinear models, which is highly meaningful, as most neural networks used today are nonlinear. The proposed method can improve the efficiency of training these models.\n\nThe paper provides a robust theoretical foundation for the proposed method, which supports its claims effectively.\n\nThe experiments demonstrate that the proposed method performs well on small subsets of datasets. However, it would be beneficial to compare the convergence speed of the proposed method, as this would provide additional insights into its practical efficiency.", "other_comments_or_suggestions": "see above", "questions_for_authors": "Does the proposed method improve convergence of model training?\n\nHow does the proposed method perform on larger datasets?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "we39NwN3D3", "reviewer": "Reviewer_JXa1", "summary": "The paper introduces a framework to generalize norm-based and leverage-score-based importance sampling from linear models to nonlinear settings. It uses adjoint operator of a nonlinear map, to do so. The authors demonstrate that their sampling methods provide guarantees analogous to linear models, enabling approximation results for nonlinear mappings.\n\n## Update after Rebuttal\nI appreciate the response provided by the authors and hope that the next version incorporates the required changes. Hence, I maintain a positive assessment.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JXa1, we sincerely appreciate the time you devoted to reviewing our paper and your comments. We aim to address your comments and questions in detail below.\n### Additional Sampling Methods in Classification\nThank you for the suggestion. While adding\nmore sampling methods would ideally strengthen our\narguments, we find that this is unfortunately not feasible, as most prior works are limited in the settings they apply to and do not extend to the nonlinear examples we have considered in the paper. We would like to note that many\nexisting methods are more restricted in the types of models they apply to, typically being linear or kernel-based,\nwhile our approach applies to general nonlinear models via the adjoint perspective. For example, L1 Lewis\nweights have been studied for linear predictor models,\ne.g., logistic regression, but are not trivially extended to\nthe nonlinear predictors we consider, e.g., single index\nmodel. To our knowledge, the only prior works applicable to our setting are that of Gajjar et al. (2023, 2024).\nHowever, their results rely on linear leverage scores, and\nthere is no general construction for nonlinear importance\nsampling like we offer in the paper. In this light, the plots\nin our paper labeled as ”LS - L,” i.e., those based on linear leverage scores, represent the expected performance\nfrom Gajjar et al. (2023, 2024).\n### Run Time Analysis\nOur theoretical focus was primarily on sample complexity and its effect on loss approximation, which in turn reduces the time complexity when training a sub-sampled\ndataset. Analyzing runtime depends on various components that are outside the scope of this work, such as the\nchoice of optimization algorithm, its hyperparameters,\nand the algorithm used for approximating the nonlinear\nscores. We will add a brief discussion in the revision,\nnoting that the cost of approximating these scores is analogous to the linear case and its associated components.\n### Utilizing Nonlinear Scores for Active/Transfer Learning\nThank you for raising this important suggestion. While\nwe did not explicitly discuss active or transfer learning in\nour paper, the general concept of “nonlinear importance\nscores” can be naturally extend to these areas. In an one-shot active learning setting, for instance, selecting the\nmost “informative” points would help reduce labeling\neffort. For transfer learning, one could use these scores\nto identify samples in a source domain that are most\nrepresentative of a target domain’s features. We will\nadd a discussion note in the final version outlining these\npossibilities to strengthen the paper.\n### Quadratic Dependence on $p$\nWe appreciate your comment. We recognize that many\nsubspace embedding results, including ours, exhibit an\n$\\mathcal{O}(p^2)$ sample-size term. However, as an upshot, we\nprovide a loss approximation guarantee of the form (2),\nwhich to our knowledge has not been done prior to our\nwork in the context of nonlinear predictor models such as\nneural networks (please see page 3, left column, lines 148–156, as well as \nRemark 3.2 on page 7).\n\nAchieving lower complexity for fully general nonlinear embeddings while maintaining a loss approximation\nguarantee of the form (2) remains an open challenge. In\nour work, we primarily operate in an underparameterized\nregime, where the number of features is not excessively\nlarge compared to the number of observations, i.e., $n \\gg p $, which\nmight help mitigate this issue to some extent. While we have noted this limitation in Remark 3.2, we will emphasize it more clearly and reference recent advances in randomized embeddings to highlight potential approaches and future directions for addressing this bottleneck in broader high-dimensional nonlinear settings.\n### Extension Beyond Squared-loss\nOur Appendix A.3 indicates that the framework extends\nconceptually to other positively homogeneous losses, but\nthe complete theoretical guarantees for general losses\nremains for future work. \n### Primary Computational Bottlenecks For Directly Calculating Nonlinear Importance Scores\nThanks for your question. For arbitrary nonlinear models,\ncomputing the adjoint operator may require numerical\nintegration if no closed-form expression exists. However,\nin more structured settings, such as single-index models or certain ReLU-based networks, explicit formulas\ndescribed in the main paper allow for standard matrix\noperations to calculate row-norm or leverage scores, similar to the linear case. For row-norm scores, one simply\nevaluates the norm of each row in the “nonlinear dual matrix.” For leverage scores, a QR or SVD-like factorization of the dual matrix is needed, for which standard randomized NLA techniques (e.g., approximate factorizations) can help speed up these factorizations. We will highlight these computational considerations in the next revision of our paper.\n### Additional Links\nhttps://anonymous.4open.science/r/ICML2025Review/", "claims_and_evidence": "The examples and propositions are supported with clear discussions.", "methods_and_evaluation_criteria": "Yes it does. It is based on the adjoint operator for non-linear maps, which complements the use of non-linear leverage scores.\nThe experiments in the paper compare the performance of a model trained on a smaller sample of training data. However, the classification task could be compared with more sampling methods.", "theoretical_claims": "The propositions and examples seemed correct, which was useful for understanding the idea and the practical and relevance. \n\nIn the main theorem, the running time analysis is missing.", "experimental_designs_or_analyses": "The experiment section supports the theoretical claims. \n\n- For the classification task, the comparison with L1 Lewis weights (like Mai, Musco, Rao, 2021) and leverage + uniform (like Munteanu, Schwiegelshohn, Sohler, Woodruff, 2018) are missing.", "relation_to_broader_scientific_literature": "Importance sampling has been extensively studied in linear model problems such as least square regression, clustering, etc. This result is a key towards non-linear subspace embedding which is due to the adjoint operator.", "essential_references_not_discussed": "All major relevant results are cited and discussed in the paper.", "other_strengths_and_weaknesses": "- $\\textbf{Strengths:}$ The paper introduces an innovative way of importance sampling for nonlinear models using the adjoint operator. Further, it offers theoretical guarantees backed by experiments. \n\n- $\\textbf{Weakness:}$ The experiments are compared with limited sampling methods. The theorem misses the running time discussion. For data in higher dimensions the quadratic dependence on the coreset size maybe a bottleneck for practical purposes.", "other_comments_or_suggestions": "Refered to questions.", "questions_for_authors": "- Can it be extended to losses other than squared loss?\n\n- Is it possible that the nonlinear leverage scores can be utilized for active learning strategies or transfer learning? If so, then you may also discuss this in the main paper to strengthen it.\n\n- What are the primary computational bottlenecks when directly calculating nonlinear importance scores? How can it be handled for high-dimensional data?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper uses the notion of adjoint operator and generalizes norm-based and leverage-score-based methods from linear to non-linear settings. The paper provides some theoretical analysis and considers the setting of generalized linear and RELU neural networks. It has limited experimental evaluations. I am leaning towards an accept if there is room in the program.
Decision: Accept (poster)