Online Optimization and Learning under Long-Term Convex Constraints and Objective

April 27, 2017, 4:15-5:15 PM

Shipra Agrawal
Assistant Professor
Columbia University

Abstract:
Sequential decision making situations in real world applications often involve multiple long term constraints and nonlinear objectives. Some examples from online advertising include budget constraints, nonlinear under-delivery penalties, need for diversity in allocation, and managing risk on revenue. However, most standard models like multi-armed bandits, contextual bandits, online learning, etc., simply optimize the sum of revenue/costs/profits received in every step, and therefore the decisions obtained do not satisfy these long-term considerations. Some full information models like online packing and covering problems allow linear knapsack type constraints on consumption.

In this talk, I will discuss a series of recent results in which we have introduced novel techniques to handle a very general form of convex constraints and objective in sequential decision making, while providing provably near-optimal guarantees. Our primal-dual techniques are efficient to implement and employ fundamental concepts of Fenchel duality in convex programming, while using online learning methods as blackbox. Our techniques are generalizable, as we demonstrate by their successful application to a variety of sequential decision making models: multi-armed bandits, contextual bandits, online packing, and online stochastic convex programming.

Bio:
Shipra Agrawal is an Assistant Professor in the Department of Industrial Engineering and Operations Research, and member of Data Science Institute, at Columbia University. Her research spans several areas of optimization and machine learning, including data-driven optimization under partial, uncertain, and online inputs, and related concepts in learning, namely multi-armed bandits, online learning, and reinforcement learning. She is also interested in prediction markets and game theory. Application areas of her interests include internet advertising, recommendation systems, revenue management and resource allocation problems.

Shipra received her PhD in Computer Science from Stanford University in June 2011 under guidance of Prof. Yinyu Ye, and was a researcher at Microsoft Research India from July 2011 to August 2015.