Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes. (2nd January 2022) - Lei, Jinlong; Shanbhag, Uday V.
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.