Structured Features Overfit Where Random Features Grok
Abstract
Xu, Vardi and Safran (ICML 2026) prove that over-parameterized ridge regression over an unstructured random Gaussian feature map groks, with the delay between memorization and generalization growing as 1/λ in the weight decay. We show that on a structured feature map the same delay does not appear. For a band-limited Fourier feature map over ℤp2 carrying a single-character target that lies inside the expressible class, enlarging the band at fixed positive weight decay drives peak held-out accuracy monotonically from $1.00$ to $0.07$, with no memorize-then-generalize regime anywhere along the sweep. The degradation is not an interpolation effect. It sets in at capacity ratio q/n = 0.638, far below the interpolation threshold, on separate grounds from the exact null space that appears above it. What does have a sharp boundary is the active support. Holding the nominal dimension fixed and masking the band back to $1089$ active modes restores held-out accuracy of $1.000$ with zero variance across seeds, while the full $4225$-mode band collapses to $0.185$. The number of active modes acts through the teacher-weighted spectrum of the empirical Gram matrix and not through the capacity ratio, which makes this a statement about feature geometry and not a restatement of double descent.
Related
- Structured Masked Diffusion for Shared-Codebook Unsourced Random Access Decoding
- Dynamic models with p parameters are identified by 2p+1 random features
- A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
- Estimating dynamic models by matching random features
- Task-Calibrated Random Features via Influence-Based Error Cancellation
BibTeX
@misc{kam2026structured,
title = {{Structured Features Overfit Where Random Features Grok}},
author = {Chon-Fai Kam and Miloud Bessafi and Frederic Cadet},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15047},
eprint = {2609.15047},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15047},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Structured Features Overfit Where Random Features Grok
AU - Chon-Fai Kam
AU - Miloud Bessafi
AU - Frederic Cadet
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15047
UR - https://arxiv.org/abs/2609.15047
AB - Xu, Vardi and Safran (ICML 2026) prove that over-parameterized ridge regression over an unstructured random Gaussian feature map groks, with the delay between memorization and generalization growing as 1/λ in the weight decay. We show that on a structured feature map the same delay does not appear. For a band-limited Fourier feature map over ℤ_p^2 carrying a single-character target that lies inside the expressible class, enlarging the band at fixed positive weight decay drives peak held-out accuracy monotonically from $1.00$ to $0.07$, with no memorize-then-generalize regime anywhere along the sweep. The degradation is not an interpolation effect. It sets in at capacity ratio q/n = 0.638, far below the interpolation threshold, on separate grounds from the exact null space that appears above it. What does have a sharp boundary is the active support. Holding the nominal dimension fixed and masking the band back to $1089$ active modes restores held-out accuracy of $1.000$ with zero variance across seeds, while the full $4225$-mode band collapses to $0.185$. The number of active modes acts through the teacher-weighted spectrum of the empirical Gram matrix and not through the capacity ratio, which makes this a statement about feature geometry and not a restatement of double descent.
ER -