技術的サマリー：オンライン多重検定における後悔の視点

1. 問題定義

オンライン多重検定（OMT）は、仮説が時間とともに外生的に到着し、帰無仮説の棄却または保持について即座に不可逆な意思決定を必要とする逐次推論問題に対処する。従来の OMT 文献は、目標レベル $\alpha$ 未満に偽発見率（FDR）を維持しつつ、統計的検出力を最大化することに焦点を当てている。しかし、本論文は、FDR と検出力を個別に評価することが、現代の自動化パイプラインにおける偽陽性（第 1 種の誤り）と偽陰性（第 2 種の誤り）の極めて非対称なコストを不明瞭にしていると主張する。

特定された核心的な問題は閾値枯渇である。信号が希薄な環境（例：「コールドスタート」または純粋なノイズの期間）において、FDR を厳密に制御する決定論的アルゴリズムは、しばしばその検定能力（$\alpha$富）を枯渇させ、意思決定閾値が単調にゼロに向かって減衰させる。これにより、アルゴリズムは後続する真の信号の急増に対して「盲目」となり、膨大な発見の見逃しを招く。逆に、一定の検出力を維持しようとするアルゴリズムは、線形的な偽陽性のペナルティを負うリスクがある。本論文は、既存のパラダイムが、これら 2 つの誤りタイプ間の非定常なパレートフロンティアを navig できないと提唱する。

2. 手法

2.1 重み付け後悔メトリック

FDR と検出力の評価を統合するために、著者は重み付け後悔を導入する。FDR（条件付き率）と検出力（周辺確率）を別々に扱う従来のメトリックとは異なり、重み付け後悔は両方の誤りタイプを単一の累積損失通貨にマッピングする：
$$\text{Regret}_T(a, b) = a \cdot V_T + b \cdot M_T$$
ここで、$V_T$ は偽陽性の総数、$M_T$ は偽陰性の総数、$a, b > 0$ はドメイン固有のペナルティ重みである。目的は、全知のオラクルに対する期待重み付け後悔を最小化することである。

2.2 後悔保存の双対性

本論文は、後悔保存の双対性と呼ばれる根本的な理論的限界を確立する。これは、純粋に決定論的で履歴依存の OMT 手続きが、必然的に線形的な後悔ペナルティ $\Omega(T)$ を負うことを証明する。これは 2 つの異なるメカニズムを通じて発生する：

1. 検出力の障壁: 最小検出検出力を維持するには、厳密に正の閾値の下限が必要であり、これは定常環境において必然的に偽陽性の線形的蓄積を誘発する。
2. FDR の障壁: 決定論的な富管理を通じて FDR を厳密に制御すると、閾値の減衰を招く。バースト性の環境（長い無信号期間の後に信号が到来する）において、この減衰は閾値を消失させ、偽陰性の線形的蓄積を引き起こす。

したがって、両方の誤りタイプに対して部分線形後悔を同時に達成する純粋な決定論的アルゴリズムは存在しない。

2.3 分離型 OMT（DOMT）アルゴリズム

決定論的メカニズムの構造的限界を克服するために、著者は決定論的ベースライン（例：LOND、LORD、SAFFRON）を閾値枯渇から救済するために設計されたメタラッパーアルゴリズムである**分離型 OMT（DOMT）**を提案する。

主要メカニズム:
DOMT は、各ステップ $t$ において意思決定閾値に履歴から分離された、厳密に非負のランダム摂動を導入する：
$$\lambda_t = \min(1, \lambda_t^{\text{base}} + \xi_t)$$
ここで、$\lambda_t^{\text{base}}$ は基礎となる決定論的手続きによって指示される閾値であり、$\xi_t = \epsilon_t Z_t$ は探索項である。

• 探索振幅: $\epsilon_t = \kappa \frac{\alpha}{\sqrt{t}}$ は、$O(t^{-1/2})$ の速度で減衰する。
• ランダム性: $Z_t \sim \text{Uniform}[0, 1]$ は i.i.d. である。
• 因果的分離: 決定的に重要なのは、ベース手続きの内部状態（富）が、仮想閾値 $\lambda_t^{\text{base}}$ と対応する仮想決定のみを使用して更新される点である。実際の決定には $\lambda_t$ が使用されるが、「ノイズ」$\xi_t$ は数学的にベース手続きの状態更新から隔離される。

特性:

• 追加の偽陰性ゼロ: $\xi_t \ge 0$ であるため、DOMT の棄却集合は常にベースラインの棄却集合を含み（$R_t^{\text{DOMT}} \supseteq R_t^{\text{base}}$）、ベースラインに対する発見の見逃しを保証する。
• 漸近的安全性: 定常環境では、探索ノイズは真の発見の蓄積によって希釈され、ベース手続きの正確な漸近 FDR 制御を維持する。
• 有限サンプル境界: 極端なコールドスタート（純粋な帰無仮説）において、DOMT は追加の偽陽性の絶対数を $O(\sqrt{T})$ に制限し、壊滅的な線形誤り蓄積を防ぐ。

3. 主要な貢献

1. メトリックの革新: 非対称な第 1 種および第 2 種の誤りを明示的にバランスさせる重み付け後悔の導入により、孤立した FDR/検出力評価を超えた。
2. 理論的下界: 後悔保存の双対性の証明により、一定の警戒（偽陽性）と閾値枯渇（偽陰性）のトレードオフにより、純粋な決定論的アルゴリズムが必然的に $\Omega(T)$ の線形後悔ペナルティを負うことを確立した。
3. アルゴリズム的解決策: 厳密に非負で履歴から分離された確率的探索を用いて閾値枯渇を緩和しつつ、漸近的安全性を損なわないプラグ・アンド・プレイ型メタラッパーDOMTの提案。
4. 後悔分析: バースト性環境において、DOMT が決定論的ベースラインと比較して重み付け後悔において順序最適の $\Omega(\sqrt{T})$ の削減を達成することを証明。
5. 相転移の特性化: 確率的探索が理論的に有利となる時期を決定するペナルティ比 $b/a$ の臨界閾値である、閉形式の**「コールドスタート税」**（$M^*$）の導出。この税は、純粋なノイズ期間中の探索のコストを定量化する。

4. 結果

理論的結果

• 決定論の線形後悔: 定理 1 と 2 は、非定常設定において、いかなる決定論的アルゴリズムも、検出力を維持する場合は線形的な偽陽性後悔を、FDR を厳密に制御する場合は線形的な偽陰性後悔のいずれかを被ることを示している。
• DOMT の部分線形後悔: 定理 6 は、バースト性信号モデルの下で、DOMT がベースラインと比較して期待重み付け後悔を $\Omega(\sqrt{T})$ 削減することを証明している。
• 安全性保証: 定理 3 は、DOMT がそのベース手続きの漸近 FDR 制御を継承することを確認している。定理 4 は、偽発見割合（FDP）の膨張に関する有限サンプルの高確率境界を提供し、定常領域では $O(1/\sqrt{t})$ として優雅にスケーリングし、敵対的なコールドスタートでは厳密に制限されることを示している。
• 減衰率の最適性: 本論文は、$O(t^{-1/2})$ の減衰率が構造的に必要であると主張する。より速い減衰（例：$O(t^{-1})$）は探索コストを $O(\log T)$ に圧縮するが、同時に発見の回復を $O(\log T)$ に窒息させ、ベースラインの $\Omega(T)$ の不足に対抗できなくなる。

実証結果

実験は合成データと 3 つの実世界データセット（RNA-Seq マイクロアレイ、S&P 500 の金融異常、IMPC マウス表現型データ）で行われた。

• 定常環境: DOMT は厳密な FDR 制御を維持しつつ、統計的検出力においてベースラインを一貫して上回る。
• バースト性/コールドスタート環境: 決定論的ベースラインは絶対的な閾値枯渇に苦しみ、信号が最終的に到着した際にほぼゼロの検出力となる。DOMT はこれらの「ミニ干ばつ」を成功裡に橋渡しし、遅れた信号バーストを捕捉して、偽陰性の巨視的な削減を達成する。
• パレートフロンティア: 実証結果は、DOMT が非定常パレートフロンティアを navig することを確認しており、偽発見における厳密に制限された横方向の税を支払うことで、偽陰性における巨視的な垂直的削減を達成している。

5. 意義と主張

本論文は、重み付け後悔の視点が、制約付き誤り制御から無制約リスク最小化へと OMT の最適化目的を根本的に変えることを主張する。決定論的枠組みにおける線形後悔の不可避性を証明することで、著者らは確率的探索は単なるヒューリスティックではなく、非定常環境を navig するための数学的必然性であると論じる。

DOMT の意義は、汎用メタラッパーとして機能する能力にある。既存の p 値または e 値手続き（LOND、LORD、SAFFRON、SCORE など）を置き換えるのではなく、それらをカプセル化し、それらの基礎となる超マルチンゲール安全性特性を侵害することなく、「ゼロ閾値のデッドロック」から救済する。本論文は、このアプローチがパレートフロンティアの「順序最適」な travers を可能にし、信号を見逃すことが壊滅的な高リスク・非対称コストのシナリオ（例：医療スクリーニング、詐欺検出）において発見の配当を確保すると強調している。

著者らは、DOMT が「コールドスタート税」（純粋なノイズ期間中の誤りの一時的な膨張）を導入するが、これは決定論的アルゴリズムのシステム的失敗を防ぐための意図的で制限されたトレードオフであり、実世界の非定常データストリームにおけるオンライン推論のための堅牢な解決策を提供すると結論付けている。