Large Margin Classification with the Progressive Hedging Algorithm

Several learning algorithms in classification and structured prediction are formu-lated as large scale optimization problems. We show that a generic iterative refor-mulation and resolving strategy based on the progressive hedging algorithm from stochastic programming results in a highly parallel algorithm when applied to the large margin classification problem with nonlinear kernels. We also underline promising aspects of the available analysis of progressive hedging strategies.