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.