Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

技術要約：インタラクティブな統計的意思決定におけるプライバシーを考慮したミニマックス・クオンタイル下界

問題提起
古典的なミニマックス・リスクおよび後悔（regret）は、期待値に基づく基準であり、最悪のケースにおける期待損失を特徴付けるが、稀に発生する高影響な失敗を捉えることはできない。この限界は、二つのアルゴリズムが同じ期待損失を共有していても、尾部挙動（tail behavior）が大きく異なる可能性がある安全性重視、あるいは信頼性重視の設定において極めて重要である。近年の研究では、非インタラクティブな推定における高確率ミニマックス・クオンタイルが確立されている一方、期待リスクに基づくインタラクティブな統計的意思決定（ISDM）のための枠組みは個別に存在する。しかし、「$\delta$-明示的なミニマックス・クオンタイル」をインタラクティブな設定で扱うための統一された理論は未解決のままであった。さらに、プライバシー制約（具体的には有界な相互情報量（MI））が、インタラクティブな問題におけるこれらの高信頼性保証に与える影響についても、体系的に対処されてこなかった。

手法
本論文は、パッシブな推定と、バンディットや強化学習のようなインタラクティブな問題を統一する、インタラクティブな統計的意思決定（ISDM）パラダイム内での理論的枠組みを開発する。その手法は以下の3段階で進行する：

1. 構造的関係： 著者らは、ミニマックス・クオンタイルと古典的なミニマックス・リスクとの関連性を確立する。彼らは「厳密な（strict）」ミニマックス・クオンタイル（事象 $\{L > r\}$ に基づくもの）と「下限（lower）」ミニマックス・クオンタイルを定義する。これら二つの定義は、可算個の信頼レベルを除いて等価であることを証明し、クオンタイル下界から期待値下界への変換方法を提示する。
2. ISDMのための逆問題ツール： 下界を導出するために、本論文は二つの高確率なインタラクティブ逆問題手法を導入する：
   • インタラクティブ・ファノの手法（Interactive Fano's Method）： 大規模なモデルクラスに適した事前分布に基づくアプローチであり、下限ミニマックス・クオンタイルに対する明示的な下界を与える。
   • インタラクティブ・レ・カンの手法（Interactive Le Cam's Method）： 二点簡約アプローチであり、誘導されたインタラクティブな法則の下での二つのモデル間の識別可能性（全変動距離またはKLダイバージェンス）に基づく境界を提供する。
3. プライバシーの統合： 本論文は、MIプライベートな問題を、有界な相互情報量制約（$I(S; Y) \le \epsilon$）を満たすものに制限された許容可能な決定則のクラスとして、MIプライベートなISDMインスタンスとしてモデル化する。座標成分ごとのガウス型プライバシー化については、プライバシーの効果を分散増幅因子として孤立させる「二点テンプレート」を導出する。これにより、プライバタイズされたメカニズムの誘導された出力法則を分析することで、一般的なISDM逆問題ツールをプライベートな設定に適用することが可能になる。

主な貢献

• ISDMのための$\delta$-明示的ミニマックス・クオンタイル理論： 本論文は、非インタラクティブなクオンタイル理論とインタラクティブな期待値理論の間の溝を埋める、インタラクティブな問題に対する厳密なミニマックス・クオンタイル下界の最初の体系的な展開を提供する。
• 高確率なインタラクティブ逆問題ツール： ISDMに特化した、信頼レベル$\delta$に対する明示的な依存関係を持つ、高確率版のファノおよびレ・カンの手法の導出。
• 統一されたプライバシー・フレームワーク： MIプライベートな決定問題を、制約付きISDMインスタンスとして定式化する。このアプローチは、一般的なミニマックス・クオンタイル論証と、プライバシーに起因するダイバージェンス制約の検証を分離する。
• 座標成分ごとのガウス型プライバシー化テンプレート： ガウス型プライバシー化に関する具体的な導出を行い、プライバシーのペナルティを、MI予算を満たすために必要な最小ノイズ分散 $\sigma^2_{\min}$ を用いた乗法的分散増幅因子 $1 + \sigma^2_{\min}(\epsilon, d)$ として定量化する。

結果
著者らは、自身の理論を5つの具体的な例に適用し、信頼レベル$\delta$、サンプルサイズ／ホライゾン、およびプライバシー予算$\epsilon$に依存する明示的な下界を導出している：

1. ガウス平均推定（古典的）： インタラクティブなレ・カンの手法を用いて、二乗誤差損失における既知のスケーリング $\frac{\log(1/\delta)}{n}$ を回収する。
2. 二腕ガウスバンディット（古典的）： 境界が $T$ で切り捨てられることを示し、有界平均バンディットの高信頼性後悔レートを示すスケーリング $\sqrt{T \log(1/\delta)}$ を導出する。
3. $K$腕ガウスバンディット（古典的）： インタラクティブ・ファノの手法を用い、下界が $\sqrt{KT \log(1/\delta)}$ とスケーリングすることを示し、$K$個の腕にわたる探索コストを捉える。
4. ガウス平均推定（プライベート）： 座標成分ごとのガウス型MIプライバシーの場合、下界は $\frac{1 + \sigma^2_{\min}(\epsilon, n)}{n} \log(1/\delta)$ となる。プライバシー制約は分散を増幅させ、$\epsilon$ が減少するにつれて境界を悪化させる。
5. 二腕ガウスバンディット（プライベート）： 下界は $\sqrt{(1 + \sigma^2_{\min}(\epsilon, T)) T \log(1/\delta)}$ とスケーリングする。推定のケースと同様に、プライバシーメカニズムは分散増幅因子を導入し、高信頼性のパフォーマンスを低下させる。

意義および主張
本論文は、テールに敏感なミニマックス下界（推定、インタラクション、およびプライバシー）が、共通のISDMフレームワーク内で共に発展できるという統一的な視点を提供すると主張している。プライバシーを許容される決定クラスの制限として扱うことで、著者らは、複雑な情報理論的下界（ファノおよびレ・カン）のメカニズムが、根本的に新しい理論的装置を必要とせずに、プライベートな設定に直接転移することを実証している。

これらの結果は、期待リスクを超えて、失敗の確率（$\delta$ によって制御される）に関する明示的な保証を提供している点で重要である。本論文は、導出された下界が古典的なガウス平均推定に対してタイトである一方で、MI制約下でのプライベートなバンディットに対する一致する上界はまだ文献において完全に確立されていないことを明記しており、彼らの研究が高信頼性パフォーマンスにおけるプライバシー制約がインタラクティブな決定問題の根本的な困難さをどのように変化させるかを体系的に分析するための基礎的な下界理論として位置づけられることを示している。本フレームワークは、プライバシー制約が高信頼性のパフォーマンスにおけるインタラクティブな決定問題の難易度をどのように変えるかを系統的に分析するためのツールとして提示されている。