Closed-form ℓ_r norm scaling with data for overparameterized linear regression and diagonal linear networks under ℓ_p bias

2025/09/25 by Shuofeng Zhang, Zhang, Shuofeng, Ard A. Louis +1 · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2509.21181

openalex publication_date 2025/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For overparameterized linear regression with isotropic Gaussian design and minimum-ℓ_p interpolator p∈(1,2], we give a unified, high-probability characterization for the scaling of the family of parameter norms ‖ \widehatw_p ‖_{r r ∈ [1,p]} with sample size. We solve this basic, but unresolved question through a simple dual-ray analysis, which reveals a competition between a signal *spike* and a *bulk* of null coordinates in X^\top Y, yielding closed-form predictions for (i) a data-dependent transition n_⋆ (the "elbow"), and (ii) a universal threshold r_⋆=2(p-1) that separates ‖ \widehatw_p ‖_r's which plateau from those that continue to grow with an explicit exponent. This unified solution resolves the scaling of *all* ℓ_r norms within the family r∈ [1,p] under ℓ_p-biased interpolation, and explains in one picture which norms saturate and which increase as n grows. We then study diagonal linear networks (DLNs) trained by gradient descent. By calibrating the initialization scale α to an effective p_eff(α) via the DLN separable potential, we show empirically that DLNs inherit the same elbow/threshold laws, providing a predictive bridge between explicit and implicit bias. Given that many generalization proxies depend on ‖ \widehat w_p ‖_r, our results suggest that their predictive power will depend sensitively on which l_r norm is used.

Citations

• Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and\n Benign Overfitting
• Understanding Double Descent Requires a Fine-Grained Bias-Variance\n Decomposition
• Deep Double Descent: Where Bigger Models and More Data Hurt
• Kernel and Rich Regimes in Overparametrized Models
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Implicit Regularization in Deep Matrix Factorization
• Harmless interpolation of noisy data in regression
• Surprises in High-Dimensional Ridgeless Least Squares Interpolation
• Reconciling modern machine learning practice and the bias-variance trade-off
• Gradient descent aligns the layers of deep linear networks
• Fluctuation-dissipation relations for stochastic gradient descent
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Spectral Normalization for Generative Adversarial Networks
• Three Factors Influencing Minima in SGD
• Don't Decay the Learning Rate, Increase the Batch Size
• The Implicit Bias of Gradient Descent on Separable Data
• Spectrally-normalized margin bounds for neural networks
• Spectral Norm Regularization for Improving the Generalizability of Deep Learning
• Implicit Regularization in Matrix Factorization
• Parseval Networks: Improving Robustness to Adversarial Examples
• Understanding deep learning requires rethinking generalization
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Statistical Learning with Sparsity: The Lasso and Generalizations
• Norm-Based Capacity Control in Neural Networks
• An Introduction to Matrix Concentration Inequalities
• The Gaussian min-max theorem in the Presence of Convexity
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Living on the edge: Phase transitions in convex programs with random\n data
• The Dantzig selector: Statistical estimation when p is much larger than n
• Ridge Regression: Biased Estimation for Nonorthogonal Problems
• Atomic Decomposition by Basis Pursuit
• A Statistical View of Some Chemometrics Regression Tools

Cited by

• Position: Many generalization measures for deep learning are fragile

Related

• Linear regression with overparameterized linear neural networks: Tight upper and lower bounds for implicit ℓ¹-regularization
• Conflicting Biases at the Edge of Stability: Norm versus Sharpness Regularization
• Kernel and Rich Regimes in Overparametrized Models
• Scaling Laws in Linear Regression: Compute, Parameters, and Data
• Minimum ℓ₁-norm interpolators: Precise asymptotics and multiple descent