Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes
Jinlong Lei, Uday V. Shanbhag
Abstract
This work considers the minimization of a sum of an expectation-valued coordinate-wise smooth nonconvex function and a nonsmooth block-separable convex regularizer. We propose an asynchronous variance-reduced algorithm, where in each iteration, a single block is randomly chosen to update its estimates by a proximal variable sample-size stochastic gradient scheme, while the remaining blocks are kept invariant. Notably, each block employs a steplength relying on its block-specific Lipschitz constant while batch-sizes are updated as a function of the number of times that block is selected. We show that every limit point is a stationary point and establish the ergodic non-asymptotic rate O(1/K). Iteration and oracle complexity to obtain an ε-stationary point are shown to be O(1/ϵ) and O(1/ϵ2), respectively. Furthermore, under a proximal Polyak–Łojasiewicz condition with batch sizes increasing at a geometric rate, we prove that the suboptimality diminishes at a geometric rate, the optimal deterministic rate while iteration and oracle complexity to obtain an ε-optimal solution are O(ln(1/ϵ)) and O(1/ϵ)1+c with c≥ 0. In the single block setting, we obtain the optimal oracle complexity O(1/ϵ). Finally, preliminary numerics suggest that the schemes compare well with competitors reliant on global Lipschitz constants.