Stochastic variance reduction

In the SAGA method,[3] the prototypical table averaging approach, a table of size ${\displaystyle n}$ is maintained that contains the last gradient witnessed for each ${\displaystyle f_{i}}$ term, which we denote ${\displaystyle g_{i}}$. At each step, an index ${\displaystyle i}$ is sampled, and a new gradient ${\displaystyle \nabla f_{i}(x_{k})}$ is computed. The iterate ${\displaystyle x_{k}}$ is updated with:

${\displaystyle x_{k+1}=x_{k}-\gamma \left[\nabla f_{i}(x_{k})-g_{i}+{\frac {1}{n}}\sum _{i=1}^{n}g_{i}\right],}$

and afterwards table entry ${\displaystyle i}$ is updated with ${\displaystyle g_{i}=\nabla f_{i}(x_{k})}$.

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,[4] improving on its flexibility and performance.

The stochastic variance reduced gradient method (SVRG),[5] 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 ${\displaystyle {\tilde {x}}}$ at regular intervals of ${\displaystyle m\geq n}$ iterations. The update becomes:

${\displaystyle x_{k+1}=x_{k}-\gamma [\nabla f_{i}(x_{k})-\nabla f_{i}({\tilde {x}})+\nabla f({\tilde {x}})],}$

This approach requires two stochastic gradient evaluations per step, one to compute ${\displaystyle \nabla f_{i}(x_{k})}$ and one to compute ${\displaystyle \nabla f_{i}({\tilde {x}})],}$ 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.

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 ${\displaystyle f_{i}^{*},}$ or its proximal operator tractable. The standard SDCA method[6] considers finite sums that have additional structure compared to generic finite sum setting:

${\displaystyle f(x)={\frac {1}{n}}\sum _{i=1}^{n}f_{i}(x^{T}v_{i})+{\frac {\lambda }{2}}\|x\|^{2},}$

where each ${\displaystyle f_{i}}$ is 1 dimensional and each ${\displaystyle v_{i}}$ is a data point associated with ${\displaystyle f_{i}}$. SDCA solves the dual problem:

${\displaystyle \max _{\alpha \in \mathbb {R} ^{n}}-{\frac {1}{n}}\sum _{i=1}^{n}f_{i}^{*}(-\alpha _{i})-{\frac {\lambda }{2}}\left\|{\frac {1}{\lambda n}}\sum _{i=1}^{n}\alpha _{i}v_{i}\right\|^{2},}$

by a stochastic coordinate ascent procedure, where at each step the objective is optimized with respect to a randomly chosen coordinate ${\displaystyle \alpha _{i}}$, leaving all other coordinates the same. An approximate primal solution ${\displaystyle x}$ can be recovered from the ${\displaystyle \alpha }$ values:

${\displaystyle x={\frac {1}{\lambda n}}\sum _{i=1}^{n}\alpha _{i}v_{i}}$.

This method obtains similar theoretical rates of convergence to other stochastic variance reduced methods, while avoiding the need to specify a step-size parameter. It is fast in practice when ${\displaystyle \lambda }$ is large, but significantly slower than the other approaches when ${\displaystyle \lambda }$ is small.

The catalyst framework[8] uses any of the standard methods above as an inner optimizer to approximately solve a proximal operator:

${\displaystyle x_{k}\approx {\text{argmin}}_{x}\left\{f(x)+{\frac {\kappa }{2}}\|x-y_{k-1}\|^{2}\right\}}$

after which it uses an extrapolation step to determine the next ${\displaystyle y}$:

${\displaystyle y_{k}=x_{k}+\beta _{k}(x_{k}-x_{k-1})}$

The catalyst method's flexibility and simplicity make it a popular baseline approach. It doesn't achieve the optimal rate of convergence among accelerated methods, it is potentially slower by up to a log factor in the hyper-parameters.

Proximal operations may also be applied directly to the ${\displaystyle f_{i}}$ terms to yield an accelerated method. The Point-SAGA method[9] replaces the gradient operations in SAGA with proximal operator evaluations, result in a simple, direct acceleration method:

${\displaystyle x_{k+1}={\text{prox}}_{j}^{\gamma }\left(z_{k}\triangleq x_{k}+\gamma \left[g_{j}-{\frac {1}{n}}\sum _{i=1}^{n}g_{i}\right]\right),}$

with the table update ${\displaystyle g_{j}={\frac {1}{\gamma }}(z_{k}-x_{k+1})}$ performed after each step. Here ${\displaystyle {\text{prox}}_{j}^{\gamma }}$ is defined as the proximal operator for the ${\displaystyle j}$th term:

${\displaystyle {\text{prox}}_{j}^{\gamma }(y)={\text{argmin}}_{x}\left\{f_{j}(x)+{\frac {1}{2\gamma }}\|x-y\|^{2}\right\}.}$

Unlike other known accelerated methods, Point-SAGA requires only a single iterate sequence ${\displaystyle x}$ to be maintained between steps, and it has the advantage of only having a single tunable parameter ${\displaystyle \gamma }$. It obtains the optimal accelerated rate of convergence for strongly convex finite-sum minimization without additional log factors.