Project and Forget: Solving Large-Scale Metric Constrained Problems
From MaRDI portal
Publication:6340285
arXiv2005.03853MaRDI QIDQ6340285FDOQ6340285
Authors: Rishi Sonthalia, Anna C. Gilbert 
Publication date: 8 May 2020
Abstract: Given a set of dissimilarity measurements amongst data points, determining what metric representation is most "consistent" with the input measurements or the metric that best captures the relevant geometric features of the data is a key step in many machine learning algorithms. Existing methods are restricted to specific kinds of metrics or small problem sizes because of the large number of metric constraints in such problems. In this paper, we provide an active set algorithm, Project and Forget, that uses Bregman projections, to solve metric constrained problems with many (possibly exponentially) inequality constraints. We provide a theoretical analysis of extsc{Project and Forget} and prove that our algorithm converges to the global optimal solution and that the distance of the current iterate to the optimal solution decays asymptotically at an exponential rate. We demonstrate that using our method we can solve large problem instances of three types of metric constrained problems: general weight correlation clustering, metric nearness, and metric learning; in each case, out-performing the state of the art methods with respect to CPU times and problem sizes.
Has companion code repository: https://github.com/rsonthal/ProjectAndForget
This page was built for publication: Project and Forget: Solving Large-Scale Metric Constrained Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340285)
