UCLA Mathnet Login

Math Graduate Student Wins IOS 2014 Student Paper Award

Damek Davis

Damek Davis, a fifth year PhD student in the UCLA Department of Mathematics, was selected as the winner of the 2014 INFORMS Optimization Society Student Paper Prize for his paper “Convergence rate analysis of several splitting schemes,” (2014), with UCLA Math Professor Wotao Yin.

So far, Damek's work has focused on operator-splitting in optimization. Operator-splitting is a collection of techniques that split complicated problems arising in PDE, monotone operator theory, optimization, and control into a series of smaller subproblems. In many cases these decompositions lead to massively parallel algorithms with low per iteration cost and easy implementation.  

"The prize-winning work [1] analyzed the speed of several operator-splitting algorithms. We proved that a class of splitting algorithms, called Krasnosel’ski˘i-Mann iterations, converges faster than was previously known, and we showed that this rate was optimal.  We also analyzed two of the most popular splitting schemes, called Douglas-Rachford splitting (DRS) and the alternating direction method of multipliers (ADMM), and proved the first tight upper and lower complexity bounds.  This leads to a surprising conclusion: in general, the DRS and ADMM algorithms are nearly as slow as the subgradient method, which is one of the slowest optimization algorithms out there.  This is unexpected because DRS and ADMM are known to work quite well in practice. 

However, our work is not all bad news. In a follow up paper [2], we completed our analysis by showing problem regularity, such as smoothness and strong convexity, guarantees faster convergence rates for DRS and ADMM. These results show how to choose algorithm parameters in order to ensure fast convergence, so they should be quite useful in practice."

 

[1] Damek Davis, Wotao Yin. Convergence rate analysis of several splitting schemes. UCLA CAM report 14-51 (2014)

[2] Damek Davis, Wotao Yin. Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions. UCLA CAM report 14-58 (2014)