2023/03/14 by Rahul Mazumder, Haoyue Wang, Mazumder, Rahul +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2303.07642
openalex publication_date 2023/03/14 · openalex created_date 2023/03/16 · openalex updated_date 2026/07/28
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.