Optimization Online


Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization

Nam Ho-Nguyen (hnh***at***andrew.cmu.edu)
Fatma Kilinc-Karzan (fkilinc***at***andrew.cmu.edu)

Abstract: In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). The standard OCO framework has seen much success for its ability to handle decision-making in dynamic, uncertain, and even adversarial environments. Nevertheless, our applications of interest present further flexibility in OCO via three simple modifications to standard OCO assumptions: we introduce two new concepts of weighted regret and online saddle point problems and study the possibility of making lookahead (anticipatory) decisions. We demonstrate how these new flexibilities are instrumental in exploiting structural properties of functions which results in improved convergence rates in our flexible OCO framework. In particular, relaxing the usual OCO assumption of uniform weights (non-anticipatory decisions) allows us to utilize algorithms that can significantly speed up the convergence and go beyond the established lower bounds on regret for strongly convex (smooth) loss functions. We then apply these OCO tools to RO and JEO. Our results improve the convergence guarantees of first-order methods in the context of RO and JEO under certain structural assumptions, and in certain cases, they match the best known or optimal rates in the corresponding problem classes without data uncertainty.

Keywords: online convex optimization, regret minimization, saddle point problems

Category 1: Nonlinear Optimization

Category 2: Convex and Nonsmooth Optimization

Citation: Technical report, Tepper School of Business, Carnegie Mellon University, August 2016

Download: [PDF]

Entry Submitted: 08/01/2016
Entry Accepted: 08/01/2016
Entry Last Modified: 04/12/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society