Professor Yin Tat Lee of the Allen School’s Theory of Computation research group has received a CAREER Award from the National Science Foundation to develop faster, more efficient algorithms for solving convex and other optimization problems. The outcome of Lee’s research, which seeks to increase the scientific community’s understanding of the relationship between convex geometry and optimization algorithms and improve upon current techniques drawn from continuous and discrete optimization, will have broad impact across the sciences and beyond.
Convex optimization techniques have applications in a range of fields, including machine learning, statistics, mathematics, economics, and operations research. However, many of these techniques historically tended to be inefficient and expensive to implement. Recent advances yielding faster algorithms have enabled Lee to break the long-standing running time barriers for specific problems, such as linear programming and maximum flow problems, and to apply optimization techniques to a broader class of problems than was previously feasible. Lee aims to build upon that past work by tackling a set of significant problems in convex geometry and optimization in order to push the state of the art even further. His approach will draw from techniques used in a variety of domains, including combinatorial and convex optimization, convex and Riemannian geometry, spectral graph theory, stochastic processes, and more.
One major goal of Lee’s CAREER proposal is to make progress towards resolving the Kannan-Lovasz-Simononoviz (KLS) conjecture — a central problem not only to the field of optimization but to theoretical computer science and mathematics, and one that implies several other well-known conjectures. Such progress would represent a significant breakthrough in researchers’ understanding of convex optimization and yield immediate running-time improvements for several problems in convex geometry. Lee also aims to resolve a number of algorithmic barriers to optimization, most notably the square-root iterations barrier for solving linear programs. This work would overcome a major obstacle to achieving nearly linear-time algorithms for the maximum flow problem, which is a key subroutine in many other algorithms and promises to have broad theoretical and practical implications.
Finally, Lee will apply a geometry perspective to the study of complex optimization algorithms, such as first-order methods and cutting-plane methods, in order to better understand their complexity and aid in the discovery of new applications. He also intends to explore the use of sampling algorithms for non-convex optimization, which is a rapidly developing area in machine learning.
The CAREER Award is administered through NSF’s Faculty Early Career Development Program and is designed to recognize and support promising junior faculty who successfully blend teaching and research and demonstrate the potential to be leaders in their respective fields. Including Lee, 59 Allen School faculty members have received one of these prestigious awards or their predecessor, the Presidential/NSF Young Investigator Award.
Read Lee’s award abstract here.
Congratulations, Yin Tat!