The Zero Pattern of a Design Matrix Drives Multiple Descent in Over-parameterized Regression
2026-07-27 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a type of linear regression model that uses more parameters than data points, relaxing common assumptions that data features are independent and have full-rank covariance. They find that when these assumptions are dropped, the model's prediction error can show multiple peaks, known as multiple descent, instead of just one. To understand this, they use a new way of representing data relationships with graphs, identifying key structures that cause unusual variance behavior. This work helps explain how dependencies and degeneracies in data affect over-parameterized regression performance.
Over-parameterized linear regressionCovariance matrixFeature dependenceDegeneracyMultiple descentPrediction riskVanishing ridgeGraph representationMaximum matchingDulmage-Mendelsohn decomposition
Authors
Kevin Han Huang, Haoyu Ye, Somak Laha, Morgane Austern
Abstract
Over-parameterized linear regression has been widely studied over the last decade. However, most existing works assume that the covariates are independent and that their covariance matrices are non-degenerate. In this paper, we relax both assumptions and derive deterministic equivalents for the prediction risk in a vanishing-ridge regime. We show that degeneracy of the covariance matrices and dependence can lead to multiple descent, and characterize where the corresponding peaks can occur. Our proofs use a novel graph representation of the variance profile. We show that maximum matchings and the Dulmage--Mendelsohn decomposition of the associated bipartite graph identify the configurations at which the variance becomes singular.