Asynchronous parallel implementations for stochastic optimization have
received huge successes in theory and practice recently. Asynchronous
implementations with lock-free are more efficient than the one with writing or
reading lock. In this paper, we focus on a composite objective function
consisting of a smooth convex function $f$ and a block separable convex
function, which widely exists in machine learning and computer vision. We
propose an asynchronous stochastic block coordinate descent algorithm with the
accelerated technology of variance reduction (AsySBCDVR), which are with
lock-free in the implementation and analysis. AsySBCDVR is particularly
important because it can scale well with the sample size and dimension
simultaneously. We prove that AsySBCDVR achieves a linear convergence rate when
the function $f$ is with the optimal strong convexity property, and a sublinear
rate when $f$ is with the general convexity. More importantly, a near-linear
speedup on a parallel system with shared memory can be obtained.

本研究论文提出了一种异步随机块坐标下降算法，通过方差约减的加速技术来处理由平滑函数和块可分离凸函数构成的复合目标函数，具有较高的效率和可扩展性。