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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Proximal Riemannian Pursuit for Large-Scale Trace-Norm Minimization
Trace-norm regularization plays an important role in many areas such as machine learning and computer vision. Solving trace-norm regularized Trace-norm regularization plays an important role in many areas such as compute…
BIG-bench Machine LearningClusteringMatrix CompletionLinear Convergence of ISTA and FISTA
In this paper, we revisit the class of iterative shrinkage-thresholding algorithms (ISTA) for solving the linear inverse problem with sparse representation, which arises in signal and image processing. It is shown in the…
Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
The gradient descent-ascent (GDA) algorithm has been widely applied to solve minimax optimization problems. In order to achieve convergent policy parameters for minimax optimization, it is important that GDA generates co…
Proximal Subgradient Norm Minimization of ISTA and FISTA
For first-order smooth optimization, the research on the acceleration phenomenon has a long-time history. Until recently, the mechanism leading to acceleration was not successfully uncovered by the gradient correction te…
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
We develop model-based methods for solving stochastic convex optimization problems, introducing the approximate-proximal point, or aProx, family, which includes stochastic subgradient, proximal point, and bundle methods.…