In several domains (such as medical diagnostics, rare languages or scientific simulations) the cost of data annotation is high, and thus only a limited number of samples can be labeled and used for training. In such applications, it is instrumental to find, among a pool or a stream of unlabeled data, the most informative samples to label. We focus on linear classification, under Gaussian design, in the high-dimensional regime where the data dimension and the number of unlabeled samples grow proportionally. In the pool-based case, for small-margin selection policies, we derive a sharp asymptotic characterization of the test error. We uncover a fundamental tradeoff in how the labeling budget should be allocated across the different selection steps. In the online setting, we determine analytically and numerically the selection policies that minimize the cumulative cost of labeling and mistakes, or maximize the final accuracy. We then comment on the case of two-layer networks. Based on joint works with Yue M Lu, Francesca Mignacco and Francesco Mori.
