A Fully Stochastic Primal-Dual Algorithm
This work addresses optimization under stochastic constraints for researchers in machine learning and operations research, but it appears incremental as it builds on existing stochastic Forward Backward algorithm results.
The authors tackled the problem of composite optimization with functions given as unknown statistical expectations by proposing a new stochastic primal-dual algorithm, which they proved converges to a saddle point of the Lagrangian function.
A new stochastic primal--dual algorithm for solving a composite optimization problem is proposed. It is assumed that all the functions/operators that enter the optimization problem are given as statistical expectations. These expectations are unknown but revealed across time through i.i.d. realizations. The proposed algorithm is proven to converge to a saddle point of the Lagrangian function. In the framework of the monotone operator theory, the convergence proof relies on recent results on the stochastic Forward Backward algorithm involving random monotone operators. An example of convex optimization under stochastic linear constraints is considered.