ランダムウォーク学習とパックマン攻撃

概要: ランダムウォーク（RW）ベースのアルゴリズムは、低オーバーヘッドでスケーラブルであることから、分散システムにおいて長らく人気を集めてきました。また近年では、分散型学習（decentralized learning）における応用が急速に増えています。しかし、それらが局所的な相互作用に依存しているため、悪意のある振る舞いに対して本質的に脆弱です。本研究では、「Pac-Man」攻撃と呼ぶ敵対的脅威を調査します。これは、悪意のあるノードがそれを訪れる任意のRWを確率的に停止（終端）させるものです。このステルス性の高い振る舞いによって、活性なRWがネットワークから徐々に消滅し、失敗アラームを引き起こすことなく、学習プロセスを実質的に停止させます。この脅威に対抗するために、平均交差（Average Crossing, AC）アルゴリズムを提案します。これは、Pac-Manの存在下でもRWの絶滅（extinction）を防ぐためにRWを複製する、完全に分散化されたメカニズムです。理論解析により、(i) ACのもとでRWの個体数はほぼ確実に有界に保たれること、そして (ii) Pac-Manが存在していてもACのもとでRWベースの確率的勾配降下法（stochastic gradient descent）は収束し、真の最適解からのずれを定量化できることを示します。合成データセットおよび現実世界のデータセットの両方に対する広範な実験結果は、これらの理論的知見を裏付けています。さらに、それらは、複製の閾値（duplication threshold）に関数として対応する絶滅確率における相転移を明らかにします。観測された相転移を説明するために、ACの単純化した変種を解析することで理論的洞察を提供します。