# Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes

arXiv: https://arxiv.org/abs/1808.02543 · HTML: https://mlsanity.com/paper/1808.02543/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2018.

## Built on by (most cited first, 3 of 3)

- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2608.05460/) (2026)

## Abstract (arXiv)

We consider the minimization of a sum of an expectation-valued coordinate-wise Li-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 that is in accordance with its block-specific Lipschitz constant while block-specific batch-sizes are random variables updated at a rate that grows either at a geometric or polynomial rate with the (random) number of times that block is selected. We show that every limit point for almost every sample path 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-Lojasiewicz (PL) condition with the batch size increasing at a geometric rate, we prove that the suboptimality diminishes at a em geometric rate, the em optimal deterministic rate while iteration and oracle complexity to obtain an ε-optimal solution are proven to be O( (Lrm max/μ) ln(1/ε)) and Oleft((Lrm ave/μ) (1/ε)1+c right) with c≥ 0, respectively. In pursuit of less aggressive sampling rates, when the batch sizes increase at a polynomial rate of degree v ≥ 1, suboptimality decays at a corresponding polynomial rate while the iteration and oracle complexity to obtain an ε-optimal solution are provably O ( v(1/ε)1/v) and O left(ev v2v+1(1/ε)1+1/vright), respectively.