Fast Training of Large Kernel Models with Delayed Projections

We thank the reviewer for their positive comments. We address the concerns one by one as follows:

I could not find what parameters were used for EigenPro 4 in the experiment. Could the authors clarify?

The 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.

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.

Thank 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.

Would it be possible to incorporate a nearest neighbor heuristic within Algorithm 1 (Line 8) to further maintain a more compressed set of centers?

How 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.

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?

We 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.

Some 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.

We thank the reviewer for their feedback. We address the concerns one by one as follows:

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).

Kernel 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.

[1] Radhakrishnan, A., Beaglehole, D., Pandit, P., & Belkin, M.
Mechanism for feature learning in neural networks and backpropagation-free machine learning models.
Science, 383(6690), 1461–1467, 2024.

Also, there is no theoretical analysis provided that guarantees convergence.

We 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.

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?

To 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:

$$\alpha^* = K(X, X)^{-1} y$$

Once 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.

How did you choose $T$ and all other hyperparameters in your experiments?

For 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$.

Do you have an explanation why also the convergence rate is faster?

If you are referring to Figure 3, that was an empirical observation.

Can your algorithm compete with other models?

Our 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.

Comments:

Thank you for pointing these out. We will fix them in the final version of the paper.

We thank the reviewer for their feedback. We address the concerns one by one as follows:

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?

From 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.

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?

In 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.

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.

We 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).

We thank the reviewer for their feedback. We address the concerns one by one as follows:

Experiments/Datasets are a bit artificial. For example, the kernel method uses features extracted from a ResNet/MobileNetV2. And 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.

The 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. We 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.

[1] Radhakrishnan, A., Beaglehole, D., Pandit, P., & Belkin, M. Mechanism for feature learning in neural networks and backpropagation-free machine learning models. Science, 383(6690), 1461–1467, 2024.

Some experimental details are missing in the main text; for example, basic information like what value of $T$ is used?

We 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.

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.

…

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.

…

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?

We 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.

As 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.

About the kernel: We 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.

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.

Figure 5 shows that performance degrades after the projection step. Are you able to explain this behaviour?

In 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.

We thank the reviewer for their feedback. We address the concerns one by one as follows:

Although the contributions could be significant, the paper does a poor job phrasing its importance with respect to other non-kernel methods.

Our 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. [1] Radhakrishnan, A., Beaglehole, D., Pandit, P., & Belkin, M. Mechanism for feature learning in neural networks and backpropagation-free machine learning models. Science, 383(6690), 1461–1467, 2024

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 .

We 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.

Some 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.

In equation 15, the otherwise branch calculates the stochastic gradient using , but should it not be on ?

Could 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.