凸最適化のための増分確率的サブグラデントアルゴリズム

本論文では、2つの制約付き増分サブグラデントアルゴリズムに対する確率的誤差の影響を研究します。増分サブグラデントアルゴリズムは、各構成関数が分散ネットワークの特定のエージェントのみに知られている場合に、関数の和を最小化するために適用される分散型ネットワーク最適化アルゴリズムと見なされます。まず、標準的な循環増分サブグラデントアルゴリズムを研究します。このアルゴリズムでは、エージェントがリング構造を形成し、反復結果をサイクルで渡します。サブグラデント評価に確率的誤差がある場合、減衰ステップサイズを使用したときにほぼ確実な収束を保証する確率的誤差のモーメントに関する十分条件が得られます。さらに、一定のステップサイズでのアルゴリズムの性能に関するほぼ確実な境界も得られます。次に、マルコフランダム化増分サブグラデント法を研究します。これは、計算エージェントのシーケンスが時間非同質マルコフ連鎖としてモデル化される増分アルゴリズムの非循環版です。このようなモデルは、モバイルネットワークに適しており、これらのネットワークでは時間の経過とともにネットワークトポロジーが変化します。減衰および一定のステップサイズにおいて確率的誤差のあるマルコフランダム法の収束結果と誤差境界が得られます。