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

High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm

AAAI 2024 · Learning theory and algorithms › Kernels and regression theory · approach: Double descent and overfitting · 3 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.

Gives a high-dimensional asymptotic analysis of generalized nonlinear ridge and ridgeless regression with subsampling, expresses risks via effective dimension, and proposes RFRed, a random Fourier feature model trained to reduce effective dimension.

Problem

Benign overfitting and double descent in nonlinear regression lack a general asymptotic framework, and existing asymptotic results are self-consistency equations rather than quantities tied to classical complexity measures like effective dimension.

Approach

Derives asymptotic equivalents of risk for nonlinear ridge/ridgeless regression with subsampling in terms of the implicit regularization parameter and effective dimension (df1, df2), then uses the empirical effective dimension as a training regularizer to jointly optimize random Fourier features and model parameters (RFRed).

Key results

• Asymptotic variance and bias of nonlinear ridge/ridgeless regression with subsampling are expressed through df2(κ), with variance ~σ² df2/(m−df2) and risk exploding as df2 approaches m.
• Experiments on MNIST show mild regularization (λ=1e-2, 1e-4) yields double descent while stronger regularization restricts df2 and removes it; the optimal λ is near 1e-3 across γ=0.5, 1, 2.
• Ridgeless regression shows exploding square loss in the over-parameterized regime, while ridge regression losses decrease with p.

Measured effects reported in the paper

Surprising findings

• Downsampling does not always hurt generalization; test error and square loss of ridge regression can decrease in the over-parameterized regime with m < p < n.
• Ridge regression losses decrease with p in the over-parameterized regime, while ridgeless regression loss explodes.

Limitations

• Effective dimension df2 is hard to compute exactly, so the empirical estimate is used, and the hyperparameters λ and S are tuned before training for efficiency.
• Assumptions are strict; the orthogonal subsampling assumption cannot be satisfied by i.i.d. sketching matrices.
• Experiments are small-scale (MNIST, n around 100 to 1000) and no comparison to deep networks or large benchmarks is reported in the main text.

Experimental setup

Datasets: MNIST

Benchmarks: MNIST

Metrics: test error square loss effective dimension df2(κ)

Baselines: linear ridge regression ridgeless regression

Builds on: Bach 2023 effective dimension asymptotics Hastie et al. 2022 high-dimensional ridge analysis random Fourier features Chen et al. 2023 sketching asymptotics

Closest papers by meaning

• Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization (ICML 2025 · similarity 0.88)
• Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate (ICML 2025 · similarity 0.87)
• Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.87)
• Dimension-free deterministic equivalents and scaling laws for random feature regression (NeurIPS 2024 · similarity 0.86)
• Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.85)
• High-dimensional Analysis of Knowledge Distillation: Weak-to-Strong Generalization and Scaling Laws (ICLR 2025 · similarity 0.85)