技術要約：滑らかな強凸損失に対する近最適純粋機械学習消去（Machine Unlearning）

問題設定

本論文は、**滑らかな強凸確率的凸最適化（SCO）**の枠組みにおける、**機械学習消去（machine unlearning）**の根本的な統計的コストを調査している。目標は、データセット $Z$ と、削除要求されたサブセット $U$（ここで $|U| \le m$）が与えられたとき、保持されたデータ $Z \setminus U$ 上でゼロから学習されたモデルと統計的に区別がつかない更新済みモデルを出力するアルゴリズムを設計することである。

解の品質は、超過集団リスク（excess population risk） $\Delta_{F_P}(w) = F_P(w) - F^*_P$ （ここで $F_P$ は集団損失）によって測定される。中心となる問いは、「滑らかな強凸SCOにおいて、$m$ 個のサンプルに対する $\epsilon$-unlearning のミニマックス最適超過集団リスクは何か？」である。

本論文では、近似 $\epsilon$-unlearning を検討している。これは、$(Z, U)$ に対する unlearning アルゴリズムの出力分布が、削除要求なしで $Z \setminus U$ 上で実行された学習アルゴリズムの出力分布と（最大ダイバージェンスの意味で）$\epsilon$-indistinguishable（$\epsilon$-識別不能）である必要があることを意味する。

手法

1. 上界：Core-Swap $\epsilon$-Unlearning アルゴリズム

著者らは、2つの極端な戦略を補間する新しいアルゴリズム（Algorithm 1）を提案している。

• ゼロからの再学習（Retraining from Scratch: RFS）: 保持されたデータ $Z \setminus U$ 上の経験リスク最小化（ERM）を返す。これは厳密な 0-unlearning を満たすが、データを破棄することによる高い統計的誤差が生じる。
• 要求の無視（Ignore Request）: 全データ $Z$ 上の ERM を返す。これは正確であるが、unlearning の保証を満たさない。

メカニズム:
このアルゴリズムは、解空間の幾何学を利用している。出力のための混合分布を以下のように構築する：

1. 高確率: 全データ ERM 解 $\hat{w}_Z$ を中心とする小さな球内から一様にサンプリングする。これにより高い精度を確保する。
2. 低確率: 減少データ ERM 解 $\hat{w}_{Z \setminus U}$ を中心とするより大きな球内から一様にサンプリングする。この球のサイズは、有効な削除後に、同じ保持データセット $Z \setminus U$ を結果として生じさせ得るあらゆる可能な全データ ERM 解をカバーできる程度に大きく設定される。

これらの球の半径と混合確率 $\eta$ を注意深く調整することで、アルゴリズムは「ドライラン（削除なし）」と「真の実行（削除あり）」の間の尤度比が $e^\epsilon$ 以下に抑えられることを保証する。このアルゴリズムは、2回の ERM オラクル呼び出しと1回の凸射影を必要とし、$O(d)$ の時間で動作する。

2. 下界：パッキング引数（Packing Argument）

最適性を確立するために、著者らは標準的な差分プライバシーの議論とは異なるパッキング手法を用いて下界を導出している。

• 構成: 単位球内の多くの分離された方向を指す「困難な」平均推定インスタンスの集合を構築する。
• 削除戦略: 各インスタンスに対して、特定の削除要求を定義し、高確率で「信号」サンプル（非ゼロ成分）を削除する。
• 崩壊: 削除後、これらすべての異なるインスタンスの保持データセットは、共通のリファレンスデータセット（すべてゼロ）へと収束する。
• 識別不能性: $\epsilon$-unlearning の制約により、これらすべての異なる初期インスタンスに対する出力分布は、共通のリファレンスデータセットによって生成される分布に近くなければならない。
• パッキング限界: パッキングのサイズ（分離された方向の数）が、アルゴリズムが真の平均を回復できる精度を制限し、エラーの下界を導く。

主な貢献と結果

1. ミニマックス最適レート

本論文は、滑らかな強凸 SCO に対する超過集団リスクの、ほぼタイトな上界と下界を確立している。最適レートは次のように特徴付けられる：
$$\text{Risk} \approx \frac{1}{n} + \left(\frac{m}{n}\right)^2 e^{-2\epsilon/(d+2)}$$
ここで：

• $\frac{1}{n}$ は標準的な統計誤差項である。
• $\left(\frac{m}{n}\right)^2$ はゼロからの再学習によるペナルティである。
• $e^{-2\epsilon/(d+2)}$ は、提案された unlearning アルゴリズムによって達成可能な指数関数的な改善因子である。

これらのバウンドは、条件数 $\kappa = \beta/\mu$ （$\beta$ は滑らかさ、$\mu$ は強凸性）の因子を除いてタイトである。

2. 平均推定に関するシャープな特性化

$\mathbb{R}^d$ における単位球上の平均推定という特定のケースについて、著者らは定数まで一致する上界と下界を提供している。これにより、この標準的な設定における unlearning の統計的代価に関する、実質的にシャープな特性化が得られている。

3. ベースラインと先行研究の分析

• ゼロからの再学習 (RFS): 本論文は、RFS が $O(1/n + (m/n)^2)$ の超過リスクを達成することを示すシャープな分析を提供している。これは $\epsilon \lesssim d$ の場合に最適であることが証明されている。
• 差分プライバシー (DP): 著者らは、標準的な DP ベースライン（group DP）が $O(1/n + d^2 m^2 / (\epsilon^2 n^2))$ のリスクをもたらすことを指摘しており、これは $\epsilon \gg d$ の場合、提案手法と比較して劣っている。
• 既存アルゴリズム: 著者らは [SAKS21] のニュートンステップ・アルゴリズムの分析を精緻化し、unlearning エラー項における二次的な改善を示し、[AKGK25] のユーティリティ分析におけるバグを特定して、修正された保証を提供している。

4. レジーム分析

結果は、プライバシー予算 $\epsilon$ と次元 $d$ の比率に基づく2つの明確なレジームを区分している：

• 低予算レジーム ($\epsilon \lesssim d$): ゼロからの再学習が統計的に最適である。unlearning によるペナルティは $(m/n)^2$ 項を超えて改善することはできない。
• 高予算レジーム ($\epsilon \gg d$): 提案されたアルゴリズムは、ゼロからの再学習や DP ベースラインと比較して、精度において指数関数的な改善を提供する。unlearning によるペナルティは $\exp(-2\epsilon/(d+2))$ の因子によって減少する。

重要性と主張

本論文は、滑らかな強凸 SCO における $\epsilon$-unlearning のミニマックス最適超過リスクに関する未解決問題を、ほぼ解決したと主張している。

• 基本的限界: unlearning の統計的コストは固定されたペナルティではなく、unlearning バジェットとモデル次元の比率に指数関数的に依存することを確立した。
• 効率性: 提案されたアルゴリズムは、十分なプライバシー予算があれば、厳格な unlearning 制約を満たしながらも、高い精度（フルデータ ERM に近い精度）を達成できることを示している。
• ユーティリティとプライバシーのトレードオフ: 本研究は、「忘れられる権利」とモデルの有用性のトレードオフを明確にし、高次元モデルにおいて十分なプライバシー予算がある場合、unlearning は（ゼロからの再学習のように）重要な統計情報を破棄することによるコストを必ずしも伴わないことを示している。

著者らは、一般的な SCO に関するバウンドは条件数因子によって異なることを注記しており、平均推定を超えた完全なシャープな特性化へのギャップを残している。また、非凸最適化への拡張や、明示的なストレージ・計算制約の取り扱いを今後の課題として挙げている。