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.
Study controls error rates of binary classifiers using hypothesis testing.
problem Traditional binary classifiers have uncontrolled error rates.
method Combines binary classification with statistical hypothesis testing.
result Trained classifiers can be made to meet target error rate thresholds.
New tests for binary classification regression functions without distribution assumptions.
problem Testing regression functions in binary classification without distributional assumptions.
method Conditional kernel mean embeddings and resampling-based framework.
result Distribution-free hypothesis tests with exact type I error control.
Study binary hypothesis testing with privacy and communication constraints.
problem Binary hypothesis testing under local differential privacy and communication constraints.
method Qualifies results as minimax or instance optimal, develops instance-optimal algorithms.
result Achieves minimum possible sample complexity under both privacy and communication constraints.
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.
Binary testing for softmax models requires many samples, similar to leverage score models.
problem Binary hypothesis testing for softmax models and leverage score models.
method Analyzing sample complexity and drawing analogies between models.
result Sample complexity is asymptotically \(O(ε^{-2})\), where \(ε\) is the distance between model parameters.
Study hypothesis testing under quantized samples with communication constraints, achieving near-optimal sample complexity.
problem Optimizing hypothesis testing with quantized samples and communication constraints.
method Developed a polynomial-time algorithm achieving near-optimal sample complexity under communication constraints.
result Achieved near-optimal sample complexity under communication constraints, with a logarithmic factor increase over unconstrained setting.
Enhanced metrics for multiclass classification improve on existing methods.
problem Lack of decisive poor classification results in existing multiclass metrics.
method Introduces three new metrics derived from multivariate Pearson correlation coefficients.
result New metrics decisively indicate poor classification results.
Study sample complexity of robust binary hypothesis testing under different contamination models.
problem Analyzing the sample complexity of robust binary hypothesis testing under various contamination models.
method Examined three standard contamination models: ε-additive (Huber), ε-subtractive, and ε-total variation (TV). Provided explicit formulas for least favourable distributions and compared sample complexities across models.
result Sample complexities are highly unstable in the contamination parameter ε and comparable up to constant-factor rescaling of ε across models.
We study nonzero-sum hypothesis testing games that arise in the context of adversarial classification, in both the Bayesian as well as the Neyman-Pearson frameworks. We first show that these games admit mixed strategy Nash equilibria, and then we examine some interesting concentration phenomena of these equilibria. Our…
We have developed a statistical technique to test the model assumption of binary regime switching extension of the geometric Brownian motion (GBM) model by proposing a new discriminating statistics. Given a time series data, we have identified an admissible class of the regime switching candidate models for the statist…
Develops GLRT for defending against adversarial attacks in hypothesis testing.
problem Adversarial attacks on machine learning models causing misclassification.
method Generalized likelihood ratio test applied to composite hypothesis testing problem.
result GLRT approach yields competitive robustness-accuracy tradeoff under various attacks.
Adversarial robustness improved by abstaining from decisions.
problem Improving classification accuracy in the presence of adversarial perturbations.
method Introducing an abstain option in binary classification problems, using metrics to quantify performance and robustness.
result There is a tradeoff between nominal performance and adversarial robustness.
New bounds on generalization error using information density moments.
problem Bounding the generalization error of randomized learning algorithms.
method Derives bounds on average and tail probabilities of generalization error using mth central moments of the information density.
result Explicit bounds on generalization error are derived, showing better dependence on confidence level with higher-order information density moments.
GRASP tests goodness-of-fit for binary classifiers without parametric assumptions.
problem Assessing the fit of a binary classifier to the underlying conditional law of labels given features.
method Formulates a tolerance hypothesis testing problem and proposes a novel test called GRASP.
result Proposes GRASP and Model-X GRASP tests for assessing goodness-of-fit in finite sample settings.
In statistical inference problems, we wish to obtain lower bounds on the minimax risk, that is to bound the performance of any possible estimator. A standard technique to obtain risk lower bounds involves the use of Fano's inequality. In an information-theoretic setting, it is known that Fano's inequality typically doe…
Quantum classification robustness improved via quantum hypothesis testing.
problem Vulnerability of quantum classification algorithms to input perturbations.
method Formalized link between quantum hypothesis testing and robustness, developed practical protocols.
result Tight robustness condition independent of noise source (natural or adversarial).
The paper confirms two groups of gamma-ray bursts using a new nonparametric metric.
problem Determining the number of inherent groups in gamma-ray bursts.
method A new nonparametric interpoint distance-based measure, combined with clustering methods.
result Confirms two groups of short and long gamma-ray bursts.
Three DP variants linked, improving SGD privacy bounds.
problem Relating different DP variants for tighter privacy bounds.
method Developed machinery to relate approximate DP to RDP and hypothesis test DP.
result Improved privacy guarantees for noisy SGD.
In this work, we consider hypothesis testing and anomaly detection on datasets where each observation is a weighted network. Examples of such data include brain connectivity networks from fMRI flow data, or word co-occurrence counts for populations of individuals. Current approaches to hypothesis testing for weighted n…
Classification is a fundamental problem in machine learning and data mining. During the past decades, numerous classification methods have been presented based on different principles. However, most existing classifiers cast the classification problem as an optimization problem and do not address the issue of statistic…
Improved bounds on combining hypothesis classes for binary functions.
problem Understanding how to combine hypothesis classes for binary functions.
method Established upper bounds on Littlestone and threshold dimensions for combined classes.
result Upper bounds are nearly tight and give exponential improvements.
The paper tackles hypothesis testing for likelihood-free inference with a new kernel-based approach.
problem Testing hypotheses with limited labeled data in likelihood-free inference.
method Kernel-based tests using maximum mean discrepancy (MMD) for non-parametric density comparison.
result Existence of an asymmetric trade-off between labeled and unlabeled data samples.
Many binary classification problems minimize misclassification above (or below) a threshold. We show that instances of ranking problems, accuracy at the top or hypothesis testing may be written in this form. We propose a general framework to handle these classes of problems and show which known methods (both known and …
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…
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…
A framework for hypothesis testing on attributed graphs using sampling.
problem Statistical testing on graph data, especially large attributed graphs.
method Sampling-based framework with PHASE and PHASEopt for accurate and efficient hypothesis testing.
result PHASE and PHASEopt improve accuracy and efficiency of hypothesis testing in attributed graphs.
Paper defends machine learning models from adversarial attacks using GLRT.
problem Adversarial attacks on machine learning models leading to misclassification.
method Generalized likelihood ratio test (GLRT) for robust classification.
result GLRT yields performance competitive with minimax approach under worst-case attacks, and better trade-off under weaker attacks.
SCoRE provides risk control for selective prediction models.
problem Enforcing strict error control in selective prediction models.
method SCoRE framework based on conformal inference and hypothesis testing.
result SCoRE offers binary trust decisions with finite-sample error control.
Study tests financial market efficiency using random number generator tests.
problem Check for informational efficiencies in financial markets.
method Analysed binary daily returns as random number generators, split analysis by annual and company levels, investigated longer-term efficiency over Nasdaq-listed companies.
result Information efficiency varies across years and reflects large-scale market impacts.
Can we make Bayesian posterior MCMC sampling more efficient when faced with very large datasets? We argue that computing the likelihood for N datapoints in the Metropolis-Hastings (MH) test to reach a single binary decision is computationally inefficient. We introduce an approximate MH rule based on a sequential hypoth…
The paper sets thresholds for testing correlation in hypergraphs, distinguishing between independent and correlated states.
problem Testing correlation between two hypergraphs under different models.
method Derives sharp information-theoretic thresholds for distinguishing between null and alternative hypotheses.
result The testing threshold decreases as the hypergraph's uniformity (m) increases, making correlation testing easier for higher uniformity.
The goal of two-sample tests is to assess whether two samples, SP∼Pn and SQ∼Qm, are drawn from the same distribution. Perhaps intriguingly, one relatively unexplored method to build two-sample tests is the use of binary classifiers. In particular, construct a dataset by pairing the n examples in $S_…
Study robust hypothesis testing under Hellinger distance, proving lower bounds and providing tests.
problem Testing close variants of specified distributions robustly to Hellinger distance.
method Lower bound on slack factor, testing with Hellinger balls, symmetric chi-squared distance analysis.
result Lower bound on slack factor quantifies robustness under misspecification.
Generates positive examples from noisy data streams.
problem Learning from noisy example streams in hypothesis classes.
method Extending results from previous studies to account for noise.
result Conditions for noisily generatable binary hypothesis classes.
In this paper, we consider data consisting of multiple networks, each comprised of a different edge set on a common set of nodes. Many models have been proposed for the analysis of such multi-view network data under the assumption that the data views are closely related. In this paper, we provide tools for evaluating t…
We show linear XOR classification is possible and propose equality separation for anomaly detection.
problem Linearly separating XOR data.
method Equality separation, adapting SVM objective for data within/outside margin.
result Equality separation can detect both seen and unseen anomalies.
New method tests causal association using noise contrastive backdoor adjustment.
problem Testing causal association in complex settings with many confounders.
method Backdoor-HSIC (bd-HSIC) using HSIC for independence testing.
result Calibrated and powerful for binary and continuous treatments with many confounders.
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.
Paper proposes a new framework for hypothesis testing in imaging.
problem Challenges in hypothesis testing for imaging data.
method Combines self-supervised imaging, vision-language models, and non-parametric hypothesis testing.
result Demonstrates improved power and robust error control in image-based phenotyping.
Paper proposes a robust hypothesis testing method using Sinkhorn distance.
problem Hypothesis testing for small samples.
method Data-driven approach using Sinkhorn uncertainty sets.
result The method provides a more flexible detector compared to Wasserstein robust test.
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.
Defines computable learning for binary classification over metric spaces.
problem Defines computable PAC learning for binary classification over computable metric spaces.
method Provides sufficient conditions for ERM learners to be computable and bounds the strong Weihrauch degree of an ERM learner.
result Gives a hypothesis class that does not admit any proper computable PAC learner with computable sample function.
Robust test for distributions under Hellinger distance, simpler than optimal tests.
problem Testing and estimating distributions robustly under Hellinger distance.
method Simple robust hypothesis test with optimal sample complexity, robust to Hellinger distance perturbations.
result Empirically demonstrated robustness and power of the test on canonical distributions.
Automated feature selection is important for text categorization to reduce the feature size and to speed up the learning process of classifiers. In this paper, we present a novel and efficient feature selection framework based on the Information Theory, which aims to rank the features with their discriminative capacity…
The article explains how to estimate confusion matrices for classifiers using unlabeled data.
problem Estimating sensitivity and specificity of binary medical diagnostic tests without gold standard tests.
method Modifying diagnostic test solutions to estimate confusion matrices for classifiers on unlabeled data.
result The approach can be used to estimate accuracy statistics for supervised or unsupervised binary classifiers on unlabeled data.
Unified Bayesian framework improves clinical trial hypothesis testing.
problem Lack of transparency and inability to quantify evidence in traditional P-values.
method Interval null hypothesis framework combined with Bayes factor-based tests.
result Bayesian interval hypothesis testing ensures frequentist error control and interpretability.
We revisit resampling procedures for error estimation in binary classification in terms of U-statistics. In particular, we exploit the fact that the error rate estimator involving all learning-testing splits is a U-statistic. Thus, it has minimal variance among all unbiased estimators and is asymptotically normally dis…