Fast Training of Large Kernel Models with Delayed Projections
Authors: Amirhesam Abedsoltan
Siyuan Ma
Parthe Pandit
Mikhail Belkin
Venue: NeurIPS 2025 spotlight ()
Keywords: Kernel machines
large-scale kernel machines
Preconditioned-SGD
Nyström approximation
Primary area: general_machine_learning
TL;DR: We introduce a new SGD-based algorithm with delayed projection for training kernel machines that achieves comparable or superior performance while reducing training time from days to under an hour.

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. We validate our algorithm, \EP4, across multiple datasets, demonstrating drastic training speedups without compromising the performance. Our implementation is publicly available at: https://github.com/EigenPro/EigenPro
.

Fast Training of Large Kernel Models with Delayed Projections
Amirhesam Abedsoltan UC San Diego abedsol1@ucsd edu
Siyuan Ma" Google siyuan@siyuanm. com
Parthe Pandit IIT Bombay pandit@iitb ac.
Mikhail Belkin
UC San Diego mbelkin@ucsd. edu
Abstract
Classical kernel machines have historically faced significant challenges in scaling large datasets and model sizes-a a key ingredient that has driven the success of neural networks. In this paper, we present 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. We validate our algorithm, EigenPro across multiple datasets, demon- strating drastic training speedups without compromising the performance. Our implementation is publicly available at: http::/ggitubb.co//iiign////////
Introduction
Kernel methods have strong theoretical foundations and broad applicability. They have also served as the foundation for understanding many significant phenomena in modern machine learning (9 4 3 28 Despite these advantages, the scalability of kernel methods has remained a persistent challenge, particularly when applied to large datasets. Addressing this limitation is critical for expanding the utility of kernel-based techniques modern machine learning applications.
A naive approach for training kernel machines is to directly solve the equivalent kernel matrix inversion problem. In general, the computational complexity of this approach is O(n"), where is the number of training samples. Thus, computational cost grows rapidly with the size of the dataset, making it computationally intractable for datasets with more than 10 data points.
To address this challenge, various methods employing iterative algorithms and approximations have been proposed. Among these, Gradient Descent (GD)-based algorithms like Pegasos (1] and EigenPro 1.0.2.0 13, 14 have significantly reduced the computational complexity to O(n²). These methods, adaptable for stochastic settings, offer more efficient implementations. Nevertheless, the scalability of kernel machines remains constrained by the inherent linkage between the model size and the training
Furthermore, the Nyström methods have emerged as favored approach for scaling kernel machines, with seminal works with (26] paving the way. Methods such as NYTRO [5). Falkon (2) and ASkotch [19] leverage the Nyström Approximation (NA) in combination with other strategies to enhance performance. NYTRO merges NA with gradient descent to improve condition number, ASkotch combines with block coordinate descent, whereas Falkon combines it with the Conjugate Gradient method, facilitating the handling of large training sets. However, these strategies limited by model size due to memory restrictions, exhibiting quadratic scaling in relation to the size of the
Work completed during author's at Google. Current affiliation: Lynko.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Time per epoch
Algorithm
FLOPS
Memory
- Palion
setup
per batch
Hours
M9M
EigenPro 4
0(1)
O(p)
(pp)
06, 62.6
96.71%
EigenPro 3
((1)
O(p²)
O
16.20%
F6 731.
08.70
00.cat
Falkon
O(p")
(pp)
Opp²
27.99%
86, 66.00%
64
128
256
512
1000
Model
Figure 1: Comparison of per-epoch time complexity across solvers as function of model size Performance in terms of classification test accuracy (indicated as percentages) is annotated next to each data point, showing that EP4 maintains superior or comparable performance across all model sizes. Details of the experiment and hardware can be found in Appendix
model. For instance, scaling Falkon [6] method to model size of 512, 000 necessitates over ITB of RAM, surpassing the capacity of most high-end servers available today.
Other lines of work the Gaussian Processes literature, e.g., [2] 1,], use so-called inducing points to control model complexity. However, these methods face similar scaling issues they require quadratic memory in terms of the number of inducing points, preventing large models.
Recently, EigenPro 3.0 was introduced in [. Unlike previous versions, EigenPro 3.0 distangles the model from the training set, similar to Falkon, but with the added advantage that its memory requirements scales linearly with the model size. This advancement makes feasible to tackle kernel models of sizes previously deemed unattainable. However, its per iteration time complexity remains quadratic relative to the model size, significantly slowing its practical application.
this paper, we build upon EigenPro 3.0 and introduce EigenPro This new algorithm retains advantageous features of EigenPro 3.0, such decoupling the model from the training set and linear scaling memory complexity. Moreover, significantly improves upon the time complexity, achiev- ing amortized linear scaling per iteration with respect model size. Empirically we observe that the proposed algorithm converges in fewer epochs, without compromising generalization performance.
1.1 Main contribution
Our method for kernel machine problems achieves three key advantages: (1) linear amortized time complexity per iteration, (2) linear memory scaling with model size, (3) comparable or superior performance compare to existing methods while demonstrating up to 600x speedup in our experiments. Figure demonstrates these benefits on the CIFAR5M data set.
1.2 Organization of the Paper
The remainder of this paper is organized as follows. Section 2 provides the necessary background and preliminaries. In Section 3 we derive the complete algorithm, and introduce the key insights and techniques that enable its dramatic improvement in computational efficiency. Finally, Section 4 presents extensive experimental results across multiple datasets and model sizes.
Notation and Background
In what follows, functions are lowercase letters sets are uppercase letters A, vectors are lowercase bold letters a, matrices are uppercase bold letters A, operators are calligraphic letters A, spaces and sub-spaces are boldface calligraphic letters A.
General kernel models. Following EigenPro 3.0 [ notations, given training data (X, = [z; Rd Vi IR) } General kernel models are models of the form,
f(x) = Σ
a K (g,K( (z)

---

Here, K : R XR + I is positive are centers, which are necessarily the training set X. We will refer to p as the model size. We define H as the unique reproducing kernel Hilbert space (RKHS) corresponding to K.
symmetric kernel function and Z = {z, E R
Loss function. Our goal will be to find the solution the following infiniteddimension. Mean Squared Error (MSE) problem for general kernel models,
minimize L(f) (f(a,) y.)² FEH
subject to f 2 == span (1(())))},))) (1)
i=1
Evaluations and kernel matrices.
The vector of evaluations of function f over set X {2; 1 denoted f(X) == (f(x.)) E R". For sets and Z, with |X| = n and |Z| P. we denote the kernel matrix () E R=*P, while K(Z,X) = ( 2) Similarly, X) E H. is vector of functions, and use K(,,)a Σ K(, 2i)a; H, to denote their linear combination. Finally, for operator A, a function a, and set A {a; of evaluations,
denote the vector
Afa (A) (b(a;)) R
where b b= A (a).
(2)
Fréchet derivative. Given a function J H + R. the Fréchet derivative of with respect to f is linear functional, denoted v,J, such that for h E H
JJ + h) J(f) V J(h) 0.
lim |M x
(3)
Since y is a linear functional, it lies in the dual space 7t" Since is a Hilbert space, is self-dual, whereby 7t" H. If f is general kernel model, and is the square loss for given dataset (X, i.e, T(])= == ">=(( (f(z)) - y:)² we can apply the chain rule, and using reproducing property of H. and the fact that V (J.9) = g. get, that the Fréchet derivative of L, at f fo is,
v = E (fo(a.)) - y:) f = K (() yy) y)
(4)
Hessian operator. The Hessian operator V3L: H-7 for the square loss is given by
K. = Σ K(, @ ((,,))).,
KC) = Σ x(2z,;))(aa))
X){(),, (5)
where @ denotes the outer product between functions in the RKHS, defined as (a8b)()) - =(-) (b. H
The operator K. has non-negative eigenvalues. which we order as \ X 2 ... 2 An Hence, we can write its eigen- decooposcoooiiiionnn as IC = EE= As th & v/. Combining Equations and 5 we can rewrite the Fréchet derivative of the loss function as
v I K. (f(()) y) (=).
Exact minimum norm solution. The closed-form minimum II-I1 norm solution the problem defined in equation (1) is given by:
:= (=,
where t is the pseudoinverse or Moore-Penrose inverse. In the case of X = Z it simplifies to f. ;== (X,
Gradient Descent (GD). If we apply GD the optimization problem in i with learning rate 77, in the 7. functional space, the update as following,
S41
7 L = (((( y)
(8)
The first point note that the derivative lies in X span (K (K(x)))}) rather than in Z. Therefore, when X * Z, SGD cannot be applied in this form. We will revisit this issue later. The second point that the case of = Z, traditional kernel regression problem, the convergence of SGD depends on the condition number of K. Simply put, this is the ratio of the largest to the smallest
3

---

non-zero singular value of the Hessian operator defined in 5 It is known that for general kernel models this condition number ill conditioned and converges slow, see [2] for more details on this.
EigenPro. Prior work, FigenPro, by 13]. addresses the slow convergence of SGD by introducing a preconditioned stochastic gradient descent mechanism in Hilbert spaces. The update rule is the same as Equation but with an additional preconditioner P H + H. applied to the gradient,
fi+1 ft PV L(f)).
(9)
In short, the role of the preconditioner P is to suppress the top eigenvalues of the Hessian operator IC to improve the condition number. We next explicitly define P.
Definition 1 (Top-q Eigensystem). Let Å₁ > A > > Xn be the eigenvalues of a Hermitian
matrix A E Raxx, where for standard unit vector ei we have Ae; λee We define the tuple (Ag: Ey: x as the top-q eigensystem, where:
Ag == diag(X (A1, ,2,...,,
A1) E Rox0
E= [e1 Eg,..., ey] Rnxy
(10)
Preconditioner. Using Definition let (Ag. Egg 11+1) be the top-q eigensystem of K ((X, (X) the preconditioner P H. H. can be explicitly written as, : I - E (1 (1-A, t @ th.
Nyström approximate preconditioner. FigenPro 2, introduced by 14) implements a stochastic approximation for P based on the Nyström extension, thereby reducing the time and memory complexity compared to EigenPro. The first step is to approximate the Hessian operator using the Nyström extension as follows,
K(, x @ K(,
Σ
X
20 vr.
(11)
This is a Nyström approximation of IC using s uniformly random samples from X, referred to X., where (Aa. E; X²+1) represents the corresponding top-g eigensystem of K(,,, X,). Using this approximation, we can define the approximated preconditioner as follows, Pa := I- I-Σ (1
X11 Xg 1 @ vp. For more details on the performance of this preconditioner compared
to the case of 8 = n, see 22, who showed that choosing Z log" n is sufficient.
Of particular importance is the action of this preconditioner any function of the form K(, A)u.
P P'K(,AAuu = K(, A)u
Σ
(I
N211 x3
(A)
(12a)
1=1
= =K(AA)u Σ 1=1
(1-
Not1
e, K(X,,, A)
(12b)
Vx
V1.
= K(, - K(, X, E Dy Esj A)u
(12c)
where D2 = A Axt11A72
EigenPro 3. The primary limitation of EigenPro was its inability to handle cases where Z * X, a necessary condition for disentangling the model and the training set. EigenPro 3 overcomes this limitation by recognizing that although the gradients in (4) may not lie within Z, it is possible to project them back Z. Consequently, EigenPro can be summarized as follows:
fi-1 = proj (fe (i-np"(V,,LL)
(13)
where projz (w) = argmin ||u - 11 for any E H. As shown in Section 4.2 J. the exact fez
projection is, (u) = K(, Z)K (Z,
This projection can be interpreted as solving kernel in Z and can be approximated using EigenPro 2, as done in 11. with a time complexity that scales quadratically with model size. However, since this projection must be performed after each stochastic step, it becomes the most computationally expensive part of the EigenPro 3 algorithm.

---

EigenPro 4: Algorithm Design, Derivation, and Optimization
In this section, we provide high-level overview and illustrations to highlight the key components of EigenPro 4 and how it significantly reduces training time. We present the EigenPro 4 algorithm in three parts. First, we introduce the algorithm's main components: the pre-projection and projection steps. Then, we detail each of these steps in the following two subsections. Finally, we describe computational optimization that reduces the runtime of EigenPro 4 by half.
Scaling Challenge: High Projection Overhead. The key development of EigenPro 3 over its contemporaries was that could train general kernel models O(p) memory. This was huge improvement over the prior methods which required Opp") memory [20] [9]. However, EigenPro has a high cost (mp + p²) per batch of data processed, as summarized the table in Figure | This is especially expensive when m & i.e., when the batch size m is small compared to the model size p-
Main Idea: Delayed Projection. To address computational complexity challenges, EP4 amortizes projection costs by delaying them for iterations. An effective method for selecting T. along with an illustration of the delayed projection mechanism for T (Figure 4 is provided in Appendix B
In fact, EigenPro can be viewed special case of EigenPro 4 when the parameter T is Figure Appendix B iilustratess this relationship. Furthermore, as shown in equation (26) in the same appendix, the total training time is minimized when 7 proportional m the mini-batch size used in SGD, Under this setting, the per-batch training cost becomes O(p).
1.
22, where m denotes
3.1 Derivation of the EigenPro 4 Algorithm
As mentioned previously is crucial hyperparameter that determines the frequency of projection back to E after every 7' steps. Before the projection step T', at every step when new batch (X ym) fetched, is added to set defined as the "temporary centers" set, denoted by Zupp Starting with an empty set, Zemp 0. we continuously add temporary centers to Zemp until the step count reaches T.
Formally, the prediction functiin prior to the projection is no longer fixed and is now expanding, The model can be described as follows:
original model
temporary
f(x)
Σ ZEZ
Oz K(x,)))
Σ (2K(2,2)
(14)
ZEZemp
where ag refers to the weights corresponding to the original model center and B, refers to the weights corresponding the temporary model centers. The full EigenPro algorithm has been illustrated in Figure 2 and mathematically can be summarized as following.
projz (f--1 (
= mod T,
(15)
fi- 7/p5 (V
otherwise.
where L is stochastic gradient of the loss function computed mini-batch of data, and Pa is the preconditioner.
3.2 Steps before the Projection Step: Update for t < T
Based on Equation 115 suppose (X1, 91), ..., (XT, yT) are the minibatches of size m, and the initial model is fo = k-, Z)a. After < T step, the following holds,
ft = fi- KPP ())(:--)))) - -a) = fo 17P= (1)g:
= (X,)
Replacing Ps using equation [I]. setting fo = k(., Z)a, and following the notation introduced in
section let (A,, E. x denote the top-q cigensystem of (X,,.X)). where E =x and
Dg g
Ap11 Then, we can simplify the update above as follows:
ft = (() Σ
-(,x)))((,,..)) K(, K(X,,Xi) 9:
(16)
5

---

Training Starts
Sampled Mini-bstches
Batch
Batch kT
Batch kT
Batch kT
Iteration
Centers
Weights
Iteration
Batch kT 1
Centers
Update
Accumulate
gradient
Weights
Weights
Iteration
Batch kT +
Batch kT 2
Temporary Model defined (14) iteratiori kT includes temporary centers weights
Centers
Only update and accumulate- weights the
Accumulate gradiente
Weights
Weights
Weights
lteratio
kT T
Centers
Batch kT
Batcch kT
Batch
Batch
Accumulate
gradients
Weights
Weights
Weights
Weights
Weights
1)-th
Model after projection only contains centers & weights
Projection
Centers
Weights
Projection
See Eq (20)
Training
Centers Weights
Temporary Centers Weights
Improving Compulational Efficiency
(Model)
Figure 2: Schematic of the iterations in EigenPro4. 4. The figure illustrates how the model updates are performed over multiple iterations EigenPro4. Weights are updated using batches, and gradients accumulated iteratively until projection step is executed. This approach reduces the computational cost by accumulating gradients before performing the projection, leading to more efficient batch processing.
This update rule implies that after steps, the weights corresponding to the original centers Z remain unchanged, the weights for the temporary centers X; are set once to -g: after they are added, and do not change thereafter, and finally, the weights associated with the Nyström samples X, are n Ei_ E,D, K(X,, X2)9, which can be updated after each batch via additive update. This is how we update the weights before projection at step T'.
3.3 Projection Step: Update for /. -
Once, we reach step T we need to project fr into 2, or formally
fr = projz
- (f/'1-1pp'1 ((f-))))
(17)
= -projz frr- - [(,, (K( Xr)gr
-n((,,.)) K(X,, (x)g))
Applying Proposition from []]. the solution to this projection problem is as follows,
JT = K(, K(= (Z) - (2(2, (2, ,K( 1 K(X., XT)
(18)

---

Algorithm EigenPro4
Require: Data ()) centers Z, batch size m, Nyström size 8, preconditioner level y, projection
period T
1: Fetch subsample X, X of size
2: (Ag, Eq 1g+1) + top-g eigensystem of (X,,, XG) and define D, := (A Apt E
Rixq
3: while Stopping criterion is not reached do
4: Zemp <- 0. Otmmp &- 0, as +- O,, h +- Op
5: for -1,2...... ...,, 7 do
6: Ferch minibatch (X Um of m samples
7: 9m < (m Z) + K (XXm Ztmp atmmp K( ((X X,) ym
8:
(mm-aappend(Xmm and (tmp-append(-1) 9m)
9: a, a, +1 D ((X,; Xm.
10: h h K Xm)m K(Z, EE; K(X,,
Xm)9m
11: end for
12:
- proj(())
(Approximate projection implemented using EigenPro 2)
13:
end while
3.4 Improving Computational Efficiency
Upon careful examination of derivations in T6.. we observe that fr-1(2) have already been computed previously. This allows us efficiently reuse fr-1(Z) as follows,
(2) K(z, "
Σ
K(Z, X, K(X,,
(19)
plugging this
18 we obtain.
fr K(, 7) (cc nnK (2,
(20a)
T K(Z,X,)g K(Z, DE Σ K(X,,
(20b)
3.5 Final algorithm
The final EigenPro 4 can be found in Algorithm 1 Note that we follow the same inexact projection scheme used in [ to approximate the exact projection in the last step the algorithm.
The benefit of this approximation is that we don't 't need to solve the problem exactly in X, nor do we need to project back to after each iteration. This approach offers the best of both worlds. In the next section, we demonstrate the effectiveness of this approach compared to prior state-of-the-art methods.
3.6 Convergence Analysis
In Appendix A we provide convergence analysis for the special case of Algorithm [ where oo and exact projection is used in the projection step. However, more rigorous theoretical analysis that accounts for the approximations introduced for scability ccability-namell.. finite T and inexact projections- is left for future work and is beyond the scope of this paper.
4 Numerical experiments
In this section, demonstrate that approach achieves orders-of-man mfggaiiee speedups state- of-the-art kernel methods while maintaining comparable or superior generalization performance. We evaluate several kernel methods the following datasets: (1) CIFARSM, (2) CIFARSM [17)
(3) ImageNet
6 (4) Webvisior
[12] and (5) LibriSpeech [8] Dataset details are provided in
Appendix C
2 Feature extraction using MobileNetV2
Feature extraction using ResNet-18

---

ImageNet* (n 1.2M)
Librispeech (n=5M)
Webvision (n=2.5M)
900
Test accuracy
66
50
899
64-
185
40
62
157
10
20
30
40
50
12
20
15
20
25
30
35
cpochs
EP4: 512,000
EP4: 256,000
EP4: 128,000
EP4: 64,000
(method:model size)
EP3: 512,000
EP3: 256,000
EP3: 128,000
EP3: 64,000
Imagenet*
Time (minutes)
10000
67
accuracy
66
1000
66
100
10
6/k
128k
256k
512k
61k
128k
256k
512k
Model
Model
EP4 Accuracy
EP4 Time
EP3 Accuracy
EP3 Time
FALKON Accuracy
FALKON Time
Figure 3: (top) Multi-epoch performance, convergence comparison for EigenPro 3 and EigenPro 4. (bottom) Time and performance comparison for Falkon, EigenPro and EigenPro 4 for ImageNet. Details of the experiments and hardware can be found in Appendix C (Here refers to total number of training samples.)
While our method is compatible with any kernel function, we primarily use the Laplace kernel due to its simplicity and strong empirical performance. For completeness, we also report results using the Gaussian and NTK kernels in Appendix C.I.
For multi-class classification, we adopt a one-vs-all decomposition strategy, training a separate binary regressor for each class with targets in 0, 1. The final prediction is obtained by selecting the class corresponding to the highest predicted value across all binary regressors.
Substantial Reduction Per-Epoch Training Time. EigenPro 4 has substantially reduced the per-epoch training time, making it the most efficient kernel method on modern machine learning hardware. In contrast to performing projection every mini-batch iteration as in EigenPro 3, EigenPro schedules one projection every few iterations such that its amortized cost is comparable to that of the standard iterations. This results an ideal per-sample complexity Opp), a remarkable improvement over the O complexity from EigenPro 3.
In Table I we evaluate the performance and computational timing for a single epoch of our proposed model against established kernel regression methods. As noted earlier, Falkon exhibits limitations due to its quadratic memory complexity. For the CIFAR5M dataset, training with a model size of 512,000 required 1.3TB of RAM, while scaling 1M model size necessitated limited our Falkon benchmarks to model sizes of 128,000 and 64,000 for the remaining datasets. While EigenPro 3 addresses these memory constraints. it demonstrates significant computational overhead, particularly evident in the Librispeech dataset where our method, EigenPro 4, achieves 411x x speedup. Notably, EigenPro maintains comparable or superior performance across all evaluated datasets relative to both bascline methods.
5TB. Resource constraints
Linear Scaling with Model Size. The total training time and memory usage of EigenPro 4 scales linearly with model size. In comparison, the time required for single EigenPro iteration grows quadratically with the model size, while the preprocessing time for Falkon grows cubically, Furthermore, the memory demand of Falkon increases quadratically with the model size. In practice, are unable to it with large model sizes, e.g., 128,000 centers for ImageNet data.

---

Model size
Method
(1 5M)
CIFARSM
Librispeech 10M)
Webvision (n 5.2M)
EigenPro
5m (4.6x, 88%)
3m (15x, 69%)
16m (9.1x, 86.8%)
2m (45.5x, 24.3%)
p= 64K
EigenPro
23m (Ix, 88.3%)
45m (Ix, 68.8%)
145m (Ix, 85.4%)
91m (Ix, 24%)
Falkon
3m (7.67x, 86.1%)
5m (9x, 57.7%)
9m (16.11x. 81.0%)
4m (22.75x, 21.7%)
EigenPro
5m (10x, 88.25%)
4m (26.25x, 70.9%)
19m (17.95x, 87.8%)
4m (49.75x, 24.9%)
p= 128K
EigenPro
50m (Ix, 88.42%)
105m (Ix. 70.3%)
341m (Ix, 84.75%)
199m (Ix, 24.5%)
Falkon
9m (5.56x, 86.55%)
Ilm (9.55x, 59.4%)
21m (16,24x, 82.30%)
13m (15.3lx, 22.4%)
EigenPro
(18.3x, %%)
(130.8x, 7188%)
24m (120x, 88.33%)
(106.2x, 26%)
p= 256K
EigenPro
128m (1x, 88.61 %))
785m (1x, 70.53%)
R: days (1x)
531m (1x, 25.52%)
Falkon
38m (3.37s, 86.7.5%)
0OM
0OM
00M
EigenPro
12m (44.25x, 88.58%
10m 288x, 72.9%)
36m 200x, 88.89%
11m (240x. 27.3%)
p= 512K
EigenPro
531m (Ix. 88,56%)
days (Ix)
> days (Ix)
days (Ix)
Falkon
240m (2.21x. 86.71%)
0OM
OOM
00M
EigenPro
2lm (>> 274x, 88.7%)
17m 508x, 73.8%)
70m (>> 411x, 89.5%)
21m (> 686x, 29.3%)
p=
EigenPro
> days (1x)
> days (1x)
2-20 days (1x)
>> days (1x)
Falkon
OOM
OOM
OOM
OOM
Table 1: Runtime (in minutes) comparison of EigenPro 4, EigenPro and Falkon across different model sizes and datasets after 1 epoch. The values in parentheses represent the speedup over EigenPro and the final accuracy. OOM indicates an Out-of-Memory error. Details of the experiments and hardware can be found in Appendix C
We summarize all empirical results in Figure 3 and demonstrate that our method achieves both linear memory complexity and linear time complexity (empirically verified) with respect to model size, offering the best of both worlds. For the ImageNet dataset, we trained all methods until convergence. While EigenPro 3 does not have the quadratic memory scaling problem, Figure 3 shows that even for relatively small dataset like ImageNet with 1M data points, training model size of 512,000 centers requires approximately 43 days on a single GPU to reach convergence (about 100 epochs). In contrast, our proposed model achieves convergence in approximately hours, requiring only 15 epochs, with each epoch being significantly more efficient than EigenPro 3 (see Table
Faster Convergence with EigenPro 4. EigenPro 4 generally demonstrates the fastest convergence among all tested methods. In certain cases, such as ImageNet with 1.2 million model centers, Eigen- 4ro4 converges in less than 10% of the epochs needed by other methods, while also delivering superior model performance. Figure compares EigenPro and EigenPro 3 across multiple train- ing epochs, following the experimental setup established in [I. Despite EigenPro 4's linear time complexity per iteration (compared to EigenPro 3's quadratic complexity), it demonstrates faster convergence with fewer epochs. This efficiency gain is particularly pronounced for larger model sizes, where EigenPro 4 maintains or exceeds EigenPro 3's accuracy while requiring significantly fewer epochs. These results empirically validate that FigenPro 4's algorithmic improvements translate to practical benefits: not only does each iteration run faster, but fewer iterations are needed to achieve optimal performance across diverse datasets. This empirically shows that our model has linear time complexity with respect to the model size.
5 Conclusion
In this work, we introduced EigenPro 4, an advancement in training large kernel models that achieves linear time complexity per iteration and linear memory scaling with model size. By implementing a delayed projection strategy, we addressed the high computational overhead previously associated with frequent projections, achieving significant time and memory efficiency improvements over EigenPro 3 and Falkon. Our empirical results on diverse datasets highlight EigenPro 4 ability to match or exceed the performance of prior methods with vastly reduced computational resources. Specifically, the algorithm demonstrates both faster convergence and superior scalability, enabling training with model sizes and datasets that were previously infeasible due to memory and time constraints.
Furthermore, EigenPro design opens up new possibilities for parallelization, as it is well-suited for multi-GPU and distributed architectures. Future work will explore these aspects, further expanding its potential in real-world applications requiring efficient, scalable kernel methods for massive data volumes.

---

Acknowledgements: We acknowledge support from the National Science Foundation (NSF) and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-2031 883 and #81 14339, the TILOS institute (NSF CCF-21 12665), and the Office of Naval Research (88644-N-ONRR). This work used ACCESS (Advanced cyberinfrastructure coordination ecosystem: services & support) which is supported by NSF grants numbers #2138259, #2138286, #2138307, #2137603, and 138296. Specifically, we used the resources from SDSC Expanse GPU compute nodes, and NCSA Delta system, via allocations TG-CIS220009, This work was done part while AA was visiting the Simons Institute for the Theory of Computing. PP was supported by the DST INSPIRE Faculty Fellowship, Schmidt Sciences, and gifts from SBI and Amazon.
References
[1] Amirhesam Abedsoltan, Mikhail Belkin, and Parthe Pandit. Toward large kernel models. In Proceedings of the 40th International Conference Machine Learning, ICML'23, JMLR.org. 2023.
[2] Amirhesam Abedsoltan, Parthe Pandit, Luis Rademacher, and Mikhail Belkin. On the nyström approximation for preconditioning in kernel machines. In International Conference on Artificial Intelligence and Statistics, pages 3718-3722 PMLR, 2024.
[3] 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,
2019.
[4] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to understand kernel learning. In International Conference on Machine Learning, pages 541-549. PMLR, 2018.
[5] Raffaello Camoriano, Tomás Angles, Alessandro Rudi, and Lorenzo Rosasco. Nytro: When subsampling meets early stopping. In Artificial Intelligence and Statistics, pages 1403-1411. PMLR, 2016.
[6] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image datahase. In 2009 IEEE conference on computer vision and pattern recognition, pages
leee, 2009.
[7] Jacob Gardner, Gcoff Pleiss, Ruihan Wu, Kilian Weinberger, and Andrew Wilson. Product kemnel interpolation for scalable gaussian processes. In International Conference Artificial Intelligence and Statistics, pages 1407-1416. PMLR, 2018.
[8] 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.
[9] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[10] Dan Jurafsky. Speech & language processing. Pearson Education India, 2000.
[11] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. Citeseer, 2009.
[12] 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.02888 2017.
[13] Siyuan Ma and Mikhail Belkin. Diving into the shallows: computational perspective on large-scale shallow learning. Advances in neural information processing systems, 30, 2017.
[14] Siyuan Ma and Mikhail Belkin. Kernel machines that adapt to gpus for effective large batch training. Proceedings of Machine Learning and Systems, 1:360-373, 2019.
10

---

[15] Alexander G. de G. Matthews, Mark van der Wilk, Tom Nickson, Keisuke. Fujüi, Alexis Boukouvalas, Pablo León- Villaga,, Zoubin Ghahramani, and James Hensman. GPflow: A Gaussian process library using TensorFlow. Journal of Machine Learning Research, 18(40): apr 2017.
[16] 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, 53:14410-14422, 2020.
[17] Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners good offline generalizers. International Conference Learning Representations, 2021.
[18] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an ast corpus based on public domain audio books. In 2015 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 5206-5210. IEEE, 2015.
[19] Pratik Rathore, Zachary Frangella, Jiaming Yang, Michal Derezinski, and Madeleine Udell. Have askotch: A neat solution for large-scale kernel ridge regression. arXiv preprint 17X1::2407.10070, 2025.
[20] Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. Falkon: An optimal large scale kernel method. Advances in neural information processing systems, 30, 2017.
[21] 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.
[22] Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial intelligence and statisties, pages 567-574. PMIR, 2009.
[23] Towns, T. Cockerill, M. Dahan, Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. Scott, and N. Wilkins-Diehh Xsede: Accelerating scientific discovery. Computing in Science Engineering, 16(05):62- 74, sep 2014.
[24] Shinji Watanabe, Takaaki Hori, Shigeki Karita, Tomoki Hayashi, Jiro Nishitoba, Yuya Unno, Nelson Enrique Yalta Soplin, Jahn Heymann, Matthew Wiesner, Nanxin Chen, Adithya Ren- duchintala, and Tsubasa Ochiai. ESPnet: End-to-end speech processing toolkit. In Proceedings of Interspeech, pages 2207-2211, 2018.
[25] Ross Wightman. Pytorch image models.
Cttts:///gttaab..ommrrrggg.a
pytorch- models 2019.
[26] Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. Advances in neural information processing systems, 13, 2000.
[27] Andrew Wilson and Hannes Nickisch. Kernel interpolation for scalable structured gaussian processes (kiss-gp). In International conference machine learning, pages 1775-1784. PMLR. 2015.
[28) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We demonstrate the efficiency of our method across multiple datasets and scales: Figures 1 and 2 illustrate performance trends, and Table I provides extensive quantitative evaluation, showing speedups of up to x600.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide a theoretical convergence analysis for the exact version of our method in Appendix [ The full algorithm is based on efficient approximation of this exact version. Although formal theoretical analysis the approximation is not included, validate its effectiveness extensively through experiments on diverse datasets and scales. Establishing complete theoretical understanding of the approximation involves nontrivial technical challenges, which consider an important direction for future work beyond the scope of this paper. We addressed the limitation in 3.6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model -ell-specification. asymptotic approxinations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
12

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The theoretical result presented in Appendix A where we include all necessary assumptions and provide complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all necessary details for reproducing experiments in Ap- pendix C
We will release our GitHub repository upon acceptance and have also included a .zip file version of the code in supplementary for the review process.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (c.g., g., in the case
13

---

of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use publicly available datasets and provide all necessary details for re- producing our experiments Appendix C The code for our algorithm is included in the supplemental material for review process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/ public/guide
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //spps.cc/pullccgiiddss.
http://oooSSSiiiiiee www.oeeewsssissisooooooosleooeee for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
14

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We provide all thethe necessary details for reproducing our experiments in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our experimental setup ensures stability and reproducibility by using the same training/test splits, center selections, and random seeds across all methods. As typical in kernel methods, there is no randomness from model or weight initialization, and the only minor source of stochasticity arises from optimization, which is consistently controlled. Because all methods are evaluated under identical conditions, traditional error bars would not provide meaningful additional information. We validate the effectiveness and robustness of our method through extensive experiments a wide range of datasets, consistently demonstrating significant speedups with comparable or better performance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
15

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We provide all necessary details in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well as estimate the total compute.
The paper should disclose whether the research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https atttpa://neurigge http:///neuiipp.ee httpp////..tttaaiiiieeee......e.
Answer: [Yes]
Justification:
We followed the NeulPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We believe there is no immediate societal impact, either positive or negative, this work focuses foundational algorithmic improvements kernel methods. The contributions are methodological in nature and not tied to any specific application domain deployment scenario. As such, we mark this question not applicable.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles. surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out
16

---

that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
This work does not involve the release of pretrained models, generative systems, scraped datasets that pose a high risk of misuse. Therefore, no specific safeguards are necessary, and we mark this question as not applicable.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: To the best of our knowledge, all datasets and codebases used in this work have been properly cited and used in accordance with their licenses and terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce new code implementing our algorithm, which we include as .zip file in the supplemental material for the review process. The code is documented with instructions for reproduction and GitHub repository will be released publicly upon acceptance.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve any crowdsourcing or research with human subjects, so this question is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
This work does not involve any research with human subjects, and therefore no IRB or equivalent approval was necessary.
Guidelines:
18

---

The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
This work does not involve the use of large language models as an important, original, or non-star standtadddrd component of the core methodology. Any of language models was limited to minor writing assistance and does not impact the scientific contribution the paper.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM httpps////eurige.ccc///ofrrrrreo for what should or should not be described.
19

---

A Convergence analysis
In this section, we derive EigenPro4.0-Exen (Algorithm(2) 2), precursor to EigenPro4.0. However, this version does not scale efficiintly. In Section 3 enhance its scalability by introducing stochastic approximations, resulting in EigenPro4.0 (Algorithm D.
Recall that the derivatives of the loss function, as defined in (3). lie in the span of the training data, denoted X. However, these derivatives cannot directly update the model, which resides in the span of the model centers, 2. To address this, we first fit the labels within the X and then project the solution into the This process is repeated iteratively on the residual labels until convergence, as outlined in Algorithm algorithm]
Algorithm 2 EigenPro4-Exxan 4-Exact
Require: Data (X, y). centers
1: Do y
2: for = 1,2,... do
3: az K-1 (X-1(XX)ūt
4: K(,, 1), projz (K(,X))ar)
5: Øt+1 y (XX,
6: end for
The following proposition provides the fixed point analysis for this algorithm.
Proposition 1. Consider any dataset X. y and a choice of model centers Z, with kernel function K Rd x Rd - TR. Assume that K ((X,X, X) and K(Z, X) are full Rank. Then, Algorithm converges the following solution:
Í= K(, (K(Z, (X Z)) X(Z,X)K-(XX,X))
(21)
Furthermore, y K(X, 2) E., where is vector of independent centered random noise with BKG 0², then
B - 1
lim [[S = 3 1-000
lim
10000
g²
tr (X
22 (X
Proof. We begin by expressing Algorithm recursively and substituting proj with the expression in (18) Recall that f. K(-, Z)B; with base case Bu = 0. The update rule for Be is given by:
B = K (2, (Z, (X, -XX
B
(22)
Let us define the matrices:
B = B K K (2, (), C: BK(X,
which allows to rewrite the recursion more succinetly:
B. Bly K(X, 2)3 9
By CB:-1 By -CBy + C
(23)
= Σ (-))c*))) By.
As the number of iterations tends infinity, we can define the infinite series sum:
= Σ IIIC..
1=0
20

---

Observe that:
C+CS=I.
Substituting the definition C (X) and B =
(2, XX,
have:
K (4, =1
Thus, this simplifies to:
s (XX22))) K(Z,Z).
Therefore, the final solution converges to:
f f= (K(, (K2, K(Z,X))
(24)
Substituting y (XX, 3) + readily completes the second claim.
21

---

line in Algorithm
computation
flops
K( ((Xm Z) - yt
mp
K K(X,, m: Zamp ampp
m² kT
K (Xm Xa)
ms
10
h1 == K(Xs: Xm)gm E R
ms + 89
Fh
sq
K K Xm)X)m
mp
Mh
pq
Table Computational cost analysis of Algorithm for processing batch for KT < (k + 1)T
for some & E N. The cost of processing batch / without the post-processing adds up to 2mp + 2ms + 2sg + pd m² m²(t kT flops.
B Computational complexity comparison
We assume that EigenPro4 is processing T batches of data at once before running the post-processing step of projection. Here we show we calculated the optimal value of T.
Cost for processing ęth batch of data. For some k E KT <ts (k: + 1)T. See Table
2
Cost of processing T batches of data before post-processing The total cost for processing T batches kT to (k 1)T before the projection is the sum the above
(6++1T
(T- - 1) = T(2mp + 2ms + 28q + pq) + m² T(T - 1)
T(2mp + 2ms + 2sq + pq) + m
Σ
2
(25)
Average of processing T batches of data with post-processing Assuming the post processing involves Tep2 epochs of EigenPro 2, the average cost of processing T batches is
T(2mp 2ms + 2sq - pq) + m T(T 1) + +p² pTppp
(26)
simple calculation shows that
T
v 2Tep2
(27)
m
minimizes the average time above. The average cost of processing a batch is thus
2mp(1 + 22T + 2ms + 28q + pq
(28)
Illustration for delayed projection for T
Time|
2
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Algorithm
EigenPro3
B1
B2
B3
B4
EigenPro4
B1
B2
B3
B4
Process batch of data
Projection (post-processing)
Figure 4: Design of EigenPro4. An illustration of how batches of data are processed by the two algorithms. EigenPro3 involves an expensive projection step when processing every batch of data. EigenPro4 waits for multiple batches be processed before running the projection step for all of them together. This reduces the amortized cost for processing each batch.
Comparison between EigenPro 4 and EigenPro 3. Figure 5 shows how FigenPro and FigenPro perform over training iterations. EigenPro 4 accuracy improves between projections and drops after
22

---

each projection step. While EigenPro 3 projects at every step, EigenPro maintains comparable accuracy with fewer projections. The left panel of Figure that both methods reach similar final accuracy, while the right panel shows EigenPro 4 significant speed advantage. With continued training, EigenPro accuracy drops from projections become progressively smaller.
25
200
Test accuracy(%
20
Minutes
EigenPro Pro 4
100
15
EigenPro 3
Eigen Pro 4 projection step
10
0
100
200
300 Steps
400
500
600
10
20
Epoch
Figure 5: Performance and computational time comparison between EigenPro 4.0 (T 11) and EigenPro 3.0 (equivalent to T = 1). highlighting the impact of the projection step the performance of EigenPro 4.0. The detail the experiment can be found in Appendix
FLOPS
Algorithm
Memory
setup
per batch"
EigenPro 4.0
/ 2T op2 2mp + p² Tpp 2ms + 2sq + pq
2mp(1
2ms 28q pq
82 + p(1 + 2TTpp)
EigenPro 3.0
((sag)
s² + D
Falkon (pp))
2mp
pd
Table 3: Comparing complexity of algorithms. Number of training samples number of model
centers p, batch size m, Nyström sub-sample size s, preconditioner level q. Here we assumed only constant number of epochs of EigenPro 2.0 is needed for large scale experiments. Cost of kernel
evaluations and number of classes are assumed to be (11), also is reasonable to assume >> 8 > q. FLOPS per iteration reported are amortized over multiple batches processed.
23

---

Experiments Results
C.1
Other kernels
For consistency with prior work, we primarily used the Laplace kernel, which offers efficient per- batch computation and scales linearly with total training time- time-making it feasible to train methods such as EigenPro 3.0 larger scales. For completeness, we also report results using alternative kernels: Gaussian (bandwidth 20) and NTK (ReLU MLP, depth 2), evaluated on the same CIFARSM embeddings as in Figure
Table 4: Comparison of kernel types and number of centers.
Kernel Type
64k Centers
128k Centers
256k Centers
Gaussian
87.77% (178s)
87.80% (194s)
88. 14% (233s)
NTK
87.01% (206s)
87.34% (309s)
87.54% (564s)
C.2 Computational resources used
This work used the Extreme Science and Engineering Discovery Environment (XSEDE) 23 We used machines with NVIDIA-V -100, NVIDIA-A and NVIDIA-A40 GPUs, with a V-RAM up to 1.3 T, and 8x cores of Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz with RAM of 100 GB. NOte that we had 1.3T of RAM for just one experiment CIFARSM", for the rest of expermients we where constraint with 400G of RAM.
C.3 Datasets
We perform experiments on these datasets: (I) CIFARIO, M. (2) CIFARSM, 17,, (3) ImageNet, (4) Webvision. [1], and (5) librispeech.
CIFAR5M. In our experiments, we utilized both raw and embedded features from the CIFARSM data-set. The embedded features were extracted using a MobileNetv2 model pre-trained on the ImageNet data-set, obtained from timun library 25 We indicate in our results when pre-trained features were used by adding an asterisk (*) to the corresponding entries.
ImageNet. our experiments, we utilized embedded features from the ImageNet data-set. The embedded features were extracted using MobileNetv2 model pre-trained the ImageNet dataset, obtained from timm library [25]. We indicate in our results when pre-trained features were used by adding asterisk (+) to the corresponding entries.
Webvision. In our experiments, we utilized embedded features from the Webvision data-set. The embedded features were extracted using a ResNet- 18 model pre-trained on the ImageNet dataset, obtained from timm library 225.. Webvision data set contains 16M images in 5K classes. However, we used only a subset of for different experiments.
Important note about Webvision dataset. In the experiments shown in Figure 3 to ensure computational feasibility for running EigenPro 3.0, used only data with labels smaller than 500, corresponding to roughly 2.5 million data points. In contrast, the results in Table I were obtained using labels up 1000, encompassing about 5.2 million data points. Since this larger label range represents a more challenging classification problem, the test accuracy in Figure is higher than in Table
Librispecch. Librispeech 18 is a large-scale (1000 hours in total) corpus of 16 kHz English speech derived from audio books. We choose the subset train-clean- 100 and train-clean-300 (5M samples) our training data, test-clean as test set. The features are got by passing through well-trained acoustic model (a VGG+BLSTM architecture in (8) ) to align the length audio and text. It is doing 301-wise classification task where different class represents different uni-gram [00]
The implementation of extracting features is based on the ESPnet toolkit 24
C.4 Experiments details
F This experiment used CIFARSM' data set, where embedding has been generated using a pre-trained mo network mentioned earlier. this is the only experiment that we had access to 1.3T of VRAM. We set the bandwidth to 5.0 and use 1 Nystrom samples with preconditioning level of size 100. We used 1 for this experiment.
24

---

Figure 5
This experiment has been run over Webvision data set with extracted embedding through Resnet 18 the model size here is set 100k number of centers. The bandwidth used is 5.0, 1k: Nystrom samples with preconditioning level of size 100. We used float16 for this experiment.
Figure We follow the setting in T The bandwith used here 20 for Librispeach and Webvision and 16 for imagnet. Here again used extracted feature of these datasets mentioned earlier. The precision used here is float32. with 10k Nystrom samples with preconditioning level of size 1000.
Table For all datasets here we used bandwidth of 5.0 with 1k Nystrom samples with precondition- ing level of size 100. We used float16 for all dataset except for Librispeach where we used float32. Further, we note that Falkonlatest library ran out of GPU memory for model sizes larger than 256000 number of centers that is the reason we could not run it for 256000. And mentioned for model sizes 521000 and above the algorithm has inherent quadratic scaling with respect to model size and we ran out of VRAM. In the plot we refer to both of these memry issues OOM.
25


Reviews:
[{"review_id": "xmLIjZvHa5", "reviewer": "Reviewer_qGfb", "summary": "The authors propose a new method for solving kernel regression via gradient\ndescent. Their method, EigenPro 4, is based heavily upon EigenPro 3. The paper\nidentifies the 'projection step' as a major bottleneck in EigenPro 3, and solve\nthis issue by amortization: instead of projecting every step, they accumulate 'temporary centres'\nand project them every T steps. This modification leads to massive speedups vs.\nEigenPro 3, and (perhaps surprisingly) also improves performance. The speedups\nare especially significant, as this unlocks the ability to use kernel regression\nfor larger datasets than previously practicable.", "questions": "- Why do we get such a noticable accuracy/performance boost for EP4 over EP3 in\n  Figure 3, when the only difference between the two is the amortization of the\n  projection? Can you comment on whether the amortization might improve\n  properties of the optimization?\n- Figure 5 shows that performance degrades after the projection step. Are you\n  able to explain this behaviour?\n- Can you provide any preliminary experiments with other kernels (i.e. not just\n  the Laplace kernel)? You mentioned that Laplace has strong empirical\n  performance, but compared to what baseline?\n- Is it possible to perform 'deep kernel' experiments? I.e. to stack several\n  kernel regressors together, and train them jointly with EP4?", "limitations": "The authors discuss theoretical limitations of their algorithm in Section 3.6. However, I would like to see a discussion of practical elements too, such as where EP4 is limited versus other methods (e.g. NNs). For example, as far as I know, EP4 is relying on good underlying representations as input to be useful in practice.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- Authors give a clear and concise exposition of kernel regression and of existing algorithms.\n- Experimental results very clearly show that EP4 is significantly faster and\n  more practical than kernel regressor alternatives.\n\nOverall EP4 is obviously very helpful for any practitioners using kernel regression / EP3.\n\nWeaknesses:\n\n- Experiments/Datasets are a bit artificial. For example, the kernel method uses\n  features extracted from a ResNet/MobileNetV2.\n- It's unclear how the proposed methods performs vs. a NN. Even if the NN is\n  more performant, this still seems relevant to include, considering that the\n  underlying features of all experiments are extracted from a NN.\n- Some experimental details are missing in the main text; for example, basic information like what value\n  of T is used?\n- The paper's results suggest that EP4 is strictly better (in terms of accuracy/loss) than EP3, but more\n  results using further kernels/datasets (only 1 kernel and 4 dataset were used)\n  would be helpful to confirm this.\n- The paper does not explain why EigenPro 4 is better than EigenPro 3, which is\n  an interesting quirk. I would like to see a discussion on why accumulating the temporary centres appears to help.\n\n\nMinor issues:\n\n- Algorithm 1 describes computational details of EigenPro 4. It would be nice to\n  have a 'diff' with EigenPro 3 to clarify the computational differences.\n- In Eq. (1) L is defined differently to L in line 78. Make these consistent.\n- Line 81, 'Operator K' -> 'The Operator K'\n- The meaning of * in line 193 (and elsewhere). Please include this,\n  possibly as a footnote, in the main text.", "was_revised": true, "final_justification": "In my original review, I was concerned about issues such as performance degrading when centres are consolidated, lack of results for different kernels, lack of comparison to neural networks. These have been addressed, except the comparison to NNs, but upon seeing the authors' justification for this, I think it is reasonable for it to be excluded.\n\nI am happy to raise my score, as I think the paper is a solid contribution to kernel methods, and my issues have been resolved.", "rebuttal": "We thank the reviewer for their feedback. We address the concerns one by one as follows:\n\n>Experiments/Datasets are a bit artificial. For example, the kernel method uses features extracted from a ResNet/MobileNetV2. \nAnd \n> It's unclear how the proposed method performs vs. a NN. Even if the NN is more performant, this still seems relevant to include, considering that the underlying features of all experiments are extracted from a NN.\n\nThe primary focus of our paper is on the computational complexity of kernel methods, rather than on comparing their predictive performance to that of neural networks. Kernel methods continue to play an important role in understanding modern learning phenomena such as feature learning, a topic that has received renewed interest. Furthermore there are recently developed high-performing variants of kernel methods such as Recursive Feature Machines (RFM) recently published in Science [1]. We will revise the paper to include a more detailed motivation for the relevance and significance of studying kernel models in this context.\nWe followed prior works in using datasets with features extracted from pretrained networks (e.g., ResNet, MobileNetV2 or VGG+BLSTM for librispeech) to enable fair and consistent comparisons with prior works. In addition, we also include results on raw image inputs from CIFAR-5M, which demonstrates that our method is not limited to feature-extracted datasets.\n\n[1] Radhakrishnan, A., Beaglehole, D., Pandit, P., & Belkin, M.\n Mechanism for feature learning in neural networks and backpropagation-free machine learning models.\n Science, 383(6690), 1461–1467, 2024.\n\n>Some experimental details are missing in the main text; for example, basic information like what value of $T$ is used?\n\nWe provide a detailed discussion on how to choose $T$ in Appendix Section B, where we explain that it should scale as \\$ \\mathcal{O}(\\frac{p}{m}) $, with $p$ denoting the model size and $m$ the batch size. In all experiments, we set $ T = 2 \\times \\frac{p}{m} $. We will clarify this choice further  in Appendix Section C in the final version.\n\n>The paper's results suggest that EP4 is strictly better (in terms of accuracy/loss) than EP3, but more results using further kernels/datasets (only 1 kernel and 4 dataset were used) would be helpful to confirm this.\n\n…\n>The paper does not explain why EigenPro 4 is better than EigenPro 3, which is an interesting quirk. I would like to see a discussion on why accumulating the temporary centres appears to help.\n\n…\n>Why do we get such a noticeable accuracy/performance boost for EP4 over EP3 in Figure 3, when the only difference between the two is the amortization of the projection? Can you comment on whether the amortization might improve properties of the optimization?\n\nWe would like to clarify that EigenPro 4 and EigenPro 3 converge to potentially different solutions. From a generalization standpoint (accuracy/loss), it is not possible to claim that one is strictly better than the other – it depends on the specifics of the dataset and the problem setting. Our primary goal in this paper is to demonstrate that EigenPro 4 offers substantial speed improvements without sacrificing generalization. The observed performance boost is not the main focus, but it does indicate that the speedup does not come at the cost of degraded accuracy.\n\nAs for the role of amortization and temporary centers: accumulating temporary centers between projections allows the model to explore a richer hypothesis space during intermediate steps. While the model eventually projects back to the original set of centers, these intermediate updates may help guide optimization toward better regions of the parameter space. A deeper theoretical understanding of this effect is an interesting direction for future work, and beyond the scope of the current paper.\n\nAbout the kernel:\nWe chose the Laplace kernel primarily for consistency with prior work and because its per-batch computation is highly efficient. Specifically, the total training time scales linearly with the per-batch kernel computation time, which makes it feasible to explore more computationally intensive methods like EP3.0—particularly for larger model sizes. For completeness, we will include results using the NTK kernel in the final version of the paper. \n\nResults using alternative kernels: Gaussian (with bandwidth 20) and NTK (ReLU MLP with depth 2), evaluated on the same extracted embeddings from the CIFAR5M dataset as used in the main paper.\n| Kernel Type | 64k Centers       | 128k Centers      | 256k Centers      |\n|-------------|-------------------|-------------------|-------------------|\n| Gaussian    | 87.77% (178s)     | 87.80% (194s)     | 88.14% (233s)     |\n| NTK         | 87.01% (206s)     | 87.34% (309s)     | 87.54% (564s)     |\n\n\n\n>Figure 5 shows that performance degrades after the projection step. Are you able to explain this behaviour?\n\nIn the EP4 algorithm, the model expands between projections by incorporating temporary centers—it is not a fixed model during this phase. After each projection step, the model reverts to its original form with a fixed set of centers. This explains the accuracy drop observed after each projection step in Figure 5: the temporary expansion improves accuracy, but once the projection is applied, the model returns to its constrained representation."}, {"review_id": "aUJHppA5h3", "reviewer": "Reviewer_TF8r", "summary": "Previous kernel-based methods have difficulties with scaling to larger model sizes due to the computational cost of projecting gradients into the kernel feature space after every iteration. The authors propose EigenPro 4, which improves upon EigenPro 3, by delaying this projection by T iterations, which reduces the per iteration cost while maintaining performance. This approach also allows the model to be approximately linear on average per epoch in terms of per iteration computations while having linear memory scaling.", "questions": "The motivation needs improvement a lot, such as why to choose a kernel-based method over a non-kernel based method (e.g. deep learning models)?\n \nIn equation 15, the otherwise branch calculates the stochastic gradient using $f_t$, but should it not be on $f_{t-1}$?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper presents a practical contribution to kernel methods which would help allow them to be used in more large scaled environments due to the linear amortized per-iteration cost. They also show impressive performance improvements over EigenPro 3 and Falkon in terms of running time. However, the paper itself, especially the beginning sections, are not the most organized nor standalone. There is little contextualization in the beginning, and no clear reason as to why one would want to use kernel methods even with linear amortized per iteration cost and linear memory scaling. Although, the contributions could be significant, the paper does a poor job phrasing its importance with respect to other non-kernel methods. There are also some things missing that would make for a comphrensive evaluation, such as using more kernels in the addition to the laplace kernel or abalations on the value of $T$. Although, $T$ is proportional to $p/m$, no exact value used is provided for the experiments and testing different values for $T$ would be informative.", "was_revised": true, "final_justification": "The rebuttal addressed my concerns, and I'd love to raise my score.", "rebuttal": "We thank the reviewer for their feedback. We address the concerns one by one as follows:\n\n>Although the contributions could be significant, the paper does a poor job phrasing its importance with respect to other non-kernel methods.\n\nOur paper is specifically focused on the computational complexity of kernel models, rather than their performance in comparison to non-kernel methods. Kernel methods play a crucial role in understanding modern learning phenomena such as feature learning – an area that has gained renewed attention, including highly performant variants of kernel machines which recently appeared in Science [1]. We will revise the paper to include a clearer and more detailed motivation for studying kernel models and their relevance.\n[1] Radhakrishnan, A., Beaglehole, D., Pandit, P., & Belkin, M.\n Mechanism for feature learning in neural networks and backpropagation-free machine learning models.\n Science, 383(6690), 1461–1467, 2024\n\n\n >There are also some things missing that would make for a comprehensive evaluation, such as using more kernels in the addition to the laplace kernel or ablations on the value of .\n\nWe chose the Laplace kernel primarily for consistency with prior work and because its per-batch computation is highly efficient. Specifically, the total training time scales linearly with the per-batch kernel computation time, which makes it feasible to explore more computationally intensive methods like EP3.0—particularly for larger model sizes. For completeness, we will include results with the NTK kernel in the final version for EP4.0.\n\nSome results using alternative kernels: Gaussian (with bandwidth 20) and NTK (ReLU MLP with depth 2), evaluated on the same extracted embeddings from the CIFAR5M dataset as used in the main paper.\n| Kernel Type | 64k Centers       | 128k Centers      | 256k Centers      |\n|-------------|-------------------|-------------------|-------------------|\n| Gaussian    | 87.77% (178s)     | 87.80% (194s)     | 88.14% (233s)     |\n| NTK         | 87.01% (206s)     | 87.34% (309s)     | 87.54% (564s)     |\n\n>In equation 15, the otherwise branch calculates the stochastic gradient using , but should it not be on ?\n\nCould you please clarify your question regarding Equation 15? It seems the sentence was cut off, and the specific expressions you're referring to are missing. We're happy to address the concern once we have the full context."}, {"review_id": "Avxn8khbEl", "reviewer": "Reviewer_CFJP", "summary": "This work (EigenPro 4) proposes Delayed Projection, instead of projection after each gradient descent step, to address high time cost per batch of EigenPro 3. Convergence and time complexity analysis are given. Experiments show the great reduction in per-epoch training time and good scalability w.r.t. model size.", "questions": "See Weakness.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe motivation of delayed projection is clear and easy to understand.\n\n2.\tThe analysis of convergence and time complexity is thorough and sound.\n\n3.\tThe experiment results demonstrate that the proposed method is practical on very large datasets . Compared with EigenPro 3, the time reduction does not cause severe test accuracy drop.\n\nWeaknesses:\n\n1.\tIn terms of effectiveness, EigenPro 4 performs inconsistently across different model sizes: it is strange to observe that although EigenPro 4 is more efficient than EigenPro 3, the accuracy of EigendPro 4 is lower (higher) than EigenPro 3 when the model size is small (large). Is there any particular reason behind this? \n\n2.\tAlthough EigenPro 4 is faster than EigenPro 3 and converges faster. The results in Figure 5 indicate the convergence process of EigenPro 4 is more unstable than EigenPro 3 due to delayed projection, especially in Webvision dataset. Is this because EigenPro 4 accuracy improves between projections and drops after each projection step as shown in Figure 5? \n\n3.\tAs claimed in line 727, the EigenPro 4 accuracy drops from projections become progressively smaller. However, in the Webvision and Librispeech results in Figure 5, the multiple accuracy drops remain relatively large when EigenPro 4 converges. Is there any specific reason behind this occurrence that warrants further exploration on the stability of EigenPro 4? Adding an analysis on this issue would be nice.", "was_revised": true, "final_justification": "The recommended score of 4 is maintained. While the work demonstrates strong technical merit and the authors have effectively addressed all the concerns during the rebuttal, a slight lack of novelty leads to this nuanced recommendation.\n\nThe motivation for delayed projection is clear and intuitive, directly addressing the high per-batch time cost of EigenPro 3. The experiments results are convincing and demonstrate the reduced per-epoch training time and good scalability with respect to model size. And the time reduction does not cause severe test accuracy drop.\n\nDuring the rebuttal, the authors addressed all my concerns. They clarified the relation between model size and EigenPro 4’s performance, and explained the reason of accuracy change in the convergence process. My misinterpretation of accuracy drops is addressed with clear explanation.\n\nThe only mitigating factor is a slight lack of novelty in the core \"delayed projection\" mechanism. The concept of delaying projections, as a strategy to balance efficiency and performance, is built upon existing projection-based optimization paradigms rather than introducing a paradigm-shifting innovation. This is not a flaw, but a subtle limitation that prevents a stronger recommendation.\n\nI would assign most of my weight on the work’s clear motivation, sound theoretical analysis and convincing experiments. I would assign little weight on the slight lack of novelty. The borderline accept recommendation comes not from weaknesses, but from a subtle lack of novelty. However, this should not reduce the significance of the authors’ contribution. The proposed method meaningfully advances EigenPro’s efficiency.", "rebuttal": "We thank the reviewer for their feedback. We address the concerns one by one as follows:\n\n>In terms of effectiveness, EigenPro 4 performs inconsistently across different model sizes: it is strange to observe that although EigenPro 4 is more efficient than EigenPro 3, the accuracy of EigenPro 4 is lower (higher) than EigenPro 3 when the model size is small (large). Is there any particular reason behind this?\n\nFrom a generalization perspective, EigenPro 4 and EigenPro 3 converge to different solutions, and their exact generalization behavior depends on the specific problem. However, we note that EigenPro 4.0 tends to be more effective at larger model sizes. This is because it allows for longer delays between projections(for a fixed batch size), and each projection step discards less information—the larger model has a better chance of adequately covering the relevant function space.\n\n>Although EigenPro 4 is faster than EigenPro 3 and converges faster. The results in Figure 5 indicate the convergence process of EigenPro 4 is more unstable than EigenPro 3 due to delayed projection, especially in Webvision dataset. Is this because EigenPro 4 accuracy improves between projections and drops after each projection step as shown in Figure 5?\n\nIn the EP4 algorithm, the model expands between projections by incorporating temporary centers—it is not a fixed model during this phase. After each projection step, the model reverts to its original form with a fixed set of centers. This explains the accuracy drop observed after each projection step in Figure 5: the temporary expansion improves accuracy, but once the projection is applied, the model returns to its constrained representation.\n\n>As claimed in line 727, the EigenPro 4 accuracy drops from projections become progressively smaller. However, in the Webvision and Librispeech results in Figure 5, the multiple accuracy drops remain relatively large when EigenPro 4 converges. Is there any specific reason behind this occurrence that warrants further exploration on the stability of EigenPro 4? Adding an analysis on this issue would be nice.\n\nWe believe you may be referring to Figure 3, rather than Figure 5. To clarify, Figure 5 plots accuracy over training steps, where projection steps are explicitly marked with dashed vertical lines. In contrast, Figure 3 shows accuracy over training epochs, where a projection occurs at the end of each epoch (In addition to every T steps projection)."}, {"review_id": "leIIYLSYLz", "reviewer": "Reviewer_aQLu", "summary": "The paper proposes a novel algorithm EigenPro 4 for training large kernel models.\nThe algorithm is an upgrade an existing EigenPro 3 version which uses preconditioned stochastic gradient descent with certain projections in order to decouple the model size from the training set size. This projection requires quadratic time in the model size and so far had to be computed after each stochastic step which yields the bottleneck for the running time.\nThe authors overcome this bottleneck by delaying the projections for $T$ iterations, where $T$ is a predefined hyperparameter (it is claimed that the optimal value for $T$ is the ratio of model size and batch size).\n\nThey validate their approach empirically with experiments on three datasets which show a clear speedup of the EigenPro 4 version compared to EigenPro3 and another state-of-the art method.", "questions": "1) You mention that you prove convergence of Alg 1 for $T=\\infty$ in the appendix. This would mean that it never projects, which does not really make sense. In fact, you prove it for $T=1$?\n\n2) How did you choose $T$ and all other hyperparameters in your experiments?\n\n3) Do you have an explanation why also the convergence rate is faster?\n\n4) Can your algorithm compete with other models?", "limitations": "The paper does not really discuss any limitations of the approach.\nFor example, how does the algorithm perform in comparison to other (non-kernel) machine learning methods.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength: The paper presents a natural approach to speed up the computational performance of the state-of-the art of kernel based learning. The performance seems to be considerably improved at least on the investigated datasets. Also the convergence rate was faster.\n\nWeakness: The result is very incremental. The idea to delay projections seems rather obvious and of little originality. The increase in performance looks solid, but I am not sure about the significance for practical purposes (since I am not an expert in practical applications).\nAlso, there is no theoretical analysis provided that guarantees convergence.\nFinally, the presentation could be improved. Many things are not defined or explained and there are several language errors. (See comments below.)\n\nComments:\n- l 28: \"to improve condition number\" -> improve the condition number\n- l 51: \"on CIFARM data set\" -> on the CIFARM data set\n- l 63: z_i not mathbold. Also explain the idea behind these centers of a general kernel model.\n- l 65: Define what a RKHS is.\n- Fig 1: Explain notation p.\n- l 80:  Explain the tensor product sign.\n- l 95: \"condition number is ill conditioned\" -> This is a confusing formulation.\n- l 102: \"unit-norm e_i\" -> Do you mean standard unit vector?\n- l 104: \"let ... as the\" -> let ... be the\n- l 134: \"models of this form\" -> which form are you referring to?\n- l 136: The variable m is not defined yet. (Also you use m later for mini batches (X_m,y_m), which could be confusing)\n- l 150: \"add to Z_tmp with temporary centers\" -> add to Z_tmp the temporary...\n- Fig 3: What is n?", "was_revised": true, "final_justification": "After considering the rebuttal and also the comments by the other reviewers, I find the paper to be acceptable.", "rebuttal": "We thank the reviewer for their feedback. We address the concerns one by one as follows:\n\n\n\n> The increase in performance looks solid, but I am not sure about the significance for practical purposes (since I am not an expert in practical applications).\n\nKernel methods play a crucial role in understanding modern learning phenomena such as feature learning—an area that has gained renewed attention, including in recent work published in *Science* [1]. We will revise the paper to include a clearer and more detailed motivation for studying kernel models and their relevance.\n\n[1] Radhakrishnan, A., Beaglehole, D., Pandit, P., & Belkin, M.  \n*Mechanism for feature learning in neural networks and backpropagation-free machine learning models.*  \nScience, 383(6690), 1461–1467, 2024.\n\n\n\n> Also, there is no theoretical analysis provided that guarantees convergence.\n\nWe provide a theoretical analysis in the appendix for the special case when $T = \\infty$. However, the primary focus of this paper is to demonstrate the empirical effectiveness of our method across a range of datasets, in comparison to prior state-of-the-art approaches.\n\n\n\n> You mention that you prove convergence of Alg 1 for $T = \\infty$ in the appendix. This would mean that it never projects, which does not really make sense. In fact, you prove it for?\n\nTo clarify, $T = \\infty$ does not mean that we never project. Rather, it refers to an idealized setting in which temporary centers are added infinitely many times. Since the training set is finite and temporary centers are selected from this set, the process can be represented by assigning weights to each data point. We know these weights converge to the closed-form solution:\n\n$$\n\\alpha^* = K(X, X)^{-1} y\n$$\n\nOnce this limiting solution is reached for $T = \\infty$, we project the resulting model back to the original model with a fixed set of centers. This process is then repeated iteratively. Our analysis focuses on this limiting behavior to better understand the convergence dynamics of the algorithm.\n\n\n\n> How did you choose $T$ and all other hyperparameters in your experiments?\n\nFor most hyperparameters, such as the kernel bandwidth, we followed standard choices from prior work—particularly those used in EigenPro 3. Similarly, for the preconditioner, we adopted the typical setting where the ratio of the number of Nyström samples to the number of top eigenvalues to suppress is around 10–15. The only new hyperparameter introduced in our method is the projection frequency $T$, which we discuss in Appendix Section B. There, we explain that $T$ should scale with the ratio of the model size $p$ to the batch size $m$.\n\n\n\n> Do you have an explanation why also the convergence rate is faster?\n\nIf you are referring to Figure 3, that was an empirical observation.\n\n\n\n> Can your algorithm compete with other models?\n\nOur paper specifically focuses on the computational complexity of kernel models, rather than benchmarking performance against non-kernel models. To this end, we compare our method to two prior state-of-the-art solvers for kernel methods, which is the relevant baseline for our study.\n\n\n\n> Comments:\n\nThank you for pointing these out. We will fix them in the final version of the paper."}, {"review_id": "QCL2MHy7cA", "reviewer": "Reviewer_tAZu", "summary": "The authors propose EigenPro4, the algorithm for fast training of kernel machines using Preconditioned Stochastic Gradient Descent. This work builds upon the previous versions of the algorithms: EigenPro, EigenPro2, and EigenPro3. The key trick is to use a subset of training points to represent the function, rather than using all trainingp points. The key difficulty is that the computed gradient in each iteration lies in the span of the training points, not in the span of the chosen Nystrom centers. In order to maintain the iterate remains in the span of the Nystrom centers (low rank), a projection method which is the most expensive step ($O(p^2)$ per iterate) was proposed in EigenPro3. This projection step was improved to $O(p)$ in EigenPro4 by delaying the projections for $T$ iterations. This means in-between the two successive projection steps, the prediction function has additional temporary centers; so for $T$ delayed projections, the maintained centers would be expanded by at most $T m$ additional centers. The authors compare EigenPro4 against EigenPro3 and Falkon on real-world datasets.", "questions": "1. I could not find what parameters were used for EigenPro4 in the experiment. Could the authors clarify?\n2. In general, the results for each method used should be parameterized (e.g. Table 1). In general, it is hard to find these parameters within the writeup.\n3. Would it be possible to incorporate a nearest neighbor heuristic within Algorithm 1 (Line 8) to further maintain a more compress set of centers?\n4. Other than the Laplace kernel (again, I was not able to find which kernel was being used for the experiment in the captions), what other kernels have the authors tried?", "limitations": "There are no significant limitations in the authors' work. However, while the experimental results for the most part are clearly presented, the authors are encouraged to tabulate the parameters used for each method for clarity.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: The manuscript is clearly written and the authors have actually made conscientious efforts to limit unnecessarily complex notations to aid in understanding the algorithm. Experimental evaluations are thorough and enlightening, although they do not cover every variant of fast kernel machines.\n\nWeaknesses: The improvement is rather trivial and relies on delaying the projection step to improve efficiency of the algorithm. But perhaps this triviality makes the manuscript stand out in times when many obscure papers are abundant.", "was_revised": true, "final_justification": "In light of the authors' responses and technical presentation of the paper, I am recommending the paper for acceptance. While the extensions could be seen as obvious, I think this paper does deserve a spot as it has applications in which kernel methods (and may also provide some inspiration of scaling deep neural networks) are applicable.", "rebuttal": "We thank the reviewer for their positive comments. We address the concerns one by one as follows:\n\n>I could not find what parameters were used for EigenPro 4 in the experiment. Could the authors clarify?\n\nThe hyper-parameters used in our experiments are listed in Appendix Section C. If there is a specific hyper-parameter you are referring to, we would be happy to clarify further.\n\n>In general, the results for each method used should be parameterized (e.g., Table 1). In general, it is hard to find these parameters within the writeup.\n\nThank you for the suggestion. If you are referring to the hyper-parameters for each method, we will add a comprehensive table summarizing all hyper-parameters across experiments and methods in the final version to improve readability.\n\n>Would it be possible to incorporate a nearest neighbor heuristic within Algorithm 1 (Line 8) to further maintain a more compressed set of centers?\n\nHow to add or choose centers is indeed an important future direction. One possible approach is to use clustering techniques like K-means to avoid selecting redundant centers. Incorporating nearest neighbor heuristics, as you suggested, is another promising direction to maintain a more compact and diverse set of centers.\n\n>Other than the Laplace kernel (again, I was not able to find which kernel was being used for the experiment in the captions), what other kernels have the authors tried?\n\nWe used the Laplace kernel in our experiments, primarily for consistency with prior work and because its per-batch computation is highly efficient. Specifically, the total training time scales linearly with the per-batch kernel computation time, which makes it feasible to explore more computationally intensive methods like EP3.0—especially at larger model scales. For completeness, we will include results using the NTK kernel for EP4.0 in the final version.\n\nSome results using alternative kernels: Gaussian (with bandwidth 20) and NTK (ReLU MLP with depth 2), evaluated on the same extracted embeddings from the CIFAR5M dataset as used in the main paper.\n| Kernel Type | 64k Centers       | 128k Centers      | 256k Centers      |\n|-------------|-------------------|-------------------|-------------------|\n| Gaussian    | 87.77% (178s)     | 87.80% (194s)     | 88.14% (233s)     |\n| NTK         | 87.01% (206s)     | 87.34% (309s)     | 87.54% (564s)     |"}]

Author rebuttal:

Meta-review: The reviewers unanimously recommend to accept the paper.

The only remaining criticisms are:
 - experimental results being limited to one kernel type
 - somewhat moderate novelty
Other initial criticisms have been resolved in the rebuttal and following discussions.

The remaining criticism is more than outweighed by the strong points:
 - interesting novel directions in scaling kernel methods
- contribution efficiency improvements
- strong technical merit 

I congratulate the authors to their work and recommend acceptance.
Decision: Accept (spotlight)