Timezone: »
We study online combinatorial decision problems, where one must make sequential decisions in some combinatorial space without knowing in advance the cost of decisions on each trial; the goal is to minimize the total regret over some sequence of trials relative to the best fixed decision in hindsight. Such problems have been studied mostly in settings where decisions are represented by Boolean vectors and costs are linear in this representation. Here we study a general setting where costs may be linear in any suitable lowdimensional vector representation of elements of the decision space. We give a general algorithm for such problems that we call lowdimensional online mirror descent (LDOMD); the algorithm generalizes both the Component Hedge algorithm of Koolen et al. (2010), and a recent algorithm of Suehiro et al. (2012). Our study offers a unification and generalization of previous work, and emphasizes the role of the convex polytope arising from the vector representation of the decision space; while Boolean representations lead to 01 polytopes, more general vector representations lead to more general polytopes. We study several examples of both types of polytopes. Finally, we demonstrate the benefit of having a general framework for such problems via an application to an online transportation problem; the associated transportation polytopes generalize the Birkhoff polytope of doubly stochastic matrices, and the resulting algorithm generalizes the PermELearn algorithm of Helmbold and Warmuth (2009).
Author Information
Arun Rajkumar (Indian Institute of Technology Madras)
Shivani Agarwal (University of Pennsylvania)
More from the Same Authors

2016 Poster: Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions »
Siddartha Ramamohan · Arun Rajkumar · Shivani Agarwal · Shivani Agarwal 
2014 Workshop: Analysis of Rank Data: Confluence of Social Choice, Operations Research, and Machine Learning »
Shivani Agarwal · Hossein Azari Soufiani · Guy Bresler · Sewoong Oh · David Parkes · Arun Rajkumar · Devavrat Shah 
2014 Poster: On the Statistical Consistency of Plugin Classifiers for Nondecomposable Performance Measures »
Harikrishna Narasimhan · Rohit Vaish · Shivani Agarwal 
2013 Poster: Convex Calibrated Surrogates for LowRank Loss Matrices with Applications to Subset Ranking Losses »
Harish G Ramaswamy · Shivani Agarwal · Ambuj Tewari 
2013 Poster: On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation »
Harikrishna Narasimhan · Shivani Agarwal 
2013 Spotlight: On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation »
Harikrishna Narasimhan · Shivani Agarwal 
2013 Spotlight: Convex Calibrated Surrogates for LowRank Loss Matrices with Applications to Subset Ranking Losses »
Harish G Ramaswamy · Shivani Agarwal · Ambuj Tewari 
2012 Poster: Classification Calibration Dimension for General Multiclass Losses »
Harish G Ramaswamy · Shivani Agarwal 
2012 Spotlight: Classification Calibration Dimension for General Multiclass Losses »
Harish G Ramaswamy · Shivani Agarwal 
2009 Workshop: Advances in Ranking »
Shivani Agarwal · Chris J Burges · Yacov Crammer