Primal-Dual Stochastic Subgradient Method For Log-Determinant Optimization

Abstract

The log-determinant optimization problem with general matrix constraints arises in many applications. The log-determinant term hampers the scalability of existing methods. This paper proposes a highly efficient stochastic method that has time complexity O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), whereas existing methods have complexity O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ). In order to achieve the quadratic complexity, the proposed algorithm leverages an efficient stochastic gradient of the augmented Lagrangian form and relies on subgradient descent method. Convergence of this method is analyzed both theoretically and empirically. The resulting primal-dual stochastic subgradient method yields the same accuracy as existing methods yet only requires O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) operations.