“Storage optimal semidefinite programming”  

Speaker: Volkan Cevher
Laboratory for Information and Inference Systems
Ecole Polytechnique Federale de Lausanne
http://lions.epfl.ch 

Abstract: Semidefinite convex optimization problems often have low-rank solutions that can be represented with O(p)-storage. However, semidefinite programming methods require us to store the matrix decision variable with size O(p^2), which prevents the application of virtually all convex methods at large scale.  

Indeed, storage, not arithmetic computation, is now the obstacle that prevents us from solving large-scale optimization problems. A grand challenge in contemporary optimization is therefore to design storage-optimal algorithms that provably and reliably solve large-scale optimization problems in key scientific and engineering applications. An algorithm is called storage optimal if its working storage is within a constant factor of the memory required to specify a generic problem instance and its solution.  

So far, convex methods have completely failed to satisfy storage optimality. As a result, the literature has largely focused on storage optimal non-convex methods to obtain numerical solutions. Unfortunately, these algorithms have been shown to be provably correct only under unverifiable and unrealistic statistical assumptions on the problem template. They can also sacrifice the key benefits of convexity, as they do not use key convex geometric properties in their cost functions.  

To this end, my talk introduces a new convex optimization algebra to obtain numerical solutions to semidefinite programs with a low-rank matrix streaming model. This streaming model provides us an opportunity to integrate sketching as a new tool for developing storage optimal convex optimization methods that go beyond semidefinite programming to more general convex templates. The resulting algorithms are expected to achieve unparalleled results for scalable matrix optimization problems in signal processing, machine learning, and computer science.  

Speaker bio: Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in Atlanta, GA in 2005. He was a Research Scientist with the University of Maryland, College Park from 2006-2007 and also with Rice University in Houston, TX, from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include signal processing theory, machine learning, convex optimization, and information theory. Dr. Cevher was the recipient of the IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.

.