Locally Private Online Quantile Regression: Estimation and Inference

技術要約：局所プライバシー保護下でのオンライン分位点回帰

問題提起
本論文は、ワンレポート（1回の報告）、ユーザーレベルの$\varepsilon$-局所差分プライバシー（$\varepsilon$-LDP）プロトコル下で、オンライン分位点回帰（QR）を実行するという課題に取り組んでいる。標準的なオンラインQRでは、サーバーは推定量の更新に、推定方程式への寄与 $g_\beta(X, Y) = X \{ \mathbb{1}(Y \le X^\top \beta) - \tau \}$ を用いる。このベクトルは、共変量 $X$ と残差比較（指示関数）を結合させている。ユーザーレベルのLDP下では、サーバーは各ユーザーからプライバシー保護された報告のみを受け取る。核心となる困難は、標準的なこのベクトルのプライバシー保護は、プライバシー制約を遵守するか、あるいは確率的近似に必要な条件付き平均の構造を破壊するかのいずれかを選択せざるを得ないという点にある。具体的には、サーバーが $X$ と指示関数を直接観察できない場合、収束に必要な不偏な更新ベクトルを形成することができない。既存の手法であるスカラーのプライベート分位点、あるいは中央集権型・プライベート分散型QRは、この「デコードされた推定方程式」の問題に対処していない。すなわち、単一のLDP報告を、いかにして不偏な共変量依存の更新へと変換するかという問題である。

手法
著者らは、サーバーが生の勾配を受け取るのではなく、推定方程式の条件付き平均を保持するデコードされた入力を受け取るフレームワークを提案している。

1. サポートを考慮した幾何学（Support-Aware Geometry）: 正確なQR推定方程式への寄与 $g_\beta(O)$ は、特定の二面体サポート幾何 $G_\tau$ 上に存在する。切片座標は、アクティブな面（$\mathbb{1}(Y \le X^\top \beta) = 0$ または $1$）を特定し、傾き座標は、その面と有界な共変量によって決定される対称な区間に制約される。
2. CQX($q, s$) チャネル: 著者らは、傾きの量子化のためのグリッドサイズ $q$ と、選択された座標ブロックのサイズ $s$ を持つ、CQX($q, s$) と名付けられた有限アルファベットチャネルを構築した。
   • ローカル処理: 各ユーザーは、ローカルで $g_\beta(X, Y)$ を計算する。ユーザーは、選択された傾き座標を（公開グリッドを用いて）確率的に量子化し、有限のカテゴリに分類する。もし切片が選択された場合は、それが面のラベルとして機能し、そうでなければ傾きは無条件のグリッド上で量子化される。
   • ランダム応答（Randomized Response）: ユーザーは、得られた有限カテゴリ（「選択されたブロックのカテゴリ」）に対してランダム応答を適用し、単一のLDP報告を生成する。
   • サーバー側デコーディング: サーバーは、歪みを補正するためにアフィン・ランダム応答デコーダを適用し、ホイト・トンプソン（Horvitz-Thompson）再構成を用いて完全なベクトルを復元する。
   • 主要な特性: デコードされた入力 $\tilde{g}_\beta$ は、条件付き不偏性 $E[\tilde{g}_\beta(X, Y) \mid X, Y, \beta] = g_\beta(X, Y)$ を満たす。これにより、サーバーはターゲットとなるパラメータにバイアスを与えることなく、投影されたポラック・ルパート（Polyak-Ruppert）平均化スキーム（$\beta_i = \Pi_B \{ \beta_{i-1} - \eta_i \tilde{g}_i(\beta_{i-1}) \}$）においてデコードされた入力を使用できる。
3. 推論: 著者らは、QRのヘッセ行列の推定が困難であることを踏まえ、ヘッセ行列を用いない推論手法を開発した。これには以下が含まれる：
   • 自己正規化（Self-Normalization, SN）: 単一の軌跡におけるポラック平均の経時的な変動を利用する。
   • 分割統治（Divide-and-Conquer, DC）: ストリームを互いに素なグループに分割し、グループ平均を計算してHotelling型の信頼集合を形成する。
   • HiGrad: 公開された木構造を使用して、既知の共分散テンプレートを持つ相関したグループセンターを生成する。

主な貢献

1. 定式化: ストリーミング線形QRを、逐次的なワンレポート・ユーザーレベルLDPの下での「デコードされた推定方程式問題」として定式化し、報告のプライバシー保証と、平均保持の要件を分離した。
2. メカニズムの構築: 公開座標選択、サポートを考慮した確率的量子化、ランダム応答、およびアフィンデコーディングを組み合わせたCQX($q, s$) チャネルを導入した。このメカニズムは、デコードされたサーバー入力が条件付き不偏であることを保証するために、QR寄与の二面体サポート幾何を利用している。
3. 理論的保証: 固定された有限チャネル設計に対し、著者らは以下を証明した：
   • ワンレコードの寄与に対する局所プライバシー（$\varepsilon$-LDP）。
   • 条件付きデコーダの不偏性。
   • 投影されたポラック・ルパート平均化推定量の一致性と漸近正規性。
   • 事前指定されたスカラーコントラストおよびベクトル楕円体に対する、妥当な自己正規化推論。
4. 実証的検証: シミュレーションおよびニューヨーク市タクシー走行データの例示を通じて、プライバシー予算（$\varepsilon$）が増加するにつれて、プライベートな軌跡が非プライベートなオンライン参照モデルに近づくことを示した。提案されたチャネルは、直接的なラプラス放出（サポートを無視するもの）や面指数放出（平均をシフトさせるもの）と比較して、推定誤差および不確実性の定量化において優れた性能を示した。

結果

• 推定精度: シミュレーションにおいて、CQX($q, s$) メカニズムは、幾何学的ベースライン（直接ラプラスおよび面指数）と比較して、より低い平均ユークリッド推定誤差を達成した。面指数メカニズムは、平均場ミスマッチによる投影境界の飽和により、高い分位点（$\tau=0.75$）においてしばしば失敗する。
• 高予算下での回復: $\varepsilon \to \infty$ かつグリッド解像度 $q$ が増加するにつれ、プライベートな推定量の共分散は、非プライベートなASGDオラクルへと収束する。
• 推論の較正: 自己正規化（SN）、分割統治（DC）、およびHiGradの手順は、特にスカラーコントラストおよび高密度コントラストにおいて、公称95%レベルに近い被覆率を持つ信頼区間を提供する。フルベクトル楕円体は、有限の有効情報と条件付けに対してより敏感であるが、規定されたランク条件の下で妥当である。
• 実データへの適用: NYCタクシーデータセットにおいて、プライベートな推定値は、非プライベートな参照モデルと同等のホールドアウト較正（ヒットレート）および予測チェック損失を維持しており、$\varepsilon$ の増加とともに性能が向上することを示した。

意義と主張
本論文は、平均を保持するデコードされた推定方程式入力に基づく、オンラインQR推定および推論のための初のワンレポートLDPフレームワークを提示すると主張している。標準的な加法的ノイズSGDアプローチは、QRの特有のサポート幾何を無視するため、QRには適さないと論じている。デコーディングステップを通じてプライバシーメカニズムと推定更新を分離することで、著者らは、ワンレポートの局所プライバシーがオンラインQRと両立可能であることを示した。その意義は、信頼できるキュレーターやユーザーあたりの複数レポートを必要とせずに、ストリーミングかつプライバシー制約のある環境において、妥当な統計的推論（一致性、正規性、信頼区間）を可能にした点にある。著者らは、本理論が意図的に固定次元であり、有界な共変量に依存していることを注記しており、高次元設定や適応的なチャネル設計への拡張は今後の課題としている。