(Stochastic) variance reduction is an algorithmic approach to minimizing functions that can be decomposed into finite sums. By exploiting the finite sum structure, variance reduction techniques are able to achieve convergence rates that are impossible to achieve with methods that treat the objective as an infinite sum, as in the classical Stochastic approximation setting.
Variance reduction approaches are widely used for training machine learning models such as logistic regression and support vector machines as these problems have finite-sum structure and uniform conditioning that make them ideal candidates for variance reduction.
Finite sum objectives
A function is considered to have finite sum structure if it can be decomposed into a summation or average:
where the function value and derivative of each can be queried independently. Although variance reduction methods can be applied for any positive and any structure, their favorable theoretical and practical properties arise when is large compared to the condition number of each , and when the have similar (but not necessarily identical) Lipschitz smoothness and strong convexity constants.
The finite sum structure should be contrasted with the stochastic approximation setting which deals with functions of the form which is the expected value of a function depending on a random variable . Any finite sum problem can be optimized using a stochastic approximation algorithm by using .
Rapid Convergence
Stochastic variance reduced methods without acceleration are able to find a minima of within accuracy , i.e. in a number of steps of the order:
The number of steps depends only logarithmically on the level of accuracy required, in contrast to the stochastic approximation framework, where the number of steps required grows proportionally to the accuracy required. Stochastic variance reduction methods converge almost as fast as the gradient descent method's rate, despite using only a stochastic gradient, at a lower cost than gradient descent.
Accelerated methods in the stochastic variance reduction framework achieve even faster convergence rates, requiring only
steps to reach accuracy, potentially faster than non-accelerated methods. Lower complexity bounds. for the finite sum class establish that this rate is the fastest possible for smooth strongly convex problems.
Approaches
Variance reduction approaches fall within 3 main categories: table averaging methods, full-gradient snapshot methods and dual methods. Each category contains methods designed for dealing with convex, non-smooth, and non-convex problems, each differing in hyper-parameter settings and other algorithmic details.
SAGA
In the SAGA method, the prototypical table averaging approach, a table of size is maintained that contains the last gradient witnessed for each term, which we denote . At each step, an index is sampled, and a new gradient is computed. The iterate is updated with:
and afterwards table entry is updated with .
SAGA is among the most popular of the variance reduction methods due to its simplicity, easily adaptable theory, and excellent performance. It is the successor of the SAG method, improving on its flexibility and performance.
SVRG
The stochastic variance reduced gradient method (SVRG), the prototypical snapshot method, uses a similar update except instead of using the average of a table it instead uses a full-gradient that is reevaluated at a snapshot point at regular intervals of iterations. The update becomes:
This approach requires two stochastic gradient evaluations per step, one to compute and one to compute where-as table averaging approaches need only one.
Despite the high computational cost, SVRG is popular as its simple convergence theory is highly adaptable to new optimization settings. It also has lower storage requirements than tabular averaging approaches, which make it applicable in many settings where tabular methods can not be used.
SDCA
Exploiting the dual representation of the objective leads to another variance reduction approach that is particularly suited to finite-sums where each term has a structure that makes computing the convex conjugate or its proximal operator tractable. The standard SDCA method considers finite sums that have additional structure compared to generic finite sum setting:
where each is 1 dimensional and each is a data point associated with . SDCA solves the dual problem: