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 PGMis 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.
|Original language||English (US)|
|Journal||Advances in Neural Information Processing Systems|
|State||Published - 2013|
|Event||27th Annual Conference on Neural Information Processing Systems, NIPS 2013 - Lake Tahoe, NV, United States|
Duration: Dec 5 2013 → Dec 10 2013