Stochastic Variance Reduced Gradient (SVRG)

While Stochastic Gradient Descent (SGD) offers scalability for large datasets, its inherent gradient variance remains a significant hurdle, often preventing rapid convergence to high-precision solutions. Stochastic Average Gradient (SAG) addresses this by storing and averaging past gradients, but this comes at the cost of potentially large memory requirements. Stochastic Variance Reduced Gradient (SVRG) presents an alternative approach to reducing variance without the need to store a gradient for every data point.

The core idea behind SVRG is elegant: instead of just using the noisy stochastic gradient, it corrects this gradient using information from a less noisy, full batch gradient computed periodically. This correction aims to maintain an unbiased estimate of the true gradient while significantly reducing its variance, especially as the optimization process nears a minimum.

The SVRG Algorithm

SVRG operates in epochs, where each epoch consists of two stages: a full gradient computation and a series of stochastic updates refined by this full gradient.

Let $f(w)$ be the objective function we want to minimize, which is typically an average over $N$ data points: $f(w) = \frac{1}{N} \sum_{i=1}^{N} f_i(w)$.

The algorithm proceeds as follows:

1. Initialization: Start with an initial parameter vector $w_0$.
2. Outer Loop (Epochs): For each epoch $s = 0, 1, 2, ...$ a. Snapshot: Choose a snapshot parameter vector $\tilde{w}$. A common choice is the final parameter vector from the previous epoch, $\tilde{w} = w_m^{(s-1)}$ (or $w_0$ for the first epoch). b. Full Gradient Calculation: Compute the average gradient over the entire dataset using the snapshot parameters: $\nabla f(\tilde{w}) = \frac{1}{N} \sum_{i=1}^{N} \nabla f_i(\tilde{w})$. This is the computationally intensive step, performed only once per epoch. c. Inner Loop (Stochastic Updates): Initialize the inner loop parameters $w_0^{(s)} = \tilde{w}$. Then, for $t = 0, 1, ..., m-1$: i. Sample: Randomly pick an index $i_t$ from $\{1, ..., N\}$ (or a mini-batch). ii. Compute Stochastic Gradients: Calculate two stochastic gradients using the same sample $i_t$: one at the current iterate $w_t^{(s)}$ and one at the snapshot $\tilde{w}$. * $\nabla f_{i_t}(w_t^{(s)})$ * $\nabla f_{i_t}(\tilde{w})$ iii. Construct Variance-Reduced Gradient: Form the SVRG gradient estimate $v_t^{(s)}$: $v_t^{(s)} = \nabla f_{i_t}(w_t^{(s)}) - \nabla f_{i_t}(\tilde{w}) + \nabla f(\tilde{w})$ iv. Update Parameters: Update the parameters using a learning rate $\eta$: $w_{t+1}^{(s)} = w_t^{(s)} - \eta v_t^{(s)}$ d. Epoch Update: Set the starting point for the next epoch, for instance, $w_0 = w_m^{(s)}$. Alternatively, one could use the average of the iterates from the inner loop.

Flow diagram illustrating the structure of the SVRG algorithm. The outer loop periodically calculates a full gradient, which is then used within the inner loop to correct stochastic gradient estimates for parameter updates.

Why Does SVRG Work?

The magic lies in the construction of the gradient estimate $v_t^{(s)}$. Let's analyze its properties:

• Unbiased Estimate: Taking the expectation over the choice of $i_t$, we see that $v_t^{(s)}$ is an unbiased estimator of the true gradient at $w_t^{(s)}$:

  $$E_{i_t}[v_t^{(s)}] = E_{i_t}[\nabla f_{i_t}(w_t^{(s)})] - E_{i_t}[\nabla f_{i_t}(\tilde{w})] + \nabla f(\tilde{w})$$

  Since $E_{i_t}[\nabla f_{i_t}(w)] = \nabla f(w)$, this simplifies to:

  $$E_{i_t}[v_t^{(s)}] = \nabla f(w_t^{(s)}) - \nabla f(\tilde{w}) + \nabla f(\tilde{w}) = \nabla f(w_t^{(s)})$$

  So, on average, the SVRG update moves in the direction of the true gradient, just like SGD or full batch gradient descent.

• Variance Reduction: The variance of $v_t^{(s)}$ is what makes SVRG powerful. Consider the term $\nabla f_{i_t}(w_t^{(s)}) - \nabla f_{i_t}(\tilde{w})$. As the iterates $w_t^{(s)}$ within an epoch converge towards the snapshot parameter $\tilde{w}$, this difference term gets smaller. Since $\nabla f(\tilde{w})$ is a constant within the inner loop, the variance of $v_t^{(s)}$ depends primarily on the variance of $\nabla f_{i_t}(w_t^{(s)}) - \nabla f_{i_t}(\tilde{w})$. As $w_t^{(s)} \to \tilde{w}$, this variance tends towards zero. This contrasts sharply with standard SGD, where the variance $Var[\nabla f_{i_t}(w_t)]$ remains roughly constant even near the minimum.

This variance reduction allows SVRG to take more aggressive steps (larger constant learning rates) and converge much faster than SGD, especially when high accuracy is desired.

SVRG vs. SGD and SAG

• SVRG vs. SGD: SVRG requires periodic full gradient calculations, which adds computational overhead compared to SGD. However, its significantly reduced variance often leads to much faster convergence in terms of the number of effective passes over the data, potentially requiring fewer overall computations to reach a target accuracy. SGD typically needs a diminishing learning rate, while SVRG can often use a constant learning rate.
• SVRG vs. SAG: Both SVRG and SAG offer faster convergence than SGD by reducing variance. SAG achieves this by storing and averaging past gradients for each data point, requiring $O(Nd)$ memory (where $d$ is the parameter dimension). SVRG avoids this memory cost by recomputing the full gradient periodically, making it more suitable when $N$ is extremely large. The computational trade-off is between SAG's per-iteration memory access/update cost and SVRG's periodic full gradient computation.

Plot comparing the convergence behavior of SVRG and SGD. SVRG often exhibits linear convergence (a straight line on a log-linear plot) due to variance reduction, while SGD shows sublinear convergence and may plateau at a higher error level.

Implementation Considerations

• Inner Loop Length ($m$): This is a critical parameter. It determines how many stochastic updates are performed for each full gradient calculation. Theoretically, $m$ should be large enough to offset the cost of the full gradient computation. Common choices relate $m$ to the dataset size $N$, such as $m=2N$ or $m=5N$. If $m$ is too small, the overhead of the full gradient dominates. If $m$ is too large, the snapshot $\tilde{w}$ might become too stale relative to the inner loop iterates $w_t^{(s)}$, potentially hindering convergence.
• Learning Rate ($\eta$): A significant advantage of SVRG is that it often works well with a constant learning rate, unlike SGD which requires careful tuning of a decaying schedule. The appropriate constant rate depends on properties of the objective function (like smoothness and strong convexity).
• Snapshot Update Strategy: While setting the next epoch's snapshot $\tilde{w}$ to the final iterate $w_m^{(s)}$ of the inner loop is common, another option is to use the average of the inner loop iterates $\frac{1}{m} \sum_{t=0}^{m-1} w_t^{(s)}$. This averaging can sometimes provide more stable performance.
• Mini-batch SVRG: The description above uses single data points $i_t$. In practice, SVRG is almost always implemented using mini-batches for efficiency, similar to standard SGD. The principles remain the same: compute the mini-batch gradient at $w_t^{(s)}$, compute the mini-batch gradient at $\tilde{w}$ using the same mini-batch, and use the pre-computed full gradient $\nabla f(\tilde{w})$ for the correction term.

Convergence and Applicability

For strongly convex and smooth objective functions, SVRG has been shown to achieve a linear convergence rate ($O(\rho^k)$ for some $\rho < 1$), meaning the error decreases exponentially with the number of epochs. This is a substantial improvement over the sublinear rate ($O(1/k)$) of standard SGD. While theoretical guarantees are often derived for convex problems, SVRG has also proven effective empirically for training deep neural networks, although the analysis in non-convex settings is more complex.

In summary, SVRG offers a compelling method for large-scale optimization. By periodically computing a full gradient and using it to correct noisy stochastic estimates, it achieves rapid convergence without the memory burden of methods like SAG, making it a valuable tool for training models on massive datasets. The primary trade-off is the computational cost of the periodic full gradient calculation, which must be balanced against the faster convergence achieved during the inner loop updates.