論文の概要: Random Walk Learning and the Pac-Man Attack

• arxiv url: http://arxiv.org/abs/2508.05663v2
• Date: Fri, 15 Aug 2025 15:28:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-18 14:51:23.55766
• Title: Random Walk Learning and the Pac-Man Attack
• Title（参考訳）: ランダムウォーク学習とパックマン攻撃
• Authors: Xingran Chen, Parimal Parag, Rohit Bhagat, Zonghong Liu, Salim El Rouayheb,
• Abstract要約: 我々は,悪質なノードが訪問する任意のRWを確率的に終了させる,パックマン攻撃(Pac-Man's attack)と呼ぶ敵の脅威を調査する。 このステルスな動作は、ネットワークからアクティブなRWを徐々に排除し、障害アラームを発生させることなく、学習プロセスを効果的に停止させる。 この脅威に対処するために、パックマンの存在下でのRWの消滅を防止するために、RWの完全分散機構である平均交差(AC)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 25.71166923112231
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.
• Abstract（参考訳）: ランダムウォーク(RW)ベースのアルゴリズムは、低オーバーヘッドとスケーラビリティのため、分散システムで長い間人気があり、近年は分散学習の応用が増加している。 しかし、局所的な相互作用に依存しているため、それらは本質的に悪意のある行動に弱い。 本研究では,悪意のあるノードが訪問する任意のRWを確率的に終了する「パックマン攻撃」と呼ばれる敵の脅威を調査する。 このステルスな動作は、ネットワークからアクティブなRWを徐々に排除し、障害アラームを発生させることなく、学習プロセスを効果的に停止させる。 この脅威に対処するために、パックマンの存在下でのRWの消滅を防止するために、RWを複製するための完全に分散化されたメカニズムである平均交差(AC)アルゴリズムを提案する。 我々の理論分析はそれを証明している (i)RW人口は、ほぼ確実にACとACに拘束されている。 (II) RW系確率勾配降下は、パックマンの存在下においてもAC下で収束し、真の最適値から定量的に逸脱する。 人工と実世界の両方のデータセットに関する広範な実験結果が、我々の理論的な発見を裏付ける。 さらに、彼らは複製閾値の関数として絶滅確率の相転移を発見した。 我々は、観測された相転移に光を放つACの簡易な変種を分析することによって理論的知見を提供する。

関連論文リスト

• The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models [99.98293908799731]
  本稿では,LLMによる推論,すなわち政策エントロピーの崩壊において,RLのスケーリングの大きな障害を克服することを目的としている。 実際には、エントロピーHと下流性能Rの間の変換方程式R=-a*eH+bを確立する。 Clip-Cov と KL-Cov という2つの単純かつ効果的な手法を提案する。
  論文  参考訳（メタデータ） (2025-05-28T17:38:45Z)
• Mitigating Deep Reinforcement Learning Backdoors in the Neural Activation Space [0.24578723416255752]
  本稿では,深層強化学習(DRL)エージェントポリシーにおけるバックドアの脅威について検討する。 実行時に検出する新しい方法を提案する。
  論文  参考訳（メタデータ） (2024-07-21T13:48:23Z)
• On Minimizing Adversarial Counterfactual Error in Adversarial RL [18.044879441434432]
  敵の騒音は、安全クリティカルなシナリオにおいて重大なリスクを生じさせる。 我々は,ACoE(Adversarial Counterfactual Error)と呼ばれる新しい目標を導入する。 本手法は, 対向RL問題に対処するための最先端手法を著しく上回っている。
  論文  参考訳（メタデータ） (2024-06-07T08:14:24Z)
• Rethinking PGD Attack: Is Sign Function Necessary? [131.6894310945647]
  本稿では,このような手話に基づく更新アルゴリズムが段階的攻撃性能にどのように影響するかを理論的に分析する。 本稿では,手話の使用を排除したRGDアルゴリズムを提案する。 提案したRGDアルゴリズムの有効性は実験で広く実証されている。
  論文  参考訳（メタデータ） (2023-12-03T02:26:58Z)
• Wasserstein distributional robustness of neural networks [9.79503506460041]
  ディープニューラルネットワークは敵攻撃(AA)に弱いことが知られている 画像認識タスクでは、元の小さな摂動によって画像が誤分類される可能性がある。 本稿では,Wassersteinの分散ロバスト最適化(DRO)技術を用いて問題を再検討し,新しいコントリビューションを得た。
  論文  参考訳（メタデータ） (2023-06-16T13:41:24Z)
• Strong Transferable Adversarial Attacks via Ensembled Asymptotically Normal Distribution Learning [24.10329164911317]
  多重漸近正規分布攻撃(MultiANDA)という手法を提案する。 我々は勾配上昇(SGA)の正規性を利用して摂動の後方分布を近似する。 提案手法は、防御の有無にかかわらず、ディープラーニングモデルに対する10の最先端のブラックボックス攻撃より優れる。
  論文  参考訳（メタデータ） (2022-09-24T08:57:10Z)
• Policy Smoothing for Provably Robust Reinforcement Learning [109.90239627115336]
  入力のノルム有界対向摂動に対する強化学習の証明可能な堅牢性について検討する。 我々は、スムーズなポリシーによって得られる全報酬が、入力の摂動のノルムバウンドな逆数の下で一定の閾値以下に収まらないことを保証した証明書を生成する。
  論文  参考訳（メタデータ） (2021-06-21T21:42:08Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  少数の敵対的攻撃は、数ピクセルを摂動するだけでディープ・ネットワーク(DNN)を騙すことができる。 近年の取り組みは、他の等級のl_infty摂動と組み合わせている。 本稿では,空間的・神経的摂動に対処するホモトピーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-10T20:11:36Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Scaling Equilibrium Propagation to Deep ConvNets by Drastically Reducing its Gradient Estimator Bias [65.13042449121411]
  実際には、EPによって提供される勾配推定によるネットワークのトレーニングは、MNISTよりも難しい視覚タスクにスケールしない。 有限ヌード法に固有のEPの勾配推定のバイアスがこの現象の原因であることを示す。 これらの手法を適用し、非対称な前方および後方接続を持つアーキテクチャをトレーニングし、13.2%のテストエラーを発生させる。
  論文  参考訳（メタデータ） (2020-06-06T09:36:07Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。