A stochastic Forward-Backward algorithm. Application to regularized optimization over large unstructured graphs

This presentation is in two parts. The first part is devoted to the dynamical behavior of a Forward-Backward algorithm involving two random maximal monotone operators. As is well-known, maximal monotone operators  generalize the subdifferentials of convex lower semicontinuous functions. Thus, the studied algorithm is a general version of the proximal gradient algorithm in the case where both functions are random. 
In the second part, a regularized optimization problem on a large unstructured graph is taken as an application. In this context, the case where the proximal gradient algorithm is implementable only when the graph is reduced to a simple path is considered. The studied algorithm consists in properly selecting random simple paths within the large graph at hand, and in performing the proximal gradient algorithm over these simple paths. The convergence of such an algorithm towards an optimal
solution is established. 
This is a  joint work with Pascal Bianchi and Adil Salim (Telecom ParisTech)