Pith. sign in

REVIEW 3 major objections 5 minor 73 references

Importance Sampling for Nonlinear Models

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sampling by nonlinear adjoint-based scores gives nonlinear models the same additive loss guarantee as linear subspace embeddings, with no large multiplicative constant.

desk verdict The adjoint-based framework for nonlinear importance sampling is clean and worth knowing, but the neural-network guarantee collapses on Example 3.4's score-domination bound, and the main proof needs a patch around theta*. read the letter →

arxiv 2505.12353 v1 pith:XKUPJMTO submitted 2025-05-18 cs.LG cs.AIstat.ML

Prakash Palanivelu Rajmohan , Fred Roosta This is my paper · ORCID
classification cs.LGcs.AIstat.ML
keywords importancesamplingnonlinearadjointoperatorleveragescoresrandomizednumericallinearalgebraleastsquaressubspaceembeddingsamplecomplexityoutlierdetection
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Importance sampling—picking which data points to train on—has a rigorous theory for linear models, where row norms and leverage scores tell you which rows matter and subspace embeddings guarantee that a small sampled matrix behaves like the full one. This paper builds the same theory for nonlinear models. Its central device is the nonlinear adjoint operator, $f^\star(\theta)=\int_0^1 \partial_\theta f(t\theta)\,dt$, which rewrites any absolutely continuous map as $f(\theta)=\langle \hat\theta, \hat f^\star(\theta)\rangle$, turning a nonlinear least-squares loss into a matrix norm $\| \widehat{F^\star}(\theta)\hat\theta\|^2$. That single rewrite makes leverage scores and norm scores definable for nonlinear models, and the paper proves Theorem 3.1: if a parameter-free score dominates the nonlinear score by a constant $\beta$ on a set containing the optimum, sampling $s=O\!\big((p\log(p/\delta)+p^2\log(p/\varepsilon))/(\beta\varepsilon^2)\big)$ points gives a solution whose full-data loss is at most $L(\theta^\star)+O(\varepsilon)$, with probability at least $1-\delta$. The guarantee is additive, with no large multiplicative constant, unlike prior single-neuron sampling results.

What carries the argument

The central object is the nonlinear adjoint operator of a map, $f^\star(\theta)=\int_0^1 \frac{\partial}{\partial\theta}f(t\theta)\,dt$, which makes the map writable as an inner product $f(\theta)=\langle\hat\theta,\hat f^\star(\theta)\rangle$. Stacking these rows gives the nonlinear dual matrix $\widehat{F^\star}(\theta)$, so the nonlinear least-squares objective becomes $\|\widehat{F^\star}(\theta)\hat\theta\|^2$ and the standard linear tools—subspace embeddings, leverage scores, norm scores—apply pointwise in $\theta$. Proposition 3.1 computes the adjoint explicitly when the map is $g\circ h$ with $h$ positively homogeneous, which covers generalized linear predictors and ReLU networks. The bounded-ratio condition $\beta \tau_i(\theta)\le \tau_i$ is what upgrades these pointwise guarantees to a uniform, parameter-independent sampling probability; the $\varepsilon$-net and the Lipschitz continuity of the sampled loss are what convert the pointwise embedding into the final additive bound on $L(\theta^\star_S)$.

What would settle it

Take a small synthetic single-index model with a Swish-type activation where the constants $l,u$ (hence $\beta=l/u$) are known, sample by the linear leverage scores exactly at the sample size prescribed in Theorem 3.1, and estimate the probability that $L(\theta^\star_S)>L(\theta^\star)+O(\varepsilon)$; if that probability exceeds $\delta$, or if the excess loss does not decrease like $O(\varepsilon)$ while $L(f,X,R)$ is held fixed, the $\varepsilon$-net/Lipschitz step hides more than the stated guarantee.

Watch

Extended reading notes

Core claim

The paper claims that the familiar linear machinery of importance sampling extends to nonlinear maps $f_i:\mathbb{R}^p\to\mathbb{R}$ once each map is written through the adjoint representation $f_i(\theta)=\langle \hat\theta,\hat f_i^\star(\theta)\rangle$, with $\hat f_i^\star(\theta)=[f_i^\star(\theta); f_i(0)]$ and $\hat\theta=[\theta;1]$. The adjoint $f_i^\star(\theta)=\int_0^1 \partial_\theta f_i(t\theta)\,dt$ is the parameter-average of the gradient along the ray from $0$ to $\theta$. For positively homogeneous inner functions (single-index models, ReLU and multi-neuron networks), the adjoint has a closed form. Defining nonlinear leverage and norm scores as the row scores of the dual matrix $\widehat{F^\star}(\theta)$, and sampling rows with those probabilities, gives for every fixed $\theta$ the usual subspace-embedding guarantee $(1-\varepsilon)L(\theta)\le L_S(\theta)\le(1+\varepsilon)L(\theta)$. The paper then shows how to make the scores parameter-free: if the activation obeys a uniform bounded-ratio condition—$l\le\phi^2(t)/t^2\le u$ for single-index models, $c_1\le(\phi(t)-\phi(0))^2/t^2\le c_2$ plus bounds on the parameter set for networks—then linear scores dominate the nonlinear scores on a set $C$ containing the optimum, with $\beta=l/u$ or $\beta=\min\{c_1l,1\}/\max\{c_2u,1\}$. With an $\varepsilon$-net and a Lipschitz-continuity control on the sampled loss, the paper proves the main theorem: sampling $s$ points by the parameter-free scores yields $L(\theta^\star_S)\le L(\theta^\star)+O(\varepsilon)$ with high probability. The same scores are then demonstrated as a sampling rule that lowers training cost on regressions and as a diagnostic that surfaces mislabeled or hard images in classification tasks.

Load-bearing premise

The activation's ratio $\phi(t)^2/t^2$ must stay between two fixed positive constants over all inputs the model can produce on the relevant parameter set, so a parameter-independent score can bound the true nonlinear score on all of $C$.

Editorial extensions

If this is right

  • Training on $s=O((p\log(p/\delta)+p^2\log(p/\varepsilon))/(\beta\varepsilon^2))$ sampled points yields a model whose full-data squared loss is within $O(\varepsilon)$ of the optimum, with probability at least $1-\delta$.
  • The same nonlinear leverage and norm scores can cut training cost on large nonlinear datasets while preserving near-optimal loss, since sampling now comes with the same theoretical backing that linear subspace embeddings provide.
  • In classification experiments, the scores surface the most informative and hardest examples: mislabeled and noisy images receive the highest nonlinear leverage scores, offering a post-hoc diagnostic for outlier detection and model explainability.
  • The scoring step is parameter-free: under the $\beta$-ratio condition, the sampling distribution is fixed ahead of time, so the chicken-and-egg coupling between sampling and estimation is reduced to a constrained optimization over a set $C$ that contains the optimum.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The adjoint representation suggests a general recipe: any nonlinear map with a computable integral-of-gradient could inherit importance scores without going through the specific single-index or ReLU examples worked out here; a natural extension is to residual networks or kernel feature maps with homogeneous building blocks.
  • If the bounded-ratio condition can be relaxed to hold only on the data manifold rather than the full parameter ball, the same machinery might reach deep ReLU networks, where $\phi^2(t)/t^2=0$ on the negative half-line currently excludes them from the theorem.
  • The $\varepsilon$-net step introduces the $p^2\log(p/\varepsilon)$ term and an unquantified Lipschitz constant; replacing the net with chaining or metric-entropy arguments could plausibly recover the linear-in-$p$ sample complexity, bringing nonlinear sampling in line with the linear benchmark.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This paper proposes a framework for importance sampling in nonlinear least-squares problems. The central device is the adjoint operator f*(θ)=∫_0^1 ∂θ f(tθ)dt, which yields the exact identity f(θ)=⟨bθ,bf*(θ)⟩ and hence L(θ)=‖bF*(θ)bθ‖² for squared loss. The authors define nonlinear norm and leverage scores from the rows of bF*(θ), prove a fixed-θ subspace embedding, and then claim a parameter-independent guarantee: under a score-domination condition βτ_i(θ)≤τ_i on a set C containing θ*, sampling s=O((p log(p/δ)+p²log(p/ε))/(β ε²)) points gives L(θ*_S)≤L(θ*)+O(ε) with high probability. Applications are given to single-index models and to two-layer ReLU networks, with experiments on regression and classification tasks.

Significance. If the main theorem were fully correct, the adjoint representation would be an elegant unification of linear RandNLA embeddings with nonlinear importance sampling, and the guarantee (2) would improve on the multiplicative-constant bounds of Gajjar et al. (2024). The exactness of the representation f(θ)=⟨bθ,bf*(θ)⟩, the explicit adjoint computations for single-index and ReLU models, and the reproducible empirical illustrations are genuine strengths. However, the advertised neural-network guarantee rests on a score-domination argument that fails for inactive ReLU units, and the proof of Theorem 3.1 has a union-bound gap at θ*. For generalized linear predictors under the stated bounded-ratio assumptions, the framework is plausible, but the paper overclaims its scope.

major comments (3)
  1. [Section 3.3.1, Example 3.4 / Appendix A.2] The derivation of β=min{c1l,1}/max{c2u,1} for ReLU networks is invalid for data rows with no active hidden unit. In Appendix A.2 the sentence 'as otherwise f*_i(θ)=0' is used to justify the uniform lower bound c1l‖x_i‖²≤‖f*_i(θ)‖², but a row with no active unit contributes zero to the denominator Σ_i‖bf*_i(θ)‖², so the denominator lower bound used in the score bound fails. Concretely, take m=1, φ(t)=t, θ=(a,b)=(1,1), C defined by a²≥1 and a²+b²≤2, and data with 20% of the x_i satisfying ⟨b,x_i⟩>0 and 80% satisfying ⟨b,x_i⟩≤0. For each active row, τ_i(θ)/τ_i=5, while 1/β=2, so βτ_i(θ)≤τ_i fails on C. Theorem 3.1 therefore cannot be invoked for the stated ReLU-NN example unless an additional assumption guarantees that every data point has at least one active hidden unit for all θ∈C and the active fraction is accounted for in β.
  2. [Section 3.3.2 / proof of Theorem 3.1] The union-bound argument covers the ε-net N_ε, but the final step 'Combining this with (11)' requires the embedding inequality LS(θ*)≤(1+ε)L(θ*) at the true optimum θ*, which is not a net point. The proof as written does not establish (10) at θ*. This is repairable by adding θ* to N_ε or by deriving a Lipschitz-perturbed version of (11), but as written the proof of Theorem 3.1 is incomplete.
  3. [Theorem 3.1 / Section 3.3.2] The theorem statement omits the Lipschitz constant L(f,X,R) introduced in Section 3.3.2, although the proof's additive error is ε/(1−ε)(L(θ*)+(2−ε)R·L(f,X,R)). Since R is chosen 'large enough' and L depends on f, X, and R, the guarantee (2) is meaningful only after fixing these quantities. The authors should either state explicit hypotheses under which R·L(f,X,R) is bounded in the relevant asymptotic regime or define the O(ε) term with the dependence on these constants made explicit.
minor comments (5)
  1. [Section 3.3.1, Example 3.3] The displayed inequality uses a constant c1 that has not been defined; from the context the intended constant is l, i.e., the factor should be 1/l rather than 1/c1.
  2. [Example 3.4 / Appendix A.2] The definition of the admissible set C is inconsistent between the main text, which has min_j(a_j)²≥l, and Appendix A.2, which appears to have min_j(a*_j)²≥l; please make the intended condition clear.
  3. [Section 4 / Appendix A.3] The classification experiments use BCE loss and a sigmoid output, while Theorem 3.1 covers squared loss and Appendix A.3 requires positively homogeneous f. The paper should state explicitly that the classification results are empirical and are not covered by Theorem 3.1.
  4. [Appendix A.1, proof of Proposition 3.1] The change of variables t=(s/h(θ))^{1/α} is written assuming h(θ)>0; for h(θ)<0, the signed substitution and integral orientation need care. Because the single-index and ReLU examples allow negative values of the relevant homogeneous function, a sentence handling the sign of h(θ) would make the proof complete.
  5. [Definition 3.3] The nonlinear leverage score is undefined when bF*(θ) has rank zero or when the pseudoinverse projection vanishes; the paper should state the nondegeneracy assumptions under which these scores are well defined and sum to one.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the adjoint representation is an exact identity and Theorem 3.1 is a conditional sufficiency theorem verified by explicit domination examples.

full rationale

The paper's core representation (6) is an identity obtained from the integral mean value theorem, f(θ)=⟨bθ,bf*(θ)⟩, and is not fitted to data. The nonlinear scores in Definitions 3.3 and 3.4 are defined directly from this dual matrix, and the parameter-independent sampling guarantee in Theorem 3.1 is a conditional result: it assumes βτ_i(θ) ≤ τ_i on C and then proves, via standard approximate matrix multiplication, epsilon-net, and Lipschitz arguments, that sampling s = O(...) points yields L(θ*_S) ≤ L(θ*) + O(ε). No fitted constant is relabeled as a prediction, and no load-bearing premise is justified only by a self-citation; the prior work of Roosta cited, e.g., Xu et al. 2016 and Eshragh et al. 2022, appears only as background. Examples 3.3 and 3.4 attempt to verify the domination condition under explicit bounded-ratio assumptions rather than assuming the theorem's conclusion. If Example 3.4's treatment of inactive ReLU units is mathematically incomplete, including the statement in Appendix A.2 that 'as otherwise f*_i(θ)=0,' that is a correctness and validity concern about the example, not circularity of the derivation chain. The main theorem still has independent content: it reduces the nonlinear approximation problem to a verifiable score-domination condition, and the proof does not use the target result as an input.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new physical entities are introduced. The nonlinear adjoint operator and dual matrix are mathematical definitions built from the model itself. The free parameters are the bounded-ratio constants and the ball radius, which are not fitted to data but are assumed to exist. The axioms are mostly standard analysis plus the restrictive bounded-ratio condition.

free parameters (3)
  • l, u = not fitted; assumed to exist
    Activation ratio bounds l <= phi^2(t)/t^2 <= u in Example 3.3. They control the dominance factor beta = l/u and the sample complexity. They are introduced as assumptions, not fitted, but in practice they must be known or estimated.
  • c1, c2, l, u = not fitted; depend on unknown theta*
    Norm bounds in Example 3.4 for ReLU-style networks. The set C is constructed using l and u that are derived from the unknown optimal parameters, so the theorem's applicability requires a priori knowledge about the optimum.
  • R = not fitted; chosen to contain theta*
    Radius of the ball B*_R containing the optimum theta*. Appears in the error bound and in the epsilon-net construction. The guarantee depends on R, which is not specified.
assumptions (5)
  • standard math Integral form of the mean value theorem and Euler's homogeneous function theorem.
    Used in Definition 3.1 and Proposition 3.1 to derive the adjoint operator and the closed-form for homogeneous h.
  • domain assumption Each mapping f_i is continuously differentiable or absolutely continuous along rays, squared loss, and the underparameterized setting n >= p.
    Stated in Section 3.1 and the introduction. Needed for the identity (6) and for the rank and pseudoinverse operations in the score definitions.
  • domain assumption X and F*(theta) are full column rank for all theta in C.
    Required in Example 3.3 to compare (F*)^T F* with X^T X and to derive the leverage score bound.
  • ad hoc to paper There exist constants 0 < l <= u such that l <= phi^2(t)/t^2 <= u for all t in a set T, and analogous norm bounds for multi-layer models.
    This is the central assumption that makes the nonlinear scores comparable to linear scores uniformly on C, enabling parameter-independent sampling. It excludes ReLU and logistic activations over unbounded domains.
  • domain assumption The sampled loss L_S is Lipschitz continuous on B*_R and its Lipschitz constant is bounded uniformly over all samples S.
    Invoked in Section 3.3.2 to replace theta*_S by a nearby net point and to pass from L_S(theta*) to L(theta*). The constant L(f,X,R) is assumed finite but never bounded.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Importance Sampling for Nonlinear Models." pith.science (2026). https://pith.science/paper/XKUPJMTO

@misc{pith2026250512353,
  author       = {Pith},
  title        = {Pith review of: Importance Sampling for Nonlinear Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XKUPJMTO}},
  note         = {Machine review of arXiv:2505.12353}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2505.12353 by the authors.

Figure 1
Figure 1. Comparison of sampling strategies. The Y-axis shows log [(L(θ ⋆ S ) − L(θ ⋆ ))/L(θ ⋆ )] against sample size (as a percent￾age of total data), where θ ⋆ S 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-based nonlinear variants. Nonlinear importance scores consistently out… view at source ↗
Figure 2
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)-(j), the top row shows images selected using nonlinear leverage scores (Definition 3.3), while the bottom row uses linear leverage scores. Samples with higher nonlinear scores contain distinct patterns and are harder to classify, w… view at source ↗
Figure 3
Figure 3. Illustration of an ε-net covering B ⋆ R. The larger circle has radius (1 + ε/2)R, while B ⋆ R has radius R. Blue dots denote the ε-net, and dashed circles of radius εR/2 cover all points. A.5. Further Details for Section 4 Classification Experiments. To carry out the experiment in an under-parameterized setting, the dataset was balanced, and the images were resized to 10 × 10 dimensions with a grayscale background. … view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Illustration of quantitative results on datasets used in [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]
Figure 5
Figure 5. Figure 5: Top 50 images with the highest and lowest nonlinear leverage scores in each grouping for the SVHN dataset. (a) NOTMNIST High (A vs B) Nonlinear Leverage Scores (b) NOTMNIST Low (A vs B) Nonlinear Leverage Scores (c) NOTMNIST High (A vs B) Linear Leverage Scores (d) NOT…
Figure 6
Figure 6. Figure 6: Top 50 images with the highest and lowest nonlinear leverage scores in each grouping for the NOTMNIST dataset. (a) QD High Nonlinear Leverage Scores (b) QD Low Nonlinear Leverage Scores (c) QD High Linear Leverage Scores (d) QD Low Linear Leverage Scores [PITH_FULL_IM…
Figure 7
Figure 7. Figure 7: Top 50 images with the highest and lowest nonlinear leverage scores for the QD dataset. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]
Figure 8
Figure 8. 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 the FER dataset. In (e) only 16 images had non-zero scores at initialization. 21 [PITH_FULL_IMAGE:figures/full_fi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 60 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    On computing approximate lewis weights

    Apers, S., Gribling, S., and Sidford, A. On computing approximate lewis weights. arXiv preprint arXiv:2404.02881, 2024

    arXiv 2024

  3. [3]

    Blendenpik: Supercharging lapack's least-squares solver

    Avron, H., Maymounkov, P., and Toledo, S. Blendenpik: Supercharging lapack's least-squares solver. SIAM Journal on Scientific Computing, 32 0 (3): 0 1217--1236, 2010

    2010

  4. [4]

    Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees

    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 learning, pp.\ 253--262. PMLR, 2017

    work page 2017

  5. [5]

    A universal sampling method for reconstructing signals with simple fourier transforms

    Avron, H., Kapralov, M., Musco, C., Musco, C., Velingker, A., and Zandieh, A. A universal sampling method for reconstructing signals with simple fourier transforms. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 1051--1063, 2019

    work page 2019

  6. [6]

    Bietti, A., Bruna, J., Sanford, C., and Song, M. J. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35: 0 9768--9783, 2022

    work page 2022

  7. [7]

    Approximation of zonoids by zonotopes

    Bourgain, J., Lindenstrauss, J., and Milman, V. Approximation of zonoids by zonotopes. Acta Mathematica, 162: 0 73 – 141, 1989

    work page 1989

  8. [8]

    Notmnist dataset

    Bulatov, Y. Notmnist dataset. Google (Books/OCR), Tech. Rep.[Online]. Available: http://yaroslavvb. blogspot. it/2011/09/notmnist-dataset. html, 2: 0 4, 2011

    work page 2011

Show all 73 references
  1. [9]

    Some properties of nonlinear adjoint operators

    Bur \'y s kov \'a , V. Some properties of nonlinear adjoint operators. The Rocky Mountain journal of mathematics, 28 0 (1): 0 41--59, 1998

    1998

  2. [10]

    Importance sampling tree for large-scale empirical expectation

    Can \'e vet, O., Jose, C., and Fleuret, F. Importance sampling tree for large-scale empirical expectation. In International Conference on Machine Learning, pp.\ 1454--1462. PMLR, 2016

    2016

  3. [11]

    and Derezinski, M

    Chen, X. and Derezinski, M. Query complexity of least absolute deviation regression via robust uniform convergence. In Conference on Learning Theory, pp.\ 1144--1179. PMLR, 2021

    2021

  4. [12]

    and Price, E

    Chen, X. and Price, E. Active regression via linear-sample sparsification. In Conference on Learning Theory, pp.\ 663--695. PMLR, 2019

    2019

  5. [13]

    Clarkson, K. L. and Woodruff, D. P. Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63 0 (6): 0 1--45, 2017

    2017

  6. [14]

    and DeVore, R

    Cohen, A. and DeVore, R. Approximation of high-dimensional parametric pdes. Acta Numerica, 24: 0 1--159, 2015

    2015

  7. [15]

    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

    2015

  8. [16]

    B., Musco, C., and Musco, C

    Cohen, M. B., Musco, C., and Musco, C. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 1758--1777. SIAM, 2017

    2017

  9. [17]

    and Mahoney, M

    Derezi \'n 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

    2024

  10. [18]

    and Mahoney, M

    Drineas, P. and Mahoney, M. W. Lectures on randomized numerical linear algebra. The Mathematics of Data, 25 0 (1), 2018

    2018

  11. [19]

    Drineas, P., Kannan, R., and Mahoney, M. W. Fast monte carlo algorithms for matrices i: Approximating matrix multiplication. SIAM Journal on Computing, 36 0 (1): 0 132--157, 2006 a

    2006

  12. [20]

    W., and Muthukrishnan, S

    Drineas, P., Mahoney, M. W., and Muthukrishnan, S. Sampling algorithms for _ 2 regression and applications. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp.\ 1127--1136, 2006 b

    2006

  13. [21]

    Fourier sparse leverage scores and approximate kernel learning

    Erd \'e lyi, T., Musco, C., and Musco, C. Fourier sparse leverage scores and approximate kernel learning. Advances in Neural Information Processing Systems, 33: 0 109--122, 2020

    2020

  14. [22]

    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 0 (22): 0 1--36, 2022

    2022

  15. [23]

    High-dimensional covariance matrix estimation in approximate factor models1

    Fan, J., Liao, Y., and Mincheva, M. High-dimensional covariance matrix estimation in approximate factor models1. Annals of statistics, 2011

    2011

  16. [24]

    Core-sets: Updated survey

    Feldman, D. Core-sets: Updated survey. Sampling techniques for supervised or unsupervised tasks, pp.\ 23--44, 2020

    2020

  17. [25]

    and Musco, C

    Gajjar, A. and Musco, C. Subspace embeddings under nonlinear transformations. In Algorithmic Learning Theory, pp.\ 656--672. PMLR, 2021

    2021

  18. [26]

    Active learning for single neuron models with lipschitz non-linearities

    Gajjar, A., Musco, C., and Hegde, C. Active learning for single neuron models with lipschitz non-linearities. In International Conference on Artificial Intelligence and Statistics, pp.\ 4101--4113. PMLR, 2023

    2023

  19. [27]

    M., Xingyu, X., Hegde, C., Musco, C., and Li, Y

    Gajjar, A., Tai, W. M., Xingyu, X., Hegde, C., Musco, C., and Li, Y. 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

    2024

  20. [28]

    and Mahoney, M

    Gittens, A. and Mahoney, M. Revisiting the nystrom method for improved large-scale machine learning. In International Conference on Machine Learning, pp.\ 567--575. PMLR, 2013

    2013

  21. [29]

    Reliably learning the relu in polynomial time

    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 Theory, volume 65 of Proceedings of Machine Learning Research, pp.\ 1004--1042. PMLR, 07--10 Jul 2...

    2017

  22. [30]

    J., Erhan, D., Carrier, P

    Goodfellow, I. 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 learning: A report on three machine learning contests. In Neural information processing: 20th international ...

    2013

  23. [31]

    and Eck, D

    Ha, D. and Eck, D. A neural representation of sketch drawings. In International Conference on Learning Representations, 2018

    2018

  24. [32]

    and Mazumdar, S

    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

    2004

  25. [33]

    a rdle, W., M \

    H \"a rdle, W., M \"u ller, M., Sperlich, S., Werwatz, A., et al. Nonparametric and semiparametric models, volume 1. Springer, 2004

    2004

  26. [34]

    Direct estimation of the index coefficient in a single-index model

    Hristache, M., Juditsky, A., and Spokoiny, V. Direct estimation of the index coefficient in a single-index model. Annals of Statistics, pp.\ 595--623, 2001

    2001

  27. [35]

    Coresets for scalable bayesian logistic regression

    Huggins, J., Campbell, T., and Broderick, T. Coresets for scalable bayesian logistic regression. Advances in neural information processing systems, 29, 2016

    2016

  28. [36]

    A., Needell, D., Rebrova, E., and Zare, A

    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 0 (1): 0 376--416, 2021

    2021

  29. [37]

    Johnson, W. B. and Schechtman, G. Finite dimensional subspaces of lp. Handbook of the geometry of Banach spaces, 1: 0 837--870, 2001

    2001

  30. [38]

    M., Kanade, V., Shamir, O., and Kalai, A

    Kakade, S. M., Kanade, V., Shamir, O., and Kalai, A. Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011

    2011

  31. [39]

    and Fleuret, F

    Katharopoulos, A. and Fleuret, F. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp.\ 2525--2534. PMLR, 2018

    2018

  32. [40]

    and Schulman, L

    Langberg, M. and Schulman, L. J. Universal -approximators for integrals. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp.\ 598--607. SIAM, 2010

    2010

  33. [41]

    Crafting papers on machine learning

    Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp.\ 1207--1216, Stanford, CA, 2000. Morgan Kaufmann

    2000

  34. [42]

    Machine learning with R: expert techniques for predictive modeling

    Lantz, B. Machine learning with R: expert techniques for predictive modeling. Packt publishing ltd, 2019

    2019

  35. [43]

    and Lee, J

    Liu, Q. and Lee, J. Black-box importance sampling. In Artificial Intelligence and Statistics, pp.\ 952--961. PMLR, 2017

    2017

  36. [44]

    H., Xu, Z., Zha, D., Tang, R

    Liu, Z., Wang, G., Zhong, S. H., Xu, Z., Zha, D., Tang, R. R., Jiang, Z. S., Zhou, K., Chaudhary, V., Xu, S., et al. Winner-take-all column row sampling for memory efficient adaptation of language model. Advances in Neural Information Processing Systems, 36, 2024

    2024

  37. [45]

    Training gaussian mixture models at scale via coresets

    Lucic, M., Faulkner, M., Krause, A., and Feldman, D. Training gaussian mixture models at scale via coresets. Journal of Machine Learning Research, 18 0 (160): 0 1--25, 2018

    2018

  38. [46]

    Mahoney, M. W. and Drineas, P. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106 0 (3): 0 697--702, 2009

    2009

  39. [47]

    Mahoney, M. W. et al. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning , 3 0 (2): 0 123--224, 2011

    2011

  40. [48]

    Coresets for classification--simplified and strengthened

    Mai, T., Musco, C., and Rao, A. Coresets for classification--simplified and strengthened. Advances in Neural Information Processing Systems, 34: 0 11643--11654, 2021

    2021

  41. [49]

    and Tropp, J

    Martinsson, P.-G. and Tropp, J. A. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29: 0 403--572, 2020

    2020

  42. [50]

    Is-count: Large-scale object counting from satellite images with covariate-based importance sampling

    Meng, C., Liu, E., Neiswanger, W., Song, J., Burke, M., Lobell, D., and Ermon, S. Is-count: Large-scale object counting from satellite images with covariate-based importance sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp.\ 12034--12042, 2022

    2022

  43. [51]

    and Mahoney, M

    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-fifth annual ACM symposium on Theory of computing, pp.\ 91--100, 2013

    2013

  44. [52]

    Coresets for data-efficient training of machine learning models

    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

    2020

  45. [53]

    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 0 (1): 0 18--31, 2017

    2017

  46. [54]

    On coresets for logistic regression

    Munteanu, A., Schwiegelshohn, C., Sohler, C., and Woodruff, D. On coresets for logistic regression. Advances in Neural Information Processing Systems, 31, 2018

    2018

  47. [55]

    W., Erichson, N

    Murray, R., Demmel, J., Mahoney, M. W., Erichson, N. B., Melnichenko, M., Malik, O. A., Grigori, L., Luszczek, P., Derezi \'n 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.11474, 2023

    2023 arXiv

  48. [56]

    P., and Yasuda, T

    Musco, C., Musco, C., Woodruff, D. P., and Yasuda, T. Active linear regression for _p norms and beyond. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 744--753. IEEE, 2022

    2022

  49. [57]

    A., Gladstone, R

    Nabian, M. A., Gladstone, R. J., and Meidani, H. Efficient training of physics-informed neural networks via importance sampling. Computer-Aided Civil and Infrastructure Engineering, 36 0 (8): 0 962--977, 2021

    2021

  50. [58]

    and Nguy \^e n, H

    Nelson, J. and Nguy \^e n, H. L. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pp.\ 117--126. IEEE, 2013

    2013

  51. [59]

    Y., et al

    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://ufldl.stanford.edu...

    2011

  52. [60]

    Derivative-informed projected neural networks for high-dimensional parametric maps governed by pdes

    O’Leary-Roseberry, T., Villa, U., Chen, P., and Ghattas, O. Derivative-informed projected neural networks for high-dimensional parametric maps governed by pdes. Computer Methods in Applied Mechanics and Engineering, 388: 0 114199, 2022

    2022

  53. [61]

    Pace, R. K. and Barry, R. Sparse spatial autoregressions. Statistics & Probability Letters, 33 0 (3): 0 291--297, 1997

    1997

  54. [62]

    G., Choudhry, S., Rodriguez-Cintron, W., Mahoney, M

    Paschou, P., Ziv, E., Burchard, E. G., Choudhry, S., Rodriguez-Cintron, W., Mahoney, M. W., and Drineas, P. Pca-correlated snps for structure identification in worldwide human populations. PLoS genetics, 3 0 (9): 0 e160, 2007

    2007

  55. [63]

    Unconditional coresets for regularized loss minimization

    Samadian, A., Pruhs, K., Moseley, B., Im, S., and Curtin, R. Unconditional coresets for regularized loss minimization. In International Conference on Artificial Intelligence and Statistics, pp.\ 482--492. PMLR, 2020

    2020

  56. [64]

    Improved approximation algorithms for large matrices via random projections

    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

    2006

  57. [65]

    Handbook of Analysis and its Foundations

    Schechter, E. Handbook of Analysis and its Foundations. Academic Press, 1996

    1996

  58. [66]

    Scherpen, J. M. and Gray, W. S. Nonlinear hilbert adjoints: Properties and applications to hankel singular value analysis. Nonlinear Analysis: Theory, Methods & Applications, 51 0 (5): 0 883--901, 2002

    2002

  59. [67]

    U., Raj, A., and Jaggi, M

    Stich, S. U., Raj, A., and Jaggi, M. Safe adaptive importance sampling. Advances in Neural Information Processing Systems, 30, 2017

    2017

  60. [68]

    Generic coreset for scalable learning of monotonic kernels: Logistic regression, sigmoid and more

    Tolochinksy, E., Jubran, I., and Feldman, D. Generic coreset for scalable learning of monotonic kernels: Logistic regression, sigmoid and more. In International Conference on Machine Learning, pp.\ 21520--21547. PMLR, 2022

    2022

  61. [69]

    Determinantal point processes for coresets

    Tremblay, N., Barthelm \'e , S., and Amblard, P.-O. Determinantal point processes for coresets. Journal of Machine Learning Research, 20 0 (168): 0 1--70, 2019

    2019

  62. [70]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Vershynin, R. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  63. [71]

    and Sievert, C

    Wickham, H. and Sievert, C. ggplot2: elegant graphics for data analysis, volume 10. springer New York, 2009

    2009

  64. [72]

    Woodruff, D. P. et al. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science , 10 0 (1--2): 0 1--157, 2014

    2014

  65. [73]

    Xu, P., Yang, J., Roosta, F., R \'e , C., and Mahoney, M. W. Sub-sampled newton methods with non-uniform sampling. Advances in Neural Information Processing Systems, 29, 2016

    2016

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.