Project and Forget: Solving Large-Scale Metric Constrained Problems
Project and Forget: Solving Large-Scale Metric Constrained Problems
复制标题
DOI：
--
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
A. Gilbert;Rishi Sonthalia
中科院分区：
文献类型：
--
作者：
A. Gilbert;Rishi Sonthalia
给定数据点之间的一组相异性度量，确定什么度量表示与输入度量或最佳捕获数据的相关几何特征的度量最“一致”是许多机器学习算法中的关键步骤。现有的方法仅限于特定种类的度量或小的问题大小，因为在这样的问题中的大量的度量约束。在本文中，我们提供了一个有效的集合算法，项目和忘记，使用Bregman投影，解决度量约束问题，许多（可能是指数）不等式约束。我们提供了一个理论分析的\textsc{Project and Forget}，并证明我们的算法收敛到全局最优解，并在当前的最优解的L_2 $距离以指数速度渐近衰减。我们证明，使用我们的方法，我们可以解决大型问题的三种类型的度量约束问题的实例：一般的权重相关聚类，度量接近，度量学习;在每种情况下，表现优于最先进的方法相对于CPU时间和问题大小。
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 \textsc{Project and Forget} and prove that our algorithm converges to the global optimal solution and that the $L_2$ 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.