  Many clustering applications in machine learning and data mining rely on
solving metric-constrained optimization problems. These problems are
characterized by $O(n^3)$ constraints that enforce triangle inequalities on
distance variables associated with $n$ objects in a large dataset. Despite its
usefulness, metric-constrained optimization is challenging in practice due to
the cubic number of constraints and the high-memory requirements of standard
optimization software. Recent work has shown that iterative projection methods
are able to solve metric-constrained optimization problems on a much larger
scale than was previously possible, thanks to their comparatively low memory
requirement. However, the major limitation of projection methods is their slow
convergence rate. In this paper we present a parallel projection method for
metric-constrained optimization which allows us to speed up the convergence
rate in practice. The key to our approach is a new parallel execution schedule
that allows us to perform projections at multiple metric constraints
simultaneously without any conflicts or locking of variables. We illustrate the
effectiveness of this execution schedule by implementing and testing a parallel
projection method for solving the metric-constrained linear programming
relaxation of correlation clustering. We show numerous experimental results on
problems involving up to 2.9 trillion constraints.
