Timezone: »
We consider the problem of minimizing block-separable convex functions subject to linear constraints. While the Alternating Direction Method of Multipliers (ADMM) for two-block linear constraints has been intensively studied both theoretically and empirically, in spite of some preliminary work, effective generalizations of ADMM to multiple blocks is still unclear. In this paper, we propose a parallel randomized block coordinate method named Parallel Direction Method of Multipliers (PDMM) to solve the optimization problems with multi-block linear constraints. PDMM randomly updates some blocks in parallel, behaving like parallel randomized block coordinate descent. We establish the global convergence and the iteration complexity for PDMM with constant step size. We also show that PDMM can do randomized block coordinate descent on overlapping blocks. Experimental results show that PDMM performs better than state-of-the-arts methods in two applications, robust principal component analysis and overlapping group lasso.
Author Information
Huahua Wang (University of Minnesota, Twin Cites)
Arindam Banerjee (University of Illinois Urbana-Champaign)
Arindam Banerjee is a Professor at the Department of Computer & Engineering and a Resident Fellow at the Institute on the Environment at the University of Minnesota, Twin Cities. His research interests are in machine learning, data mining, and applications in complex real-world problems in different areas including climate science, ecology, recommendation systems, text analysis, and finance. He has won several awards, including the NSF CAREER award (2010), the IBM Faculty Award (2013), and six best paper awards in top-tier conferences.
Zhi-Quan Luo (University of Minnesota, Twin Cites)
More from the Same Authors
-
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: Gradient Boosted Normalizing Flows »
Robert Giaquinto · Arindam Banerjee -
2019 Poster: Random Quadratic Forms with Dependence: Applications to Restricted Isometry and Beyond »
Arindam Banerjee · Qilong Gu · Vidyashankar Sivakumar · Steven Wu -
2018 Poster: An Improved Analysis of Alternating Minimization for Structured Multi-Response Regression »
Sheng Chen · Arindam Banerjee -
2017 Poster: Alternating Estimation for Structured High-Dimensional Multi-Response Models »
Sheng Chen · Arindam Banerjee -
2016 Poster: High Dimensional Structured Superposition Models »
Qilong Gu · Arindam Banerjee -
2016 Poster: Structured Matrix Recovery via the Generalized Dantzig Selector »
Sheng Chen · Arindam Banerjee -
2015 Poster: Unified View of Matrix Completion under General Structural Constraints »
Suriya Gunasekar · Arindam Banerjee · Joydeep Ghosh -
2015 Poster: Beyond Sub-Gaussian Measurements: High-Dimensional Structured Estimation with Sub-Exponential Designs »
Vidyashankar Sivakumar · Arindam Banerjee · Pradeep Ravikumar -
2015 Poster: Structured Estimation with Atomic Norms: General Bounds and Applications »
Sheng Chen · Arindam Banerjee -
2014 Poster: Bregman Alternating Direction Method of Multipliers »
Huahua Wang · Arindam Banerjee -
2014 Poster: Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization »
Meisam Razaviyayn · Mingyi Hong · Zhi-Quan Luo · Jong-Shi Pang -
2014 Poster: Estimation with Norm Regularization »
Arindam Banerjee · Sheng Chen · Farideh Fazayeli · Vidyashankar Sivakumar -
2014 Poster: Generalized Dantzig Selector: Application to the k-support norm »
Soumyadeep Chatterjee · Sheng Chen · Arindam Banerjee -
2014 Tutorial: Climate Change: Challenges for Machine Learning »
Arindam Banerjee · Claire Monteleoni -
2013 Poster: Large Scale Distributed Sparse Precision Estimation »
Huahua Wang · Arindam Banerjee · Cho-Jui Hsieh · Pradeep Ravikumar · Inderjit Dhillon -
2013 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 -
2012 Poster: Online L1-Dictionary Learning with Application to Novel Document Detection »
Shiva Kasiviswanathan · Huahua Wang · Arindam Banerjee · Prem Melville