Low-rank mirror-prox methods for nonsmooth and low-rank matrix optimization problems

Abstract Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in developing efficient methods for smooth problems that avoid computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced. In this paper we consider a standard convex relaxation: minimizing a convex nonsmooth objective function over the spectrahedron (set of real positive-semidefinite matrices with unit trace), under a plausible strict complementarity (SC) condition. Following an observation that, even arbitrarily close to a low-rank optimal solution which satisfies SC, the standard projected subgradient descent method may fail to produce low-rank iterates, we focus on nonsmooth objectives that can be written as a maximum of smooth functions and consider the corresponding saddle-point formulation. Mainly, we prove that (approximated) variants of two popular mirror-prox methods: the Euclidean extragradient method and mirror-prox with matrix exponentiated gradient updates, when initialized with a “warm-start”, converge to an optimal solution with the standard O (1/ t ) ergodic rate, while requiring only two low-rank SVDs per iteration. For the Euclidean method we also consider relaxed versions of SC which yield a trade-off between the rank of SVDs and the radius of the ball in which we need to initialize. We support our theoretical findings with empirical experiments on several tasks, demonstrating both the plausibility of the SC assumption, and the efficient convergence of our proposed mirror-prox variants.