KAUST Research Workshop on Optimization and Big Data
Olivier Fercoq is a Lecturer at Télécom ParisTech. He obtained a MSc from Paris 6 in optimisation and from Ensta ParisTech in engineering. During his PhD studies in École Polytechnique, he worked on optimisation problems related to web page ranking and chemotherapy. He spent two years at the University of Edinburgh, where he specialised to coordinate descent methods. He joined Télécom ParisTech en 2014. His current research interests are primal-dual methods, coordinate descent methods, restarting strategies and applications to machine learning.
We introduce a randomized coordinate descent version of the Vu-Condat algorithm. By coordinate descent, we mean that only a subset of the coordinates of the primal and dual iterates is updated at each iteration, the other coordinates being maintained to their past value. Our method allows us to solve optimization problems with a combination of differentiable functions, constraints as well as non-separable and non-differentiable regularizers.
We show that the sequences generated by our algorithm almost surely converge to a saddle point of the problem at stake, for a wider range of parameter values than previous methods. In particular, the condition on the step-sizes depends on the coordinate-wise Lipschitz constant of the differentiable function's gradient, which is a major feature allowing classical coordinate descent to perform so well when it is applicable.
We then prove a sublinear rate of convergence in general and a linear rate of convergence if the objective enjoys strong convexity properties.
We illustrate the performances of the algorithm on a total-variation regularized least squares regression problem, support vector machine problems and distributed optimization.