Title: Greedy block coordinate descent (GBCD) method for high dimensional quadratic programs
Speaker: Gugan Thoppe, TIFR Mumbai
Time and Date: 11:00 am, Tuesday October 6
Venue: Room 217, Mechanical Engineering
Abstract: Recent high dimensional optimization literature has majorly focussed on large scale optimization problems where the objective function is a sum of two functions - one with a block Lipschitz gradient and the other one being block separable. The emerging belief is that only variants of block coordinate descent (BCD) methods amongst existing methods may be suitable for efficiently solving the above class of problems. A rigorous verification of this belief has however been missing. In this talk, we will fill in the gap in the context of unconstrained quadratic programs (UQPs) - the simplest nonlinear problems in the above class. We will first define a notion of high dimensional compliant (HDC) methods for UQPs. We will then show that BCD and block Kaczmarz (BK) are the only existing UQP methods that can be readily made HDC. We will in fact show that even natural generalizations of BK and BCD methods are non HDC. We will then define a notion of `best' and, based on this, propose a novel deterministic greedy BCD (GBCD) method for UQPs with serial, parallel, and distributed variants. Using convergence rates and numerical tests, we will then demonstrate that the GBCD is indeed a competitive algorithm and is sometimes better than even the conjugate gradient. We will end with a brief discussion on extending the GBCD idea for generic optimization problems.