技術的概要：オンライン最適化によるオンライン適合性予測

問題定義

適合性予測は、有限サンプルの被覆保証を伴う不確実性定量化のための原理的な枠組みを提供する。近年の進展により、これらの手法はオンラインおよび逐次的な設定に拡張されてきたが、既存のアプローチは通常、単一の被覆レベル（$1-\alpha$）で動作する。複数の被覆レベルを同時に必要とする場合（気象予報、マクロ経済予測、リスク管理など、ユーザーが異質なリスク許容度を持つアプリケーションで一般的なシナリオ）には、標準的なオンライン手法は各$\alpha$に対して独立して実行されなければならない。

この独立した実行は、決定的な限界をもたらす：得られる予測集合はネスト（入れ子）構造であることが保証されない。実用的には、高い信頼度レベル（例：99%）の予測集合は、低い信頼度レベル（例：90%）の集合の超集合でなければならない。このネスト性が欠如すると、不確実性の推定値は非整合的となり、解釈が困難になる。さらに、独立した推定は、非交差制約を課すことで分位数間での情報共有を可能にする、結合分位数回帰から知られる統計的効率性の向上を活用できない。

本論文は、非定常または敵対的なデータ系列の下でも長期的な被覆保証を維持しつつ、複数の被覆レベルにわたってネストされた予測集合を同時に出力するオンライン適合性予測手法の開発という課題に取り組む。

手法

著者は、オンライン最適化の視点に基づいた 2 つの新しいアルゴリズムを提案する。適合性しきい値の更新を、しきい値に対する単調性制約を課しながら結合損失関数を最小化するオンライン学習タスクとして定式化する。

1. 問題定式化

時刻$t$における有界な非適合性スコアを$s_t$とする。誤被覆レベルの列$0 = \alpha_0 < \alpha_1 < \dots < \alpha_K < \alpha_{K+1} = 1$に対して、予測集合$C^i_t = \{y : s_t(x,y) \le q_{t,i}\}$がネストされる（$C^{i+1}_t \subseteq C^i_t$）ようなしきい値$q_{t,i}$を推定することを目的とする。これには、しきい値が単調減少である必要がある：$q_{t,1} \ge q_{t,2} \ge \dots \ge q_{t,K}$。

標準的なオンライン更新（例：Adaptive Conformal Inference）は、各分位数を独立して扱う：
$$q_{t+1,i} = q_{t,i} - \eta_t (\alpha_i - \text{err}_{t,i})$$
ここで、$\text{err}_{t,i}$は誤被覆の指標である。このアプローチはレベル間の結合を欠き、単調性を保証しない。

2. 提案アルゴリズム

本論文は、オンライン最適化の手法を用いて単調性を強制するように更新則を修正する 2 つの手法を導入する。

A. 指数勾配（EG）降下法

この手法は、変換されたパラメータ空間に適用される**指数勾配（Exponentiated Gradient）**アルゴリズムを利用する。

• パラメータ化: しきい値を直接更新する代わりに、アルゴリズムは切断された単体上の連続する分位数間の正規化されたギャップ（$w_{t,i}$）を更新する。この変数変換（$q_{t,i} = B \sum_{j=i}^K w_{t,j}$）により、重みが非負であれば、分位数が順序付けられることが本質的に保証される。
• 更新則: アルゴリズムは、EG 更新を用いて結合損失関数$g_t(\bar{w})$を最小化する。各座標の勾配は、すべての関連する分位数レベルにわたる誤被覆の不一致を集約し、グローバルな結合を誘発する。
• メカニズム: 手法が過度に保守的であるか、あるいは過小被覆している場合、累積誤差項は分位数曲線全体にわたってギャップを同時に調整する。これにより、手法はレベル間で「力を借りて」、ネスト性を自然に維持するための調整を協調的に行うことができる。

B. 射影勾配（PG）降下法

この手法は、特定の制約集合を用いた**射影勾配（Projected Gradient）**降下法を利用する。

• 更新則: アルゴリズムは、結合損失に基づいて分位数ベクトル$\bar{q}_t$に対して独立した勾配更新をまず行う。
• 射影: 得られたベクトルは、減少列の凸集合（$Q = \{\bar{q} : B \ge q_1 \ge \dots \ge q_K \ge 0\}$） onto 射影される。
• メカニズム: この射影は、Pool Adjacent Violators Algorithm (PAVA)を用いて実装される。EG と異なり、PG は局所的な修正を通じて動作する：分位数を独立して更新し、その後、順序制約を回復するために最小限の調整を加える。勾配ステップ中にレベル間で情報を再分配する本質的なメカニズムは持たない。

3. 理論的保証

著者は、両手法に対して理論的 bound を確立する：

• 被覆: 両手法とも長期的な被覆保証を提供し、すべてのレベルにおいて経験的誤被覆率が目標$\alpha_i$に収束することを保証する。
• 後悔と誤差: 本論文は、動的後悔および推定分位数と真の分位数からの偏差（$\|\bar{q}_t - \bar{q}^*_t\|_2$）の bound を導出する。これらの bound は、真の分位数の動的変動（$V_T$）とステップサイズ$\eta$に依存する。EG 手法の bound は、構造化された結合により改善された効率性を示唆しており、一方 PG は各時刻において実行可能性（ネスト性）を保証する。

主要な貢献

1. 新規定式化: 複数の被覆レベルにわたってネストされた予測集合を生成するオンライン適合性予測枠組みの導入。これにより、リスクスペクトル全体にわたって較正された不確実性定量化が可能となる。
2. アルゴリズム的革新: 凸最適化に基づく 2 つのオンラインアルゴリズム（EG と PG）の提案。これらは単調性を厳密に強制しながら、適合性しきい値を結合的に推定する。
3. 理論的保証: すべてのレベルに対する長期的な被覆保証の確立および、各時刻においてネストされた予測集合を保証する証明。
4. 実証的検証: これらの手法が、独立した単レベルのベースラインと比較して、安定した被覆、厳密にネストされた集合、および改善された統計的効率を達成することを示す。

実験結果

これらの手法は、合成データおよび実世界データセットの両方で評価された。

合成データ

• 設定: 潜在反射ランダムウォークを通じてスコア分布が進化する非定常環境。
• 知見: **指数勾配（EG）**法は、独立した分位数トラッカーおよび射影勾配法と比較して、低い$\ell_1$追跡誤差を達成した。これは、分位数間で情報を共有することが、時間変化する分布の追跡において統計的効率を向上させるという仮説を支持する。PG 法は独立したトラッカーと同様の性能を示し、この特定の設定では EG に比べて結合最適化からの利得が限定的であることを示唆している。

実世界データ（米国インフレ）

• 設定: ローリングウィンドウを用いた AR(3) モデルによる米国消費者物価指数（CPI）インフレの予測。
• 知見:
  • 較正: すべての手法は最終的に低い較正誤差に収束した。しかし、制約のない分位数トラッカーは振動的な挙動（過剰補正）を示したのに対し、提案された制約付き手法はより安定した軌道を示した。
  • ネスト性と滑らかさ: ベースライン手法（独立トラッカーおよび事後射影）は、時折の歪みやネストされていない領域を持つ予測バンドを生成した。対照的に、提案された手法（特に EG）は、ネスト構造を厳密に保持するより滑らかで整合性の高い予測集合を生成した。
  • 解釈可能性: EG 更新は、累積的不一致を通じて隣接する分位数を協調させることで、レベル間での急激な変化を減らし、より滑らかな予測バンドをもたらした。

意義と主張

本論文は、その主な意義を、多レベルオンライン設定における不確実性推定値の非整合性の解決にあると主張する。オンライン最適化を通じて構造的制約（単調性）を強制することで、提案された手法は整合的なリスクスペクトルを提供する。

主な主張には以下が含まれる：

• 統計的効率性: 結合推定は分位数間で情報を共有することで効率を向上させる。これは、EG 手法の優れた追跡性能によって明示的に実証されている。
• 解釈可能性: 得られるネストされた予測集合は、異なるリスク許容度（例：緊急計画者と政策決定者）に対して一貫した不確実性推定を必要とする意思決定の文脈において不可欠である。
• 安定性: 単調性を更新と結合して強制することは、学習ダイナミクスを安定化させ、制約のないトラッカーで見られる不規則な振動を防ぐ。
• 広範な文脈: この研究は、敵対的頑健性（最悪ケース設定における保証）と統計的効率性（時間変化する分布の追跡）の間のギャップを埋め、動的後悔分析を伴う時間変化する分位数の追跡問題としてオンライン適合性予測を位置づける。

著者は、将来の研究として非定常環境における性能をさらに向上させるための適応的学習率の検討が可能であると指摘しているが、現在の貢献は固定ステップサイズ制約下での結合推定の構造的利点に焦点を当てている。