The Zero Pattern of a Design Matrix Drives Multiple Descent in Over-parameterized Regression

Technical Summary: The Zero Pattern of a Design Matrix Drives Multiple Descent in Over-Parameterized Regression

Problem Statement
Over-parameterized linear regression has been extensively studied, yet existing theoretical frameworks largely rely on two restrictive assumptions: that covariates are independent and that their covariance matrices are non-degenerate (positive definite). Under these conditions, the prediction risk typically exhibits a "double descent" curve with a single peak at the interpolation threshold ($\gamma = p/n = 1$), driven by a single spectral event where the design matrix loses rank.

This paper addresses the gap in understanding when and why multiple descent—the emergence of multiple risk peaks—can arise solely from the structure of the data, without relying on architectural tuning, separate feature blocks, or distinct kernel scales. The authors investigate ridge least squares with a vanishing penalty ($\lambda_n \downarrow 0$) in the proportional regime ($p/n \to \gamma \in (0, \infty)$) under two specific relaxations:

1. Heterogeneity: Observations are independent but possess distinct, potentially rank-deficient covariance matrices.
2. Dependence: Observations are correlated through finite-rank separable components (e.g., data augmentation).

Methodology
The core methodological innovation is the reduction of both heterogeneous and dependent Gaussian designs to a variance-profile model. By rotating the data into a shared eigenbasis (where covariances are simultaneously diagonalizable), the authors transform the problem into analyzing a Gaussian matrix with independent entries but unequal variances, defined by a variance profile matrix $S \in \mathbb{R}^{n \times p}$.

1. Variance Profile Reduction:

   • For Model 1 (Heterogeneous), where $X_i = \Sigma_i^{1/2} Z_i$, the profile $S$ is constructed from the eigenvalues of the individual covariances $\Sigma_i$.
   • For Model 2 (Dependent), where $X = \sum (\tilde{\Sigma}^{(m)})^{1/2} Z^{(m)} (\Sigma^{(m)})^{1/2}$, the profile $S$ is derived from the product of the eigenvalues of the sample and coordinate covariance components.
   • Crucially, the zero pattern of $S$ (where $S_{ij} = 0$) encodes which observations cannot "see" which coordinate directions, representing structural degeneracies.

2. Deterministic Equivalents via Local Laws:
   The authors derive deterministic equivalents for the prediction risk (bias and variance) in a vanishing-ridge regime. This requires extending the local law of random matrix theory (specifically from [4]) to track the spectral parameter explicitly as it approaches zero ($\lambda_n \downarrow 0$). This allows the analysis of the "hard edge" of the spectrum, where small eigenvalues accumulate.

3. Combinatorial Characterization:
   The behavior of the risk is linked to the Dulmage–Mendelsohn (DM) decomposition of the bipartite graph associated with the support of $S$ (the "variance graph").

   • Bias Support: Determined by the set of columns ($J_S$) that can be left unmatched by a maximum matching in the variance graph. These correspond to directions where the estimator retains bias.
   • Variance Peaks: Determined by a "switching condition" on the residual graph (after removing degenerate columns and their neighbors). A peak occurs when the residual graph loses the "column-side strong Hall property," forcing the smallest nonzero eigenvalues to the hard edge.

Key Contributions and Results

1. Mechanism for Multiple Descent:
   The paper demonstrates that a single design matrix and a single estimator can produce multiple risk peaks. These peaks are not artifacts of specific architectures but are intrinsic to the spectral degeneracy caused by the zero pattern of the covariance structure.

   • Bias: Persists on coordinates that are structurally unobservable (unmatched in the DM decomposition).
   • Variance: Diverges at specific aspect ratios where the residual design becomes "square" (the switching condition), causing a spike in risk.

2. Exact Rules for Peak Locations:
   The authors provide an exact combinatorial rule to predict the number and location of peaks:

   • The bias support is fixed by the degenerate column set $J_S$.
   • The variance peaks occur at the values of $\gamma$ where the residual sub-design (after removing $J_S$) transitions from having column-side strong Hall slack to failing it.
   • This is illustrated in examples such as data augmentation (Model 2) and heterogeneous subspaces (Model 1), where multiple thresholds emerge as different blocks of the design become square relative to the sample size.

3. Contrast with Positive-Definite Designs:
   The paper distinguishes between rank-deficient and positive-definite covariances.

   • If covariances are positive definite (even if heterogeneous and non-commuting), the zero pattern is empty. The authors conjecture, supported by simulations, that such designs retain only the single classical peak at $\gamma = 1$.
   • Multiple descent is driven specifically by the zeros (rank deficiency) in the covariance, not merely by heterogeneity or rotation.

4. Robustness and Universality:

   • The theoretical results hold for designs with independent entries and matching variance profiles, not just Gaussian ones (Remark 1). Simulations with Student-$t_3$ entries (infinite third moment) confirm that the peak structure persists.
   • The mechanism applies to real-world degenerate designs, such as text embeddings from pretrained transformers augmented with Gaussian noise, which exhibit multiple descent in empirical tests.

Significance
The paper claims that the phenomenon of multiple descent is not limited to complex, multi-component models but can arise from the structural zero pattern of a single, heterogeneous, or dependent design. By characterizing the risk peaks through the Dulmage–Mendelsohn decomposition of the variance profile's support, the authors provide a deterministic rule for predicting where risk spikes occur. This shifts the understanding of over-parameterized regression from a purely spectral perspective (based on aspect ratios) to a structural one (based on the observability of coordinates), highlighting that degeneracy in the data covariance is the primary driver of multiple descent.

The work also introduces a technical extension of local laws to the vanishing-ridge regime, enabling the analysis of the hard edge of the spectrum in the presence of structural zeros, a tool of independent interest to random matrix theory.