REVIEW 4 major objections 4 minor 29 references
Fast training of large kernel models with delayed projections
T0 review · 4 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Delaying the projection step makes large-kernel-model training linear in time and memory.
desk verdict Delayed projection is a clean algorithmic contribution with strong empirical scaling, but the paper's stated convergence target and its O(p) complexity claim both rest on assumptions that are neither proved nor tested. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Before a projection, the model is the auxiliary model $f=K(\cdot,Z)\alpha+K(\cdot,Z_{\mathrm{tmp}})\beta+K(\cdot,X_s)\alpha_s$, with $Z_{\mathrm{tmp}}$ holding the last $T$ minibatches and $X_s$ a Nyström subsample. The algorithm maintains the accumulated gradient $h$ and the auxiliary weights $\alpha_s$ through additive updates, reusing values $f_{T-1}(Z)$ that were already computed, so the projection step only needs to solve a system with $K(Z,Z)$. The preconditioner $P^s=I-\sum_{i=1}^q(1-\lambda^s_{q+1}/\lambda^s_i)\psi_i\otimes\psi_i$, built from the top-$q$ eigensystem of $K(X_s,X_s)$, suppresses the largest Hessian eigenvalues and adds only $O(sq)$ extra storage.
What would settle it
Fix a dataset and $T_{\mathrm{ep2}}$, run EigenPro 4 with $p=64$K, $256$K, and $1$M centers, and measure wall-clock time per epoch; linear scaling in $p$ is falsified if per-epoch time grows faster than linearly. A more direct check is to measure the projection residual of the inexact projection as $p$ grows at fixed $T_{\mathrm{ep2}}$: if the residual does not stay bounded, the constant-epoch premise is false.
Extended reading notes
Core claim
The central discovery is that the projection back onto the model subspace, $\mathrm{proj}_Z(u)=K(\cdot,Z)K^{-1}(Z,Z)u(Z)$, does not have to be recomputed after every stochastic batch. EigenPro 4 lets the model grow for $T$ batches by adding those batches as temporary centers, applies the Nyström-preconditioned updates there, and only then projects back into $\mathrm{span}\{K(\cdot,z_j)\}$. The amortized cost is minimized at $T^\star=(p/m)\sqrt{2T_{\mathrm{ep2}}}$, where $T_{\mathrm{ep2}}$ is the number of inner EigenPro 2 epochs used for the approximate projection; at this $T$ the per-batch cost is $O(p)$ and memory remains $O(p)$. The paper verifies this empirically on CIFAR5M, ImageNet, Webvision, and Librispeech, reporting speedups of up to 600x (and larger in the tables) with accuracy comparable to or better than EigenPro 3 and Falkon.
Load-bearing premise
The linear-time claim stands on the assumption, stated in the complexity analysis, that a fixed number of inner EigenPro 2 epochs ($T_{\mathrm{ep2}}$) is enough to approximate the projection for every model size; if that number must grow with $p$, the amortized per-batch cost stops being $O(p)$.
Editorial extensions
If this is right
- A kernel model with $p=1$M centers can be trained on a 10M-sample dataset in roughly an hour on one GPU (Librispeech: 70 minutes, over 411x faster than EigenPro 3), instead of days.
- Memory stays $O(p)$: Falkon-style $O(p^2)$ memory blowups disappear, so models that run out of memory for Falkon at 256K centers run for EigenPro 4 up to 1M centers.
- The number of epochs to convergence drops sharply for large models: on ImageNet with 512K centers, EigenPro 4 converges in about 15 epochs, while EigenPro 3 needs roughly 100 epochs.
- Per-epoch wall-clock time grows roughly linearly with model size, making larger kernel models practical on a single GPU rather than prohibitive.
Reading between the lines
- The amortization idea should transfer to any iterative method whose per-step projection is the bottleneck, such as constrained RKHS descent or sparse Gaussian-process variational inference.
- The accuracy dips after each projection visible in the paper's experiments suggest an adaptive schedule starting with small $T$ and increasing it over training; the paper fixes $T$ as a hyperparameter.
- If the constant-$T_{\mathrm{ep2}}$ premise fails, scaling $T_{\mathrm{ep2}}$ logarithmically or polynomially with $p$ and re-optimizing $T$ would be a natural repair; the paper gives no such analysis.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces EigenPro 4, a kernel machine training algorithm that combines Nyström-preconditioned stochastic gradient descent with delayed projections. The key idea is to accumulate gradient updates over T mini-batches in an auxiliary model (temporary centers plus Nyström corrections) and only then project back onto the span of the model centers Z. The paper claims that this reduces the amortized per-iteration time from O(p^2) to O(p), achieves linear memory scaling with model size, and delivers up to 600x speedups over EigenPro 3 and Falkon across CIFAR, ImageNet, Webvision, and Librispeech. The theoretical appendix analyzes an exact precursor (Algorithm 2) and claims convergence to a kernel ridge-type solution, while the empirical section reports large and consistent speedups.
Significance. If the complexity claim holds, this is a significant advance for large-scale kernel methods: it decouples the model from the training set and achieves linear scaling in both time and memory, with strong empirical evidence (Table 2, Figure 6) showing consistent speedups and maintained or improved accuracy. The paper provides detailed flop counts (Table 3) and derives the update rules from first principles, which are genuine strengths. However, the central complexity claim depends on an unproven constant-epoch assumption for the inner projection, and the theoretical appendix contains a concrete error (Proposition 2). The empirical results are compelling but do not by themselves establish the asymptotic complexity claim.
major comments (4)
- [Appendix B, Table 4, Eq. (36)] The claim of O(p) amortized time per batch (abstract, Section 1.1, and Eq. (36)) rests on the assumption, stated in Table 4, that a constant number T_ep2 of EigenPro 2 epochs suffices for each delayed projection regardless of model size p. No proof or scaling experiment is provided. The inner projection is a kernel regression over p centers whose conditioning changes with p and with the choice of centers, so this premise cannot be inherited from the Nyström preconditioning results cited for the outer iterations. If T_ep2 grows with p, the factor p sqrt(2 T_ep2) in Eq. (36) becomes superlinear and the central complexity claim fails. The paper should prove a bound on T_ep2 or report experiments that vary p while holding T_ep2 fixed and measure projection error.
- [Appendix A, Proposition 2 (Eqs. (29)-(32))] Proposition 2 states that Algorithm 2 converges to K(·,Z)K^+(Z,X)y, but the proof derives the fixed point in Eq. (32) as K(·,Z)[K(Z,X)K^{-1}(X,X)K(X,Z)]^{-1}K(Z,X)K^{-1}(X,X)y. These two expressions are not equal in general, so the proposition is internally inconsistent. Proposition 1 already proves convergence to the Eq. (32) expression; either the statement of Proposition 2 is a typo and should be corrected, or the proof needs to be revised. Since Eq. (25) uses K^{-1}(Z,Z), the relevance of the pseudoinverse claim to Algorithm 1 is also unclear.
- [Section 4.3, Eq. (25)] Equation (25) is inconsistent with Eq. (24). Eq. (24) defines the projection step as f_T = proj_Z(f_{T-1} - η P^s ∇L(f_{T-1})), but Eq. (25) states f_T = K(·,Z)K^{-1}(Z,Z)f_{T-1}(Z), omitting the gradient term. The subsequent derivation in Eq. (27) introduces h to account for the accumulated gradients, but the text should show the gradient term explicitly in Eq. (25) and explain how h replaces it.
- [Algorithm 1, lines 16-20] There is a sign and scaling mismatch between the pseudocode and the derivation in Eq. (27). In the pseudocode, h accumulates h ← h - η K(Z,Xm)gm + η M F^T K(Xs,Xm)gm, so h is O(η). Line 20 then updates α ← α - (n/m) η θ with θ = proj_Z(h). If θ = K^{-1}(Z,Z)h, this correction is O(η^2) and has the opposite sign from the coefficient update α - K^{-1}(Z,Z)h derived in Eq. (27). Please reconcile the pseudocode with the derivation; this is essential for reproducing the reported results.
minor comments (4)
- [Section 3.2] The statement that the value of T has "an effective selection method detailed in Section B" is not supported: Appendix B derives the optimal T in terms of p, m, and T_ep2, but does not say how to choose T_ep2 or set T in practice.
- [Appendix A, Algorithm 2] The pseudocode does not make explicit that the coefficient vector β_t accumulates across iterations; the proof in Eq. (30) uses β_t = β_{t-1} + correction. Please update the pseudocode to avoid ambiguity.
- [Table 2 and Section 5] The reported speedups are for one epoch rather than for end-to-end training; the abstract's "up to 600× speedup" should be qualified as a per-epoch speedup unless full convergence-time comparisons are provided for all datasets.
- [Appendix C.3 and various] Typos and minor wording issues: "distangle" (Introduction), "compare to" (Section 1.1), "expermients" (Appendix C.1), "bandwith" and "imagnet" (Appendix C.3), and the contradictory sentence about Falkon running out of memory for model sizes "larger than 256000" while also stating "we could not run it for 256000" (Appendix C.3).
Circularity Check
No significant circularity: the O(p) amortized complexity is arithmetic from explicit flop counts, and the speedups are measured; the unproven constant-T_ep2 premise is a correctness gap, not a circular reduction.
full rationale
The derivation chain is self-contained. Appendix B tabulates the per-line flops of Algorithm 1 (Table 3), sums them over T batches (Eq. 33), optimizes T (Eq. 35), and substitutes back to obtain the amortized per-batch cost (Eq. 36). Each step is explicit algebra from the update equations in Section 4, so the O(p) claim does not secretly rest on a fitted parameter or on a result whose target is the paper's own conclusion. The speedup figures in Table 2 and Figure 6 are measured runtimes, not values produced by the complexity formula. Prior work by the same authors (EigenPro 2 preconditioner, EigenPro 3 projection, the log^4 n Nyström result) is used as lemmas and components; none of these citations is invoked to force the delayed-projection result, and the cited projection formula is an elementary fact. The genuine weakness is non-circular: Table 4 states 'we assumed only a constant number of epochs of EigenPro 2.0 is needed for large scale experiments' without proof or scaling study, so if T_ep2 grows with p then Eq. (36) becomes superlinear. That is an unproven premise, not a reduction-by-construction. Similarly, Proposition 2's proof reaches the fixed point [K(Z,X)K^{-1}(X,X)K(X,Z)]^{-1}K(Z,X)K^{-1}(X,X)y, which does not in general equal K(·,Z)K^+(Z,X)y; this is a proof error, not circularity. Because the central complexity and speedup claims are either measured or derived by explicit count, the paper receives score 0.
Assumptions & free parameters
free parameters (6)
- kernel bandwidth =
5.0 (Table 2, Figures 1 and 3), 16 or 20 (Figures 5 and 6)
- Nyström sample size s =
1000 (Table 2, Figures 1 and 3), 10000 (Figures 5 and 6)
- preconditioner level q =
100 (Table 2, Figures 1 and 3), 1000 (Figures 5 and 6)
- projection period T =
T = 11 in Figure 3; otherwise optimal T* derived in Equation 35 using T_ep2
- inner EigenPro 2 epochs T_ep2 =
not reported
- learning rate eta =
not reported
assumptions (5)
- standard math Reproducing kernel Hilbert space theory, including the reproducing property and Fréchet derivatives (Section 2).
- standard math The Nyström approximation with s = O(log^4 n) samples is sufficient for preconditioning, cited to Abedsoltan et al. (2024).
- domain assumption The feature representations are fixed and pretrained (MobileNetV2, ResNet-18, VGG+BLSTM), and the kernel is applied to these features.
- domain assumption The Laplace kernel with a hand-chosen bandwidth is a suitable kernel for the tested image and speech features.
- ad hoc to paper The projection step can be approximated by a constant number T_ep2 of EigenPro 2 iterations, independent of model size.
Cite this review
Pith. "Pith review of Fast training of large kernel models with delayed projections." pith.science (2026). https://pith.science/paper/DYUV5IC5
@misc{pith2026241116658,
author = {Pith},
title = {Pith review of: Fast training of large kernel models with delayed projections},
year = {2026},
howpublished = {\url{https://pith.science/paper/DYUV5IC5}},
note = {Machine review of arXiv:2411.16658}
}
read the original abstract
Classical kernel machines have historically faced significant challenges in scaling to large datasets and model sizes--a key ingredient that has driven the success of neural networks. In this paper, we present a new methodology for building kernel machines that can scale efficiently with both data size and model size. Our algorithm introduces delayed projections to Preconditioned Stochastic Gradient Descent (PSGD) allowing the training of much larger models than was previously feasible, pushing the practical limits of kernel-based learning. We validate our algorithm, EigenPro4, across multiple datasets, demonstrating drastic training speed up over the existing methods while maintaining comparable or better classification accuracy.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[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]
Amirhesam Abedsoltan, Mikhail Belkin, and Parthe Pandit. Toward large kernel models. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023
work page 2023
-
[3]
On the nystrom approximation for preconditioning in kernel machines
Amirhesam Abedsoltan, Mikhail Belkin, Parthe Pandit, and Luis Rademacher. On the nystrom approximation for preconditioning in kernel machines. 27th International Conference on Artificial Intelligence and Statistics (AISTATS), 2024
work page 2024
-
[4]
To understand deep learning we need to understand kernel learning
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541--549. PMLR, 2018
work page 2018
-
[5]
Reconciling modern machine-learning practice and the classical bias--variance trade-off
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias--variance trade-off. Proceedings of the National Academy of Sciences, 116 0 (32): 0 15849--15854, 2019
2019
-
[6]
Nytro: When subsampling meets early stopping
Raffaello Camoriano, Tom \'a s Angles, Alessandro Rudi, and Lorenzo Rosasco. Nytro: When subsampling meets early stopping. In Artificial Intelligence and Statistics, pages 1403--1411. PMLR, 2016
work page 2016
-
[7]
Imagenet: A large-scale hierarchical image database
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248--255. Ieee, 2009
2009
-
[8]
Product kernel interpolation for scalable gaussian processes
Jacob Gardner, Geoff Pleiss, Ruihan Wu, Kilian Weinberger, and Andrew Wilson. Product kernel interpolation for scalable gaussian processes. In International Conference on Artificial Intelligence and Statistics, pages 1407--1416. PMLR, 2018
work page 2018
Show all 29 references
-
[9]
Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=hsFN92eQEla
2021
-
[10]
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Cl \'e ment Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018
2018
-
[11]
Speech & language processing
Dan Jurafsky. Speech & language processing. Pearson Education India, 2000
2000
-
[12]
Learning multiple layers of features from tiny images
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009
2009
-
[13]
Webvision database: Visual learning and understanding from web data
Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool. Webvision database: Visual learning and understanding from web data. arXiv preprint arXiv:1708.02862, 2017
2017 arXiv
-
[14]
Diving into the shallows: a computational perspective on large-scale shallow learning
Siyuan Ma and Mikhail Belkin. Diving into the shallows: a computational perspective on large-scale shallow learning. Advances in neural information processing systems, 30, 2017
2017
-
[15]
Kernel machines that adapt to gpus for effective large batch training
Siyuan Ma and Mikhail Belkin. Kernel machines that adapt to gpus for effective large batch training. Proceedings of Machine Learning and Systems, 1: 0 360--373, 2019
2019
-
[16]
Alexander G. de G. Matthews, Mark van der Wilk , Tom Nickson, Keisuke. Fujii, Alexis Boukouvalas , Pablo Le \'o n-Villagr \'a , Zoubin Ghahramani, and James Hensman. GP flow: A G aussian process library using T ensor F low . Journal of Machine Learning Research, 18 0 (40): 0 1...
2017
-
[17]
Kernel methods through the roof: handling billions of points efficiently
Giacomo Meanti, Luigi Carratino, Lorenzo Rosasco, and Alessandro Rudi. Kernel methods through the roof: handling billions of points efficiently. Advances in Neural Information Processing Systems, 33: 0 14410--14422, 2020
2020
-
[18]
The deep bootstrap framework: Good online learners are good offline generalizers
Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. International Conference on Learning Representations, 2021
2021
-
[19]
Librispeech: an asr corpus based on public domain audio books
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an asr corpus based on public domain audio books. In 2015 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 5206--5210. IEEE, 2015
2015
-
[20]
Have askotch: Fast methods for large-scale, memory-constrained kernel ridge regression
Pratik Rathore, Zachary Frangella, and Madeleine Udell. Have askotch: Fast methods for large-scale, memory-constrained kernel ridge regression. arXiv preprint arXiv:2407.10070, 2024
2024
-
[21]
Falkon: An optimal large scale kernel method
Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. Falkon: An optimal large scale kernel method. Advances in neural information processing systems, 30, 2017
2017
-
[22]
Pegasos: Primal estimated sub-gradient solver for svm
Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub-gradient solver for svm. In Proceedings of the 24th international conference on Machine learning, pages 807--814, 2007
2007
-
[23]
Variational learning of inducing variables in sparse gaussian processes
Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial intelligence and statistics, pages 567--574. PMLR, 2009
2009
-
[24]
Towns, T
J. Towns, T. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. Scott, and N. Wilkins-Diehr. Xsede: Accelerating scientific discovery. Computing in Science & Engineering, 16 0 (05): 0 62--74, sep 2014. IS...
2014 doi
-
[25]
ESPnet : End-to-end speech processing toolkit
Shinji Watanabe, Takaaki Hori, Shigeki Karita, Tomoki Hayashi, Jiro Nishitoba, Yuya Unno, Nelson Enrique Yalta Soplin , Jahn Heymann, Matthew Wiesner, Nanxin Chen, Adithya Renduchintala, and Tsubasa Ochiai. ESPnet : End-to-end speech processing toolkit. In Proceedings of Inter...
2018 doi
-
[26]
Pytorch image models
Ross Wightman. Pytorch image models. https://github.com/rwightman/pytorch-image-models, 2019
2019
-
[27]
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. Advances in neural information processing systems, 13, 2000
2000
-
[28]
Kernel interpolation for scalable structured gaussian processes (kiss-gp)
Andrew Wilson and Hannes Nickisch. Kernel interpolation for scalable structured gaussian processes (kiss-gp). In International conference on machine learning, pages 1775--1784. PMLR, 2015
2015
-
[29]
Understanding deep learning (still) requires rethinking generalization
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64 0 (3): 0 107--115, 2021
2021
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.