Technisches Resümee: Restriktierte Dynamische Geometrische Komplexität

Problemstellung

Die Arbeit adressiert die geometrischen Kosten der Verwendung strukturierter Präkonditionierer in der Optimierung. Während die „Optimierungs-Geometrodynamik“ (Li, 2026) einen Benchmark für die minimale affin-invariante Pfadlänge etabliert, die erforderlich ist, um die Konditionszahl einer quadratischen Zielfunktion zu reduzate, wenn die Metrik innerhalb des vollen positiven definiten Kegels ($S^d_{++}$) frei evolvieren kann, sind reale adaptive Optimierer (z. B. AdaGrad, Adam, K-FAC, Shampoo) auf spezifische Metrikfamilien beschränkt (diagonal, blockdiagonal, Kronecker, Low-Rank).

Das Kernproblem besteht darin, die Restriktierte Dynamische Geometrische Komplexität (RDGC) zu quantifizieren: die intrinsische Pfaddistanz von einer initialen relativen Metrik $S_0$ zu einer Ziel-Konditionszahl-Klasse $C_K$, unter der Bedingung, dass der Pfad innerhalb einer spezifizierten strukturierten Familie $\mathcal{F} \subset S^d_{++}$ verbleiben muss. Die Arbeit untersucht folgende Fragen:

1. Ob eine Ziel-Konditionszahl innerhalb einer spezifischen Familie erreichbar ist.
2. Die exakten geometrischen Kosten (Pfadlänge), falls diese erreichbar ist.
3. Wie die Unerreichbarkeit zertifiziert oder obere Schranken auf diese Kosten angegeben werden können.

Methodik

Das Framework operiert auf einer stark konvexen quadratischen Zielfunktion $f(\theta) = \frac{1}{2}\theta^\top H \theta$ mit Hesse-Matrix $H \succ 0$. Die Metrikevolution wird im relativen Koordinatensystem analysiert, das durch $S = H^{-1/2} G H^{-1/2}$ definiert ist, wobei $G$ der Präkonditionier ist. Die verwendete Distanzmetrik ist die affin-invariante Riemannsche Distanz auf dem Kegel der positiven definiten Matrizen:
$$d_{AI}(S_0, S_1) = \|\log(S_0^{-1/2} S_1 S_0^{-1/2})\|_F$$

Die Methodik verläuft wie folgt:

1. Definition realisierbarer Familien: Etablierung strenger Anforderungen an Metrikfamilien (positive Definitheit, Skalenbehandlung, glatte Mannigfaltigkeitsstruktur), um sicherzustellen, dass Pfadlänge und Erreichbarkeit wohldefiniert sind.
2. Erreichbarkeitsanalyse: Formulierung der Existenz eines Präkonditionierers, der eine Ziel-Konditionszahl $K$ erreicht, als ein Zulässigkeitsproblem.
3. Zertifikatskonstruktion: Entwicklung von Primal-Zertifikaten (zulässige Metriken) und Dual-Zertifikaten (Unerreichbarkeits-Zeugen) unter Verwendung von Linearen Matrizen-Ungleichungen (LMI) und Semidefinitem Programmierung (SDP)-Dualität.
4. Projektion und Surrogate: Für komplexe Familien wie Kronecker-Produkte unterscheidet die Arbeit zwischen:
   • Spektralen Surrogaten: Additive Log-Spektrum-Modelle, welche die Eigenvektor-Beschränkungen ignorieren.
   • Intrinsischer Geometrie: Affin-invariante Projektionen auf die Mannigfaltigkeit strukturierter Metriken unter Nutzung partieller Spur-Normalgleichungen.
5. Berücksichtigung von Schichten (Layers): Dekomposition des Gesamteffekts zwischen einem praktischen Optimierer und dem theoretischen Benchmark in vier multiplikative Verhältnisse: Expression (Ausdrucksfähigkeit), Estimation (Krümmungs-Proxy), Flow (kontinuierliche Dynamik) und Discretization (Diskretisierung).

Zentrale Beiträge und Ergebnisse

1. Der volle SPD-Benchmark (Referenz)

Die Arbeit dokumentiert formal den unbeschränkten Benchmark (Theorem 1): die Distanz vom initialen Log-Spektrum zur Menge der Spektren mit einer Breite $\le \log K$. Dies dient als untere Schranke für alle restriktierten Komplexitäten.

2. Diagonale und Block-Familien

• Erreichbarkeit als LMI: Die Arbeit beweist, dass die Erreichbarkeit für diagonale und blockdiagonale Familien exakt äquivalent zu einem LMI-Zulässigkeitsproblem ist: die Suche nach einem $E \in \mathcal{F}$, sodass $E \preceq H \preceq KE$ gilt (Theorem 2 und 4).
• Zertifikate:
  • Primal: Ein zulässiges $E$ beweist die Erreichbarkeit.
  • Dual: Eine unerreichbare Zielgröße wird durch einen strukturierten SDP-Dual-Zeugen zertifiziert (Proposition 3), einschließlich eines spezifischen „Sign-Flip“-Rang-eins-Zeugen für Cross-Block-Hindernisse (Corollary 2).
• Exakte 2D-Formel: Eine exakte geschlossene Formel wird für die diagonale Komplexität in 2D hergeleitet, die zeigt, wie Off-Diagonal-Hesse-Einträge das zulässige Log-Skalen-Intervall einschränken (Theorem 3).

3. Kronecker-Familien

• Spektrales Surrogat vs. Intrinsische Geometrie: Die Arbeit trennt das „Kronecker-Spektral-Surrogat“ ( additives Log-Spektrum-Modell) von der wahren intrinsischen Geometrie. Das Surrogat ist nur dann exakt, wenn die Hesse-Matrix und die Metrik eine feste Kronecker-Eigenbasis teilen (Proposition 8).
• Affin-invariante Projektion: Theorem 6 etabliert, dass die Kronecker-Familie eine geschlossene, total geodätische Untermannigfaltigkeit ist. Sie liefert eine eindeutige Projektion $G^\star$, die durch partielle Spur-Normalgleichungen charakterisiert ist ($Tr_B(R^\star)=0, Tr_A(R^\star)=0$).
• Solver-Konvergenz: Ein Armijo-basierter Solver wird für die Projektion auf die Kronecker-Familie vorgeschlagen, inklusive eines zertifizierten Stopp-Residuums und einer Konvergenzrate (Corollary 4).
• Hesse-relative Erreichbarkeit: Theorem 8 liefert eine exakte Äquivalenz für die Hesse-relative Erreichbarkeit: Eine Kronecker-Metrik mit $\kappa(G^{-1}H) \le K$ existiert genau dann, wenn es $A, B \succ 0$ gibt, sodass $B \otimes A \preceq H \preceq K(B \otimes A)$. Dies ist im Allgemeinen ein nichtkonvexes Zulässigkeitsproblem, aber exakt im Regime der festen Basis (Proposition 9).
• Kandidaten-Zertifikate: Jede Kandidaten-Kronecker-Metrik, die den Konditionszahl-Test besteht, liefert eine endliche obere Schranke auf die restriktierte Komplexität (Proposition 10).

4. Low-Rank Modelle und Erweiterungsschichten

• Low-Rank Modelle: Die Arbeit unterscheidet zwischen additiven, Log-Low-Rank- und inversen Woodbury-Formen. Sie liefert ein spektrales Monotonie-Resultat für Modelle mit gemeinsamer Eigenbasis (Proposition 13), welches zeigt, dass ein höheres Rank-Budget die spektrale Komplexität reduziert.
• Diagnostische Schnittstellen: Es werden Schnittstellen zur Handhabung praktischer Abweichungen eingeführt:
  • Krümmungs-Proxies: Quantifiziert, wie Proxy-Fehler (z. B. Fisher vs. Hesse) die erforderliche Konditionszahl-Schwelle aufblähen (Proposition 14).
  • Stochastische Komplexität: Definiert Wahrscheinlichkeits-Schranken für stochastische Controller (Proposition 15).
  • Flow und Diskretisierung: Trennt die Kosten suboptimaler kontinuierlicher Flows und endlicher Diskretisierungsschritte.

5. Exakte Ketten-Faktorisierung

Theorem 9 präsentiert eine „Accounting Identity“, die das Verhältnis zwischen der tatsächlichen algorithmischen Pfadlänge und dem vollen SPD-Benchmark dekomponiert:
$$\frac{\text{Len}_{alg}}{D_K(S_0)} = R_{expr} \cdot R_{est} \cdot R_{flow} \cdot R_{disc}$$
Diese stehen für die Kosten von Expression (strukturelle Einschränkung), Estimation (Proxy-Fehler), Flow (suboptimale Dynamik) und Discretization (endliche Schritte). Die Arbeit stellt klar, dass dies diagnostische Verhältnisse sind; sie repräsentieren nur „Kostenaufblähungen“ (Werte $\ge 1$) unter spezifischen Hypothesen.

Bedeutung und Ansprüche

Die Arbeit beansprucht, eine mathematische Sprache bereitzustellen, die Fragen zu strukturierten Präkonditionierern in geometrische Distanz-, Erreichbarkeits- und Zertifikats-Probleme transformiert. Ihre Bedeutung liegt in:

1. Trennung der Belange (Separation of Concerns): Sie trennt rigoros die Expressivität einer Metrikfamilie (Kann sie das Ziel erreichen?) von den Aspekten der Estimation (Ist die Krümmung bekannt?) und der Algorithmik (Wie wird der Pfad durchlaufen?).
2. Exaktheit für strukturierte Familien: Sie geht über heuristische Analysen hinaus und liefert exakte LMI-Charakterisierungen für diagonale/blockdiagonale Familien sowie exakte Projektionstheoreme für Kronecker-Familien.
3. Diagnostischer Rahmen: Sie bietet eine systematische Methode, um zu diagnostizieren, warum ein Optimierer ein Ziel-Konditionszahl nicht erreicht, indem sie das Versagen spezifischen geometrischen Lücken zuordnet (z. B. „die diagonale Familie kann die notwendige Krümmung nicht ausdrücken“ vs. „der Proxy ist zu verrauscht“).
4. Benchmarking: Sie etabliert einen Referenzpunkt (den vollen SPD-Benchmark), gegen den die „Kosten“ strukturierter Approximationen gemessen werden können.

Die Autoren betonen explizit, dass die Arbeit nicht beansprucht, spezifische Optimierer (wie Adam oder K-FAC) vollständig zu charakterisieren oder skalierbare Solver für das allgemeine nichtkonvexe Kronecker-Erreichbarkeitsproblem bereitzustellen. Stattdessen liefert sie die theoretischen, „zertifikat-bereiten“ Spezialisierungen und diagnostischen Schnittstellen, die zur Analyse solcher Methoden notwendig sind. Das Repository enthält deterministische Toy-Workflows, um diese Zertifikate an kleinen quadratischen Instanzen zu verifizieren, was als Reproduzierbarkeitsprüfung der Theorie und nicht als empirischer Benchmark für großskalige Optimierung dient.