確率的勾配降下法

確率的勾配降下法（Stochastic Gradient Descent，以下 SGD）は確率密度関数 $p(z)$ に対して目的関数が期待値で表された以下のような最適化問題に対して有効なアルゴリズムである．

$$ \min L(w) = \displaystyle\int{l(w,z)p(z)dz}. $$

上式における $l,w,z$ をそれぞれ損失関数，モデルパラメータ，データに対応する確率変数の実現値とすれば，上記問題は機械学習における期待損失（汎化誤差）の最小化問題に他ならない．そこで，関数 $L(w)$ は期待損失と呼ぶことにする．期待損失の値やその勾配 $\nabla L(w)$ はいくつかの理由により計算困難である場合が多い．例えば分布 $p(z)$ が未知，$p(z)$ が既知であっても期待値計算が困難，あるいは母集団が有限集合であっても濃度が大きく和演算が高コストといった場合である．そこで勾配 $\nabla L(w)$ の代わりに，その不偏推定量である確率的勾配(stochastic gradient) $\nabla l(w,z)$ を用いた勾配法

$$ w_{t+1}=w_t-\eta_t\nabla l(w,z_t) $$

が SGD である．ここで $z_t$ は $t$ 反復時点での $z$ の実現値である．$\eta_t$ はパラメータの更新幅を制御するハイパーパラメータであり，機械学習の分野においては学習率と呼ばれている．SGD の速度・安定性を向上させるためにパラメータの重み付き平均で予測をする Averaged SGD も提案されている．滑らかさ・凸性等の目的関数の性質及び，学習率・パラメータの平均の取り方等のアルゴリズムの性質に応じて，その収束性は様々である．これら手法の収束性について詳しくは [1-9] を参照されたい．

上述の通り SGD は期待損失の最小化を目的とするが，実際には期待損失では無く有限個の訓練データ $z_1,\ldots,z_n$ に対して定まる（正則化付き）経験損失の最小化問題を解く場合が多い．

$$ \min L_n(w)=\frac{1}{n}\sum_{i=1}^n{l(w,z_i)+\lambda h(w)}. $$

$h$ にはサンプルデータへの過剰適合 (Overfitting) を防ぐ役割があり，正則化項と呼ばれる．

$h$ は一般に滑らかとは限らず，経験損失最小化問題に SGD あるいは GD（確率的でない厳密な勾配を用いる勾配法，Gradient Descent）を適用する場合は，$h$ については劣勾配で近似する事になる．目的関数が滑らかでない場合，解の近傍においても劣勾配のノルムが大きくなる可能性に起因し，SGD/GD の収束速度の低下が起こる．しかし，$h$ が $L_1$正則化あるいは $L_2$正則化のような比較的単純な関数であれば，関数を（劣）勾配で近似すること無く反復を行う近接勾配法を適用することで，この様な収束速度の低下を抑制することが出来る[10]．以降は，損失関数と正則化項を区別せず $g_i(w)=l(w,z_i)+\lambda h(w)$ と置き，$g_i$ は $L$-smooth（微分可能かつ勾配がリプシッツ連続 i.e. $\|\nabla g_i(x) - \nabla g_i(y) \| \le L\|x-y\|$）とする．経験損失最小化問題は単に滑らかな関数の有限和に対する最小化問題となる．

$$ \min g(w)=\frac{1}{n}\sum_{i=1}^{n}{g_i(w)}. $$

この問題に SGD を適用する場合は，各反復においてランダムに一つの関数 $g_i$ を選択し，その関数の勾配を $g$ の確率的勾配として用いる．また，一つの関数でなく少数の関数（ミニバッチ）をランダムに抽出し，その平均を採用する場合もある．

アルゴリズムの収束は関数の滑らかさだけでなく，凸性にも影響を受ける．ここでは $g$ は $\mu$-strongly convex（$\mu$-強凸）とする．$L$ と$\mu$ の比 $\kappa$ は条件数 (condition number) と呼ばれる．関数が二階微分可能である場合は，そのヘッセ行列の最大固有値と最小固有値の比に相当し，この値が大きい程，勾配の変化の仕方が方向に依り大きく変わり得ることを意味している．そのため，条件数の大きさは GD/SGD のような一次の勾配を用いるアルゴリズムの収束に強く影響を及ぼす．経験損失最小化問題において SGD と GD は収束率（一度の反復で解へ接近する度合）と一反復あたりの計算量の観点でトレードオフの関係にある．GD は SGD に比べて優れた収束率，具体的には線形収束を達成するが，一度のパラメータの更新に $O(n)$ の計算量を要する．線形収束とは $\epsilon$ 精度の解を求めるのに必要な反復数が $O(\log(1/\epsilon))$ であるという事である．一方，SGD は $O(1/\epsilon)$ の反復を要する代わりに一反復あたりの計算量は $O(1)$ というようにデータサイズの影響を受けない．以上から，$\epsilon$ 精度の解を得るのに掛かる総計算量は GD の場合は $O(n\log(1/\epsilon))$，SGD の場合 $O(1/\epsilon)$ となる．データサイズが大きい程，SGD が有利な状況になり，機械学習で大規模データを扱うようになった近年において SGD が重宝される理由である．収束率は $\kappa,L,\mu$ にも依存しているが，データサイズおよび求解精度の関係に着目するため，ここでは省略したことを注意しておく．また，パラメータの次元についても，データのスパース性を無視すれば GD と SGD で同程度の依存度であるため省いている．本稿では焦点からは外しているニュートン法や準ニュートン法等のアルゴリズムと比較する場合はパラメータの次元も含めて比較すべきである．（準）ニュートン法の計算量はパラメータ次元に大きく依存する代わりに，各反復においてヘッセ行列が単位行列と見なせるような空間で更新を行うため条件数からの影響が弱く，線形収束より速い二次収束あるいは超一次収束を達成する．

ここまでで，大規模データを対象とした経験損失最小化問題における SGD の優位性を確認した．しかし，$\epsilon$ については依然 GD に分がある．SGD が線形収束しない原因は確率的勾配の分散の影響を軽減するために，学習率を $0$ に収束させる必要があることである．一方で，GD は学習率を定数に保つことが可能であり，これにより一度の反復で十分な目的関数の減少が得られる．そこで，SGD のように一反復毎の計算量を小さく保ちつつも確率的勾配の分散を小さくする方法が 2012年辺りから研究されだし，GD と同じく線形収束を達成するアルゴリズム Stochastic Average Gradient (SAG)[11], Stochastic Dual Coordinate Ascent (SDCA)[12], Stochastic Variance Reduction Gradient (SVRG)[13], SAGA[14] 等が提案された．SGD は本来，期待損失最小化問題を対象としているため，各反復で選択するデータは一時的なものとして扱われるが，経験損失最小化問題に適用する場合は，有限個の固定のデータを何周もすることになるので，データ毎に情報を保持することが出来る．この観点に着目し，データ毎に最後に更新した確率的勾配を保持する方法が SAG である．SDCA は正則化項付き経験損失最小化問題の Fenchel 双対問題に対して Coordinate Ascent を適用するアルゴリズムであり，データ毎に双対変数を保持する．SVRG は定期的に $O(n)$ のコストを消費し厳密な勾配を計算する方法で，$O(n)$ のメモリ領域を必要としない点に特徴がある．SAGA は SAG と SVRG の中間的なアルゴリズムで，SAG の更新ステップを勾配の不偏推定量に修正している（SAG は不偏推定量ではない）．これらはいずれも確率的勾配の分散の減少を実現している．SAG, SVRG, SAGA の反復では次で定義されるステップを勾配の推定量とする[14]．

SAG: (biased)

$$ \frac{1}{n} \left( \nabla g_{i_k}(x_k) - \nabla g_{i_k}(\phi_{i_k}^k) \right) + \frac{1}{n} \sum_{i=1}^n{\nabla g_i(\phi_i^k)}, $$

SAGA: (unbiased)

$$ \nabla g_{i_k}(x_k) - \nabla g_{i_k}(\phi_{i_k}^k) + \frac{1}{n}\sum_{i=1}^n{\nabla g_i(\phi_i^k)}, $$

SVRG: (unbiased)

$$ \nabla g_{i_k}(x_k) - \nabla g_{i_k}(\tilde{x}) + \frac{1}{n}\sum_{i=1}^n{\nabla g_i(\tilde{x})}. $$

ここで $i_k \in \{1,\ldots,n\}$ は $k$ 反復目にランダムに選択した関数に対応する添え字，$\phi_i^k$ は現在の反復までに最後に $i$ が選択された際の反復点，即ち $\phi_i^{k+1} = x_k \ (i=i_k)$，$\phi_i^k(i \ne i_k)$ であり，$\tilde{x}$ は SVRG で定期的に更新されるベースポイントである．これら 3 つのアルゴリズムはいずれも確率変数 $X \colon \Omega \to \mathbb{R}^d$ の平均 $\mathrm{E}X$ を推定する際に $X$ そのものでなく，別の確率変数 $Y \colon \Omega \to \mathbb{R}^d$ を用いて $\theta_{\alpha} = \alpha(X-Y) + \mathrm{E}Y$，$\alpha \in [0,1]$ で推定していると捉えられる[14]．この時，$\theta_{\alpha}$ の平均と分散は $\mathrm{E}\theta_{\alpha} = \alpha \mathrm{E}X + (1-\alpha) \mathrm{E}Y$，$\mathrm{Var}(\theta_{\alpha}) = \alpha^2 \left( \mathrm{Var}(X) + \mathrm{Var}(Y) - 2\mathrm{Cov}(X,Y) \right)$ となる．$\alpha=1$ の場合，$\theta_{\alpha}$ は $\mathrm{E}X$ の不偏推定量であるが，$\mathrm{E}X \ne \mathrm{E}Y$ で $\alpha < 1$ の時には，不偏推定量にはならない．一方で推定量の分散は $\alpha$ が $0$ に近い程，小さいというトレードオフがあり，SAG, SVRG, SAGA の関係を表している．いずれにせよ，$\mathrm{Cov}(X,Y)$ の寄与で確率的勾配の分散の軽減に成功している．SDCA についても，反復を主変数で記述すれば，このような分散の軽減をしていると [13] で言及している．これらのアルゴリズムは線形収束を実現し，$\epsilon$ 精度の解を得るための総計算量は $O \left( (n+\kappa)\log(1/\epsilon) \right)$ に抑えられている．GD の総計算量は $O \left( n\kappa\log(1/\epsilon) \right)$ であるので（前述の GD のオーダーでは条件数 $\kappa$ を省略していた事に注意されたい），SGD と違い GD の総計算量を真に改善していることが確認出来る．その他，関連するアルゴリズムとして [15-18] を参照されたい．GD の条件数 $\kappa$ への依存を軽減させることに成功した Nesterov の加速法[19] のアイディアを取り入れることで，SDCA 及び SVRG を加速させるアルゴリズムも提案されている[20,21]．

この様な研究が活発になった背景として，近年のコンピュータの計算力の向上に伴い，大規模データに対しての機械学習が可能になっただけでなく，データの傾向をより良く捉えるためのパワフルなモデルが使われるようになった事が考えられる．Deep Learning がその代表例である．Deep Learning で用いられるモデルは表現力が高い一方でパラメータ空間の次元が高く，その振る舞いも複雑である．例えば局所解や鞍点，関数表現の冗長性に依存したパラメータの変化に対してモデルの感度が低い領域の存在，等の問題がある．従って，大規模データに対応しつつも，関数の複雑さに影響されにくい高速なアルゴリズムの研究が必要である．一つの方向性として，ここで紹介した確率的な最適化方法に対して準ニュートン法，自然勾配法[22] で使われるような関数やパラメータ空間から定まる計量を効率良く導入する方法が研究[23-27] されていて，今後の更なる発展が期待される．

[参考]
[1] B. T. Polyak and A. B. Juditsky, Acceleration of Stochastic Approxximation by Averaging, SIAM Journal on Control and Optimization, 1992.
[2] L.Bottou, Online Algorithms and Stochastic Approximations, Online Learning and Neural Networks, Cambridge University Press, 1998,
[3] L.Bottou and Y.LeCun, Large Scale Online Learning, Advances in Neural Information Processing Systems 16, 2004,
[4] L.Bottou and O.Bousquet, The Tradeoffs of Large Scale Learning, Advances in Neural Information Processing Systems, 2008.
[5] F. Bach and E. Moulines, Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning, Advances in Neural Information Processing Systems, 2011.
[6] A. Rakhlin, O. Shamir, and K. Sridharan, Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization, Proceedings of the International Conference on Machine Learning, 2012.
[7] S. Lacoste-Julien, M. Schmidt, and F. Bach, A Simpler Approach to Obtain an $O(1/t)$ Convergence Rate for the Projected Stochastic Subgradient Method, arXiv, 2012
[8] F. Bach and E. Moulines, Non-Strongly-Convex Smooth Stochastic Approximation with Convergence Rate $O(1/n)$, Advances in Neural Information Processing Systems , 2013.
[9] O. Shamir and T. Zhang, Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes, Proceedings of the International Conference on Machine Learning, 2013.
[10] N. Parikh and S. Boyd, Proximal Algorithms, Foundations and Trends in Optimization, 2013.
[11] N. Le Roux, M. Schmidt, and F. Bach, A Stochastic Gradient Method with an Exponential Convergence Rate for Strongly-Convex Optimization with Finite Training Sets, Advances in Neural Information Processing Systems, 2012.
[12] S. Shalev-Shwartz and T. Zhang, Proximal Stochastic Dual Coordinate Ascent, arXiv, 2012.
[13] R. Johnson and T. Zhang, Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Advances in Neural Information Processing Systems, 2013.
[14] A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: A Fast Incremental Gradient Method with Support for Non-Strongly Convex Composite Objectives, Advances in Neural Information Processing Systems, 2014.
[15] L. Xiao and T. Zhang, A Proximal Stochastic Gradient Method with Progressive Variance Reduction, arXiv, 2014.
[16] S. Shalev-Shwartz and T. Zhang, Accelerated Mini-Batch Stochastic Dual Coordinate Ascent, Advances in Neural Information Processing Systems, 2013.
[17] J. Konecny and P. Richtarik, S2GD: Semi-Stochastic Gradient Descent Methods, arXiv, 2013.
[18] T. Suzuki, Stochastic Dual Coordinate Ascent with Alternating Direction Method of Multipliers, Proceedings of the International Conference on Machine Learning, 2014.
[19] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, Boston, 2004.
[20] S. Shalev-Shwartz and T. Zhang, Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization, Proceedings of the International Conference on Machine Learning, 2014.
[21] A. Nitanda, Stochastic Proximal Gradient Descent with Acceleration Techniques, Advances in Neural Information Processing Systems, 2014.
[22] S. Amari, Natural Gradient works Efficiently in Learning, Neural Computation, 1998.
[23] J. Martens, Deep Learning via Hessian-free Optimization, Proceedings of the International Conference on Machine Learning, 2010.
[24] R.H. Byrd, G.M. Chin, J. Nocedal, and Y.Wu, Sample size selection in optimization methods for machine learning, Mathematical Programming, 2012.
[25] R.H. Byrd, G.M. Chin, W. Neveitt, and J. Nocedal, On the use of stochastic Hessian information in unconstrained optimization, Mathematical Programming, 2013.
[26] Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio, Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, arXiv, 2014.
[27] R. Pascanu, Y. Dauphin, S. Ganguli, and Y. Bengio, On the saddle point problem for non-convex optimization, arXiv, 2014.