Accelerated Gradient Methods for Stochastic Optimization and Online Learning (Hu, Kwok and Pan, NIPS2009) 二宮 崇 機械学習勉強会 2010 年 6 月 17 日 1.

Presentation on theme: "Accelerated Gradient Methods for Stochastic Optimization and Online Learning (Hu, Kwok and Pan, NIPS2009) 二宮 崇 機械学習勉強会 2010 年 6 月 17 日 1."— Presentation transcript:

1 Accelerated Gradient Methods for Stochastic Optimization and Online Learning (Hu, Kwok and Pan, NIPS2009) 二宮 崇 機械学習勉強会 2010 年 6 月 17 日 1

2 論文 Chonghai Hu, James T. Kwok and Weike Pan (2009) Accelerated Gradient Methods for Stochastic Optimization and Online Learning, In Proc. of NIPS2009. 2

3 はじめに 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

4 この論文の contribution Strong Convexity に対する SGD と Acceleration Strong convexity の例 : Log loss, square loss, L2 正則化項など Convergence rate オンライン化 リグレット 4

5 問題 一般の問題 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

6 Lipschitz Continuity と Strong Convexity Lipschitz Continuity Strong Convexity 6

7 Algorithm Generalized gradient update (Nesterov, 2007) 提案アルゴリズム SAGE 7

8 Convergence Analysis 8 良い L t と α t を選択することによって、期待値は正解に急速に収束する。 ここでは は convex とする。

9 Convergence Analysis 9 ここでは は μ-strongly convex とする。

10 Online Algorithm SAGE-based Online Algorithm 10

11 Regret 11

12 Experiments Data Sets pcmac (subset of 20 newsgroup) PCV1 (a filtered collection of the Reuters) Loss function: square loss Regularizer: L1 regularizer 12

13 Experiments 13

14 Experiments 14

15 Experiments 15

16 Experiments 16