【数学学院】The efficiency of Random Permutation For ADMM and Coordinate Descent

  • 日期：2018-08-29        来源：四川大学数学学院         点击数：


Title:The efficiency of Random Permutation For ADMM and Coordinate Descent

报告人：Ruoyu Sun,（University of Illinois at Urbana-Champaign)

时间：2018年8月29日（周三）下午3点

地点：数学学院西303

Abstract:A simple yet powerful idea to deal with large-scale problems is todecompose them into smaller subproblems, such as SGD and 

coordinate descent (CD). It is natural to apply the same idea to solve linearly constrained problems by an algorithm called ADMM 

(Alternating Direction Method of Multipliers). Unfortunately, when there are three blocks, ADMM was previously shown to be possibly 

divergent even for solving a linear system. In this talk, we discuss a variant of ADMM, called RP-ADMM (Randomly Permuted ADMM) and 

prove its expected convergence for solving linear systems.

Built on this result, we present the first nontrivial progress on a difficult open question: what is the convergence rate of RP-coordinate

descent (RP-CD)? A widely known conjecture is that RP-CD is faster than randomized CD, thus can be O(n^2) times faster than cyclic CD 

according to our last talk. We prove that in expectation RP-CD is at least O(n) times faster than cyclic CD. The proof is based on a weak 

version of a new matrix AM-GM (algebraic mean-geometric mean) inequality.

邀请人：宋恩彬


来源链接：http://math.scu.edu.cn/info/1062/3673.htm