Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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. 

I 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. 

Some recent papers might worth discussing and comparing with, e.g.,
Verma and Branson, Sample Complexity of Learning Mahalanobis Distance Metrics, NIPS2015
Ye et al. Learning Mahalanobis Distance Metric: Considering Instance Disturbance Helps. IJCAI

In the proof for Lemma2.1., why “adding constraints to a feasible instance can only make it infeasible”? 

In Figure 4, why the running time is not a monotonic curve as the dimension increases?

The conclusion of the paper is missing. 

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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
- for all pairs (p, q) \in S: ||Gp - Gq|| \leq u, and
- for all pairs (p, q) \in D: ||Gp - Gq|| \geq l.

Note 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.

Other comments: 
1. 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.
2. It will be good to define “accuracy” before using it in Theorem 1.1.
3. Did you define combinatorial dimension before using this in Lemma 2.1?
4. What is Exact-LPTML(.) in line 6 of Algorithm 1. The function call should take two inputs.
5. 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.
6. 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.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 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.

I 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.

Questions:

- 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?

- 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?

- Why is the approximation needed?

- In the proof, why is it true that, for a given solution, adding a constraint implies this constraint is not satisfied? 


review_title: Official Blind Review #1

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