École Nationale Supérieure de
Techniques Avancées

Abstract

When solving composite optimization problems, which are fundamental in machine learning applications, finding the optimal point quickly and its structure are two tasks which call for accelerated first order methods, and identification promoting algorithms. The main part of this internship is dedicated towards exploring numerically the interplay between acceleration and structure identification for first-order methods. We propose a method which benefits from a convergence rate matching the accelerated first order method, and which is empirically more stable in terms of structure identification. The second part of this project is turned towards the field of multi-stage stochastic programming. With ever more expressive models, the need arises for methods able to tackle large-scale problems on distributed infrastructure, going beyond the celebrated progressive hedging algorithm. We derive incremental randomized versions of the progressive hedging algorithm, and demonstrate numerically their efficiency.