Holm-Bonferroni Verification of Math Solvers: A Hessian-Mismatch Diagnostic for Benchmark-Level Failure Modes

Motivation

• Known: 벤치마크 스위트에서 여러 데이터셋에 걸쳐 solver를 비교할 때 다중비교 문제가 발생하며, Bonferroni나 Holm-Bonferroni, Benjamini-Hochberg 같은 보정 절차가 존재함은 알려져 있다. 또한 $\ell_2$-regularized logistic regression의 고정 preconditioner 반복법의 점근적 선형 수렴률이 generalized Rayleigh quotient로 특징지어짐도 수치선형대수 및 self-concordance 분석 문헌에서 알려져 있다.
• Gap: 기존 벤치마크 관행은 보정되지 않은 p-value를 보고하거나 아예 보고하지 않으며, 다중비교 보정을 적용하더라도 왜 특정 데이터셋에서 기각이 일어나는지 알고리즘적 메커니즘으로 설명하는 구조적 진단이 결여되어 있어, 기각된 데이터셋이 무작위 Type-I 오류와 구별되지 않는다는 문제가 있다.
• Why: 이 프로토콜은 통계적 보정과 구조적 원인 규명을 결합함으로써, 고전적 solver뿐 아니라 LLM 기반 정리 증명기 등 스펙트럼적 특성화가 가능한 AI 기반 수학 시스템 전반의 벤치마크 검증 방법론에 일반화 가능성을 제시한다는 점에서 중요하다.
• Approach: Holm-Bonferroni로 보정된 paired t-test를 11개 데이터셋에 걸쳐 적용해 R1+10(closed-form solver)과 warm-start L-BFGS 간 iso-accuracy 귀무가설을 검정하고, 기각된 데이터셋을 Hessian-mismatch index $\mu_*$(generalized Rayleigh quotient)로 사후 설명하는 방식을 취한다.

Achievement

Figure 2. Convergence of two diagnostics toward the true asymp-

1. 검증 프로토콜 제시: 11개 데이터셋에 대해 Holm-Bonferroni 보정 paired t-test를 적용해 정확히 2개 데이터셋(Adult, Covertype)에서 iso-accuracy 귀무가설을 corrected p<0.05로 기각했으며, 4가지 보정 절차(Bonferroni, Holm-Bonferroni, Benjamini-Hochberg, 무보정)와 4가지 검정통계량(paired t, Wilcoxon, sign-test, bootstrap CI)이 모두 일치하는 결과를 보였다.
2. 구조적 귀인 분석: $\mu_$가 두 기각 사례를 사후적으로 설명함을 보였다 — Covertype은 벤치마크 내 가장 작은 $\mu_(\approx10^{-3})$로 진짜 느린 수렴 실패이나, Adult($\mu_\approx0.09$)는 7개의 기각되지 않은 데이터셋보다 오히려 $\mu_$가 크며 10회 반복 후 잔차에 정확도가 민감해서 기각됨을 밝혔다.
3. 사전 반복 추정치의 실패 입증: 5회 반복 후 추정치 $\hat\mu_5$가 실제 $\mu_$와 무관하게 [0.08, 0.21] 범위에 몰려있어 결정 규칙으로 사용 시 $\tau=0.05$에서 위양성률(FP rate) 100%임을 보임으로써, $\mu_$가 사전 예측 지표가 아니라 사후 설명 지표임을 명확히 했다.

How

Figure 2. Convergence of two diagnostics toward the true asymp-

• $\ell_2$-regularized logistic loss의 minimizer $\theta^*(\lambda)$에 대해 fixed preconditioner $M=2\lambda I+\frac14 X^\top X$를 이용한 one-step estimator $\hat\theta_{R1}$을 계산하고 10회 반복(R1+10)한다.
• Hessian-mismatch index $\mu_ := \lambda_{\min}(M^{-1/2}H(\theta^)M^{-1/2})$를 정의하며, 이는 반복법의 점근적 선형 수렴률 $1-\mu_*$를 결정하는 generalized Rayleigh quotient이다.
• 11개 데이터셋에 대해 5-fold CV, $K=20$ log-spaced $\lambda$ grid, $R=5$ split-repetition으로 R1+10과 warm-start L-BFGS의 CV 정확도 차이 $\Delta_d^{(r)}$를 계산하고 paired t-statistic $T_d$를 산출한다.
• Holm-Bonferroni, Bonferroni, Benjamini-Hochberg, 무보정의 4가지 다중비교 보정과 paired t, Wilcoxon signed-rank, sign test, bootstrap CI의 4가지 검정통계량을 비교한다.
• 사전 반복 추정치 $\hat\mu_5$(R1의 5회 반복만으로 얻은 근사치)를 결정 규칙으로 사용했을 때의 위양성률을 실제 $\mu_*$와 비교 평가한다.

Originality

• 다중비교 통계 보정(Holm-Bonferroni)과 문제 특화 스펙트럼 진단(Hessian-mismatch index)을 결합한 벤치마크 검증 프로토콜은 기존 문헌(Demšar 2006, Benavoli et al. 2017)에 없던 새로운 조합이다.
• Rayleigh quotient 기반 $\mu_*$가 수치선형대수 및 self-concordance 문헌에서 이미 알려진 개념이었으나, 이를 가설검정 프로토콜과 페어링하여 벤치마크 레벨의 실패 모드를 사후 진단하는 데 사용한 점이 새롭다.
• $\mu_*$가 예측 지표가 아니라 사후 설명 지표라는 점을 실증적으로 명확히 구분하고, 이를 반영해 사전 추정치 $\hat\mu_5$의 결정 규칙 실패를 정량적으로 보인 점이 독창적이다.

Limitation & Further Study

• 실증적 주장이 convex logistic regression 사례 한 가지에 국한되어 있으며, 다른 수학 solver(SGD, CG, LLM 기반 정리 증명기 등)로의 일반화는 저자들 스스로도 "conjecture"라고 명시할 뿐 검증하지 않았다.
• $\mu_*$는 사후 진단으로만 유용하며 사전 예측력이 없다는 한계가 있어, 실제 벤치마크 설계 단계에서 실용적 가치가 제한적일 수 있다.
• Adult 데이터셋의 기각 원인이 $\mu_*$만으로 설명되지 않고 "residual 민감도"라는 별도 메커니즘이 필요하다는 점에서, 진단지표의 설명력 자체가 불완전함을 저자들도 인정하고 있다.
• 후속 연구로 SGD의 sharpness, CG의 Krylov-subspace gap 등 다른 알고리즘에 대한 problem-specific diagnostic 개발과 AI 기반 수학 시스템(LLM prover 등)으로의 실제 확장 검증이 필요하다.

Evaluation

총평: 통계적 다중비교 보정과 알고리즘적 구조 진단을 결합한다는 아이디어는 벤치마크 검증 방법론에 신선한 관점을 제공하지만, 단일 convex 사례 연구에 국한되어 일반화 가능성이 추측 수준에 머물러 있어 후속 검증이 필요한 초기 단계의 연구이다.