Accelerated Gradient Methods for Stochastic Optimization and Online Learning (Hu, Kwok and Pan, NIPS2009) 二宮 崇 機械学習勉強会 2010 年 6 月 17 日 1
論文 Chonghai Hu, James T. Kwok and Weike Pan (2009) Accelerated Gradient Methods for Stochastic Optimization and Online Learning, In Proc. of NIPS
はじめに Stochastic Gradient Descent (SGD) 大量のデータから学習可 収束が遅い Acceleration (Nesterov, 1983) Smooth component & non-smooth component に対 する Acceleration (Nesterov, 2007)(Beck&Teboulle, 2009) ヒンジロスや L1 正則化項 Convergence rate (N…iteration の回数 ) (Lan, 2009) 3 smooth componentnon-smooth component
この論文の contribution Strong Convexity に対する SGD と Acceleration Strong convexity の例 : Log loss, square loss, L2 正則化項など Convergence rate オンライン化 リグレット 4
問題 一般の問題 Stochastic optimization Problem ここでは次のように定式化しておく 5 ξ is a random vector f (x)≡ E [F(x, ξ)] is convex and differentiable (and L-Lipschitz) is convex but non-smooth is μ-strongly convex
Lipschitz Continuity と Strong Convexity Lipschitz Continuity Strong Convexity 6
Algorithm Generalized gradient update (Nesterov, 2007) 提案アルゴリズム SAGE 7
Convergence Analysis 8 良い L t と α t を選択することによって、期待値は正解に急速に収束する。 ここでは は convex とする。
Convergence Analysis 9 ここでは は μ-strongly convex とする。
Online Algorithm SAGE-based Online Algorithm 10
Regret 11
Experiments Data Sets pcmac (subset of 20 newsgroup) PCV1 (a filtered collection of the Reuters) Loss function: square loss Regularizer: L1 regularizer 12
Experiments 13
Experiments 14
Experiments 15
Experiments 16