4:00 pm Monday, November 14, 2016
Colloquium: Online optimization, smoothing, and worst-case competitive ratio by
Maryam Fazel [mail] (University of Washington) in RLM 5.104
In Online Optimization, the data in an optimization problem is revealed over time, and at each step a decision variable needs to be set without knowing the future data. This setup covers online resource allocation, from classical inventory problems to the Adwords problem popular in online advertising. In this talk, we prove bounds on the competitive ratio of two primal-dual algorithms for a broad class of online convex optimization problems. We derive a sufficient condition on the objective function that guarantees a constant worst case competitive ratio (greater than or equal to 1/2) for monotone functions. We discuss examples of online conic optimization problems that satisfy the condition. We show how smoothing the objective can improve the competitive ratio of these algorithms, and in particular for separable functions, we show that the optimal smoothing can be derived by solving a convex optimization problem. This result allows us to directly optimize the competitive ratio bound over a class of smoothing functions, and hence design effective smoothing customized for a given cost function. Submitted by
|
|