kisa12012の日記 RSSフィード Twitter

2012-12-09

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をワンパス回すとさらに収束早くなる場合が多い
  • 正則化項を入れる場合は,正則化項は勾配近似せずに陽に最適化すると良い
  • 線形分類器の場合は,各データに関して保存しておくべき量はスカラー値1個のみ

雑感

  • 以前も結構話題になっていたので,すでに読んでいる人も多い?
  • 以前実装して実験を回してみましたが,実際SGDより遥かに高速に収束してました
  • 証明を解釈する会開きましょう(白目)

投稿したコメントは管理者が承認するまで公開されません。

トラックバック - http://d.hatena.ne.jp/kisa12012/20121209/1355053868