Optimizing over the growing spectrahedron

Abstract We devise a framework for computing an approximate so-lution path for an important class of parameterized semidefinite prob-lems that is guaranteed to be ε-close to the exact solution path. The problem of computing the entire regularization path for matrix factor-ization 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 combi-natorial 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 algo-rithm 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.