Generalized Inverse Optimization through Online Learning
Inverse optimization is a powerful paradigm for learning preferences and restrictions that explain the behavior of a decision maker, based on a set of external signal and the corresponding decision pairs. However, most inverse optimization algorithms are designed specifically in batch setting, where all the data is available in advance. As a consequence, there has been rare use of these methods in an online setting suitable for real-time applications. In this paper, we propose a general framework for inverse optimization through online learning. Specifically, we develop an online learning algorithm that uses an implicit update rule which can handle noisy data. Moreover, under additional regularity assumptions in terms of the data and the model, we prove that our algorithm converges at a rate of O(1/ √ T ) and is statistically consistent. In our experiments, we show the online learning approach can learn the parameters with great accuracy and is very robust to noises, and achieves a dramatic improvement in computational efficacy over the batch learning approach.
Inverse optimization deals with finding the underlying objective function of an optimization problem (mainly in a parametric setup) from observation of inputs and correspoding optimal solutions as the data.  This can be done in a batch or in an online fashion from the data. The authors provide an online approach for doing this and prove that it can achieve a regret O(1/sqrt(T)) as a function of data size T.  1. I believe the paper is not written very well. For example, the underlying idea of inverse optimization is not clearly explained as in main references such as [1]. Moreover, the problem has been posed in a quite general setup but at the end the authors have focused on the convex and strongly convex setup where they have used the result already in the literature with some minor modifications.  2. the definition of the function h(x,thet_1,theta_2) at end of page 4 is not clear at all. What is the role of the variable "u" and where does it appear?   3. There are some typoes in the text that should be corrected: 3.1. batching learning --> batch learning 3.2. Also. estimation --> Also, estimation 3.3. rational making decison --> rational decision makers  4. the definition of the function h(x,thet_1,theta_2) at end of page 4 is not clear at all. What is the role of the variable "u" and where does it appear?  5. since the authors have focused on the convex case, there was no need to consider S(u, theta) since the optimal solution would be unique thus S(u, \theta) would be a single point.  6. As far as I see, the main novelty of the paper lies in the fact that the authors have notice that the inverse optimization in an online formulation can be posed as an online learning problem with a cost function that relates to the objective of the optimization problem and have posed it in the context of learning with regret. Also, the proved results seem to be a simple extension of the techniques in "Brian Kulis and Peter L. Bartlett. Implicit online learning".   However, this is not clearly written and connected in the paper. So, the paper needs to be modified to clearify this connection.   7. In the "Problem Statement" in Section 2, it is necessary to explain that the inverse optimization is considered in a parametric setup where \theta is the parameter of the objective function to be learned. This is not clearly epxlained in the paper.