技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

まとめ

確率的最適化は機械学習の重要なコンポーネントであり、その中核となるのは確率的勾配降下アルゴリズム (SGD) です。この手法は、60 年以上前に初めて提案されて以来、広く使用されてきました。過去 8 年間にわたり、私たちは確率的最適化手法の分散削減技術という刺激的な新しい発展を目の当たりにしてきました。これらの分散削減手法 (VR 手法) は、トレーニング データの複数回の反復が可能なシナリオで良好に機能し、理論上も実際上も SGD よりも速い収束を示します。この速度の向上は、VR 手法への関心の高まりと、この分野での研究成果の急速な蓄積を浮き彫りにしています。この記事では、専門家以外の読者に情報を提供することを目的として、限られたデータセットの最適化のための VR 手法における重要な原則と大きな進歩について概説します。私たちは主に凸最適化環境に焦点を当てており、非凸関数の最小化の拡張に興味のある読者にリファレンスを提供します。

キーワード | 機械学習の最適化;

1 はじめに

機械学習研究の分野では、モデルを巨大なデータセットにどのように適応させるかが基本的かつ重要な問題となります。たとえば、線形最小二乗モデルの典型的なケースを考えることができます。

$${バツ}^{\ast }\in \mathrm{arグ}\underset{バツ\in {\mathbb{R}}^d}{分}\frac{1}{ん}\sum _{私=1}^{ん}({1つの}_{私}^Tバツ-b_{私}{)}^2$$

このモデルでは、 $d$ ベクトルで表されるパラメータ$バツ\in {\mathbb{R}}^d$ 与えられた。その間、私たちは手元に$ん$ データポイント（特徴ベクトルを含む）${1つの}_{私}\in {\mathbb{R}}^d$ と目標値$b_{私}\in \mathbb{R}$ 。モデルの適応プロセスでは、モデルの予測出力が適切になるようにこれらのパラメーターを調整します。${1つの}_{私}^Tバツ$ 平均して目標値にできるだけ近づける$b_{私}$。

より広く言えば、損失関数を使用することもできます。 ${ふ}_{私}(バツ)$ モデルの予測と$私$ データ ポイントがどの程度近いか:

$${バツ}^{\ast }\in \mathrm{arグ}\underset{バツ\in {\mathbb{R}}^d}{分}ふ(バツ):=\frac{1}{ん}\sum _{私=1}^{ん}{ふ}_{私}(バツ)$$

損失関数 ${ふ}_{私}(バツ)$ これが大きい場合は、モデルの予測がデータから大きく外れていることを示します。${ふ}_{私}(バツ)$ ゼロに等しい場合、モデルはデータ ポイントに完全に適合します。関数$ふ(バツ)$ データセット全体にわたるモデルの平均損失を反映します。

上記の形式 (2) のような問題は、線形最小二乗問題だけでなく、機械学習で研究される他の多くのモデルにも当てはまります。たとえば、ロジスティック回帰モデルでは次のことを解決します。

$${バツ}^{\ast }\in \mathrm{arグ}\underset{バツ\in {\mathbb{R}}^d}{分}\frac{1}{ん}\sum _{私=1}^{ん}\mathrm{見よグ}(1+e^{-b_{私}{1つの}_{私}^Tバツ})+\frac{\lambda }{2}\Vert バツ{\Vert }_2^2$$

ここで扱っているのは、 bi ∈ { − 1 , + 1 } b_i は {-1, +1} の範囲内にあるb私​∈{−1,+1} バイナリ分類問題の場合、予測は以下に基づいて行われます。${1つの}_{私}^Tバツ$ シンボル。正規化項も式に導入されています$\frac{\lambda }{2}\Vert バツ{\Vert }_2^2$ データの過剰適合を避けるため、$\Vert バツ{\Vert }_2^2$ 急行$バツ$ のユークリッドノルムの二乗。

ほとんどの教師あり学習モデルでは、トレーニング プロセスは、L1 正則化最小二乗法、サポート ベクター マシン (SVM)、主成分分析、条件付きランダム フィールド、ディープ ニューラル ネットワークなどを含む形式 (2) で表現できます。

現代の問題における主な課題は、データ ポイントの数です。 $ん$ おそらく非常に大きいでしょう。私たちはテラバイトの範囲をはるかに超えたデータセットを扱うことが多く、そのソースはインターネット、衛星、リモートセンサー、金融市場、科学実験など多岐にわたります。このような大規模なデータ セットを処理するための一般的なアプローチは、各反復でランダムに選択された少数のデータ ポイントのみを使用する確率的勾配降下法 (SGD) アルゴリズムを使用することです。さらに、最近では、従来の確率勾配法よりも収束速度が速い分散低減 (VR) 確率勾配法への関心が急激に高まっています。

図 1. マッシュルーム データセット [7]、勾配降下法 (GD)、加速勾配降下法 (AGD、[50] の加速 GD)、確率的勾配降下法 (SGD) および ADAM [30] 法に基づくロジスティック回帰問題について分散削減 (VR) 手法である SAG および SVRG との比較 (n = 8124、d = 112)。

1.1. 勾配および確率的勾配降下法

勾配降下法 (GD) は、上記の問題 (2) を解決するために使用される古典的なアルゴリズムであり、その反復更新式は次のとおりです。
$${バツ}_{け+1}={バツ}_{け}-\gamma \frac{1}{ん}\sum _{私=1}^{ん}\nabla {ふ}_{私}({バツ}_{け})$$

ここ、$\gamma$ ゼロより大きい固定ステップ値です。GD アルゴリズムの各反復中に、各データ ポイントは次のようにする必要があります。$私$ 勾配を計算する$\nabla {ふ}_{私}({バツ}_{け})$、つまり、GD にはすべてが必要です。 $ん$ データポイントの完全な走査を実行します。データセットのサイズが$ん$ 非常に大きくなると、GD アルゴリズムの各反復のコストが非常に高くなり、その適用が制限されます。

代わりに、Robbins と Monro によって最初に提案された確率的勾配降下法 (SGD) 法を考慮することができます。その反復更新式は次のとおりです。
$${バツ}_{け+1}={バツ}_{け}-\gamma \nabla {ふ}_{{私}_{け}}({バツ}_{け})$$

SGD アルゴリズムは、各反復でランダムに選択された 1 つのデータ ポイントの勾配のみを使用して機能します。 $\nabla {ふ}_{{私}_{け}}({バツ}_{け})$ 各反復のコストを削減します。図 1 では、最適化プロセスの初期段階で、SGD が GD (加速された GD メソッドを含む) よりも大幅な進歩を遂げていることがわかります。グラフは、最適化の進行状況をエポック単位で示します。エポックは、すべての要素の計算として定義されます。$ん$ トレーニング サンプルの勾配の数。 GD アルゴリズムは各ラウンドで 1 回の反復を実行しますが、SGD アルゴリズムは各ラウンドで 1 回の反復を実行します。$ん$ 繰り返し。SGD と GD を比較するための基礎としてラウンドを使用します。$ん$ 非常に大きなケースでは、両方の方法の主なコストは勾配に集中します。$\nabla {ふ}_{私}({バツ}_{け})$ 計算。

1.2. 分散の問題

ランダムなインデックス付けを考えてみましょう ${私}_{け}$ コレクションから { 1 , … , n } {1, ldots, n}{1,…,ん} 一様ランダム選択の場合、これは、すべての$私$、選ぶ ${私}_{け}=私$ 確率$ポ[{私}_{け}=私]$ 等しい$\frac{1}{ん}$ 。この場合、$\nabla {ふ}_{{私}_{け}}({バツ}_{け})$ として$\nabla ふ({バツ}_{け})$ 期待値の定義により、次のとおりであるため、 の推定量は不偏です。
$$え[\nabla {ふ}_{{私}_{け}}({バツ}_{け})|{バツ}_{け}]=\frac{1}{ん}\sum _{私=1}^{ん}\nabla {ふ}_{私}({バツ}_{け})=\nabla ふ({バツ}_{け})(6)$$

SGD (確率的勾配降下法) 法は各反復での機能を保証するものではありませんが、 $ふ$ の値は減少しますが、平均して、下方向を表す負の完全な勾配に向かって移動します。

ただし、不偏勾配推定器があるだけでは、SGD 反復の収束を保証するには十分ではありません。この点を説明するために、図 2 (左) は、LIBSVM [7] によって提供される 4 つのカテゴリのデータセットに一定のステップ サイズを使用してロジスティック回帰関数を適用したときの SGD の反復軌跡を示しています。図中の同心円状の楕円は関数の輪郭、つまり関数値を表しています。 $ふ(バツ)=c$ 対応点$バツ$ 集める、$c$ は実数のセット内の特定の定数です。異なる定数値$c$ さまざまな楕円に対応します。

SGD の反復軌跡は最適解 (図の緑色のアスタリスクで示されている) には収束せず、最適解の周囲に点群を形成します。対照的に、図 2 に、後で紹介する同じ一定のステップ サイズを使用した、分散低減 (VR) 手法である確率的平均勾配 (SAG) の反復軌跡を示します。 この例で SGD が収束しない理由は、確率的勾配自体が 0 に収束しないためであり、したがって、一定ステップ SGD 法 (5) が停止することはありません。これは、自然に停止する勾配降下法 (GD) 法とは大きく対照的です。${バツ}_{け}$ アプローチ${バツ}^{\ast }$、勾配 $\nabla ふ({バツ}_{け})$ ゼロになる傾向があります。

図 2. 固定ステップ SGD (左) および SAG (右) 反復法を使用した 2 次元ロジスティック回帰のレベル セット プロット。緑色のアスタリスクは x を示しますほどく。

1.3. 古典的な分散削減法

による処理 $\nabla {ふ}_{私}({バツ}_{け})$ 値の分散によって引き起こされる非収束問題に対する古典的な手法がいくつかあります。たとえば、Robbins と Monro [64] は一連の減少ステップを使用します。${\gamma }_{け}$ 分散問題を解決し、製品が${\gamma }_{け}\nabla {ふ}_{{私}_{け}}({バツ}_{け})$ ゼロに収束する可能性があります。ただし、アルゴリズムの停止が早すぎたり遅すぎたりしないように、この一連の減少ステップを調整するのは難しい問題です。

分散を減らすためのもう 1 つの古典的な手法は、複数の変数を使用することです。 $\nabla {ふ}_{私}({バツ}_{け})$ 平均して完全な勾配を取得する$\nabla ふ(バツ)$ より正確な見積もり。このアプローチはミニバッチと呼ばれ、複数の勾配を並行して評価できる場合に特に便利です。これにより、次の形式の反復が行われます。
$${バツ}_{け+1}={バツ}_{け}-\gamma \frac{1}{|B_{け}|}\sum _{私\in B_{け}}\nabla {ふ}_{私}({バツ}_{け})(7)$$
で$B_{け}$ はランダムなインデックスセットであり、$|B_{け}|$ 急行$B_{け}$ サイズ。もし$B_{け}$ 置換を伴う均一なサンプリングの場合、この勾配推定値の分散は「バッチ サイズ」に関連します。$|B_{け}|$ は反比例するため、バッチサイズを増やすことで分散を小さくできます。

ただし、このような反復のコストはバッチ サイズに比例するため、この形式の分散削減には計算コストの増加が伴います。

分散を削減し、SGD の経験的パフォーマンスを向上させるためのもう 1 つの一般的な戦略は、過去のステップで使用された方向に基づく追加の用語である「モメンタム」を追加することです。特に勢いのあるSGDの形は以下の通りです。
$${バツ}_{け+1}={バツ}_{け}-\gamma {メートル}_{け}(9)$$
ここで、運動量パラメータは$\beta$ (0, 1) の範囲内にあります。最初の勢いなら${メートル}_0=0$、(8) で展開します。 ${メートル}_{け}$ 更新情報については、${メートル}_{け}$ は前の勾配の加重平均です。
$${メートル}_{け}=\sum _{t=0}^{け}{\beta }^{け-t}\nabla {ふ}_{{私}_t}({バツ}_t)(10)$$
したがって、${メートル}_{け}$ 確率的勾配の加重和です。なぜなら${\sum }_{t=0}^{け}{\beta }^{け-t}=\frac{1-{\beta }^{け+1}}{1-\beta }$、変換できます $\frac{1-\beta }{1-{\beta }^{け}}{メートル}_{け}$ 確率的勾配の加重平均として考慮されます。これを完全な勾配の式と比較すると、$\nabla ふ({バツ}_{け})=\frac{1}{ん}{\sum }_{私=1}^{ん}\nabla {ふ}_{私}({バツ}_{け})$ 比較するには、$\frac{1-\beta }{1-{\beta }^{け}}{メートル}_{け}$（同様に ${メートル}_{け}$ ) は完全な勾配の推定値として解釈されます。この加重合計により分散は減少しますが、重要な問題も生じます。加重合計 (10) は最近サンプリングされた勾配により多くの重みを与えるため、完全な勾配には収束しません。$\nabla ふ({バツ}_{け})$ 、後者は単純な平均です。セクション II-A で説明する最初の分散削減方法は、加重平均の代わりに単純な平均を使用することでこの問題を解決します。

1.4. 最新の分散削減方法

古典的な方法とは異なり、1 つまたは複数の方法を直接使用します。 $\nabla {ふ}_{私}({バツ}_{け})$ として$\nabla ふ({バツ}_{け})$ 近似として、最新の分散削減 (VR) 手法では異なる戦略が採用されています。これらのメソッドでは、$\nabla {ふ}_{私}({バツ}_{け})$ 勾配推定値を更新するには${グ}_{け}$を作るのが目標です。 ${グ}_{け}$ アプローチ$\nabla ふ({バツ}_{け})$ 。具体的には、${グ}_{け}$ 満足できる${グ}_{け}\approx \nabla ふ({バツ}_{け})$ 。このような勾配推定に基づいて、次の形式の近似勾配ステップを実行します。
$${バツ}_{け+1}={バツ}_{け}-\gamma {グ}_{け}(11)$$
ここ$\gamma >0$ はステップ サイズ パラメータです。

一定のステップ サイズが使用されるようにするには $\gamma$ 反復 (11) が収束できる場合、勾配推定値が次の値であることを確認する必要があります。${グ}_{け}$ 分散はゼロになる傾向があります。数学的には、これは次のように表現できます。
$$え\left[\Vert {グ}_{け}-\nabla ふ({バツ}_{け}){\Vert }^2\right]\to 0\text{として}け\to \infty (12)$$
ここでの期待$え$ までのアルゴリズムに基づいています。$け$ すべての確率変数は反復計算されます。特性 (12) により、最適解に到達したときに VR メソッドを停止できることが保証されます。私たちはこのプロパティを VR アプローチの特徴的な機能とみなしているため、これを VR プロパティと呼びます。実際には分散はゼロになる傾向があるため、分散が「減少した」という表現は誤解を招く可能性があることに注意してください。特性 (12) は、理論 (適切な仮定の下) および実際 (図 1 に示すように) において VR 手法がより高速な収束を達成できるようにする重要な要素です。

1.5. 分散削減法の最初の例: SGD²

簡単な改善方法では、ステップ サイズを減らすことなく SGD 再帰式 (5) を収束させることができます。具体的な方法は、減算です。 $\nabla {ふ}_{私}({バツ}^{\ast })$、このメソッドは次のように定義されます。
$${バツ}_{け+1}={バツ}_{け}-\gamma (\nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({バツ}^{\ast }))(13)$$
この方法は SGD² と呼ばれます [22]。通常、すべてを確実に知ることはできませんが、$\nabla {ふ}_{私}({バツ}^{\ast })$ , しかし、例として SGD² は、分散削減法の基本的な特性をよく示しています。さらに、多くの分散削減手法は SGD² 手法の近似形式とみなすことができます。これらの手法は既知の手法に依存しません。$\nabla {ふ}_{私}({バツ}^{\ast })$ですが、代わりに近似できる方法を使用します。 $\nabla {ふ}_{私}({バツ}^{\ast })$ 推定値。

SGD² は完全な勾配の不偏推定値を使用することに注意してください。なぜなら$\nabla ふ({バツ}^{\ast })=0$、F:
$$え[\nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({バツ}^{\ast })]=\nabla ふ({バツ}_{け})-\nabla ふ({バツ}^{\ast })=\nabla ふ({バツ}_{け})$$
さらに、SGD² が最適解に達すると、自然に停止します。$私$、持っている：
$$(\nabla {ふ}_{私}(バツ)-\nabla {ふ}_{私}({バツ}^{\ast })){|}_{バツ={バツ}^{\ast }}=0$$

さらに観察すると、 ${バツ}_{け}$ 近く${バツ}^{\ast }$(連続の場合 $\nabla {ふ}_{私}$)、SGD² は次の理由により分散削減特性 (12) を満たします。
$$\begin{gathered} え\left[\Vert {グ}_{け}-\nabla ふ({バツ}_{け}){\Vert }^2\right]= \\ え\left[\Vert \nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({バツ}^{\ast })-\nabla ふ({バツ}_{け}){\Vert }^2\right]\le え\left[\Vert \nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({バツ}^{\ast }){\Vert }^2\right] \end{gathered}$$
ここで補題 2 を使用します。$バツ=\nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({バツ}^{\ast })$を利用し、 $え[\nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({バツ}^{\ast })]=\nabla ふ({バツ}_{け})$ 自然。このプロパティは、SGD² が従来の SGD 手法よりも収束速度が速いことを示しています。これについては付録 B で説明します。

1.6. 分散の高速収束法

このセクションでは、分散削減 (VR) 法の分析に使用される 2 つの標準的な仮定を紹介し、これらの仮定の下で達成できる加速効果について、従来の SGD 法と比較して説明します。まず、勾配にはリプシッツ連続性があると仮定します。これは、勾配の変化率が有限であることを意味します。

仮定 1 (リプシッツ連続性)

関数は次のように仮定します。 $ふ$微分可能であり、 $ら$- スムーズに、すべての人に $バツ$ そして$ええ$ そして誰か$0<ら<\infty$,以下の条件があります。
$$\Vert \nabla ふ(バツ)-\nabla ふ(ええ)\Vert \le ら\Vert バツ-ええ\Vert (14)$$
これは、すべての$ふ私:{\mathbb{R}}^d\to \mathbb{R}$ 微分可能です、${ら}_{私}$- スムーズ、私たちは定義します ${ら}_{\text{最大}}$ のために 最大⁡ {L 1 、 . 。 。 , L n } max{L_1, . 。 。 、L_n}最大{ら1​,...,らん​}。

これは一般に弱い仮定であると考えられていますが、後続の章では、滑らかでない問題に適した VR 手法について説明します。 2 回微分可能な一変量関数の場合、$ら$-滑らかさは次のように直感的に理解できます: 二次導関数が次のように仮定されることと等価です。 $ら$ 上限、つまり$|{ふ}^{\prime \prime }(バツ)|\le ら$ すべてのために$バツ\in {\mathbb{R}}^d$ 。複数の変数の 2 回微分可能な関数の場合、ヘッセ行列を仮定するのと同じです。${\nabla }^2ふ(バツ)$ の特異値$ら$ 上限。

仮定２（凸性が強い）

私たちが考える 2 番目の仮説は、関数 (f) は次のとおりであるということです。 $\mu$- 凸が強い、つまり特定の場合に $\mu >0$、関数 $バツ\mapsto ふ(バツ)-\frac{\mu }{2}\Vert バツ{\Vert }^2$ 凸ですよ。さらに、それぞれについて、$私=1,...,ん$，$ふ私:{\mathbb{R}}^d\to \mathbb{R}$ 凸ですよ。

これは強い仮定です。最小二乗問題では、各 (fi$ は凸ですが、全体の関数 (f) は計画行列内にのみ存在します) $あ:=[{1つの}_1,...,{1つの}_{ん}]$ 列ランクが完璧な場合のみ強凸です。 L2 正則化ロジスティック回帰問題は、正則化項の存在によりこの仮定を満たします。$\mu \ge \lambda$。

これらの前提を満たす重要な問題のクラスは、次の形式の最適化問題です。
$${バツ}^{\ast }\in \mathrm{arグ}\underset{バツ\in {\mathbb{R}}^d}{分}ふ(バツ)=\frac{1}{ん}\sum _{私=1}^{ん}{\ell }_{私}({1つの}_{私}^Tバツ)+\frac{\lambda }{2}\Vert バツ{\Vert }^2(15)$$
それぞれの「損失」が関数になるところ${\ell }_{私}:\mathbb{R}\to \mathbb{R}$ は 2 回微分可能であり、その 2 階導関数は${\ell }_{私}^{\prime \prime }$ 0 と何らかの上限に制限されます$ま$ 間。これには、最小二乗法、ロジスティック回帰、プロビット回帰、フーバーロバスト回帰など、機械学習における L2 正則化を使用したさまざまな損失関数が含まれます。この場合、全員にとって、$私$、我々は持っています ${ら}_{私}\le ま\Vert {1つの}_{私}{\Vert }^2+\lambda$ そして$\mu \ge \lambda$。

これらの仮定の下で、勾配降下法 (GD) 法の収束率は条件数によって決まります。 $\kappa :=ら/\mu$ 決める。条件番号は常に 1 以上であり、条件番号が 1 より大幅に大きい場合、関数の輪郭が非常に楕円になり、GD メソッドの反復が振動する原因になります。逆に、こんなときは$\kappa$ 1 に近い場合、GD 法の収束が速くなります。

仮定 1 および 2 の下では、VR 法は線形速度で収束します。ランダムメソッド ({f(x_k)}) の関数値は次のように与えられると言います。 $0<\rho \le 1$ 定数が存在する場合の線形収束率 (予想内)$Ｃ>0$ 作るもの:
$$え[ふ({バツ}_{け})]-ふ({バツ}^{\ast })\le (1-\rho {)}^{け}Ｃ=お(\mathrm{経験}(-け\rho ))\forall け(16)$$
これは、各反復での勾配の不偏推定値のみに依存する古典的な SGD 手法とは対照的であり、次の仮定の下で準線形レートのみを取得します。
$$え[ふ({バツ}_{け})]-ふ({バツ}^{\ast })\le お(1/け)$$
この不等式を満たす最小値$け$ これは、アルゴリズムの反復複雑度と呼ばれます。以下は、GD、SGD、および VR メソッドの基本的なバリアントの反復の複雑さと 1 回の反復のコストです。

アルゴリズムの合計実行時間は、反復の複雑さと反復の実行時間の積によって決まります。ここで使われている ${\kappa }_{\text{最大}}:={\mathrm{最大}}_{私}{ら}_{私}/\mu$ 。知らせ${\kappa }_{\text{最大}}\ge \kappa$; したがって、GD の反復の複雑さは VR 法の反復の複雑さよりも小さくなります。

ただし、GD の反復あたりのコストは VR 法のコストであるため、 $ん$ 合計実行時間の点では VR 方式の方が優れています。

古典的な SGD 手法の利点は、実行時間と収束率が依存しないことです。 $ん$、しかし許容範囲はあります $ϵ$ の依存性はさらに悪化しており、これが許容値が小さい場合の SGD のパフォーマンスの低下を説明しています。

付録 B では、SGD² メソッドの反復複雑さが VR メソッドと同じであることを示す簡単な証明を提供します。

2. 基本的な分散削減方法

分散低減 (VR) 手法の開発はいくつかの段階を経て、最初のバッチの手法では収束率が大幅に向上しました。この一連の手法の始まりは SAG アルゴリズムです。その後、確率的双対座標上昇 (SDCA) アルゴリズム、MISO アルゴリズム、確率的分散減少勾配 (SVRG/S2GD) アルゴリズム、SAGA (「改良された」SAG の意味) アルゴリズムが次々と登場しました。

この章では、これらの先駆的な VR 手法について詳しく説明します。第 4 章では、特定のアプリケーション シナリオでこれらの基本的な方法と比較して優れた特性を示すいくつかの新しい方法を検討します。

2.1. 確率的平均勾配法 (SAG)

最初の分散低減 (VR) 法の探索は、完全な勾配構造の模倣から始まります。完全な勾配なので $\nabla ふ(バツ)$ すべてであります$\nabla {ふ}_{私}(バツ)$ 勾配の単純な平均、その後の完全な勾配の推定値${グ}_{け}$ これは、これらの勾配推定値の平均でもあります。このアイデアから、最初の VR 手法である確率的平均勾配 (SAG) 手法が生まれました。

SAG 法 [37]、[65] は、初期増分集約勾配 (IAG) 法 [4] のランダム化バージョンです。 SAG の中心的な考え方は、各データ ポイントに対して$私$ 見積もりを維持する${ヴ}_{いいね}\approx \nabla {ふ}_{私}({バツ}_{け})$ 。次に、これらを使用します${ヴ}_{いいね}$ 値の平均は、完全な勾配の推定値として使用されます。つまり、次のようになります。
$${\overline{グ}}_{け}=\frac{1}{ん}\sum _{じゅう=1}^{ん}{ヴ}_{冗談}\approx \frac{1}{ん}\sum _{じゅう=1}^{ん}\nabla {ふ}_{じゅう}({バツ}_{け})=\nabla ふ({バツ}_{け})(18)$$

SAG の各反復で、セットから { 1 , … , n } {1, ldots, n}{1,…,ん} からインデックスを抽出します${私}_{け}$、次のルールに従って更新されます ${ヴ}_{冗談}$：
$${ヴ}_{冗談}^{け+1}=\{\begin{array}{ll}\nabla {ふ}_{{私}_{け}}({バツ}_{け}),& \text{もし}じゅう={私}_{け}\\ {ヴ}_{冗談}^{け},& \text{もし}じゅう\ne {私}_{け}\end{array}(19)$$
その中でもそれぞれ、${ヴ}_{0私}$ ゼロまたは$\nabla {ふ}_{私}({バツ}_0)$ おおよその値。解決策を使って${バツ}^{\ast }$ それぞれの近似値${ヴ}_{いいね}$ 徐々に～に収束していきます$\nabla {ふ}_{私}({バツ}^{\ast })$、それによりＶＲ特性（１２）を満たす。

SAG を効率的に実装するには、計算に注意を払う必要があります。 ${\overline{グ}}_{け}$ 毎回合計を最初から始めるのを避けるため$ん$ ベクトル、これは$ん$ 大きいと値段も高くなります。幸いなことに、各反復には 1 つしかないため、${ヴ}_{いいね}$ 条件は変更されるため、毎回合計額を再計算する必要はありません。具体的には、反復中に次のように仮定します。$け$ から抽出されたインデックス${私}_{け}$、すると次のようになります。
$${\overline{グ}}_{け}=\frac{1}{ん}\sum _{\begin{array}{c}じゅう=1\\ じゅう\ne {私}_{け}\end{array}}^{ん}{ヴ}_{冗談}+\frac{1}{ん}{ヴ}_{{私}_{け}}^{け}={\overline{グ}}_{け-1}-\frac{1}{ん}{ヴ}_{{私}_{け}}^{け-1}+\frac{1}{ん}{ヴ}_{{私}_{け}}^{け}(20)$$

それに加えて ${ヴ}_{{私}_{け}}$ 以外のすべて${ヴ}_{冗談}$ 値はすべて同じままで、それぞれを保存するだけです$じゅう$ に対応するベクトル${ヴ}_{じゅう}$ 。アルゴリズム 1 は、SAG メソッドの具体的な実装を示しています。

SAG は線形収束を達成する最初の確率的手法であり、その反復複雑さは次のとおりです。 $お(({\kappa }_{\text{最大}}+ん)\mathrm{見よグ}(1/ϵ))$、ステップ サイズを使用して $\gamma =お(1/{ら}_{\text{最大}})$ 。この線形収束は図 1 で観察できます。注目に値するのは、${ら}_{\text{最大}}$-あらゆる用途に対応したスムーズな機能 ${ら}^{\prime }\ge {ら}_{\text{最大}}$ あまりにも${ら}^{\prime }$- スムーズな SAG メソッドは、実際には調整が難しい一連のステップ サイズの減少でのみ線形未満の収束速度を達成する古典的な SGD メソッドとは対照的に、十分に小さいステップ サイズで線形収束速度を達成します。

当時、SAG の線形収束は、各反復で確率的勾配を 1 つだけ計算する (単一のデータ ポイントを処理する) だけであったため、大きな進歩でした。ただし、Schmidt et al. [65] によって提供された収束証明は非常に複雑で、コンピューターで検証された手順に依存しています。 SAG の分析が難しい主な理由は次のとおりです。 ${グ}_{け}$ は勾配の偏った推定値です。

次に、共変量の概念を利用して、同様のパフォーマンスを持ちながら分析が容易な SAG 法の偏りのないバリアントを作成する SAG のバリアントである SAGA メソッドを紹介します。

---

アルゴリズム 1: SAG 法

1. パラメータ: ステップサイズ $\gamma >0$
2. 初期化:${バツ}_0$，${ヴ}_{私}=0\in {\mathbb{R}}^d$ のために$私=1,\dots ,ん$
3. 右 $け=1,\dots ,T-1$ 埋め込む：
   a. ランダムな選択 ik ∈ { 1 , … , n } i_k は {1, ldots, n} に含まれる私け​∈{1,…,ん}
   b. 計算する${\overline{グ}}_{け}={\overline{グ}}_{け-1}-\frac{1}{ん}{ヴ}_{{私}_{け}}^{け-1}$
   c. アップデート${ヴ}_{{私}_{け}}^{け}=\nabla {ふ}_{{私}_{け}}({バツ}_{け})$
   d. 勾配推定値を更新する${\overline{グ}}_{け}={\overline{グ}}_{け}+\frac{1}{ん}{ヴ}_{{私}_{け}}^{け}$
   e. アップデート${バツ}_{け+1}={バツ}_{け}-\gamma {\overline{グ}}_{け}$
4. 出力：${バツ}_T$

2.2.SAGA法

減少した基本的な不偏勾配推定値 $\nabla {ふ}_{{私}_{け}}({バツ}_{け})$ 分散アプローチは、いわゆる共変量、または制御変数を使用します。のために$私=1,\dots ,ん$、設定 ${ヴ}_{私}\in {\mathbb{R}}^d$ ベクトルです。これらのベクトルを使用して、完全な勾配を変換できます。$\nabla ふ(バツ)$ 次のように書き換えられます。
$$\nabla ふ(バツ)=\frac{1}{ん}\sum _{私=1}^{ん}(\nabla {ふ}_{私}(バツ)-{ヴ}_{私}+{ヴ}_{私})=\frac{1}{ん}\sum _{私=1}^{ん}\nabla {ふ}_{私}(バツ)-{ヴ}_{私}+\frac{1}{ん}\sum _{じゅう=1}^{ん}{ヴ}_{じゅう}$$
$$:=\frac{1}{ん}\sum _{私=1}^{ん}\nabla {ふ}_{私}(バツ,ヴ)(21)$$
定義するもの$\nabla {ふ}_{私}(バツ,ヴ):=\nabla {ふ}_{私}(バツ)-{ヴ}_{私}+\frac{1}{ん}{\sum }_{じゅう=1}^{ん}{ヴ}_{じゅう}$ 。これで、ランダムにサンプリングできるようになりました。$\nabla {ふ}_{私}(バツ,ヴ)$ 完全なグラデーションを構築するには$\nabla ふ(バツ)$ ～の不偏推定値 i ∈ { 1 , … , n } i は {1, ldots, n} の範囲内である私∈{1,…,ん}、SGD メソッドを適用し、勾配推定を使用できます。
$${グ}_{け}=\nabla {ふ}_{{私}_{け}}({バツ}_{け},ヴ)=\nabla {ふ}_{{私}_{け}}({バツ}_{け})-{ヴ}_{{私}_{け}}+\frac{1}{ん}\sum _{じゅう=1}^{ん}{ヴ}_{じゅう}(22)$$

観察用 ${ヴ}_{私}$ 選択ペアの違い${グ}_{け}$ 影響を与えることができます${グ}_{け}=\nabla {ふ}_{{私}_{け}}({バツ}_{け},ヴ)$ 代用して使用してください${え}_{私}\sim \frac{1}{ん}[{ヴ}_{私}]=\frac{1}{ん}{\sum }_{じゅう=1}^{ん}{ヴ}_{じゅう}$ 期待値を計算すると、次のようになります。
$$え\left[\Vert \nabla {ふ}_{私}({バツ}_{け})-{ヴ}_{私}+{え}_{私}\sim \frac{1}{ん}[{ヴ}_{私}-\nabla {ふ}_{私}({バツ}_{け})]{\Vert }^2\right]\le え\left[\Vert \nabla {ふ}_{私}({バツ}_{け})-{ヴ}_{私}{\Vert }^2\right](23)$$
ここでは補助定理 2 が使用されます。$バツ=\nabla {ふ}_{私}({バツ}_{け})-{ヴ}_{私}$ 。この境界 (23) は、次のことを示しています。${ヴ}_{私}$ とともに$け$ 増加は近いです$\nabla {ふ}_{私}({バツ}_{け})$ 、VR 属性 (12) を取得できます。だからこそ私たちはそう呼んでいます${ヴ}_{私}$ は共変量であり、分散を減らすためにそれらを選択できます。

たとえば、このアプローチは SGD² メソッド (13) によっても実装されます。 ${ヴ}_{私}=\nabla {ふ}_{私}({バツ}^{\ast })$ 。ただし、これは実際にはよくわからないため、実際にはあまり使用されません。$\nabla {ふ}_{私}({バツ}^{\ast })$ 。より現実的なオプションは、${ヴ}_{私}$ みなさんご存じのとおり${\overline{バツ}}_{私}\in {\mathbb{R}}^d$ 近くの勾配$\nabla {ふ}_{私}({\overline{バツ}}_{私})$ 。 機能ごとのSAGA${ふ}_{私}$ 基準点を使用する${\overline{バツ}}_{私}\in {\mathbb{R}}^d$、共変量を使用します ${ヴ}_{私}=\nabla {ふ}_{私}({\overline{バツ}}_{私})$、それぞれ ${\overline{バツ}}_{私}$ 私たちの最後の評価になります${ふ}_{私}$ ポイント。これらの共変量を使用すると、(22) に従って勾配推定値を構築でき、次のようになります。
$${グ}_{け}=\nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({\overline{バツ}}_{{私}_{け}})+\frac{1}{ん}\sum _{じゅう=1}^{ん}\nabla {ふ}_{じゅう}({\overline{バツ}}_{じゅう})(24)$$

SAGA を実装するには、勾配を保存できます。 $\nabla {ふ}_{私}({\overline{バツ}}_{私})$ の代わりに$ん$ 基準点${\overline{バツ}}_{私}$ 。つまり、次のように仮定します${ヴ}_{じゅう}=\nabla {ふ}_{じゅう}({\overline{バツ}}_{じゅう})$ のために j ∈ { 1 , … , n } j は {1, ldots, n} に属するじゅう∈{1,…,ん}、各反復で、SAG のような確率的勾配を更新します。 ${ヴ}_{じゅう}$。

アルゴリズム 2 サーガ

1. パラメータ: ステップサイズ $\gamma >0$
2. 初期化:${バツ}_0$，${ヴ}_{私}=0\in {\mathbb{R}}^d$ のために$私=1,\dots ,ん$
3. 行為 $け=1,\dots ,T-1$ 反復:
   a. ランダムな選択 ik ∈ { 1 , … , n } i_k は {1, ldots, n} に含まれる私け​∈{1,…,ん}
   b. 古い値を保存する${ヴ}_{\text{古い}}={ヴ}_{{私}_{け}}$
   c. アップデート${ヴ}_{{私}_{け}}=\nabla {ふ}_{{私}_{け}}({バツ}_{け})$
   d. アップデート${バツ}_{け+1}={バツ}_{け}-\gamma ({ヴ}_{{私}_{け}}-{ヴ}_{\text{古い}}+{\overline{グ}}_{け})$
   e. 勾配推定値を更新する${\overline{グ}}_{け}={\overline{グ}}_{け-1}+\frac{1}{ん}({ヴ}_{{私}_{け}}-{ヴ}_{\text{古い}})$
4. 出力：${バツ}_T$

SAGA メソッドの反復複雑さは SAG と同じです $お(({\kappa }_{\text{最大}}+ん)\mathrm{見よグ}(1/ϵ))$、ステップ サイズを使用して $\gamma =お(1/{ら}_{\text{最大}})$ 、しかし証明はもっと簡単です。ただし、SAG と同様に、SAGA メソッドにはストレージが必要です$ん$ 補助ベクトル${ヴ}_{私}\in {\mathbb{R}}^d$ のために$私=1,\dots ,ん$、つまり必要性を意味します $お(んd)$ 収納スペースの。いつ$d$ そして$ん$ 両方が大きい場合、これは実現できない可能性があります。次のセクションでは、正則化線形モデルなどの一般的なモデルでこのメモリ要件を削減する方法について詳しく説明します。

できるとき $ん$ 2 つの補助ベクトルがメモリに格納されている場合、SAG と SAGA は同様に動作する傾向があります。このメモリ要件が高すぎる場合は、次のセクションで説明する SVRG 方式が良い代替手段となります。 SVRG 手法は同じ収束率を達成し、多くの場合、実際にはほぼ同じ速度ですが、必要なのは$お(d)$ 一般的な問題については、メモリの不足。

2.3.SVRG法

SAGA メソッドが出現する前、初期の研究の一部では、SAG メソッドに必要な高メモリ問題を解決するために初めて共変量が導入されました。これらの研究は固定された基準点に基づいて行われます$\overline{バツ}\in {\mathbb{R}}^d$ 共変量、その時点での完全な勾配を計算しました$\nabla ふ(\overline{バツ})$ 。基準点を保存することにより$\overline{バツ}$ および対応する完全な勾配$\nabla ふ(\overline{バツ})$、それぞれを保存せずにこれを行うことができます $\nabla {ふ}_{じゅう}(\overline{バツ})$ 場合に備えて、使用してください${\overline{バツ}}_{じゅう}=\overline{バツ}$ みんなに$じゅう$ update(24)を実装します。具体的には、これらのベクトルを保存する代わりに、各反復で保存された参照点を利用します。$\overline{バツ}$ 計算する$\nabla {ふ}_{{私}_{け}}(\overline{バツ})$ 。この手法は当初、異なる著者によって異なる名前で提案されましたが、後に [28] および [84] の命名法に従って SVRG 手法として統一されました。

アルゴリズム 3 で SVRG メソッドを形式化します。

(23) を使用して、勾配推定値を導き出すことができます。 ${グ}_{け}$ の分散には限界があります。
$$え\left[\Vert {グ}_{け}-\nabla ふ({バツ}_{け}){\Vert }^2\right]\le え\left[\Vert \nabla {ふ}_{私}({バツ}_{け})-\nabla {ふ}_{私}(\overline{バツ}){\Vert }^2\right]\le {ら}_{\text{最大}}^2\Vert {バツ}_{け}-\overline{バツ}{\Vert }^2$$
ここで、2 番目の不等式はそれぞれを使用します。${ふ}_{私}$ の${ら}_{私}$-滑らかさ。

注目すべき基準点は、 $\overline{バツ}$ 現在地に近づくほど${バツ}_{け}$、勾配推定の分散が小さくなります。

SVRG 手法を効果的にするには、参照点を頻繁に更新する必要があります。 $\overline{バツ}$ (したがって、完全な勾配の計算が必要になります) は、分散の減少による利点と比較検討されます。このため、私たち一人ひとりが、$t$ 反復ごとに基準点を更新して、基準点を次の値に近づけます。${バツ}_{け}$ (アルゴリズム II-C の 11 行目を参照)。つまり、SVRG メソッドには 2 つのループが含まれています。$s$、参照勾配が計算されます。 $\nabla ふ({\overline{バツ}}_{s-1})$(行 4)、および参照点が固定され、内部反復が確率的勾配ステップに基づいて更新される内部ループ (22) ${バツ}_{け}$(10行目)。

SAG や SAGA とは異なり、SVRG に必要なのは $お(d)$ 記憶の。 SVRG の欠点は次のとおりです。 1) 追加のパラメーターがあります。$t$、つまり、内側のループの長さを調整する必要があります。 2) 反復ごとに 2 つの勾配を計算する必要があり、基準点が変更されるたびに完全な勾配を計算する必要があります。

Johnson と Zhang [28] は、SVRG には反復的な複雑性があることを示しました。 $お(({\kappa }_{\text{最大}}+ん)\mathrm{見よグ}(1/ϵ))$ 、SAG と SAGA に似ています。これは仮説内のループの数です。$t$ コレクションから { 1 , … , m } {1, ldots, m}{1,…,メートル} 均一サンプリングの条件で得られます。${ら}_{\text{最大}}$，$\mu$、 刻み幅 $\gamma$ そして$t$ それらの間で特定の依存関係を満たす必要があります。実際に使用すると、$\gamma =お(1/{ら}_{\text{最大}})$ と内側のループの長さ$t=ん$, SVRG はパフォーマンスが良い傾向にあり、これはまさに図 1 で使用した設定です。

現在、元の SVRG メソッドには多くのバリエーションがあります。たとえば、いくつかのバリエーションでは、 $t$ 代替ディストリビューション [32]、いくつかのバリアントでは次の形式が可能です$お(1/{ら}_{\text{最大}})$ ステップサイズ[27]、[33]、[35]。を使用したいくつかのバリエーションもあります$\nabla ふ(\overline{バツ})$ ミニバッチ近似を使用して、これらの完全な勾配評価のコストを削減し、ミニバッチ サイズを増やして VR プロパティを維持します。[54] に従って、内側のループで更新が繰り返されるバリアントもいくつかあります。${グ}_{け}$：
[ g_k = ナブラ f_{i_k}(x_k) - ナブラ f_{i_k}(x_{k-1}) + g_{k-1} 四辺形 (25) ]
これにより、より局所的な近似が得られます。セクション IV で簡単に説明するように、この連続更新バリアント (25) を使用すると、非凸関数を最小限に抑える上で独自の利点が得られます。最後に、SVRG は次のことを利用できることに注意してください。$\nabla ふ({\overline{バツ}}_s)$ アルゴリズムをいつ終了するかを決定するのに役立つ値。

アルゴリズム3 SVRG法

1. パラメータ: ステップサイズ $\gamma >0$
2. 基準点の初期化 ${\overline{バツ}}_0={バツ}_0\in {\mathbb{R}}^d$
3. 外部循環を行う $s=1,2,\dots$：
   a. 計算して保存する$\nabla ふ({\overline{バツ}}_{s-1})$
   b. 仮定する${バツ}_0={\overline{バツ}}_{s-1}$
   c. 内側のループの反復数を選択します。$t$
   d. 内部循環を行う$け=0,1,\dots ,t-1$：
   i. ランダムな選択 ik ∈ { 1 , … , n } i_k は {1, ldots, n} に含まれる私け​∈{1,…,ん}
   ii. 計算${グ}_{け}=\nabla {ふ}_{{私}_{け}}({バツ}_{け})-\nabla {ふ}_{{私}_{け}}({\overline{バツ}}_{s-1})+\nabla ふ({\overline{バツ}}_{s-1})$
   iii. アップデート${バツ}_{け+1}={バツ}_{け}-\gamma {グ}_{け}$
   e. 基準点を更新する${\overline{バツ}}_s={バツ}_t$

2.4. SDCA とそのバリアント

SAG 手法と SVRG 手法の欠点の 1 つは、それらのステップ サイズが、問題によっては未知の可能性がある未知の値に依存していることです。 ${ら}_{\text{最大}}$ 。 SVRG が登場する前、初期の VR 手法の 1 つである SDCA 手法 [70] は、座標降下法の研究を有限和問題に拡張しました。 SDCA とその変形の背後にある考え方は、勾配の座標が自然な分散を​​低減する勾配推定値を提供するというものです。具体的に考えてみると、 j ∈ { 1 , … , d } j は {1, ldots, d} の範囲内にあるじゅう∈{1,…,d}、定義します ${\nabla }_{じゅう}ふ(バツ):=\left(\frac{\partial ふ(バツ)}{\partial {バツ}_{じゅう}}\right)e_{じゅう}$ (f(x)) の 3 番目です$じゅう$ 座標方向の導関数、ここで$e_{じゅう}\in {\mathbb{R}}^d$ それは最初です$じゅう$ 単位ベクトル。座標導関数の重要な特性は次のとおりです。${\nabla }_{じゅう}ふ({バツ}^{\ast })=0$、私たちは知っているので $\nabla ふ({バツ}^{\ast })=0$ 。各データポイントでのこれの導関数$\nabla {ふ}_{じゅう}$ 違います、後者は${バツ}^{\ast }$ ゼロではないかもしれない。したがって、次のようになります。
$$\Vert \nabla ふ(バツ)-{\nabla }_{じゅう}ふ(バツ){\Vert }^2\to 0\text{いつ}バツ\to {バツ}^{\ast }(26)$$
これは、座標導関数が分散低減特性 (12) を満たすことを意味します。さらに、次のこともできます。${\nabla }_{じゅう}ふ(バツ)$ 構築する$\nabla ふ(バツ)$ の不偏推定値。たとえば、次のように仮定します。$じゅう$ コレクションからです { 1 、 … 、 d } {1、 ldots、 d}{1,…,d} で一様にランダムに選択されたインデックス。したがって、どのような場合でも、 i ∈ { 1 , … , d } i は {1, ldots, d} の範囲内である私∈{1,…,d}、我々は持っています $ポ[じゅう=私]=\frac{1}{d}$ 。したがって、$d\times {\nabla }_{じゅう}ふ(バツ)$ はい$\nabla ふ(バツ)$ 以下の理由による不偏推定:
$$え\left[d{\nabla }_{じゅう}ふ(バツ)\right]=d\sum _{私=1}^dポ[じゅう=私]\frac{\partial ふ(バツ)}{\partial {バツ}_{私}}{e}_{私}=\sum _{私=1}^d\frac{\partial ふ(バツ)}{\partial {バツ}_{私}}{e}_{私}=\nabla ふ(バツ)$$

したがって、${\nabla }_{じゅう}ふ(バツ)$ 共変量を使用する必要がなく、完全な勾配を推定する VR に期待される理想的な特性をすべて備えています。この座標勾配を使用する場合の 1 つの欠点は、和の問題 (2) の計算コストが高くつくことです。これは計算だからです${\nabla }_{じゅう}ふ(バツ)$ データセット全体を走査する必要があるため、${\nabla }_{じゅう}ふ(バツ)=\frac{1}{ん}{\sum }_{私=1}^{ん}{\nabla }_{じゅう}{ふ}_{私}(バツ)$ 。したがって、座標導関数の使用は、和の問題の構造と互換性がないように見えます。ただし、多くの場合、元の問題 (2) をいわゆる双対定式化に書き直すことができ、座標導関数が固有の構造を利用できます。

たとえば、L2 正則化線形モデル (15) の双対公式は次のとおりです。
$${ヴ}^{\ast }\in \mathrm{arグ}\underset{ヴ\in {\mathbb{R}}^{ん}}{\mathrm{最大}}\frac{1}{ん}\sum _{私=1}^{ん}-{\ell }_{私}^{\ast }(-{ヴ}_{私})-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{私=1}^{ん}{ヴ}_{私}{1つの}_{私}\Vert }^2(27)$$
で${\ell }_{私}^{\ast }(ヴ)$ はい${\ell }_{私}$ 凸共役。マッピングを使用できます$バツ=\frac{1}{\lambda }{\sum }_{私=1}^{ん}{ヴ}_{私}{1つの}_{私}$ 元の問題を復元する (15)$バツ$ 変数。解決します${ヴ}^{\ast }$ 上記のマッピングの右側に代入すると、(15) の解が得られます。${バツ}^{\ast }$。

この二重問題には次の点があることに注意してください。 $ん$ 実数変数${ヴ}_{私}\in \mathbb{R}$ 、トレーニング サンプルごとに 1 つに対応します。さらに、それぞれの二重損失関数${\ell }_{私}^{\ast }$ のみ${ヴ}_{私}$ 関数。つまり、損失関数の最初の項は座標的に分離可能です。この座標の分離可能性と第 2 項の単純な形式を組み合わせることで、座標上昇法を効率的に実装することができます。実際、Shalev-Shwartz と Zhang は、この問題の座標上昇には SAG、SAGA、SVRG と同様の反復的な複雑さがあることを示しました。$お(({\kappa }_{\text{最大}}+ん)\mathrm{見よグ}(1/ϵ))$。

反復コストとアルゴリズム構造も非常に似ています: 追跡による合計 ${\sum }_{私=1}^{ん}{ヴ}_{私}{1つの}_{私}$ (27) の第 2 項を処理するには、各二重座標上昇反復では 1 つのトレーニング サンプルのみを考慮する必要があり、各反復のコストは次と同じです。$ん$ 何もすることはありません。さらに、1D ライン検索を使用して、次のように最大化するステップ サイズを効率的に計算できます。${ヴ}_{私}$ 機能の二重の目的。これは、たとえそうでなくても、${ら}_{\text{最大}}$ または、関連する量の知識があれば、VR メソッドの最悪の場合の実行時間を短縮することも可能です。

3. 分散削減の実際的な問題

基本的な分散削減 (VR) メソッドを実装し、適切なパフォーマンスを達成するには、いくつかの実装上の問題に対処する必要があります。このセクションでは、上記で説明されていないいくつかの問題について説明します。

3.1.SAG/SAGA/SVRG設定ステップサイズ

最適化アルゴリズムの分野、特に確率的平均勾配 (SAG)、確率的平均勾配アルゴリズム (SAGA)、確率的勾配 (SVRG) などの変動低減手法では、ステップ サイズの設定が重要な問題です。確率的双対座標上昇 (SDCA) 法の場合、二重目的を使用してステップ サイズを決定できますが、SAG、SAGA、および SVRG の元の変数法の理論的根拠は、ステップ サイズは次のとおりである必要があるということです。 $\gamma =お\left(\frac{1}{{ら}_{\text{最大}}}\right)$ 形状。しかし、実際のアプリケーションでは、わからないことがよくあります。${ら}_{\text{最大}}$ 正確な値を使用し、他のステップ サイズを使用するとパフォーマンスが向上する可能性があります。

完全勾配降下法 (フル GD) 法でステップ サイズを設定するための古典的な戦略は、Armijo ライン探索です。与えられた現在点 ${バツ}_{け}$ そして検索方向${グ}_{け}$、アルミホライン検索で ${\gamma }_{け}$ は次のように定義されるライン上で実行されます。 γ k ∈ {γ:xk + γgk} gamma_k において {gamma:x_k + gammag_k}γけ​∈{γ:バツけ​+γグけ​}、関数は十分に削減される必要があります。つまり、次のとおりです。
$$ふ({バツ}_{け}+{\gamma }_{け}{グ}_{け})<ふ({バツ}_{け})-c{\gamma }_{け}\Vert \nabla ふ({バツ}_{け}){\Vert }^2$$
ただし、このアプローチには複数の候補ステップが必要です${\gamma }_{け}$ 計算$ふ({バツ}_{け}+{\gamma }_{け}{グ}_{け})$、評価します $ふ(バツ)$ データセット全体を走査するとなると、法外なコストがかかります。

この問題を解決するには、ランダム変動法を使用して、次の条件を満たすものを見つけることができます。 ${\gamma }_{け}$：
$${ふ}_{いいね}({バツ}_{け}+{\gamma }_{け}{グ}_{け})<{ふ}_{いいね}({バツ}_{け})-c{\gamma }_{け}\Vert \nabla {ふ}_{いいね}({バツ}_{け}){\Vert }^2$$
このアプローチは通常、特に次のような場合に実際にうまく機能します。$\Vert \nabla {ふ}_{いいね}({バツ}_{け})\Vert$ ゼロに近いわけではありませんが、現時点ではこのアプローチをサポートする理論はありません。

さらに、Mairal は実際にステップ サイズを設定するための「Bottou テクニック」を提案しました。このメソッドは、データ セットのごく一部 (例: 5%) を取得して二分探索を実行し、このサンプルの 1 回のパスで最適なステップ サイズを見つけようとします。 Armijo ライン検索と同様に、この方法も実際にはうまく機能することがよくありますが、やはり理論的基盤が不足しています。

上記の内容は、数式と変数を表すためにマークダウン形式を使用して、原文を再記述したものであることに注意してください。

ただし、SDCA 方式にはいくつかの欠点もあります。まず、凸共役を計算する必要があります。 ${\ell }_{私}^{\ast }$ 単純なグラデーションではなく。凸共役に相当する自動微分関数がないため、実装の労力が増加する可能性があります。最近の研究では、共役を必要とせず、代わりに勾配を直接使用する「デュアルフリー」SDCA 方法が提案されています。ただし、これらの方法では、デュアル ターゲットを追跡してステップ サイズを設定することはできなくなります。第二に、SDCA が必要とするのは$お(ん+d)$ (15) の問題を解決するにはメモリが必要ですが、この問題カテゴリの場合、SAG/SAGA に必要なのは$お(ん+d)$ メモリの容量（セクション 3 を参照）。SAG/SAGA に関するより一般的な問題に適した SDCA のバリアント$お(んd)$ 記憶があるから${ヴ}_{私}$ 持つようになる$d$ 要素のベクトル。 SDCA の最後の微妙な欠点は、暗黙的に強い凸定数を仮定していることです。$\mu$ 等しい$\lambda$ 。のために$\mu$ 以上$\lambda$ 問題は、元の VR メソッドは通常、SDCA よりも大幅に優れたパフォーマンスを発揮します。

3.2. 終了条件の決定

アルゴリズム最適化の分野では、アルゴリズムが特定の精度を達成するために必要な最悪の場合の反復回数を予測するために、反復の複雑さの理論的結果に頼ることがよくあります。ただし、これらの理論的限界は、予測できないいくつかの定数に依存することが多く、実際のアプリケーションでは、アルゴリズムは多くの場合、より少ない反復で期待される精度を達成できます。したがって、アルゴリズムをいつ終了するかを決定するために、いくつかのテスト基準を設定する必要があります。

従来の完全勾配降下法 (フル GD) 法では、通常、勾配のノルムを使用します。 $\Vert \nabla ふ({バツ}_{け})\Vert$ または、反復をいつ停止するかを決定するために、これに関連する他の数量。SVRG メソッドの場合も同じ基準を採用できますが、次を使用します。$\Vert \nabla ふ({\overline{バツ}}_s)\Vert$ 判断材料として。SAG/SAGA 法の場合、完全な勾配を明示的に計算するわけではありませんが、量 $ g_{bar{k}} $ は徐々に近似します。$\nabla ふ({バツ}_{け})$したがって、使用します $\Vert {グ}_{\overline{け}}\Vert$ 停止条件は合理的なヒューリスティックであるためです。

SDCA 法では、追加の記録作業を行うことで、漸近コストを追加することなく二重目的の勾配を追跡できます。さらに、より体系的なアプローチは、二重ギャップを追跡することですが、これにより、$お(ん)$ コストはかかりますが、デュアルギャッププルーフによる終端条件を提供できます。さらに、強く凸のターゲットの最適性条件に基づいて、MISO 方法は二次下限に基づく原則的な方法を採用しています [41]。

以下は、マークダウン形式で表現された数式と変数です。

• 勾配ノルム:$\Vert \nabla ふ({バツ}_{け})\Vert$
• SVRG 法の勾配ノルム:$\Vert \nabla ふ({\overline{バツ}}_s)\Vert$
• SAG/SAGA法における近似勾配量: $ g_{bar{k}} $
• 反復あたりのコストの増加:$お(ん)$
• MISOメソッド
• 二次下限

上記の内容は、数式と変数を表すためにマークダウン形式を使用して、原文を再記述したものであることに注意してください。

3.3. メモリ要件の削減

確率的変分勾配低減 (SVRG) アルゴリズムは、以前の変分低減法のメモリ要件を排除しますが、実際のアプリケーションでは、SAG (確率的平均勾配降下法) および SAGA (勾配累積を伴う確率的平均勾配降下法) アルゴリズムが多くの問題で使用されます。 SVRG アルゴリズムよりも必要な反復回数が少なくなる傾向があります。これをきっかけに次のような考えが生まれました。SAG/SAGA が $お(んd)$ メモリ要件は以下のように実装されます。このセクションでは、メモリ要件を大幅に削減できる線形モデルのクラスについて説明します。

各関数が次のような線形モデルであると考えます。 ${ふ}_{私}(バツ)$ それは次のように表現できます${\xi }_{私}({1つの}_{私}^{\top }バツ)$ 。右$バツ$ 微分すると勾配の形が得られます。
$$\nabla {ふ}_{私}(バツ)={\xi }^{\prime }({1つの}_{私}^{\top }バツ){1つの}_{私}$$
ここ、${\xi }^{\prime }$ 急行$\xi$ の派生語。固有ベクトルに直接アクセスできると仮定すると、${1つの}_{私}$の場合、SAG/SAGA メソッドを実装するには、スカラーを保存するだけで済みます。 $\xi ({1つの}_{私}^{\top }バツ)$ 。このように、メモリ要件は次のように異なります。$お(んd)$ に減少$お(ん)$ 。 SVRG アルゴリズムは、この勾配構造を利用することもできます。$ん$ スカラーの場合、このクラスの問題では、SVRG の「内部」反復ごとに必要な勾配評価の数を 1 に減らすことができます。

確率的グラフィカル モデルなど、メモリ要件を削減できる可能性を提供する他のタイプの問題もあります [66]。特定のデータ構造とアルゴリズムの最適化により、実行時にアルゴリズムが必要とするメモリ リソースをさらに削減できます。

以下は、マークダウン形式で表現された数式と変数です。

• 線形モデル関数:${ふ}_{私}(バツ)={\xi }_{私}({1つの}_{私}^{\top }バツ)$
• グラデーション表現：$\nabla {ふ}_{私}(バツ)={\xi }^{\prime }({1つの}_{私}^{\top }バツ){1つの}_{私}$
• 特徴ベクトル:${1つの}_{私}$
• メモリ要件の範囲は次のとおりです。 $お(んd)$ に減らす$お(ん)$。

3.4. 疎な勾配の処理

一部の問題では、勾配 $\nabla {ふ}_{私}(バツ)$ まばらな特徴を持つ線形モデルなど、多数のゼロ値が含まれる可能性があります。この場合、従来の確率的勾配降下法 (SGD) アルゴリズムを効率的に実装でき、計算量は勾配内の非ゼロ要素の数に比例し、通常は問題の次元よりもはるかに小さくなります。$d$ 。ただし、標準的な変分リダクション (VR) 方法では、この利点は活用されません。幸いなことに、これを改善する既知の方法が 2 つあります。

最初の改良点は Schmidt らによって提案されたもので、更新プロセスの単純さを利用し、各反復のコストが非ゼロの数に比例するように「オンザフライ」計算の変形を実装します。要素。SAG を例にとると (ただし、このアプローチはすべてのバリアントに機能します)、これは各反復後に完全なベクトルを保存しないことで行われます。 ${ヴ}_{いいね}$ただし、ゼロ以外の要素に対応する要素のみを計算します。 ${ヴ}_{私{け}_{じゅう}}$、要素が最後にゼロ以外であったときから各変数を更新することによって ${ヴ}_{私{け}_{じゅう}}$。

2 番目の改善方法は、SAGA に対して Leblond らによって提案されたもので、式を更新します。 ${バツ}_{け+1}={バツ}_{け}-\gamma (\nabla {ふ}_{いいね}({バツ}_{け})-\nabla {ふ}_{いいね}({\overline{バツ}}_{いいね})+{\overline{グ}}_{け})$ 追加のランダム性が導入されます。ここ、$\nabla {ふ}_{いいね}({バツ}_{け})$ そして$\nabla {ふ}_{いいね}({\overline{バツ}}_{いいね})$ まばらであり、${\overline{グ}}_{け}$ 濃いです。この方法では、密な項は$({\overline{グ}}_{け}{)}_{じゅう}$ の各コンポーネントは次のように置き換えられます。${わ}_{じゅう}({\overline{グ}}_{け}{)}_{じゅう}$、で $わ\in {\mathbb{R}}^d$ サポート セットが含まれるランダムなスパース ベクトルです。$\nabla {ふ}_{いいね}({バツ}_{け})$ 、すべての要素が 1 に等しい定数ベクトルであることが期待されます。このようにして、更新プロセスは偏りのない状態を維持し (現在はまばらになっていますが)、分散の増加はアルゴリズムの収束率に影響を与えません。 詳細については、Leblond et al. が提供しています。

以下は、マークダウン形式で表現された数式と変数です。

• 勾配：$\nabla {ふ}_{私}(バツ)$
• SGD の更新:${バツ}_{け+1}={バツ}_{け}-\gamma (\nabla {ふ}_{いいね}({バツ}_{け})-\nabla {ふ}_{いいね}({\overline{バツ}}_{いいね})+{\overline{グ}}_{け})$
• 疎なグラデーション:$\nabla {ふ}_{いいね}({バツ}_{け})$ そして$\nabla {ふ}_{いいね}({\overline{バツ}}_{いいね})$
• 濃いグラデーション:${\overline{グ}}_{け}$
• ランダムなスパースベクトル:$わ$
• 定数ベクトル、つまりすべての要素が 1 に等しいベクトルを期待します。