Paid feature observation improves predictions beyond simple variance measures
Beyond Second-Order Information: Paid Logistic Regression with Noisy Features
Machine Learning
Summary
Getting better information about a situation often costs money, like paying for medical tests to get clearer results. This paper studies how to best decide when and how much to pay for better data to predict yes/no outcomes accurately. The authors found that simply knowing the variability of the noise in data isn't enough to make good decisions when the prediction model is logistic. They show that paying more to reduce certain noises helps, and they offer mathematical guarantees on how well their approach works, even when the noise details are unknown.
What this means in practice
- •For hospital data teams: Optimize medical test spending to improve patient outcome predictions with limited budgets.
- •For fraud detection analysts: Balance costs of acquiring clearer transaction features to better predict fraudulent activities.
A theory result. No direct application yet.
Authors
Sanghwa Kim, Kyoungseok Jang, Se-Young Yun
Abstract
We consider online binary prediction with paid stochastic features, where the learner can spend resources to obtain better observations of the underlying features. This setting is motivated by applications such as medical testing, where additional cost can provide more precise measurements of patient's features for predicting a binary outcome. At each round, a latent feature is drawn i.i.d., the response is generated through a logistic model, and the learner chooses how much to pay before observing a noisy version of the feature. The goal of learner is to jointly control prediction loss and acquisition cost. In contrast to the former result on the online linear regression with paid features, covariance information alone is no longer sufficient: two noise distributions with the same covariance may induce different optimal logistic losses, and lower variance can even lead to higher loss. Under a structural ordering in which larger payments yield better observations by removing independent noise, we obtain $\widetilde O(\sqrt{T})$ regret when the noise structure is known and $\widetilde O(T^{2/3})$ regret when it is unknown, with matching lower bounds up to logarithmic factors.