Entropy-Penalized Semidefinite Programming
Entropy-Penalized Semidefinite Programming
复制标题
DOI：
10.24963/ijcai.2019/157
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
M. Krechetov;Jakub Marecek;Yury Maximov;Martin Takác
中科院分区：
文献类型：
--
作者：
M. Krechetov;Jakub Marecek;Yury Maximov;Martin Takác
半定规划（SDP）的低秩方法最近引起了人们的极大兴趣，特别是在机器学习应用中。它们的分析通常涉及基于行列式或Schatten范数的惩罚，由于计算量大，在实践中很难实现。在本文中，我们提出了熵罚半定规划（EP-SDP），它提供了一个统一的框架，在实践中使用的广泛的惩罚函数，以促进低秩的解决方案。我们表明，EP-SDP问题承认一个有效的数值算法，具有（几乎）线性时间复杂度的梯度计算，这使得它适用于许多机器学习和优化问题。我们说明了我们的方法在几个组合优化和机器学习问题的实际效率。
Low-rank methods for semi-definite programming (SDP) have gained a lot of interest recently, especially in machine learning applications. Their analysis often involves determinant-based or Schatten-norm penalties, which are difficult to implement in practice due to high computational efforts. In this paper, we propose Entropy-Penalized Semi-Definite Programming (EP-SDP), which provides a unified framework for a broad class of penalty functions used in practice to promote a low-rank solution. We show that EP-SDP problems admit an efficient numerical algorithm, having (almost) linear time complexity of the gradient computation; this makes it useful for many machine learning and optimization problems. We illustrate the practical efficiency of our approach on several combinatorial optimization and machine learning problems.