An LP for Sequential Learning Under Budgets

Abstract

We present a convex framework to learn se-quential decisions and apply it to the prob-lem of learning under a budget. We con-sider the structure proposed in [1], where sensor measurements are acquired in a se-quence. The goal after acquiring each new measurement is to make a decision whether to stop and classify or to pay the cost of us-ing the next sensor in the sequence. We in-troduce a novel formulation of an empirical risk objective for the multi stage sequential decision problem. This objective naturally lends itself to a non-convex multilinear for-mulation. Nevertheless, we derive a novel perspective that leads to a tight convex ob-jective. This is accomplished by expressing the empirical risk in terms of linear super-position of indicator functions. We then derive an LP formulation by utilizing hinge loss surrogates. Our LP achieves or ex-ceeds the empirical performance of the non-convex alternating algorithm that requires a large number of random initializations. Consequently, the LP has the advantage of guaranteed convergence, global optimality, repeatability and computation efficiency. 1