ORIE Colloquium on 11/12/2013 - Assaf Zeevi : From Online Convex Optimization to Non-stationary Stochastic Approximation

Tuesday, November 12, 2013 at 4:15pm Frank H. T. Rhodes Hall, 253 ORIE Colloquium: Assaf Zeevi (Columbia) - From Online Convex Optimization to Non-stationary Stochastic Approximation In an online convex optimization problem nature selects at each time instant a cost function from a given class of admissible (convex) functions, and then a decision maker picks an action from a given feasible action set, with the objective of optimizing the unknown cost function. The decision maker then observes some feedback signal based on the selected action, e.g., the value of the cost function and/or its gradient etc., and the game repeats itself until the end of the playing horizon. The performance of an online algorithm is measured in units of regret: the gap between the cumulative cost accrued by the algorithm's actions, and that of the single best action that would be chosen with benefit of hindsight, i.e., having observed nature's sequence cost functions. This formulation has (some of) its origins in the seminal work of Hannan in the 1950s, and has recently been the subject of several papers. The stochastic approximation literature, whose origin incidentally also dates back to the 1950s, is concerned with sequentially estimating the optimum point of a fixed yet unknown cost function whose observations are confounded by statistical noise. In this talk we draw certain connections between these two strands of literature, and develop some theory that attempts to expand the scope of stochastic approximation to non-stationary environments.