SEMINAIRE DU 1 OCTOBRE 2015 – 15H @ LTCI – SALLE C49
Finite identification and local linear convergence of proximal splitting algorithms.
Convex nonsmooth optimization has become ubiquitous in most quantitative disciplines of science. Proximal splitting algorithms are very popular to solve structured convex optimization problems. Within these algorithms, the Forward-Backward and its variants (e.g. inertial FB, FISTA, Tseng’s FBF), Douglas-Rachford and ADMM are widely used. The goal of this work is to investigate the local convergence behavior of these schemes when the involved functions are partly smooth relative to the associated active manifolds. In particular, we show that (i) all the aforementioned splitting algorithms correctly identify the active manifolds in a finite number of iterations (finite activity identification), and (ii) then enter a local linear convergence regime, which we characterize precisely in terms of the structure of the involved active manifolds. For problems involving quadratic and polyhedral functions, we show how to get finite termination of Forward-Backward-type splitting. These results may have numerous applications including in signal/image processing, sparse recovery and machine learning. Indeed, the obtained results explain the typical behaviour that has been observed numerically for many problems in these fields such as the Lasso, the group Lasso, the fused Lasso and the nuclear norm regularization to name only a few.
Jalal Fadili est Professeur de traitement d’images et du signal au ENSICAEN et membre junior de l’Institut Universitaire de France.