4.7 Article

Project and Forget: Solving Large-Scale Metric Constrained Problems

Journal

JOURNAL OF MACHINE LEARNING RESEARCH
Volume 23, Issue -, Pages 1-54

Publisher

MICROTOME PUBL

Keywords

Large Scale Convex Optimization; Metric Constrained Optimization; Metric Learning; Correlation Clustering

Funding

  1. NSF [DMS-2027277]

Ask authors/readers for more resources

This paper introduces a method called "PROJECT AND FORGET" for solving highly constrained convex optimization problems. The authors provide a theoretical analysis and demonstrate through experiments that this method converges to the global optimal solution with a linear rate of convergence.
Many important machine learning problems can be formulated as highly constrained convex optimization problems. One important example is metric constrained problems. In this paper, we show that standard optimization techniques can not be used to solve metric constrained problem.To solve such problems, we provide a general active set framework, called PROJECT AND FORGET, and several variants thereof that use Bregman projections. PROJECT AND FORGET is a general purpose method that can be used to solve highly constrained convex problems with many (possibly exponentially) constraints. We provide a theoretical analysis of PROJECT AND FORGET and prove that our algorithms converge to the global optimal solution and have a linear rate of convergence. We demonstrate that using our method, we can solve large problem instances of general weighted correlation clustering, metric nearness, information theoretic metric learning and quadratically regularized optimal transport; in each case, out-performing the state of the art methods with respect to CPU times and problem sizes.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available