Beyond Second-Order Information: Paid Logistic Regression with Noisy Features
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 Õ(√T) regret when the noise structure is known and Õ(T2/3) regret when it is unknown, with matching lower bounds up to logarithmic factors.
Related
- Data generation for the logistic regression model under controlled conditions
- A penalized logistic generalized regression estimator
- Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices
- Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
- Logistic Gaussian process density regression: a generalized Bayesian approach
BibTeX
@misc{kim2026beyond,
title = {{Beyond Second-Order Information: Paid Logistic Regression with Noisy Features}},
author = {Sanghwa Kim and Kyoungseok Jang and Se-Young Yun},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12919},
eprint = {2610.12919},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12919},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Beyond Second-Order Information: Paid Logistic Regression with Noisy Features
AU - Sanghwa Kim
AU - Kyoungseok Jang
AU - Se-Young Yun
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.12919
UR - https://arxiv.org/abs/2610.12919
AB - 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 Õ(√T) regret when the noise structure is known and Õ(T^2/3) regret when it is unknown, with matching lower bounds up to logarithmic factors.
ER -