Distributed Optimization for Non-Strongly Convex Regularizers
Simone Forte · Repository for Publications and Research Data (ETH Zurich) · 2015
We develop primal-dual algorithms for distributed training of linear models in the Spark framework.We present the ProxCoCoA+ method which represents a generalization of the CoCoA+ algorithm and extends it to the case of general strongly convex regularizers.A primal-dual convergence rate analysis is provided along with an experimental evaluation of the algorithm on the problem of elastic net regularized logistic regression.We also develop the PrimalCoCoA+ method, a method that allows certain non-strongly convex regularizers to be trained in the ProxCoCoA+ theoretical framework; the algorithm works under the assumption that this regularizers are linearly separable and box constrained.This allows for primal-dual convergence rates for L 1 regularized models, which are, to the best of our knowledge, the first of their kind; we also evaluate the practical efficiency of this method in the case of L 1 regularized logistic on two real world datasets.Finally, we experimentally explore and prove the validity of ProxCo-CoA+ Wild and PrimalCoCoA+ Wild, two new optimization methods that combine distributed and parallel optimization techniques and achieve significant speed-ups with respect to their non-wild variants.