Low-cost learning via active data procurement

We design mechanisms for online procurement of data held by strategic agents for machine learning tasks. We study a model in which agents cannot fabricate data, but may lie about their cost of furnishing their data. The challenge is to use past data to actively price future data in order to obtain learning guarantees, even when agents' costs can depend arbitrarily on the data itself. We show how to convert a large class of no-regret algorithms into online posted-price and learning mechanisms. Our results parallel classic sample complexity guarantees, but with the key resource constraint being money rather than quantity of data available. With a budget constraint B, we give robust risk (predictive error) bounds on the order of 1/√B. In many cases our guarantees are significantly better due to an active-learning approach that leverages correlations between costs and data. Our algorithms and analysis go through a model of no-regret learning with T arriving pairs (cost, data) and a budget constraint of B, coupled with the "online to batch conversion". Our regret bounds for this model are on the order of T/√B and we give lower bounds on the same order.