John Ellipsoid 근사에서의 평균화(Averaging)를 넘어서: 레버리지 스코어(Leverage-Score) 모델에서의 고정밀

대칭 다면체 $P={\mathbf{x}\in\mathbb{R}^d:|\mathbf{A}\mathbf{x}|\infty\le1}$, $\mathbf{A}\in\mathbb{R}^{n\times d}$의 John ellipsoid는 Cohen, Cousins, Lee, Yang (COLT 2019)부터 그 후속 연구들 [WY24, CLS+25]에 이르기까지 긴 레버리지 스코어 (leverage-score) 알고리즘 계보를 통해 계산되어 왔으며, 이들은 모두 $Θ(\varepsilon^{-1}\log(n/d))$ 반복(iterations) 내에 $(1+\varepsilon)$-근사 (approximation)에 도달합니다. 우리는 현대의 알고리즘 계보가 혼재시키고 있는 이 복잡성을 세 가지 비용(인증 (certification), 식별 (identification), 정확도 (accuracy))으로 분리하며, 역사적인 $\varepsilon^{-1}$ 항이 오직 첫 번째 비용에만 위치함을 밝힙니다. 등가적인 D-최적 설계 (D-optimal-design) 형태인 $\min{\mathbf{p}\in\Delta_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top)$에서, 레버리지 스코어 오라클 (leverage-score oracle)은 정확히 1차 오라클 (first-order oracle)이며, $(1+\varepsilon)$-John 보장은 Frank-Wolfe 갭 (Frank-Wolfe gap) $g(\mathbf{p})\le\varepsilon d$를 의미합니다. 이 사전 (dictionary)을 통해 각 비용을 분리할 수 있습니다. $\varepsilon^{-1}$은 인증 (certification)의 산물입니다. 즉, 해당 계보 전반에서 사용된 인증 수단인 반복값들의 균등 평균 (uniform average)은 각 반복의 비용이 얼마나 저렴하든 관계없이 정확히 $Θ(1/T)$의 갭을 가집니다. 대신 마지막 반복값 (last iterate)에 초점을 맞추면 동일한 오라클은 매우 빠릅니다. 웜 스타트 (warm-started)된 가속화된 방법 (accelerated method)은 $\varepsilon$에 독립적인 설정 $C(\mathbf{A})$ 이후, $C(\mathbf{A})+O(\sqrt{\kappa}\log(1/\varepsilon))$번의 쿼리 (queries) 내에 보장에 도달하며, 일단 최적의 면 (optimal face)이 식별되면 해당 면의 문제는 오라클이 헤시안 (Hessian)을 정확히 복구할 수 있는 제약 없는 자기 수렴적 최소화 (unconstrained self-concordant minimization) 문제가 됩니다. 따라서 댐프 뉴턴 (damped Newton) 방법은 단 $O(\log\log(1/\varepsilon))$ 단계만을 필요로 하며, 총 $C(\mathbf{A})+O(d^2\log\log(1/\varepsilon))$번의 쿼리가 소요됩니다. 따라서 정확도 (accuracy)에 대한 의존성은 $\varepsilon$에 독립적이고 조건에 의존적인 설정 이후 이중 로그 (doubly logarithmic) 형태를 띱니다. 남은 미해결 과제는 식별 비용 (identification cost, 최적의 면에 도달하기 위한 조건에 무관한 상한)과 하한 (lower bounds)입니다. 정확도가 장애물이 아닙니다.