The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification

arXiv:2510.01020v2 Announce Type: replace Abstract: We study sequential testing for a binary disease outcome when risk follows an unknown logistic model. At each round, the decision maker may either pay for a test revealing the true label or predict the outcome based on patient features and past data. The goal is to minimize costly tests while ensuring the misclassification rate stays below alpha with probability at least 1-elta. We propose a method that jointly estimates the logistic parameter heta^{star} and the feature distribution, using a conservative threshold on the logistic score to decide when to test. We prove our procedure achieves the target error with high probability and requires only widetilde O(sqrt{T}) more tests than an oracle with full knowledge. This is the first no-regret guarantee for error-constrained logistic testing, with direct applications to medical screening. Simulations corroborate our theoretical results, showing safe classification of patients and efficient estimation of heta^{star} with few excess tests.

Source: arXiv cs.LG | 2026-05-05