ランダム化サブスペース・ネステロフ加速勾配

Abstract

ランダム化サブスペース法は、低次元の射影勾配情報のみを用いることで、一階最適化のコストを削減する。これは、順方向モードの自動微分や、通信が制限された状況で魅力的な特徴である。Nesterov 加速は、全勾配法や座標に基づく方法については十分に理解されている一方で、射影勾配情報のみを用い、さらにオラクル計算量において全次元の Nesterov 加速より改善し得る、一般のサブスペース・スケッチに対する加速法を得ることは、技術的に非自明である。 我々は、行列平滑性（matrix smoothness）および一般的なスケッチのモーメント仮定の下で、滑らかな凸最適化および滑らかな強凸最適化に対する、ランダム化サブスペース Nesterov 加速勾配法を開発する。主要な技術的要素は、行列平滑性に合わせて設計された三系列の定式化であり、これにより全次元の場合には対応する古典的な Nesterov 法が復元される。得られた理論は、加速されたオラクル計算量の保証を確立し、行列平滑性とスケッチ分布が計算量にどのように組み込まれるかを明示する。また、スケッチ族を比較するための統一的な基盤を提供し、さらにどのときに、オラクル計算量においてランダム化サブスペース加速が全次元の Nesterov 加速より改善するのかを特定することも可能にする。