{"id":"7d0753e1-146e-4b3d-abc6-7fa8b690b79f","arxiv_id":"2411.16658","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Delaying projections in EigenPro-style kernel training cuts the amortized per-batch cost from quadratic to linear in model size, yielding up to hundreds of times faster training at comparable accuracy.","lead":"EigenPro 4 is a new algorithm for training kernel models that delays the expensive projection step so each data batch costs about one gradient step. On datasets with millions of samples it reports cutting training time from days to minutes with the same accuracy as previous kernel methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(p) amortized complexity claim depends on an unproven 'constant T_ep2' assumption for the inner projection (Table 4/Appendix B); if T_ep2 grows with p, Eq. (36) is superlinear and the central scaling claim fails.","rationale":"The reader's weakest_assumption identifies the same load-bearing premise: constant T_ep2 epochs for the inner projection. I agree that this is the most consequential gap because the central asymptotic claim--linear amortized time per iteration--is derived directly from this assumption in Appendix B and Table 4. If T_ep2 must grow with p, the amortized cost is superlinear and the headline scaling claim is not established. The Proposition 2 fixed-point mismatch is also real and should be fixed, but it is secondary: it undermines the appendix's convergence story rather than the complexity derivation itself. The empirical results are large-scale and concrete, and they may well indicate true practical speedups at the tested sizes, so I would not reject the paper. The verdict should remain conditional: the authors need to verify the T_ep2 scaling, correct Proposition 2, and provide code before the asymptotic claims are taken at face value.","tokens_in":35,"tokens_out":6053,"duration_ms":123589,"concrete_test":"On a fixed dataset (e.g., CIFAR5M* features, Laplace kernel bandwidth 5.0, Nystrom s=1000, preconditioner q=100), run the inner projection routine for p = 64K, 128K, 256K, 512K centers and measure the number of EigenPro 2 epochs T_ep2 needed to reach a fixed relative projection error ||proj_Z(f) - approx||_H / ||proj_Z(f)||_H <= epsilon (e.g., 1e-2). If T_ep2 grows with p, then Eq. (36) is not O(p) and the central complexity claim fails; report the fitted exponent of T_ep2 versus p.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Section 1.1 claim linear amortized time complexity per iteration, but the derivation in Appendix B rests on an explicit assumption stated in Table 4: that a constant number T_ep2 of EigenPro 2 epochs suffices for every delayed projection, independent of model size p. No proof or scaling experiment supports this. The inner projection is itself a kernel regression over p centers; EigenPro 2's convergence depends on the spectrum of K(Z,Z), which changes with p and with center placement, so the constant-epochs premise cannot be inherited from the Nystrom preconditioning results cited for the outer iterations. If T_ep2 grows like p^gamma, the amortized per-batch cost in Eq. (36) becomes superlinear in p, invalidating the claimed asymptotic scaling and the extrapolated speedups. The theoretical appendix also contains a concrete proof error: Proposition 2 claims convergence to K(·,Z)K^+(Z,X)y, but the proof's fixed point in Eq. (32) is [K(Z,X)K^{-1}(X,X)K(X,Z)]^{-1}K(Z,X)K^{-1}(X,X)y, which is not the pseudoinverse solution in general. Thus the theoretical support for the delayed-projection algorithm is incomplete, and the practical claims currently rest on empirical scaling alone.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15292,"tokens_out":18874,"duration_ms":149289,"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":[{"comment":"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.","section":"Appendix B, Table 4, Eq. (36)"},{"comment":"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":"Appendix A, Proposition 2 (Eqs. (29)-(32))"},{"comment":"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.","section":"Section 4.3, Eq. (25)"},{"comment":"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.","section":"Algorithm 1, lines 16-20"}],"minor_comments":[{"comment":"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.","section":"Section 3.2"},{"comment":"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.","section":"Appendix A, Algorithm 2"},{"comment":"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.","section":"Table 2 and Section 5"},{"comment":"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).","section":"Appendix C.3 and various"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for the journal and the empirical results are impressive. The main risks are the unverified constant-T_ep2 assumption and the inconsistencies in the theoretical appendix and pseudocode. If the authors address these, I would support publication. I did not attempt to reproduce the experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the EigenPro 4 paper. The delayed projection is a clean mechanism: instead of projecting back to the center set every mini-batch, accumulate temporary centers and run one projection every T steps, choosing T to balance the p^2 cost of projection against the batch work. That turns the per-batch cost from O(p^2) to O(p), assuming a constant number of inner EigenPro 2 epochs. The empirical section is the strongest part. On CIFAR5M, ImageNet, Webvision, and Librispeech, wall-clock speedups over EigenPro 3 and Falkon are large, accuracy is comparable or better, and scaling with model size looks roughly linear. If those numbers hold, this is a real advance for kernel methods.\n\nThe soft spots are both in the theory. First, Proposition 2 in Appendix A claims the exact algorithm converges to K(·,Z)K^+(Z,X)y, but the proof derives a different fixed point, the expression in Eq. (32), which is not the pseudoinverse solution in general. So the stated convergence target is wrong, even if the algorithm converges to something useful. Second, the O(p) amortized claim rests on the assumption in Table 4 that the number of inner EigenPro 2 epochs T_ep2 is constant in the model size p. There is no proof or scaling experiment for that. The inner projection is itself a kernel regression on p centers; its spectrum changes with p and center placement, so the constant-epochs premise cannot be inherited from the Nystrom preconditioning results cited for the outer loop. If T_ep2 grows as p^gamma, Eq. (36) becomes superlinear and the headline complexity claim fails. This is load-bearing, not a minor caveat.\n\nThe stress-test note is right about both issues. I would not reject the paper; the empirical evidence is consistent and the algorithm is well specified. But the complexity claims should be restated as conditional on an empirical constant-epochs observation, and the fixed-point claim should be corrected. Also worth asking for code release with a commit hash and variance numbers.\n\nThis is for anyone working on scalable kernel methods or the EigenPro line. It deserves a serious referee and likely major revision rather than a desk reject.","headline":"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.","tokens_in":15844,"tokens_out":3268,"would_cite":true,"duration_ms":28838,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Delaying the projection step makes large-kernel-model training linear in time and memory.","keywords":["kernel methods","large-scale kernel regression","delayed projection","preconditioned stochastic gradient descent","Nyström approximation","EigenPro","linear-time training","kernel machines"],"falsifier":"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.","tokens_in":14765,"feed_emoji":"⚡","tokens_out":10994,"duration_ms":89999,"temperature":0.7,"pith_summary":"EigenPro 4 is a training algorithm for kernel models of the form $f(x)=\\sum_i \\alpha_i K(x,z_i)$. The paper claims that by delaying the projection back onto the model's center set until after several minibatches have been processed, the amortized cost per iteration becomes linear in the model size $p$, while memory also stays linear in $p$. If true, kernel machines with hundreds of thousands to millions of centers can be trained on a single GPU in minutes to hours instead of days, while matching or exceeding the accuracy of prior kernel solvers such as EigenPro 3 and Falkon. The reported speedups reach 600x and more, and convergence requires fewer epochs for large models.","feed_headline":"Delayed projections make kernel training linear in model size","feed_subtitle":"Million-center kernel models train on one GPU in minutes to hours, matching or beating prior accuracy.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the EigenPro preconditioned SGD update that this algorithm inherits","marker":"(Ma and Belkin, 2017)"},{"why":"introduces the Nyström-approximate preconditioner and the inner EigenPro 2 solver used for the inexact projection","marker":"(Ma and Belkin, 2019)"},{"why":"introduces EigenPro 3, the decoupled model formulation, and the exact projection formula used here","marker":"(Abedsoltan et al., 2023)"},{"why":"establishes that $O(\\log^4 n)$ Nyström samples suffice for preconditioning, justifying the small subsample size","marker":"(Abedsoltan et al., 2024)"},{"why":"defines Falkon, the $O(p^2)$-memory baseline whose complexity and memory are compared","marker":"(Rudi et al., 2017)"},{"why":"is the scaled Falkon implementation cited for memory requirements at large model sizes","marker":"(Meanti et al., 2020)"},{"why":"supplies the Nyström approximation used in the preconditioner and auxiliary model","marker":"(Williams and Seeger, 2000)"}],"fun_headline_variants":["Delayed projections make kernel training 600x faster","Million-center kernel models train on one GPU with delayed projections","EigenPro4: delayed projections accelerate large kernel training","Delayed projections slash kernel training time by up to 600x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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)$.","fun_headline_variants_meta":{"raw":{"variants":["Delayed projections make kernel training 600x faster","Million-center kernel models train on one GPU with delayed projections","EigenPro4: delayed projections accelerate large kernel training","Delayed projections slash kernel training time by up to 600x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000273,"raw_usage":{"total_tokens":1591,"prompt_tokens":855,"completion_tokens":736,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":667}},"tokens_in":471,"tokens_out":736,"duration_ms":7008,"temperature":1.0,"reasoning_tokens":667,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:51:49.913806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Diving into the shallows: a computational perspective on large-scale shallow learning","cited_arxiv_id":null,"evidence_quote":"introduces the EigenPro preconditioned SGD update that this algorithm inherits"},{"cited_title":"Toward large kernel models","cited_arxiv_id":null,"evidence_quote":"introduces EigenPro 3, the decoupled model formulation, and the exact projection formula used here"},{"cited_title":"On the nystrom approximation for preconditioning in kernel machines","cited_arxiv_id":null,"evidence_quote":"establishes that $O(\\log^4 n)$ Nyström samples suffice for preconditioning, justifying the small subsample size"},{"cited_title":"Kernel methods through the roof: handling billions of points efficiently","cited_arxiv_id":null,"evidence_quote":"is the scaled Falkon implementation cited for memory requirements at large model sizes"},{"cited_title":"Using the nystr \\\"o m method to speed up kernel machines","cited_arxiv_id":null,"evidence_quote":"supplies the Nyström approximation used in the preconditioner and auxiliary model"}],"review_version":1}