Project and Forget: Solving Large Scale Metric Constrained Problems
Authors: Anna C. Gilbert
Rishi Sonthalia
Venue:  (2020)
Keywords: metric constrained problems
metric learning
metric nearness
correlation clustering
Bregman projection
cutting planes
large scale optimization

Abstract: Given a set of distances amongst points, determining what metric representation is most “consistent” with the input distances or the metric that 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, 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 (L2 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.

Under review as a conference paper at ICLR 2019
PROJECT AND FORGET: SOLVING LARGE-SCALE MET- RIC CONSTRAINED PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Given 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 key step in many machine learning algorithms. In this paper, we focus on metric constrained problems, a class optimization problems with metric constraints. In particular, identify three types of metric constrained problems: metric nearness (Brickell et al. (2008), ) weighted correlation clustering general graphs (Bansal al. (2004)). and metric learning (Bellet et al. (2013); 3 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, show that the optimality error (L2 distance of the current iterate to the optimal) asymptotically decays at an exponential rate. We show that using method can solve large problem instances of three types of metric constrained problems, out out-performing all state the methods with respect CPU times and problem sizes.
INTRODUCTION
Given a set distances amongst data points, many machine learning algorithms are considerably "casier" once these distances adhere to metric. Furthermore, learning what metric is most "consistent" with the input distances or the metric that best captures the relevant geometric features of the data (e.g., the correlation structure in the data) is key step in efficient, approximation algorithms for classification, clustering, regression, feature selection, etc. Indyk (1999) provides a list of other computational problems such as nearest neighbor search, (approximate) proximity problems, facility location, and variety of graph problems for which we have efficient approximation algorithms in general metric space. Given the importance of metric representations of data sets, we focus on metric constrained problems, a class of optimization problems with metric constraints; i.c., optimization of a convex function subject metric constraints, such as the triangle inequality, on all the output variables.
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)) Briefly, the metric nearness problem seeks the closest metric to given set of distances, the goal of correlation clustering is to partition nodes in graph according to their similarity, and metric learning finds a metric on a dataset that is consistent with (dis)similarity information about the data points.
All of these problems can be modeled as constrained convex optimization problems with a large number of constraints. Unfortunately, because of the large number of constraints, using standard optimization techniques, researchers have been forced to restrict either the kinds of metrics learned or the size of the problem that can be solved.
Many of the existing methods for metric constrained problems suffer from some sort of significant drawback that hampers performance or restricts the instance size. Gradient based algorithms such as

---

Under review as a conference paper at ICLR 2019
projected gradient descent (e.g.. BBeck & Teboulle 20099;; y Nesterov (1983) Riemannian gradient descent require a projection onto the space of all metrics, which in general, is an intractable problem. One modification of this approach is to subsample the constraints and then project onto the sampled set (see Nedič (2011); Polyak (200T): Wang & Bertsekas) (203)); Wang et al. (2015)). For metric constrained problems, however, we have many more constraints than data points, so the condition numbers of the problems are quite high and these algorithms tend to require a large number of iterations.
Another standard approach is to consider the Lagrangian and maintain a KKT type optimality condition. These methods run into two different kinds of problems. First, computing the gradient becomes an intractable problem for methods that maintain the KKT condition by using Newton's 's method. Examples of such methods include the interior point method and the barrier method. One fix could be to subsample the constraints and only compute those gradients, but this approach runs into the same drawbacks as before. The other option to incrementally update the Lagrangian, looking at one constraint
time. These methods, such as Bauschke & Lewis (2000); [usem| [199I); [uusem & De Pierro 1990), traditionally require us to cycle through all the constraints which is not feasible with metric constraints.
One final approach is to use cutting planes. The performance of this method is very heavily dependent on the cut selection process (see Dey & Molinaro (2018); Poirrie& & Yu (2019) for deep discussions about the cut selection process). The discovery of Gomory cuts and other subsequent work such as branch and bound, has led to the viability of the cutting plane method for solving mixed integer linear programs. This success has, however, not transferred to other problems. In general, if the cuts are not selected appropriately, the algorithm could potentially take an exponential number of iterations; i.e., add an exponential number of constraints. Thus, to use this method, we must show for each problem that the specific cutting plane selection method results in feasible algorithm (see Chandrasekaran et al. (2012) for an example).
In this paper, 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. In fact, the algorithm is general purpose one that can solve large constrained convex optimization problems, not only those arising from metric constraints. We also develop a stochastic version of our algorithm. This version is a similar adaptation of the Bregman method, as Nedic (201T); Polyak (2001): Wang & Bertsekas (2033); Wang et al. (2015) are adaptations of the projected gradient method. This version of our algorithm can be used to solve problems where each data point (or pair, triple of data points) form constraint. The major contributions of our paper is as follows:
1. Using a specific instantiation of the PROJECT AND FORGET algorithm, we solve the weighted correlation clustering problem graph with over 130, 000 nodes. To solve this problem with previous methods, we would need to solve a linear program with over 10 constraints. Furthermore, demonstrate our algorithms superiority by outperforming the current state of the art in terms of CPU times.
2. We use our algorithm to develop a new algorithm that solves the metric nearness problem. We show that our algorithm outperforms the current state of the art with respect to CPU time and can be used to solve the problem for non-complete graphs.
3. We the the stochastic version of our algorithm to develop a new algorithm to solve the information theoretic machine learning problem. We compare this against the standard method and show that in general we require fewer projections to solve the problem. Using our algorithm we can also solve the full version of the convex program presented in Davis et al. (207)) instead of a heuristic approximation. Thus, demonstrating that we can solve larger instances of the problem.
4. Finally, we prove that our algorithm converges to the global optimal solution. Additionally, we show that the optimality error (Ly distance of the current iterate to the optimal) asymp- totically decays at an exponential rate. We also show that because of the FORGET step, when the algorithm terminates, the set of constraints that remain remembered are exactly the active constraints. Thus, our algorithm also finds the set of active constraints.
We present the necessary background material and problem formulations in Section 2 In Section 3 we provide a general form of the PROJECT AND FORGET algorithm and detail its theoretical analysis. We instantiate our algorithm to solve three types of metric constrained problems in Section 4 and
2

---

Under review as a conference paper at ICLR 2019
highlight the empirical performance. Complete proofs and discussion may be found in the sections in the Appendix.
PRELIMINARIES
2.1 METRIC CONSTRAINED PROBLEMS, GENERAL FORMULATION
Metric polytope. To set the stage for our optimization problems, we define the set over which we optimize first. Let MET, C (R) the space all metrics on n points. Given a graph the metric polytope MET(G) is the projection of MET, onto the coordinates given by the edges of G (i.e., consider distances only between pairs of points that are adjacent in G).
have that (E), if and only if G, sree) 2 and for every cycle C in G and Ve E C, we have that sre) S EEecafe x(e). Therefore, MET,, (G) can be described as the intersection of exponentially many half-spaces.
It can be easily seen that for any I R (()),,
Metric constrained problems. Now that we have the set over which we want to optimize, we give general formulation for metric constrained optimization problems: given a strictly convex function f. a graph G, and finite family of salf-space H. {H,} such that H; = {z : (as, x) S b,), we seek the unique point x² E N H; O MET(G) =: C that minimizes f. That is, if we set A to be the matrix whose rows are ag and b be the vector whose coordinates are by we seek
minimize subject to
f(x)
Ax b I IE MEM(GG))
(2.1)
The constraints encoded the matrix let us impose additional constraints beyond that of metric. In this paper, A is used only for correlation clustering.
2.2 SPECIFIC METRIC CONSTRAINED PROBLEMS
Metric nearness. Following Brickell et al. (2088), the metric nearness problem is: given a point
IR (5), find the closest (in some fp norm) point x² MET, x. This problem is form of metric learning; see [rickell et al. (2008) for an application to clustering and see Gilbert & Sonthalia (2088) for an application unsupervised metric learning.
Weighted correlation clustering on graphs. Bansal et (2004) introduced correlation clustering. In this problem, we are given a graph G (V, E') (not necessarily complete) in which each edge has two non-negative numbers wt (e) and w (e) that indicate the level of similarity and dissimilarity partition the nodes into clusters so as to
between its nodes. The goal of correlation clustering
minimize some objective function. The most common objective is Σ Ew+ (e)xx))) + w (e) xx),
cEE
where x, E {0, 1 indicates whether the end points of the edge e belong to different cluster. In general, this variant the problem harhard and many different algorithms have been developed to solve the problem. The best approximation results (with approximation ratios Ollog n) in general, and (1) for specific cases), however, are obtained by rounding the solution to the following relaxed linear problem
minimize subject to
EeEE w (e)xe + w (e)(e) xz)
Fij
Fik + Ikj
=
(2.2)
Jij E [0.1]
i, = 1,
See Charikar et al. (2005): Emanuel Fiat (003)) for details. Many special cases, such when the
weights are +1 and Kn, can be solved with faster algorithms (e.g.. Ailon et al.) (0055). ).
Metric learning. The final metric constrained problem we consider is metric learning. There many different versions of this problem (see Bellet et al. (2013); Suárez Díaz et al. (2018) for two different surveys on the topic) but all of the instantiations have a similar formulation: given data set X and possibly some additional information, learn an appropriate metric on X. Many of the existing methods seek linear map such that the learned metric is given by
do v) V(x (x --))- C(x
3

---

Under review as a conference paper at ICLR 2019
where C' C== L. Our general purpose algorithm directly learn the appropriate metric without resorting to the above specific form, however, this generalization requires more focus than we can give it in this paper. Instead, we focus specific instantiation (that also differs from the above), specifically information theoretic metric learning (ITML), as in Davis et al. (2007). In ITMI,, we consider I." I. the covariance matrix of Gaussian distribution p(æ; C') and we given sets S, D which represent the set of similar and dissimilar points. The problem we solve is:
minimize subject to
[p(e ()]p((;:1) 1)) (
S M
(1)) es (i,))
(2.3)
dz( 2
2.3 BREGMAN PROJECTIONS
All of the above problems can be couched in general terms and, the Appendix 6 general formulation. We seek to optimize rich class of convex functions f. known as Bregman functions, denoted (S). with useful properties for algorithmic and convergence analysis, subject to metric constraints. More details about Bregman functions and the general setting in which our algorithm works can be found in the Appendix sec:generalProblem.. We do, however, detail Bregman projections, a key step in specific algorithms in this section.
we give such a
Definition 1. Given a convex function (*) S - IR whose gradient is defined on all of S, define its generalized Bregman distance D S x S + IR as follows: Dy(x, 3) = f(x) f(y) (V) x-)))
Definition 2. Given a strictly convex function f, a closed convex set C, and point y. the projection of onto C' with respect to D is point x² E dom(f) such that
x²
arg min Dy(x, y). #ECrdom(f)
ALGORITHMS AND ANALYSIS
In this section, we present our algorithm that we will use to solve metric constrained problems and state its convergence behavior. The detailed proofs can all be found in the Appendix g
3.1 THE ALGORITHM
Our method is an iterative one and is presented in Algorithm ! Each iteration consists of three phases. In the first phase, we obtain a list of violated metric constraints L. If we have additional constraints represented in A, A is a list corresponding to these hyperplanes. In the second phase, we merge (()), the list constraints we have been keeping tracking of up to the vth iteration, with L and project onto each of the constraints in the list (()) U L iteratively. Finally, in the third phase, we forget some constraints.
The project and forget steps for algorithm are presented in Algorithm Let us step through the code to understand intuitively its behavior. Let H, = {x (a:, x) < b; be constraint and x the current iterate. The first step to calculate x and Here x= is the projection of onto the boundary of H, and 0 is a "measure" of how far x is from x². However, 0 can be any real number and so we examine two cases: positive or negative.
It can be easily seen that 0 is negative if and only if the constraint is violated. In this case, we have e = 0 because (as we will see in proof) the algorithm always maintains 2; 2 O. Then on line 5, we compute the projection of x onto H, Finally, since we corrected for this constraint, we add |0| to 2;. Since each time we correct for H,, we add to 2;, we see that 2; stores the total corrections made for H,.
On the other hand, 0 is positive, this constraint is satisfied. In this case, if we also have that 2; is positive; i.e., have corrected for H, before, then have over compensated for this constraint and,
In the general formulation of the algorithm in the Appendix 6 this list is obtained by querying separation oracle with one of properties, See the Appendix for detailed discussion.
4

---

Under review as a conference paper at ICLR 2019
Algorithm I General Algorithm.
1:
function F(,AA)
2:
[( 0, (0)) = Initialize (0) so that V/(x(0)) - O.
3:
while Not Converged do
4:
== METRIC VIOLATIONS(2")
[(++1) = U
5:
6:
x(++1) Project(x!!)) [(v+1))
7:
[((+1) Forget Forgen(I ((++))
return
8:
9:
function METRIC VIOLATIONS(d)
10:
L=
11:
Let j) be the weight of shortest path between nodes i and if none exists.
12:
for Edge e = (i,j) E do
if () d(i, then
14:
Let / be the shortest path between and j Add C P ((i.))} L
return
thus, must undo some of the corrections. If c 2i, then we undo all of the corrections and zj is set to O. Otherwise, c = we only undo part of the correction.
The forget step is relatively easy: given constraint H,, check if 2, 0. If 2; 0, then this means we have not done any net corrections for this constraint and we can forget about it; i.c., delete it from ((o)
Algorithm 2 Project and Forget algorithms.
1: function PROJECT(I, 2, L)
2: for H, = {y: (a,, y) = b,} E L do
3: Find x², 0 by solving Vf(x")
()(x) Oa, and x² H
4: Q = min (z, 0)
5:
such that V (2 fzxx c;a;
6:
2, +
return x,
7: function FORGET(2, 2, L.)
8: for H; {x (a;, x) = b,} E do
9: return
2, then Forget H;
In general, calculating the Bregman projection (line 3) cannot be done exactly. See Dhillon & Tropp (2077) for general method to perform the calculation line and for an analytic formula for when is quadratic function.
3.2 CONVERGENCE ANALYSIS
Now that we have specified the algorithm, we establish a few crucial theoretical properties. The first is that algorithm is guaranteed to converge to the global optimum. In fact, also show that asymptotically, our error decreases at an exponential rate. These main theoretical results can be summarized by the following theorem.
Theorem 1. If E B(S), H; are strongly zone consistent with respect to A and 20 e S such that
Vf(x)) = 0, then
1. Then any sequence x² produced by Algorithm Conneergeennnnnees to the optimal solution of problem 2
This technical condition and is discussed Appendix In the of our problems this is true.

---

Under review as a conference paper at ICLR 2019
2. If x² is the optimal solution, f is twice differentiable x², and the Hessian H: := Hf((x* is positive semidefinite, then there exists E (0, 1) such that
| - 2 || S
lim 10000
(3.1)
x - 101111
where 1lvll y² Hy.
Proof. The proof of this theorem has been moved to the supplementary material section.
The proof of Theorem also establishes another important theoretical property.
Proposition ag is inactive constraint, then there exists N, such that for all N, we have that zi" = 0. That is, after some finite time, we never project onto inactive constraints ever again.
Corollary 1. Under the assumptions for part (2) of Theorem we have that the sequence z" - z² also converges.
These properties are important as they permit the following interpretation of our algorithm. The algorithm spends the initial few iterations identifying the active constraints from amongst large number of constraints. The algorithm then spends the remainder of the iterations finding the optimal solution with respect to these constraints. This ability to find the set of active constraints is of the main advantages of our algorithm.
3.3 STOCHASTIC VARIANT
In some problems, we do not optimize over the whole of MET(G) but a subset, as is the case in ITML. In such problems, have constraints defined using subsets of the data points and have many data points, we may have considerably more constraints than we want to examine. For this reason, we present stochastic version of our algorithm that can be used in these cases. Instead of calling METRIC VIOLATION to get a list of metric violated constraints, we randomly sample from our constraints. In this version, at each iteration, we choose a random set of constraint and project onto these constraints and the ones we remember from before, and then forget some constraints. The advantage this has over similar stochastic methods such Wang et al.) (2015) that as we sample constraints, the list (²) keeps track of the important constraints that have seen far. In this case, we have the following convergence result.
may
Theorem 2. If E B(S), H, are strongly zone consistent with respect to f. and 3x E S such that (x))) O, then with probability any sequence x" produced by the stochastic algorithm converges to the optimal solution of problem 2.1 Furthermore, if x² is the optimal solution, f is twice differentiable x", and the Hessian H Hf(x") ) is positive semidefinite, then there exists E (0,1) such that with probability 1,
ox x² || 1 1² S p.
lim
EXPERIMENTS
To demonstrate the effectiveness of our method in solving metric constrained problems, we solve large instances of each of the problem. More details about each of the experiments can be found in the Appendix
4.1 WEIGHTED CORRELATION CLUSTERING ON GENERAL GRAPIIS
4.1.1 DENSE GRAPHS
As the LP formulation for correlation clustering Equation 2.2 has O(n²) constraints, solving the LP for large n becomes infeasible quickly, in terms of both memory and time. Veldt et al. (0019)
Alll implementations and experiments can be found https: /ww. www.eddrooooccoooo com cw..sh////hhccccccccccc

---

Under review as a conference paper at ICLR 2019
showed that for instances with z 4000, standard solvers such as Gurobi out of memory a 100 GB machine. On the other hand. |eeldt et al. (2019) develop a method using which they can feasibly solve the problem for 11000. To solve the problem, they transformation problem 2.2 into 1. some an appropriately defined d, v., W. For general 7, the solution to problem 4.1 approximates the optimal solution to 2.2 However, for large enough ry it has been shown that the two problems are equivalent.
6F + f/1 d/= d) subject to x E (ET(K,))
minimize
(4.1)
This is the version of the LP that we solve with our algorithm. We solve this for four graphs from the Stanford sparse network repository Leskovec & Krev](2014) Following Veldt et al. (2019), we use the method from Wang et al. (2013) to convert these graphs into instances of weighted correlation clustering on complete graph. We compare our method against Ruggles et al. (219). a parallel version of Veldt et al. 2019). in terms of running time, quality of the solutions, and memory usage.
We see from Table I that our algorithm takes less time get better approximation ratio, but requires more memory per iteration. Our algorithm requires more memory because the initial few iterations find a large number of constraints. Later, in the forget step, the algorithm forgets these constraints until the number of constraints stabilizes at a reasonable level. Hence, our initial memory usage is much larger than our later memory usage.
Table I: Comparison with Ruggles et al. 2019). We set = 1 and ran until the maximum violation of a metric constraint was smaller than 0.01. We used parallel version of the algorithm METRIC VIOLATION as our oracle. All of the computations were done on a machine with 16 physical cores and 13 GB of RAM per core. More details about the experiment can be found in the supplementary material section.
Graph
Time (8)
Opt Ratio
Avg. mem. / iter. (GiB)
n
Ours
Ruggles et al.
Ours
Ruggles et al.
Ours
Ruggles et al.
CAGrQc
41588
2098
5577
1.33
1.38
4.4
1.3
Power 4941
1393
6082
1.33
1.37
5.9
2
CAHepTTh 8638
9660
35021
1.33
1.36
24
8
CAHepPh 11204
71071
135568
1.33
1.46
27.5
15
To see how the number of constraints found by the oracle evolves, we plot the number of constraints found by the oracle and the number of constraints after the forget step for the CA-HepTTh graph. This plot can be seen in Fi Figure T also shows us, as expected, the exponential decay of the maximum violation of a metric constraint.
122
Nu sturt conataae cenatarr a ahee the bogal skip
Number of controntss
1655
Vaximum consensint vicltto
5.5
17
1250
15'
1250
77
1250
12
leretions
Figure 1: Left: The number of constraints is on the y axis (log scale) and the number of iterations the x axis. Right: Plot for the maximum violation of a metric constraint (log scale) versus iterations.
7

---

Under review as a conference paper at ICLR 2019
4.1.2 SPARSE GRAPHS
For much real-world data, the graph G larger than our previous experiments but it is also sparse. As stated, the problem (.2) requires O(n") constraints and O(n²) variables. However, in practice, there are very few active constraints, seen in T Proposition tells us that if we optimize over MET(G) instead of MET,, then the quality of the solution is not degraded. With this generalization to (ET(G), the number variables greatly reduced but the number of constraints is increased. Our algorithmic approach, however, can handle this increase in the number of constraints. Thus, we can solve the weighted correlation clustering problem for general graphs G.
Proposition 2. Let π be the projection from MET, to MET(G). Then for any optimal solution x² to the following problem
minimize subject to
Eeer w (c)xe + w (c)(1 Ize)
I I MET(G)
(4.2)
Tiy E [0,
Tij
i,j L,..,
we have that for all & E a (x*),, &t an optimal solution 2.2
Table 2: Results for our algorithm larger graphs. We ran experiment machine with 48 physical cores and 13 GB of RAM per core, but we only used 32 threads for the computations.
Graph
# Constraints
Time
Opt Ratio
# Active Constraints Iters.
Slashdot 82140
5.54
10
46.7 hours
1.78
384227
145
Epinions
131,828
2.29 x 10
121.2 hours
1.77
579926
193
Since the weighting of the edges does not affect the size of the linear program that needs to be solved, we tested our algorithm on signed graphs to get estimate of the running time for the algorithm. We took two graphs from Leskovec & Krevl (2014). These graphs are much bigger instances than our previous experiments and have 82140 nodes and 131,89 132, nodes, respectively. Even if we use the parallel version of Veldt et al. (2019), based on the average time took for a single iteration for the CA-HepPh graph, it would take an estimated two days for single iteration for graph with n R 80, 000. Since most graphs require at least 100 iterations, Veldt et al. (2019): Ruggles et al. (2019) cannot be used to solve problems of this magnitude. Other methods of solving the LP are also not feasible as they run out of memory on much smaller instances.
As see from Table 2 these instances have over 500 trillion constraints, but the number of active constraints is only a tiny fraction of the number of active constraints. Thus, using our approach we solve the weighted correlation clustering problem much larger graphs than ever before and this possible because the graphs are sparse. That is, our oracle finds violated cycle inequalities relatively quickly and, since we forget inactive constraints, project onto only relatively small number of constraints. Thus, each iteration is done relatively quickly. In this experiment, each iteration took 500 3000 seconds.
4.2 METRIC NEARNESS
To do a head to head comparison against the algorithm presented in Brickell et al. (2008). we generated two types of random weighted complete graphs. For type one graphs, for each edge e we set w(e) with probability 0.8 and and w(e) 0 with probability 0.2. For type two graphs, we let w(e) ~ (0, 1). For both types of graphs, we ran both algorithms until the distance between current iterate and its optimal decrease only solution (see Brickell et al. (2008) was smaller than one. The computations were done on a machine with four physical cores with 13 GB of memory per core.
We can see from Figure 2 that as grows, our algorithm outperforms the algorithm from Brickell cet al. (2008). We also see that our algorithm has less variability in its running time. Additionally, since forget constraints, From our experiments, we see that for type one graphs, our algorithm consistently returns n²/2 constraints, and for type two graphs, consistently returns n² constraints.
are interested in the number of active constraints for these problems.
In general. Brickell et al. (2008)* 's algorithm works for = K,, only. For real-world data, we may not have full information about the interactions between data points; such relations may be
8

---

Under review as a conference paper at ICLR 2019
120
Cor sggtti
1000
Time in ancorrds
830
3000
030
2000
230
1200
Numbor of nodes
Numbe of tnahes
Figure 2: The red line the mean running time over 5 samples for the algorithm from Brickell et al. (2008). The blue line is the running mean time for our algorithm. On the left we have the running times for type one graphs and on the right we have the running times for type two graphs.
sparse. Therefore, do not restrict ourselves to finding the closest point in MET, when seeking metric. Instead, we want to find the closest point in MET(G) where G is the graph representing the interactions for which we have information. As seen in Section 4.1.2 we can solve the problem when G is sparse.
4.3 METRIC LEARNING
For the final problem, we solve variant of the metric learning problem, ITML. To do a head head comparison against Davis et al. (2007), we implemented their algorithm in Julia. As the algorithm from Davis et al. (2007) doesn't solve the complete linear program, only an approximation, we compare algorithms the quality of the solution.
For each data set, we uniformly at random choose 80% of the data points to the training set and the remaining to be the test set. We then let the similar pairs $ be pairs that had the same label and the dissimilar pairs be all of the other pairs. For the algorithm from Davis et al. (2007), as suggested in the paper, randomly sampled 20c² constraints, where c is the number of different classes and ran the algorithm so that it performed about 1 projections.
Because the algorithm from Davis al. (207)) is also based on Bregman projections, do a fair head to head comparison, we limit our selves to the same number of projections and, on each iteration, randomly sampled 2 x 105 constraints, 10 from S and 10 from D. We then the algorithm for 10 iterations. Note when sampling constraints we allowed repetition. That is, if a constraint was sampled & times during an iteration, we projected onto k times.
Table 3: Table comparing the testing aceuracy of PROJECT AND FORGET and ITML. Here the accuracy for ITML the average over 100 trials.
Algorithm Banana
Ionsphere
Coil2000
Letter
Penbased
Spambase
Texture
Ourt
0.88679
0.90000
0.93842
0.90250
0.97408
0.93587
0.99909
ITML
0.88816
0.86985
0.93842
0.92852
0.99039
0.90713
0.98390
The accuracy reported in Table 3 based on one run of our algorithm since we have a theoretical guarantee that we converge to the optimal solution. However, since there is a great amount of variability in the constraints selected for the algorithm from Davis et al.) (2007). we ran their algorithm 100 times and report the mean accuracy. As it can be seen from the table, in half cases our algorithm has better test accuracy as we solve the complete lincar program.
These results are interesting as both methods are guaranteed theoretically to converge to their optimal solution; the difference in accuracy is due to the difference in the set of constraints being considered. We conclude that in the cases ITML does better average, it indicates that subsampling the set of constraints, rather than using all of constraints, leads to lower generalization error. To verify that this difference in performance highlighted difference in problems and not in convergence of the

---

Under review as a conference paper at ICLR 2019
different algorithms, ran PROJECT AND FORGET for 10 iterations, where sample 2 x 103 constraints per iteration and did not see any significant improvement in the accuracy.
FUTURE WORK
In conclusion we see that our algorithm PROJECT AND FORGET can be used to solve not only large scale versions of three metric constrained problems but also opens many avenues for future work.
The first direction is motivated by ITML. As we see in Table 3 sometimes is better select only a small subset of the constraints rather than computing with all of them. It is interesting question whether we can determine what inherent properties of the data set result this phenomenon. If we answer this, we reduce the number of constraints by several orders of magnitude.
Another avenue of work that this algorithm opens learning better, more general metrics. Many existing metric learning algorithms learn linear transform of Euclidean space and then this transformed space to obtain a more relevant metric. Using our technique, however, we can directly learn Euclidean metric that optimizes the objective function which could then embed into Euclidean space using multidimensional scaling or some other embedding technique. We are also no longer restricted to Euclidean metrics, but can learn hyperbolic and tree metrics well, getting better metric representations of our data. With these techniques, we would gain better understanding the space a data set lies and a better, usable metric representation.
10

---

Under review as a conference paper at ICLR 2019
REFERENCES
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. In S00C'05; Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 684-693, ACM, New York, 2005. doi: 10.1145/0060500 1155//00600900000069922
David Avis, Patrick Hayden, and Mark M. Wilde. Leggett-Garg inequalities and the geometry of the cut polytope. Phys. Rev. A (3), 82(3):030102, 2010. ISSN 1050-2947. doi: 10. 10..103/PhyseeA. 82.030102.
Egon Balas and William Pulleyblank. The perfectly matchable subgraph polytope of bipartite graph. In Proceedings of the symposium on the matching problem: theory, algorithms, and applications (Gaithersburg, Md.,, 1981), volume 13, pp. 495-516, 1983, doi: (0.1002/het.3333130000
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Mach. Learn 56(1-3); 89-113, 2004. ISSN 0885-6125.
doi: 10. 100.00//-AAAA...000333666677777.
Francisco Barahona. On cuts and matchings in planar graphs. Math. Programming, 60(1, Ser. A): 53 28, 1993. ISSN 0025-5610. doi: (0.1007/BF0158060)
Francisco Barahona and Ali Ridha Mahjoub. Compositions of graphs and polyhedra. I. Balanced induced subgraphs and acyelic subgraphs. SIAM J. Discrete Math., 7(3):444 1994. ISSN
0895-4801. doi: 10.1 10.113777009544800011
Heinz H. Bauschke and Jonathan M. Borwein. Legendre functions and the method of random Bregman projections. J. Convex Anal., 4(1):27-67, 1997. ISSN 0944-6532.
Heinz H. Bauschke and Adrian S. Lewis. Dykstra's algorithm with Bregman projections: convergence proof. Optimization, 48(4):409 427, 2000. ISSN 0233-1934. doi: 10.1080/
02331930008844513.
Amir Beck and Mare Teboulle. A fast iterative shrinkage- thwesholdishggggooooo algorithm for linear inverse problems. SIAM Imaging Sci., 2(1):183-202, 2009. ISSN 1936-4954. doi: 171130000716542.
Aurelien Bellet, Amaury Habrard, and Marc Sebban. A survey on metric learning for feature vectors and structured data. ArXiv, abs/1306.6709, 2013.
Justin Brickell, Inderjit S. Dhillon, Suvrit Sra, and Joel A. Tropp. The metric nearness problem.
SIAM J. Matrix Anal. Appl, 30(1))375-396 2008. ISSN 0895-4798. doi: 10.1137/06065339.
Yair Censor and Stavros Zenios. Parallel optimization: Theory, algorithms, and applications. Oxford University Press, 01 1997. ISBN ISBN- 978-0195100624.
Karthekeyan Chandrasekaran, László A. Végh, and Santosh Vempala. The cutting plane method is polynomial for perfect matchings. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science-FOCS 2012, pp. 571-580, IEEE Computer Soc., Los Alamitos, CA, 2012.
Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. System Sci., 71(3):360-383, 2005. ISSN 0022-0000. doi: 10. J.06//..csss.0000 20....0044....... 10.012.
Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S. Dhillon. iooomaation-thoorede metric learning. In Proceedings of the 24th International Conference on Machine Learning, ICMI. '07, pp. 209-216, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-799
Santanu S. Dey and Marco Molinaro. Theoretical challenges towards cutting-plane selection. Math. doi: 10. 10.10077110007-018- 1302-44.
Program., 170(1, Ser. 2):237-266, 2018. ISSN 0025-5610.
Michel Deza and Monique Laurent. Applications of cut polyhedra. I, II. J. Comput. Appl. Math., 55 (2):191-216. 217-247, 1994. ISSN 0377-0427. doi: 10. 10.101600377-0227(4)90000
Inderjit S. Dhillon and Joel A. Tropp. Matrix nearness problems with Bregman divergences. SIAM J. Matrix Anal. Appl., 29): 120-111444 2007. ISSN 0895-4798. doi: 10. 17.16377060499111.
Tommy Elfving. An algorithm for maximum entropy image reconstruction from noisy data. Math. Comput. Modelling, 12(6):729-745, 1989. ISSN 0895-7177. doi: 10.
11

---

Under review as a conference paper at ICLR 2019
Dotan Emanuel and Amos Fiat. Correlation clustering Blsttringg-minimizinn -iiiiiizing disagreements arbitrary weighted graphs. Algorihhms -artrihhss--AAA 2003, volume 2832 of Lecture Notes in Comput. Sci., pp. 208-220. Springer, Berlin, 2003, doi: 110100/99783355--996666666
Rong-En Fan, Pai-Hsuen Chen, and Chih-Jen Lin. Working set selection using second order infor- mation for training support vector machines. J. Mach. Learn. Res., 6: 68188991918, 2005. ISSN 1532-4435.
Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. Journal of Machine Learning Research, 9:1871-1874, 2008.
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald Wolf. Linear semidefinite extended formulations: exponential separation and strong lower bounds. In of the 2012 ACM Symposium on Theory of Computing, pp. 95-106. ACM, New York, 2012. doi: 10. 00.11445/213377.22233
A. C. Gilbert and Jain. It ain't broke, don't 't fix it: Sparse metric repair. 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 612-619, Oct 2017. doi: 10. 1100//LLLLETONN00...6677777
Anna C. Gilbert and Rishi Sonthalia. Unsupervised metric learning in presence of missing data. 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 313-321, 2018.
W. Glunt, T. L. Hayden, S. Hong, and J. Wells. An alternating projection algorithm for computing the nearest Euclidean distance matrix. SIAM J. Matrix Anal. Appl., 114)):899-600 1990a. ISSN 0895-4798. doi: 10.1 N0.1137/061 1042.
W. Glunt, L. Hayden, S. Hong, and Wells. An alternating projection algorithm for computing the nearest euclidean distance matrix. SIAM Journal on Matrix Analysis and Applications, 12, October 1990b.
M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. ISSN 0209-9683. doi: 10. 10.000//002579233.
Piotr Indyk. Sublinear time algorithms for metric space problems. Annual ACM Symposium on
Theory of Computing (Atlanta, GA, 1999), pp. 428 432-432.44 ACM, New York, 1999. doi: 10.1 301250.301366.
Alfredo N. Iusem. On dual convergence and the rate of primal convergence of Bregman's 's convex programming method. SIAM J. Optim., 1(3):401-423, 1991. ISSN 1052-6234, doi: 10.1137/ 0801025.
Alfredo N. lusem and Alvaro R. De Pierro. On the convergence properties of Hildreth's quadratic programming algorithm. Math. Programming, 47(1, (Ser. A)):37-51, 1990. ISSN 0025-5610. doi: 10.1007/BF015808511
Ariel Jaimovich, Gal Elidan, Hanah Margalit, and Nir Friedman. Towards an integrated protein- protein interaction network: A relational markov network approach. Journal of computational biology: a journal of computational molecular cell biology, 13 2:145664, 2006.
Thorsten Joachims, Thomas Finley, and Chun-Nam John Yu. Cutting-plane training of structural svms. Machine Learning, 77:27-59, 2009.
Monique Laurent. A connection between positive semidefinite and Euclidean distance matrix completion problems. Linear Algebra Appl., 273:9-22, 1998. ISSN 0024-3795. doi: 10. 1016/ 5002443799599999022644
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection, June 2014.
Bo Lin, Anthea Monod, and Ruriko Yoshida. Tropical foundations for probability and statistics on phylogenetic space. arXiv e-prints, 2018.
12

---

Under review as a conference paper at ICLR 2019
Angelia Nedić. Random algorithms for convex minimization problems. Math. Program., 129(2. Ser. B):225 253, 2011. ISSN 0025-5610. doi: 10. 10.10077/11000--11--466-99
Yu. E. Nesterov. A method for solving the convex programming problem with convergence rate O(1/k²). Dokl. Akad. Nauk SSSR, 269(3):543 547, 1983. ISSN 0002-3264.
Xinghao Pan. Dimitris S. Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael Jordan. Parallel correlation clustering on big graphs. In NIPS, 2015.
Divya Pandove, Shivani Goel, and Rinkle Rani. Correlation clustering methodologies and their fundamental results. Expert Systems, 2018.
Laurent Poirrier and James Yu. On the depth of cutting planes. arXiv e-prints, art. 10Xiv:1903.05304
Mar 2019.
B. Polyak. Random algorithms for solving convex inequalities. Inherently parallel algorithms in feasibility and optimization and their applications (Haifa, 2000), volume 8 of Stud. Comput. Math., pp. 409-422. North-Hollann Amsterdam, 2001. doi: 10.1016/51570-5790000030
Thomas Rothvoss. The matching polytope has exponential extension complexity. STOC' 14- Proceedings of the 2014 ACM Symposium on Theory of Computing, pp. 263-272. ACM, New York, 2014.
Cameron Ruggles, Nate Veldt, and David F. Gleich. A Parallel Projection Method for Metric Constrained Optimization. arXiv e-prints, art. 190.::11101.100000 Jan 2019.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoff's for hyperbolic embeddings. Proceedings of the 35th International Conference on Machine Learning, pp. 4460- 4469, July 2018
I. J. Schoenberg. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 44(3): 522-536, 1938. ISSN 0002-9947. doi: 10.2307/1989894.
David Sontag and Tommi S. Jaakkola. New outer bounds on the marginal polytope. In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis (eds.), Advances in Neural Information Processing Systems Curran Associates, Inc., 2008.
20, pp. 1393-1400.
David Sontag, Talya Meltzer, Amir Globerson, Tommi Jaakkola, and Yair Weiss. Tightening Ip relaxations for map using message passing. In Proceedings of the Twenty-Fourds Conference Uncertainty in Artificial Intelligence, UAI'08, pp. 503-510, Arlington, Virginia, United States, 2008. AUAI Press. ISBN 0-9749039-4-9.
David Sontag, Do Kook Choe, and Yitao Li. Efficiently searching for frustrated cycles in map inference. In Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12), pp. 795-804, Corvallis, Oregon, 2012. AUAI Press.
David A Sontag and Tommi S. Jaakkola. On iteratively constraining the marginal polytope for approximate inference and map. Semantic Scholar, 2007.
Juan Luis Suárez Díaz, Salvador García, and Francisco Herrera. A tutorial on distance metric learning: Mathematical foundations, algorithms and software. arxiv eprint, 12 2018.
Yichuan Tang. Deep learning using support vector machines. ICML 2013 Challenges in Representa-
tion Learning, abs//306 300.0223, 2013.
Nate Veldt, David Gleich, Anthony Wirth, and James Saunderson. Metric-constrained optimization for graph clustering algorithms. SIAM Journal on Mathematics of Data Science, 1353--355, 01 2019. doi: 10. 10.1137/18M1217152
Mengdi Wang and Dimitri Bertsekas. Incremental constraint projection- methods for nonsmooth convex optimization. http://www.mit..ek edu/ dimitrib/, 2013.
Mengdi Wang, Yichen Chen, Jialin Liu, and Yuantao Gu. Random multi-constraint projection: Stochastic gradient methods for convex optimization with many constraints. ArXiv, abs/151 13.0766,, 2015.
13

---

Under review as a conference paper at ICLR 2019
Yubo Wang, Linli Xu, Yucheng Chen, and Hao Wang. A scalable approach for general correlation clustering. In ADMA, 2013.
Chen Yanover, Talya Meltzer, and Yair Weiss. Linear programming relaxations and belief propagation-an empirical study. J. Mach, Learn, Res., 7:1887-1907, 2006. ISSN 1532-4435.
14

---

Under review as a conference paper at ICLR 2019
6 CONVEX PROGRAMMING
As we mentioned in main body of the paper, there is a much more general formulation of the metric constrained optimization problems and correspondingly general variant of the algorithm. We present that setting below and detail the convergence results in the following section.
Given strictly convex function f. and finite family of half-space H {Hf)) such that H; far (as, 4) S bx). we want to find the unique point x² E E H, =: C' that minimizes f- That is, if we set A to the matrix whose rows are a, and be the vector whose coordinates are b, we seek
minimize f(z) subject Ar b
(6.1)
We refer to each H. as a constraint sel and C as the feasible region. We shall assume that C' is not empty, i.e., there least one feasible point. In general, we can represent any half-space by linear inequality.
In general, since is an extremely large matrix, computing A or writing down is not computation- ally feasible for many large instances of the problem. Therefore, we access the constraint sets only through an oracle that has one of the two following separation properties.
Property 1. Q is deterministic separation oracle for family of haaf-spacer H. if there exists positive, non-decree decreeere,,,ng continuous function é. with ((0) = 0, such that on input x E Rd, Q either
certifies or returns a list C H such that
max dist xx Õ) ((dist(
CEC
Property 2. Q is random separation oracle for a family of half-spaces H. if there exists some distribution DD and lower bound 0, such that on input R.d returns list H such that
vn H. Pro|H e 2
For the random oracle, do not need it to decide whether C, so this oralce can be used to solve optimization problems over polytopes for which deciding membership is NP-hard.
In addition method works for rich class of functions known Bregman functions. Definition 3. A function f A - TR is called a functionn if there exists a non-empty conver set S such that C A and the following hold:
(i) ((x) is continuous, strictly convex on S, and has continuous partial derivatives in S. (ii) For every a E R, the partial level sets I (y, a) = {x E 5 Dy(æ,v) a} and 1A (x, = {y E S: D2( y) S ox) are bounded for all x E 5,y (ii) yn E S and lim Un y² then lim Dy(y", .Va) O. 12000
12
(iv) yn E. F.p S, lim Df(#n Vn.) ) = O, Yn - y", and ny bounded, then In - y"- n n2020
We denote the family of Bregman functions by B(S). We refer to as the zone of the function and we take the closure of the S to be the domain of f-
Definition 4. We say that a hyperplane H; is strongly zone consistent with a respect to a Bregman function f and its zone S, if for all y S and for all hyperplanes H, parallel to H; that lie in between and H,, the Bregman projection of onto H lies in S instead of in S.
Next, we briefly discuss under what assumptions can we solve solve our optimization problem and what these assumptions mean.
Assumption 1. f(x) is Bregman function.
This class of function includes many natural objective functions, including f(x) Σx_ v. log( with zone S TR. (here f is defined on the boundary of S by taking the limit) and fxx) , | for p E (1, o.). The lp norms for = 1, oo are not Bregman functions but can be made Bregman functions by adding quadratic term. That is, f(x) = c" x is a not Bregman function, but TT x=+x"" Qx for any positive definite Q is Bregman function.
15

---

Under review as a conference paper at ICLR 2019
Additionally, strongly convex functions and Legendre functions related to Bregman functions, but neither class implies the other. See Bauschke Lewis (2000) for an example and more in-depth discussion.
Assumption 2. All hyperplanes in are strongly zone consistent with respect to ((a)
This assumption is used to guarantee that when we do projection the point we project onto lies within domain. This is not too restrictive. For example, all hyperplanes strongly zone consistent with respect to the objective functions ((x) |z5| and f() = D; æi log(r;).
Assumption 3. C is non-empty.
This is needed to make that the algorithm converges.
THE GENERAL ALGORITHMS
To set the stage for subsequent discussions, we present the general structure of all of our algorithms. They are all iterative and, in general, are run until some convergence criterion has been met. The convergence criterion depends largely on the specific application for which the algorithm is tailored. For this reason, we postpone the discussion of the convergence criterion until the applications section.
Each iteration consists of three phases, as shown in algorithm 3 In the first phase, we query our oracle Q to obtain list of constraints L. In the second phase, we merge (M),, the list of constraints we have been keeping tracking up the vth iteration, with L and project onto each of the constraints in the list (()) U L iteratively. Finally, in the third phase, forget some constraints.
Algorithm 3 General Algorithm.
1: function F(Q,
2:
[ 0, (0) = Initialize (0))) that V((x(0)) 0.
3:
while Not Converged do
4: == Q(x")
5:
[(++1) L [ UL
6:
(1++1) Project(x [(++1))
7:
[((+1) = Forget( (((++))
return æ
7.1 PROJECT AND FORGET ALGORITHMS
The project and forget steps for algorithm are presented in Algorithm 4 Let us step through the code to understand the behavior of the algorithm. Let H, {z (a,, x) S bg be our constraint and
current iterate. The first thing we do is calculate x² and Here x² the projection of x onto boundary of H, and 0 is "measure" of how far x is from æ². However, 0 can be any real number. Let us discuss separately the cases positive and negative below.
It can be easily seen Censor & Zenios (997) that 0 is negative if and only if the constraint is violated. In this case, c = 0. This is because (as we will see in proof) we will always maintain that 2; 2 0. Then line 5, we just compute the projection of onto H,. Finally, since corrected for this constraint, we add [ to 2,. Since each time we correct for H,, we add to 2;, we see that 2; stores how the total corrections made for H,.
On the other hand, if / is positive, this means that this constraint is satisfied. In this case, if we also have that 2; is positive, i.e., have corrected for H; before, then have compensated for this constraint. Hence we must do undo some of the corrections. Thus, if = then we undo all of the we only undo part the correction.
corrections and 2; now 0. Otherwise if
The FORGET step is relatively easy, given constraint H, we just need to check if z; = 0. If 2; 0, then this means we have not done any net corrections for this constraint. Thus, we can forget about it; i... delete from [.())
16

---

Under review as a conference paper at ICLR 2019
Algorithm 4 Project and Forget algorithms.
1: function PROJECT(I, 2, L)
2: for H, { (as; u) = b E do
3: Find x² by solving Vf(x") - Vf(x)) = 0a, and x² E H,
4:
Q: = min (2,, 8)
5:
4- such that V f( fz)) C;a,
6:
2j + 2 C2
return 20,
7: function FORGET
8: for H, = {x: (a,, r) = b E do
9: if 21 then Forget Hi;
return
In general, calculating the Bregman projection (line 3) cannot be done exactly. See Dhillon & Tropp (2007) for general method to perform the calculation line and for analytic formula for when is a quadratic function.
7.2 CONVERGENCE ANALYSIS
Now that we have specified our algorithm, we need to establish a few crucial theoretical properties. The first is that under assumptions 1,2,3 our algorithm is guaranteed to converge the global optimum solution. In fact, we also show that asymptotically, our error decreases at an exponential rate. These main theoretical results can be summarized by the following theorem.
Theorem 3. If B(S), H; are strongly zone consistent with respect to and 3x E S such that ff(x)) = 0, then
1. If the oracle Q satisfies property ② (property 2). then any sequence x² produced by the above algorithm converges (with probability 1) the optimal solution of problem 6.1
2. If x² is the optimal solution, f is twice differentiable x², and the Hessian == (f())) is positive semidefinite, then there exists p E (0, 1) such that
|x=
22+ || Sp
lim 10+00
(7.1)
xx
x² 11
where | y² Hy. In the case when we have oracle that satisfies property the limit in holds with probability 1.
Proof. The proof of this theorem has been moved to the supplementary material section.
The proof of Theorem also establishes another important theoretical property.
Proposition If 0g is an inactive constraint, then (with probability 1) 2 = 0 for the tail of the sequence.
Corollary 2. Under the assumptions for part (2) Theorem 3 we have that the sequence 2n - 2² also converges.
These properties are important as they permit the following interpretation of our algorithm. The algorithm spends the initial few iterations identifying the active constraints from amongst large number constraints. The algorithm then spends the remainder the iterations finding the optimal solution with respect to these constraints. This ability to find the set of active constraints is one of the main advantages of our algorithm.
7.3
THE METRIC CONSTRAINED VERSIONS
First we can easily see that function METRIC VIOLATION in Algorithm is an oracle that satisfies
Property [
17

---

Under review as a conference paper at ICLR 2019
Proposition 4. Function METRIC VIOLATION in Algorithm 7 O(n² log(n) that has Property
En)E)) oracle
Proof. The first step METRIC VIOLATION is to calculate the shortest distance between all pairs of nodes. This can be done using Dijkstra's algorithm in @(n" log(n) + n E|) time. Then if the shortest path between any adjacent pair of vertices is not the edge connecting them, then the algorithm has found violated cycle inequality. Note that if no such path exists, then all cycle inequalities have been satisfied. Hence our point is within the metric polytope. Thus, we have an oracle that separates the polytope. However, we want oracle that satisfies property
Given a point x and a hyperplane Hc,es defined by some eycle and an edge e, the deficit of this constraint is given by the following formula.
d(CC,) ((()))
Σ
x(e)
EEC,E
If this quantity is positive, then violates this constraint. In this case, the distance from this constraint is d(C.e) distance, it does find the cycle C' and edge that maximize d(C, e). Since |C| E [1, if we let ((x) = x x/n, we see that oracle satisfies property
CC While the above oracle does not find the cycle C' and edge e that maximize this
Similarly
that uniformly randomly sampling constraints is oracle that satisfies Property Thus we can see that both algorithms presented in the main text are special cases the above algorithm.
2
7.4 TRULY STOCHASTIC VARIANT
Now Algorithm 4 can be used with an oracle that satisfies property However, this is not a completely stochastic algorithm. We still have keep track of the constraints that we have seen and carefully pick which constraints to forget. Nevertheless, we can modify our forget step forget all constraints and obtain truly stochastic version of the algorithm. random set of constraint and project onto these constraints only, independently of what constraints were used in previous iterations. We cannot, however, forget the values of the dual variables. this case, have the following convergence result.
this version, at each iteration, we choose
Theorem 4. If f E B(S), H, are strongly zone consistent with respect to f. and 3x E S such that (= = O, then with probability any sequence x" produced by the above truly stochastic algorithm converges to the optimal solution of problem 6.1 Furthermore, x is the optimal solution, twice differentiable at x", and the Hessian H H f(x")( is positive semidefinite, then there exists E (0, 1) such that with probability 1,
||x0 x² x ||
lim inf 0-000
S.p.
||
x² ||
This version of our algorithm is very similar to the algorithms presented Nedić (2011) 1) Wang et al. 2015).. The major difference being that we do not need to gradient descent step. Instead we maintain the KKT conditions, by keeping track of the dual variables and doing dual corrections.
However, in practice using 4 with the random oracle tends to produce better results. This is because by not forgetting the active constraints that we have seen, instead of hoping that we sample them, speed up convergence significantly.
8 CONVERGENCE RESULTS
In this section, we present the proofs of Theorems 3 and Because the proof of Theorem is quite technical and involves two different types of separation oracles, we split it into several parts. In Subsections 8.1 and 8.2 we prove the first part of Theorem 3 separation oracles with property [ and respectively. In Subsection 8.3 we prove the second part of Theorem (also subdividing this proof into several cases). Finally, in Subsection 8.4 we prove Theorem noting only the changes necessary from the proof of Theorem
18

---

Under review as a conference paper at ICLR 2019
8.1 PROOF OF PART OF THEOREM 3 FOR ORACLES THAT SATISFY PROPERTY
We remind the reader of the notation established in Section 2 The vector of variables over which we optimize x; J' is the objective function, H, = {y (y, dz) b,} are the hyperplanes that lie on the boundaries of the half-space constraints, L is the Lagrangian, is the dual variable, A is the matrix with rows given by aş. and b is the vector with rows b,.
Next, we clarify the indexing of the variables. Algorithm 3 has three steps per iteration and during the PROJECT step there are multiple projections. When we want refer to variable after the vth iteration, it will have a superscript with v. When we refer to a variable after the n(i, k)th projection, we use the superseript (i, k). Finally, before the nth projection, i(n) will represent the index of the hyperplane onto which we project.
Finally, R be the maximum number of constraints that our oracle Q returns. This is clearly upper bounded by the total number of constraints, which we have assumed is finite. We are now ready to prove the first part of Theorem
Theorem (Part ff B(S), H; are strongly zone consistent with respect to f. 3x E S, such that V f O, and the oracle Q satisfies property ] then any sequence x" produced by Algorithm 3 converges to optimal solution of problem 6.1
Proof. The proof of this theorem is an adaptation of the proof convergence for the traditional Bregman method that is presented in Censor & Zenios (1997) whose proof entails the following four steps. The main difference between Censor and Zenios' proof and ours is that of the last two steps. We present the entire proof, however, for completeness. To that end, we show that
Step 1. the KKT condition, vf(x) = (=²==) A is always maintained,
Step 2. the sequence x" is bounded and it has at least one accumulation point,
Step 3. any accumulation point of xM is feasible (i.e., is in C), and
Step 4. any accumulation point is the optimal solution.
Step 1. The KKT condition, fz(x)= f(²²)) ATz, 2, is always maintained.
We show by induction that for all n, ff(x") = -A" z". In the base case, = = O, thus, vf(x9) =
0 -A- 20, Assume the result holds for iteration n, then
(z (11 = (x(") + c" aa)n = - A =" + A c" (((())) = - A= c" d'es(n)) = - -0+=
We know that c < am)) therefore, we maintain 2+1 2 0 as well.
Step 2. The sequence x" is bounded and has accumulation point.
To show that xn is a bounded, we first show that (L(x", [[(x,,")) ==)) is a monotonically increasing sequence bounded from above. This observation results from the following string of equalities:
1(x ((*ntt,aat1) - ((x",2")
-(x f(x") (2 Ar b) - (2" Ax." - 6)
-1(x+1)- f(x")= (AT 211 x1 (AT n" ,x²)) - (2 2. b)
-1(a+1)- )- -1(x)) - (V x n1 + (Vf(x") ),²)) + (c" b) =1(xnt1)- -((*") (V/(x") + d" Q:(n); x , + (Vi(x"), xxx") ) + (s(()))
- )- -(x") (V/(x"), ), n+ _ x²) (c" ds(n), n+ + c be(r)
Dy( x²)) + cd (be(m) (ai(m)) 22))
(1)
(2)
Next, we show that both terms (1) and (2) are non-negative. We know that D, is always non-negative so we only need to consider term (2). There are two cases: (i) if eth 0", then g=+1 H)()) and
19

---

Under review as a conference paper at ICLR 2019
Di(n) (n) )= O. On the other hand, (ii) if c" [n))) then bi(n) (ai(m)) xn 2 and 2 We can conclude that the difference between successive terms of [(x", =n) always non-negative and, hence, it is an increasing sequence.
To bound the sequence, let y be feasible point (i.e., Ay - b). (Note that this the only place use the assumption that the feasible set is not empty.) Then
D D1 x²) = f(v) f(a") (Vf(="), ).y x²)) f(y) f(x") (2" Ay Axr) S fv( f(=") + (z", \r")
Rearranging terms in the inequality, obtain bound the sequence 2(x"2") from above:
L(x", = f(x") + (z", Az 6) - f()) - (y x²) S f(y).
Since the sequence (L(x". neNN increasing and bounded, it convergent sequence and the difference between successive terms of the sequence goes to 0. Therefore,
lim Dy (x"+1 xx")) =
n n-000
From the previous inequality we also have that
Dy(u,²") s ((v) L(x","",,)) f(v) L(x",
Using part (ii) of the definition of a Bregman function, we see that Lí (y, a) is bounded and since JUEN
(NE") E T.f (y, o),, xn is bounded sequence with an accumulation point.
Step 3. Any accumulation point x" of x. is feasible (i.e., is in C).
This is the only step in which we use the fact that our oracle satisfies property [ Let x= be some accumulation point for x" and assume for the sake contradiction that Ax" z b. Let A, 6 be the maximal set of constraints that x does satisfy; i.e.,
Ax" < b.
Let ( be subsequence such that th + xx and H be constraint that x² violates. Define
:== H)) O.
(8.1)
Because x" is bounded, n* is convergent subsequence = + x², and Dy(xat1 ,x²) - 0. by equation 6.48 from Censor & Zenios (1997) we see that for any t,
nutt x²
In particular, the proposition holds for all t < 2| + T:
Let us consider an augmented subsequence x² -0
"T i.e., add in extra terms. Note that if n4++1 n4 + oc, then this augmented sequence is not the entire sequence. We want to show that infinitely many of the terms in our augmented sequence satisfy a constraint not in Á. Should this hold, then because we have only finitely many constraints, there exists at least one single constraint that is not in Á, such that infinitely many terms of the augmented sequence all satisfy the single constraint à. Finally, because our augmented sequence converges to x² and we are only looking at closed constraints, we must have that x also satisfies the constraint ā. Thus, we would arrive at contradiction of the maximality of Á and x would have to be in the feasible region.
To see that infinitely many of the terms in our augmented sequence satisfy constraint not in Á, let Vy be the iteration in which the nyth projection takes place. Note that we can assume without loss of generality that in any iteration, the case and we projected onto constraints more often, we would simply change the value T to reflect this larger number of projections. Therefore, we have two possibilities for which iteration the ny + |Å| + 1st projection takes place and we consider each case below.
project onto any constraint at most once. If this were not
Case 1: The ny + | + 1st projection, infinitely often, takes places in 14th iteration. Since project onto each constraint at most once, one of the projections between the ny and n& | 1st
20

---

Under review as a conference paper at ICLR 2019
projection must be onto hyperplane defined by constraint not represented in À and amongst the terms æ"h, x 1.... I"v must have term that satisfies constraint not in À infinitely often.
Case 2: The ny + |A + 1st projection, infinitely often, takes place in 2y 1st iteration or later.
If this projection happens in + 1st iteration, consider the iteration in which we do the n& + Tth projection. If this projection also takes place in the Vi + 1st iteration, then we have done at least |Á] + projections in the Vi + 1st iteration. Hence, amongst x + +1 "...,,"**.? x**+7 we must have a term that satisfies a constraint not in Á.
If the T&K | 1st the n& + Tth projection happens in the 21 2nd iteration later, then between the th and the n& + T'th projection, we must have projected onto all constraints returned by oracle in the Vk + 1st iteration. Therefore, we must have projected onto some hyperplane defined by (for some constraint C) such that
dn == d(x +1 Õ) 2 ((d(x C)).
Then there exists sufficiently small 5 > 0, depending on A, b, x², such that if lly x=1 S 6, then
Ay S b b+ E L, 2
where 1 is vector of all ones.
Since our augmented sequence converges to z², we know that there exists K, such that for all k 2 K and < T, | x²Il < 6. That is, for all ls 2 K and f < T,
mt b 1. 2
(8.2)
Note 2 is within our augmented sequence if à is infinitely often in Å. by equation 8.2 have that infinitely often
dm
Finally, because the augmented sequence converges to x..
<= .I)) o(d(=", C)) lim o(d(z C)) < lim d S
2
The first inequality follows from the fact that o is non-decreasing. Therefore, à is not in À infinitely often and amongst ,= ==*+1 ...., RT+ we must have term that satisfies a constraint not in Á infinitely often. Thus, there is a constraint not in A that satisfied by infinitely terms of our augmented sequence and we have contradiction.
Step Optimality of accumulation point.
Because we have established the feasibility of all accumulation points, we show next that any accumulation point x² is optimal.
First, we show that there exists an N, such that for any A 2 N, and for any a, such that
(a,, x²) < b,
we have 2/th O. To do so, we assume for the sake of contradiction that for some a, our sequence =! is infinitely often not O. The algorithm then projects onto this constraint infinitely often. Therefore, the point ** lies on the hyperplane defined by a, infinitely often. Thus, the limit point x² must lie on this hyperplane as well and we have contradiction.
Now we know that for any constraint a,, we either have that (a,,z*) by or we have that 2 for the tail of the sequence. Thus, for sufficiently large k.
(2 T - b) (A" =* "h x²) (- V Vf( ), nh -x") = -(==)
Next, by part (iii) of the definition a Bregman function,
lim Dz =*)) = 8-000
21

---

Under review as a conference paper at ICLR 2019
Finally,
lim L(x x lim f(**)) (2"t Ax -) f(x)). k0000
k-000
We also know that L(**, 2²) S f(y) for any feasible y. Thus, f(x") I f(y). Hence x' is optimal solution. Now since I is strictly convex, this optimal point is unique. Therefore, we have that (x*) JEN has only one accumulation point and xx
An important fact consequence of this proof is the following proposition:
Proposition 3 If a, is an inactive constraint, then there exists N, such that for all n 2 N, we have that 27 O. That after some finite time, we never project onto inactive constraints ever again.
8.2 PROOF OF PART OF THEOREM 3 FOR ORACLES THAT SATISFY PROPERTY
We make note of In this subsection, we prove part I of Theorem for oracles that satisfy property 2
the key ideas in this proof as they are useful in the proof of the truly stochastic vanant. To be precise, we prove:
Theorem (Part If E B(S), H, are strongly zone consistent with respect to f. 3x0 E S, such that (xx)) and the oracle Q satisfies property 2 then with probability 1, any sequence x" produced by Algorithm converges to optimal solution of problem 6.7
Proof. Assume that we have oracle that satisfies property 2 A careful reading of the previous proof shows that if we switch out an oracle with property for an oracle with property 2 then we only need adjust step 3 of our proof. The erucial part of that step was showing that for augmented sequence, we had infinitely many terms that satisfied constraint not in A. We make the following adjustments to our analysis.
Let V/8 be the iteration in which the nyth projection takes place. In the previous proof, we used the property of the oracle only when the nı + Tth projection took place the v + 2nd iteration or later iteration. In this case, the augmented sequence encompasses all of the V4. 1st iteration infinitely often.
Let us choose a constraint à that is not satisfied by x". Because the oracle satisfies property 2 for each iteration 2A + 1, our oracle returns à with probability at least > 0. By the Borel Cantelli Lemma, know that during the selected iterations, the constraint with probability one, returned infinitely often by our oracle. Thus, our augmented sequence satisfies this constraint with probability 1 and lies in the feasible region with probability 1.
A direct consequence of this proof is the proof of the probabilistic version of Proposition 3
Proposition
3 With probability 1, we project onto inactive constraints a finite number of times.
8.3 PROOF OF PART 2 OF THEOREM 3
The discussions in lusem & De Pierro (990): Jusem (191)) almost directly apply to that for our algorithm. For completeness, we present it along with the necessary modifications. As with the traditional Bregman algorithm, we first present the case when f(x) is quadratic. That is,
1 x Hr
f(x)= = ST x.
2
where H is positive definite matrix. In this case, is easy to see that
Dy(0,v) || -1ln-vlia = (x y) H(x v)-
22

---

Under review as a conference paper at ICLR 2019
8.3.1 PROOF OF PART 2 OF THEOREM QUADRATIC CASE
In this section, we will prove the following variation of Theorem
Theorem
3 If a strictly convex quadratic function, H2 are strongly zone consistent with respect
f. xn H s S, and the oracle satisfies either property 1 or then there exists p (0, 1)
such that
120
lim
S
(8.3)
||
x²
where llyl y Hy. In the case when we have oracle that satisfies property 2 the limit in 8.3
holds with probability 1.
We establish some notation ahead of our lemmas. Let I be the set of all active constraints. That is, if xx the optimal solution then
T= {i: (0,, =b)).
Let S be the set of all a that satisfy these constraints (namely S = (x: Vi E I, (a,, = b.))) Let H be the hyperplane, such that H₂ represents the constraint in / that is furthest from x. Define
1 inf d(z, H2).
2g5 d(z, S)
By lusem & De Pierro 1990). we know that > 0. Let U be the set of all optimal dual variables i.c., U {z:
A" A 2} and let
{i 2 x # 03.
Next, we present a few preliminary lemmas. These lemmas exist in some form or another in lusem (1991); lusem & De Pierro (190)) and we present them suitably modified for our purpose. These lemmas require the tollowing set of assumptions about an iteration v:
Vi & 2
2. for all & I, we do not project onto this constraint in the vth iteration; and,
3. there exists E U, such that for all & Iy, 2, 0.
Lemma 1. Let x² be the optimal solution for an instance of problem 6.1 For any sequence x² - x² such that x" 2n maintain the KKT conditions, there exists an M, such that for all v 2 M, there exists E U, such that for
all & Iv, we have that 0.
Proof. Let V, = (=:Vigg Tp. 2; 03. Then assume, for the sake contradiction, that the result is false. That is, there is sequence Ph, such that V2, n 0. Then since there finitely many different lu (hence finitely many V,), we have that one of these must occur infinitely often. Thus, by taking an appropriate subsequence, we assume, without loss of generality, that I, are all equal. Let V Vn and obtain V n = 0.
Since closed subspace, U is closed set, and +1+1 E V and so
0, we must have that d(V, U) But
CC U) Z d(V U) > 0.
Since x. xx and maintain the KKT conditions, have that for any = U,
A 2" - -v(x"" A²2.
Thus C(z,UU) + O which is a contradiction.
Lemma 2. For any sequence xt - x", if for a given v, we have that the sequence satisfies assumptionn (1) and (2), then
K
|
x 11
1|20" x=
Σ
n+
1²113
where k and K are the indices of the first and last projection that take place in the vth iteration.
Proof. This Lemma is simply a statement about Bregman projections and so its proof requires no modification.
23

---

Under review as a conference paper at ICLR 2019
Before proceed, introduce additional notation. Let Al.: bú, be the submatrix of A, with rows from ly and
S, = Ar., bbnb
Lemma 3. For any sequence such that x² + x², if a given we have that it satisfies assumptions (1), (2), and (3), then we have that || x lle = d(x"+1, SS,).
Proof. Consider the constrained problem
min #ES,
||x x11ē
(8.4)
Then sufficient conditions for a pair (z, 2r.) to be optimal for this problem are
Ar, = br, and x =+1 Q A
By Proposition 3 we see that since x² is solution to problem 6.1 we have that A,, = b,,- Then by assumptions and the manner in which we do projections, we have that there exists U, such that for all & Iu. = 0 and
Then since z{-11 = 0 for all & Iu we have that
1-1---1- (27, 21.)
Thus, xf the optimal solution 8.4
Next for x & Sp, let Hy be the hyperplane of that is furthest from x and define
Hy inf d(z, H²) zgs, d(x, Sv)
Now we are ready to prove the following theorem.
Theorem 5. Let x" is the optimal solution to problem (I), (2), and (3), we have that
6.1
Then given that satisfies assumptions
L
x 20112
1122
L nr
where L is the number of projections that happened in vth iteration.
Proof. By Lemma 3 for any such u we have that x*+1 E Sy (or we have converged already).
Suppose constraint j E I, defines the hyperplane H² * Then by Lemma and definitions of μe, / we have the following incquality.
||1 x² d(2"t1
d(a HH
1
d(a H1 4
Now since I, = {i: 2 * 0}, we know that during the 1/th iteration must have projected onto H Note that this is the only place in the proof where we need the fact that we remember old constraints. Let say that this happens during the rth projection of the wtth iteration.
Note by assumption, we satisfy the assumptions of Lemma xf s1111 onto H +1+ Then that
Let y" g 1 be the projections of
24

---

Under review as a conference paper at ICLR 2019
d(x"+1 H 1)
111 xx+ lle
$ 11 e2t+1113
[g--1 by def is the closest point)
2
11
-x--11l 110
Σ
||
x x0t1110
(Triangle inequality]
1
2
Σ
|| x
x1ttlla 110
imr+1
||
x
+++
110
L Σ || 1ett1112
Cauchy Schwarz]
k=0
I L (1|x" =x1113 -112
x= x²))
Lemma 2
Thus, we get that
p 1
x x=1 s d(x Hmu+1)² (1|x" -2"112 -112 =x2)
Rearranging, we get that
| x²113 S L 1 11 - x² 121
As corollary the above theorem, we have that algorithm 1 converges linearly.
Theorem
3 If f a strictly convex quadratic function, H2 are strongly zone consistent with respect
f. x0 HH-1 s S, and the oracle satisfies either property 1 oor then there exists p (0, 1)
such that
||0"
2
11
lim 1-000
S
8.3
|
x²
where 1yyl Hy. In the case when we have an oracle that satisfies property 2 the limit in 8.3 holds with probability 1.
Proof. Using Proposition Lemma I and that we have fimitely many constraints, we see that if is large enough, the assumptions for Theorem 5 Jrre satisfied. Taking the limit gives the needed result.
In the case when we have an oracle that satisfies property 2 consider the product space of all possible sequences of hyperplanes returned by our oracle. In this product space, we see that with probability 1, we generate sequence of hyperplanes, such that algorithm [edorrthhm[coomee converges. For any such sequence of hyperplanes, we have that 8.3 holds. Thus, the limit in 8.3 holds with probability 1 for random separation oracles.
8.3.2 PROOF OF PART 2 OF THEOREM 3
GENERAL
The rate of convergence for the general Bregman method was established in lusem (1991). To show this, let f be the 2nd degree Taylor polynomial of f centered at the optimal solution. x.".
f(x) = f(x)) + Vf(=")". x xx" V2 v2f(x")
For notational convenience, let be the Hessian of f at x". Then we can see that if replace f with 6.1 then the optimal solution does not change. Thus, if had access to ff and could use this function to do our projections, then from the quadratic case we have result.
25

---

Under review as a conference paper at ICLR 2019
Thus, get the general result, if x" is our standard iterate and ø" is the iterate produced by using instead of f. then Lusem (1991) shows that | - -E"l is o( ||20 - (lH). Specifically, we can extract
the following theorem from lusem (1991).
Theorem 6. Jusem (1991) Let x² is the optimal solution for problem 6.1 and Hn is the sequence produced by using the same sequence of hyperplanes but with f instead of f. Given sequence x" produced by Bregman projections, such that x² + x², and for large enough v we satisfy assumptions (I). (2), and (3), then |x" in is o[Ix=" x x=H
Using this we can get the general result as follows
1 S ||, +1 50+1 |11 + || x² ||
$ || - - 1 HH + p||ā" - x²||
[Quadratic case convergence)
$ || 1 1 + pl|ă" - x² 1l + p||a" - x² I|
Then diving by ||att1 x²11 ||H, and using Theorem to take the limit, we get that there exists E 1) such that
| xx
lim
8.3
As with the quadratic case, we see that is an oracle satisfies property then 8.3 holds with probability Thus, we have proved Theorem 3 in its complete generality.
8.4 PROOF OF THEOREM
4 in essentially the same manner we did for Theorem and so we outline only what changes are necessary.
In this section prove Theorem
Theorem 4 I / E B(S), the hyperplanes H; are strongly zone consistent with respect to J, and 3x. E S such that f(²²)= = 0, then with probability 1 any sequence x" produced by the algorithm converges to the optimal solution of problem 6.1 Furthermore, if x² is the optimal solution, f is twice differentiable x", and the Hessian H == fxx)") is positive semidefinite, then there exists E (0, 1) such that with probability 1,
| x S.p. p.
lim inf
1x x:" 1
To prove Theorem 4 we need to analyze only what goes wrong if the algorithm "forgets" all of the old constraints. First, consider the proof in the case that converge the optimal solution. Then, steps 1,2, and 3 are completely unaffected by forgetting old constraints. The only step that is affected step 4. In previous proof, we argued that if for some inactive constraint a,, 2; is non-zero infinitely often, then we projected onto this constraint infinitely often. In our present setting, we cannot conclude this directly as z! > 0 does not imply that we remember a; on the vth iteration. However, due to property - we know that Q returns a; with probability at least 7. Thus, again using the Borel Cantelli Lemmas, we see that we have a; infinitely often and this iteration converges to optimal.
To prove the second part of the theorem, we recall from Theorem 6 that we only need to analyze the case when is quadratic function. Indeed, the only place where used the fact that remembered old constraints was in the proof of Theorem 5 5 which we needed to remember old project onto the constraint a, that is furthest
constraints guarantee that during the yth iteration from x" among those constraints for which 2 2 > O. We cannot guarantee that this happens always but we guarantee that it happens infinitely often.
Therefore, the conclusion of Theorem 5 holld infinitely often instead of for the tail of the sequence and we replace the limit with limit infimum to obtain the desired result.
26

---

Under review as a conference paper at ICLR 2019
9 APPLICATION DETAILS
All code, data, and outputs from the experiments be found at /ttp:p::::/ww..//////s http:://wwwwddoppo...ooo com/ sh/ hh/1g5nnhi44
All code was written in
Julia 1.1.0 and run Google Cloud Compute instances.
9.1
METRIC NEARNESS
Convergence Criterion.
One variant the metric nearness problem is the decrease only variant, which we are not allowed to increase the distances and must only decrease them. This problem can solved in O time by calculating the all pairs shortest path metric Gilbert & Jain (017). Given x" as input, let 6" be the optimal decrease only metric. We ran these experiments until
x 22112
Implementations.
We implemented the algorithm from Brickell et al. (2088) We made small modification that improves the running time. In Brickell et al. (2008), it is recommended that we store the dual variable sparse vector. However, as we do not want the overhead of handling sparse vectors, store as a dense vector.
Algorithm ! was implemented with two modifications. As the oracle finds violated constraints, looks at each edge in and then decides whether there is a violated inequality with that edge. It is cleaner in theory find all such violated constraints once and then do the project and forget steps. It is, however, much more efficient in practice to do the project and forget steps for single constraint we find This approach also helps cut down on memory usage.
see from algorithm ??, when
The second modification is that once our oracle returns list of constraints (note we have already projected onto these once), we project onto our whole list of constraints again. Thus, for the constraints returned by the oracle, we project onto these constraints twice per iteration. Note this does not affect any of the convergence results for the algorithm. The pseudocode for this modification can be seen in Algorithm
Algorithm 5 Pseudocode for the implementation for Metric Nearness.
1:
I ===00 0, 20 O. Initialize z0 that f2 0.
2: while Not Converged do
3: Let d(i,j) be the weight of shortest path between nodes i and if none exists.
4:
L=
5:
for Edge e i(,j)
do if (i.jj) > d(i,j) then
6:
7:
Let P the shortest path between and j.
8:
Let C = PU ((t,))} Project onto C and update x, z.
9:
10:
if = then
11:
Add C to iu+l L" UL
12:
13:
r0+1 z0+1 Project(x",, ,", ju+1)
14:
- = Forget(I
return
Additional Test Case.
We also tested our algorithm on an additional type of random weighted complete graph. Let uy be sampled from the uniform distribution [0, 1] and viy from a standard normal, then the weight for an edge e = ij is given by
W/ 1000 ui ufg
In this case, got the following running times.
27

---

Under review as a conference paper at ICLR 2019
6000
4832
023
Number
Figure 3: The red line is the mean rumning time for the algorithm from Brickell et al. (2008). The blue line the running mean time for our algorithm. All computations were done on machine with 4 physical cores, each with 13 GB of RAM.
9.2 CORRELATION CLUSTERING
Transforming the LP. The formulation of the LP that we solve is as follows:
minimize subject
TT 1 W.f
x x MET fij Fij del. (i.j)
(9.1)
The transformation 2.2 into 9.1 has two parts. The first part is the transformation done in Veldi et al. (2019) to obtain the formulation presented in 4.1 To do this transformation define (e()) w
(e) w (e)]. Then W is diagonal matrix whose entries are given by w. Finally, we define
as follows
di - {
w (e) w (e)
otherwise
The second step of the transformation, is the relaxation from I E MET, to x E MET(G). The proof for the second now presented.
Let ((x) be a fanction whose values only depends on the values Taj for (i.j) E and consider the following constrained optimization problem.
Proposition 2,
minimize
f(x)
(9.2)
subject to E &EET(KK))
Let be the projection from MET, to MET(G) and let f(((x))) f(x). Then for any optimal solution x² to the following problem
minimize
f(x)
subject to E MET(GG)
we have that for all â E π x (x*),, ā is an optimal solution to 9.2
Proof. Here, we that if the minimizer of 4.2 and x² the minimizer of 9.2 then
f(x*) f(m((*)) 2 f(ā) f( f()
Calculating the Approximation Ratio.
W 2 E
Let à be the optimal solution 4.1 then we let I
by Veldt et al. (019), we have that
1 ++7 f is 1 R approximation to the optimal solution of 2.2 This is the formula used to caleulate
the approximation ratios reported in Tables
and
For experiments used 7 1.
28

---

Under review as a conference paper at ICLR 2019
Convergence Criterion.
We ran the experiment until the maximum violation a metric inequality was at most 0.01. However, the two algorithms, Ruggles et al. (2019) and ours, have different metric constraints. Specifically Ruggles et al. 2019) only uses all constraints that come from 3 cycles, whereas we use all cycle constraints. Theoretically both sets of constraints define the same polytope, but practically there is difference. Thus, in practice our algorithm was run to a slightly greater level convergence than the one from Ruggles al. (2019).
Implementations.
For the case when G Kn. in addition to the modifications that done for metric nearness experiment, we made two more modifications. First, we did the PROJECT and FORGET step one additional time per iteration. Second, we parallelized the oracle by running Dykstra algorithm in parallel. The pseudocode for this version of algorithm can be seen in Algorithm 6
Algorithm Pseudocode for the implementation for CC for the dense case.
I: L = 0, 20 = O. Initialize æ" so that fxx²)) = 0.
2: La the list of additional constraints. 2g = 0 (dual for additional constraints)
3: while Not Converged do
4: Let d(í,j) .) be the weight shortest path between nodes and j or oc if none exists. This found using parallel algorithm.
5:
L=
6:
for Edge i(,j) do (i, > j) then Let C = PU ((t,5)) Where P be the shortest path between and Project onto C and update x, 2.
7:
8:
9:
if' if = 0 then Add C to L.
L" U
12:
for i = 1,2 do
x", 2" + Project(x" ,2", L") L" <- Forget(L.")
14:
15:
x" 2/ t Project(x" 2n La)
16:
x. n41 = x", Lutl -L, u+1
return
For the sparse version, we made only two modifications: we used the parallel version of the oracle, and during each iteration, we did the project and forget step 75 times.
Note that for both experiments, the additional constraints that were introduced due to the transforma- tion were all projected onto once per iteration and never forgotten. The pseudocode for this version can be seen in Algorithm 7
We used the implementation provided by the authors of Veldt al. (2019) run the experiments for their algorithm.
9.3 INFORMATION THEORETIC METRIC LEARNING
The spper-parameters were set as follows: 7 = 1, u = 1, 10. The pseudocode for our algorithm
can be seen in Algorithm g The classification was done using the k nearest neighbor classifier.
29

---

Under review as a conference paper at ICLR 2019
Algorithm 7 Pseudocode for the implementation for CC for the sparse case.
1: L 0, 2
Initialize x" that fax")) = 0.
2: La is the list of additional constraints. z = 0 (dual for additional constraints)
3: while Not Converged do
4: Let d( be the weight of shortest path between nodes i and j or oc if none exists. This is
found using parallel algorithm.
5:
T= 0
6:
for Edge e = i(,j) E E do
7:
if w(( > d(i,j) then
8:
Let C' = PU ((i,5)). Where P be shortest path between and j.
9:
Add to L.
10:
L' < 1'" U U
for i 1,..., 75 do
12:
x" x²,2" ," + Project(a", 2², L') L" Forget(L""
14:
x" 22 t Project(x", 2 La) x²41 x² Lut1 L gutl
15:
22, , 2/4 2
return
Algorithm 8 Pseudocode for the Project and Forget algorithm for ITML.
1: function PFITMI(X, C, 7, 1, D)
2: XO = E-j = u for () E S and Ei = for (i,j) E D. Initialize C' 1.
3: while Not Converged do
4:
Randomly sample (i,j) from S
5: Do projection for this constraint
6: Randomly sample (i,j) from D
7:
Do projection for this constraint
return C
8: function S,
9:
(Xsto X,) = =if (i. E and = -1 (i.j) D
10:
11:
a min Aijs 2 E
~
12:
B = T-bay zij
ba
13:
Eij = =T=toaE.;
14:
Aig Xij
15:
C C + 3C(r 21)(44 (144--14))) ( CCT
30


Reviews:
[{"review_id": "SkeMSMYctS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new method for solving the metric constrained problem based on projections on cutting planes. Its main contribution comes from the \"forgetting\" part, where unnecessary constraints (that are inactive) are removed in order to keep the number of constraints manageable. \n\nPros: \n\nThe methods seem practically useful as verified in the experiments. \n\nCons: \n\nMost importantly, the paper is out of format and there exist some critical typos that need to be fixed. \n- The margin of the paper is wider than the official ICLR format. It needs to be reformatted and verified to be under 10 pages limit. \n- There seem to be multiple Latex bugs on referring the section numbers, e.g., \"see appendix refsec:genealProblem\" at bottom of page 5. \n\nThere is no theoretical guarantee on its improvement over existing methods, i.e., the forgotten constraints can reappear during optimization for multiple numbers of times. However, I think this point is not crucial given the empirical usefulness of the algorithm.\n\nMinor questions: \n- To my knowledge, cutting plane methods for the integer programming method (including Gurobi) already use an instance \"project and forget\" method, i.e., iteratively solving linear programs and then adding & removing cutting planes. See [1] for an example. Could the authors discuss the relationship between the two methods and highlight the relative difference & contribution?\n\n[1] The cutting plane method is polynomial for perfect matchings, Chandrasekaran et al., 2012\n\n========= \n\nI have checked that the authors have re-formatted the paper into a correct form. I raise my score since I think the paper is interesting and provides a practically useful algorithm.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1xchXF0tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nAuthors argue that the constraint \"x is a metric\" translate into exponentially many linear constraints, which results in to a hard to solve problem\nThe 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\n \nAuthors claim that the sequence created by their algorithm asymptotically converges to the global optimum, and show numerical superiority to baselines.\n\nMajor remarks:\n\nMy general feeling is that the paper overstates its results. The paper has some good contribution, which could be better emphasized.\n\nThe algorithm stacks multiple subroutines which are not necessarily very light. I am skeptical about the numerical efficiency of such algorithms.\n\nTheoretical 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\n\nThe algorithm starts at a stationary point of f. This itself can be nontrivial. Can authors discuss this?\n\nMinor remarks:\n\nmetric and distance to me mean the same, hence the first sentence of the intro doesn't read easily..\n\nwhat 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 \n\nThe notation L is confusing in Algo 1 MetricViolation: wasn't L the matrix defining the metric?\n\nA few typos: l. 12 Algo 1, e = (i, j), 3.2 \"global optimum [remove solution].\"\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "B1l78StUcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of optimizing convex functions under metric constraints. The main challenge is that expressing all metric constraints on n points requiries O(n^3) constraints. The paper proposes a “project and forget” approach which is essentially is based on cyclic Bregman projections but with a twist that some of the constraints are forgotten. The proof of convergence of this method is given, but no explicit bound on the number of iterations. While the general method doesn’t appear to be particularly novel, I found it quite impressive that the authors were able to solve 10x larger instances of weighted correlation clustering than the previous work. While from a theoretical perspective this work is hardly very exciting, the practical results are rather interesting. Other applications to the metric nearness and metric learning problems are also given. \n\n\nComments:\n-- The paper is full of typos and needs to be proofread by a native English speaker.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Quoting from Reviewer2: "The paper considers the problem of optimizing convex functions under metric constraints. The main challenge is that expressing all metric constraints on n points requiries O(n^3) constraints. The paper proposes a “project and forget” approach which is essentially is based on cyclic Bregman projections but with a twist that some of the constraints are forgotten."  The reviewers were split on this submission, with two arguing for weak acceptance and one arguing for rejection.  Purely based on scores, this paper is borderline.  It was pointed out by multiple reviewers that the method is not very novel.  In particular it effectively works as an active set method.  It appears to be very effective in this setting, but the basic algorithm does not differ in structure from any active set method, for which removal of inactive constraints is considered standard (see even the wikipedia page on active set methods).
Decision: Reject