Abstract
The Neural Tangent Kernel (NTK) provides a theoretical bridge between deep neural networks and kernel methods, yet its $O(n^2)$ computational complexity limits its application to large-scale datasets. While random feature (RF) approximations offer a speedup, standard sampling methods are data-agnostic and often require a large number of features for high accuracy. This paper proposes a data-dependent optimization framework that selects a sparse subset of "informative" random features by maximizing kernel alignment with target labels. Experimental results on regression benchmarks demonstrate that the proposed Optimized NTK-RF (OPT NTK-RF) significantly reduces approximation error and feature count compared to standard RF methods, while avoiding the memory constraints of exact NTK computation.
Introduction
The Neural Tangent Kernel (NTK) is a landmark concept in deep learning theory, describing how an infinitely wide neural network evolves during training. By treating complex deep networks as fixed kernel methods, researchers can perform tasks like regression without the need for intensive network training. However, computing the exact NTK scales quadratically with the number of data points, making it prohibitively slow and memory-intensive for large datasets.
To address this, random features are often used to approximate kernels. However, standard methods sample these features blindly, ignoring specific patterns in the data or target labels. This often necessitates a massive number of features to achieve acceptable accuracy. This paper introduces an optimization step to select the most relevant features, improving both efficiency and performance.
Methodology
The authors build upon recursive formulas for the NTK of ReLU networks, which utilize arc-cosine kernels ($A_0$ and $A_1$). Their core contribution is an additional optimization step for these random features:
- Initial Sampling: A large pool of standard random features (e.g., $N_w = 20,000$) is initially sampled.
- Kernel Alignment: The method solves an optimization problem to find a new probability distribution ($Q$) over these features that maximizes "kernel alignment"—ensuring the resulting kernel closely matches the target labels.
- Constrained Optimization: To prevent overfitting, the distribution $Q$ is constrained to remain close to the original uniform distribution using $\chi^2$-divergence.
- Sparse Selection: The resulting optimal distribution $Q$ is naturally sparse, allowing the algorithm to identify and retain only the most useful features while discarding the rest.
Experimental Results
The researchers evaluated their approach on two regression benchmarks: the CT dataset ($N = 53,500$) and the WorkLoads dataset ($N = 199,843$). The performance was compared against exact NTK calculations and standard NTK-RF approximations.
As shown in the results above, the OPT NTK-RF method consistently outperformed standard random feature approximations. On the CT dataset, the Mean Squared Error (MSE) dropped from 216.74 to 183.63. On the larger WorkLoads dataset, the exact NTK calculation resulted in an Out of Memory (OOM) error, while the optimized approach successfully provided a high-accuracy approximation.
Crucially, the optimized version achieved these lower errors using significantly fewer features ($m_0$ and $m_1$ values around 350-400) compared to the standard method. While the optimization step introduces a small computational overhead (e.g., 74.74s vs 14.05s on CT), it remains orders of magnitude faster than exact calculations and provides superior accuracy.
Discussion and Conclusion
The primary insight of this work is that feature quality is more important than quantity. By aligning features with labels at each layer, the model achieves better performance with a fraction of the features typically required. Furthermore, the optimization step makes complex sampling schemes, such as Gibbs sampling, largely redundant.
Future work aims to address the "tensoring problem" in deep networks, where feature counts can explode due to recursive tensor products. Additionally, the authors intend to develop formal asymptotic upper bounds on the number of optimized features required for specific accuracy levels, potentially extending this method to tasks like data distillation.
Summary updated