Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes. (2nd January 2022)

• Record Type: Journal Article
• Authors: Lei, Jinlong; Shanbhag, Uday V.
• Is Part Of: Optimization methods and software. Volume 37:Number 1(2022)
• Page Start: 264
• Page End: 294
• Publication Date: 2022-01-02
• Subjects: Asynchronous variance-reduced scheme -- non-smooth non-convex stochastic optimization -- stochastic gradient methods -- rate and complexity -- limited block coordination; 90C15 -- 90C26; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1746963
• Languages: English
• ISSNs: 1055-6788

Abstract

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.