Sintesi Tecnica: Complessità Geometrica Dinamica Restritta

Definizione del Problema

Il documento affronta il costo geometrico dell'uso di precondizionatori strutturati nell'ottimizzazione. Mentre l'"ottimizzazione geometrodinamica" (Li, 2026) stabilisce un benchmark per la lunghezza minima del percorso invariante per affinità necessario per ridurre il numero di condizionamento di un obiettivo quadratico quando la metrica può evolvere liberamente all'interno del pieno cono positivo definito ($S^d_{++}$), i moderni ottimizzatori adattivi (es. AdaGrad, Adam, K-FAC, Shampoo) sono vincolati a specifiche famiglie metriche (diagonale, blocco-diagonale, Kronecker, low-rank).

Il problema centrale è quantificare la Complessità Geometrica Dinamica Restritta (RDGC): la distanza intrinseca del percorso da una metrica relativa iniziale $S_0$ a una classe di numero di condizionamento target $C_K$, vincolata dal fatto che il percorso debba rimanere entro una specifica famiglia strutturata $\mathcal{F} \subset S^d_{++}$. Il documento mira a determinare:

1. Se un numero di condizionamento target è raggiungibile all'interno di una specifica famiglia.
2. L'esatto costo geometrico (lunghezza del percorso) se raggiungibile.
3. Come certificare l'infeasibilità o fornire limiti superiori a tale costo.

Metodologia

Il framework opera su un obiettivo quadratico fortemente convesso $f(\theta) = \frac{1}{2}\theta^\top H \theta$ con Hessiano $H \succ 0$. L'evoluzione della metrica viene analizzata nel sistema di coordinate relativo definito da $S = H^{-1/2} G H^{-1/2}$, dove $G$ è il precondizionatore. La metrica di distanza utilizzata è la distanza riemanniana affine-invariante sul cono delle matrici positive definite:
$$d_{AI}(S_0, S_1) = \|\log(S_0^{-1/2} S_1 S_0^{-1/2})\|_F$$

La metodologia procede attraverso:

1. Definizione di Famiglie Realizzabili: Stabilire requisiti rigorosi per le famiglie metriche (positività definita, trattamento della scala, struttura di varietà smooth) per garantire che la lunghezza del percorso e la raggiungibilità siano ben definite.
2. Analisi della Raggiungibilità: Formulare l'esistenza di un precondizionatore che raggiunga un numero di condizionamento $K$ come un problema di fattibilità.
3. Costruzione di Certificati: Sviluppare certificati primali (metriche fattibili) e certificati duali (testimoni di infeasibilità) utilizzando disuguaglianze matriciali lineari (LMI) e la dualità della programmazione semidefinita (SDP).
4. Proiezione e Surrogati: Per famiglie complesse come i prodotti di Kronecker, il documento distingue tra:
   • Surrogati Spettrali: Modelli additivi del log-spettro che ignorano i vincoli degli autovettori.
   • Geometria Intrinseca: Proiezioni affine-invarianti sulla varietà delle metriche strutturate, utilizzando equazioni normali di traccia parziale.
5. Conteggio dei Livelli (Accounting Layers): Decomporre l'errore totale tra un ottimizzatore pratico e il benchmark teorico in quattro rapporti moltiplicativi: espressione, stima (proxy di curvatura), flusso (dinamiche continue) e discretizzazione.

Contributi Chiave e Risultati

1. Il Benchmark SPD Completo (Riferimento)

Il documento registra formalmente il benchmark non vincolato (Teorema 1): la distanza dallo spettro logaritmico iniziale all'insieme degli spettri con ampiezza $\le \log K$. Questo funge da limite inferiore per tutte le complessità ristrette.

2. Famiglie Diagonali e a Blocchi

• Raggiungibilità come LMI: Il documento prova che la raggiungibilità per le famiglie diagonali e a blocchi-diagonale è esattamente equivalente a un problema di fattibilità LMI: trovare $E \in \mathcal{F}$ tale che $E \preceq H \preceq KE$ (Teoremi 2 e 4).
• Certificati:
  • Primale: Una $E$ fattibile prova la raggiungibilità.
  • Duale: Un target non raggiungibile è certificato da un testimone duale SDP strutturato (Proposizione 3), includendo un particolare testimone di rango uno con "inversione di segno" per ostacoli cross-block (Corollario 2).
• Formula Esatta 2D: Viene derivata una formula chiusa esatta per la complessità diagonale in 2D, mostrando come le voci off-diagonal dell'Hessiano restringano l'intervallo di scala logaritmica fattibile (Teorema 3).

3. Famiglie di Kronecker

• Surrogato Spettrale vs. Geometria Intrinseca: Il documento separa il "surrogato spettrale di Kronecker" (modello additivo del log-spettro) dalla vera geometria intrinseca. Il surrogato è esatto solo quando l'Hessiano e la metrica condividono una base propria di Kronecker fissa (Proposizione 8).
• Proiezione Affine-Invariante: Il Teorema 6 stabilisce che la famiglia di Kronecker è una sottovarietà chiusa e totalmente geodetica. Fornisce una proiezione unica $G^\star$ caratterizzata da equazioni normali di traccia parziale ($Tr_B(R^\star)=0, Tr_A(R^\star)=0$).
• Convergenza del Solver: Viene proposto un solver basato su Armijo per proiettare sulla famiglia di Kronecker, con un residuo di arresto certificato e tasso di convergenza (Corollario 4).
• Raggiungibilità Relativa all'Hessiano: Il Teorema 8 fornisce un'equivalenza esatta per la raggiungibilità relativa all'Hessiano: esiste una metrica di Kronecker con $\kappa(G^{-1}H) \le K$ se e solo se esistono $A, B \succ 0$ tali che $B \otimes A \preceq H \preceq K(B \otimes A)$. Questo è un problema di fattibilità non convesso in generale, ma esatto nel regime a base fissa (Proposizione 9).
• Certificati Candidati: Qualsiasi metrica di Kronecker candidata che superi il test del numero di condizionamento fornisce un limite superiore finito sulla complessità ristretta (Proposizione 10).

4. Livelli di Estensione e Low-Rank

• Modelli Low-Rank: Il documento distingue tra forme additive, log-low-rank e inverse Woodbury. Fornisce un risultato di monotonicità spettrale per i modelli a base propria condivisa (Proposizione 13), mostrando che aumentare il budget di rango riduce la complessità spettrale.
• Interfacce Diagnostiche: Introduce interfacce per gestire le deviazioni pratiche:
  • Proxy di Curvatura: Quantifica come gli errori di proxy (es. Fisher vs. Hessiano) gonfino la soglia del numero di condizionamento richiesta (Proposizione 14).
  • Complessità Stocastica: Definisce limiti di alta probabilità per controller stocastici (Proposizione 15).
  • Flusso e Discretizzazione: Separa il costo di flussi continui non ottimali e degli errori di discretizzazione a passi finiti.

5. Fattorizzazione Esatta della Catena

Il Teorema 9 presenta un' "identità di contabilità" che decompone il rapporto tra la lunghezza del percorso algoritmico effettivo e il benchmark SPD completo in quattro fattori:
$$\frac{\text{Len}_{alg}}{D_K(S_0)} = R_{expr} \cdot R_{est} \cdot R_{flow} \cdot R_{disc}$$
Questi rappresentano i costi di espressione (restrizione strutturale), stima (errore di proxy), flusso (dinamiche subottimali) e discretizzazione (passi finiti). Il documento chiarisce che questi sono rapporti diagnostici; rappresentano "inflazioni di costo" (valori $\ge 1$) solo sotto ipotesi specifiche.

Significato e Rivendicazioni

Il documento sostiene di fornire un linguaggio matematico che trasforma le questioni sui precondizionatori strutturati in problemi di distanza geometrica, raggiungibilità e certificazione. La sua importanza risiede in:

1. Separazione delle Responsabilità: Separa rigorosamente gli aspetti di espressività di una famiglia metrica (può raggiungere il target?) da quelli di stima (la curvatura è nota?) e algoritmici (come viene percorso il cammino?).
2. Esattezza per le Famiglie Strutturate: Va oltre l'analisi euristica per fornire caratterizzazioni LMI esatte per le famiglie diagonali/a blocchi e teoremi di proiezione esatti per le famiglie di Kronecker.
3. Framework Diagnostico: Offre un modo sistematico per diagnosticare perché un ottimizzatore potrebbe non raggiungere un target di numero di condizionamento, attribuendo il fallimento a specifici gap geometrici (es. "la famiglia diagonale non può esprimere la curvatura necessaria" vs "il proxy è troppo rumoroso").
4. Benchmarking: Stabilisce un punto di riferimento (il benchmark SPD completo) rispetto al quale il "costo" delle approssimazioni strutturate può essere misurato.

Gli autori dichiarano esplicitamente che il documento non pretende di caratterizzare completamente specifici ottimizzatori (come Adam o K-FAC) o di fornire solver scalabili per il problema generale di raggiungibilità di Kronecker non convesso. Inveve, fornisce le specializzazioni "pronte per la certificazione" e le interfacce diagnostiche necessarie per analizzare tali metodi. Il repository include workflow deterministici semplificati per verificare tali certificati su piccole istanze quadratiche, servendo come controlli di riproducibilità della teoria piuttosto che come benchmark empirici per l'ottimizzazione su larga scala.