  Progressive Hedging is a popular decomposition algorithm for solving
multi-stage stochastic optimization problems. A computational bottleneck of
this algorithm is that all scenario subproblems have to be solved at each
iteration. In this paper, we introduce randomized versions of the Progressive
Hedging algorithm able to produce new iterates as soon as a single scenario
subproblem is solved. Building on the relation between Progressive Hedging and
monotone operators, we leverage recent results on randomized fixed point
methods to derive and analyze the proposed methods. Finally, we release the
corresponding code as an easy-to-use Julia toolbox and report computational
experiments showing the practical interest of randomized algorithms, notably in
a parallel context. Throughout the paper, we pay a special attention to
presentation, stressing main ideas, avoiding extra-technicalities, in order to
make the randomized methods accessible to a broad audience in the Operations
Research community.
