Title: Worst-case Complexity of Cyclic Methods: O(n^2) Gap with Randomized Versions
报告人：Ruoyu Sun,（University of Illinois at Urbana-Champaign)
时间：2018年8月29日（周三）上午9点
地点：数学学院西303
Abstract:One of the most powerful ideas for solving big data optimization problems is to iteratively solve smaller subproblems. The
applications of this idea include Gauss-Seidel (G-S) method, Kaczmarz method and coordinate descent (CD) method. Despite the long history
of this type of methods (dating back to Gauss), the precise convergence speed is not well understood. In this talk, we study the
fundamental question: what is the worst-case complexity of these methods? There are existing upper bounds of the convergence rate, but
these bounds allow an O(n^2) gap with randomized versions, and thus considered to be a theoretical artifact. By carefully analyzing a class
of examples, we prove that these upper bounds are tight. This implies that in the worst-case there is indeed an O(n^2) gap between CD/G-S/K
aczmarz method and their randomized versions. Note that for this example, the gap exists for any fixed update order, not just a particular
order. We will also show empirically that our theoretical bounds are partially consistent with the practical performance of cyclic methods.
As a few modern algorithms are based on randomized CD, an interesting open question is whether the same complexity can be achieved by
deterministic algorithms.
邀请人：宋恩彬
来源链接：http://math.scu.edu.cn/info/1062/3674.htm
学术讲坛