A Stochastic Gradient Method with an Exponential Convergence Rate with Finite Training Sets

概要

データが事前に固定されていれば，ある種の一般的条件設定のもとで，データ数に対して定数オーダーの計算コストで線形収束を実現するSGDを提案．確率的最適化手法であるSGDと全データの勾配を毎ステップ計算して最適化するGDのハイブリッド（良いとこ取り）手法を提案し，こちらも理論的・実験的に非常に高速に最適解へ収束する事を示した．

背景

• 近年，ビッグデータが流行ってます
• 大量のデータから高速に学習する手法が求められています
  • イテレーションコストを小さく，収束レートを早く

貢献

• Stochastic Average Gradient method (SAG) を提案
• SAGは線形収束することを証明
  • 損失関数が微分可能，最適化問題はStrongly Convexである等の条件がいくつかあるが，大体の問題設定では満たされる

アルゴリズム

• 1. データを1つランダムに選択し，現在の重みベクトルで勾配を計算
• 2. 各データの「最後に」算出された勾配を集め，その平均ベクトルを用いて学習器を更新
• 3. 一定の回数反復，あるいは一定の収束基準を満たすまで，1,2ステップを反復

実装上の工夫など

• SAGを回す前に一度SGDをワンパス回すとさらに収束早くなる場合が多い
• 正則化項を入れる場合は，正則化項は勾配近似せずに陽に最適化すると良い
• 線形分類器の場合は，各データに関して保存しておくべき量はスカラー値１個のみ

雑感

• 以前も結構話題になっていたので，すでに読んでいる人も多い？
• 以前実装して実験を回してみましたが，実際SGDより遥かに高速に収束してました
  • コードは一応公開してます https://github.com/kisa12012/stochastic_average_gradient
• 証明を解釈する会開きましょう（白目）