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

Tavor Baharav, Spyros Dragazis, Aldo Pacchiano
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:865-873, 2026.

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-\delta$. We propose a method that jointly estimates the logistic parameter $\theta^{\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 $\theta^{\star}$ with few excess tests.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-baharav26a, title = { The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification }, author = {Baharav, Tavor and Dragazis, Spyros and Pacchiano, Aldo}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {865--873}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/baharav26a/baharav26a.pdf}, url = {https://proceedings.mlr.press/v300/baharav26a.html}, 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-\delta$. We propose a method that jointly estimates the logistic parameter $\theta^{\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 $\theta^{\star}$ with few excess tests. } }
Endnote
%0 Conference Paper %T The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification %A Tavor Baharav %A Spyros Dragazis %A Aldo Pacchiano %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-baharav26a %I PMLR %P 865--873 %U https://proceedings.mlr.press/v300/baharav26a.html %V 300 %X 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-\delta$. We propose a method that jointly estimates the logistic parameter $\theta^{\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 $\theta^{\star}$ with few excess tests.
APA
Baharav, T., Dragazis, S. & Pacchiano, A.. (2026). The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:865-873 Available from https://proceedings.mlr.press/v300/baharav26a.html.

Related Material