Variance reduced finite sum and adaptive gradient optimization

Fix a dimension d at least 1, an initial point x_1 in R^d, a constant step size eta>0, a denominator constant epsilon>0, and parameters beta_1,beta_2 in [0,1). Set m_0=v_0=0. Given a gradient g_t in R^d at each integer time t>=1, calculate

$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t,v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)(g_t\odot g_t),$

where \odot denotes coordinatewise multiplication. Define the bias-corrected moments

${\widehat{m}}_t=\frac{m_t}{1-{\beta }_1^t},{\widehat{v}}_t=\frac{v_t}{1-{\beta }_2^t},$

and update, coordinatewise,

All operations involving vectors in the update are coordinatewise except the ordinary vector addition in the moment recurrences. Since 1-\beta_j^t>0 for t>=1 and v_t has nonnegative coordinates, every denominator is positive; the procedure is defined at every finite step for every finite gradient sequence.

This item defines the update only. It makes no convergence or regret claim.

The real field used here is complete by The Cauchy-sequence reals have the least-upper-bound property, so the complete-ordered-field hypothesis of Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$ holds.

For $0\le {\beta }_j<1$ and integer $t\ge 1$, Monotonicity of $x\mapsto x^n$ and of $n\mapsto a^n$ gives $0\le {\beta }_j^t<1$, so each bias-correction denominator is positive. For each coordinate, a squared gradient is nonnegative by Squares of nonzero elements are positive (with the zero case equal to zero); induction in the recurrence, using the nonnegative coefficients ${\beta }_2$ and $1-{\beta }_2$ and the product sign rules Sign rules for products and monotonicity of multiplication, Multiplication by zero: $0\cdot a=0$, gives $v_t\ge 0$. Division by the positive bias-correction factor preserves nonnegativity by Inverses of positives are positive, and reciprocation reverses order, so ${\widehat{v}}_t\ge 0$; its square root exists by Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$, and $\sqrt{{\widehat{v}}_t}+ϵ>0$. These facts justify every finite update.

Fix a dimension d at least 1, an initial point x_1 in R^d, a constant step size eta>0, a denominator constant epsilon>0, and parameters beta_1,beta_2 in [0,1). Set m_0=v_0=\widehat v^{\max}_0=0. Given a gradient g_t in R^d at each integer time t>=1, calculate

$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t,v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)(g_t\odot g_t),$

${\widehat{m}}_t=\frac{m_t}{1-{\beta }_1^t},{\widehat{v}}_t=\frac{v_t}{1-{\beta }_2^t},{\widehat{v}}_t^{\max }=\max ({\widehat{v}}_{t-1}^{\max },{\widehat{v}}_t),$

where \odot and max are coordinatewise. Update

coordinatewise. Each coordinate of v_t and \widehat v^{\max}_t is nonnegative, and the denominator is at least epsilon>0, so every finite update is defined.

This carrier defines a bias-corrected AMSGrad variant under the assigned denominator convention. Reddi–Kale–Kumar's Algorithm 2 takes the running maximum of the uncorrected second-moment recurrence and uses that maximum directly in the denominator; it does not apply Adam's second-moment bias correction. The recurrences are not identified here. No AMSGrad convergence theorem is claimed.

For $0\le {\beta }_j<1$ and integer $t\ge 1$, Monotonicity of $x\mapsto x^n$ and of $n\mapsto a^n$ gives $0\le {\beta }_j^t<1$, so each bias-correction denominator is positive. Induction in the second-moment recurrence, Squares of nonzero elements are positive, Sign rules for products and monotonicity of multiplication and Multiplication by zero: $0\cdot a=0$ give $v_t\ge 0$. Division by the positive bias-correction factor preserves nonnegativity by Inverses of positives are positive, and reciprocation reverses order, so ${\widehat{v}}_t\ge 0$ and its square root exists by Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$. The coordinatewise maximum is the maximum of a two-element real set, which exists by Maximum and minimum of a set and Every nonempty finite set of reals has a maximum and a minimum and is nonnegative because it is one of its two nonnegative entries. Thus every denominator is at least $ϵ>0$.

Let U be open in R^d, let x in U, let n>=1, and let f_1,...,f_n:U->R be totally differentiable at x. Put F=n^{-1}sum_{i=1}^n f_i. Then F is totally differentiable at x and

Let d>=1, let C be a nonempty closed convex subset of R^d, and let D=diag(d_1,...,d_d) with every d_j>0. Then DC={Dx:x in C} is nonempty, closed, and convex.

Let n,d>=1, let f_1,...,f_n:R^d->R be continuously differentiable, and set F(x)=n^{-1}sum_i f_i(x), with \nabla F(x)=n^{-1}sum_i\nabla f_i(x) by Gradient of a finite sum is the finite sum of gradients and Finite sums and finite products, by recursion. Given a deterministic initial point x_0 and step size \eta>0, initialize a table \alpha_i^0=\nabla f_i(x_0) and its mean \bar\alpha_0=n^{-1}sum_i\alpha_i^0. At iteration k:

1. Draw I_k uniformly from {1,...,n}, independently of the history \mathcal F_k.
2. Evaluate $g_k=\mathrm{\nabla }{f}_{I_k}(x_k)$ once. Using the old table, form $$v_k=g_k-{\alpha }_{I_k}^k+{\bar{\alpha }}_k,x_{k+1}=x_k-\eta v_k\mathrm{.}$$
3. Replace only the sampled table entry, using the pre-update point: $${\alpha }_{I_k}^{k+1}=g_k,{\alpha }_i^{k+1}={\alpha }_i^k(i\mathrm{\ne }{I}_k),$$ and set $${\bar{\alpha }}_{k+1}={\bar{\alpha }}_k+\frac{1}{n}(g_k-{\alpha }_{I_k}^k)\mathrm{.}$$

The stored state is the current iterate, the component-gradient table, and its running mean. For each fixed history, each coordinate of the correction is a scalar control-variate estimator in Control-variate estimators: take one uniform sample $I$ from $\{1,\dots ,n\}$, integrand $i\mapsto (\mathrm{\nabla }{f}_i(x_k){)}_j$, control $i\mapsto ({\alpha }_i^k{)}_j$, known control mean $({\bar{\alpha }}_k{)}_j$, and coefficient $1$. The conditional claims are proved locally. The conditional-expectation convention inherits The Axiom of Choice from Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates.

Let n,d>=1 and let f_1,...,f_n:R^d->R be continuously differentiable convex functions. Define the finite-sum objective

where the gradient identity follows from Gradient of a finite sum is the finite sum of gradients and the sums use Finite sums and finite products, by recursion. Suppose each component gradient is L-Lipschitz for a common L>0. An SVRG epoch with snapshot \tilde x and inner length m>=1 is:

1. Compute the full gradient \nabla F(\tilde x), set x_0=\tilde x.
2. For t=0,...,m-1, draw I_t uniformly from {1,...,n}, independently of the past, and set $$v_t=\mathrm{\nabla }{f}_{I_t}(x_t)-\mathrm{\nabla }{f}_{I_t}(\tilde{x})+\mathrm{\nabla }F(\tilde{x}),x_{t+1}=x_t-\eta v_t$$ for a selected step size \eta>0.
3. Independently draw J uniformly from {0,...,m-1} and return x_J as the next snapshot.

The displayed procedure evaluates the snapshot component gradient at every inner update rather than caching those values. Coordinatewise at a fixed pre-update history, its correction has the one-sample scalar form of Control-variate estimators: the uniform index is the production draw, the integrand is the current component-gradient coordinate, the control is its snapshot coordinate, the known control mean is the corresponding full snapshot-gradient coordinate, and the coefficient is one; the conditional properties needed here are proved in local results on this page. Conditional-expectation notation inherits the The Axiom of Choice assumption from Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates.

The claim that bounded gradients alone keep every bias-corrected Adam iterate bounded is false, even in one dimension with fixed parameters beta_1=0, beta_2=1/2, eta=1, and epsilon=1/100.

The drift calculation concerns the unprojected Adam update defined in Bias-corrected Adam update on R; no lower-bounded fixed objective or bounded feasible set is assumed. It refutes a blanket bounded-iterate guarantee from bounded gradients alone and makes no claim about Adam on a fixed strongly convex objective.

Let n,d>=1, L>0, and let f_i:R^d->R be continuously differentiable, convex, with L-Lipschitz gradients. Put F=n^{-1}sum_i f_i. For all x,y in R^d,

$\frac{1}{n}{\sum }_{i=1}^n\mathrm{\parallel }\mathrm{\nabla }{f}_i(x)-\mathrm{\nabla }{f}_i(y){\mathrm{\parallel }}_2^2\le 2L(F(x)-F(y)-⟨\mathrm{\nabla }F(y),x-y⟩)\mathrm{.}$

Let $n,d\ge 1$, let $(\mathrm{\Omega },\mathcal{F},({\mathcal{F}}_k{)}_{k\ge 0},P)$ be a discrete filtered probability space, and fix $k$. Let $f_i:{\mathbb{R}}^d\to \mathbb{R}$ be continuously differentiable, let $x:\mathrm{\Omega }\to {\mathbb{R}}^d$ be ${\mathcal{F}}_k$-measurable, and suppose each $g_i=\mathrm{\nabla }{f}_i(x)$ is square-integrable. Define $F=n^{-1}{\sum }_i{f}_i$, $\bar{g}=n^{-1}{\sum }_i{g}_i=\mathrm{\nabla }F(x)$ by Gradient of a finite sum is the finite sum of gradients, and

For an integer $b\ge 1$, draw $I_1,\dots ,I_b$ as mutually independent uniform indices from $\{1,\dots ,n\}$, with the whole index vector independent of ${\mathcal{F}}_k$, and set $G_b=b^{-1}{\sum }_{j=1}^b{g}_{I_j}$. Then

$\mathbb{E}[G_b\mid {\mathcal{F}}_k]=\bar{g},\mathbb{E}[\mathrm{\parallel }{G}_b-\bar{g}{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_k]=\frac{{\sigma }^2(x)}{b}\mathrm{.}$

For sampling without replacement, let $S$ be a uniform subset of $\{1,\dots ,n\}$ of size $b$, independent of ${\mathcal{F}}_k$, and set $G_S=b^{-1}{\sum }_{i\in S}{g}_i$. If $n>1$ and $1\le b\le n$, then

$\mathbb{E}[G_S\mid {\mathcal{F}}_k]=\bar{g},\mathbb{E}[\mathrm{\parallel }{G}_S-\bar{g}{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_k]=\frac{n-b}{b(n-1)}{\sigma }^2(x)\mathrm{.}$

When $n=1$, the without-replacement case requires $b=1$; both estimators equal $\bar{g}$ and both errors are zero.

Let d>=1 and let C be a nonempty closed convex subset of R^d, closed in the standard Euclidean metric topology of ${\mathbb{R}}^n$ as the set of functions $n\to \mathbb{R}$, and $d_1$, $d_2$, $d_{\mathrm{\infty }}$ are metrics on it and convex as in A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points. Use the one-based coordinate labels $z_j:=z(j-1)$ for $1\le j\le d$ for the vectors of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$. Fix x_1 in C, a constant eta>0, and epsilon>0. An admissible input consists of convex losses ell_t:C->R and a subgradient oracle that returns a finite vector g_t in partial ell_t(x_t) at each queried iterate, with subgradient convention Subgradients and the subdifferential of a convex function. On round t, observe ell_t and obtain g_t from this oracle. For j=1,...,d set

$s_{t,j}=\sqrt{{ϵ}^2+{\sum }_{k=1}^t{g}_{k,j}^2},A_t=\mathrm{diag}(s_{t,1},\mathrm{.}\mathrm{.}\mathrm{.},s_{t,d})\mathrm{.}$

For a positive diagonal matrix A, write ||z||A^2=z^TAz. Set x{t+1} to the unique minimizer

$x_{t+1}={\mathrm{argmin}}_{x\in C}\{\eta ⟨g_t,x⟩+\frac{1}{2}\mathrm{\parallel }x-x_t{\mathrm{\parallel }}_{A_t}^2\}\mathrm{.}$

Because epsilon>0, every diagonal entry s_{t,j} is positive. The displayed minimizer exists and is unique by Diagonal AdaGrad subproblem has a unique minimizer ↗, so the procedure is defined at each finite round. This is the proximal update in the diagonal metric A_t; after the coordinate scaling A_t^{1/2}, its subproblem is an ordinary Euclidean proximal problem in the sense of Proximal mapping.

Each nonzero $g_{k,j}$ has positive square by Squares of nonzero elements are positive, and the zero case has square zero by Multiplication by zero: $0\cdot a=0$. Clause 4 of Laws of finite sums and finite products makes its finite sum nonnegative, so ${ϵ}^2+{\sum }_{k=1}^t{g}_{k,j}^2\ge {ϵ}^2>0$. Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$ therefore supplies a nonnegative, nonzero root $s_{t,j}$, hence $s_{t,j}>0$. This verifies the positive diagonal hypothesis used by the subproblem result.

For the SAGA iterates and table in Finite-sum SAGA, with step size $\eta >0$ and a minimizer $x^{\ast }$ of $F=n^{-1}{\sum }_i{f}_i$, write $V_k=\mathrm{\parallel }{x}_k-x^{\ast }{\mathrm{\parallel }}_2^2$, $S_k=n^{-1}{\sum }_{i=1}^n\mathrm{\parallel }{\alpha }_i^k-\mathrm{\nabla }{f}_i(x^{\ast }){\mathrm{\parallel }}_2^2$, and ${\mathcal{L}}_k=V_k+7{\eta }^{2}n{S}_k$.

The contract-required one-step bound $\mathbb{E}[{\mathcal{L}}_{k+1}]\le (1-\mu \eta )\mathbb{E}[{\mathcal{L}}_k]$ need not hold for the prescribed SAGA initialization, even when $\eta \le \min \{1\mathrm{/}(3L),\mu \mathrm{/}(13L^2)\}$. The following finite instance has $n=100$, $L=\mu =1$, $x_0=1$, and $\eta =1\mathrm{/}13$, but ${\mathcal{L}}_1\mathrm{/}{\mathcal{L}}_0=844\mathrm{/}869>12\mathrm{/}13=1-\mu \eta$.

Let f_i:R^d->R be convex and continuously differentiable with L-Lipschitz gradients, set F=n^{-1}sum_i f_i, and let x* satisfy grad F(x*)=0. Conditional on the current iterate x_k and table alpha_i^k, assume an independent uniform index I_k and finite second moments. Put

$S_k=\frac{1}{n}{\sum }_{i=1}^n\mathrm{\parallel }{\alpha }_i^k-\mathrm{\nabla }{f}_i(x^{\ast }){\mathrm{\parallel }}_2^2,{\bar{\alpha }}_k=\frac{1}{n}{\sum }_i{\alpha }_i^k,v_k=\mathrm{\nabla }{f}_{I_k}(x_k)-{\alpha }_{I_k}^k+{\bar{\alpha }}_k\mathrm{.}$

Then

$\mathbb{E}[v_k\mid {\mathcal{F}}_k]=\mathrm{\nabla }F(x_k),\mathbb{E}[\mathrm{\parallel }{v}_k{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_k]\le 6L(F(x_k)-F(x^{\ast }))+6S_k,$

and, for the SAGA table replacement in Finite-sum SAGA,

Let f_i:R^d->R be convex and continuously differentiable with L-Lipschitz gradients, set F=n^{-1}sum_i f_i, and let x* satisfy grad F(x*)=0. Conditional on a filtration \mathcal F_t, suppose x_t and the snapshot \tilde x are measurable, the uniform index I_t is independent of \mathcal F_t, and the relevant second moments are finite. For

one has

$\mathbb{E}[v_t\mid {\mathcal{F}}_t]=\mathrm{\nabla }F(x_t),\mathbb{E}[\mathrm{\parallel }{v}_t{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_t]\le 4L(F(x_t)-F(x^{\ast }))+4L(F(\tilde{x})-F(x^{\ast }))\mathrm{.}$

Let C be a nonempty closed convex subset of R^d, let A=diag(a_1,...,a_d) with every a_j>0, and let eta>0 and x,g in R^d. Then the minimizer set

${\mathrm{argmin}}_{z\in C}\{\eta ⟨g,z⟩+\frac{1}{2}\mathrm{\parallel }z-x{\mathrm{\parallel }}_A^2\}$

contains exactly one point.