Pith. sign in

REVIEW 2 major objections 6 minor 44 references

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr\"om Method

T0 review · 2 major / 6 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 This paper claims that a $\lambda$-regularized $O(\alpha)$-approximation of any positive semidefinite matrix can be built and inverted faster than classical Nyström when the spectrum is heavy-tailed, by averaging $q = \tilde{O}(\alpha)$…

desk verdict Smart averaging idea with real potential, but the central spectral bound currently rests on an unproved self-cited lemma and the recursion theorem is not in checkable form. read the letter →

arxiv 2506.17556 v2 pith:JZVHUX35 submitted 2025-06-21 cs.DS cs.LG

Sachin Garg , Micha{l} Dereziński This is my paper · ORCID
classification cs.DScs.LG MSC 68W20
keywords Block-Nyströmmethodlow-rankmatrixapproximationridgeleveragescoreseffectivedimensionkernelregressionrecursivepreconditioningheavy-tailedspectrarandomizednumericallinearalgebra
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

The paper proposes Block-Nyström, a randomized low-rank approximation for positive semidefinite matrices aimed at the regime where classical Nyström becomes too expensive: heavy-tailed spectra with large effective dimension. Its central claim is that averaging $q = \tilde{O}(\alpha)$ independent small Nyström approximations, each built from $\tilde{O}(d_{\alpha^2 \lambda}(A))$ landmarks, produces a $\lambda$-regularized $O(\alpha)$-approximation of $A$ in Loewner order, while reducing the construction cost to $\tilde{O}((n m^2 + m^3)/\alpha^2 + n m)$ and allowing $(\hat A + \lambda I)^{-1}$ to be applied in $\tilde{O}(n m \alpha^{o(1)})$ time. The key insight is a bias-variance trade-off: one large Nyström approximation has a poor spectral tail, whereas several smaller ones average out tail variance while retaining top-spectrum bias. The paper applies this construction to preconditioned convex optimization and to kernel ridge regression in the unattainable regime, proving new risk bounds for approximate solvers that are no longer exact projections.

What carries the argument

The load-bearing object is the Block-Nyström matrix, defined as an average of $q$ i.i.d. Nyström projections $\hat A_i = C_i W_i^{-1} C_i^\top$ on disjoint landmark blocks $S_i$; the block-diagonal $W$ encodes that averaging. The argument runs on two small parts. First, the expected projection bound $\mathbb{E}[P] \succeq \tfrac12 A(A+\lambda' I)^{-1}$ for $\lambda'$-ridge leverage score sampling (Lemma 6) shows that the expectation of a single Nyström matrix estimates the spectral tail, even though any single low-rank realization does not; a matrix Chernoff bound then converts this expectation into a bias-variance error of order $\sqrt{\lambda'/\lambda} + \lambda'/(q\lambda)$, whose optimum forces $\lambda' = \alpha^2 \lambda$ and $q=\tilde{O}(\alpha)$. Second, the inverse is computed by recursive preconditioning: at level $k$ the system $M_k = \hat A[q_k] + c^{2k}\lambda I$ is preconditioned by the smaller $M_{k+1}$, until the recursion reaches a single Nyström block inverted via Woodbury; a solver composition lemma keeps the total per-vector cost nearly linear. A novel risk analysis for kernel ridge regression replaces the projection assumption of prior work with the regularized-approximation condition (1), which is what lets the non-projection Block-Nyström solver inherit near-optimal learning rates.

What would settle it

Run the construction on a diagonal matrix $A$ with eigenvalues $i^{-1/\gamma}$ (for instance $n=10^4$, $\gamma=0.8$), choose $\lambda$ so that $d_{\alpha^2\lambda}(A)\approx 200$, draw $q=64\alpha\log(n/\delta)$ blocks, and compute $\rho_{\min} = \lambda_{\min}\big((A+\lambda I)^{-1/2}(\hat A[q]+\lambda I)(A+\lambda I)^{-1/2}\big)$. If $\rho_{\min} < 1/(64\alpha)$ with non-negligible probability, the main spectral guarantee fails; alternatively, Monte Carlo estimate the Loewner gap $\mathbb{E}[P] - \tfrac12 A(A+\lambda'I)^{-1}$ on one block to test Lemma 6 directly.

Watch

Extended reading notes

Core claim

For any positive semidefinite $A$, regularizer $\lambda>0$, and approximation factor $\alpha\ge 1$, the paper claims a data structure $\hat A$ of rank $m=\tilde{O}(\alpha d_{\alpha^2\lambda}(A))$ such that $(64\alpha)^{-1}(A+\lambda I) \preceq \hat A+\lambda I \preceq A+\lambda I$ with high probability. Here $d_{\lambda}(A)=\operatorname{tr}(A(A+\lambda I)^{-1})$ is the $\lambda$-effective dimension. The structure is the Block-Nyström matrix $\hat A = C W^{-1} C^\top$ with $C=A_{:,S}$ and $W = q\operatorname{diag}(A_{S_1,S_1},\ldots,A_{S_q,S_q})$, equivalently the average of $q$ independent Nyström approximations sampled from $O(1)$-approximate $\alpha^2\lambda$-ridge leverage scores. Setting $\alpha=1$ recovers the classical Nyström guarantee, while increasing $\alpha$ replaces the costly dimension $d_\lambda(A)$ by the smaller $d_{\alpha^2\lambda}(A)$. The paper also claims that $(\hat A+\lambda I)^{-1}$ can be applied to a vector in $\tilde{O}(n m \alpha^{o(1)})$ time using a recursive preconditioning scheme, and that these guarantees translate into faster preconditioning and near-optimal kernel ridge regression in heavy-tailed settings.

Load-bearing premise

The load-bearing premise is Lemma 6, an imported result that for $\tilde{O}(d_{\lambda'}(A))$ landmarks from $\lambda'$-ridge leverage scores the expected Nyström projection satisfies $\mathbb{E}[P] \succeq \tfrac12 A(A+\lambda'I)^{-1}$; if that lemma is false or weaker than stated, the block count and the $O(\alpha)$ approximation factor collapse.

Editorial extensions

If this is right

  • For spectra with polynomial decay $\lambda_i=\Theta(i^{-1/\gamma})$, the construction is faster than classical Nyström by a factor $\tilde{\Omega}(\alpha^{2\gamma})$ at the same approximation quality; heavier tails give larger gains.
  • As a preconditioner for a strongly convex quadratic in the spiked-covariance model with at most $O(n^{0.82})$ large eigenvalues, the paper's Corollary 2 reduces the runtime from $\tilde{O}(n^{2.065})$ to $\tilde{O}(n^{2.044})$.
  • In kernel ridge regression over Hilbert spaces with smoothness $\zeta<1/2$, Block-Nyström recovers the near-optimal learning rate with an extra factor $\alpha$, and for small $\theta$ (with $\alpha=n^\theta$) it cuts the Nyström cost by $n^{2\theta\gamma}$.
  • The recursive inversion scheme itself is a reusable primitive: it applies $(\hat A+\lambda I)^{-1}$ in near-linear time without paying the $O(m^3)$ Woodbury cost on the full block system.

Reading between the lines

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

  • Beyond the paper: the averaging principle is not tied to ridge leverage scores; any estimator whose expectation captures the spectral tail but whose single draws are noisy could be averaged the same way, so random-feature and sketching variants are a natural testbed.
  • Beyond the paper: the bias-variance split suggests the optimal block count should track the ratio $d_{\alpha\lambda}(A)/d_{\alpha^2\lambda}(A)$, so one could tune $q$ adaptively from eigenvalue estimates, which the paper does not do.
  • Beyond the paper: if the imported expected-projection lemma is improved or weakened, the $16\alpha$ and $64\alpha$ constants and the phase-transition thresholds in the cost analysis should shift; the same calculations would identify cross-over regimes not listed in the paper.
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

2 major / 6 minor

Summary. The paper proposes Block-Nyström, an algorithm that averages q independent Nyström approximations built from smaller blocks of ridge-leverage-score landmarks, and claims a λ-regularized O(α)-approximation of an n×n psd matrix with rank m = O~(α d_{α²λ}(A)), construction time O~((nm²+m³)/α²+nm), and (after a recursive preconditioning scheme) inverse-application time O~(nm α^{o(1)}). The analysis is based on a bias-variance trade-off in which the expectation of the Nyström projection provides tail information and averaging controls variance, leading to a Chernoff-type concentration bound. Applications to quadratic minimization and to kernel ridge regression in the unattainable setting are given, including a new risk bound for approximate KRR with non-projection approximations.

Significance. The proposed technique is a genuine departure from the classical Nyström method: the improvement is obtained by sampling at regularizer α²λ instead of αλ, and the comparison with classical Nyström is not tautological. If the results hold, they reduce the cost of low-rank approximation in heavy-tailed spectral regimes by a factor α^{2γ} for polynomial decay, and the general KRR risk analysis of Theorem 5 is a useful independent contribution. The proof structure is transparent and the Chernoff argument for averaging is clean. However, the main spectral approximation theorem is conditional on an unproved external lemma (Lemma 6), and the recursive solver is stated with a self-referential constant; these are load-bearing gaps that must be addressed before the claims can be accepted.

major comments (2)
  1. [§3.1, Appendix B, Lemma 6] The proof of Theorem 6 relies on Lemma 6, which is stated without proof and cited to Rathore et al. [2025], an unpublished preprint with overlapping authorship. The lower bound E[P] ⪰ (1/2)A(A+λ'I)^{-1} is the sole source of the bound μ_min ≥ (1/8)√(λ/λ'), which in turn determines q = O(α) and the final approximation factor in Theorem 3, and the same lemma drives Theorem 7 and hence the recursive solver. This is the central load-bearing step of the paper; please include a complete proof of Lemma 6 or replace it with an independently verifiable published result.
  2. [Theorem 4 (main text) and Theorem 8 (Appendix B)] The stated condition on c is self-referential and therefore not a well-formed theorem hypothesis. Theorem 4 requires c ≥ max{ log^{2/ϕ}(20c²(1+θ)^4), 2 }, and Theorem 8 requires c ≥ max{ (4(1+θ)²)^{2/ϕ}, log^{2/ϕ}(20c²(1+θ)^4) }; in both cases c appears on both sides of the inequality. The proof sketch and Lemma 13 show that a sufficiently large c exists, but the theorem statements should be reformulated with an explicit choice, for example c = Θ(log n) satisfying the required inequalities, rather than a condition defined in terms of c itself.
minor comments (6)
  1. [Theorem 3] The displayed inequality uses (64α)^{-1} on the left-hand side, but the text calls this a 16α-approximation; the constant in the statement and the constant in the text should be made consistent.
  2. [Remark 2] The total landmark count is m = O~(α d_{α²λ}(A)), not O~(α d_{αλ}(A)) as written; the current formula is inconsistent with Theorem 1 and with the proof of Theorem 1.
  3. [Section 4 Discussion] The text 'O~(n^{0.065}+k^ω)' appears to be a typo for 'O~(n^{2.065}+k^ω)' based on the comparison in Corollary 2; please correct it.
  4. [Appendix C, Lemma 17] The phrase 'using techniques from Lemma 8' should refer to Theorem 8, since Lemma 8 is the Cordes inequality and is not the solver result used for the linear-system cost.
  5. [Theorem 8] The statement does not explicitly restrict 0<θ<1 and 0<ϕ<1, although the proof uses these restrictions; please state them in the theorem.
  6. [Proof of Theorem 6] The claim that the minimum of the displayed rational function is attained at x = √(λλ') is asserted without showing the calculation; adding the one-line derivation would improve verifiability.

Circularity Check

1 steps flagged · score 4.0 of 10

Central O(α) approximation guarantee rests on unproved, self-cited Lemma 6 from an overlapping-authorship preprint; no tautological fit, but the main bias bound is imported.

  1. self citation load bearing [Appendix A, Lemma 6; Appendix B, proof of Theorem 6 (restated Theorem 3)]
    "Lemma 6 (Rathore et al. [2025]) Let A ∈ Rn×n be psd and λ′ > 0. Let {pi}ni=1 be O(1)-approximate λ′-ridge leverage score sampling probabilities. ... E[P] ⪰ 1/2 A (A +λ′I)−1. (7) ... The second inequality holds due to Lemma 6 as E ˆAi ⪰ 1/2 A(A +λ′I)−1A."

    The proof of Theorem 6 derives μ_min ≥ (1/8)√(λ/λ′) solely by applying Lemma 6, and this μ_min is the only lower bound fed into the matrix-Chernoff step that yields the O(√(λ′/λ)) approximation and the block count q > 64√(λ′/λ) log(n/δ). With λ′ = α²λ, this becomes the O(α) guarantee of Theorem 1. Lemma 6 is stated without proof and attributed to Rathore et al. 2025, an arXiv preprint co-authored by M. Dereziński, one of the present authors; its constant 1/2 and sample-size condition O(d_{λ′}(A) log³ n) are not re-derived or independently verified in this paper.

full rationale

This is not a case of a fitted parameter being renamed as a prediction, nor does the O(α) guarantee reduce to the construction by definition. The averaging strategy, the bias-variance trade-off, the matrix-Chernoff argument, and the recursive preconditioning scheme are genuine technical content that goes beyond a tautology. However, the paper's central approximation Theorem 3 (and hence Theorem 1) is conditional on Lemma 6, an expected-projection lower bound imported from Rathore et al. 2025, a preprint with overlapping authorship (M. Dereziński). The lemma is quoted verbatim and used as a black box in the proof of Theorem 6; no proof or independent verification is provided in this manuscript. The constant 1/2 in Lemma 6 directly fixes the final approximation constant (16α) and the required number of blocks q = O(α), so the dependency is load-bearing rather than cosmetic. The recursive solver additionally imports Lemma 12 from Dereziński et al. 2025, but that is a published SODA result and is less of a circularity concern. Theorem 4 also contains a self-referential admissibility condition on c (c ≥ log^{2/ϕ}(20c²(1+θ)⁴)); this is an implicit fixed-point condition rather than a derivation that reduces to its own conclusion, so it is a presentation/correctness issue, not a circular step. On balance, the paper has some load-bearing self-citation in its key bias estimate, while much of the surrounding analysis remains independent, giving a score of 4 rather than 0 or 2.

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

The central claim rests on standard randomized linear algebra tools plus two imported technical lemmas from closely related papers by the same group (Lemma 6, Lemma 12). No data fitting; no new entities.

assumptions (5)
  • domain assumption E[P] >= (1/2) * A * (A + lambda' * I)^{-1} for lambda'-ridge leverage score sampling with Otilde(d_{lambda'}(A)) landmarks (Lemma 6, Rathore et al. 2025).
    Used in Theorem 6 (Appendix B) to lower bound the bias of the averaged Nyström estimators; this is the step that converts the block average into an O(sqrt(lambda'/lambda)) tail approximation.
  • domain assumption Approximate ridge leverage scores can be computed or generated at cost Otilde(n * d_lambda(A)^2) (Lemma 1, Musco-Musco 2017) or Otilde(min(1/lambda,n) * d_lambda(A)^2) when A_ii = O(1) (Lemma 2, Rudi et al. 2018).
    The stated time complexity of Block-Nyström construction relies on these sampling algorithms; they are standard but external.
  • domain assumption Single Nyström linear systems (Ahat_1 + psi*I)^{-1} can be solved in Otilde(n*m + m^3) preprocessing plus Otilde(n*m) per solve (Lemma 12, Dereziński et al. 2025).
    Used as the base case of the recursive preconditioning scheme in Theorem 8.
  • domain assumption Smoothness (Assumption 3) and capacity (Assumption 4) on the covariance operator for the KRR results.
    Standard in the unattainable learning setting; the risk bounds in Theorem 5 and 9 are conditional on these.
  • standard math Matrix Chernoff and Cordes inequalities.
    Used in Theorem 6 and 7 concentration arguments and in the risk decomposition in Theorem 9.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr\"om Method." pith.science (2026). https://pith.science/paper/JZVHUX35

@misc{pith2026250617556,
  author       = {Pith},
  title        = {Pith review of: Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr\"om Method},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JZVHUX35}},
  note         = {Machine review of arXiv:2506.17556}
}
read the original abstract

The Nystr\"om method is a popular low-rank approximation technique for large matrices that arise in kernel methods and convex optimization. Yet, when the data exhibits heavy-tailed spectral decay, the effective dimension of the problem often becomes so large that even the Nystr\"om method may be outside of our computational budget. To address this, we propose Block-Nystr\"om, an algorithm that injects a block-diagonal structure into the Nystr\"om method, thereby significantly reducing its computational cost while recovering strong approximation guarantees. We show that Block-Nystr\"om can be used to construct improved preconditioners for second-order optimization, as well as to efficiently solve kernel ridge regression for statistical learning over Hilbert spaces. Our key technical insight is that, within the same computational budget, combining several smaller Nystr\"om approximations leads to stronger tail estimates of the input spectrum than using one larger approximation. Along the way, we provide a novel recursive preconditioning scheme for efficiently inverting the Block-Nystr\"om matrix, and provide new statistical learning bounds for a broad class of approximate kernel ridge regression solvers.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 39 canonical work pages

  1. [1]

    Abedsoltan, M

    A. Abedsoltan, M. Belkin, and P. Pandit. Toward large kernel models. In International Conference on Machine Learning, pages 61--78. PMLR, 2023

    work page 2023

  2. [2]

    Abedsoltan, P

    A. Abedsoltan, P. Pandit, L. Rademacher, and M. Belkin. On the nystr \"o m approximation for preconditioning in kernel machines. In International Conference on Artificial Intelligence and Statistics, pages 3718--3726. PMLR, 2024

    work page 2024

  3. [3]

    A. E. Alaoui and M. W. Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In Proceedings of the 28th International Conference on Neural Information Processing Systems, pages 775--783, December 2015

    work page 2015

  4. [4]

    Avron, K

    H. Avron, K. L. Clarkson, and D. P. Woodruff. Faster kernel ridge regression using sketching and preconditioning. SIAM Journal on Matrix Analysis and Applications, 38 0 (4): 0 1116--1138, 2017

    work page 2017

  5. [5]

    F. Bach. Sharp analysis of low-rank kernel matrix approximations. In Conference on learning theory, pages 185--209. PMLR, 2013

    work page 2013

  6. [6]

    Bauer, S

    F. Bauer, S. Pereverzev, and L. Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23 0 (1): 0 52--72, 2007

    work page 2007

  7. [7]

    D. Burt, C. E. Rasmussen, and M. Van Der Wilk. Rates of convergence for sparse variational gaussian process regression. In International Conference on Machine Learning, pages 862--871. PMLR, 2019

    work page 2019

  8. [8]

    Caponnetto and E

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

    2007

Show all 44 references
  1. [9]

    M. B. Cohen, J. Nelson, and D. P. Woodruff. Optimal approximate matrix product in terms of stable rank. In International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016

    2016

  2. [10]

    Cucker and D

    F. Cucker and D. X. Zhou. Learning theory: an approximation theory viewpoint, volume 24. Cambridge University Press, 2007

    2007

  3. [11]

    Derezi \'n ski and E

    M. Derezi \'n ski and E. Rebrova. Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition. SIAM Journal on Mathematics of Data Science, 6 0 (1): 0 127--153, 2024

    2024

  4. [12]

    Derezi \'n ski and A

    M. Derezi \'n ski and A. Sidford. Approaching optimality for solving dense linear systems with low-rank structure. arXiv preprint arXiv:2507.11724, 2025

    2025 arXiv

  5. [13]

    Derezi \'n ski and J

    M. Derezi \'n ski and J. Yang. Solving dense linear systems faster than via preconditioning. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1118--1129, 2024

    2024

  6. [14]

    Derezi \'n ski, C

    M. Derezi \'n ski, C. Musco, and J. Yang. Faster linear systems and matrix norm approximation via multi-level sketched preconditioning. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1972--2004. SIAM, 2025

    2025

  7. [15]

    D \' az, E

    M. D \' az, E. N. Epperly, Z. Frangella, J. A. Tropp, and R. J. Webber. Robust, randomized preconditioning for kernel ridge regression. arXiv preprint arXiv:2304.12465, 2023

    2023 arXiv

  8. [16]

    M. A. Erdogdu and A. Montanari. Convergence rates of sub-sampled N ewton methods. Advances in Neural Information Processing Systems, 28: 0 3052--3060, 2015

    2015

  9. [17]

    Frangella, J

    Z. Frangella, J. A. Tropp, and M. Udell. Randomized nystr \"o m preconditioning. SIAM Journal on Matrix Analysis and Applications, 44 0 (2): 0 718--752, 2023

    2023

  10. [18]

    Frangella, P

    Z. Frangella, P. Rathore, S. Zhao, and M. Udell. Promise: Preconditioned stochastic optimization methods by incorporating scalable curvature estimates. Journal of Machine Learning Research, 25 0 (346): 0 1--57, 2024

    2024

  11. [19]

    Fujii, M

    J. Fujii, M. Fujii, T. Furuta, and R. Nakamoto. Norm inequalities equivalent to heinz inequality. Proceedings of the American Mathematical Society, 118 0 (3): 0 827--830, 1993

    1993

  12. [20]

    Gittens and M

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

    2013

  13. [21]

    Halko, P.-G

    N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53 0 (2): 0 217--288, 2011

    2011

  14. [22]

    Jambulapati and A

    A. Jambulapati and A. Sidford. Ultrasparse ultrasparsifiers and faster laplacian system solvers. ACM Trans. Algorithms, Feb. 2024. ISSN 1549-6325

    2024

  15. [23]

    I. M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. The Annals of statistics, 29 0 (2): 0 295--327, 2001

    2001

  16. [24]

    Kumar, M

    S. Kumar, M. Mohri, and A. Talwalkar. Sampling techniques for the nystrom method. In Artificial intelligence and statistics, pages 304--311. PMLR, 2009

    2009

  17. [25]

    J. Li, Y. Liu, and W. Wang. Optimal convergence rates for distributed nystr \"o m approximation. Journal of Machine Learning Research, 24 0 (141): 0 1--39, 2023

    2023

  18. [26]

    Lin and V

    J. Lin and V. Cevher. Optimal distributed learning with multi-pass stochastic gradient methods. In International Conference on Machine Learning, pages 3092--3101. PMLR, 2018

    2018

  19. [27]

    Lin and V

    J. Lin and V. Cevher. Convergences of regularized algorithms and stochastic gradient methods with random projections. Journal of Machine Learning Research, 21 0 (20): 0 1--44, 2020

    2020

  20. [28]

    Lin and L

    J. Lin and L. Rosasco. Optimal rates for multi-pass stochastic gradient methods. Journal of Machine Learning Research, 18 0 (97): 0 1--47, 2017

    2017

  21. [29]

    J. Lin, A. Rudi, L. Rosasco, and V. 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

  22. [30]

    Musco and C

    C. Musco and C. Musco. Recursive sampling for the nystrom method. Advances in neural information processing systems, 30, 2017

    2017

  23. [31]

    Mutny, M

    M. Mutny, M. Derezinski, and A. Krause. Convergence analysis of block coordinate algorithms with determinantal sampling. In International Conference on Artificial Intelligence and Statistics, pages 3110--3120, 2020

    2020

  24. [32]

    o m. \"U ber die praktische aufl \

    E. Nystr \"o m. \"U ber die praktische aufl \"o sung von integralgleichungen mit anwendungen auf randwertaufgaben. Acta Mathematica, 54 0 (1): 0 185--204, 1930

    1930

  25. [33]

    Z. Qu, P. Richt \'a rik, M. Tak \'a c, and O. Fercoq. Sdna: Stochastic dual newton ascent for empirical risk minimization. In International Conference on Machine Learning, pages 1823--1832. PMLR, 2016

    2016

  26. [34]

    Rathore, Z

    P. Rathore, Z. Frangella, J. Yang, M. Derezi\'nski, and M. Udell. Have AS kotch: Fast cocktails for large-scale kernel ridge regression. arXiv preprint arXiv:2407.10070, 2025

    2025

  27. [35]

    Rodomanov and D

    A. Rodomanov and D. Kropotov. A randomized coordinate descent method with volume sampling. SIAM Journal on Optimization, 30 0 (3): 0 1878--1904, 2020

    1904

  28. [36]

    Rudi and L

    A. Rudi and L. Rosasco. Generalization properties of learning with random features. Advances in neural information processing systems, 30, 2017

    2017

  29. [37]

    A. Rudi, R. Camoriano, and L. Rosasco. Less is more: Nystr \"o m computational regularization. Advances in neural information processing systems, 28, 2015

    2015

  30. [38]

    A. Rudi, L. Carratino, and L. Rosasco. Falkon: An optimal large scale kernel method. Advances in neural information processing systems, 30, 2017

    2017

  31. [39]

    A. Rudi, D. Calandriello, L. Carratino, and L. Rosasco. On fast leverage score sampling and optimal learning. Advances in Neural Information Processing Systems, 31, 2018

    2018

  32. [40]

    Steinwart

    I. Steinwart. Support Vector Machines. Springer, 2008

    2008

  33. [41]

    J. Sun, Z. Frangella, and M. Udell. Sapphire: Preconditioned stochastic variance reduction for faster large-scale statistical learning. arXiv preprint arXiv:2501.15941, 2025

    2025 arXiv

  34. [42]

    Williams and M

    C. Williams and M. Seeger. Using the nystr \"o m method to speed up kernel machines. Advances in neural information processing systems, 13, 2000

    2000

  35. [43]

    C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006

    2006

  36. [44]

    H. Ye, L. Luo, and Z. Zhang. Nesterov's acceleration for approximate newton. Journal of Machine Learning Research, 21 0 (142): 0 1--37, 2020

    2020

Pith tools

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