[Colloquium] TTI-C Talk: Satyen Kale (Microsoft)

[Julia MacGlashan]

When:             Thursday, March 5 @ 11:00am (lunch will be provided after
talk)

Where:            TTI-C Conference Room #526, 6045 S Kenwood Ave, 5th Floor

Who:                Satyen Kale (Microsoft Research New England)

Title:                 Improved Decision-Making under Uncertainty


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 online decision-making algorithms that are competitive with the
best possible decision in hindsight, under minimal assumptions on how the
costs of the decisions are set.

A major achievement of online learning theory has been the development of
algorithms that minimize regret even under such "worst-case" assumptions.
However, the regret bounds are quite suboptimal in real-life scenarios where
the decision costs are particularly benign. On the other hand,
"average-case" learning methods that posit a specific stochastic model on
the costs have better convergence bounds, but may fail to work when the
actual costs deviate from the model. Although these algorithms have been
developed over several decades, designing regret minimizing algorithms that
smoothly handle benign cost sequences, while not compromising worst-case
robustness, was considered a significant open problem. In my talk, I will
give an overview of my recent work with Elad Hazan which solved this open
problem for four fundamental online learning scenarios: (a) prediction from
expert advice, (b) online linear optimization, (c) universal portfolio
selection, and (d) bandit linear optimization. The work on portfolio
selection algorithms has implications in the standard Brownian motion model
of stock prices, which were verified by experiments on real data.

Contact:          Sham Kakade, TTI-C		sham at tti-c.org
<mailto:shai at tti-c.org>  		834-2550



-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 8390 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090227/ecd26c84/attachment-0001.bin