🔢 mathematics

Restricted Dynamic Geometric Complexity: Certificates for Structured Preconditioning

This paper introduces "Restricted Dynamic Geometric Complexity" as an intrinsic certificate framework that transforms structural preconditioning challenges into geometric distance and reachability problems, providing provable monotonicity principles, linear matrix inequality formulations, and exact complexity formulas for optimizing under restricted metric families.

Original authors: Zavier Li

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zavier Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a hilly landscape to find the lowest valley (the best solution to a problem). In the world of math and computer science, this is called optimization. To move efficiently, you need a map that tells you how steep the hills are. This map is called the Hessian.

However, real-world maps are often too detailed or too expensive to carry. So, we use preconditioners—simplified, "good enough" maps that help us move faster.

This paper is a theoretical guidebook that measures how much extra effort it takes to use these simplified maps compared to a perfect, full-detail map. It does this by treating the map itself as a shape that can stretch and shrink (geometry).

Here is the breakdown of the paper's ideas using simple analogies:

1. The Perfect Map vs. The Simplified Map

The Full Map (The Benchmark): Imagine you have a perfect, flexible rubber sheet that can stretch in any direction to flatten the hills perfectly. The paper first calculates the absolute minimum distance you need to travel on this perfect sheet to make the hills easy to climb. This is the "gold standard."
The Simplified Maps (The Restriction): In real life, we can't carry a perfect sheet. We use specific types of simplified maps:
- Diagonal: A map that only stretches North-South or East-West, but never diagonally. (Like the maps used by common tools like Adam or AdaGrad).
- Block: A map that stretches in chunks (like a grid of squares).
- Kronecker: A map made by combining two smaller, simpler maps (like a Lego structure).
- Low-Rank: A map that only stretches in a few specific directions.

2. The Core Question: "How Far Can We Get?"

The paper asks: If we are forced to use a simplified map, how far away from the "perfect" solution are we?

It calls this distance "Restricted Dynamic Geometric Complexity."

Analogy: Imagine you need to walk from Point A to Point B.
- With the Perfect Map, you can walk in a straight line.
- With a Restricted Map (e.g., you can only walk North, South, East, or West), you might have to take a zig-zag path.
- The paper calculates the exact length of that zig-zag path compared to the straight line. If the zig-zag is too long, it means your simplified map is too weak to solve the problem efficiently.

3. The "Certificate" (The Pass/Fail Test)

One of the paper's main contributions is creating a test (a certificate) to see if a simplified map can even reach the goal.

The LMI Test: For simple maps (Diagonal or Block), the paper shows you can run a specific math check (like a checklist) to see if it's possible to flatten the hills enough.
- If the test passes: Great! A solution exists.
- If the test fails: The paper provides a "witness" (a proof) showing exactly why it's impossible. It's like a referee blowing a whistle and saying, "No matter how you stretch this specific type of map, you can never flatten these hills."

4. The "Kronecker" Puzzle

The paper dives deep into a specific type of map called Kronecker (used by advanced tools like K-FAC).

The Problem: These maps are tricky because they have "gauge" issues (like a map that can be scaled up or down without changing the shape).
The Solution: The authors developed a way to "project" a perfect map onto the Kronecker family. They proved that there is a unique "best fit" Kronecker map for any situation.
The Catch: They found that sometimes the "best fit" Kronecker map is still far away from the goal because the hills are twisted in a way the Kronecker map simply cannot handle. They created a formula to measure this "mismatch."

5. The "Accounting" of Errors

The paper realizes that in real life, we don't just have a simplified map; we also have:

Noisy Data: We don't know the hills perfectly; we only have a guess (a proxy).
Step-by-Step Movement: We don't move smoothly; we take discrete steps.
Flow: We might not move in the most efficient direction.

The paper creates an accounting identity (a math equation) that breaks down the total distance traveled into four parts:

Expression Cost: How much extra distance is caused by using a simplified map?
Estimation Cost: How much extra distance is caused by using a noisy guess of the hills?
Flow Cost: How much extra distance is caused by moving inefficiently?
Discretization Cost: How much extra distance is caused by taking steps instead of gliding?

This allows researchers to look at a slow optimizer and say, "Ah, the problem isn't the map; the problem is that our guess of the hills is too noisy," or "The map is too simple."

Summary

This paper doesn't propose a new algorithm to make computers faster. Instead, it builds a ruler and a set of tests to measure the theoretical limits of existing optimization tools.

It tells us exactly how much "geometry" we lose when we restrict our tools to be simpler (diagonal, block, Kronecker).
It gives us proofs to show when a tool is fundamentally incapable of solving a problem.
It provides a language to separate the cost of the tool's design from the cost of using noisy data or taking imperfect steps.

In short, it turns the question "Is this optimizer good?" into a precise geometric measurement of "How far is this specific map from the perfect solution?"

Technical Summary: Restricted Dynamic Geometric Complexity

Problem Statement

The paper addresses the geometric cost of using structured preconditioners in optimization. While "optimization geometrodynamics" (Li, 2026) establishes a benchmark for the minimum affine-invariant path length required to reduce the condition number of a quadratic objective when the metric can evolve freely within the full positive-definite cone ( $S^d_{++}$ ), real-world adaptive optimizers (e.g., AdaGrad, Adam, K-FAC, Shampoo) are constrained to specific metric families (diagonal, block-diagonal, Kronecker, low-rank).

The core problem is to quantify the Restricted Dynamic Geometric Complexity (RDGC): the intrinsic path distance from an initial relative metric $S_0$ to a target condition-number class $C_K$ , constrained such that the path must remain within a specified structured family $\mathcal{F} \subset S^d_{++}$ . The paper seeks to determine:

Whether a target condition number is reachable within a specific family.
The exact geometric cost (path length) if reachable.
How to certify infeasibility or provide upper bounds on this cost.

Methodology

The framework operates on a strongly convex quadratic objective $f(\theta) = \frac{1}{2}\theta^\top H \theta$ with Hessian $H \succ 0$ . The metric evolution is analyzed in the relative coordinate system defined by $S = H^{-1/2} G H^{-1/2}$ , where $G$ is the preconditioner. The distance metric used is the affine-invariant Riemannian distance on the cone of positive-definite matrices:
$d_{AI}(S_0, S_1) = \|\log(S_0^{-1/2} S_1 S_0^{-1/2})\|_F$

The methodology proceeds by:

Defining Realizable Families: Establishing strict requirements for metric families (positive definiteness, scale treatment, smooth manifold structure) to ensure path length and reachability are well-defined.
Reachability Analysis: Formulating the existence of a preconditioner achieving a target condition number $K$ as a feasibility problem.
Certificate Construction: Developing primal certificates (feasible metrics) and dual certificates (infeasibility witnesses) using Linear Matrix Inequalities (LMIs) and semidefinite programming (SDP) duality.
Projection and Surrogates: For complex families like Kronecker products, the paper distinguishes between:
- Spectral Surrogates: Additive log-spectrum models that ignore eigenvector constraints.
- Intrinsic Geometry: Affine-invariant projections onto the manifold of structured metrics, utilizing partial-trace normal equations.
Accounting Layers: Decomposing the total error between a practical optimizer and the theoretical benchmark into four multiplicative ratios: expression, estimation (curvature proxy), flow (continuous dynamics), and discretization.

Key Contributions and Results

1. The Full SPD Benchmark (Reference)

The paper formally records the unconstrained benchmark (Theorem 1): the distance from the initial log-spectrum to the set of spectra with width $\le \log K$ . This serves as the lower bound for all restricted complexities.

2. Diagonal and Block Families

Reachability as LMI: The paper proves that reachability for diagonal and block-diagonal families is exactly equivalent to an LMI feasibility problem: finding $E \in \mathcal{F}$ such that $E \preceq H \preceq KE$ (Theorems 2 and 4).
Certificates:
- Primal: A feasible $E$ proves reachability.
- Dual: An infeasible target is certified by a structured SDP dual witness (Proposition 3), including a specific "sign-flip" rank-one witness for cross-block obstructions (Corollary 2).
Exact 2D Formula: An exact closed-form formula is derived for the diagonal complexity in 2D, showing how off-diagonal Hessian entries shrink the feasible log-scale interval (Theorem 3).

3. Kronecker Families

Spectral Surrogate vs. Intrinsic Geometry: The paper separates the "Kronecker spectral surrogate" (additive log-spectrum model) from the true intrinsic geometry. The surrogate is exact only when the Hessian and metric share a fixed Kronecker eigenbasis (Proposition 8).
Affine-Invariant Projection: Theorem 6 establishes that the Kronecker family is a closed, totally geodesic submanifold. It provides a unique projection $G^\star$ characterized by partial-trace normal equations ( $Tr_B(R^\star)=0, Tr_A(R^\star)=0$ ).
Solver Convergence: An Armijo-based solver is proposed for projecting onto the Kronecker family, with a certified stopping residual and convergence rate (Corollary 4).
Hessian-Relative Reachability: Theorem 8 provides an exact equivalence for Hessian-relative reachability: a Kronecker metric exists with $\kappa(G^{-1}H) \le K$ if and only if there exist $A, B \succ 0$ such that $B \otimes A \preceq H \preceq K(B \otimes A)$ . This is a nonconvex feasibility problem in general, but exact in the fixed-basis regime (Proposition 9).
Candidate Certificates: Any candidate Kronecker metric passing the condition-number test provides a finite upper bound on the restricted complexity (Proposition 10).

4. Low-Rank and Extension Layers

Low-Rank Models: The paper distinguishes between additive, log-low-rank, and inverse Woodbury forms. It provides a spectral monotonicity result for shared-eigenbasis models (Proposition 13), showing that increasing rank budget reduces the spectral complexity.
Diagnostic Interfaces: The paper introduces interfaces for handling practical deviations:
- Curvature Proxies: Quantifies how proxy errors (e.g., Fisher vs. Hessian) inflate the required condition number threshold (Proposition 14).
- Stochastic Complexity: Defines high-probability bounds for stochastic controllers (Proposition 15).
- Flow and Discretization: Separates the cost of non-optimal continuous flows and finite-step discretization errors.

5. Exact Chain Factorization

Theorem 9 presents an "accounting identity" decomposing the ratio between the actual algorithmic path length and the full SPD benchmark into four factors:
$\frac{\text{Len}_{alg}}{D_K(S_0)} = R_{expr} \cdot R_{est} \cdot R_{flow} \cdot R_{disc}$
These represent the costs of expression (structural restriction), estimation (proxy error), flow (suboptimal dynamics), and discretization (finite steps). The paper clarifies that these are diagnostic ratios; they only represent "cost inflations" (values $\ge 1$ ) under specific hypotheses.

Significance and Claims

The paper claims to provide a mathematical language that transforms structural preconditioner questions into geometric distance, reachability, and certificate problems. Its significance lies in:

Separation of Concerns: It rigorously separates the expressivity of a metric family (can it reach the target?) from the estimation (is the curvature known?) and algorithmic (how is the path traversed?) aspects.
Exactness for Structured Families: It moves beyond heuristic analysis to provide exact LMI characterizations for diagonal/block families and exact projection theorems for Kronecker families.
Diagnostic Framework: It offers a systematic way to diagnose why an optimizer might fail to reach a condition number target, attributing the failure to specific geometric gaps (e.g., "the diagonal family cannot express the necessary curvature" vs. "the proxy is too noisy").
Benchmarking: It establishes a reference point (the full SPD benchmark) against which the "cost" of structured approximations can be measured.

The authors explicitly state that the paper does not claim to fully characterize specific optimizers (like Adam or K-FAC) or provide scalable solvers for the general nonconvex Kronecker reachability problem. Instead, it provides the theoretical "certificate-ready" specializations and diagnostic interfaces necessary to analyze such methods. The repository includes deterministic toy workflows to verify these certificates on small quadratic instances, serving as reproducibility checks for the theory rather than empirical benchmarks for large-scale optimization.