Efficient algorithms identify true hypothesis from many options with minimal actions.
problem Identifying true hypothesis from a large set of options with minimal actions.
method Greedy approximation algorithms for active sequential hypothesis testing.
result First approximation guarantees for ASHT, independent of the number of hypotheses.
Hypothesis testing is an important problem with applications in target localization, clinical trials etc. Many active hypothesis testing strategies operate in two phases: an exploration phase and a verification phase. In the exploration phase, selection of experiments is such that a moderate level of confidence on the …
New private algorithm for sequential hypothesis testing with privacy and error rate guarantees.
problem Privacy protection in sequential hypothesis testing for sensitive data.
method Renyi differential privacy, Wald's Sequential Probability Ratio Test (SPRT).
result Private algorithm with strong privacy guarantees and theoretical performance analysis.
Transforms any test into anytime-valid with sample savings.
problem Sequential data invalidates classical test guarantees.
method Predicts test outcomes to create anytime-valid stopping rules.
result Ensures Type-I error control and near-optimal power.
Framework for online hypothesis testing across various data types.
problem Testing various nonparametric hypotheses in data streams.
method Unified framework using operators on data distributions, leveraging ML models.
result Efficient, adaptive, and error-controlled sequential tests.
Paper resolves open problems on sample complexity in binary hypothesis testing.
problem Open problems in distributed simple binary hypothesis testing under information constraints.
method One-shot lower bound on Bayes error, streamlined sample complexity formula, reverse data-processing inequality.
result Optimally tight sample complexity bounds for communication-constrained simple binary hypothesis testing.
We study "active" decision making over sensor networks where the sensors' sequential probing actions are actively chosen by continuously learning from past observations. We consider two network settings: with and without central coordination. In the first case, the network nodes interact with each other through a centr…
New algorithm improves on static methods in Active Simple Hypothesis Testing.
problem Optimizing Active Simple Hypothesis Testing with active sampling.
method Game-theoretic formulation, differential games, PDEs, Blackwell Approachability.
result Proposes an efficient algorithm that outperforms static methods in ASHT.
Optimal sequential testing for Markovian data with lower and upper bounds.
problem Sequential hypothesis testing for Markovian data.
method Non-asymptotic lower bounds and optimal test design.
result Optimal test matches lower bound asymptotically.
Paper extends Chernoff sampling for active testing and parameter estimation, improving neural network and regression models.
problem Reducing sample complexity in hypothesis testing and model parameter estimation.
method Developed an extension of Chernoff sampling for active learning and parameter estimation.
result Non-asymptotic bounds for sample complexity and estimation error in active learning.
Optimal tests developed for sequential experiments with asymptotic properties.
problem Performing hypothesis tests after sequential experiments without prior design.
method Analyze asymptotic properties of sequential experiments; develop tests for Gaussian process observations.
result Asymptotic power function of any test can be matched by a specific test in a limit experiment.
Improved sequential tests detect anomalies faster in multi-stream auditing.
problem Efficiently auditing machine learning systems across multiple data streams.
method Developed new sequential tests using merging martingales and averaging/products rules.
result Balanced tests achieve optimal stopping times in sparse and dense alternatives.
Sequential tests for two-sample and independence testing using betting strategies.
problem Testing sequential data for two-sample and independence without kernel selection issues.
method Prediction-based betting strategies that adaptively determine distribution and joint distribution.
result Prediction-based tests outperform kernel-based approaches in high-dimensional or structured data settings.
We study the power of interactivity in local differential privacy. First, we focus on the difference between fully interactive and sequentially interactive protocols. Sequentially interactive protocols may query users adaptively in sequence, but they cannot return to previously queried users. The vast majority of exist…
PEAK tests means of multiple data streams with sequential betting.
problem Testing means of multiple data streams with nonparametric methods.
method Sequential, nonparametric testing using a betting scheme.
result PEAK provides up to 85% reduction in samples for stopping.
aLTT selects hyperparameters efficiently with statistical guarantees.
problem Statistical validity and efficiency in hyperparameter selection.
method Sequential data-dependent multiple hypothesis testing with early termination.
result Reduces testing rounds while maintaining statistical validity.
We propose a new algorithmic framework for sequential hypothesis testing with i.i.d. data, which includes A/B testing, nonparametric two-sample testing, and independence testing as special cases. It is novel in several ways: (a) it takes linear time and constant space to compute on the fly, (b) it has the same power gu…
User releases data to service provider while balancing privacy and utility.
problem Balancing user privacy and service utility in data release.
method Formulated as a Markov decision process (MDP) and solved using deep reinforcement learning (RL).
result Achieved a trade-off between revealing useful information and protecting sensitive data.
Motivated by real-world machine learning applications, we consider a statistical classification task in a sequential setting where test samples arrive sequentially. In addition, the generating distributions are unknown and only a set of empirically sampled sequences are available to a decision maker. The decision maker…
E-valuator converts verifier scores into reliable decision rules.
problem Ensuring the correctness of agent trajectories based on heuristic scores.
method Sequential hypothesis testing framework for online monitoring of agent trajectories.
result E-valuator provides better false alarm rate control and statistical power than other strategies.
We propose a nonparametric sequential test that aims to address two practical problems pertinent to online randomized experiments: (i) how to do a hypothesis test for complex metrics; (ii) how to prevent type 1 error inflation under continuous monitoring. The proposed test does not require knowledge of the underlying…
New algorithms for decision trees with noisy outcomes improve learning efficiency.
problem Learning with noisy outcomes in active learning.
method Approximation algorithms for optimal decision trees with persistent noise.
result Approximation algorithms provide nearly optimal performance guarantees.
Model-X test detects conditional independence in streaming data.
problem Detecting conditional independence in data streams with arbitrary dependency.
method Sequential testing inspired by model-X and testing by betting.
result Significantly reduces type-I error rate and enhances data efficiency.
Formula derived for sample complexity in binary hypothesis testing.
problem Determine the minimum number of samples to distinguish between two distributions.
method Developed a formula for sample complexity in both prior-free and Bayesian settings, using Jensen-Shannon and Hellinger divergences.
result Formula characterizes sample complexity for a wide range of error parameters, up to multiplicative constants.
A new stopping rule based on E-values helps efficiently use sampling in Bayesian Deep Ensembles.
problem How long should sampling continue in Bayesian Deep Ensembles to yield significant improvements?
method Formulated as a sequential anytime-valid hypothesis test, using E-values to decide when to stop sampling.
result Only a fraction of the full-chain budget is often required for significant improvements.
The paper presents a method for detecting jump sizes in crude oil prices.
problem Detecting jump sizes in crude oil price data.
method Sequential hypothesis testing using infinitesimal generators and super-solutions.
result The method improves the Barndorff-Nielsen and Shephard model for derivative and commodity market analysis.
This paper shows how to construct sequential tests with power one against weakly compact sets in Polish spaces.
problem Testing composite null hypotheses involving weakly compact sets in Polish spaces.
method Develops sequential tests for i.i.d. laws in Polish spaces, providing a sufficient condition for power one.
result Power-one sequential tests exist for weakly compact sets against their complements in i.i.d. laws in Polish spaces.
Active inference uses machine learning to prioritize data labeling for more efficient statistical inference.
problem Efficiently collecting data points for statistical inference with limited labels.
method A machine learning-assisted approach that identifies uncertain data points for labeling.
result Achieves the same level of accuracy with fewer samples, resulting in smaller confidence intervals and more powerful p-values.
EviTrack improves sequential prediction in delayed disambiguation scenarios.
problem Challenges in sequential prediction with delayed disambiguation where early observations are ambiguous.
method EviTrack operates over latent trajectories, applying evidence- and likelihood-ratio-based selection to delay commitment until supported by data.
result EviTrack outperforms sampling-based baselines in a controlled synthetic benchmark, achieving faster post-disambiguation recovery.
A new method reduces computational costs for testing RF variable importance measures.
problem Testing variable importance measures from random forests is computationally expensive and challenging.
method Sequential permutation testing and sequential p-value estimation to reduce computational costs.
result Theoretical properties of sequential tests are confirmed, maintaining type-I error and high power.
The paper tests if LLMs' capabilities are executed by small subnetworks (circuits).
problem Understanding how LLMs execute their capabilities.
method Formalized criteria for circuits, developed hypothesis tests, applied to six circuits.
result Synthetic circuits align with idealized properties, while Transformer circuits vary in their alignment.
The hypothesis of randomness is fundamental in statistical machine learning and in many areas of nonparametric statistics; it says that the observations are assumed to be independent and coming from the same unknown probability distribution. This hypothesis is close, in certain respects, to the hypothesis of exchangeab…
Study on continuous sequence classification with distribution uncertainty.
problem Classifying continuous sequences with varying distribution uncertainty.
method Proposes distribution-free tests for three test designs: fixed-length, sequential, and two-phase tests.
result Error probabilities decay exponentially fast for all test designs.
A new method uses active learning to improve bile duct stone evaluation.
problem Efficiently collecting necessary patient data in sequential healthcare decisions.
method Developed an active learning-based multistage sequential decision-making model.
result Improves estimation efficiency by 62%-1838% compared to baseline methods.
Determining the extent to which different cognitive modalities (understood here as the set of cognitive processes underlying the elaboration of a stimulus by the brain) rely on overlapping neural representations is a fundamental issue in cognitive neuroscience. In the last decade, the identification of shared activity …
Bayesian method optimizes interventions for causal discovery.
problem Active interventions are needed for causal discovery when observational data is insufficient.
method Bayesian optimization-based approach using observational data and pre-experimental evaluation of interventions.
result Demonstrated effectiveness through various experiments.
MARLA uses deep reinforcement learning for multi-agent AHT, reducing Bayes risk.
problem Decentralized active hypothesis testing among multiple agents.
method MARLA algorithm using deep multi-agent reinforcement learning.
result MARLA outperforms single-agent learning in AHT problems.
New algorithm for efficiently identifying the best arm in stochastic bandits.
problem Best arm identification in stochastic multi-armed bandits with fixed confidence.
method Sequential probability ratio tests for arm selection.
result Asymptotically optimal sample complexity and guaranteed δ−PAC performance. Sequential hypothesis testing is a desirable decision making strategy in any time sensitive scenario. Compared with fixed sample-size testing, sequential testing is capable of achieving identical probability of error requirements using less samples in average. For a binary detection problem, it is well known that for k…
Unified framework for online LLM watermark detection using e-processes.
problem Detecting AI-generated text from human-written content in online settings.
method Unified framework based on e-processes for anytime-valid hypothesis testing on independence.
result Proposed methods achieve competitive performance in watermark detection.
The problem of multi-hypothesis testing with controlled sensing of observations is considered. The distribution of observations collected under each control is assumed to follow a single-parameter exponential family distribution. The goal is to design a policy to find the true hypothesis with minimum expected delay whi…
A new stopping criterion for active learning based on deterministic generalization bounds.
problem Determining the optimal stopping point for active learning when data acquisition is costly.
method The proposed stopping criterion is based on the difference in expected generalization errors and hypothesis testing, derived from PAC-Bayesian theory.
result The proposed stopping criterion effectively stops active learning by combining an upper bound with a statistical test.
Unified framework for constrained online decision-making.
problem Sequential decisions under stage-wise feasibility constraints.
method Upper counterfactual confidence bounds and generalized eluder dimension.
result Principled foundation for constrained sequential decision-making.
We develop a novel computationally efficient and general framework for robust hypothesis testing. The new framework features a new way to construct uncertainty sets under the null and the alternative distributions, which are sets centered around the empirical distribution defined via Wasserstein metric, thus our approa…
New method selects features for sequential decision making.
problem Dynamic feature selection for instance-wise decisions.
method Latent variable model trained in a supervised manner; reasoning across stochastic latent space.
result Outperforms existing methods on various datasets.
Study efficient sequential evaluation of large language models using historical data.
problem Sequentially evaluate a new large language model (LLM) on a fixed question set.
method Construct a confidence sequence (CS) and design active querying rules to shrink CS width.
result Simple uniform sampling can sometimes outperform adaptive querying rules.
Proposes handling ambiguity in sequential data predictions.
problem Handling uncertainty in sequential data predictions.
method Extension of MHP model to recurrent architectures, introducing a novel metric.
result Achieved promising results on various sequential data tasks.
In this paper we address the problem of pool based active learning, and provide an algorithm, called UPAL, that works by minimizing the unbiased estimator of the risk of a hypothesis in a given hypothesis space. For the space of linear classifiers and the squared loss we show that UPAL is equivalent to an exponentially…