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

• URL: http://arxiv.org/abs/2510.01020v1
• Date: Wed, 01 Oct 2025 15:28:00 GMT
• Title: The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification
• Authors: Tavor Z. Baharav, Spyros Dragazis, Aldo Pacchiano,
• Abstract summary: We study the problem of sequentially testing individuals for a binary disease outcome whose true risk is governed by an unknown logistic model.<n>Our goal is to minimize the total number of costly tests required while guaranteeing that the fraction of misclassifications does not exceed a prespecified error tolerance.<n>This establishes the first no-regret guarantees for error-constrained logistic testing, with direct applications to cost-sensitive medical screening.
• Score: 25.36548531839979
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of sequentially testing individuals for a binary disease outcome whose true risk is governed by an unknown logistic model. At each round, a patient arrives with feature vector $x_t$, and the decision maker may either pay to administer a (noiseless) diagnostic test--revealing the true label--or skip testing and predict the patient's disease status based on their feature vector and prior history. Our goal is to minimize the total number of costly tests required while guaranteeing that the fraction of misclassifications does not exceed a prespecified error tolerance $\alpha$, with probability at least $1-\delta$. To address this, we develop a novel algorithm that interleaves label-collection and distribution estimation to estimate both $\theta^{*}$ and the context distribution $P$, and computes a conservative, data-driven threshold $\tau_t$ on the logistic score $|x_t^\top\theta|$ to decide when testing is necessary. We prove that, with probability at least $1-\delta$, our procedure does not exceed the target misclassification rate, and requires only $O(\sqrt{T})$ excess tests compared to the oracle baseline that knows both $\theta^{*}$ and the patient feature distribution $P$. This establishes the first no-regret guarantees for error-constrained logistic testing, with direct applications to cost-sensitive medical screening. Simulations corroborate our theoretical guarantees, showing that in practice our procedure efficiently estimates $\theta^{*}$ while retaining safety guarantees, and does not require too many excess tests.

Related papers

• Global Sequential Testing for Multi-Stream Auditing [13.390852646411929]
  It is critical to continuously audit the performance of machine learning systems and detect any unusual behavior quickly.<n>This can be modeled as a sequential hypothesis testing problem with $k$ incoming streams of data and a global null hypothesis.<n>We construct new sequential tests by using ideas of merging test martingales with different trade-offs in expected stopping times under different, sparse or dense alternative hypotheses.
  arXiv  Detail & Related papers  (2026-02-25T01:10:45Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data [3.1138411427556445]
  In the measurement-constrained problems, despite the availability of large datasets, we may be only affordable to observe the labels on a small portion of the large dataset. This poses a critical question that which data points are most beneficial to label given a budget constraint. In this paper, we focus on the estimation of the optimal individualized threshold in a measurement-constrained M-estimation framework.
  arXiv  Detail & Related papers  (2024-11-21T00:21:17Z)
• Doubly Robust Conditional Independence Testing with Generative Neural Networks [8.323172773256449]
  This article addresses the problem of testing the conditional independence of two generic random vectors $X$ and $Y$ given a third random vector $Z$. We propose a new non-parametric testing procedure that avoids explicitly estimating any conditional distributions.
  arXiv  Detail & Related papers  (2024-07-25T01:28:59Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  We develop a test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the signal level,' $Gamma,$ of any instance. We complement this by a minimax lower bound $(Omegad/Gamma2)$ for sample costs of reliable tests.
  arXiv  Detail & Related papers  (2024-06-21T20:56:35Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  The goal is to identify nodes where the null hypothesis $p_v = q_v$ should be rejected. We propose the non-parametric collaborative two-sample testing (CTST) framework that efficiently leverages the graph structure. Our methodology integrates elements from f-divergence estimation, Kernel Methods, and Multitask Learning.
  arXiv  Detail & Related papers  (2024-02-08T14:43:56Z)
• A Priori Determination of the Pretest Probability [0.0]
  We introduce a novel method to estimate the pretest probability of disease, a priori, utilizing the Logit function from the logistic regression model. In a patient presenting with signs or symptoms, the minimal bound of the pretest probability, $phi$, can be approximated by: $phi approx frac15lnleft[styleprod_theta=1ikappa_thetaright]$ where $ln$ is the natural, and $kappa_theta$ is the likelihood ratio associated with
  arXiv  Detail & Related papers  (2024-01-08T18:44:43Z)
• Towards Optimal Statistical Watermarking [95.46650092476372]
  We study statistical watermarking by formulating it as a hypothesis testing problem. Key to our formulation is a coupling of the output tokens and the rejection region. We characterize the Uniformly Most Powerful (UMP) watermark in the general hypothesis testing setting.
  arXiv  Detail & Related papers  (2023-12-13T06:57:00Z)
• The Projected Covariance Measure for assumption-lean variable significance testing [3.8936058127056357]
  A simple but common approach is to specify a linear model, and then test whether the regression coefficient for $X$ is non-zero. We study the problem of testing the model-free null of conditional mean independence, i.e. that the conditional mean of $Y$ given $X$ and $Z$ does not depend on $X$. We propose a simple and general framework that can leverage flexible nonparametric or machine learning methods, such as additive models or random forests.
  arXiv  Detail & Related papers  (2022-11-03T17:55:50Z)
• Cost-aware Generalized $\alpha$-investing for Multiple Hypothesis Testing [5.521213530218833]
  We consider the problem of sequential multiple hypothesis testing with nontrivial data collection costs. This problem appears when conducting biological experiments to identify differentially expressed genes of a disease process. We make a theoretical analysis of the long term behavior of $alpha$-wealth which motivates a consideration of sample size in the $alpha$-investing decision rule.
  arXiv  Detail & Related papers  (2022-10-31T17:39:32Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)
• Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design [63.48989885374238]
  When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually. Our goal in this paper is to propose new group testing algorithms that can operate in a noisy setting.
  arXiv  Detail & Related papers  (2020-04-26T23:41:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.