Can random proximal coordinate descent be accelerated on nonseparable convex composite minimization problems?
(2023) 2023 European Control Conference (ECC) — Location: Bucharest, Romania (13.June.2023)
Files
Can_random_proximal_coordinate_descent_be_accelerated_on_nonseparable_convex_composite_minimization_problems.pdf
Open Access - Adobe PDF
- 565.2 KB
Details
- Authors
- Abstract
- In this paper we consider convex composite optimization problems, where first term is smooth, while the second term is proximal easy but nonseparable (possibly non-smooth). For this problem we adapt the accelerated proximal coordinate descent algorithm from [7], initially developed for convex composite problems having the second term separable. We study convergence to a coordinate-wise minimizer point, and derive convergence rate in expected function values of order O((C+(E[S#k])+)/k2). The first term, C, coincides with the usual constant appearing in the rate of accelerated gradient type methods, while the second one, S#k, measures the nonseparability of the second term in the objective along the iterates. We conjecture that the second term, S#k, is bounded as this is what we observe in all our numerical simulations and that coordinate descent can be accelerated.
- Affiliations
Citations
Chorobura, F., Glineur, F., & Necoara, I. (2023). Can random proximal coordinate descent be accelerated on nonseparable convex composite minimization problems? 2023 European Control Conference (ECC). Published. 2023 European Control Conference (ECC), Bucharest, Romania. https://doi.org/10.23919/ecc57647.2023.10178217