Optimal Posterior E-values with Non-Convex Parameter Sets with Applications to Voting Systems

技術要約：非凸なパラメータ集合を持つ最適事後E値（Posterior E-values）と、投票制度への応用

問題提起
本論文は、政治的な世論調査や投票制度の文脈において、選好データに対する逐次仮説検定を行う際の課題に取り組んでいる。目的は、ペア比較データを逐次的に収集し、統計的に有意な結果が得られた時点で停止することによって、選挙の勝者（コンドルセ、ボルダ、またはシュルツェ・ルールに基づく）を決定することである。

統計的な核心的な困難は、仮説集合の性質に起因する。ペア選好（多変量ベルヌーイ分布データ）のパラメータ空間は明確に定義されている一方で、特定の投票勝者に対応するパラメータの集合（$H_0$ および $H_1$）は複雑になり得る。

• コンドルセおよびボルダの勝者は、凸集合または単純なパラメータ集合に対応する。
• シュルツェの勝者は、多くの凸成分（選好の厳密な順序によって定義される）の和集合からなる、非凸なパラメータ集合に対応する。

既存の逐次的検定を構築するための手法（成長率最適化（GRO）E値など）は、多くの場合、逆情報投影（Reverse Information Projection; RIPr）を計算するために、帰無仮説の集合（$H_0$）の凸性に依存している。本論文は、シュルツェ投票法に見られるような一般的な複合仮説を扱うことができる理論とアルゴリズムの開発を目的としている。

手法
著者らは、**事後最適E値（Posterior Optimal E-values; POE）**に基づくフレームワークを提案している。

1. 理論的枠組み (POE):

   • 特定の対立仮説の下でのE値の期待対数成長率を最大化するGRO基準に基づき、著者らはベイズ的観点を用いてこれを複合仮説へと拡張している。
   • 彼らは、対立パラメータ集合 $\Phi_1$ 上の事前分布 $\pi$ に基づくE値 $E$ の効用関数を定義している。目標は、任意の停止時刻 $\tau$ に対して、統合された効用 $G_t(E, \pi, \tau)$ を最大化するテスト・スーパーマーチンゲールを見つけることである。
   • 定理2 は、最適なE値（POE）が、一ステップごとの最適E値の積であることを確立している。各ステップでは、分子が事後予測分布であり、分母がこの事後分布を帰無集合 $H_0$ へ投影したものであるような尤度比を計算する。
   • 特定の単純化（凸集合や固定次元への依存）に頼る既存の手法（Turner and Grunwald, 2022など）とは異なり、POEの定式化は一般的であり、KLダイバージェンスが有限である限り、任意の $H_0$ および $H_1$ に適用可能である。

2. アルゴリズムの実装 (RIPrのためのFrank-Wolfe法):

   • POEの計算には、各ステップで逆情報投影（RIPr）問題を解く必要がある。すなわち、現在の事後予測分布からのKLダイバージェンスを最小化する分布を $H_0$ 内から見つけることである。
   • 標準的なアルゴリズム（Liのアルゴリズムなど）は、高次元の多変量ベルヌーイデータに対して計算コストが高い。
   • 著者らは、この問題にFrank-Wolfeアルゴリズムを適応させた。分布の有限なサポート（$2^D$ 通りの可能な結果の空間）を活用することで、最適化を $\mathbb{R}^{2^D}$ における問題として再構成している。
   • 補題5 は、パラメータ集合 $\Phi'$ 上の分布の極値点がディラック分布（$P_{\delta_\phi}$）であることを証明している。これにより、Frank-Wolfeアルゴリズムは、パラメータ集合の極値点（ディラック測度）を反復的に探索することで、最適な投影を計算できる。
   • このアプローチにより、たとえ $H_0$ が（シュルツェ法のように）非凸な凸集合の和集合であっても、RIPrの計算が可能となる。これは、従来のGROベースの手法が失敗するシナリオである。

3. 検定手順:

   • キャップ付きサンプルサイズ検定（Capped Sample Size Test）: 固定予算による検定であり、E値が $1/\alpha$ を超えるか、あらかじめ計算された最大サンプルサイズ $T$ に達した時点で停止する。
   • 固定信頼度検定（Fixed Confidence Test; PPOE）: 2つのE値のシーケンス（$H_0$ 対 $H_1$ と $H_1$ 対 $H_0$）を用いる並行検定である。いずれかのシーケンスが閾値を超えたときに停止し、サンプルサイズの硬い上限を設けずに、偽陽性率と検出力の保証を提供する。

主な貢献

• 事後最適E値 (POE): ベイズ事前分布を用いて複合仮説へのGROを一般化する、新しいE値の最適化基準。これは、事後分布で条件付けられた一ステップごとの最適E値の積であることが示されている。
• 非凸集合の取り扱い: 非凸なパラメータ空間を持つことで知られるシュルツェ投票制度に対する、初の統計的処理を提供した。
• 効率的なRIPrアルゴリズム: 多変量ベルヌーイデータに対して逆情報投影を計算するための、Frank-Wolfeベースのアルゴリズムを導入した。この手法は、シュルツェ投票に求められる非凸な凸集合の和集合を扱うのに十分な効率性を備えており、凸な $H_0$ に限定されていた従来のGRO手法の限界を克服している。
• 理論的保証: POEの集中不等式を導出し、固定サンプルおよび固定信頼度検定の両方について、期待停止時間の境界を提供し、サンプル複雑性の観点からの最適性を示している。

実験結果
著者らは、シミュレーションと実データを通じて手法を検証している。

• 合成データ: 3人の候補者がいるコンドルセ、ボルダ、シュルツェの投票シナリオにおいて、最先端の手法（Universal Inference, GLRT, Turner-Grunness e-values, およびGRO）と比較を行った。
  • POEおよびその並行バリアント（PPOE）は、競争力のある検出力とサンプル複雑性を示した。
  • シュルツェ投票（非凸な $H_0$）においては、凸性に制限された手法を直接適用できないため、POEが不可欠であることが示された。
  • 本手法は「事前データ」（事前分布 $\pi$ の事前学習）の恩恵を受け、事前情報が増加するにつれて、オラクルGRO検定の性能へと収束していく。
• 実データへの適用: 2022年フランス大統領選挙のペア選好データに手法を適用した。
  • 目的は、逐次的検定を用いてボルダの勝者を決定することであった。
  • Turner-Grunwald (TG) 推定量（凸なボルダの場合には十分である）を用いることで、候補者を逐次的に排除していった。
  • 実験の結果、**ヤニック・ジャド（Yannick Jadot）**がボルダの勝者になることが判明した。この検定は、従来の政治調査（例：IPSOSは7,321人の投票者を使用）よりも大幅に少ないサンプル数（171人の投票者、4,721件のペア比較）で、決定的な結論に達した。

意義と主張
本論文は、仮説集合の凸性に制限されない、選好投票における逐次的検定の一般的なフレームワークを提供すると主張している。

• シュルツェ投票制度（その非凸なパラメータ空間ゆえに極めて困難である）に取り組んだ最初の統計的手法である。
• 提案されたFrank-Wolfeアルゴリズムは、有限サポートの分布に対する逆情報投影を計算するための実用的な方法を提供しており、投票以外の他の設定にも拡張できる可能性がある。
• 著者らは、凸な設定（ボルダなど）ではPOEとより単純なTG推定子が同様の性能を示すが、非凸な設定ではPOEが必要であることを指摘している。また、POE（Frank-Wolfeによる更新のため）の計算コストはTGよりも高いが、非凸問題においてはそのトレードオフが必要であると認めている。
• 本研究は、高次元の実世界のシナリオにおける逐次的検定の実現可能性を強調しており、統計的に有意な結論が、従来の世論調査よりも少ないサンプルで到達可能であることを示している。

著者らは、今後の展望について謙虚な姿勢を保っており、Frank-Wolfe実装の収束率、滑らかさのための $\epsilon$-スラックの必要性、および高次元のシュルツェ投票における凸成分の爆発的な増加を扱うためのより効率的な手法の可能性といった、未解決の問いを挙げている。