マルチパス前処理付き SGD の平均的安定性と有効次元

マルチパス前処理付き確率的勾配降下法（PSGD）の汎化能力に対する、母集団リスクの曲率の幾何学、ノイズの幾何学、および前処理の幾何学のトレードオフを研究します。多くの実践的な最適化ヒューリスティックは、このトレードオフをさまざまな方法で暗黙のうちにナビゲートしている。たとえば、勾配ノイズをホワイトニングしようとするものもあれば、更新を期待損失の曲率と整列させようとするものもある。母集団リスクの曲率の幾何学と勾配ノイズの幾何学が一致しない場合、一方の側面を改善する過度な選択が他方の不安定性を増幅し、統計的挙動が最適でなくなる。本論文では、平均的なアルゴリズム安定性を用いて、PSGDの汎化とこれらの曲率源に依存する有効次元を結びつける。SGDの平均的安定性の既存手法は単一パスに限定されているが、第一の貢献として、データ再利用によって生じる相関を扱うマルチパスSGDの新しい平均的安定性解析を開発する。これにより、有効次元に依存する過剰リスクの境界を導出できる。特に、不適切に選択された前処理は、最適化と汎化の両方において有効次元の依存性を不適切なものにすることを示す。最後に、上界を、対応するインスタンス依存の下界と一致する形で補完する。