Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

Abstract

We develop a parallel framework that assembles static gradient methods to achieve better adaptivity. A static gradient method, denoted by $\mathrm{GD}(x_0,T)$, takes as input an initial point $x_0\in {\mathbb{R}}^n$ and $T\in {\mathbb{R}}^{+}$ specifying the number $\floor{T}$ of iterations. The step size is chosen as $s=S(T)$, where $S(\cdot )$ is a predetermined function of $T$. The method then performs the iterations $x_{i+1}=x_i-\frac{\hat{I}}{\cdot }s\cdot g_i,$ where $g_i$ is a stochastic gradient evaluated at $x_i$, and $\hat{I}\cdot$ is a scaling factor. For an integer $p\ge 1$, the $p$ processors in the proposed parallel framework search for an appropriate value of $T$ according to a geometric sequence so that the resulting gradient descent satisfies the desired convergence conditions. Each processor executes an infinite sequence of stages indexed by $i=1,2,\dots$. At stage $i$, processor $j$ is assigned $T_{j,i}=h(j,i),$ where $h:\mathbb{N}\times \mathbb{N}\to {\mathbb{R}}^{+}$ is a prescribed function. Processor $j$ $(j=0,1,\dots ,p-1)$ executes $\mathrm{GD}(x_0,T_{j,i})$ at stage $i$.