Swati Gupta

 

Faculty Candidate Swati Gupta [MIT] 
Title Learning Combinatorial Structures
Date & Time Wednesday, February 15, 2017
Place UCLA Anderson School of Management 
Room A201

 

Abstract
At the heart of most applications today, like search, recommender systems, pricing and routing, there is an optimization engine trying to provide the best decision with partial information observed thus far in time, the so-called problem of online learning. However, often it becomes difficult to find near-optimal decisions (like optimal prices of items, ordering of web-pages) in these applications due to their inherent combinatorial structure that leads to certain computational bottlenecks. We first consider a near-optimal learning method, online mirror descent, which requires the computation of a certain projection over the decision sets. We provide a conceptually simple algorithm to compute these projections over an important class of problems (submodular base polytopes). Our method obtains the fastest-known running time when the decisions are cardinality-based, for e.g. k-subsets, permutations, and probability distributions. This is useful for learning customer preferences for various applications. Next, we consider a related computational bottleneck of movement along a line while staying feasible in these decision sets, and show a running time improvement of n^6 from the state of the art. Finally, we discuss extensions and applications of these ideas to problems in dynamic pricing, robust inventory routing and prediction of heuristic performance.

Swati Gupta