September 29, 2017, Webb 1100

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 inputs. We consider an online optimization setup that includes problems such as online resource allocation with a fixed inventory and the `Adwords' problem popular in online advertising. We examine two classes of primal-dual algorithms, with a focus on the competitive ratio, i.e., the ratio of the objective achieved by the algorithm to that of the optimal offline sequence of decisions. We give a bound on this ratio and show how certain smoothing of the objective function can improve the bound, and how to seek the optimal smoothing by solving a convex design problem. This approach allows us to design effective smoothing customized for a given cost function and problem structure.

Maryam Fazel is an Associate Professor of Electrical Engineering at the University of Washington, with adjunct appointments in Computer Science and Engineering, Mathematics, and Statistics. Maryam received her MS and PhD from Stanford University, her BS from Sharif University of Technology in Iran, and was a postdoctoral scholar at Caltech prior to joining UW. Her current research interests are in mathematical optimization and applications in machine learning. She is a recipient of the NSF Career Award, the UWEE Outstanding Teaching Award, UAI conference Best Student Paper Award (with her student), and coauthored a paper on low-rank matrix recovery selected as a Fast-Breaking paper by Science Watch (2011).