Stochastic variance reduction

A function $f$ is considered to have finite sum structure if it can be decomposed into a summation or average:

:$f(x)\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^n\; f\_i(x),$

where the function value and derivative of each $f\_i$ can be queried independently. Although variance reduction methods can be applied for any positive $n$ and any $f\_i$ structure, their favorable theoretical and practical properties arise when $n$ is large compared to the condition number of each $f\_i$, and when the $f\_i$ 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 $f(\backslash theta)\; =\; \backslash operatorname\; E\_\{\backslash xi\}\; [F(\backslash theta,\backslash xi)]$

which is the expected value of a function depending on a random variable $\backslash xi$. Any finite sum problem can be optimized using a stochastic approximation algorithm by using $F(\backslash cdot,\backslash xi)=f\_\backslash xi$.

Stochastic variance reduced methods without acceleration are able to find a minima of $f$ within accuracy $\backslash epsilon>$, i.e. $f(x)-f(x\_*)\backslash leq\; \backslash epsilon$ in a number of steps of the order:

:$$

O \left( \left( \frac{L}{\mu} + n \right)\log \left( \frac{1}{\epsilon} \right)\right).

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 $$

O\bigl( L/(\mu \epsilon)\bigr) required grows proportionally to the accuracy required.

Stochastic variance reduction methods converge almost as fast as the gradient descent method's $O\backslash bigl(\; (L/\backslash mu)\backslash log(1/\backslash epsilon)\; \backslash bigr)$ rate, despite using only a stochastic gradient, at a $1/n$ lower cost than gradient descent.

Accelerated methods in the stochastic variance reduction framework achieve even faster convergence rates, requiring only

:$$

O \left( \left( \sqrt{\frac{nL}{\mu}} + n \right)\log \left( \frac{1}{\epsilon} \right)\right)

steps to reach $\backslash epsilon$ accuracy, potentially $\backslash sqrt\{n\}$ faster than non-accelerated methods. Lower complexity bounds.{{cite journal |last1=Lan |first1=Guanghui |last2=Zhou |first2=Yi |date=2018 |title=An optimal randomized incremental gradient method |journal=Mathematical Programming: Series A and B |volume=171 |issue=1–2 |pages=167–215|doi=10.1007/s10107-017-1173-0 |arxiv=1507.02000 |s2cid=9143586 }} for the finite sum class establish that this rate is the fastest possible for smooth strongly convex problems.

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.

In the SAGA method,{{cite journal |last1=Defazio |first1=Aaron |last2=Bach |first2=Francis |last3=Lacoste-Julien |first3=Simon |date=2014 |title=SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives |journal=Neural Information Processing Systems|arxiv=1407.0202 }} the prototypical table averaging approach, a table of size $n$ is maintained that contains the last gradient witnessed for each $f\_i$ term, which we denote $g\_i$. At each step, an index $i$ is sampled, and a new gradient $\backslash nabla\; f\_i(x\_k)$ is computed. The iterate $x\_k$ is updated with:

: $x\_\{k+1\}\; =\; x\_k\; -\; \backslash gamma\; \backslash left[\; \backslash nabla\; f\_i(x\_k)\; -\; g\_i\; +\; \backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^n\; g\_i\; \backslash right],$

and afterwards table entry $i$ is updated with $g\_i=\backslash 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,{{cite journal |last1=Schmidt |first1=Mark |last2=Le Roux |first2=Nicolas |last3=Bach |first3=Francis |date=2017 |title=Minimizing finite sums with the stochastic average gradient |journal=Mathematical Programming |volume=162|arxiv=1309.2388 }} improving on its flexibility and performance.

The stochastic variance reduced gradient method (SVRG),{{cite journal |last1=Johnson |first1=Rie |last2=Zhang |first2=Tong |date=2013 |title=Accelerating Stochastic Gradient Descent using Predictive Variance Reduction |url=https://papers.nips.cc/paper/2013/file/ac1dd209cbcc5e5d1c6e28598e8cbbe8-Paper.pdf |journal= Neural Information Processing Systems}} 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 $\backslash tilde\{x\}$ at regular intervals of $m\backslash geq\; n$ iterations. The update becomes:

: $x\_\{k+1\}\; =\; x\_k\; -\; \backslash gamma\; [\backslash nabla\; f\_i(x\_k)\; -\; \backslash nabla\; f\_i(\backslash tilde\{x\})\; +\; \backslash nabla\; f(\backslash tilde\{x\})],$

This approach requires two stochastic gradient evaluations per step, one to compute $\backslash nabla\; f\_i(x\_k)$ and one to compute $\backslash nabla\; f\_i(\backslash 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 $f\_\{i\}^\{*\},$ or its proximal operator tractable. The standard SDCA method{{cite journal |last1= Shalev-Shwartz |first1=Shai |last2=Zhang |first2=Tong |date=2013 |title=Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization |url=https://www.jmlr.org/papers/volume14/shalev-shwartz13a/shalev-shwartz13a.pdf |journal=Journal of Machine Learning Research |volume=14}} considers finite sums that have additional structure compared to generic finite sum setting:

:$f(x)\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^n\; f\_i(x^Tv\_i)\; +\; \backslash frac\{\backslash lambda\}\{2\}\backslash |x\backslash |^2,$

where each $f\_i$ is 1 dimensional and each $v\_i$ is a data point associated with $f\_i$.

SDCA solves the dual problem:

:$$

\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 $\backslash alpha\_i$, leaving all other coordinates the same. An approximate primal solution $x$ can be recovered from the $\backslash alpha$ values:

:$$

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 $\backslash lambda$ is large, but significantly slower than the other approaches when $\backslash lambda$ is small.

Accelerated variance reduction methods are built upon the standard methods above. The earliest approaches make use of proximal operators to accelerate convergence, either approximately or exactly. Direct acceleration approaches have also been developed{{cite journal |last1=Lan |first1=Guanghui |last2=Zhou |first2=Yi |date=2018 |title=An optimal randomized incremental gradient method |journal=Mathematical Programming: Series A and B |volume=171 |issue=1–2 |pages=167–215|doi=10.1007/s10107-017-1173-0 |arxiv=1507.02000 |s2cid=9143586 }}

The catalyst framework{{cite journal |last1=Lin |first1=Hongzhou |last2=Mairal |first2=Julien |last3=Harchaoui |first3=Zaid |date=2016 |title=Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice |journal=Journal of Machine Learning Research |volume=18|arxiv=1712.05654 }} uses any of the standard methods above as an inner optimizer to approximately solve a proximal operator:

:$$

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 $y$:

:$$

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 $f\_i$ terms to yield an accelerated method. The Point-SAGA method{{cite journal |last1=Defazio |first1=Aaron |date=2016 |title=A Simple Practical Accelerated Method for Finite Sums |journal=Neural Information Processing Systems|arxiv=1602.02442 }} replaces the gradient operations in SAGA with proximal operator evaluations, result in a simple, direct acceleration method:

:$$

x_{k+1} = \text{prox}^\gamma_j\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 $g\_j\; =\; \backslash frac\{1\}\{\backslash gamma\}(z\_k\; -\; x\_\{k+1\})$ performed after each step. Here $\backslash text\{prox\}^\backslash gamma\_j$ is defined as the proximal operator for the $j$th term:

:$$

\text{prox}^\gamma_j(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 $x$ to be maintained between steps, and it has the advantage of only having a single tunable parameter $\backslash gamma$. It obtains the optimal accelerated rate of convergence for strongly convex finite-sum minimization without additional log factors.

• Stochastic gradient descent
• Coordinate descent
• Online machine learning
• Proximal operator
• Stochastic optimization
• Stochastic approximation

{{Reflist}}

Category:Stochastic optimization

Category:Gradient methods

Category:Machine learning algorithms

Category:Convex optimization