기술 요약: 제한된 동적 기하학적 복잡도 (Restricted Dynamic Geometric Complexity)

문제 정의

본 논문은 구조화된 프리컨디셔너(preconditioners)를 사용하는 최적화의 기하학적 비용을 다룬다. "최적화 지오메트로드라이내믹스(optimization geometrodynamics)" (Li, 2026)가 메트릭이 전체 양의 정치행렬 코(full positive-definite cone, $S^d_{++}$) 내에서 자유롭게 진화할 수 있을 때, 이차 목적 함수의 조건수(condition number)를 줄이기 위해 필요한 최소 아핀 불변 경로 길이(affine-invariant path length)의 벤치마크를 설정했다면, 실제 세계의 적응형 옵티마이저(예: AdaGrad, Adam, K-FAC, Shampoo)는 특정 메트릭 패밀리(대각, 블록 대각, 크로네커, 저계수 등)에 의해 제약을 받는다.

핵심 문제는 **제한된 동적 기하학적 복잡도(Restricted Dynamic Geometric Complexity, RDGC)**를 정량화하는 것이다. 즉, 초기 상대적 메트릭 $S_0$로부터 목표 조건수 클래스 $C_K$까지의 고유한 경로 거리를 구하되, 해당 경로가 지정된 구조적 패밀리 $\mathcal{F} \subset S^d_{++}$ 내에 머물러야 한다는 제약 조건을 포함한다. 본 논문은 다음을 결정하고자 한다:

1. 특정 패밀리 내에서 목표 조건수가 도달 가능한가?
2. 도달 가능하다면 정확한 기하학적 비용(경로 길이)은 얼마인가?
3. 불가능성을 입증하거나 이 비용에 대한 상한(upper bounds)을 제공하는 방법은 무엇인가?

방법론

본 프레임워크는 강볼록 이차 목적 함수 $f(\theta) = \frac{1}{2}\theta^\top H \theta$ (단, $H \succ 0$) 위에서 작동한다. 메트릭의 진화는 프리컨디셔너 $G$에 의해 정의된 상대 좌표계 $S = H^{-1/2} G H^{-1/2}$에서 분석된다. 사용되는 거리 척도는 **양의 정치행렬 코에 대한 아핀 불변 리만 거리(affine-invariant Riemannian distance)**이다:
$$d_{AI}(S_0, S_1) = \|\log(S_0^{-1/2} S_1 S_0^{-1/2})\|_F$$

방법론은 다음과 같이 진행된다:

1. 실현 가능한 패밀리 정의: 경로 길이와 도달 가능성이 잘 정의될 수 있도록 메트릭 패밀리에 대한 엄격한 요구 사항(양의 정치성, 스케일 처리, 매끄러운 다양체 구조)을 설정한다.
2. 도달 가능성 분석: 목표 조건수 $K$를 달성하는 프리컨디셔너의 존재 여부를 결정하는 문제를 타당성 문제(feasibility problem)로 정식화한다.
3. 인증서 구축: 선형 행렬 부등식(LMI)과 준정부호 계획법(SDP) 쌍대성을 사용하여 프라이멀 인증서(feasible metrics)와 듀얼 인증서(infeasibility witnesses)를 개발한다.
4. 투영 및 대리 모델: 크로네커 곱과 같은 복잡한 패밀리의 경우, 다음을 구분한다:
   • 스펙트럴 대리 모델(Spectral Surrogates): 고유벡터 제약을 무시하는 가산 로그-스펙트럼 모델.
   • 고유 기하학(Intrinsic Geometry): 부분 트레이스 법 방정식(partial-trace normal equations)을 활용하여 구조화된 메트릭의 다양체로의 아핀 불변 투영.
5. 계층별 분해: 실제 옵티마이저와 이론적 벤치마크 사이의 전체 오차를 네 가지 곱셈 비율(표현, 추정, 흐름, 이산화)로 분해한다.

주요 기여 및 결과

1. 전체 SPD 벤치마크 (참조점)

본 논문은 제약 없는 벤치마크(Theorem 1, 초기 로그-스펙트럼에서 폭이 $\le \log K$인 스펙트럼 집합까지의 거리)를 공식적으로 기록한다. 이는 모든 제한된 복잡도의 하한선 역할을 한다.

2. 대각 및 블록 패밀리

• LMI로서의 도달 가능성: 대각 및 블록 대각 패밀리에 대한 도달 가능성이 $E \in \mathcal{F}$를 찾아 $E \preceq H \preceq KE$를 만족시키는 LMI 타당성 문제와 정확히 동일함을 증명한다(Theorems 2 및 4).
• 인증서:
  • 프라이멀(Primal): 실행 가능한 $E$는 도달 가능성을 증명한다.
  • 듀얼(Dual): 불가능한 목표는 구조화된 SDP 듀얼 증인(witness)에 의해 인증된다(Proposition 3). 여기에는 크로스-블록 장애를 위한 특정 "부호 반전(sign-flip)" 랭크-1 증인이 포함된다(Corollary 2).
• 정확한 2D 공식: 2D에서의 대각 복잡도에 대한 정확한 폐쇄형 공식을 유도하며, 헤시안의 비대각 성분이 어떻게 실행 가능한 로그-스케일 구간을 축소시키는지 보여준다(Theorem 3).

3. 크로네커 패밀리

• 스펙트럴 대리 모델 vs. 고유 기하학: 논문은 "크로네커 스펙트럴 대리 모델"(가산 로그-스펙트럼 모델)과 실제 고유 기하학을 구분한다. 대리 모델은 헤시안과 메트릭이 고정된 크로네커 고유기저를 공유할 때만 정확하다(Proposition 8).
• 아핀 불변 투영: Theorem 6은 크로네커 패밀리가 닫혀 있고 전지조직적(totally geodesic)인 부분 다양체임을 확립한다. 또한 부분 트레이스 법 방정식($Tr_B(R^\star)=0, Tr_A(R^\star)=0$)으로 특징지어지는 유일한 투영 $G^\star$를 제공한다.
• 솔버 수렴성: 크로네커 패밀리로 투영하기 위한 Armijo 기반 솔버를 제안하며, 인증된 정지 잔차(stopping residual)와 수렴 속도를 제공한다(Corollary 4).
• 헤시안 상대적 도달 가능성: Theorem 8은 헤시안 상대적 도달 가능성에 대한 정확한 동치를 제공한다: $\kappa(G^{-1}H) \le K$를 만족하는 크로네커 메트릭이 존재할 필요충분조건은 $A, B \succ 0$가 존재하여 $B \otimes A \preceq H \preceq K(B \otimes A)$를 만족하는 것이다. 이는 일반적으로 비볼록(nonconvex) 타당성 문제이지만, 고정된 기저 체제에서는 정확하다(Proposition 9).
• 후보 인증서: 조건수 테스트를 통과하는 임의의 후보 크로네커 메트릭은 제한된 복잡도에 대한 유한한 상한을 제공한다(Proposition 10).

4. 저계수(Low-Rank) 및 확장 계층

• 저계수 모델: 가산(additive), 로그-저계수(log-low-rank), 역 우드베리(inverse Woodbury) 형태를 구분한다. 공유 고유기저 모델에 대한 스펙트럼 단조성 결과를 제공하여(Proposition 13), 랭크 예산이 증가함에 따라 스펙트럼 복잡도가 감소함을 보여준다.
• 진단 인터페이스: 실제 편차를 처리하기 위한 인터페이스를 도입한다:
  • 곡률 프록시(Curvature Proxies): 프록시 오차(예: Fisher vs. Hessian)가 어떻게 요구되는 조건수 임계값을 팽창시키는지 정량화한다(Proposition 14).
  • 확률적 복잡도: 확률적 컨트롤러를 위한 고확률 상한을 정의한다(Proposition 15).
  • 흐름 및 이산화: 비최적 연속 흐름과 유한 단계 이산화 오차의 비용을 분리한다.

5. 정확한 체인 인수분해 (Exact Chain Factorization)

Theorem 9는 실제 알고리즘 경로 길이와 전체 SPD 벤치마크 사이의 비율을 네 가지 인자로 분해하는 "회계 항등식"을 제시한다:
$$\frac{\text{Len}_{alg}}{D_K(S_0)} = R_{expr} \cdot R_{est} \cdot R_{flow} \cdot R_{disc}$$
이들은 각각 표현(구조적 제한), 추정(프록시 오차), 흐름(비최적 역학), 이산화(유한 단계)의 비용을 나타낸다. 논문은 이들이 진단적 비율임을 명시한다. 즉, 특정 가설 하에서만 "비용 팽창"(값 $\ge 1$)을 나타낸다.

의의 및 주장

본 논문은 구조적 프리컨디셔너 문제를 기하학적 거리, 도달 가능성, 그리고 인증서 문제로 변환하는 수학적 언어를 제공한다고 주장한다. 그 의의는 다음과 같다:

1. 관심사의 분리: 메트릭 패밀리의 표현력(목표에 도달할 수 있는가?)과 추정(곡률을 알고 있는가?), 그리고 알고리즘적 측면(경로가 어떻게 횡단되는가?)을 엄격하게 분리한다.
2. 구조화된 패밀리에 대한 정확성: 대각/블록 패밀리에 대한 정확한 LMI 특성화와 크로네커 패밀리에 대한 정확한 투영 정리를 제공함으로써 휴리스틱 분석을 넘어선다.
3. 진단 프레임워크: 옵티마이저가 왜 조건수 목표에 도달하지 못하는지를 진단할 수 있는 체계적인 방법을 제공한다(예: "대각 패밀리가 필요한 곡률을 표현할 수 없는가" vs "프록시가 너무 노이즈가 심한가").
4. 벤치마킹: "비용"을 측정할 수 있는 기준점(전체 SPD 벤치마크)을 설정한다.

저자들은 본 논문이 특정 옵티마이저(Adam이나 K-FAC 등)를 완전히 규명하거나 일반적인 비볼록 크로네커 도달 가능성 문제를 위한 확장 가능한 솔버를 제공하는 것을 목표로 하지 않는다고 명시한다. 대신, 이러한 방법들을 분석하는 데 필요한 이론적 "인증서 준비 완료(certificate-ready)" 특수화 및 진단 인터페이스를 제공한다. 저장소에는 소규모 이차 인스턴스에서 이러한 인증서를 검증하기 위한 결정론적 토이 워크플로우가 포함되어 있으며, 이는 일반적인 최적화의 경험적 벤치마크가 아니라 이론에 대한 재현성 확인용으로 설계되었다.