TY - GEN

T1 - On correcting inputs

T2 - 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015

AU - Daumé, Hal

AU - Khuller, Samir

AU - Purohit, Manish

AU - Sanders, Gregory

N1 - Funding Information:
Partially supported by NSF grants IIS-1451430 and CCF-1217890.
Publisher Copyright:
© Hal Daumé III and Samir Khuller and Manish Purohit, and Gregory Sanders.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - Algorithm designers typically assume that the input data is correct, and then proceed to find "optimal" or "sub-optimal" solutions using this input data. However this assumption of correct data does not always hold in practice, especially in the context of online learning systems where the objective is to learn appropriate feature weights given some training samples. Such scenarios necessitate the study of inverse optimization problems where one is given an input instance as well as a desired output and the task is to adjust the input data so that the given output is indeed optimal. Motivated by learning structured prediction models, in this paper we consider inverse optimization with a margin, i.e., we require the given output to be better than all other feasible outputs by a desired margin. We consider such inverse optimization problems for maximum weight matroid basis, matroid intersection, perfect matchings in bipartite graphs, minimum cost maximum flows, and shortest paths and derive the first known results for such problems with a non-zero margin. The effectiveness of these algorithmic approaches to online learning for structured prediction is also discussed.

AB - Algorithm designers typically assume that the input data is correct, and then proceed to find "optimal" or "sub-optimal" solutions using this input data. However this assumption of correct data does not always hold in practice, especially in the context of online learning systems where the objective is to learn appropriate feature weights given some training samples. Such scenarios necessitate the study of inverse optimization problems where one is given an input instance as well as a desired output and the task is to adjust the input data so that the given output is indeed optimal. Motivated by learning structured prediction models, in this paper we consider inverse optimization with a margin, i.e., we require the given output to be better than all other feasible outputs by a desired margin. We consider such inverse optimization problems for maximum weight matroid basis, matroid intersection, perfect matchings in bipartite graphs, minimum cost maximum flows, and shortest paths and derive the first known results for such problems with a non-zero margin. The effectiveness of these algorithmic approaches to online learning for structured prediction is also discussed.

KW - Inverse optimization

KW - Online learning

KW - Structured prediction

UR - http://www.scopus.com/inward/record.url?scp=84958758726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958758726&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.FSTTCS.2015.38

DO - 10.4230/LIPIcs.FSTTCS.2015.38

M3 - Conference contribution

AN - SCOPUS:84958758726

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 38

EP - 51

BT - 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015

A2 - Harsha, Prahladh

A2 - Ramalingam, G.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 16 December 2015 through 18 December 2015

ER -