Mathematical Programming Computation, Volume 6, Number 1, March 2014

Font Size:  Small  Medium  Large

Block splitting for distributed optimization

Neal Parikh, Stephen Boyd

Abstract


This paper describes a general purposemethod for solving convex optimization problems in a distributed computing environment. In particular, if the problem data includes a large linear operator or matrix A, the method allows for handling eachsub-block of A on a separatemachine. The approach works as follows. First, we define a canonical problem form called graph form, in which we have two sets of variables related by a linear operator A, such that the objective function is separable across these two sets of variables. Many types of problems are easily expressed in graph form, including cone programs and a wide variety of regularized loss minimization problems from statistics, like logistic regression, the support vector machine, and the lasso. Next, we describe graph projection splitting, a form of Douglas–Rachford splitting or the alternating direction method of multipliers, to solve graph form problems serially. Finally, we derive a distributed block splitting algorithm based on graph projection splitting. In a statistical or machine learning context, this allows for training models exactly with a huge number of both training examples and features, such that each processor handles only a subset of both. To the best of our knowledge, this is the only general purpose method with this property. We present several numerical experiments in both the serial and distributed settings.


Full Text: pdf

mpc footer
© MPS 2008-2017