Journal
JOURNAL OF MACHINE LEARNING RESEARCH
Volume 23, Issue -, Pages 1-54Publisher
MICROTOME PUBL
Keywords
Large Scale Convex Optimization; Metric Constrained Optimization; Metric Learning; Correlation Clustering
Funding
- 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
Recommended
No Data Available