[Colloquium] Theory seminar, Tuesday 12:45 at TTI

[meridel]

TTI/CS THEORY SEMINAR

Speaker: Adam Kalai

Title: Online convex optimization: gradient descent without a gradient

Time: Tuesday, October 5th 12:45pm 
Place: TTI-C (1427 E. 60th St., 2nd Floor) 
LUNCH PROVIDED 

Speaker's Homepage: http://www.tti-c.org/kalai.html
<http://www.tti-c.org/langford.html> 
 
Abstract: We study a general online convex optimization problem. We have
a convex set S and an unknown sequence of cost functions c_1,c_2,...,
and in each round, we choose a feasible point x_t in S, and learn the
cost c_t(x_t). If the function c_t is also revealed after each round
then, as Zinkevich has shown that online gradient descent can be used on
these functions, even if they are not related . That is, after n rounds,
the total cost incurred will be O(sqrt(n)) more than the cost of the
best single feasible point chosen with the benefit of hindsight,
min_{x\in S} c_1(x)+c_2(x)+...c_n(x). We present this result and then
extend it to the more difficult "bandit" setting where each period, only
the cost c_t(x_t) is revealed, and bound the expected regret (against an
oblivious adversary) as O(n^{5/6}).

Our approach uses a simple approximation of the gradient that is
computed from evaluating c_t at a single (random) point. We show that
this biased estimate is sufficient to approximate gradient descent on
the sequence of functions. In other words, it is possible to use
gradient descent in the online setting without seeing anything more than
the value of the functions at a single point. This also has interesting
implications for the tradeoff between exploration and exploitation.

This is joint work with two TTI summer interns: Abie Flaxman and Brendan
McMahan
 
If you have questions, please contact Meridel at 4-9873 or
mtrimble at tti-c.org
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041001/bcd9c2c2/attachment.htm