Can random proximal coordinate descent be accelerated on nonseparable convex composite minimization problems?

Chorobura, Flavia [University Politehnica Bucharest, Bucharest, Romania] Glineur, François [UCL] Necoara, Ion [University Politehnica Bucharest, Romania]

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.