Resumen Técnico: Complejidad Geométrica Dinámica Restringida

Planteamiento del Problema

El artículo aborda el costo geomético del uso de precondicionadores estructurados en la optimización. Mientras que la "geometrodinámica de la optimización" (Li, 2026) establece un punto de referencia para la longitud de trayectoria mínima invariante por afinidad requerida para reducir el número de condición de una función cuadrática cuando la métrica puede evolucionar libremente dentro del pleno cono de matrices definidas positivas ($S^d_{++}$), los optimizadores adaptativos del mundo real (por ejemplo, AdaGrad, Adam, K-FAC, Shampoo) están restringidos a familias métricas específicas (diagonales, de bloque diagonal, de Kronecker, de bajo rango).

El problema central es cuantificar la Complejidad Geométrica Dinámica Restringida (RDGC): la distancia de trayectoria intrínseca desde una métrica relativa inicial $S_0$ hasta una clase de número de condición $C_K$, con la restricción de que la trayectoria debe permanecer dentro de una familia estructurada específica $\mathcal{F} \subset S^d_{++}$. El artículo busca determinar:

1. Si un número de condición objetivo es alcanzable dentro de una familia específica.
2. El costo geomético exacto (longitud de trayectoria) si es alcanzable.
3. Cómo certificar la inviabilidad o proporcionar cotas superiores sobre este costo.

Metodología

El marco de trabajo opera sobre una función cuadrática fuertemente convexa $f(\theta) = \frac{1}{2}\theta^\top H \theta$ con Hessiano $H \succ 0$. La evolución de la métrica se analiza en el sistema de coordenadas relativo definido por $S = H^{-1/2} G H^{-1/2}$, donde $G$ es el precondicionador. La métrica de distancia utilizada es la distancia de Riemann invariante por afinidad en el cono de matrices definidas positivas:
$$d_{AI}(S_0, S_1) = \|\log(S_0^{-1/2} S_1 S_0^{-1/2})\|_F$$

La metodología procede mediante:

1. Definición de Familias Realizables: Establecer requisitos estrictos para las familias métricas (definición positiva, tratamiento de escala, estructura de variedad suave) para asegurar que la longitud de la trayectoria y la alcanzabilidad estén bien definidas.
2. Análisis de Alcanzabilidad: Formular la existencia de un precondicionador que logre un número de condición $K$ como un problema de factibilidad.
3. Construcción de Certificados: Desarrollar certificados primales (métricas factibles) y certificados duales (testigos de inviabilidad) utilizando Desigualdades de Matriz Lineal (LMI) y dualidad de programación semidefinida (SDP).
4. Proyección y Sustitutos: Para familias complejas como los productos de Kronecker, el artículo distingue entre:
   • Sustitutos Espectrales: Modelos de espectro logarítmico aditivo que ignoran las restricciones de los autovectores.
   • Geometría Intrínseca: Proyecciones invariantes por afinidad sobre la variedad de métricas estructuradas, utilizando ecuaciones normales de traza parcial.
5. Capas de Contabilidad: Descomponer el error total entre un optimizador práctico y el punto de referencia teórico en cuatro razones multiplicativas: expresión, estimación (proxy de curvatura), flujo (dinámicas continuas) y discretización.

Contribuciones Clave y Resultados

1. El Punto de Referencia SPD Completo (Referencia)

El artículo registra formalmente el benchmark no restringido (Teorema 1): la distancia desde el espectro logarítmico inicial hacia el conjunto de espectros con ancho $\le \log K$. Esto sirve como el límite inferior para todas las complejidades restringidas.

2. Familias Diagonales y de Bloque

• Alcanzabilidad como LMI: El artículo demuestra que la alcanzabilidad para las familias diagonal y de bloque diagonal es exactamente equivalente a un problema de factibilidad LMI: encontrar $E \in \mathcal{F}$ tal que $E \preceq H \preceq KE$ (Teoremas 2 y 4).
• Certificados:
  • Primal: Un $E$ factible prueba la alcanzabilidad.
  • Dual: Un objetivo inviable es certificado por un testigo dual de SDP estructurado (Proposición 3), incluyendo un testigo específico de rango uno con "cambio de signo" para obstrucciones de bloques cruzados (Corolario 2).
• Fórmula Exacta en 2D: Se deriva una fórmula cerrada exacta para la complejidad diagonal en 2D, mostrando cómo las entradas fuera de la diagonal del Hessiano reducen el intervalo de escala logarítmica factible (Teorema 3).

3. Familias de Kronecker

• Sustituto Espectral vs. Geometría Intrínseca: El artículo separa el "sustituto espectral de Kronecker" (modelo de espectro logarítmico aditivo) de la verdadera geometría intrínseca. El sustituto es exacto solo cuando el Hessiano y la métrica comparten una base de autovectores de Kronecker fija (Proposición 8).
• Proyección Invariante por Afinidad: El Teorema 6 establece que la familia de Kronecker es una subvariedad cerrada y totalmente geodésica. Proporciona una proyección única $G^\star$ caracterizada por ecuaciones normales de traza parcial ($Tr_B(R^\star)=0, Tr_A(R^\star)=0$).
• Convergencia del Solucionador: Se propone un solucionador basado en Armijo para proyectar sobre la familia de Kronecker, con un residuo de parada certificado y tasa de convergencia (Corolario 4).
• Alcanzabilidad Relativa al Hessiano: El Teorema 8 proporciona una equivalencia exacta para la alcanzabilidad relativa al Hessiano: existe una métrica de Kronecker con $\kappa(G^{-1}H) \le K$ si y solo si existen $A, B \succ 0$ tales que $B \otimes A \preceq H \preceq K(B \otimes A)$. Este es un problema de factibilidad no convexo en general, pero exacto en el régimen de base fija (Proposición 9).
• Certificados Candidatos: Cualquier métrica de Kronector candidata que pase la prueba del número de condición proporciona una cota superior finita sobre la complejidad restringida (Proposición 10).

4. Modelos de Bajo Rango y Capas de Extensión

• Modelos de Bajo Rango: El artículo distingue entre formas aditivas, de bajo rango logarítmico e inversas de Woodbury. Proporciona un resultado de monotonicidad espectral para modelos de base de autovectores compartida (Proposición 13), mostrando que aumentar el presupuesto de rango reduce la complejidad espectral.
• Interfaces de Diagnóstico: El artículo introduce interfaces para manejar desviaciones prácticas:
  • Proxies de Curvatura: Cuantifica cómo los errores de proxy (por ejemplo, Fisher vs. Hessiano) inflan el umbral del número de condición requerido (Proposición 14).
  • Complejidad Estocástica: Define límites de alta probabilidad para controladores estocásticos (Proposición 15).
  • Flujo y Discretización: Separa el costo de flujos continuos no óptimos y los errores de discretización de pasos finitos.

5. Factorización de Cadena Exacta

El Teorema 9 presenta una "identidad de contabilidad" que descompone la razón entre la longitud de trayectoria algorítmica real y el benchmark SPD completo en cuatro factores:
$$\frac{\text{Len}_{alg}}{D_K(S_0)} = R_{expr} \cdot R_{est} \cdot R_{flow} \cdot R_{disc}$$
Estos representan los costos de expresión (restricción estructural), estimación (error de proxy), flujo (dinámicas subóptimas) y discretización (pasos finitos). El artículo aclara que estos son ratios diagnósticos; solo representan "inflaciones de costo" (valores $\ge 1$) bajo hipótesis específicas.

Significado y Reivindicaciones

El artículo afirma proporcionar un lenguaje matemático que transforma las cuestiones de precondicionadores estructurales en problemas de distancia geométrica, alcanzabilidad y certificados. Su importancia radica en:

1. Separación de Preocupaciones: Separa rigurosamente la expresividad de una familia métrica (¿puede alcanzar el objetivo?) de la estimación (¿se conoce la curvatura?) y los aspectos algorítmicos (¿cómo se recorre la trayectoria?).
2. Exactitud para Familias Estructuradas: Va más allá del análisis heurístico para proporcionar caracterizaciones LMI exactas para familias de bloque diagonal y teoremas de proyección exactos para familias de Kronecker.
3. Marco de Diagnóstico: Ofrece una forma sistemática de diagnosticar por qué un optimizador podría no alcanzar un objetivo de número de condición, atribuyendo el fallo a brechas geométricas específicas (por ejemplo, "la familia diagonal no puede expresar la curvatura necesaria" frente a "el proxy es demasiado ruidoso").
4. Benchmarking: Establece un punto de referencia (el benchmark SPD completo) contra el cual se puede medir el "costo" de las aproximaciones estructuradas.

Los autores declaran explícitamente que el artículo no pretende caracterizar completamente optimizadores específicos (como Adam o K-FAC) ni proporcionar solucionadores escalables para el problema general de alcanzabilidad de Kronecker no convexo. En su lugar, proporciona las especializaciones "listas para certificados" y las interfaces de diagnóstico necesarias para analizar tales métodos. El repositorio incluye flujos de trabajo deterministas de juguete para verificar estos certificados en instancias cuadráticas pequeñas, sirviendo como verificaciones de reproducibilidad de la teoría más que como benchmarks empíricos para la optimización a gran escala.