Timezone: »
Poster
On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization
Ke Hou · Zirui Zhou · Anthony Man-Cho So · Zhi-Quan Luo
Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
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.
Author Information
Ke Hou (CUHK)
Zirui Zhou (CUHK)
Anthony Man-Cho So (CUHK)
Zhi-Quan Luo (University of Minnesota, Twin Cites)
More from the Same Authors
-
2022 : Nonsmooth Composite Nonconvex-Concave Minimax Optimization »
Jiajin Li · Linglingzhi Zhu · Anthony Man-Cho So -
2022 : Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization »
Kaiwen Zhou · Anthony Man-Cho So · James Cheng -
2022 Spotlight: Stability Analysis and Generalization Bounds of Adversarial Training »
Jiancong Xiao · Yanbo Fan · Ruoyu Sun · Jue Wang · Zhi-Quan Luo -
2022 Spotlight: Adam Can Converge Without Any Modification On Update Rules »
Yushun Zhang · Congliang Chen · Naichen Shi · Ruoyu Sun · Zhi-Quan Luo -
2022 Spotlight: Lightning Talks 6B-1 »
Yushun Zhang · Duc Nguyen · Jiancong Xiao · Wei Jiang · Yaohua Wang · Yilun Xu · Zhen LI · Anderson Ye Zhang · Ziming Liu · Fangyi Zhang · Gilles Stoltz · Congliang Chen · Gang Li · Yanbo Fan · Ruoyu Sun · Naichen Shi · Yibo Wang · Ming Lin · Max Tegmark · Lijun Zhang · Jue Wang · Ruoyu Sun · Tommi Jaakkola · Senzhang Wang · Zhi-Quan Luo · Xiuyu Sun · Zhi-Quan Luo · Tianbao Yang · Rong Jin -
2022 Poster: Adam Can Converge Without Any Modification On Update Rules »
Yushun Zhang · Congliang Chen · Naichen Shi · Ruoyu Sun · Zhi-Quan Luo -
2022 Poster: Stability Analysis and Generalization Bounds of Adversarial Training »
Jiancong Xiao · Yanbo Fan · Ruoyu Sun · Jue Wang · Zhi-Quan Luo -
2021 Poster: When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work »
Jiawei Zhang · Yushun Zhang · Mingyi Hong · Ruoyu Sun · Zhi-Quan Luo -
2020 Poster: Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates »
Kaiwen Zhou · Anthony Man-Cho So · James Cheng -
2020 Poster: Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine »
Jiajin Li · Caihua Chen · Anthony Man-Cho So -
2019 Poster: A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression »
Jiajin Li · SEN HUANG · Anthony Man-Cho So -
2014 Poster: Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization »
Meisam Razaviyayn · Mingyi Hong · Zhi-Quan Luo · Jong-Shi Pang -
2014 Poster: Parallel Direction Method of Multipliers »
Huahua Wang · Arindam Banerjee · Zhi-Quan Luo -
2012 Poster: Learning with Partially Absorbing Random Walks »
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang · John Wright · Anthony Man-Cho So -
2009 Poster: Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming »
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li -
2009 Spotlight: Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming »
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li