Alternating Randomized Block Coordinate Descent
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:12321240, 2018.
Abstract
Blockcoordinate descent algorithms and alternating minimization methods are fundamental optimization algorithms and an important primitive in largescale optimization and machine learning. While various blockcoordinatedescenttype methods have been studied extensively, only alternating minimization – which applies to the setting of only two blocks – is known to have convergence time that scales independently of the least smooth block. A natural question is then: is the setting of two blocks special? We show that the answer is “no” as long as the least smooth block can be optimized exactly – an assumption that is also needed in the setting of alternating minimization. We do so by introducing a novel algorithm ARBCD, whose convergence time scales independently of the least smooth (possibly nonsmooth) block. The basic algorithm generalizes both alternating minimization and randomized block coordinate (gradient) descent, and we also provide its accelerated version – AARBCD.
Related Material


