Events Calendar

CS Colloquium

Speaker: Satyen Kale, Yahoo! Research

Talk Title: Efficient Online Decision-Making and Applications to Semidefinite Programming

Abstract: Decision-making in the face of uncertainty over future outcomes is a fundamental algorithmic task, with roots in statistics and information theory, and applications in machine learning, signal processing, network routing and finance. The framework of regret minimization captures the notion of competitive online decision-making algorithms. Such algorithms are very effective for optimizing in settings where the environment is changing or just too large-scale for traditional optimization methods.
Semidefinite programming (SDP) is a widely used convex optimization technique today in operations research and computer science. The running time of SDP solvers can be quite high however. In this talk I will describe a new algorithm for online decision-making over the space of positive-semidefinite matrices. This algorithm, dubbed Matrix Multiplicative Weights, yields a general, combinatorial, primal-dual method for designing efficient algorithms for SDP. This method yields algorithms with the best known running time bounds for several graph partitioning and constraint satisfaction problems. The Matrix Multiplicative Weights algorithm also has numerous other applications in machine learning, derandomization and quantum computing which I will mention briefly.
This is joint work with Sanjeev Arora.


Biography: Satyen Kale is a postdoctoral scientist at Yahoo! Research working on algorithms for fundamental problems in Machine Learning and Optimization. His main research interests are decision making under uncertainty, statistical learning theory, combinatorial optimization, convex optimization, and more recently, algorithmic game theory. Previously, he was a postdoc at Microsoft Research New England, Cambridge, MA. In 2007, he completed his Ph.D. in the department of Computer Science at Princeton University, under the supervision of Prof. Sanjeev Arora. He completed his B.Tech in Computer Science at the Indian Institute of Technology, Bombay in 2002.


Host: Prof. Yan Liu

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Kanak Agrawal