Alternating Randomized Block Coordinate Descent

arXiv1805.09185MaRDI QIDQ6302003FDOQ6302003

Authors: Jelena Diakonikolas, Lorenzo Orecchia 

Publication date: 23 May 2018

Abstract: Block-coordinate descent algorithms and alternating minimization methods are fundamental optimization algorithms and an important primitive in large-scale optimization and machine learning. While various block-coordinate-descent-type 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 AR-BCD, whose convergence time scales independently of the least smooth (possibly non-smooth) block. The basic algorithm generalizes both alternating minimization and randomized block coordinate (gradient) descent, and we also provide its accelerated version -- AAR-BCD. As a special case of AAR-BCD, we obtain the first nontrivial accelerated alternating minimization algorithm.

This page was built for publication: Alternating Randomized Block Coordinate Descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6302003)