【深度學習】圖形模型基礎(7)：機器學習優化中的方差減少方法(1)

摘要

隨機優化是機器學習中至關重要的組成部分，其核心是隨機梯度下降算法（SGD），這種方法自60多年前首次提出以來一直被廣泛使用。近八年來，我們見證了一個激動人心的新進展：隨機優化方法的方差降低技術。這些方差降低的方法（VR方法）在允許多次迭代訓練數據的場景下表現出色，無論是在理論上還是在實踐中，它們都顯示出比SGD更快的收斂速度。這種速度的提高凸顯了VR方法的日益增長的興趣和這一領域迅速積累的研究成果。本文綜述了VR方法在有限數據集優化中的關鍵原則和主要進展，旨在為非專家讀者提供信息。我們主要集中討論了凸優化環境，并為那些對非凸函數最小化擴展感興趣的讀者提供了參考。

關鍵詞 | 機器學習；優化；方差降低

1.引言

在機器學習的研究領域中，一個基礎而重要的問題是如何將模型適配到龐大的數據集上。例如，我們可以考慮線性最小二乘模型的典型案例：

$x^* \in \arg\min_{x \in \mathbb{R}^d} \frac{1}{n} \sum_{i=1}^{n} (a_i^T x - b_i)^2$

在這個模型中，我們有 $d$ 個參數，它們由向量 $\in \mathbb{R}^d$ 給出。同時，我們手頭有 $n$ 個數據點，包括特征向量 $a_i \in \mathbb{R}^d$ 和目標值 $b_i \in \mathbb{R}$ 。模型的適配過程就是調整這些參數，以使得模型的預測輸出 $a_i^T x$ 平均上盡可能接近目標值 $b_i$ 。

更廣泛地說，我們可能會使用損失函數 $f_i(x)$ 來衡量模型預測與第 $i$ 個數據點的接近程度：

$x^* \in \arg\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{n} \sum_{i=1}^{n} f_i(x)$

損失函數 $f_i(x)$ 如果較大，表明模型的預測與數據有較大偏差；如果 $f_i(x)$ 等于零，則表示模型完美地擬合了數據點。函數 $f (x)$ 反映了模型在整個數據集上的平均損失。

類似上述形式 (2) 的問題不僅適用于線性最小二乘問題，也適用于機器學習中研究的許多其他模型。例如，在邏輯回歸模型中，我們解決的是：

$x^* \in \arg\min_{x \in \mathbb{R}^d} \frac{1}{n} \sum_{i=1}^{n} \log(1 + e^{-b_i a_i^T x}) + \frac{\lambda}{2} \|x\|_2^2$

這里，我們處理的是 $b_i \in \{-1, +1\}$ 的二元分類問題，預測是基于 $a_i^T x$ 的符號來進行的。公式中還引入了正則化項 $\frac{\lambda}{2} \|x\|_2^2$ 來避免對數據的過擬合，其中 $x\|_2^2$ 表示 $x$ 的歐幾里得范數的平方。

在大多數監督學習模型中，訓練過程可以表示為形式 (2)，包括 L1 正則化最小二乘、支持向量機 (SVM)、主成分分析、條件隨機場和深度神經網絡等。

現代問題實例中的一個關鍵挑戰是數據點的數量 $n$ 可能極其龐大。我們經常處理的數據集大小遠遠超出了太字節的范圍，這些數據可能來自互聯網、衛星、遠程傳感器、金融市場和科學實驗等多種來源。為了應對如此龐大的數據集，一種常見的方法是使用隨機梯度下降（SGD）算法，該算法在每次迭代中僅使用少量隨機選取的數據點。此外，最近對方差減少（VR）的隨機梯度方法的興趣急劇上升，這些方法比傳統的隨機梯度方法具有更快的收斂速度。
在這里插入圖片描述
圖1. 在基于蘑菇數據集[7]的邏輯回歸問題上，將梯度下降（GD）、加速梯度下降（AGD，即[50]中的加速GD）、隨機梯度下降（SGD）和ADAM[30]方法與方差減少（VR）方法SAG和SVRG進行了比較，其中n=8124，d=112。

1.1. 梯度與隨機梯度下降方法

梯度下降（GD）是一種經典算法，用于解決上述問題 (2)，其迭代更新公式如下所示：
$x_{k+1} = x_k - \gamma \frac{1}{n} \sum_{i=1}^{n} \nabla f_i(x_k)$

這里， $\gamma$ 是一個大于零的固定步長值。在GD算法的每次迭代過程中，必須對每一個數據點 $i$ 計算梯度 $\nabla f_i(x_k)$ ，這意味著GD需要對所有 $n$ 個數據點進行完整的遍歷。當數據集的大小 $n$ 變得非常大時，GD算法的每次迭代成本會變得非常高，從而限制了其應用。

作為替代，我們可以考慮隨機梯度下降（SGD）方法，這是由 Robbins 和 Monro 首次提出的，其迭代更新公式如下：
$x_{k+1} = x_k - \gamma \nabla f_{i_k}(x_k)$

SGD算法通過在每次迭代中僅使用一個隨機選取的數據點的梯度 $\nabla f_{i_k}(x_k)$ 來降低每次迭代的成本。在圖 1 中，我們可以看到SGD在優化過程的初期階段比GD（包括加速的GD方法）取得了更顯著的進步。該圖根據輪次（epoch）來展示優化的進展，輪次定義為計算所有 $n$ 個訓練樣本的梯度的次數。GD算法在每個輪次進行一次迭代，而SGD算法則在每個輪次進行 $n$ 次迭代。我們以輪次作為比較SGD和GD的依據，因為在假設 $n$ 非常大的情況下，兩種方法的主要成本都集中在梯度 $\nabla f_i(x_k)$ 的計算上。

1.2.方差問題

讓我們考慮隨機索引 $i_k$ 從集合 $\{1, \ldots, n\}$ 中均勻隨機選擇的情況，這意味著對于所有 $i$ ，選擇 $i_k = i$ 的概率 $P[i_k = i]$ 等于 $\frac{1}{n}$ 。在這種情況下， $\nabla f_{i_k}(x_k)$ 作為 $\nabla f(x_k)$ 的估計量是無偏的，因為根據期望的定義，我們有：
$E[\nabla f_{i_k}(x_k) | x_k] = \frac{1}{n} \sum_{i=1}^{n} \nabla f_i(x_k) = \nabla f(x_k) \quad (6)$

盡管SGD（隨機梯度下降）方法在每次迭代中不保證函數 $f$ 的值會減少，但平均而言，它朝著負的完整梯度方向移動，這代表了下降方向。

然而，擁有一個無偏梯度估計量并不足以確保SGD迭代的收斂性。為了說明這一點，圖 2（左側）展示了使用常數步長對LIBSVM [7] 提供的四類數據集應用邏輯回歸函數時SGD的迭代軌跡。圖中的同心橢圓代表了函數的等高線，即函數值 $f (x) = c$ 對應的點 $x$ 集合， $c$ 是實數集中的特定常數。不同的常數值 $c$ 對應不同的橢圓。

SGD的迭代軌跡并沒有收斂到最優解（圖中以綠色星號表示），而是在最優解周圍形成了一個點云。與此相反，我們在圖 2中使用相同的常數步長展示了一種方差減少（VR）方法——隨機平均梯度（SAG）的迭代軌跡，我們將在后文中介紹這種方法。SGD在這個例子中未能收斂的原因是隨機梯度本身沒有收斂到零，因此，常數步長的SGD方法（5）永遠不會停止。這與梯度下降（GD）方法形成鮮明對比，GD方法會自然停止，因為隨著 $x_k$ 趨近于 $x^*$ ，梯度 $\nabla f(x_k)$ 會趨向于零。
在這里插入圖片描述
圖2. 使用固定步長的SGD（左）和SAG（右）迭代方法的二維邏輯回歸的水平集圖。綠色星號表示x解。

1.3.經典方差減少方法

處理由于 $\nabla f_i(x_k)$ 值的方差導致的非收斂性問題，有幾種經典技術。例如，Robbins 和 Monro [64] 通過使用一系列遞減的步長 $\gamma_k$ 來解決方差問題，確保乘積 $\gamma_k \nabla f_{i_k}(x_k)$ 能夠收斂到零。然而，調整這個遞減步長序列以避免過早或過晚停止算法是一個難題。

另一種減少方差的經典技術是每次迭代中使用多個 $\nabla f_i(x_k)$ 的平均值，以獲得對完整梯度 $\nabla f(x)$ 的更準確估計。這種方法稱為小批量處理（minibatch），尤其適用于可以并行評估多個梯度的情況。這導致迭代形式如下：
$x_{k+1} = x_k - \gamma \frac{1}{|B_k|} \sum_{i \in B_k} \nabla f_i(x_k) \quad (7)$
其中 $B_k$ 是一個隨機索引集合， $B_k|$ 表示 $B_k$ 的大小。如果 $B_k$ 以有放回的方式均勻采樣，那么這個梯度估計的方差與“批量大小” $B_k|$ 成反比，因此可以通過增加批量大小來降低方差。

但是，這種迭代的成本與批量大小成正比，因此這種方差減少形式是以增加計算成本為代價的。

另一個常見的減少方差并提高SGD經驗性能的策略是添加“動量”，這是一個基于過去步驟中使用的方向的額外項。特別是，帶動量的SGD形式如下：
$x_{k+1} = x_k - \gamma m_k \quad (9)$
其中動量參數 $\beta$ 位于 (0, 1) 范圍內。如果初始動量 $m_0 = 0$ ，并在 (8) 中展開 $m_k$ 的更新，我們得到 $m_k$ 是之前梯度的加權平均：
$m_k = \sum_{t=0}^{k} \beta^{k-t} \nabla f_{i_t}(x_t) \quad (10)$
因此， $m_k$ 是隨機梯度的加權和。由于 $\sum_{t=0}^{k} \beta^{k-t} = \frac{1 - \beta^{k+1}}{1 - \beta}$ ，我們可以將 $\frac{1 - \beta}{1 - \beta^k} m_k$ 視為隨機梯度的加權平均。如果我們將其與完整梯度的表達式 $\nabla f(x_k) = \frac{1}{n} \sum_{i=1}^{n} \nabla f_i(x_k)$ 進行比較，我們可以將 $\frac{1 - \beta}{1 - \beta^k} m_k$ （以及 $m_k$ ）解釋為對完整梯度的估計。這種加權和雖然減少了方差，但也帶來了關鍵問題。由于加權和（10）對最近采樣的梯度賦予了更多權重，它不會收斂到完整梯度 $\nabla f(x_k)$ ，后者是一個簡單平均。我們將在第二節A中看到的第一種方差減少方法通過使用簡單平均而不是任何加權平均來解決這個問題。

1.4.現代方差減少方法

與經典方法不同，它們直接使用一個或多個 $\nabla f_i(x_k)$ 作為 $\nabla f(x_k)$ 的近似值，現代方差減少（VR）方法采用了一種不同的策略。這些方法利用 $\nabla f_i(x_k)$ 來更新梯度的估計值 $g_k$ ，其目標是讓 $g_k$ 逼近 $\nabla f(x_k)$ 。具體來說，我們希望 $g_k$ 能夠滿足 $g_k \approx \nabla f(x_k)$ 。基于這樣的梯度估計，我們接著執行形式如下的近似梯度步驟：
$x_{k+1} = x_k - \gamma g_k \quad (11)$
這里的 $\gamma > 0$ 是步長參數。

為了確保使用常數步長 $\gamma$ 時迭代 (11) 能夠收斂，我們需要保證梯度估計 $g_k$ 的方差趨向于零。數學上，這可以表達為：
$E\left[ \| g_k - \nabla f(x_k) \|^2 \right] \rightarrow 0 \quad \text{as } k \rightarrow \infty \quad (12)$
這里的期望 $E$ 是基于算法中直到第 $k$ 次迭代的所有隨機變量計算的。屬性 (12) 確保了 VR 方法在達到最優解時能夠停止。我們將此屬性視為 VR 方法的一個標志性特征，因此稱之為 VR 屬性。值得注意的是，“減少的”方差這個表述可能會引起誤解，因為實際上方差是趨向于零的。屬性 (12) 是 VR 方法在理論上（在適當的假設條件下）和實踐中（如圖 1 所展示的）能夠實現更快收斂的關鍵因素。

1.5.第一個方差減少方法的例子：SGD2

一種簡單的改進方法可以使SGD遞歸式（5）在不減小步長的情況下實現收斂，那就是對每個梯度進行平移，具體做法是減去 $\nabla f_i(x^*)$ ，這種方法定義如下：
$x_{k+1} = x_k - \gamma (\nabla f_{i_k}(x_k) - \nabla f_{i_k}(x^*)) \quad (13)$
這種方法被稱為SGD2 [22]。雖然我們通常無法確切知道每個 $\nabla f_i(x^*)$ ，但SGD2作為一個例子，能夠很好地闡釋方差減少方法的基本特性。此外，許多方差減少方法都可以看作是SGD2方法的一種近似形式；這些方法不是依賴于已知的每個 $\nabla f_i(x^*)$ ，而是使用能夠逼近 $\nabla f_i(x^*)$ 的估計值。

值得注意的是，SGD2使用的是對完整梯度的無偏估計。因為 $\nabla f(x^*) = 0$ ，所以有：
$E[\nabla f_{i_k}(x_k) - \nabla f_{i_k}(x^*)] = \nabla f(x_k) - \nabla f(x^*) = \nabla f(x_k)$
另外，當SGD2達到最優解時，它自然會停止，因為對于任意 $i$ ，有：
$(\nabla f_i(x) - \nabla f_i(x^*)) \bigg|_{x=x^*} = 0$

進一步觀察，隨著 $x_k$ 接近 $x^*$ （對于連續的 $\nabla f_i$ ），SGD2滿足方差減少屬性（12），因為：
$E\left[ \| g_k - \nabla f(x_k) \|^2 \right] = \\E\left[ \| \nabla f_{i_k}(x_k) - \nabla f_{i_k}(x^*) - \nabla f(x_k) \|^2 \right] \leq E\left[ \| \nabla f_{i_k}(x_k) - \nabla f_{i_k}(x^*) \|^2 \right]$
這里我們使用了引理2，令 $\nabla f_{i_k}(x_k) - \nabla f_{i_k}(x^*)$ ，并利用了 $E[\nabla f_{i_k}(x_k) - \nabla f_{i_k}(x^*)] = \nabla f(x_k)$ 的性質。這個屬性表明SGD2具有比傳統SGD方法更快的收斂速度，我們已在附錄B中對此進行了詳細說明。

1.6.方差減少方法的快速收斂性

本節我們將介紹兩個標準假設，這些假設用于分析方差減少（VR）方法，并討論在這些假設下相比于傳統SGD方法所能夠實現的加速效果。首先，我們假設梯度具有Lipschitz連續性，這表示梯度的變化速度是有限的。

假設1（Lipschitz連續性）

我們假設函數 $f$ 是可微的并且是 $L$ -平滑的，對于所有 $x$ 和 $y$ 以及某個 $\infty$ ，滿足以下條件：
$\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\| \quad (14)$
這意味著每個 $\mathbb{R}^d \rightarrow \mathbb{R}$ 是可微的， $L_i$ -平滑的，我們定義 $L_{\text{max}}$ 為 $max\{L_1, . . . , L_n\}$ 。

雖然這通常被認為是一個較弱的假設，但在后續章節中，我們將討論適用于非光滑問題的VR方法。對于兩次可微的單變量函數， $L$ -平滑性可以直觀理解為：它等同于假設二階導數被 $L$ 上限，即 $\leq L$ 對于所有 $\in \mathbb{R}^d$ 。對于多變量的兩次可微函數，它等同于假設Hessian矩陣 $\nabla^2 f(x)$ 的奇異值被 $L$ 上限。

假設2（強凸性）

我們考慮的第二個假設是函數 (f) 是 $\mu$ -強凸的，這意味著對于某個 $\mu > 0$ ，函數 $\mapsto f(x) - \frac{\mu}{2}\|x\|^2$ 是凸的。此外，對于每個 $i = 1, ..., n$ ， $\mathbb{R}^d \rightarrow \mathbb{R}$ 是凸的。

這是一個較強的假設。在最小二乘問題中，每個 (fi$ 是凸的，但總體函數 (f) 只有在設計矩陣 $A := [a_1, . . . , a_n]$ 具有完全行秩時才是強凸的。L2正則化的邏輯回歸問題由于正則化項的存在，滿足這個假設，其中 $\mu \geq \lambda$ 。

滿足這些假設的一個重要問題類別是形式如下的優化問題：
$x^* \in \arg\min_{x \in \mathbb{R}^d} f(x) = \frac{1}{n} \sum_{i=1}^{n} \ell_i(a_i^Tx) + \frac{\lambda}{2}\|x\|^2 \quad (15)$
其中每個“損失”函數 $\ell_i: \mathbb{R} \rightarrow \mathbb{R}$ 是兩次可微的，并且其二階導數 $\ell_i''$ 被限制在0和某個上界 $M$ 之間。這包括了機器學習中帶有L2正則化的多種損失函數，例如最小二乘、邏輯回歸、probit回歸、Huber穩健回歸等。在這種情況下，對于所有 $i$ ，我們有 $L_i \leq M\|a_i\|^2 + \lambda$ 并且 $\mu \geq \lambda$ 。

在這些假設下，梯度下降（GD）方法的收斂速率由條件數 $\kappa := L/\mu$ 決定。條件數總是大于或等于1，當它顯著大于1時，函數的等值線變得非常橢圓形，導致GD方法的迭代產生振蕩。相反，當 $\kappa$ 接近1時，GD方法收斂得更快。

在假設1和假設2下，VR方法以線性速率收斂。我們說一個隨機方法的函數值 ({f(x_k)}) 以 $\rho \leq 1$ 的速率線性收斂（在期望下），如果存在一個常數 $C > 0$ 使得：
$E[f(x_k)] - f(x^*) \leq (1 - \rho)^k C = O(\exp(-k\rho)) \quad \forall k \quad (16)$
這與每次迭代僅依賴于梯度無偏估計的經典SGD方法形成對比，后者在這些假設下只能獲得次線性速率：
$E[f(x_k)] - f(x^*) \leq O(1/k)$
滿足這個不等式的最小 $k$ 稱為算法的迭代復雜度。以下是GD、SGD和VR方法的基本變體的迭代復雜度和一次迭代的成本：

算法	迭代次數	一次迭代的成本
GD	$O(\kappa \log(1/\epsilon))$	$O (n)$
SGD	$O(\kappa_{\text{max}} \max(1/\epsilon))$	$O (1)$
VR	$O((\kappa_{\text{max}} + n) \log(1/\epsilon))$	$O (1)$

算法的總運行時間由迭代復雜度和迭代運行時間的乘積決定。這里使用了 $\kappa_{\text{max}} := \max_i L_i/\mu$ 。注意 $\kappa_{\text{max}} \geq \kappa$ ；因此，GD的迭代復雜度小于VR方法。

然而，由于GD的每次迭代成本是VR方法的 $n$ 倍，VR方法在總運行時間方面更優越。

經典SGD方法的優勢在于它們的運行時間和收斂速率不依賴于 $n$ ，但它對容差 $\epsilon$ 的依賴性要差得多，這解釋了當容差很小時SGD的性能較差。

在附錄B中，我們提供了一個簡單的證明，表明SGD2方法具有與VR方法相同的迭代復雜度。

2.基礎方差減少方法

方差減少（VR）方法的發展經歷了幾個階段，最初的一批方法使得收斂速率得到了顯著提升。這一系列方法的開端是SAG算法。隨后，隨機對偶坐標上升（SDCA）算法、MISO算法、隨機方差減少梯度（SVRG/S2GD）算法，以及SAGA（意為“改進的”SAG）算法相繼問世。

在本章中，我們將詳細介紹這些開創性的VR方法。而在第四章，我們會探討一些更新的方法，它們在特定的應用場景中相比這些基礎方法展現出了更優越的特性。

2.1.隨機平均梯度方法（SAG）

我們對第一種方差減少（VR）方法的探索，始于對完整梯度結構的模仿。既然完整梯度 $\nabla f(x)$ 是所有 $\nabla f_i(x)$ 梯度的簡單平均，那么我們對完整梯度的估計 $g_k$ 也應該是這些梯度估計的平均。這種思想催生了我們的第一種VR方法：隨機平均梯度（SAG）方法。

SAG方法[37]，[65]是早期增量聚合梯度（IAG）方法[4]的隨機化版本。SAG的核心思想是對每個數據點 $i$ 維護一個估計值 $v_{ik} \approx \nabla f_i(x_k)$ 。然后，用這些 $v_{ik}$ 值的平均來作為對完整梯度的估計，即：
$\bar{g}_k = \frac{1}{n} \sum_{j=1}^{n} v_{jk} \approx \frac{1}{n} \sum_{j=1}^{n} \nabla f_j(x_k) = \nabla f(x_k) \quad (18)$

在SAG的每次迭代中，從集合 $\{1, \ldots, n\}$ 中抽取一個索引 $i_k$ ，然后根據以下規則更新 $v_{jk}$ ：
$v_{jk}^{k+1} = \begin{cases} \nabla f_{i_k}(x_k), & \text{if } j = i_k \\ v_{jk}^k, & \text{if } j \neq i_k \end{cases} \quad (19)$
其中，每個 $v_{0i}$ 可以初始化為零或 $\nabla f_i(x_0)$ 的近似值。隨著解 $x^*$ 的逼近，每個 $v_{ik}$ 會逐漸收斂到 $\nabla f_i(x^*)$ ，從而滿足VR屬性（12）。

為了高效實現SAG，我們需要注意在計算 $\bar{g}_k$ 時避免每次都從頭開始求和 $n$ 個向量，因為這在 $n$ 很大時成本很高。幸運的是，由于每次迭代只有一個 $v_{ik}$ 項會改變，我們可以不必每次都重新計算整個和。具體來說，假設在迭代 $k$ 中抽取了索引 $i_k$ ，則有：
$\bar{g}_k = \frac{1}{n} \sum_{\substack{j=1 \\ j \neq i_k}}^{n} v_{jk} + \frac{1}{n} v_{i_k}^k = \bar{g}_{k-1} - \frac{1}{n} v_{i_k}^{k-1} + \frac{1}{n} v_{i_k}^k \quad (20)$

由于除了 $v_{i_k}$ 之外的所有 $v_{jk}$ 值都保持不變，我們只需存儲每個 $j$ 對應的一個向量 $v_j$ 。算法1展示了SAG方法的具體實現。

SAG是首個實現線性收斂的隨機方法，其迭代復雜度為 $O((\kappa_{\text{max}} + n) \log(1/\epsilon))$ ，使用步長 $\gamma = O(1/L_{\text{max}})$ 。這種線性收斂性可以在圖1中觀察到。值得注意的是，由于 $L_{\text{max}}$ -平滑函數對于任何 $\geq L_{\text{max}}$ 也是 $L^{'}$ -平滑的，SAG方法對于足夠小的步長都能獲得線性收斂速率，這與經典SGD方法形成鮮明對比，后者只有在難以在實踐中調整的遞減步長序列下才能獲得次線性速率。

在當時，SAG的線性收斂是一個顯著的進展，因為它在每次迭代中只計算了一個隨機梯度（處理單個數據點）。然而，Schmidt等人[65]提供的收斂證明非常復雜，并且依賴于計算機驗證的步驟。SAG難以分析的一個關鍵原因是 $g_k$ 是梯度的一個有偏估計。

接下來，我們將介紹SAGA方法，這是SAG的一個變體，它利用協變量的概念來創建一個無偏的SAG方法變體，該變體具有類似的性能但更易于分析。

算法 1：SAG 方法

參數：步長 $\gamma > 0$
初始化： $x_0$ ， $v_i = 0 \in \mathbb{R}^d$ 對于 $\ldots, n$
對 $\ldots, T - 1$ 執行：
a. 隨機抽取 $i_k \in \{1, \ldots, n\}$
b. 計算 $\bar{g}_k = \bar{g}_{k-1} - \frac{1}{n} v_{i_k}^{k-1}$
c. 更新 $v_{i_k}^k = \nabla f_{i_k}(x_k)$
d. 更新梯度估計 $\bar{g}_k = \bar{g}_k + \frac{1}{n} v_{i_k}^k$
e. 更新 $x_{k+1} = x_k - \gamma \bar{g}_k$
輸出： $x_T$

2.2.SAGA方法

一種減少基本無偏梯度估計 $\nabla f_{i_k}(x_k)$ 方差的方法是通過使用所謂的協變量（或稱控制變量）。對于 $\ldots, n$ ，設 $v_i \in \mathbb{R}^d$ 是一個向量。利用這些向量，我們可以將完整梯度 $\nabla f(x)$ 重寫為：
$\nabla f(x) = \frac{1}{n} \sum_{i=1}^{n}(\nabla f_i(x) - v_i + v_i) = \frac{1}{n} \sum_{i=1}^{n} \nabla f_i(x) - v_i + \frac{1}{n} \sum_{j=1}^{n} v_j$
$\frac{1}{n} \sum_{i=1}^{n} \nabla f_i(x, v) \quad (21)$
其中定義 $\nabla f_i(x, v) := \nabla f_i(x) - v_i + \frac{1}{n} \sum_{j=1}^{n} v_j$ 。現在，我們可以通過隨機抽樣一個 $\nabla f_i(x, v)$ 來構建完整梯度 $\nabla f(x)$ 的無偏估計，對于 $\in \{1, \ldots, n\}$ ，可以應用SGD方法，并使用梯度估計：
$g_k = \nabla f_{i_k}(x_k, v) = \nabla f_{i_k}(x_k) - v_{i_k} + \frac{1}{n} \sum_{j=1}^{n} v_j \quad (22)$

為了觀察 $v_i$ 的選擇對方差 $g_k$ 的影響，我們可以將 $g_k = \nabla f_{i_k}(x_k, v)$ 代入，并利用 $E_i \sim \frac{1}{n}[v_i] = \frac{1}{n} \sum_{j=1}^{n} v_j$ 來計算期望，得到：
$\left[ \|\nabla f_i(x_k) - v_i + E_i \sim \frac{1}{n}[v_i - \nabla f_i(x_k)]\|^2 \right] \leq E \left[ \|\nabla f_i(x_k) - v_i\|^2 \right] \quad (23)$
這里使用了引理2，其中 $\nabla f_i(x_k) - v_i$ 。這個界限 (23) 表明，如果 $v_i$ 隨著 $k$ 的增加接近 $\nabla f_i(x_k)$ ，我們就能獲得VR屬性 (12)。這就是為什么我們稱 $v_i$ 為協變量，并且我們可以選擇它們來減少方差。

例如，SGD2 方法 (13) 也實現了這種方法，其中 $v_i = \nabla f_i(x^*)$ 。然而，這在實踐中不常用，因為我們通常不知道 $\nabla f_i(x^*)$ 。一個更實用的選擇是 $v_i$ 作為我們知道的點 $\bar{x}_i \in \mathbb{R}^d$ 附近的梯度 $\nabla f_i(\bar{x}_i)$ 。SAGA 對每個函數 $f_i$ 使用一個參考點 $\bar{x}_i \in \mathbb{R}^d$ ，并使用協變量 $v_i = \nabla f_i(\bar{x}_i)$ ，其中每個 $\bar{x}_i$ 將是我們最后一次評估 $f_i$ 的點。使用這些協變量，我們可以構建梯度估計，按照 (22)，給出：
$g_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(\bar{x}_{i_k}) + \frac{1}{n} \sum_{j=1}^{n} \nabla f_j(\bar{x}_j) \quad (24)$

為了實現SAGA，我們可以存儲梯度 $\nabla f_i(\bar{x}_i)$ 而不是 $n$ 個參考點 $\bar{x}_i$ 。也就是說，設 $v_j = \nabla f_j(\bar{x}_j)$ 對于 $\in \{1, \ldots, n\}$ ，在每次迭代中，我們像SAG一樣更新一個隨機梯度的 $v_j$ 。

算法 2 SAGA

參數：步長 $\gamma > 0$
初始化： $x_0$ ， $v_i = 0 \in \mathbb{R}^d$ 對于 $\ldots, n$
進行 $\ldots, T - 1$ 次迭代：
a. 隨機抽取 $i_k \in \{1, \ldots, n\}$
b. 保存舊值 $v_{\text{old}} = v_{i_k}$
c. 更新 $v_{i_k} = \nabla f_{i_k}(x_k)$
d. 更新 $x_{k+1} = x_k - \gamma (v_{i_k} - v_{\text{old}} + \bar{g}_k)$
e. 更新梯度估計 $\bar{g}_k = \bar{g}_{k-1} + \frac{1}{n} (v_{i_k} - v_{\text{old}})$
輸出： $x_T$

SAGA方法具有與SAG相同的迭代復雜度 $O((\kappa_{\text{max}} + n) \log(1/\epsilon))$ ，使用步長 $\gamma = O(1/L_{\text{max}})$ ，但證明要簡單得多。然而，與SAG一樣，SAGA方法需要存儲 $n$ 個輔助向量 $v_i \in \mathbb{R}^d$ 對于 $\ldots, n$ ，這意味著需要 $O (n d)$ 的存儲空間。當 $d$ 和 $n$ 都很大時，這可能是不可行的。在下一節中，我們將詳細說明如何為常見模型（如正則化線性模型）減少這種內存需求。

當能夠將 $n$ 個輔助向量存儲在內存中時，SAG和SAGA的表現往往相似。如果這個內存需求太高，我們將在下一節中回顧的SVRG方法是一個不錯的選擇。SVRG方法實現了相同的收斂速率，并且在實踐中通常幾乎一樣快，但只要求 $O (d)$ 的內存，對于一般問題。

2.3.SVRG方法

在SAGA方法出現之前，一些早期的工作首次引入了協變量，以解決SAG方法所要求的高內存問題。這些研究構建了基于一個固定參考點 $\bar{x} \in \mathbb{R}^d$ 的協變量，我們已經在該點計算了完整的梯度 $\nabla f(\bar{x})$ 。通過存儲參考點 $\bar{x}$ 和對應的完整梯度 $\nabla f(\bar{x})$ ，我們可以在不存儲每個 $\nabla f_j(\bar{x})$ 的情況下，使用 $\bar{x}_j = \bar{x}$ 對所有 $j$ 來實現更新 (24)。具體來說，我們不是存儲這些向量，而是在每次迭代中利用存儲的參考點 $\bar{x}$ 來計算 $\nabla f_{i_k}(\bar{x})$ 。這個方法最初由不同的作者以不同的名字提出，但后來統一被稱為SVRG方法，遵循[28]和[84]的命名。

我們在算法3中對SVRG方法進行了形式化。

利用 (23)，我們可以得出梯度估計 $g_k$ 的方差有界：
$E\left[ \| g_k - \nabla f(x_k) \|^2 \right] \leq E\left[ \| \nabla f_i(x_k) - \nabla f_i(\bar{x}) \|^2 \right] \leq L_{\text{max}}^2 \| x_k - \bar{x} \|^2$
其中第二個不等式使用了每個 $f_i$ 的 $L_i$ -平滑性。

值得注意的是，參考點 $\bar{x}$ 越接近當前點 $x_k$ ，梯度估計的方差就越小。

為了讓SVRG方法有效，我們需要在頻繁更新參考點 $\bar{x}$ （從而需要計算完整梯度）的成本與降低方差的好處之間做出權衡。為此，我們每 $t$ 次迭代更新一次參考點，使其接近 $x_k$ （見算法II-C的第11行）。也就是說，SVRG方法包含兩個循環：一個外循環 $s$ ，其中計算參考梯度 $\nabla f(\bar{x}_{s-1})$ （第4行），以及一個內循環，其中固定參考點，并根據隨機梯度步驟（22）更新內部迭代 $x_k$ （第10行）。

與SAG和SAGA不同，SVRG只需要 $O (d)$ 的內存。SVRG的缺點包括：1) 我們有一個額外的參數 $t$ ，即內循環的長度，需要調整；2) 每次迭代需要計算兩個梯度，并且每次更改參考點時都需要計算完整梯度。

Johnson和Zhang[28]展示了SVRG具有迭代復雜度 $O((\kappa_{\text{max}} + n) \log(1/\epsilon))$ ，與SAG和SAGA相似。這是在假設內循環次數 $t$ 從集合 $\{1, \ldots, m\}$ 中均勻抽樣的情況下得出的，其中 $L_{\text{max}}$ ， $\mu$ ，步長 $\gamma$ 和 $t$ 之間必須滿足一定的依賴關系。在實踐中，通過使用 $\gamma = O(1/L_{\text{max}})$ 和內循環長度 $t = n$ ，SVRG往往表現良好，這正是我們在圖1中使用的設置。

現在，有許多原始SVRG方法的變體。例如，有些變體使用 $t$ 的替代分布[32]，有些變體允許形式為 $O(1/L_{\text{max}})$ 的步長[27]，[33]，[35]。還有一些變體使用 $\nabla f(\bar{x})$ 的小批量近似來減少這些完整梯度評估的成本，并增加小批量大小以保持VR屬性。還有一些變體在內循環中根據[54]重復更新 $g_k$ ：
[ g_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(x_{k-1}) + g_{k-1} \quad (25) ]
這提供了更局部的近似。使用這種連續更新變體 (25) 在最小化非凸函數時顯示出獨特的優勢，正如我們在第四節簡要討論的。最后，注意SVRG可以利用 $\nabla f(\bar{x}_s)$ 的值來幫助決定何時終止算法。

算法 3 SVRG方法

參數：步長 $\gamma > 0$
初始化參考點 $\bar{x}_0 = x_0 \in \mathbb{R}^d$
進行外循環 $\ldots$ ：
a. 計算并存儲 $\nabla f(\bar{x}_{s-1})$
b. 設 $x_0 = \bar{x}_{s-1}$
c. 選擇內循環迭代次數 $t$
d. 進行內循環 $\ldots, t - 1$ ：
i. 隨機抽取 $i_k \in \{1, \ldots, n\}$
ii. 計算 $g_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(\bar{x}_{s-1}) + \nabla f(\bar{x}_{s-1})$
iii. 更新 $x_{k+1} = x_k - \gamma g_k$
e. 更新參考點 $\bar{x}_s = x_t$

2.4. SDCA及其變體

SAG和SVRG方法的一個不足之處在于，它們的步長依賴于可能在某些問題中未知的 $L_{\text{max}}$ 。在SVRG之前，SDCA方法[70]作為最早的VR方法之一，將坐標下降方法的研究擴展到了有限和問題。SDCA及其變體背后的理念是，梯度的坐標提供了一種自然的方差減少梯度估計。具體來說，設 $\in \{1, \ldots, d\}$ ，并且定義 $\nabla_j f(x) := \left( \frac{\partial f(x)}{\partial x_j} \right) e_j$ 為 (f(x)) 的第 $j$ 個坐標方向的導數，其中 $e_j \in \mathbb{R}^d$ 是第 $j$ 個單位向量。坐標導數的一個關鍵特性是 $\nabla_j f(x^*) = 0$ ，這是因為我們知道 $\nabla f(x^*) = 0$ 。這與每個數據點的導數 $\nabla f_j$ 不同，后者在 $x^*$ 處可能不為零。因此，我們有：
$\| \nabla f(x) - \nabla_j f(x) \|^2 \rightarrow 0 \quad \text{當} \quad x \rightarrow x^* \quad (26)$
這意味著坐標導數滿足了方差減少屬性（12）。此外，我們還可以使用 $\nabla_j f(x)$ 來構建 $\nabla f(x)$ 的無偏估計。例如，設 $j$ 是從集合 $\{1, \ldots, d\}$ 中均勻隨機選取的索引。因此，對于任何 $\in \{1, \ldots, d\}$ ，我們有 $\frac{1}{d}$ 。因此， $\times \nabla_j f(x)$ 是 $\nabla f(x)$ 的無偏估計，因為：
$E\left[ d \nabla_j f(x) \right] = d \sum_{i=1}^{d} P[j = i] \frac{\partial f(x)}{\partial x_i} e_i = \sum_{i=1}^{d} \frac{\partial f(x)}{\partial x_i} e_i = \nabla f(x)$

因此， $\nabla_j f(x)$ 具有我們期望的VR估計完整梯度的所有理想屬性，而且不需要使用協變量。使用這種坐標梯度的一個缺點是，對于我們的和問題（2），它的計算成本很高。這是因為計算 $\nabla_j f(x)$ 需要遍歷整個數據集，因為 $\nabla_j f(x) = \frac{1}{n} \sum_{i=1}^{n} \nabla_j f_i(x)$ 。因此，使用坐標導數似乎與我們的和問題的結構不兼容。然而，我們可以經常將原始問題（2）重寫為所謂的對偶公式，其中坐標導數可以利用固有的結構。

例如，L2正則化線性模型（15）的對偶公式為：
$v^* \in \arg\max_{v \in \mathbb{R}^n} \frac{1}{n} \sum_{i=1}^{n} -\ell_i^*(-v_i) - \frac{\lambda}{2} \left\| \frac{1}{\lambda} \sum_{i=1}^{n} v_i a_i \right\|^2 \quad (27)$
其中 $\ell_i^*(v)$ 是 $\ell_i$ 的凸共軛。我們可以使用映射 $\frac{1}{\lambda} \sum_{i=1}^{n} v_i a_i$ 來恢復原始問題（15）中的 $x$ 變量。將解 $v^*$ 代入上述映射的右側可以得到（15）的解 $x^*$ 。

注意，這個對偶問題有 $n$ 個實變量 $v_i \in \mathbb{R}$ ，每個訓練樣本對應一個。此外，每個對偶損失函數 $\ell_i^*$ 僅是 $v_i$ 的函數。也就是說，損失函數中的第一項在坐標上是可分離的。這種在坐標上的可分離性，加上第二項的簡單形式，允許我們有效實現坐標上升方法。實際上，Shalev-Shwartz和Zhang展示了在這個問題上的坐標上升具有與SAG、SAGA和SVRG類似的迭代復雜度 $O((\kappa_{\text{max}} + n) \log(1/\epsilon))$ 。

迭代成本和算法結構也非常相似：通過跟蹤求和 $\sum_{i=1}^{n} v_i a_i$ 來處理（27）中的第二項，每個對偶坐標上升迭代只需要考慮一個訓練樣本，并且每次迭代的成本與 $n$ 無關。此外，我們可以使用一維線搜索有效地計算步長，以最大限度地提高作為 $v_i$ 函數的對偶目標。這意味著，即使沒有 $L_{\text{max}}$ 或相關量的了解，也可以實現VR方法的快速最壞情況運行時間。

3.方差縮小的實踐問題

為了實現基本的方差減少（VR）方法并取得合理的性能，必須解決幾個實施問題。在本節中，我們將討論上述未涉及的若干問題。

3.1.SAG/SAGA/SVRG設置步長

在優化算法的領域，特別是隨機平均梯度（SAG）、隨機平均梯度算法（SAGA）和隨機梯度（SVRG）等變分減少方法中，步長的設置是一個關鍵問題。雖然對于隨機對偶坐標上升（SDCA）方法，我們可以使用對偶目標來確定步長，但是SAG、SAGA和SVRG這些原始變量方法的理論依據是步長應為 $\gamma = O\left(\frac{1}{L_{\text{max}}}\right)$ 的形式。然而，在實際應用中，我們往往不知道 $L_{\text{max}}$ 的確切值，而且使用其他步長可能會得到更好的性能。

全梯度下降（full-GD）方法中設置步長的一種經典策略是Armijo線搜索。給定當前點 $x_k$ 和搜索方向 $g_k$ ，Armijo線搜索在 $\gamma_k$ 的線上進行，該線定義為 $\gamma_k \in \{\gamma : x_k + \gamma g_k\}$ ，并且要求函數有充分的減少，即：
$f(x_k + \gamma_k g_k) < f(x_k) - c \gamma_k \|\nabla f(x_k)\|^2$
然而，這種方法需要在多個候選步長 $\gamma_k$ 上計算 $f(x_k + \gamma_k g_k)$ ，這在評估 $f (x)$ 需要遍歷整個數據集時成本過高。

為了解決這個問題，可以采用隨機變體的方法，尋找滿足以下條件的 $\gamma_k$ ：
$f_{ik}(x_k + \gamma_k g_k) < f_{ik}(x_k) - c \gamma_k \|\nabla f_{ik}(x_k)\|^2$
這種方法在實踐中通常效果良好，尤其是在 $\|\nabla f_{ik}(x_k)\|$ 不接近零的情況下，盡管目前還沒有理論支持這種方法。

另外，Mairal 提出了一種在實踐中設置步長的“Bottou技巧”。這種方法通過取數據集的一小部分（例如5%）進行二分搜索，以嘗試找到在通過這個樣本進行一次遍歷時的最優步長。與Armijo線搜索類似，這種方法在實踐中通常表現良好，但同樣缺乏理論基礎。

請注意，上述內容是對原文的重新表述，使用了Markdown格式來表示數學公式和變量。

然而，SDCA方法也有一些缺點。首先，它需要計算凸共軛 $\ell_i^*$ 而不是簡單的梯度。我們沒有凸共軛的自動微分等價物，所以這可能會增加實現工作量。最近的工作已經提出了不需要共軛的“無對偶”SDCA方法，而是直接使用梯度。然而，在這些方法中，不再可能跟蹤對偶目標以設置步長。其次，盡管SDCA只需要 $O (n + d)$ 的內存來解決（15）問題，但對于這個問題類別，SAG/SAGA也只需要 $O (n + d)$ 的內存（見第三節）。適用于更一般問題的SDCA變體具有SAG/SAGA的 $O (n d)$ 內存，因為 $v_i$ 成為具有 $d$ 個元素的向量。SDCA的一個最后的微妙缺點是它隱含地假設強凸性常數 $\mu$ 等于 $\lambda$ 。對于 $\mu$ 大于 $\lambda$ 的問題，原始的VR方法通常顯著優于SDCA。

3.2. 終止條件的確定

在算法優化領域，我們通常依賴于迭代復雜度的理論結果來預測算法達到特定精度所需的最壞情況下的迭代次數。但是，這些理論界限往往依賴于一些我們無法預知的常數，而在實際應用中，算法往往能在更少的迭代次數內達到預期精度。因此，我們需要設立一些測試標準來決定何時應該結束算法的運行。

在傳統的全梯度下降（full-GD）方法中，我們通常根據梯度的范數 $\| \nabla f(x_k) \|$ 或者與此相關的其他量來決定何時停止迭代。對于SVRG方法，我們可以采用相同的準則，但使用 $\| \nabla f(\bar{x}_s) \|$ 來作為判斷依據。對于SAG/SAGA方法，盡管我們沒有顯式地計算完整的梯度，但量 $ g_{\bar{k}} $ 會逐漸逼近 $\nabla f(x_k)$ ，因此，使用 $\| g_{\bar{k}} \|$ 作為停止條件是一種合理的啟發式方法。

在SDCA方法中，通過一些額外的記錄工作，我們可以在不增加額外漸近成本的情況下跟蹤對偶目標的梯度。此外，一種更為系統的方法是跟蹤對偶間隙，雖然這會增加每迭代 $O (n)$ 的成本，但它能夠提供具有對偶間隙證明的終止條件。另外，基于強凸目標的最優性條件，MISO方法采用了一種基于二次下界[41]的原則性方法。

以下是使用Markdown格式表示的數學公式和變量：

梯度范數： $\| \nabla f(x_k) \|$
SVRG方法中的梯度范數： $\| \nabla f(\bar{x}_s) \|$
SAG/SAGA方法中逼近梯度的量：$ g_{\bar{k}} $
每迭代增加的成本： $O (n)$
MISO方法
二次下界

請注意，上述內容是對原文的重新表述，使用了Markdown格式來表示數學公式和變量。

3.3. 減少內存需求

盡管隨機梯度變分減少（SVRG）算法消除了早期變分減少方法的內存需求，但在實際應用中，SAG（隨機平均梯度下降）和SAGA（帶梯度累積的隨機平均梯度下降）算法在很多問題上往往比SVRG算法需要更少的迭代次數。這引發了一個思考：是否存在某些問題，使得SAG/SAGA能夠在 $O (n d)$ 內存需求以下實現。本節將探討線性模型類別，這類模型的內存需求可以顯著降低。

考慮線性模型，其中每個函數 $f_i(x)$ 可以表示為 $\xi_i(\mathbf{a}_i^\top x)$ 。對 $x$ 求導得到梯度形式：
$\nabla f_i(x) = \xi'(\mathbf{a}_i^\top x) \mathbf{a}_i$
這里， $\xi'$ 表示 $\xi$ 的導數。假設我們可以直接訪問特征向量 $\mathbf{a}_i$ ，那么為了實現SAG/SAGA方法，我們只需要存儲標量 $\xi(\mathbf{a}_i^\top x)$ 。這樣，內存需求就從 $O (n d)$ 減少到了 $O (n)$ 。SVRG算法也可以利用梯度的這種結構：通過存儲這 $n$ 個標量，我們可以將SVRG“內部”迭代中每次所需的梯度評估次數減少到1，對于這一類問題。

還有其他類型的問題，例如概率圖模型，它們也提供了降低內存需求的可能性[66]。通過特定的數據結構和算法優化，可以進一步減少算法在運行時所需的內存資源。

以下是使用Markdown格式表示的數學公式和變量：

線性模型函數： $f_i(x) = \xi_i(\mathbf{a}_i^\top x)$
梯度表達式： $\nabla f_i(x) = \xi'(\mathbf{a}_i^\top x) \mathbf{a}_i$
特征向量： $\mathbf{a}_i$
內存需求從 $O (n d)$ 減少到 $O (n)$ 。

3.4. 稀疏梯度的處理

在某些問題中，梯度 $\nabla f_i(x)$ 可能包含大量零值，例如具有稀疏特征的線性模型。在這種情況下，傳統的隨機梯度下降（SGD）算法可以高效實現，其計算復雜度與梯度中非零元素的數量成線性關系，這通常遠小于問題維度 $d$ 。然而，在標準的變分減少（VR）方法中，這種優勢并沒有被利用。幸運的是，存在兩種已知的改進方法。

第一種改進方法由Schmidt等人提出，它利用了更新過程的簡單性，實現了一種“即時”計算的變體，使得每次迭代的成本與非零元素的數量成正比。以SAG為例（但這種方法適用于所有變體），具體做法是在每次迭代后不存儲完整的向量 $v_{ik}$ ，而是只計算對應于非零元素的 $v_{ik_j}$ ，通過更新自上次該元素非零以來的每個變量 $v_{ik_j}$ 。

第二種改進方法由Leblond等人為SAGA提出，它在更新公式 $x_{k+1} = x_k - \gamma(\nabla f_{ik}(x_k) - \nabla f_{ik}(\bar{x}_{ik}) + \bar{g}_k)$ 中引入了額外的隨機性。這里， $\nabla f_{ik}(x_k)$ 和 $\nabla f_{ik}(\bar{x}_{ik})$ 是稀疏的，而 $\bar{g}_k$ 是密集的。在這個方法中，密集項 $(\bar{g}_k)_j$ 的每個分量被替換為 $w_j (\bar{g}_k)_j$ ，其中 $\in \mathbb{R}^d$ 是一個隨機稀疏向量，其支持集包含在 $\nabla f_{ik}(x_k)$ 中，并且期望上是一個所有元素都為1的常數向量。這樣，更新過程保持了無偏性（盡管現在是稀疏的），并且增加的方差不會影響算法的收斂速率。Leblond等人提供了更多的細節。

以下是使用Markdown格式表示的數學公式和變量：

梯度： $\nabla f_i(x)$
SGD更新： $x_{k+1} = x_k - \gamma(\nabla f_{ik}(x_k) - \nabla f_{ik}(\bar{x}_{ik}) + \bar{g}_k)$
稀疏梯度： $\nabla f_{ik}(x_k)$ 和 $\nabla f_{ik}(\bar{x}_{ik})$
密集梯度： $\bar{g}_k$
隨機稀疏向量： $w$
期望常數向量：所有元素都為1的向量。