Satyen Kale talk, 04/07, 3:30
David Kempe
we have one more theory faculty candidate for this semester: Satyen
Kale from Yahoo! Research will be giving a colloquium talk on Thursday
(04/07) at 3:30. All the important info is below. Looking forward to
seeing many of you there.
Time: Thursday, 04/07, 3:30 PM
Location: SSL 150
Speaker: Satyen Kale, Yahoo! Research
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.
Bio:
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.
--
David Kempe <dke...@usc.edu>