共強圧ゲームにおける学習のためのラストイテレート保証

要旨: ノイズのあるフィードバックの下で、co-coercive（共コーサイブ）ゲームにおけるバニラ確率的勾配降下法（stochastic gradient descent）に対して、有限時間での最後の反復（last-iterate）保証を確立する。これは、強単調（strongly monotone）なゲームよりも一般的な広いクラスのゲームであり、複数のナッシュ均衡を許容し、例えば、負半定値の相互作用行列をもつ二次ゲームや、滑らかな凹ポテンシャルをもつポテンシャルゲームを含む。この設定での先行研究は、反復が均衡に近づくにつれてノイズが消失する相対ノイズ・モデルに依存してきたが、この仮定は実際にはしばしば非現実的である。我々は代わりに、ノイズの第2モーメントが、反復のノルムの2乗に対してアフィンにスケールすることを許す、はるかに一般的なノイズ・モデルの下で取り組む。この仮定は、作用空間が有界でない（unbounded）学習において自然である。このモデルのもとで、最後の反復に対する次数 O(
log(t)/t^{1/3}) の上界を証明する。これは、非消失ノイズの下でco-coerciveゲームに対する最初のそのような上界である。さらに、反復がナッシュ均衡の集合へ確率1で収束することを示し、時間平均の収束保証を導出する。