Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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. 


Comments:
-- The paper is full of typos and needs to be proofread by a native English speaker.

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper presents an algorithm for optimizing an function f under the constraints that the square matrix variable x represents "metric". In this context, this means that we have also observed a graph G with n vertices, and x is of size n by n, x(i, j) < x(i, e) + x(e, j) if i ~ e and j ~ e are adjacent: this is a generalized for of triangle inequality.
Authors argue that the constraint "x is a metric" translate into exponentially many linear constraints, which results in to a hard to solve problem
The algorithm they propose to tackle this (Algorithm 1) has two subroutines that are shown in Algorithm 2 (Forget and Project). The Project subroutine itself is a projection onto a convex set according to a Bregman divergence, which is not trivial. In this paper I understand that authors only consider metrics of type x' L x where L = C'C >0 is psd
 
Authors claim that the sequence created by their algorithm asymptotically converges to the global optimum, and show numerical superiority to baselines.

Major remarks:

My general feeling is that the paper overstates its results. The paper has some good contribution, which could be better emphasized.

The algorithm stacks multiple subroutines which are not necessarily very light. I am skeptical about the numerical efficiency of such algorithms.

Theoretical results are stated asymptotically while interpreted in the text as finite steps results: page 5, after Corollary 1., read "The algorithm spends the first few iterations ..." in this case, a theoretical result should support the claim

The algorithm starts at a stationary point of f. This itself can be nontrivial. Can authors discuss this?

Minor remarks:

metric and distance to me mean the same, hence the first sentence of the intro doesn't read easily..

what is \cal A line 5 of Algorithm 1? It seems to be a "list of hyperplanes" according to the previous text, but it is unclear to me how to build it algorithmically 

The notation L is confusing in Algo 1 MetricViolation: wasn't L the matrix defining the metric?

A few typos: l. 12 Algo 1, e = (i, j), 3.2 "global optimum [remove solution]."


review_title: Official Blind Review #775

final_score: rating: 6: Weak Accept
review_content: 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. 

Pros: 

The methods seem practically useful as verified in the experiments. 

Cons: 

Most importantly, the paper is out of format and there exist some critical typos that need to be fixed. 
- 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. 
- There seem to be multiple Latex bugs on referring the section numbers, e.g., "see appendix refsec:genealProblem" at bottom of page 5. 

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

Minor questions: 
- 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?

[1] The cutting plane method is polynomial for perfect matchings, Chandrasekaran et al., 2012

========= 

I 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.
review_title: Official Blind Review #3

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