Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems

Ion Necoara () and Olivier Fercoq ()
Additional contact information
Ion Necoara: Automatic Control and Systems Engineering Department, Politehnica University of Bucharest, 060042 Bucharest, Romania; Gheorghe Mihoc–Caius Iacob Institute of Mathematical Statistics and Applied Mathematics of the Romanian Academy, 050711 Bucharest, Romania
Olivier Fercoq: Laboratoire Traitement et Communication de l’Information, Télécom Paris, Institut Polytechnique de Paris, 91120 Palaiseau, France

Mathematics of Operations Research, 2022, vol. 47, issue 4, 2641-2666

Abstract: This paper deals with constrained convex problems, where the objective function is smooth and strongly convex, and the feasible set is described by a large number of closed convex (possibly nonpolyhedral) sets. In order to deal efficiently with the complicated constraints, we consider a dual formulation of this problem. We prove that the corresponding dual function satisfies a quadratic growth property on any sublevel set, provided that the primal objective function is smooth and strongly convex and the feasible set verifies Slater’s condition. We propose (accelerated) random coordinate descent algorithms that use the special composite structure of the dual problem. However, with the existing theory, one can prove only that such methods converge sublinearly. Based on our new quadratic growth property derived for the dual problem, we show that such methods have faster convergence, that is, the dual (accelerated) random coordinate descent algorithms converge linearly. Besides providing a general dual framework for the analysis of random dual coordinate descent schemes, our results resolve an open problem in the literature related to the convergence of the Dykstra algorithm on the best feasibility problem for a collection of convex sets. That is, we establish linear convergence rate for the random Dykstra algorithm when the convex sets just satisfy Slater’s condition and derive also a new accelerated variant for the Dykstra algorithm.

Keywords: Primary: 90C25; 90C15; 65K05; convex problems; nonpolyhedral constraints; dual quadratic growth; random dual coordinate descent; Dykstra-type algorithms; linear convergence (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1222 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:2641-2666

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().