Research map / Learning theory and algorithms / Kernels and regression theory
Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem
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.
Extends the Gauss-Markov theorem to allow bounded bias measured by Schatten norms, derives closed-form Nuclear, Frobenius (ridge), and Spectral estimators, and shows Nuclear regression has flatter cross-validation minima than Ridge.
Problem
Minimum-variance linear estimation when bias is allowed but bounded; understanding how non-L2 (matrix norm) regularization behaves, especially how flat or sharp the test-error minimum is as a function of regularization strength under cross-validation.
Approach
Define the p-bias constrained linear estimator as the minimum-variance linear estimator whose bias operator LX−I has bounded Schatten-p norm; show it has the form (Ĝ)^{-1}X^T with closed forms for p=1 (Nuclear), p=2 (ridge), and p=∞ (Spectral), and analyze the resulting test error in random matrix ensembles.
Key results
- Nuclear estimator minima are nearly as deep as Ridge (within a few percentage points) but substantially flatter in the spherical Gaussian model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nuclear Regression instead of Ridge | Cross-validated linear regression · Gaussian predictors | average test error | No clear effect |
| Use Nuclear Regression instead of Ridge | Cross-validated linear regression · Gaussian predictors | probability of winning on a dataset | Helped |
| Use Spectral Regression instead of Ridge | Cross-validated linear regression · Gaussian predictors | average test error | Hurt |
| Use Nuclear Regression instead of Ridge | Cross-validated linear regression · Random Fourier features | test error | Helped |
| Use Nuclear Regression instead of Ridge | Linear regression · Spherical Gaussian and diagonal power-law ensembles | curvature at the test-error minimum | Helped |
| Use Nuclear Regression instead of Ridge | Linear regression · Spherical Gaussian and diagonal power-law ensembles | minimum test error | Mixed |
| Use Spectral Regression instead of Ridge | Linear regression · Spherical Gaussian and diagonal power-law ensembles | curvature at the test-error minimum | Helped |
| Use Spectral Regression instead of Ridge | Linear regression · Spherical Gaussian and diagonal power-law ensembles | minimum test error | Hurt |
| Increase the number of regularization strengths in cross-validation | Ridge Regression · Gaussian predictors | average test error | Helped |
| Increase the number of regularization strengths in cross-validation | Ridge Regression · Gaussian predictors | average test error | Mixed |
| Use Ridge with oracle-optimal regularization strength instead of another pointwise spectral transform | Linear estimators in both random matrix models · Spherical Gaussian and diagonal ensembles | test error | Helped |
Surprising findings
- Ridge is theoretically optimal among the family, yet cross-validated Nuclear often wins on individual datasets because its flatter minimum is less penalized by noisy search.
- Ridge benefits more from increasing the number of cross-validation alpha values and can overtake Nuclear when many values are used.
Limitations
- Theory relies on a thermodynamic limit and specific random matrix ensembles (spherical Gaussian and diagonal Stiefel-based).
- Gauss-Markov extension only gives trace-variance optimality rather than the full matrix-ordering version of the classical theorem.
- Spectral estimator does not naturally handle the overparametrized regime, so it was excluded from the RFF experiments.
Experimental setup
Datasets: synthetic Gaussian predictors synthetic diagonal random matrix ensemble with power-law spectrum synthetic random Fourier features regression
Metrics: test MSE minimum test error curvature at minimum win probability under cross-validation
Baselines: Ridge regression Principal Components Regression Lasso Stein shrinkage
Builds on: Gauss-Markov theorem ridge regression principal components regression
Closest papers by meaning
- Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.87)
- Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms (NeurIPS 2024 · similarity 0.86)
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.86)
- Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods (NeurIPS 2024 · similarity 0.85)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.85)
- Non-Asymptotic Analysis Of Data Augmentation For Precision Matrix Estimation (NeurIPS 2025 · similarity 0.85)
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.