Given a set of distances amongst points, determining what metric representation is most "consistent" with the input distances or the metric that best captures the relevant geometric features of the data is a key step in many machine learning algorithms. In this paper, we focus on metric constrained problems, a class of optimization problems with metric constraints. In particular, we identify three types of metric constrained problems: metric nearness (Brickell et al. (2008)), weighted correlation clustering on general graphs (Bansal et al. (2004)), and metric learning (Bellet et al. (2013); Davis et al. (2007)). Because of the large number of constraints in these problems, however, these and other researchers have been forced to restrict either the kinds of metrics learned or the size of the problem that can be solved. We provide an algorithm, PROJECT AND FORGET, that uses Bregman projections with cutting planes, to solve metric constrained problems with many (possibly exponentially) inequality constraints. We also prove that our algorithm converges to the global optimal solution. Additionally, we show that the optimality error (L 2 distance of the current iterate to the optimal) asymptotically decays at an exponential rate. We show that using our method we can solve large problem instances of three types of metric constrained problems, out-performing all state of the art methods with respect to CPU times and problem sizes.
The paper presents an algorithm for optimizing an function f under the constraints that the square matrix variable x represents "metric". In this context, this means that we have also observed a graph G with n vertices, and x is of size n by n, x(i, j) < x(i, e) + x(e, j) if i ~ e and j ~ e are adjacent: this is a generalized for of triangle inequality.
Authors argue that the constraint "x is a metric" translate into exponentially many linear constraints, which results in to a hard to solve problem
The algorithm they propose to tackle this (Algorithm 1) has two subroutines that are shown in Algorithm 2 (Forget and Project). The Project subroutine itself is a projection onto a convex set according to a Bregman divergence, which is not trivial. In this paper I understand that authors only consider metrics of type x' L x where L = C'C >0 is psd
 
Authors claim that the sequence created by their algorithm asymptotically converges to the global optimum, and show numerical superiority to baselines.
Major remarks:
My general feeling is that the paper overstates its results. The paper has some good contribution, which could be better emphasized.
The algorithm stacks multiple subroutines which are not necessarily very light. I am skeptical about the numerical efficiency of such algorithms.
Theoretical results are stated asymptotically while interpreted in the text as finite steps results: page 5, after Corollary 1., read "The algorithm spends the first few iterations ..." in this case, a theoretical result should support the claim
The algorithm starts at a stationary point of f. This itself can be nontrivial. Can authors discuss this?
Minor remarks:
metric and distance to me mean the same, hence the first sentence of the intro doesn't read easily..
what is \cal A line 5 of Algorithm 1? It seems to be a "list of hyperplanes" according to the previous text, but it is unclear to me how to build it algorithmically 
The notation L is confusing in Algo 1 MetricViolation: wasn't L the matrix defining the metric?
A few typos: l. 12 Algo 1, e = (i, j), 3.2 "global optimum [remove solution]."