The need for faster and better optimization algorithms is ubiquitous and ever increasing. Besides the sheer size of data to be analyzed, the nature of modern optimization instances presents formidable challenges with data being partially specified, uncertain or high-dimensional data. Convex optimization remains the principal workhorse, but needs to be developed in several ways to meet these challenges. This project aims to do so by (a) developing faster algorithms for convex optimization using randomization (b) making optimization algorithms robust to uncertainty, and (c) providing robust guarantees when the input is only partially specified or uncertain.
Intellectual Merit. The foundational ideas of this project are novel, timely and will extend the frontier of our knowledge of optimization. They integrate multiple disciplines --- operations research, theoretical computer science, signal processing and statistical learning --- with the common goal of fast, robust and versatile convex optimization algorithms. Trading off accuracy for efficiency, the use of randomization, guarantees in the face of uncertain data and new formulations of convex optimization problems for learning, are all promising methods with wide applicability.
Broader Impact. This project is motivated by several general problems in applied mathematics that touch many different application areas. Progress on these problems, which include structured matrix factorization and estimation, graph estimation, robust multi-stage decision making and signal recovery, will have direct and lasting impact in applications as diverse as medical imaging, radar array processing, passive acoustic imaging, and digital communications. Mentoring and collaborating with a graduate student and a shared postdoctoral student across multiple EAGERs are additional aspects of the broader impact of this EAGER.
