In this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronously and randomly according to an arbitrary probability distribution. We prove that the iterates generated by the algorithm form a stochastic quasi-Fej\'er sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type.
翻译:在本文中,我们研究了为尽量减少复合锥形目标功能而随机制成的区块协调下游算法的趋同特性,其中区块坐标根据任意的概率分布以不同步和随机的方式加以更新。我们证明,由此算法产生的迭代形成一个随机的准Fej\'er序列,因此几乎肯定会与目标函数的最小化相趋同。此外,我们还证明,在成型型的错误约束条件下,预期函数值会达到一般次线性趋同率和预期线性趋同率。