The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

技術要約：近似差分プライバシーにおける連続カウントのための二分木メカニズムの最適性

問題定義
本論文は、**プライベートな連続カウント（private continual counting）**という根本的な問題に取り組んでいる。この設定では、組織は長さ $n$ のバイナリ・ストリーム $x \in \{0, 1\}^n$ を観測する。ここで、タイムステップ $i$ における '1' は、単一の個人によるイベントの寄与を示す。目標は、すべてのタイムステップ $i \in [n]$ において、累積和（接頭辞和）$Ax$を、$(\epsilon, \delta)$-差分プライバシー（DP）を満たしながら公開することである。ここで、$A$ は $n \times n$ の下三角接頭辞和行列である。精度の主要な指標は、期待 $\ell_\infty$ 誤差 $\mathbb{E}[\|M(x) - Ax\|_\infty]$ であり、これはすべてのタイムステップにおける最悪の誤差を表す。

**二分木メカニズム（binary tree mechanism）**は、このタスクのための標準的なアルゴリズムであるが、近似DP設定（$\delta > 0$）におけるその最適性は未解決の問いであった。これまでの分析では、二分木メカニズムは $\ell_\infty$ 誤差 $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$ を達成することが示されていた。しかし、既知の最良の下界は $\Omega(\log n / \epsilon)$ （具体的には、期待二乗最悪誤差の平方根に対して）に過ぎず、$\log^{3/2} n$ というストリーム長 $n$ に対する依存性が本当に必要なのかどうかについて、ギャップが残されていた。

手法および証明の概要
著者らは、$\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$ という一致する下界を確立することにより、二分木メカニズムが漸近的に最適であることを証明する。証明は、以下の主要な技術的ステップを通じて進行する：

1. 忘却型メカニズムへの帰着（Reduction to Oblivious Mechanisms）： 先行研究に従い、著者らは問題を、入力 $x$ と独立したノイズベクトル $z$ を持つ形式 $M(x) = Ax + z$の忘却型メカニズムの分析へと帰着させる。目標は$\mathbb{E}[|z|_\infty]$ を下から抑えることとなる。
2. 木基底分解（Tree Basis Decomposition）： 標準的な基底で直接ノイズを分析する代わりに、著者らは完全二分木によって誘導される基底を用いてノイズベクトル $z$ を分解する。具体的には、部分木（部分木の葉のインジケーター）に対応するベクトル $\chi_u$ を定義する。この基底において、任意のリーフ $i$ におけるノイズは、ルートからリーフ $i$ への経路に沿った係数 $b_u$ の総和となる。これにより、最大座標誤差をバウンディングする問題が、ルートからリーフへの経路に沿ったノイズの蓄積をバウンディングする問題へと変換される。
3. ノイズの蓄積と残留不確実性（Noise Accumulation and Residual Uncertainty）： 証明では「残留ノイズ」$\sigma_u$ の概念を導入する。もしあるノード $u$ におけるノイズが、その下の部分木のノイズから高精度に予測可能であれば、プライバシーが侵害されると著者らは主張する。著者らは、$\sigma_u$ を、部分木のノイズを条件としたときの現在のノードのノイズ係数の予測における期待絶対誤差と定義する。彼らは、期待 $\ell_\infty$ 誤差が、ランダムなルート・リーフ経路に沿ったこれらの残留不確実性の加重和によって下限付けられることを示す。
4. 「予測」の障害の克服（Overcoming the "Prediction" Obstacle）： 大きな課題は、入力 $x$ が未知であるため、アドバーサリ（攻撃者）は部分木のノイズを直接観察して現在のノードのノイズを予測できないことである。これを回避するために、著者らは「孫（grandchildren）」戦略を採用する。特定の部分木に注意を向け、メカニズムの3つの独立したコピーを利用することで（合成特性を利用）、アドバーサリがノイズ分散を制御できる median-of-three trick を用いて、分散の制御された $q$ を持つ線形測定 $x_i \nu_i + q$ を計算できる派生メカニズムを構築できることを示す。
5. 線形測定とハール・ウェーブレット（Linear Measurements and Haar Wavelets）： 最終ステップでは、ハール・ウェーブレット基底に着想を得た線形測定を用いてアドバーサリを構成する。直交する測定ベクトルを選択することにより、著者らはアドバーサリの推定の二乗誤差の和を、残留ノイズの $\ell_2$ ノルムに関連付ける。彼らは、もし残留ノイズ $\sigma_u$ が小さければ、アドバーサリは高い確率で隣接する入力を識別でき、これは差分プライバシーに抵触することを示す。これにより、残留ノイズは大きく、具体的には $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$ でなければならないことが強制される。
6. 総和（Summation）： これらの残留不確実性を経路に沿って合計することで、最終的な $\Omega(\log^{3/2} n)$ の下界が得られる。

主な貢献と結果

• 二分木メカニズムの最適性： 本論文は、近似DPにおいて、あらゆる連続カウントのメカニズムは期待 $\ell_\infty$ 誤差 $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$ を被らなければならないことを証明している。これは、定数倍を除いて、二分木メカニズムの上界と一致しており、$\log^{3/2} n$ への依存性が必要であるという未解決問題を解決した。
• 純粋DP境界のタイト化（Tightening Pure DP Bounds）： 純粋DP（$\delta = 0$）の場合、既知の上界 $O(\log^2 n / \epsilon)$ と下界の間のギャップを、$\Omega(\log^{3/2} n / \epsilon)$ という下界を示すことでタイトにしている。
• 遺伝的ディスクレパンシー（Hereditary Discrepancy）からの分離： 帰結として、著者らは遺伝的ディスクレパンシーとプライベートな線形クエリの誤差との間で、可能な最大の分離を導出している。彼らは、一般的な上界 $err_{\epsilon, \delta}^\infty(A) = O(\log^{3/2} m \cdot \text{herdisc}_\infty(A))$ が、接頭辞和行列が遺伝的ディスクレパンシー 1 を持ちながら $\Omega(\log^{3/2} n)$ の誤差を必要とするという事実により、クエリ数 $m$ に対する依存性においてタイトであることを示している。

意義
本論文は、近似DPの設定における連続カウントのための二分木メカニズムが漸近的に最適であることを証明することにより、差分プライバシーにおける中心的な未解決問題を解決したと主張している。開発された手法、特に、木ベースのノイズ分解、残留ノイズ分析、および線形測定攻撃を扱うための median-of-three trick の組み合わせは、下界を証明するための新しいアイデアとして提示されており、さらなる応用が期待される。この結果は、現在の最先端のアルゴリズムが、ストリーム長 $n$ に対する依存性の観点から大幅に改善できないことを裏付けている。