
CS Colloquium
Thu, Apr 07, 2011 @ 03:30 PM  01:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Satyen Kale, Yahoo! Research
Talk Title: Efficient Online DecisionMaking and Applications to Semidefinite Programming
Abstract: Decisionmaking 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 decisionmaking algorithms. Such algorithms are very effective for optimizing in settings where the environment is changing or just too largescale 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 decisionmaking over the space of positivesemidefinite matrices. This algorithm, dubbed Matrix Multiplicative Weights, yields a general, combinatorial, primaldual 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