Research map / Learning theory and algorithms / Kernels and regression theory

Optimized Random Features for the Neural Tangent Kernel (Student Abstract)

AAAI 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Neural tangent kernel analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Adds a data-dependent, kernel-alignment optimization (chi-square f-divergence distribution over sampled random features) to sketched arc-cosine random-feature approximations of the neural tangent kernel, yielding lower MSE with fewer features on two regression datasets.

Problem

Computing the neural tangent kernel exactly is costly as dataset size and network depth/width grow, and randomized random-feature approximations are not optimized for the label space.

Approach

Sample an initial set of arc-cosine random features, then learn a distribution over them (via f-divergence-constrained kernel alignment, following Sinha and Duchi 2016) so that the approximate NTK aligns with labels; keep only features with nonzero probability.

Key results

• On the first dataset (1 hidden layer), OPT NTK-RF reduces MSE from 216.74 (NTK-RF, m0=m1=692) to 199.15 using about 350/395 effective features.
• On the WorkLoads dataset (2 layers), OPT NTK-RF achieves MSE 28362.16 versus 32662.96 for NTK-RF, with about 274-347 features per layer instead of 3192.
• Exact NTK achieves MSE 64.74 on the first dataset, so the optimized approximation remains far from exact performance.

Measured effects reported in the paper

Surprising findings

• Optimized features without Gibbs sampling for the A1 kernel achieved lower MSE on the first dataset (183.63) than the GS variant, although they required more features.

Limitations

• Optimized MSE remains far from the exact NTK MSE.
• Evaluated only on kernel ridge regression with two datasets and small architectures from prior work.
• Optimization adds computation time over unoptimized random features.

Experimental setup

Datasets: dataset with N=53500, d=379 (from Zandieh et al. 2021) WorkLoads dataset with N=199843, d=6 (from Zandieh et al. 2021)

Benchmarks: kernel ridge regression on two regression datasets

Metrics: mean squared error running time (seconds) number of random features

Baselines: Exact NTK NTK-RF

Builds on: NTK-RF (Han et al. 2021) Zandieh et al. 2021 NTK sketching Sinha and Duchi 2016 distributionally robust kernel alignment Gibbs sampling for arc-cosine features

Closest papers by meaning

• Scaling Neural Tangent Kernels via Sketching and Random Features (NeurIPS 2021 · similarity 0.92)
• On the Impacts of the Random Initialization in the Neural Tangent Kernel Theory (NeurIPS 2024 · similarity 0.90)
• Divergence of Neural Tangent Kernel in Classification Problems (ICLR 2025 · similarity 0.88)
• The Surprising Effectiveness of Infinite-Width NTKs for Characterizing and Improving Model Training (AAAI 2025 · similarity 0.88)
• Shortcut Features as Top Eigenfunctions of NTK: A Linear Neural Network Case and More (NeurIPS 2025 · similarity 0.87)
• A generalized neural tangent kernel for surrogate gradient learning (NeurIPS 2024 · similarity 0.87)