Pith. sign in

REVIEW 2 major objections 5 minor 47 references

Random feature approximation for general spectral methods

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Random feature approximation does not degrade the minimax learning rate of any spectral regularization method.

desk verdict Sound generalization of random-feature rates to spectral methods, with an overbroad 'arbitrary r>0' claim and minor boundary omissions. read the letter →

arxiv 2506.16283 v1 pith:RW66CRJY submitted 2025-06-19 stat.ML cs.LG

Mike Nguyen , Nicole Mücke This is my paper · ORCID
classification stat.MLcs.LG MSC 68T0562G0868Q32
keywords randomfeatureapproximationspectralregularizationmethodskernelridgeregressionlearningrateseffectivedimensionneuraltangentoperatorsgradientdescent
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

Random feature approximations replace an expensive kernel by a finite random sum, and this paper asks whether that substitution costs anything in statistical accuracy. The answer, under a smoothness condition and a kernel-capacity bound, is no: for any spectral regularization method, the random-feature estimator reaches the same minimax-optimal rate $n^{-r/(2r+b)}$ as the exact kernel method, with high probability. The price is only the number of random features, which in the well-specified case scales as $O(\sqrt{n}\log n)$. This matters because it certifies that cheap large-scale kernel algorithms, including neural tangent kernel models and neural operators, can retain optimal accuracy while using random features.

What carries the argument

The load-bearing object is the spectral-filter estimator $$f^M_\$\lambda$=\phi_\$\lambda$(\hat\Sigma_M)\hat S^*_M y,$$ where $\phi_\lambda$ is a regularization function acting on the empirical covariance operator $\hat\Sigma_M$ of the random-feature kernel $K_M$, and $\hat S^*_M$ is the empirical sampling operator. The proof splits the excess risk into a bias term, controlled by the qualification $\nu$ of $\phi_\lambda$ together with the source condition $g_\rho=L_\infty^r h$, and a variance term, controlled by operator concentration: $\hat\Sigma_M$ concentrates around $\Sigma_M$ in the random-feature Hilbert space, and the random-feature kernel operator $L_M$ concentrates around $L_\infty$ in the ambient space. The effective dimension $N_{L_\infty}(\lambda)=\operatorname{tr}(L_\infty(L_\infty+\lambda I)^{-1})\le c_b\lambda^{-b}$ is what converts these concentration bounds into the stated feature-count thresholds $M$.

What would settle it

Take a kernel whose eigenvalues decay like $\mu_i\sim i^{-1/b}$ with $b=1/2$ (so $N_{L_\infty}(\lambda)\sim \lambda^{-1/2}$) and a target $g_\rho=L_\infty^r h$ with $r=0.3$, giving $2r+b=1.1$. Choose $\lambda\sim n^{-1/1.1}$ and $M=\sqrt{n}\log n$ as in Theorem 3.5; if, for large $n$, the excess risk $\|g_\rho-S_M f^M_\lambda\|_{L^2(\rho_x)}$ fails to decay like $n^{-0.3/1.1}$ with high probability, the theorem's bound is violated.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.5. Suppose the kernel admits an integral representation $$K_\infty(x,\tilde x)=\sum_{i=1}^p\int_\$\Omega$ \$varphi^{{(i)}}$(x,\omega)\otimes \$varphi^{{(i)}}$(\tilde x,\omega)\,d\pi(\omega),$$ the regression function satisfies the source condition $g_\rho=L_\infty^r h$ with $\|h\|_{L^2(\rho_x)}\le R$, and the kernel integral operator satisfies the effective-dimension bound $N_{L_\infty}(\lambda)\le c_b\lambda^{-b}$ with $2r+b>1$. Then, for any spectral regularization method with qualification $\nu\ge r\vee 1$, choosing $$\$\lambda$=C $n^{{-1/(2r+b)}}$\$log^{3}$(2/\delta)$$ and $M\ge \tilde C\log(n)$ times $n^{1/(2r+b)}$ for $r<1/2$, $n^{[1+b(2r-1)]/(2r+b)}$ for $1/2<r<1$, and $n^{2r/(2r+b)}$ for $r>1$, yields $$\|g_\rho-S_M f^M_\$\lambda$\|_{$L^{2}$(\rho_x)}\le \bar C\, $n^{{-r/(2r+b)}}$\$log^{{3r+1}}$(1/\delta)$$ with probability at least $1-\delta$. In words, random features do not degrade the minimax-optimal rate of the underlying spectral algorithm; they only set a feature-count threshold that must be crossed.

Load-bearing premise

Everything rests on the 'easy learning' assumption that the smoothness parameter $r$ and the kernel-capacity parameter $b$ satisfy $2r+b>1$; when $2r+b\le 1$, the bias-variance balance that produces the rate $n^{-r/(2r+b)}$ is not proved, so the theorem's feature count and rate are unsupported.

Editorial extensions

If this is right

  • Kernel ridge regression, gradient descent, Heavy-Ball, and Nesterov all attain the minimax rate with only $M=O(\sqrt{n}\log n)$ random features in the well-specified case, so no method in this class loses statistical efficiency to random features.
  • Smoothness classes with $r<1/2$ that lie outside the reproducing kernel Hilbert space are covered whenever $2r+b>1$, removing the saturation limitation that blocked earlier random-feature analyses of kernel ridge regression.
  • For smoother targets, the optimal rate needs fewer iterations but more random features: $T=O(n^{1/(2r+b)})$ and $M=O(n^{2r/(2r+b)}\log n)$ for $r\ge 1$.
  • Because the framework accepts finite sums of integral kernels, it covers neural tangent kernels and yields optimal $n_U^{-r/(2r+b)}$ rates for two-layer neural operators trained by gradient descent, provided the network width and the second-stage sample count are large enough.
  • The result unifies and extends the previously KRR-only random-feature guarantees to the whole class of spectral methods, closing the algorithmic gap between theory and practice for random-feature kernel models.

Reading between the lines

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

  • Beyond the paper, a plausible next step is that the logarithmic factor in the feature count is removable, as it was for kernel ridge regression, so $M=O(\sqrt{n})$ would suffice for all spectral methods; the paper does not prove this.
  • Since Assumptions 3.3 and 3.4 exclude the hard-problem regime $2r+b\le 1$, a concrete test is whether lowering $r$ or $b$ forces a larger feature count, for instance $M\asymp n^{1/(2r+b)}$, to keep any optimal rate; the paper only establishes the easy-regime balance.
  • The same operator-concentration argument could be re-run for data-dependent sketches or Nyström approximations, suggesting that the $O(\sqrt{n}\log n)$ threshold may be a general property of kernel approximations rather than a special fact about random features.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies random feature (RF) approximation for a broad class of spectral regularization methods in vector-valued kernel regression. Under a source condition gρ = L∞^r h, an effective-dimension bound N(λ) ≤ cb λ^{-b}, and the easy-learning restriction 2r+b>1, the main theorem (Theorem 3.5) shows that with λ = C n^{-1/(2r+b)} log^3(2/δ) and M of order log(n) times a piecewise power of n, the excess risk satisfies O(n^{-r/(2r+b)} polylog(1/δ)) for any spectral method with qualification ν ≥ r∨1. The framework covers Tikhonov regularization, gradient descent, Heavy-Ball, and Nesterov acceleration, and the authors apply it to neural networks and neural operators via the neural tangent kernel. The appendix supplies a detailed bias-variance proof with operator concentration inequalities, and numerical experiments on NTK random features illustrate the predicted M = O(√n) regime.

Significance. If the main result is correct, it is a useful extension of random-feature theory: previous sharp guarantees were largely limited to kernel ridge regression, whereas this paper covers general spectral filtering methods and vector-valued kernels, including NTK-type kernels. The proof strategy is standard but self-contained, with explicit constants and a clean bias-variance decomposition; the statement that M = O(√n log n) suffices to preserve the underlying spectral method's optimal rate is concrete and testable. The main caveat is that the result is restricted to the easy-learning regime 2r+b>1, which is explicit in Assumption 3.4 but is not always reflected in the paper's broader claims. The boundary values r=1/2 and r=1 are omitted from the theorem statement despite being covered by the proof.

major comments (2)
  1. [Theorem 3.5 (Section 3.1)] The piecewise condition on M uses the open intervals r ∈ (0,1/2), r ∈ (1/2,1), and r ∈ (1,∞), thereby omitting r=1/2 and r=1. This is not purely cosmetic: Proposition A.16 proves closed-interval cases ("CASE (r ≤ 1/2)", "CASE (r ∈ [1/2,1])", "CASE (r ≥ 1)"), and at r=1 the second branch gives M of order n^{(1+b)/(2+b)} while the third branch gives n^{2/(2+b)}, which are different unless b=1. The theorem statement should therefore use closed or half-open intervals, e.g., r ∈ (0,1/2], r ∈ (1/2,1], and r ∈ (1,∞), or explicitly defer the boundary cases to a corollary. Since the appendix proof already covers these values, this is a statement-completeness issue rather than a flaw in the derivation.
  2. [Assumption 3.4 and Conclusion (Section 3.1, Section 6)] The conclusion states that the framework "yields minimax-optimal rates for arbitrary smoothness r > 0", but Assumption 3.4 requires 2r+b>1. For any b<1 there are values r ≤ (1-b)/2 that are excluded, so the qualifier "with 2r+b>1" must appear in every summary claim, including the abstract's statement about "optimal learning rates over regularity classes". The proof explicitly relies on this condition to make the lower bound n ≥ n0 = exp((2r+b)/(2r+b-1)) consistent with λ = C n^{-1/(2r+b)} log^3(2/δ); the condition is not an artifact. I recommend replacing "arbitrary smoothness r > 0" with "arbitrary r > 0 satisfying 2r+b>1".
minor comments (5)
  1. [Section 3.1] The sentence "The case b = 1 is refereed as the capacity independent case" contains a typo: "refereed" should be "referred".
  2. [Appendix A.2, Propositions A.2 and A.3] "Mercers theorem" should be "Mercer's theorem".
  3. [Theorem 4.2 (Section 4.3)] The theorem heading "Theorem 4.2 (Nguyen and Mücke (2024) (Theorem 3.5.))" has mismatched parentheses and a stray period; please clean up the citation formatting.
  4. [Section 4.3] The norms such as ∥GθT − gρ∥L2ρu are written without parentheses around the measure; writing L2(ρu) and L2(µx) consistently would improve readability.
  5. [Section 2.1, Eq. (2.6)] The notation φ(i)(x, ωm) is used in the display but the random variables ωm are defined only in surrounding text; consider explicitly writing φ(i)_m(x) = φ(i)(x, ω_m) before Eq. (2.6) to avoid ambiguity with the sum index i.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: Theorem 3.5 is derived from its assumptions via explicit bias-variance and concentration bounds; the self-citations in the neural-operator application are auxiliary and not inputs to the main theorem.

full rationale

The core derivation (Theorem 3.5) is self-contained: the excess risk is decomposed in Eq. (3.3) into BIAS and VARIANCE, bounded in Propositions A.1 and A.3, which in turn rest on operator norm estimates (Propositions A.14-A.17) and concentration inequalities for Hilbert-Schmidt operators (Propositions A.19-A.22). The rate n^{-r/(2r+b)} is obtained by substituting lambda = C n^{-1/(2r+b)} log^3(2/delta) into the bound of Theorem A.4 and checking the n and M conditions; no parameter is fitted to data and no predicted quantity is defined in terms of an estimator's own output. The claim that the rate is minimax optimal cites Caponnetto and De Vito (2007) and Blanchard and Muecke (2017), which are external standard references; although Blanchard-Muecke shares an author, it is an independent published theorem and is not written to be equivalent to this result. Section 4's neural-operator theorem imports several bounds from the authors' own Nguyen-Muecke (2024) - NTK convergence (Prop. 2.3), Taylor remainder (Prop. D.2), and finite-width error (Thm. B.4) - but these are auxiliary estimates for the operator-application section, not inputs to Theorem 3.5, and the new term III is bounded by the new Theorem 3.5. The omission of hard problems (2r+b <= 1) and boundary values is an explicit scope limitation stated in Assumption 3.4 and Section 6, not a circular reduction. I therefore find no circular step; the minor self-citations are not load-bearing for the central claim.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The proof rests on standard spectral calculus and operator concentration, plus four substantive statistical assumptions (moment condition, kernel representation, source condition, effective dimension). The only user-chosen number is λ, specified by the theorem; no new entities are introduced.

free parameters (1)
  • regularization parameter λ = C n^{-1/(2r+b)} log^3(2/δ)
    Tuning parameter set by the theorem to balance bias and variance; it depends on the unknown smoothness r and capacity b, so in practice it would be chosen by model selection, not fitted to data.
assumptions (6)
  • domain assumption Data distribution satisfies moment condition (Assumption 3.1)
    Bounded moments of the output, standard in learning theory; used in Proposition A.22 and A.23.
  • domain assumption Kernel has integral representation (2.7) with bounded features (Assumption 3.2)
    Required for random feature approximation; includes NTK; the uniform bound κ^2 is needed in all concentration events.
  • domain assumption Source condition gρ = L∞^r h with r>0 (Assumption 3.3)
    Defines the smoothness of the regression function; the rate depends on r.
  • domain assumption Effective dimension N(λ) ≤ cb λ^{-b} with 2r+b>1 (Assumption 3.4)
    Capacity condition; the easy-learning restriction 2r+b>1 is load-bearing, hard problems are excluded.
  • domain assumption Spectral filter has qualification ν ≥ r∨1 (Definition 2.2)
    Needed for the residual bound (2.13); excludes e.g., Tikhonov for r>1.
  • standard math Operator concentration inequalities (Tropp 2011; Caponnetto-De Vito 2007)
    Used in Proposition A.19-A.23 to control random feature and sample fluctuations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Random feature approximation for general spectral methods." pith.science (2026). https://pith.science/paper/RW66CRJY

@misc{pith2026250616283,
  author       = {Pith},
  title        = {Pith review of: Random feature approximation for general spectral methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RW66CRJY}},
  note         = {Machine review of arXiv:2506.16283}
}
read the original abstract

Random feature approximation is arguably one of the most widely used techniques for kernel methods in large-scale learning algorithms. In this work, we analyze the generalization properties of random feature methods, extending previous results for Tikhonov regularization to a broad class of spectral regularization techniques. This includes not only explicit methods but also implicit schemes such as gradient descent and accelerated algorithms like the Heavy-Ball and Nesterov method. Through this framework, we enable a theoretical analysis of neural networks and neural operators through the lens of the Neural Tangent Kernel (NTK) approach trained via gradient descent. For our estimators we obtain optimal learning rates over regularity classes (even for classes that are not included in the reproducing kernel Hilbert space), which are defined through appropriate source conditions. This improves or completes previous results obtained in related settings for specific kernel algorithms.

Figures

Figures reproduced from arXiv: 2506.16283 by the authors.

Figure 1
Figure 1. Depiction of the architecture of our operator class. [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Heat plot of the test-error for different numbers of RF [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 41 canonical work pages

  1. [1]

    A. B. Aleksandrov and V. V. Peller. Operator h\"older--zygmund functions, 2009. URL https://arxiv.org/abs/0907.3049

    work page Pith review arXiv 2009

  2. [2]

    Katyusha: The first direct acceleration of stochastic gradient methods

    Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18 0 (221): 0 1--51, 2018. URL http://jmlr.org/papers/v18/16-410.html

    work page 2018

  3. [3]

    Optimal rates for regularization of statistical inverse learning problems

    Gilles Blanchard and Nicole M \"u cke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18: 0 971--1013, 2017

    work page 2017

  4. [4]

    Caponnetto and Ernesto De Vito

    A. Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7: 0 331--368, 2007

    work page 2007

  5. [5]

    Carmeli, E

    C. Carmeli, E. De Vito, and V. Umanità A. Toigo. Vector valued reproducing kernel hilbert spaces and universality, 2008

    work page 2008

  6. [6]

    Reproducing kernel hilbert spaces and mercer theorem, 2005

    Claudio Carmeli, Ernesto De Vito, and Alessandro Toigo. Reproducing kernel hilbert spaces and mercer theorem, 2005

    work page 2005

  7. [7]

    Learning with sgd and random features, 2019

    Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with sgd and random features, 2019

    work page 2019

  8. [8]

    On the impact of kernel approximation on learning accuracy

    Corinna Cortes, Mehryar Mohri, and Ameet Talwalkar. On the impact of kernel approximation on learning accuracy. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 113--120, Chia Laguna Resort, Sardinia,...

    work page 2010

Show all 47 references
  1. [9]

    Every model learned by gradient descent is approximately a kernel machine, 2020

    Pedro Domingos. Every model learned by gradient descent is approximately a kernel machine, 2020

    2020

  2. [10]

    On the nystr \"o m method for approximating a gram matrix for improved kernel-based learning

    Petros Drineas, Michael W Mahoney, and Nello Cristianini. On the nystr \"o m method for approximating a gram matrix for improved kernel-based learning. journal of machine learning research, 6 0 (12), 2005

    2005

  3. [11]

    Regularization of inverse problems, volume 375

    Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996

    1996

  4. [12]

    Stochastic heavy ball

    S \'e bastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball . Electronic Journal of Statistics, 12 0 (1): 0 461 -- 529, 2018. doi:10.1214/18-EJS1395. URL https://doi.org/10.1214/18-EJS1395

    2018 doi

  5. [13]

    Lo Gerfo, L

    L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito, and A. Verri. Spectral algorithms for supervised learning. Neural Computation, 20 0 (7): 0 1873--1897, 2008. ISSN 0899-7667. doi:10.1162/neco.2008.05-07-517. URL https://doi.org/10.1162/neco.2008.05-07-517

    2008 doi

  6. [14]

    Global convergence of the heavy-ball method for convex optimization

    Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European Control Conference (ECC), pages 310--315, 2015. doi:10.1109/ECC.2015.7330562

    2015

  7. [15]

    Nelsen, and Margaret Trautner

    Daniel Zhengyu Huang, Nicholas H. Nelsen, and Margaret Trautner. An operator learning perspective on parameter-to-observable maps, 2024

    2024

  8. [16]

    Neural tangent kernel: Convergence and generalization in neural networks

    Arthur Jacot, Cl \'e ment Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In NeurIPS, 2018

    2018

  9. [17]

    Kovachki, Zong-Yi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Andrew M

    Nikola B. Kovachki, Zong-Yi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Andrew M. Stuart, and Anima Anandkumar. Neural operator: Learning maps between function spaces with applications to pdes. J. Mach. Learn. Res., 24: 0 89:1--89:97, 2023. URL https://api....

    2023

  10. [18]

    Kovachki, Samuel Lanthaler, and Andrew M

    Nikola B. Kovachki, Samuel Lanthaler, and Andrew M. Stuart. Operator learning: Algorithms and analysis, 2024

    2024

  11. [19]

    Samuel Lanthaler and Nicholas H. Nelsen. Error bounds for learning with vector-valued random features, 2023

    2023

  12. [20]

    Kwok, and Bao-Liang Lu

    Mu Li, Wei Bi, James T. Kwok, and Bao-Liang Lu. Large-scale nyström kernel matrix approximation using randomized svd. IEEE Transactions on Neural Networks and Learning Systems, 26 0 (1): 0 152--164, 2015

    2015

  13. [21]

    Mufan Bill Li, Mihai Nica, and Daniel M. Roy. The future is log-gaussian: Resnets and their infinite-depth-and-width limit at initialization, 2021 a

    2021

  14. [22]

    Towards a unified analysis of random fourier features, 2021 b

    Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards a unified analysis of random fourier features, 2021 b

    2021

  15. [23]

    Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms, 2018

    Junhong Lin and Volkan Cevher. Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms, 2018. URL https://arxiv.org/abs/1801.07226

    2018 arXiv

  16. [24]

    Optimal rates for spectral algorithms with least-squares regression over hilbert spaces

    Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48 0 (3): 0 868--890, 2020

    2020

  17. [25]

    Woodruff

    Alexander Munteanu, Simon Omlor, Zhao Song, and David P. Woodruff. Bounding the width of neural networks via coupled initialization -- a worst case analysis, 2022

    2022

  18. [26]

    How many neurons do we need? a refined analysis for shallow networks trained with gradient descent, 2023

    Mike Nguyen and Nicole Mücke. How many neurons do we need? a refined analysis for shallow networks trained with gradient descent, 2023

    2023

  19. [27]

    Optimal convergence rates for neural operators, 2024

    Mike Nguyen and Nicole Mücke. Optimal convergence rates for neural operators, 2024. URL https://arxiv.org/abs/2412.17518

    2024 arXiv

  20. [28]

    Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime

    Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. In International Conference on Learning Representations. arXiv, 2020

    2020

  21. [29]

    Towards moderate overparameterization: global convergence guarantees for training shallow neural networks, 2019

    Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks, 2019

    2019

  22. [30]

    Implicit regularization of accelerated methods in hilbert spaces

    Nicol \`o Pagliana and Lorenzo Rosasco. Implicit regularization of accelerated methods in hilbert spaces. Advances in Neural Information Processing Systems, 32: 0 14481--14491, 2019

    2019

  23. [31]

    Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes, 2018

    Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes, 2018

    2018

  24. [32]

    Random features for large-scale kernel machines

    Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2007

    2007

  25. [33]

    Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning

    Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2...

    2008

  26. [34]

    A stochastic gradient method with an exponential convergence \_rate for finite training sets

    Nicolas Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence \_rate for finite training sets. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran...

    2012

  27. [35]

    Generalization properties of learning with random features, 2016

    Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features, 2016

    2016

  28. [36]

    Less is more: Nystroem computational regularization, 2016

    Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco. Less is more: Nystroem computational regularization, 2016

    2016

  29. [37]

    Schoelkopf and A

    B. Schoelkopf and A. J. Smola. Learning with Kernels, Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning). MIT Press, 2002

    2002

  30. [38]

    Mathematical Statistics

    Jun Shao. Mathematical Statistics. Springer-Verlag New York Inc, 2nd edition, 2003

    2003

  31. [39]

    Support vector machines

    Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008 a

    2008

  32. [40]

    Support vector machines

    Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008 b

    2008

  33. [41]

    Sriperumbudur

    Nicholas Sterge and Bharath K. Sriperumbudur. Statistical optimality and computational efficiency of nystrom kernel pca. Journal of Machine Learning Research, 23 0 (337): 0 1--32, 2022. URL http://jmlr.org/papers/v23/21-0766.html

    2022

  34. [42]

    Gain with no pain: Efficiency of kernel-pca by nyström sampling

    Nicholas Sterge, Bharath Sriperumbudur, Lorenzo Rosasco, and Alessandro Rudi. Gain with no pain: Efficiency of kernel-pca by nyström sampling. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence a...

    2020

  35. [43]

    Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12 0 (4): 0 389--434, 2011

    2011

  36. [44]

    Using the nystr\" o m method to speed up kernel machines

    Christopher Williams and Matthias Seeger. Using the nystr\" o m method to speed up kernel machines. In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000. URL https://proceedings.neurips.cc/paper_files/p...

    2000

  37. [45]

    A proximal stochastic gradient method with progressive variance reduction

    Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24 0 (4): 0 2057--2075, 2014. doi:10.1137/140961791

    2014 doi

  38. [46]

    On the optimality of misspecified spectral algorithms, 2024

    Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms, 2024. URL https://arxiv.org/abs/2303.14942

    2024 arXiv

  39. [47]

    Learning to learn kernels with variational random features, 2020

    Xiantong Zhen, Haoliang Sun, Yingjun Du, Jun Xu, Yilong Yin, Ling Shao, and Cees Snoek. Learning to learn kernels with variational random features, 2020

    2020

Pith tools

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