On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization

Part of Advances in Neural Information Processing Systems 26 (NIPS 2013)

Bibtex »Metadata »Paper »Reviews »Supplemental »


Ke Hou, Zirui Zhou, Anthony Man-Cho So, Zhi-Quan Luo


Motivated by various applications in machine learning, the problem of minimizing a convex smooth loss function with trace norm regularization has received much attention lately. Currently, a popular method for solving such problem is the proximal gradient method (PGM), which is known to have a sublinear rate of convergence. In this paper, we show that for a large class of loss functions, the convergence rate of the PGM is in fact linear. Our result is established without any strong convexity assumption on the loss function. A key ingredient in our proof is a new Lipschitzian error bound for the aforementioned trace norm-regularized problem, which may be of independent interest.