On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization
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.
--------added after authors' rebuttal-------- The 
      proof for |R_k| <= kappa |X_k - X_{k+1}| has been explicitly 
      established in "Scalable nonconvex inexact proximal splitting", Suvrit 
      Sra, NIPS'12. (Lemma 4) --------end-------- For trace norm 
      regularized risk minimization, a popular method is the proximal gradient 
      algorithm. The sublinear global convergence rate of this algorithm is 
      well-understood while it is also known that the rate is linear if the loss 
      is additionally strongly convex. This paper relaxes the strong convexity 
      assumption by following the framework established by Luo and Tseng. In 
      particular, the authors proved a local error bound that allows them to 
      show that the proximal gradient converges asymptotically at a linear rate 
      for trace norm regularization. The paper more or less follows the usual 
      pattern to prove the local error bound, with a new observation that allows 
      simultaneous diagonalization of the matrices. Quality: This 
      paper appears to be technically sound. The only gap I had in mind is in 
      the appendix, line 085. Please explain why such a choice of kappa_3 (say 
      alpha < 1) leads to the claimed inequality R(X^k) <= kappa_3 |X^k - 
      X^{k+1}|_F ? Clarity: I could follow the paper without much 
      difficulty. Although due to the technical nature, it might be a good idea 
      to lay out the main claims first and then go to details one by one. 
      Particularly, after stating the local error bound, the authors might want 
      to postpone the very technical proof of the local error bound but turn 
      immediately to prove the linear rate (which by the way, has hardly 
      anything new in it). Originality: The originality of this 
      paper is moderate. The observation that allows the authors to 
      simultaneously diagonalize matrices seems to be new and interesting; other 
      than that, the authors more or less follow the existing approach to 
      establish the local error bound. The rest steps are not new. 
      Significance: The significance of this paper is mainly in 
      theory, with little impact on algorithm design though. While it is 
      certainly great to extend the linear convergence rate of the proximal 
      gradient algorithm to more practical scenarios (i.e., relaxed form of 
      strong convexity), the significance is nevertheless lowered by the 
      asymptotic nature of the proof (and claim). The way the authors handle the 
      diagonalization of matrices might be of some independent 
      interest.