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

Technische Zusammenfassung: Das Null-Muster einer Designmatrix treibt den multiplen Abstieg in der überparametrisierten Regression

Problemstellung
Die überparametrisierte lineare Regression wurde bereits intensiv untersucht, doch bestehende theoretische Rahmenwerke stützen sich weitgehend auf zwei restriktive Annahmen: dass Kovariaten unabhängig sind und dass ihre Kovarianzmatrizen nicht-degeneriert (positiv definit) sind. Unter diesen Bedingungen zeigt das Vorhersagerisiko typischerweise eine „Double Descent“-Kurve mit einem einzelnen Peak am Interpolationsschwellenwert ($\gamma = p/n = 1$), der durch ein einzelnes Spektralereignis getrieben wird, bei dem die Designmatrix den Rang verliert.

Dieses Paper adresset die Lücke im Verständnis darüber, wann und warum multipler Abstieg (multiple descent)—das Auftreten mehrerer Risikopeaks—allein aus der Struktur der Daten entstehen kann, ohne auf architektonische Abstimmung, separate Feature-Blöcke oder unterschiedliche Kernel-Skalen zurückzugreifen. Die Autoren untersuchen die Ridge-Kleinste-Quadrate-Methode mit einem verschwindenden Strafterm ($\lambda_n \downarrow 0$) im proportionalen Regime ($p/n \to \gamma \in (0, \infty)$) unter zwei spezifischen Relaxierungen:

1. Heterogenität: Beobachtungen sind unabhängig, besitzen aber distinkte, potenziell rangdefiziente Kovarianzmatrizen.
2. Abhängigkeit: Beobachtungen sind durch endlich-rangige, separierbare Komponenten korreliert (z. B. Data Augmentation).

Methodik
Die zentrale methodische Innovation ist die Reduktion sowohl heterogener als auch abhängiger Gaußscher Designs auf ein Varianzprofil-Modell. Durch die Rotation der Daten in eine gemeinsame Eigenbasis (in der Kovarianzen gleichzeitig diagonalisierbar sind), transformieren die Autoren das Problem in die Analyse einer Gaußschen Matrix mit unabhängigen Einträgen, aber ungleichen Varianzen, definiert durch eine Varianzprofil-Matrix $S \in \mathbb{R}^{n \times p}$.

1. Varianzprofil-Reduktion:

   • Für Modell 1 (Heterogen), wobei $X_i = \Sigma_i^{1/2} Z_i$, wird das Profil $S$ aus den Eigenwerten der individuellen Kovarianzen $\Sigma_i$ konstruiert.
   • Für Modell 2 (Abhängig), wobei $X = \sum (\tilde{\Sigma}^{(m)})^{1/2} Z^{(m)} (\Sigma^{(m)})^{1/2}$, wird das Profil $S$ aus dem Produkt der Eigenwerte der Stichproben- und Koordinaten-Kovarianzkomponenten abgeleitet.
   • Entscheidend ist, dass das Null-Muster von $S$ (wo $S_{ij} = 0$) kodiert, welche Beobachtungen welche Koordinatenrichtungen nicht „sehen“ können, was strukturelle Degenerationen repräsentiert.

2. Deterministische Äquivalente via Local Laws:
   Die Autoren leiten deterministische Äquivalente für das Vorhersagerisiko (Bias und Varianz) in einem Regime mit verschwindender Regularisierung her. Dies erfordert die Erweiterung der Local Laws der Zufallsmatrientheorie (speziell aus [4]), um den Spektralparameter explizit zu verfolgen, während er sich Null nähert ($\lambda_n \downarrow 0$). Dies ermöglicht die Analyse der „harten Kante“ (hard edge) des Spektrums, wo kleine Eigenwerte akkumulieren.

3. Kombinatorische Charakterisierung:
   Das Verhalten des Risikos ist mit der Dulmage–Mendelsohn (DM)-Zerlegung des bipartiten Graphen verknüpft, der mit der Unterstützung (Support) von $S$ (dem „Varianz-Graphen“) assoziiert ist.

   • Bias-Support: Wird durch die Menge der Spalten ($J_S$) bestimmt, die durch eine maximale Paarung (Matching) im Varianz-Graphen nicht gematcht werden können. Dies entspricht Richtungen, in denen der Schätzer Bias beibehält.
   • Varianz-Peaks: Werden durch eine „Switching-Bedingung“ im Residuen-Graphen (nach Entfernung der degenerierten Spalten und ihrer Nachbarn) bestimmt. Ein Peak tritt auf, wenn der Residuen-Graph die „Spalten-seitige starke Hall-Eigenschaft“ verliert, was die kleinsten nicht-null Eigenwerte zur harten Kante zwingt.

Zentrale Beiträge und Ergebnisse

1. Mechanismus für multiplen Abstieg:
   Das Paper zeigt, dass ein einzelnes Design und ein einziger Schätzer mehrere Risikopeaks erzeugen können. Diese Peaks sind keine Artefakte spezifischer Architekturen, sondern intrinsisch durch die spektrale Degeneration verursacht durch das Null-Muster der Kovarianzstruktur.

   • Bias: Besteht auf Koordinaten, die strukturell nicht beobachtbar sind (ungematcht in der DM-Zerlegung).
   • Varianz: Divergiert bei spezifischen Aspektverhältnissen, bei denen das Residuen-Design „quadratisch“ wird (die Switching-Bedingung), was einen Spike im Risiko verursacht.

2. Exakte Regeln für die Lage der Peaks:
   Die Autoren liefern eine exakte kombinatorische Regel zur Vorhersage der Anzahl und Lage der Peaks:

   • Der Bias-Support wird durch die degenerierte Spaltenmenge $J_S$ fixiert.
   • Die Varianz-Peaks treten bei jenen Werten von $\gamma$ auf, bei denen das Residuen-Sub-Design (nach Entfernung von $J_S$) von der Erfüllung der starken Hall-Eigenschaft auf der Spaltenseite in ein Scheitern derselben übergeht.
   • Dies wird durch Beispiele wie Data Augmentation (Modell 2) und heterogene Subräume (Modell 1) illustriert, in denen multiple Schwellenwerte entstehen, während verschiedene Blöcke des Designs relativ zur Stichprobengröße quadratisch werden.

3. Kontrast zu positiv-definiten Designs:
   Das Paper unterscheidet zwischen rangdefizienten und positiv-definiten Kovarianzen.

   • Wenn Kovarianzen positiv definit sind (selbst wenn sie heterogen und nicht-kommutierend sind), ist das Null-Muster leer. Die Autoren konjekturieren, gestützt durch Simulationen, dass solche Designs nur den einzelnen klassischen Peak bei $\gamma = 1$ beibehalten.
   • Multipler Abstieg wird spezifisch durch die Nullen (Rangdefizienz) in der Kovarianz getrieben, nicht bloß durch Heterogenität oder Rotation.

4. Robustheit und Universalität:

   • Die theoretischen Ergebnisse gelten für Designs mit unabhängigen Einträgen und passenden Varianzprofilen, nicht nur für Gaußsche Designs (Remark 1). Simulationen mit Student-$t_3$-Einträgen (unendlicher dritter Moment) bestätigen, dass die Peak-Struktur bestehen bleibt.
   • Der Mechanismus ist anwendbar auf reale, degenerative Designs, wie etwa Text-Embeddings von vortrainierten Transformern, die mit Gaußschem Rauschen augmentiert wurden und in empirischen Tests multiplen Abstieg zeigen.

Bedeutung
Das Paper behauptet, dass das Phänomen des multiplen Abstiegs nicht auf komplexe, mehrkomponentige Modelle beschränkt ist, sondern aus dem strukturellen Null-Muster eines einzelnen, heterogenen oder abhängigen Designs resultieren kann. Durch die Charakterisierung der Risikopeaks mittels der Dulmage–Mendelsohn-Zerlegung des Supports des Varianzprofils liefern die Autoren eine deterministische Regel zur Vorhersage, wo Risikosprünge auftreten. Dies verschiebt das Verständnis der überparametrisierten Regression von einer rein spektralen Perspektive (basierend auf Aspektverhältnissen) hin zu einer strukturellen Perspektive (basierend auf der Beobachtbarkeit von Koordinaten) und hebt hervor, dass die Degeneration in der Datenkovarianz der primäre Treiber des multiplen Abstiegs ist.

Die Arbeit führt zudem eine technische Erweiterung der Local Laws auf das Regime der verschwindenden Regularisierung ein, was die Analyse der harten Kante des Spektrums in Gegenwart struktureller Nullen ermöglicht – ein Werkzeug von eigenständigem Interesse für die Zufallsmatrientheorie.