MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization

Yangyang Xu Shuzhong Zhang

Numerical Linear Algebra mathscidoc:1912.43149

Computational Optimization and Applications, 70, (1), 91--128, 2018
Block coordinate update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primaldual BCU method for solving linearly constrained convex program with multi-block variables. The method is an accelerated version of a primaldual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an <i>O</i>(1/<i>t</i>) convergence rate under convexity assumption. We show that the rate can be accelerated to O ( 1 / t 2 ) if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can
No keywords uploaded!
[ Download ] [ 2019-12-21 11:25:54 uploaded by Yangyang_Xu ] [ 733 downloads ] [ 0 comments ] 
@inproceedings{yangyang2018accelerated,
  title={Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization},
  author={Yangyang Xu, and Shuzhong Zhang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112554372851709},
  booktitle={Computational Optimization and Applications},
  volume={70},
  number={1},
  pages={91--128},
  year={2018},
}
Yangyang Xu, and Shuzhong Zhang. Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization. 2018. Vol. 70. In Computational Optimization and Applications. pp.91--128. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112554372851709.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved