Optimizing over the Growing Spectrahedron

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 in near linear time 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. © 2012 Springer-Verlag.

Epstein, Leah
Ferragina, Paolo
Published in:
Proceedings of the 20th Annual European Symposium, 7501, 503-514
Presented at:
European Symposia on Algorithms (ESA) 2012, Ljubljana, Slovenia, September 10-12, 2012
Berlin, Heidelberg, Springer Berlin Heidelberg

 Record created 2017-06-21, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)