Learning Mahalanobis Metric Spaces via Geometric Approximation Algorithms
Authors: Diego Ihara
Neshat Mohammadi
Anastasios Sidiropoulos
Venue:  (2020)
Keywords: Metric Learning
Geometric Algorithms
Approximation Algorithms

Abstract: Learning Mahalanobis metric spaces is an important problem that has found numerous applications. Several algorithms have been designed for this problem, including Information Theoretic Metric Learning (ITML) [Davis et al. 2007] and Large Margin Nearest Neighbor (LMNN) classification [Weinberger and Saul 2009].  We consider a formulation of Mahalanobis metric learning as an optimization problem,where the objective is to minimize the number of violated similarity/dissimilarity constraints.  We show that for any fixed ambient dimension, there exists a fully polynomial time approximation scheme (FPTAS) with nearly-linear running time.This result is obtained using tools from the theory of linear programming in low dimensions. We also discuss improvements of the algorithm in practice, and present experimental results on synthetic and real-world data sets. Our algorithm is fully parallelizable and performs favorably in the presence of adversarial noise.

Under review as a conference paper at ICLR 2020
LEARNING MAHALANOBIS METRIC SPACES VIA GEO- METRIC APPROXIMATION ALGORIHTMS
Anonymous authors Paper under double-blind review
ABSTRACT
Learning Mahalanobis metric spaces is an important problem that has found numer- ous applications. Several algorithms have been designed for this problem, including Information Theoretic Metric Learning (ITML) [Davis et al. 2007] and Large Mar- gin Nearest Neighbor (LMNN) classification [Weinberger and Saul 2009]. We consider a formulation of Mahalanobis metric learning as an optimization problem, where the objective is to minimize the number of violated similarityddissimlaartg constraints. We show that for any fixed ambient dimension, there exists a fully polynomial-time approximation scheme (FPTAS) with nearly-linear running time. This result is obtained using tools from the theory of linear programming in low dimensions. We also discuss improvements the algorithm in practice, and present experimental results synthetic and real-world data sets. Our algorithm is fully parallelizable and performs favorably in the presence adversarial noise.
INTRODUCTION
Learning metric spaces is fundamental computational primitive that has found numerous applications and has received significant attention in the literature. We refer the reader to Kulis et al. 20 [i] and Tian (2018) for detailed exposition and discussion of previous work. At the high level, the input to metric learning problem consists of some universe of objects X, together with some similarity information on subsets of these objects. Here, we focus on pairwise similarity and dissimilarity constraints. Specifically, we are given S, D (*), which are sets of pairs of objects that are labeled as similar and dissimilar respectively. We are also given some u, > O. and we seek to find a mapping f X into some target metric space (Y. p). such that for all x, y
pl p(f(x), f())) &
and for all x, D.
f((()) >
In the case of Mahalanobis metric learning, have X c Rd with [X| for some d e N, and the mapping f gd Rd is linear. Specifically, we seek to find a matrix G Rdddd such that for all (p. 4) S, we have
GG Ggl2 $ u
(1)
and for all {p. 4} E D, we have
Gp Ggl2 l.
1.1 OUR CONTRIBUTION
In general, there might not exist any G that satisfies all constraints of type 1 and We are thus interested in finding solution that minimizes the fraction of violated constraints, which corresponds to maximizing the accuracy of the mapping. We develop (1 + -)-approximation algorithm for optimization problem of computing a Mahalanobis metric space of maximum accuracy, that runs in near-linear time for any fixed ambient dimension d E N. This algorithm is obtained using tools from geometric approximation algorithms and the theory of linear programming in small dimension. The following summarizes our result.

---

Under review as a conference paper at ICLR 2020
Theorem 1.1. For any d N, E O, there exists randomized algorithm for learning d-dimensional Mahalanobis metric spaces, which given an instance that admits a mapping with accuracy r", computes mapping with accuracy at least r E, in time d' d(())((lo //)))) with high probability.
The above algorithm can be extended to handle various forms of regularization. We also propose several modifications of our algorithm that lead to significant performance improvements in practice. The final algorithm is evaluated experimentally on both synthetic and real-world data sets, and is compared against the currently best-known algorithms for the problem.
1.2 RELATED WORK
Several algorithms for learning Mahalanobis metric spaces have been proposed. Notable examples include the SDP based algorithm of Xing et al. Xing et al. (2003), the algorithm of Globerson and Roweis for the fully supervised setting Globerson and Roweis (2006), Information Theoretic Metric Learning (ITML) by Davis et al. Davis et al. (2007). which casts the problem particular optimization minimizing LogDet divergence, as well as Large Margin Nearest Neighbor (LMNN) by Weinberger et al. Weinberger et al. (2006), which attempts to learn metric geared towards optimizing k-NN classification. We refer the reader to the surveys Kulis et al. (2013); Li and Tian (2018) for detailed discussion of previous work. Our algorithm differs from previous approaches in that it seeks to directly minimize the number of violated pairwise distance constraints, which is highly non-convex objective, without resorting to convex relaxation of the corresponding optimization problem.
1.3 ORGANIZATION
The rest of the paper organized follows. Section[ the main algorithm and the proof of Theorem 1.] Bection3dissusse practical improvements used in the implementation of the algorithm. Section presents the experimental evaluation.
2 MAHALANOBIS METRIC LEARNING AS AN LP-TYPE PROBLEM
In this Section we present approximation scheme for Mahalanobis metric learning in d-dimensional Euclidean space, with nearly-linear running time. We begin by recalling some prior results on the class of LP-type problems, which generalizes linear programming. We then show that linear metric learning can be cast as an LP-type problem.
2.1 LP-TYPE PROBLEMS
Let us recall the definition of LP-type problem. Let be set of constraints, and let 2 R o (-00, +00), such that for any G = H, (/G) is the value of the optimal solution of the instance defined by G. We say that (H, w) defines an I.Pttpe problem if the following axioms hold:
(A1) Monotonicity, For any F G = H. we have ae( F) & w w(G).
(A2) Locality. For any F = G S H. with -00 < w(F) w(G), and any E H, if w(G) < w(G u (h)), then w(
(F {h))-
More generally, we say that (H. w) defines an type problem on some H' H. when conditions (A1) and (A2) hold for all F P
subset = called basis if w(B) B) - and w/ (B') < wr (B) for any proper subset B' ş B.
A basic operation is defined to be one of the following:
(BO) Initial basis computation. Given some G = H. compute any basis for G.
(B1) Violation test. For some h H and some basis B H. test whether w (h3) w(B) (in other words, whether B violates h).
(B2) Basis computation. For some h H and some basis B H. compute basis of B (h))
2

---

Under review as a conference paper at ICLR 2020
2.2 AN LP-TYPE FORMULATION
We now show that learning Mahalanobis metric spaces can be expressed as an LP-type problem. We first note that we can rewrite ! and 2 as
(p AT 9) u²
(3)
and
( -- A(p 9) - E
(4)
where A GT is positive semidefinite.
We define = (0, 1 x (2²). where for each (0, {p. q)) E H. we have a constraint of type 3 and for every (1, (p.q]) E H. we have constraint of type (4). Therefore, for any set of constraints F S H. we may associate the set of feasible solutions for with the set Ar of all positive semidefinite matrices A R=xx, satisfying (3 and (4 for all constraints in F.
Let w 2 - R, such that for all F E H. we have
w F) = inf Ar AF Ar
if Ar * Ø if Ar Ø
where r Rdd is a vector chosen uniformly at random from the unit sphere from some rotationally- invariant probability measure. Such vector can be chosen, for example, by first choosing some r' Rdd where each coordinate is sampled from the normal distribution N/ 1), and setting r ///lr'
Lemma 2.1. When w is chosen as above, the pair (H, w) defines an LP-type problem of combina- torial dimension Odd), with probability Moreover, for any n 0, if each ri is chosen using (logn) bits of precision, then for each F = H. with [F) the assertion holds with high probability.
Proof. Since adding constraints to feasible instance can only make it infeasible, it follows that satisfics the monotonicity axiom (AI).
We next argue that the locality axion (A2) also holds, with high probability. Let F = G S H. with -OC < (FF) = w()), and let E H. with w(G) G) < w(G u (h)). Let Ar AF and Ag E Ag be some (not necessarily unique) infimizers of w(( (A),, when A ranges in AF and Ag respectively. The set Ap, viewed as a convex subset of TRd is the intersection of the SDP cone with n half-spaces, and thus AF has at most facets. There are at least two distinct infimizers for w (Ac). when Ag Ac. only when the randomly chosen vector r' is orthogonal to a certain direction, which occurs with probability O. When each entry of r is chosen with log n bits of precision, the probability that orthogonal to any single hyperplane at most 2 c clogo n n: the assertion follows by a union bound over facets. This establishes that axiom (A2) holds with high probability.
remains to bound the combinatorial dimension, K. Let F S H be a set of constraints. For each A Ap, define the ellipsoid
EA = fue Rd :|Av||2 = =1. Ar, with EA Ex. and A GTG A' = G we have that for all p,q e Rd,
For any [Gp Ggla = (p- q)² A(p -Q) (p 9) A'(p q) = IG'p G'ql2- Therefore in order to specify linear transformation G, up an isometry, it suffices to specify the ellipsoid EA.
A' E A,
Each {p. q) E corresponds to the constraint that the point (p- 9) must lie in EA. Similarly each {p. q) 'D corresponds to the constraint that the point (p 1 q)/l must lie either on the boundary or the exterior of Ex. Any ellipsoid in Rd is uniquely determined by specifying most (d+ 31+32 = ( distinct points on its boundary (see Welzi (1911): Chazelle (200)). Therefore, each optimal solution can be uniquely specified as the intersection of at most (dd) constraints, and thus the combinatorial dimension is (dd).
Lemma 2.2. Any initial basis computation (BO), any violation test (B1), and any basis computation (B2) can be performed in time ((1).
3

---

Under review as a conference paper at ICLR 2020
Proof. The violation test (B1) can be performed by solving SDP compute w (B), and another to compute w(B B u {h]). By Lemma 2.1 the combinatorial dimension is O(d²), thus each SDP has ((d) constraints, and be solved in time d0(1)
The basis computation step (B2) can be performed starting with the set of constraints B o {h}, and iteratively remove every constraint whose removal does not decrease the optimum cost, until we arrive at minimal set, which is a basis. In total, we need to solve most d SDPs, each of size O(P), which can be done in total time do(1).
Finally, by the choice of ue any set containing single constraint in S is valid initial basis.
2.3 ALGORITHMIC IMPLICATIONS
Using the above formulation of Mahalanobis metric learning as an LP-type problem, we can obtain our approximation scheme. Our algorithm uses as a subroutine an exact algorithm for the problem (that is, for the special case where we seek to find mapping that satisfies all constraints). We first present the exact algorithm and then show how it can be used to derive the approximation scheme.
obtained simple randomized linear-time algorithm for the minimum enclosing ball and minimum enclosing ellipsoid problems. This algorithm naturally extends to general LP-type problems (we refer the reader to Har- Heled (2011): Chazelle (2000) for further
An exact algorithm. Welzi (991)
details).
With the interpretation of Mahalanobis metric learning as an L.P-yppe problem given above, we thus obtain a linear time algorithm for Rd, for any constant E N. The resulting algorithm on a set of constraints F = H. is implemented by the procedure Exact-LPTML(E* Ø), which is presented in Algorithm The procedure LPTML(F:; B) takes as input sets of constraints F, B S H. It outputs a solution A e Raxd to the problem induced by the set of constraints F u B, such that all constraints in B are tight (that is, they hold with equality): no such solution solution exists, then returns nil. The procedure Basic-LPTML((B computes LPTML [2; B). The analysis of Welzl (1991) implies that when Basic-LP (B) is called, the cardinality of B is at most the combinatorial dimension, which by Lemma 2.1 is (dd). Thus the procedure Basic-LPTML.
be implemented using one
initial basis computation (BO) and (d²) basis computations (B2), which by Lemma 2.2 takes total
time (11)
Algorithm 1 An exact algorithm for Mahalanobis metrie learning.
procedure Exact-LPTML(FF B) if = Ø then
A Basic-LPTML(B3)
else
choose h F uniformly random
A < Exact-LPTML( - {h})
if A violates then
A : EXacttLPTML(FF - (h); (N)
end if
end if return end procedure
An (1 + E) -approximation algorithm. is known that the above exact linear-time algorithm leads to an nearly-linear-ting approximation scheme for LP-type problems. This is summarized in the following. We refer the reader Har-Peled (20TT) for a more detailed treatment.
Lemma 2.3 (Har- (2011), Ch. 15). Let A be some LP-type problem of combinatorial dimension > O, defined by some pair (H, w), and let e > O. There exists a randomized algorithm which given some instance F = H. with [F| n, outputs some basis B F. that violates most (1 + E)k constraints in F. such that w( () & (uBB),, any basis B' violating at most k constraints in F, in
time O (1 (o + n2 + n min
log 1og-12n
ke "g" 1) (1 (1)). where to is the time needed to compute
4

---

Under review as a conference paper at ICLR 2020
an arbitrary initial basis of A. and f1, t2, and upper bounds the time needed perform the basic operations (BO), (B1) and (B2) respectively. The algorithm succeeds with high probability.
For the special case of Mahalanobis metric learning, the corresponding algorithm is given Algorithm 2 The approximation guarantee for this algorithm is summarized in 1.1 We can now give the proof of our main result.
Proof of Theorem
1.7
Follows immediately by Lemmas 2.2 and 2.3
Algorithm 2 An approximation algorithm for Mahalanobis metric learning.
procedure LPTML(F)
for i 0 to logi+ n do
p (1+
for j
log 0(6)) logo(d)
do
subsample Fj S F. where each element is chosen independently with probability
Aij (XaC-L))MML(())
end for end for
return a solution out of (Aighs violating the minimum number of constraints in F end procedure
Regularization. We now argue that the LP-type algorithm described above can be extended to handle certain types of regularization on the matrix A. methods based on convex optimization, introducing regularizers that are convex functions can often be done easily. In our case, cannot directly introduce a regularizing term in the objective function that is implicit in Algorithm 2 More specifically, let cost(A, A) denote the total number of constraints of type (3) and (4) that A vIolates. Algorithm
2 approximately minimizes the objective function cost A)). A natural regularized version of Mahalanobis metric learning is to instead minimize the objective function
cost' (A) cost( A) + 1) reg(A)
for some 1) > 0, and regularizer reg(A). One typical choice is reg( tr( (AC) for some matrix C E Rd the case C = I corresponds to the trace norm (see Kulis et al. (2013)) We can extend the Algorithm 2 to handle any regularizer that can be expressed as linear function on the entries of A. such as tr( A). The following summarizes the result.
Theorem 2.4. Let (e)(A) be linear function on the entries of A, with polynomially bounded coefficients. For any de E N, > O, there exists a randomized algorithm for learning d-dimensional Mahalanobis metric spaces, which given an instance that admits a solution Ao with cost'(An) = ct. computes a solution A with cost' (A) & (1+5)c", in time m(log n/c O(d), with high probability.
Proof. If 7 < E", for sufficiently large constant / > O, since the coefficients in reg(A) are poly- nomially bounded, it follows that the largest possible value of 1 reg(A) is O(s), and can thus be omitted without affecting the result. Similarly, if > (1/c)n", for sufficiently large constant t' > since there are at most (?) constraints, it follows that the term cost A) can be omitted form the objective. Therefore,
may assume w.l.o.g. that reg(Av) [(0(), (1/E)n We can guess some: = (log n + log( log(1/E)), 1/=)), such that reg(An) E ((1+e)* <- (11+e) We modify the SDP used in the proof of Lemma 2.2 by introducing the constraint reg( A) (1 E).. Guessing the correct value requires O(log n + log(1/E)) executions of Algorithm which implies the running time bound.
PRACTICAL IMPROVEMENTS AND PARALLELIZATION
We now discuss some modifications of the algorithm described in the previous section that significantly improve its performance in practical scenarios, and have been integrated in our implementation.
5

---

Under review as a conference paper at ICLR 2020
Move-to-front and pivoting heuristics. We use heuristics that have been previously used in algorithms for linear programming Seidel (190)); Clarkson (1995). minimum enclosing ball in R Megiddo 1983). minimum enclosing ball and ellipsoid is R"," for any fixed d e N Welzi (191)) as well as in fast implementations of minimum enclosing ball algorithms Gärtner (1999). The move-to-front heuristic keeps ordered list of constraints which gets reorganized as the algorithm runs; when the algorithm finds a violation, it moves the violating constraint to the beginning of the list of the current sub-problem. The pivoting heuristic further improves performance by choosing to add to the basis the constraint that is "violated the most". For instance, for similarity constraints, we pick the one that is mapped the largest distance greater than u, for dissimilarity constraints, we pick the one that is mapped to the smallest distance less than L.
Approximate counting. The main loop of Algorithm 2 innvllves counting the number of violated constraints in each iteration. In problems involving a large number of constraints, we use approximate counting by only counting the number of violations within a sample of Ollog 1/E) constraints. We denote by LPTML; for the version of the algorithm that performs a total of iterations of the inner loop.
AlgoritmmBinvolee
Early termination. A bottleneck of Algorithm stems from the fact that the inner loop needs to be executed for log ((d") iterations. In practice, we have observed that significantly smaller number of iterations is needed to achieve high accuracy.
Parallelization. Algorithm 2 consists of several executions of the algorithm Exact-LPTML on independently sampled sub-problems. Therefore, Algorithm 2 can trivially be parallelized by distributing a different set sub-problems to each machine, and returning the best solution found overall.
EXPERIMENTAL EVALUATION
We have implemented Algorithm 2 incorporating the practical improvements described in Section 3 and performed experiments on synthetic and real-world data sets. Our LPTML implementation and documentation can found at the supplementary materia We now describe the experimental setting and discuss the main findings.
4.1 EXPERIMENTAL. SETTING
Classification task. Each data set used in the experiments consists of set of labeled points in Rd. The label each point indicates class, and there is constant number of classes. The set of similarity constraints S (respt. dissimilarity constraints D) is formed by uniformly sampling pairs of points in the same class (resp. from different classes). We use various algorithms to learn a Mahalanobis metric for labeled input point set in Rdd, given these constraints. The values and e are chosen as the 90th and 10th percentiles of all pairwise distances. We used 2-fold cross-valle cross-validation: At the training phase learn Mahalanobis metric, and in the testing phase we N--N classification, with k = 4, to evaluate the performance.
Data sets.
We have tested our algorithm on the following synthetic and real-world data sets:
1. Real-world: We have tested the performance of our implementation on the Iris, Wine, Ionosphere and Soybean data sets from the UCI Machine Learning Repository
2. Synthetic: Next, we consider synthetic data set that is constructed by first sampling set of 100 points from mixture two Gaussians in IR? with identity covariance matrices, and with means (-3, 0) and (3, 0) respectively; we then apply linear transformation that stretches the axis by a factor of 40. This linear transformation reduces the accuracy of k--N on the underlying Euclidean metric with & 4 from to 0.68.
AA copy our implementation is also available http:///wooottttaaoo.////o/o///r wtt.eeew...ggge.e.eeeaeeeaaoolae ww https::/arrchis iss uci wwc.i.edummlic
Xqa Bqyh8k CoRGach hus.shshh..ccddppppppsssshhr.nn.

---

Under review as a conference paper at ICLR 2020
3. Synthetic Adversarial Noise: We modify the above synthetic data set by introducing small fraction of points in an adversarial manner, before applying the linear transformation. Figure
3b depicts the noise added five points labeled one of the classes, and sampled from Gaussian with identity covariance matrix and mean 1000 0) (Figure 3ap.
Algorithms. We compare the performance of our algorithm against ITML and LMNN. We used the implementations provided by the authors of these works, with minor modifications.
4.2 RESULTS
Algorithm 2 minimizes the number of violated pairwise distance constraints. It is interesting to examine the effect of this objective function on the accuracy of k-NN classification. Figure D depicts this relationship for the Wine data set. We observe that, in general, the number of iterations of the main loop of LPTML increases, the number of violated pairwise distance constraints decreases, and the accuracy of k--N increases. This phenomenon remains consistent when first perform PCA to d = 4, 8, 12 dimensions.
Accuracy.
Fraction of violated constraints
0.5
4
Accuracy of k-NN
0.8
d
12
0.6
0.4
d = 4
11
0.4
+ d = 8
0.3
+ d = 12
0.2
10
20
30
40
50
10
20
30
40
50
Iterations
Iterations
(a) Fraction of violated constraints
(b) Accuracy
Figure Fraction of violated constraints (left) and accuracy (right) as the number of iterations of LPTML increases (average over 10 executions). Each curve corresponds to the Wine data reduced to dimensions using PCA.
Comparison to ITML and LMNN. We compared the accuracy obtained by LPTML,, for t = 2000 iterations, against ITML and LMNN. Table [ summarizes the findings on the real-world and data sets and the synthetic data set without adversarial noise. We observe that LPTML achieves accuracy that comparable ITML and LMNN.
We observe that LPTML outperforms ITML and LMNN on the Synthetic + Adversarial Noise data set. This is due the fact that the introduction of adversarial noise causes the relaxations used in ITML and LMNN to be biased towards contracting the æ-axis. In contrast, the noise does not "fool" LPTML because only changes the optimal accuracy by small amount. The results are summarized in Figure
Data Iris
ITML
LMNN
LPTML:=2000
0.96 + 0.01
0.96 + 0.02
0.94 + 0.04
Soybean
0.95 0.04
0.96 + 0.04
0.90 + 0.05
Synthetic
0.97 0.02
1.00 + 0.00
1.00 + 0.00
Table 1: Average accuracy and standard deviation over 50 executions of ITML, LMNN and LPTML.
The effeet of dimension. The running time of LPTML grows with the dimension d. This is caused mostly by the fact that the combinatorial dimension of the underlying LP-type problem is (d2), and thus performing each basic operation requires solving SDP with O(d²) constraints.
7

---

Under review as a conference paper at ICLR 2020
Accuracy of K- NN
0.8
0.6
Euclidean
ITML
LMNN
LPTML:-100
I Without noise With noise
Figure Accuracy in a syntetic data set scenario where small fraction of points were placed adversarially. See Figure 3a
10
100
100
0
-100
-100
10
100
50
100
-50
-125
1005
5
5
(a) Noisy data
(b) After LPTML
(c) After LPTML (magnified view)
Figure 3: Synthetic Adversarial Noise scenario. On the left, the data set before learning. The center image shows the correct transformation recovered by LPTML. On the right, magnified view of the recovered data.
Figure 4 (appearing in the Appendix) depicts the effect of dimensionality in the running time, for t 100. ... 2000 iterations of the main loop. The data used is Wine after performing PCA dimensions, for d = 2....,13. 13.
Parallel implementation. We implemented massively parallel version of LPTML in the MapRe- duce model. The program maps different cub-problemss of the main loop of LPTML to different machines. In the reduce step, keep the result with the minimum number of constraint violations. The implementation uses the mrjob Yelp and Contributors (2019) package. For these experiments, we used Amazon cloud computing instances of type m44 m4.xlarge, AMI 5.20.0 and configured with Hadoop. As expected, the training time decreases as the number available processors increases (Figure 5 the Appendix). All technical details about this implementation can be found in the parallel section of the documentation of our code.
REFERENCES
B. Chazelle. The discrepancy method: randomness and complexity. Cambridge University Press, 2000.
K. L. Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM (JACM), 42(2):488-4)) 499, 1995.
V. Davis, B. Kulis, Jain, S. Sra, and I. S. Dhillon. Proceedings of the 24th international conference on Machine learning, pages 209-216 ACM, 2007.
metric learning. In
B. Gärtner. Fast and robust smallest enclosing balls. In European Symposium on Algorithms, pages 325-338. Springer, 1999.
8

---

Under review as a conference paper at ICLR 2020
A. Globerson and S. T. Roweis. Metric learning by collapsing classes. In Advances in neural information processing systems, pages 451-458, 2006.
S. Har-Peled. Geometric approximation algorithms. Number 173, American Mathematical Soc., 2011.
B. Kulis al. Metric learning: A survey. Foundations and Trends( in Machine Learning, 5(4): 287-364, 2013.
D. Li and Y. Tian. Survey and experimental study metric learning methods. Neural Networks, 105:447-462, 2018.
N. Megiddo. Linear-time algorithms for linear programming in r"3 and related problems. SIAM journal computing, 12(4):759-776, 1983.
R. Seidel. Linear programming and convex hulls made easy. In Proceedings of the sixth annual symposium on Computational geometry, pages 211-215. ACM, 1990.
K. Q. Weinberger, J. Blitzer, and L. K. Saul. Distance metric learning for large margin nearest neighbor classification. In Advances in neural information processing systems, pages 1473-1480, 2006.
E. Welzl. Smallest enclosing disks (balls and ellipsoids). In New results and new trends in computer science, pages 359-370. Springer, 1991.
E. P. Xing, M. I. Jordan, J. Russell, and A. Y. Ng. Distance metric learning with application to clustering with side-information. Advances neural information processing systems, pages 521-528, 2003.
Yelp and Contributors. Mrjob library, 2019. URL http://pythohhostee..oo///oo v0.6.8.dvvO.

---

Under review as a conference paper at ICLR 2020
A
ADDITIONAL FIGURES
1,000
LPTML
LPTML 5500 500
Rumning time (see)
LPTML 1000
LPTML 1500
LPTML 22000
500
0
2
4
5
6
7
8
10
11 12 13
Dimension d
Figure 4: Average running time of 10 executions of LPTML at different levels of dimensionality reduction using PCA on the Wine data set. Each curve corresponds LPTML limited to iterations.
Ionosphere
Running time (sec)
Soybean
4,000
Wine
3,000
2,000
1,000
1
2
4
Number of machines
Figure 5: Running time for parallel LPTML on an increasing number of machines (average over 10 executions).
10


Reviews:
[{"review_id": "ryxFcwpnKr", "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": "This paper discusses the following problem. Given a set X \\subset R^d of points, sets S, D of pairs (S and D denoting similar and dissimilar pairs), numbers u, l, find a matrix G such that\n- for all pairs (p, q) \\in S: ||Gp - Gq|| \\leq u, and\n- for all pairs (p, q) \\in D: ||Gp - Gq|| \\geq l.\n\nNote that such a matrix G may not exist for a given input instance (X, S, D, u, l). So, the relevant problem is maximising the number of constraints. The paper gives an (1+\\eps)-approximation algorithm for the maximisation problem. The main idea is defining an LP-type problem and then using a previous result of Har-peled. Some experimental results for a heuristic version are given and compared against other Mahalanobis distance learning algorithms (that may or may not be defined as a maximisation problem). I think the paper ports an interesting result from LP-type problems into the context of distance learning that people may find interesting and may encourage further work.\n\nOther comments: \n1. I did not find any comment about the computational hardness of the problem. It is always good to the hardness of a problem before evaluating an approximation algorithm for the problem.\n2. It will be good to define “accuracy” before using it in Theorem 1.1.\n3. Did you define combinatorial dimension before using this in Lemma 2.1?\n4. What is Exact-LPTML(.) in line 6 of Algorithm 1. The function call should take two inputs.\n5. When you say that your algorithm is an FPTAS I think you are assuming that the dimension d is a constant. It will be good to make this clear.\n6. It will good to know what results for minimising the number of constraints are known from past work. The paper mentions some references. It will be much easier if the results that are known about this problem is clearly stated.", "extra_scores": {"experience_assessment": "I do not know much about 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": {}}, {"review_id": "H1xwygViFB", "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 proposes a method to handle Mahalanobis metric learning thorough linear programming. The authors consider the specific setup where examples are labelled as similar or dissimilar and the task is to find a mapping such that the feature-space distance between examples is i) smaller than a certain value if the examples are labelled as 'similar' and ii) greater than a possibly different value if the examples are labelled as 'dissimilar'. Arguments from the theory of linear programming are leveraged to define exact and approximated algorithms.\n\nI would tend to reject the paper because I do not fully understand where is where is the main novelty.  Transforming the problem into a linear programming does not look a very complicated step given the specific setup considered in the paper. Moreover, it is not clear enough if there are computational or theoretical gains in following the proposed approach instead of applying other existing methods. Especially because the provided experiments seem to show that there is no improvement  in the accuracy, the authors should have spent some more words  to motivate their strategy.\n\nQuestions:\n\n- Are there any theoretical guarantees for the proposed approximation? Is the proposed approximation strategy completely new or similar approaches have been already applied to slightly different setups?\n\n- What are the key differences between the proposed method and with other convex approximations for learning Mahalanobis metrics? As the experimental performance of the proposed approach and other existing methods, what are the net advantages to be associated with the geometric approximation?\n\n- Why is the approximation needed?\n\n- In the proof, why is it true that, for a given solution, adding a constraint implies this constraint is not satisfied? \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1lULCyZ5r", "reviewer": "AnonReviewer3", "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": "This paper study the problem of Mahalanobis Metric Spaces learning, which is formulated as an optimization problem with the objective of minimizing the number of violated similarity/dissimilarity constraints. \n\nI am not an expert in this subarea. From what I have read, the method is based on sound theory and outperforms some classical methods, including ITML and LMNN on several standard data sets. However it is unclear to me what is the state-of-the-art of this field from this paper and its novelty. \n\nSome recent papers might worth discussing and comparing with, e.g.,\nVerma and Branson, Sample Complexity of Learning Mahalanobis Distance Metrics, NIPS2015\nYe et al. Learning Mahalanobis Distance Metric: Considering Instance Disturbance Helps. IJCAI\n\nIn the proof for Lemma2.1., why “adding constraints to a feasible instance can only make it infeasible”? \n\nIn Figure 4, why the running time is not a monotonic curve as the dimension increases?\n\nThe conclusion of the paper is missing. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this 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: The paper proposes a method to handle Mahalanobis metric learning thorough linear programming.

All reviewers were unclear on what novelty of the approach is compared to existing work.

I recommend rejection at this time, but encourage the authors to incorporate reviewers' feedback (in particular placing the work in better context and clarifying the motivations) and resubmitting elsewhere.


Decision: Reject