Optimizing over the Growing Spectrahedron
Optimizing over the Growing Spectrahedron
复制标题
DOI：
10.1007/978-3-642-33090-2_44
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
Joachim Giesen;Martin Jaggi;S. Laue
中科院分区：
文献类型：
--
作者：
Joachim Giesen;Martin Jaggi;S. Laue
我们为一类重要的参数化半定问题设计了一个计算近似解路径的框架，保证近似解路径ε-接近精确解路径，计算矩阵分解问题（如最大边际矩阵分解）的整个正则化路径的问题符合这个框架，以及机器学习中的许多其他核范数正则化凸优化问题。我们证明了近似路径的组合复杂性与矩阵的大小无关。此外，整个解路径可以在输入矩阵大小的近似线性时间内计算，该框架采用了一个近似的半定规划求解器对一个固定的参数值。在这里，我们使用的算法，最近介绍了哈赞。我们提出了一个精致的分析哈赞的算法，结果在改进的运行时间范围为一个单一的解决方案，以及为整个解决方案的路径作为一个函数的近似保证。
We devise a framework for computing an approximate solution path for an important class of parameterized semidefinite problems that is guaranteed to beε-close to the exact solution path. The problem of computing the entire regularization path for matrix factorization problems such as maximum-margin matrix factorization fits into this framework, as well as many other nuclear norm regularized convex optimization problems from machine learning. We show that the combinatorial complexity of the approximate path is independent of the size of the matrix. Furthermore, the whole solution path can be computed innear lineartime in the size of the input matrix.The framework employs an approximative semidefinite program solver for a fixed parameter value. Here we use an algorithm that has recently been introduced by Hazan. We present a refined analysis of Hazan’s algorithm that results in improved running time bounds for a single solution as well as for the whole solution path as a function of the approximation guarantee.