Research map / Learning theory and algorithms / Kernels and regression theory
Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
Jing Xu, Jiaye Teng, Yang Yuan, Andrew C Yao
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use optimal early-stopping iterate instead of min-norm interpolator | GD on overparameterized linear regression · eigenvalues 1/i, n=100, p=1000 | excess risk: 24.071 -> 2.399 | Improved |
| use optimal early-stopping iterate instead of min-norm interpolator | GD on overparameterized linear regression · eigenvalues 1/i^2, n=100, p=1000 | excess risk: 43.472 -> 0.214 | Improved |
| use optimal early-stopping iterate instead of min-norm interpolator | GD on overparameterized linear regression · eigenvalues 1/i^3, n=100, p=1000 | excess risk: 10.401 -> 0.077 | Improved |
| use optimal early-stopping iterate instead of min-norm interpolator | GD on overparameterized linear regression · eigenvalues 1/(i log(i+1)), n=100, p=1000 | excess risk: 89.922 -> 0.697 | Improved |
| use optimal early-stopping iterate instead of min-norm interpolator | GD on overparameterized linear regression · eigenvalues 1/(i log^2(i+1)), n=100, p=1000 | excess risk: 82.413 -> 0.298 | Improved |
| use optimal early-stopping iterate instead of min-norm interpolator | GD on overparameterized linear regression · eigenvalues 1/(i log^3(i+1)), n=100, p=1000 | excess risk: 38.145 -> 0.187 | Improved |
| use best GD iterate instead of final SGD iterate | CNN · Corrupted MNIST 20% label noise | test error (%): 19.9 -> 2.88 | Improved |
| faster eigenvalue decay of feature covariance (1/i to 1/i^3) | early-stopped GD · synthetic linear regression | optimal excess risk: 2.399 -> 0.077 | Improved |
| faster decay of eigenvalues | min-norm interpolator · synthetic linear regression | excess risk: 24.071 -> 43.472 -> 10.401 | Mixed |
| log-polynomial decay with larger power beta (1 to 3) | early-stopped GD · synthetic linear regression | optimal excess risk: 0.697 -> 0.187 | Improved |
Closest papers by meaning
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.87)
- Improving Adaptivity via Over-Parameterization in Sequence Models (NeurIPS 2024 · similarity 0.87)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.86)
- Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression (NeurIPS 2024 · similarity 0.86)
- Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate (ICML 2025 · similarity 0.86)
- Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
