Importance Sampling for Nonlinear Models

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.

Additional Sampling Methods in Classification

Thank you for the suggestion. While adding more sampling methods would ideally strengthen our arguments, 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 existing methods are more restricted in the types of models they apply to, typically being linear or kernel-based, while our approach applies to general nonlinear models via the adjoint perspective. For example, L1 Lewis weights have been studied for linear predictor models, e.g., logistic regression, but are not trivially extended to the nonlinear predictors we consider, e.g., single index model. To our knowledge, the only prior works applicable to our setting are that of Gajjar et al. (2023, 2024). However, their results rely on linear leverage scores, and there is no general construction for nonlinear importance sampling like we offer in the paper. In this light, the plots in our paper labeled as ”LS - L,” i.e., those based on linear leverage scores, represent the expected performance from Gajjar et al. (2023, 2024).

Run Time Analysis

Our 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 dataset. Analyzing runtime depends on various components that are outside the scope of this work, such as the choice of optimization algorithm, its hyperparameters, and the algorithm used for approximating the nonlinear scores. We will add a brief discussion in the revision, noting that the cost of approximating these scores is analogous to the linear case and its associated components.

Utilizing Nonlinear Scores for Active/Transfer Learning

Thank you for raising this important suggestion. While we did not explicitly discuss active or transfer learning in our paper, the general concept of “nonlinear importance scores” can be naturally extend to these areas. In an one-shot active learning setting, for instance, selecting the most “informative” points would help reduce labeling effort. For transfer learning, one could use these scores to identify samples in a source domain that are most representative of a target domain’s features. We will add a discussion note in the final version outlining these possibilities to strengthen the paper.

Quadratic Dependence on $p$

We appreciate your comment. We recognize that many subspace embedding results, including ours, exhibit an $\mathcal{O}(p^2)$ sample-size term. However, as an upshot, we provide a loss approximation guarantee of the form (2), which to our knowledge has not been done prior to our work in the context of nonlinear predictor models such as neural networks (please see page 3, left column, lines 148–156, as well as Remark 3.2 on page 7).

Achieving lower complexity for fully general nonlinear embeddings while maintaining a loss approximation guarantee of the form (2) remains an open challenge. In our work, we primarily operate in an underparameterized regime, where the number of features is not excessively large compared to the number of observations, i.e., $n \gg p$, which might 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.

Extension Beyond Squared-loss

Our Appendix A.3 indicates that the framework extends conceptually to other positively homogeneous losses, but the complete theoretical guarantees for general losses remains for future work.

Primary Computational Bottlenecks For Directly Calculating Nonlinear Importance Scores

Thanks for your question. For arbitrary nonlinear models, computing the adjoint operator may require numerical integration if no closed-form expression exists. However, in more structured settings, such as single-index models or certain ReLU-based networks, explicit formulas described in the main paper allow for standard matrix operations to calculate row-norm or leverage scores, similar to the linear case. For row-norm scores, one simply evaluates 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.

Additional Links

https://anonymous.4open.science/r/ICML2025Review/

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.

Experiments with High-dimensional Data

Thank 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 valid for all dimensions, the nonlinear scores in Definitions 3.3 and 3.4 only provide useful information when $n \geq p$. Otherwise, if $p \geq n$, the nonlinear leverage scores for all data points would be the same, meaning that all data points are considered equally important in fitting the model. In this case, our sampling distributions imply a uniform sampling scheme rather than a non-uniform importance sampling scheme.

This inherent limitation is also present across the field of randomized numerical linear algebra (RandNLA) and widely 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 points 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.

In this light, we would like to clarify that in our setting, “high dimensional” is interpreted in terms of the number of observations rather than the number of features. While many of the datasets considered in our experiment contain large numbers of observations, the underparameterized regime limits us from using more conventional datasets that would result in overparameterization and large number of features.

[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.

Improving Convergence of Model Training

Thank you so much for your suggestion. We note that our main focus in the paper and our theoretical results concentrate on sampling complexity and its effect on loss approximation rather than the convergence speed of a given optimization method used for training. As you agree, convergence speed can be influenced by many factors, such as the choice of the optimization algorithm, selection of hyper-parameters, computing/network architecture, etc. While our results are not concerned with these factors, to address your question, we have provided a plot showing training time (in seconds) and relative error with respect to sample size for subsampling using nonlinear leverage score (the results are consistent across different nonlinear sampling methods), offering insight into the tradeoff (please see here). As shown, training a model sampled according to nonlinear leverage scores achieves $10^{−2}$ relative error faster than the time it takes to train the model on the entire dataset. This speedup, coupled with the reduction in the cost of labeling the additional data, showcases the advantages of our nonlinear scores in reducing overall costs of training.

Additional Links

1. New Datasets (Numerical Experimentation): Please see here
2. Existing Classification Dataset (Numerical Experimentation): Please see here

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.

Scope of Theoretical Guarantees

1. 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 method extends conceptually to broader classes of functions via its natural definition (Definition 3) through numerical integration.
2. While our approach can conceptually extend to broader nonlinear models, we agree that our current theoretical guarantees focus on squared losses. Appendix A.3 outlines initial steps toward more general losses, but fully developing the theory in this setting remains an open challenge we are pursuing. We will make sure to clearly state these limitations in the revised version.

Numerical Experimentation (Figure 1)

1. 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).
2. We believe our method can offer substantial performance gains in many cases. The perception otherwise may 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 a log-scale can represent a significant absolute difference. For example, in the California Housing Prices dataset, comparing linear row-norm with non-linear row-norm, the shift from −0.75 to −2 in log-scale corresponds to a relative error reduction from 18% to 1%. We will clarify this more clearly in the text.

Qualitative Interpretation of Classification Tasks (Figure 2)

We agree that our current results for the classification task rely on qualitative interpretation rather than quantitative analysis. Our main goal was to demonstrate the perceptual interpretability and diagnostic power of our framework, highlighting that our nonlinear scores capture meaningful information about the data that would otherwise be unavailable. To our knowledge, this is the first approach of its kind, introducing a new interpretability & diagnostics paradigm for classification with nonlinear models. However, we fully agree that incorporating quantitative metrics would strengthen our work. To address this, we have added two additional figures that compare the quantitative performance on two existing datasets, namely SVHN & QD (Please see here).

Fundamental Challenges

Our 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.

However, 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.

Addressing this “chicken-and-egg” problem in broader nonlinear contexts remains an open problem. We will ensure that these limitations are discussed more prominently.

Literature on Coresets

Thank you for pointing this out, and we apologize for the oversight. Although we briefly mentioned the idea of coresets and their applicability beyond linear embeddings on page 2, we will ensure that the final version includes a dedicated related work section on coreset frameworks.

Strengthening Theorem 3.1

Thank you for the thoughtful question. Our approach aims to construct a sampling distribution that is independent of the parameter being optimized. Accordingly, our theory allows for an approximation of $\tau_i(\theta)$ in the form 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. In 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.