Technische Samenvatting: Beperkte Dynamische Geometrische Complexiteit

Probleemstelling

Het artikel behandelt de geometrische kosten van het gebruik van gestructureerde preconditioners in optimalisatie. Terwijl "optimalisatie-geometrodynamica" (Li, 2026) een benchmark vaststelt voor de minimale affien-invariante padlengte die vereist is om de conditiegetal van een kwadratisch object te reduceren wanneer de metriek vrij kan evolueren binnen de volledige positief-definiete kegel ($S^d_{++}$), zijn real-world adaptieve optimizers (bijv. AdaGrad, Adam, K-FAC, Shampoo) beperkt tot specifieke metriek-families (diagonaal, blok-diagonaal, Kronecker, low-rank).

De kern van het probleem is het kwantificeren van de Beperkte Dynamische Geometrische Complexiteit (RDGC): de intrinsieke padafstand van een initiële relatieve metriek $S_0$ naar een doel-conditiegetal-klasse $C_K$, geconstraineerd door het feit dat het pad binnen een gespecificeerde gestructureerde familie $\mathcal{F} \subset S^d_{++}$ moet blijven. Het artikel beoogt te bepalen:

1. Of een doel-conditiegetal bereikbaar is binnen een specifieke familie.
2. De exacte geometrische kosten (padlengte) indien bereikbaar.
3. Hoe onbereikbaarheid gecertificeerd kan worden of hoe bovengrenzen op deze kosten kunnen worden geboden.

Methodologie

Het raamwerk opereert op een sterk convexe kwadratische doelfunctie $f(\theta) = \frac{1}{2}\theta^\top H \theta$ met Hessiaan $H \succ 0$. De evolutie van de metriek wordt geanalyseerd in het relatieve coördinatenstelsel gedefinieerd door $S = H^{-1/2} G H^{-1/2}$, waarbij $G$ de preconditioner is. De gebruikte afstandmetriek is de affien-invariante Riemanniaanse afstand op de kegel van positief-definiete matrices:
$$d_{AI}(S_0, S_1) = \|\log(S_0^{-1/2} S_1 S_0^{-1/2})\|_F$$

De methodologie verloopt als volgt:

1. Definiëren van Realiseerbare Families: Het vaststellen van strikte vereisten voor metriek-families (positief definitheid, schaalbehandeling, gladde manifoldstructuur) om te waarborgen dat padlengte en bereikbaarheid goed gedefinieerd zijn.
2. Bereikbaarheidsanalyse: Het formuleren van de existentie van een preconditioner die een doel-conditiegetal $K$ bereikt als een haalbaarheidsprobleem.
3. Certificaatconstructie: Het ontwikkelen van primaire certificaten (haalbare metrieken) en duale certificaten (onhaalbaarheidsgetuigen) met behulp van Linear Matrix Inequalities (LMI's) en semidefinitie programmering (SDP) dualiteit.
4. Projectie en Surrogaten: Voor complexe families zoals Kronecker-producten maakt het artikel onderscheid tussen:
   • Spectrale Surrogaten: Additieve log-spectraalmodellen die eigenvector-restricties negeren.
   • Intrinsieke Geometrie: Affien-invariante projecties op de manifold van gestructureerde metrieken, gebruikmakend van partial-trace normale vergelijkingen.
5. Verantwoordingslagen: Het deconstrueren van de totale fout tussen een praktische optimizer en de theoretische benchmark in vier multiplicatieve ratio's: expressie, schatting (kromming-proxy), flow (continue dynamica) en discretisatie.

Belangrijkste Bijdragen en Resultaten

1. De Volledige SPD Benchmark (Referentie)

Het artikel legt formeel de onbeperkte benchmark vast (Theorema 1): de afstand van het initiële log-spectrum naar de verzameling spectra met breedte $\le \log K$. Dit dient als de ondergrens voor alle beperkte complexiteiten.

2. Diagonaal en Blok-families

• Bereikbaarheid als LMI: Het artikel bewijst dat bereikbaarheid voor diagonaal en blok-diagonaal families exact equivalent is aan een LMI-haalbaarheidsprobleem: het vinden van $E \in \mathcal{F}$ zodanig dat $E \preceq H \preceq KE$ (Theorema's 2 en 4).
• Certificaten:
  • Primair: Een haalbare $E$ bewijst bereikbaarheid.
  • Duaal: Een onhaalbaar doel wordt gecertificeerd door een gestructureerde SDP duale getuige (Proposition 3), inclus_ief een specifieke "sign-flip" rank-één getuige voor cross-block obstructies (Corollary 2).
• Exacte 2D Formule: Een exacte gesloten vorm formule wordt afgeleid voor de diagonale complexiteit in 2D, waarbij wordt getoond hoe off-diagonaal Hessiaanse entries het haalbare log-schaalinterval verkleinen (Theorema 3).

3. Kronecker-families

• Spectrale Surrogaat vs. Intrinsieke Geometrie: Het artikel scheidt de "Kronecker spectrale surrogaat" (additief log-spectraalmodel) van de ware intrinsieke geometrie. De surrogaat is alleen exact wanneer de Hessiaan en de metriek een vaste Kronecker-eigenbasis delen (Proposition 8).
• Affien-Invariante Projectie: Theorema 6 stelt vast dat de Kronecker-familie een gesloten, totaal geodesische submanifold is. Het biedt een unieke projectie $G^\star$ gekarakteriseerd door partial-trace normale vergelijkingen ($Tr_B(R^\star)=0, Tr_A(R^\star)=0$).
• Solver Convergentie: Een Armijo-gebaseerde solver wordt voorgesteld voor het projecteren op de Kronecker-familie, met een gecertificeerd stopprobleem-residue en convergentiesnelheid (Corollary 4).
• Hessiaan-Relatieve Bereikbaarheid: Theorema 8 biedt een exacte equivalentie voor Hessiaan-relatieve bereikbaarheid: er bestaat een Kronecker-metriek met $\kappa(G^{-1}H) \le K$ indien en slechts indien er $A, B \succ 0$ bestaan zodanig dat $B \otimes A \preceq H \preceq K(B \otimes A)$. Dit is in het algemeen een niet-convexe haalbaarheidsvraag, maar exact in het regime van de vaste basis (Proposition 9).
• Kandidaat-Certificaten: Elke kandidaat Kronecker-metriek die de conditiegetal-test doorstaat, levert een eindige bovengrens op de beperkte complexiteit (Proposition -10).

4. Low-Rank en Uitbreidingslagen

• Low-Rank Modellen: Het artikel maakt onderscheid tussen additieve, log-low-rank en inverse Woodbury-vormen. Het biedt een spectrale monotoniciteitsresultaat voor modellen met een gedeelde eigenbasis (Proposition 13), wat aantoont dat het verhogen van de rank-budget de spectrale complexiteit vermindert.
• Diagnostische Interfaces: Het introduceert interfaces voor het afhandelen van praktische afwijkingen:
  • Kromming-Proxies: Kwantificeert hoe proxy-fouten (bijv. Fisher vs. Hessiaan) de vereiste conditiegetal-drempel opblazen (Proposition 14).
  • Stochastische Complexiteit: Definieert hoog-waarschijnlijkheid grenzen voor stochastische controllers (Proposition 15).
  • Flow en Discretisatie: Scheidt de kosten van niet-optimale continue flows en eindige-stap discretisatiefouten.

5. Exacte Ketenfactorisatie

Theorema 9 presenteert een "boekhoudkundige identiteit" die de ratio tussen de werkelijke algoritmische padlengte en de volledige SPD benchmark deconstrueert in vier factoren:
$$\frac{\text{Len}_{alg}}{D_K(S_0)} = R_{expr} \cdot R_{est} \cdot R_{flow} \cdot R_{disc}$$
Deze vertegenwoordigen de kosten van expressie (structurele restrictie), schatting (proxy-fout), flow (suboptimale dynamica) en discretisatie (eindige stappen). Het artikel verduidelijkt dat dit diagnostische ratio's zijn; ze vertegenwoordigen alleen "kosteninflaties" (waarden $\ge 1$) onder specifieke hypothesen.

Betekenis en Claims

Het artikel beweert een wiskundige taal te bieden die vragen over gestructureerde preconditioners transformeert naar geometrische afstand, bereikbaarheid en certificaatproblemen. De betekenis ligt in:

1. Scheiding van Zaken: Het scheidt rigoureus de expressiviteit van een metriek-familie (kan het het doel bereiken?) van de schatting (is de kromming bekend?) en de algoritmische aspecten (hoe wordt het pad afgelegd?).
2. Exactheid voor Gestructureerde Families: Het gaat verder dan heuristische analyse door exacte LMI-karakterisaties te bieden voor diagonaal/blok-families en exacte projectietheorema's voor Kronecker-families.
3. Diagnostisch Raamwerk: Het biedt een systematische manier om te diagnosticeren waarom een optimizer mogelijk een doel-conditiegetal niet bereikt, door de fout toe te schrijven aan specifieke geometrische hiaten (bijv. "de diagonale familie kan de noodzakelijke kromming niet uitdrukken" versus "de proxy is te ruisachtig").
4. Benchmarking: Het vestigt een referentiepunt (de volledige SPD benchmark) waartegen de "kosten" van gestructureerde benaderingen gemeten kunnen worden.

De auteurs verklaren expliciet dat het artikel niet beweert specifieke optimizers (zoals Adam of K-FAC) volledig te karakteriseren of schaalbare solvers te bieden voor het algemene niet-convexe Kronecker-bereikbaarheidsprobleem. In plaats daarvan biedt het de theoretische "certificaat-klare" specialisaties en diagnostische interfaces die nodig zijn om dergelijke methoden te analyseren. De repository bevat deterministische toy-workflows om deze certificaten te verifiëren op kleine kwadratische instanties, dienend als reproduceerbaarheidschecks voor de theorie in plaats van empirische benchmarks voor grootschalige optimalisatie.