Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

The paper introduces a parallel architecture for stochastic gradient methods that adaptively selects the number of iterations. An algorithm A(x₀, y) takes an initial point and a step limit y, and p processors search for an appropriate iteration count T using a prescribed function h. The framework guarantees a (p, αₚ)-approximation, meaning for any T ≥ T₀ there exists a processor and stage where the cumulative iterations lie within a factor αₚ of T, and the authors prove tight lower bounds for αₚ while presenting simple arithmetic stochastic gradient methods that use only divisions by powers of two.