Project and Forget: Solving Large Scale Metric Constrained Problems
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.
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.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Project and Forget: Solving Large Scale Metric Constrained Problems
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.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



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