Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

Let A(x0,y) be an algorithm with two inputs: an initial point x0 and an integer parameter y, which specifies that A(.,.) executes at most y iterations or steps. Given an integer p≥ 1, p parallel processors search an appropriate value of T for for A(.). Each processor executes an infinite sequence of stages indexed by i=0,1,2,ldots. At stage i, processor j is assigned Tj,i=h(j,i), where h:mathbbN×mathbbNrightarrowℝ+ is a prescribed function. Processor j (j=0,1,ldots,p-1) then executes A(x0,Tj,i). The efficiency of the parallel framework is characterized by its (p,αp)-approximation guarantee. Specifically, for every integer T≥ T0, there exist a processor j and a stage i such that T≤ Tj,i≤ Tj,i^*<αp T, where Tj,i^*=sumt=0iTj,t denotes the cumulative number of iterations executed by processor j from the beginning to stage i. We prove that this framework achieves a (p,αp)-approximation, and a tight lower bound for αp for all large p. We develop arithmetically simple stochastic gradient methods in which every division is of the form x/2t for some integer t, and integrate them into the proposed parallel framework.