技術的サマリー：ビザンチン耐性を持つ連合学習における実用的妥当性条件

1. 問題定義

連合学習（FL）において、中央サーバーは $n$ 人のクライアントから高次元のモデル更新を集約する。最大 $t$ 人のクライアントがビザンチン（悪意あるまたは故障している）場合、それらは学習プロセスを撹乱するために任意のベクトルを送信できる。核心的な課題は、特定のデータ分布や攻撃モデルに依存することなく、集約出力が正直な入力に対してどこに存在すべきかを規定する幾何学的保証である「妥当性条件」を定義することである。

出力が正直なベクトルの凸包内に存在することを要求する古典的な「凸妥当性」条件は、理論的には強力であるが、現代の FL においては実用的に欠陥がある。これは次元に依存する耐性を持ち、$d$ 次元において高々 $t < n/(d+1)$ 人のビザンチンクライアントしか許容できない。この上限は高次元モデルに対しては過度に制限的である。さらに、実用的な集約則は、正直な集団に近接したままでありながら、正直なベクトルの凸包の外部に出力を生成することが多く、この挙動は凸妥当性では捉えきれない。

2. 手法と枠組み

著者は、凸包ではなく「最小包含球（MEB）」に基づく新たな妥当性枠組みを提案する。

• MEB 妥当性: 出力ベクトルが、すべての正直な入力ベクトルを囲む最小の球内に存在することを要求する。凸包とは異なり、MEB は完全次元の物体であり、凸包から外れても正直な更新の幾何学的スケール内に留まる出力を自然に許容する。
• c-MEB 妥当性（緩和版）: 正確な MEB 妥当性が高次元において依然として耐性の限界に直面することを認識し、著者は乗法的緩和を導入する。アルゴリズムが、正直な MEB の中心に中心を持ち、半径が係数 $c$ 倍（すなわち半径 $c \cdot r^*$）に拡大された球内に出力が存在する場合、そのアルゴリズムはc-MEB 妥当性を満たすという。
• 安全領域: 著者は、MEB 妥当性に対する「安全領域」を、$n-t$ 個のベクトルのすべての可能な部分集合の MEB の交差として定義する。MEB 妥当性を満たすためには、この交差内での合意が必要であることを証明している。

3. 主要な貢献と結果

A. 正確な MEB 妥当性の限界

本論文は、高次元設定において正確な MEB 妥当性が普遍的に達成可能ではないことを確立する。

• 不可能性結果: 著者は、$n \le (d+1)t - d$ の場合、いかなる合意アルゴリズムも正確な MEB 妥当性を満たすことができないことを証明する。これは凸妥当性の耐性制限と類似しており、厳密な幾何学的包含が高次元のビザンチン耐性には不十分であることを示している。

B. 緩和された MEB 妥当性に対する最適アルゴリズム

正直な多数派（$n > 2t$）を仮定して、著者は c-MEB 妥当性に対する最適集約則であるMinMax-MEBを提示する。

• メカニズム: このアルゴリズムは、$n-t$ 人のクライアントのすべての部分集合に対して MEB を計算する。その後、これらの候補 MEB への正規化された最大距離を最小化する出力ベクトルを選択する。
• 緩和上限: 接球に関するデカルトの定理の一般化であるソディ・ゴセットの定理を用いて、著者は $n > 2t$ の場合、最適緩和係数 $c$ が以下によって上から抑えられることを証明する：
  $$c < \sqrt{2}$$
  具体的には、$c \le 1 + \frac{k-1}{k+1+\sqrt{2(k+1)k}}$ であり、ここで $k = \min\{d, \frac{n}{n-t} - 1\}$ である。この上限は $d=2$ の場合、tight（厳密）である。

C. 実用的集約則に対する妥当性保証

本論文は、既存のロバスト集約則を分析し、それらの c-MEB 妥当性定数を決定する：

1. 最小直径平均化（MDA）: $\left(1 + \frac{2t}{n-t}\right)$-MEB 妥当性を満たす。
2. メドイド: $\frac{3n-2t}{n-2t}$-MEB 妥当性を満たす。著者はまた、メドイドが $c \le 2$ に対して c-MEB 妥当性を満たすことができないことを証明する。
3. 幾何中央値: $\frac{2(n-t)}{n-2t}$-MEB 妥当性を満たす。本論文は、幾何中央値が 1.08-MEB 妥当性を満たさず、また凸妥当性も満たさないことを示す反例を提供する。

これらの結果は、厳密な凸妥当性を違反する標準的な実用アルゴリズムであっても、ビザンチンノードと正直ノードの比率に依存する定数係数で緩和された MEB 妥当性を本質的に満たしていることを示している。

D. 妥当性条件の体系的比較

著者は、MEB 妥当性と既存の条件との関係をマッピングする：

• 凸妥当性 $\implies$ MEB 妥当性: 凸包は MEB に含まれるため、凸妥当性を満たす任意の出力は自動的に MEB 妥当性を満たす。
• MEB 妥当性 $\nRightarrow$ 凸妥当性: MEB 妥当性は、凸包（例えば、凸包によって縮退した低次元部分空間内）の外部にある出力を許容する。
• 緩和された凸妥当性との関係: c-MEB 妥当性は、$\delta = (c+1)r^*$ なる $(\delta, 2)$-緩和凸妥当性を意味する。逆に、緩和された凸妥当性は緩和された MEB 妥当性を意味する。
• ボックス妥当性との関係: ボックス妥当性（座標ごとの境界）は $\sqrt{d}$-MEB 妥当性を意味するが、MEB 妥当性はボックス妥当性を意味しない。これは、MEB が完全次元であるのに対し、ボックスは特定の次元で縮退する可能性があるためである。

4. 意義と主張

本論文は、c-MEB 妥当性が、ビザンチン耐性を持つ連合学習に対する凸妥当性の実用的な代替案であると主張する。

• 理論と実践の架け橋: 分散コンピューティングで使用される幾何学的妥当性条件と、FL で使用される実用的な集約則の挙動を結びつける。
• 次元非依存性: 凸妥当性と異なり、緩和された MEB 条件（$n > 2t$ が保証されている場合）は次元に依存する耐性制限に悩まされず、高次元モデルに適している。
• バイアス上限: 著者は、c-MEB 妥当性が、正直な平均更新に対する集約のバイアスに関する分布非依存の上限を提供し、幾何学的保証をビザンチン耐性最適化の標準的な分析と結びつけることを指摘する。

5. 限界

著者はいくつかの限界を認めている：

• 計算複雑性: 最適な MinMax-MEB 則は、サイズ $n-t$ のすべての部分集合に対して MEB を計算する必要があり、$t$ が大きい場合、計算コストが高い。実用的な規則（メドイド、幾何中央値）はより効率的であるが、より弱い緩和係数を提供する。
• モデル仮定: この枠組みは、信頼できるサーバー、信頼できる通信、ユークリッド幾何学、およびビザンチンクライアントに関する既知の上限 $t$ を仮定している。
• 上限の厳密性: 上限 $c < \sqrt{2}$ は $d=2$ の場合 tight であるが、より高次元および MDA やメドイドのような特定のアルゴリズムに対する最適係数は、現在証明されているものよりも tight である可能性がある。
• 加法的対乗法的: 乗法的緩和と加法的緩和の間の関係は未解決の問題のまま残っている。