技術要約：無限ストリーム推定のためのパーソナライズされたw-イベント・プライバシー

1. 問題定義

本論文は、個々のユーザーのプライバシーを差分プライバシー（DP）の下で保護しつつ、無限のデータストリームから統計量を推定するという課題に取り組んでいる。既存のw-イベント・プライバシー（スライディングウィンドウ $w$ 個の連続するタイムスロットにわたるユーザーデータの保護）の手法は、通常、すべてのユーザーに対して一律のプライバシー予算（$\epsilon$）とウィンドウサイズ（$w$）を適用する**均質的（homogeneous）**な要件を強制する。

この「一律（one-size-fits-all）」のアプローチは、ユーザーごとに異なるプライバシーの好みが存在する現実世界のシナリオにおいては最適ではない。例えば、著名人は位置情報に対して強力な保護（大きな $w$、小さな $\epsilon$）を必要とする一方、ストリートアーティストは知名度を最大化するために、より弱い保護を好む可能性がある。すべてのユーザーに対して最も厳しい要件を強制すると、過剰なデータ誤差（低い有用性）が生じ、最も緩い要件を強制すると、機密性の高いユーザーの保護に失敗する。

本論文は、以下の2つの問題設定を定式化している：

1. 固定パーソナライズ設定 (PWEPP-IDS): 各ユーザー $u_i$ は、固定されたウィンドウサイズ $w_i$ と固定されたプライバシー予算 $E_i$ によって定義される静的なプライバシー要件を持つ。
2. 動的パーソナライズ設定 (DPWEPP-IDS): ユーザーは、時間とともに変化する要件を指定できる。各タイムスロット $t$ において、ユーザーは直近の過去をカバーする**後方（backward）要件（ウィンドウ $w_{B,i,t}$、予算 $E_{B,i,t}$）と、今後の未来をカバーする前方（forward）**要件（ウィンドウ $w_{F,i,t}$、予算 $E_{F,i,t}$）を宣言する。

核心となる課題は、**オンライン実現可能性（Online Feasibility）**である。システムは、各タイムスロットにおいて、これまでに消費された予算との整合性を確保し、かつ将来の要件に対する実現可能性を保証しながら、すべてのユーザーの異種混合で時変的なプライバシー制約を同時に満たす、単一の共有集計統計量を公開しなければならない。

2. 手法

著者らは、異種混合のユーザー要件を有効なシステムレベルのリリース決定へと変換する統一フレームワークを提案している。このフレームワークは、固定設定のための**パーソナライズされたウィンドウサイズ・メカニズム（PWSM）と、動的設定のための動的パーソナライズされたウィンドウサイズ・メカニズム（DPWSM）**という2つの主要コンポーネントで構成されている。

2.1 コアコンポーネント

• 最適予算選択 (Optimal Budget Selection: OBS): 異種混合のプライバシー予算の集合に対し、OBSは総報告誤差を最小化する最適な閾値 $\epsilon_{opt}$ を選択する。誤差は、閾値未満の予算を持つユーザーによるサンプリング誤差と、閾値に適用されるラプラス・メカニズムによるノイズ誤差で構成される。
• パーソナライズされたプライベートな非類似度測定: 新しい難読化された統計量を公開するか、あるいは（予算を節約するために）直前の統計量を再利用するかを決定するために、システムは現在のデータと前回の公開値との間の非類似度を計算する。この計算は、プライバシー予算の一部を使用してプライベートに行われる。
• 適応型リリース戦略: プライベートな非類似度が期待されるノイズ誤差の平方根を超えた場合、新しい公開が行われる。そうでなければ、システムはリリースをスキップ（null publication）し、直前の値で現在の値を近似する。

2.2 固定設定のソリューション (PWSM)

固定設定において、フレームワークは以下の2つのメカニズムによってインスタンス化される：

1. パーソナライズされた予算配分 (Personalized Budget Distribution: PBD):
   • 各ユーザーの総予算 $E_i$ を2つに分割する：一つは非類似度計算用、もう一つは公開用。
   • 公開予算はウィンドウ全体に均等に分配される（$E_i / 2w_i$）。
   • 公開が発生した場合、現在のウィンドウに対する残りの予算が調整される。非類似度が低い場合、予算は将来のスロットのために保存される。
2. パーソナライズされた予算吸収 (Personalized Budget Absorption: PBA):
   • より滑らかなストリーム向けに設計されている。時刻 $t$ における公開が、ユーザーのウィンドウ内の将来のタイムスロットから予算シェアを「借りる」ことを可能にする。
   • 公開が平均以上の予算を使用した場合、平均予算制約を維持するために、後続のスロットが「無効化（nullified）」（スキップ）される。
   • このメカニズムは、将来の低有用なリリースをスキップすることによって、高有用なリリースのコストを吸収する。

2.3 動的設定のソリューション (DPWSM)

動的設定では、フレームワークは DPBD および DPBA へと一般化される。これらのメカニズムは、時変的な制約を扱うための**実現可能性条件（Feasibility Conditions）**を導入している：

• 後方実現可能性 (Backward Feasibility): 時刻 $t$ で使用される予算は、現在の後方ウィンドウの残存予算（$E_{B,i,t}$ から過去の消費量を引いたもの）を超えてはならない。
• 前方実現可能性 (Forward Feasibility): 時刻 $t$ で使用される予算は、その時刻 $t$ をカバーする前方ウィンドウを持つ、過去の任意の時刻 $\tau$ で宣言された前方プライバシー要件を侵害してはならない。
• メカニズムのロジック:
  • DPBD: 各ユーザーの実現可能な予算の上限を、後方残存予算と前方残存予算（すべてのアクティブな前方ウィンドウから導出される）の最小値を取ることによって算出する。その後、この実現可能な予算を非類似度と公開用に分割する。
  • DPBA: 動的なウィンドウに対して吸収ロジックを拡張する。過去の前方要件に基づき、各ユーザーの「前方無効化右境界（forward nullified right border）」を計算する。現在のタイムスロットがこの境界内に含まれる場合、リリースはスキップされる。そうでなければ、すべてのアクティブな前方制約を尊重しつつ、将来のスロットから吸収可能な最大予算を計算する。

3. 主な貢献

1. 問題の定式化: 本論文は、**動的パーソナライズされたw-イベント・プライベート・パブリッシング（DPWEPP-IDS）**を定義し、時変的な後方および前方プライバシー要件を許可することで、固定パーソナライズ設定を一般化した。また、プライバシー概念 $(\tau, w_B, w_F, E_B, E_F)\text{-EPDP}$ を導入した。
2. オンライン実現可能性の課題: 単一の共有リリースが、重複するウィンドウを持つ異種混合の時変的な制約を同時に満たさなければならないという、新規性の高い課題を特定し、対処した。
3. 統一フレームワーク: 著者らは、最適予算選択 (OBS) と適応型リリース戦略を用いて、異種混合のパーソナライズされた要件を共有リリース決定へと変換する、統一フレームワーク（PWSM/DPWSM）を提案した。
4. メカニズム:
   • PBD & PBA: 固定パーソナライズ設定のためのソリューション。
   • DPBD & DPBA: 後方および前方の実現可能性を厳格に遵守する、動的パーソナライズ設定のためのソリューション。
5. 理論的保証: すべてのメカニズムがそれぞれのパーソナライズされた差分プライバシー定義を満たすことを証明し、平均誤差（有用性）の理論的上界を確立した。
6. 実験的検証: 実データおよび合成データを用いた広範な実験により、提案されたメカニズムが古典的な均質的ベースライン（BDおよびBA）よりも有用性において大幅に優れていることを示した。

4. 実験結果

著者らは、実世界および合成データの両方でメカニズムを評価した。

• パフォーマンス: 提案手法は、古典的な均質的ベースラインに対して一貫して有用性を向上させた。
  • 実データにおいて、DPBD は標準的な予算配分（BD）法と比較して、平均相対誤差（AMRE）を少なくとも 62.7% 削減した。
  • 合成データにおいて、DPBA は標準的な予算吸収（BA）法と比較して、AMRE を少なくとも 53.6% 削減した。
• スケーラビリティ: 理論的分析によれば、時間の計算量はユーザー数（$n$）および最大ウィンドウサイズに対して線形であり、このアプローチは大規模なユーザー集団に対してもスケーラブルである。

5. 意義と主張

本論文の主な貢献は、単にグローバルなパラメータをパーソナライズされたものに置き換えることではなく、重複し、異種混合で、かつ時変的な制約の下で、有効な共有リリース予算を構築し維持することにあると主張している。

• 一般化: 本研究は、プライバシーの好みが時間とともに進化するという、より一般的で実用的な設定へとw-イベント・プライバシーのパラダイムを拡張している。
• 実現可能性: 単一の集計リリースが、過去の予算消費と将来のプライバシー実現可能性の両方と整合し続けるという、非自明な問題を解決している。これは、従来の均質的なw-イベント・プライバシーには存在しない課題である。
• 実用性: ユーザーが異なるプライバシーレベルを設定できるようにすることで、システムは「一部のユーザーを過剰に保護する（高い誤差を引き起こす）」ことと「他のユーザーを保護不足にする」ことの間のトレードオフを回避できる。結果は、パーソナライズされたメカニズムが、個々のユーザーに求められる特定のプライバシー保証を損なうことなく、大幅に高いデータ有用性を達成できることを示唆している。

著者らは、信頼できるキュレーター（trusted curator）の仮定は中央集約的なストリームリリースの標準的なものであるとしつつも、提案されたメカニズムは、既存の中央集約的手法（BD, BA, RescueDP, SPASなど）がサポートしていない、異種混合および動的なプライバシー要件を扱うというギャップに特に対処していると述べている。