A Cyclic Coordinate Descent Method for Convex Optimization on Polytopes

arXiv2303.07642MaRDI QIDQ6429463FDOQ6429463

Publication date: 14 March 2023

Abstract: Coordinate descent algorithms are popular for huge-scale optimization problems due to their low cost per-iteration. Coordinate descent methods apply to problems where the constraint set is separable across coordinates. In this paper, we propose a new variant of the cyclic coordinate descent method that can handle polyhedral constraints provided that the polyhedral set does not have too many extreme points such as L1-ball and the standard simplex. Loosely speaking, our proposed algorithm PolyCD, can be viewed as a hybrid of cyclic coordinate descent and the Frank-Wolfe algorithms. We prove that PolyCD has a O(1/k) convergence rate for smooth convex objectives. Inspired by the away-step variant of Frank-Wolfe, we propose PolyCDwA, a variant of PolyCD with away steps which has a linear convergence rate when the loss function is smooth and strongly convex. Empirical studies demonstrate that PolyCDwA achieves strong computational performance for large-scale benchmark problems including L1-constrained linear regression, L1-constrained logistic regression and kernel density estimation.

This page was built for publication: A Cyclic Coordinate Descent Method for Convex Optimization on Polytopes

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