The problem of chasing convex functions is easy to state: faced with a sequence of convex functions {f_t}, the goal of the algorithm is to output a point x_t at each time, so that the sum of the function costs f_t(x_t), plus the movement costs || x_t - x_{t-1} || is minimized. This general problem generalizes several classic questions in online algorithms, such as caching and the k-server problem.
The question of getting an algorithm whose total cost is comparable to the optimal cost in hindsight was posed by Friedman and Linial in 1994. This was finally (mostly) resolved last year, using a combination of ideas from online algorithms and convex geometry. In this talk we will survey the results and ideas.
This is based on works with C.J.Argue, S.Bubeck, M.B.Cohen, G.Guruganesh, Y. T.Lee, and Z.Tang.
YouTube link : https://www.youtube.com/watch?v=TMilw8CX1Yg
