Paper proposes universally consistent K-sample tests using any dependence measure.
problem Testing whether K groups of data points are drawn from the same distribution.
method Demonstrates the use of any dependence measure for K-sample testing.
result Achieves universally consistent K-sample testing using distance correlation and Hilbert-Schmidt independence criterion.
High-dimensional k-sample comparison is a common applied problem. We construct a class of easy-to-implement nonparametric distribution-free tests based on new tools and unexplored connections with spectral graph theory. The test is shown to possess various desirable properties along with a characteristic exploratory fl…
We introduce hyppo, a unified library for performing multivariate hypothesis testing, including independence, two-sample, and k-sample testing. While many multivariate independence tests have R packages available, the interfaces are inconsistent and most are not available in Python. hyppo includes many state of the art…
The paper addresses hypothesis selection with local differential privacy, requiring more samples than non-private methods.
problem Hypothesis selection under local differential privacy constraints.
method Develops algorithms for hypothesis selection with local differential privacy, achieving near-optimal sample and round complexities.
result Non-interactive algorithms for k-wise simple hypothesis testing require O~(k) samples and O(loglogk) rounds of interaction. Private method measures nonlinear correlations between data hosted across two entities.
problem Measuring nonlinear correlations between sensitive data hosted across multiple parties while preserving privacy.
method Differentially private estimator of distance correlation.
result First private estimator of nonlinear correlations in a multi-party setup.
Massively parallel RWS improves inference in complex models.
problem Exponential sample requirement for effective importance weighting.
method Draws K samples of all n latent variables and individually reasons through all combinations. result Significant improvements over standard RWS.
Paper proposes a chi-square test for distance correlation.
problem Testing distance correlation is computationally expensive.
method Proposes a chi-square test for distance correlation, non-parametric, fast, applicable to various metrics.
result Chi-square test exhibits similar power to permutation test and can be valid and universally consistent for testing independence.
CEDA analyzes large categorical datasets using tree geometry and binary codes.
problem Analyzing large categorical datasets with extreme-K samples. method CEDA uses tree geometry and binary codes to analyze categorical data.
result CEDA discovers patterns and evaluates their reliability in large categorical datasets.
Algorithm learns CNF formulas from random solutions under specific conditions.
problem Learning a CNF formula from uniform random solutions.
method Revisits Valiant's algorithm and applies Lovász local lemma conditions.
result Significantly reduces sample complexity for learning CNFs.
New metrics improve quantum ensemble learning efficiency and power.
problem Quantum ensembles' distances poorly understood due to measurement constraints.
method Introduce MMD-k hierarchy of integral probability metrics for quantum ensembles. result MMD-k requires fewer samples for full discriminative power at higher k. Three-layer neural networks learn hierarchical polynomial functions efficiently.
problem Learning hierarchical polynomial functions with three-layer neural networks.
method Layerwise gradient descent on square loss, focusing on feature learning.
result Achieves optimal sample complexity for learning hierarchical polynomials.
Recurrent models can produce infinite sequences, causing bias; new methods prevent this.
problem Inconsistency in decoding infinite-length sequences from recurrent language models.
method Defined and proved inconsistency of common decoding algorithms; proposed remedies.
result Proposed methods prevent inconsistency in practice.
Study uses reinforcement learning to optimize portfolios under recursive utility.
problem Improving portfolio allocation using risk-sensitive objectives.
method Approximated certainty equivalent via Monte Carlo, trained actor-critic algorithms (PPO, A2C).
result Recursive-utility agent outperforms discounted baseline in Sharpe ratio, max drawdown, and cumulative return.
We introduce a new sampling method for large language models that balances diversity and parallelism.
problem Balancing diversity and parallelism in decoding for large language models.
method Arithmetic sampling framework compatible with various sampling variations.
result Improves estimation of expected BLEU score reward and reduces the gap with beam search.
Software package assesses spherical data distributions and clusters.
problem Assessing and clustering spherical data distributions.
method Innovative goodness-of-fit tests and clustering algorithms using kernel-based quadratic distances.
result Efficient and mathematically sound goodness-of-fit tests for spherical data.
We study three fundamental statistical-learning problems: distribution estimation, property estimation, and property testing. We establish the profile maximum likelihood (PML) estimator as the first unified sample-optimal approach to a wide range of learning tasks. In particular, for every alphabet size k and desired…
Novel anti-grokking phase discovered in neural networks, revealed by HTSR layer quality metric.
problem Understanding and detecting overfitting in neural networks.
method 3-layer MLP, weight decay, HTSR layer quality metric α, correlation traps, Kolmogorov–Smirnov tests. result Anti-grokking phase detected late in training, revealed by α<2 and correlation traps. A new measure k-variance captures local distributional shape.
problem Summarizing distributional shape with local information.
method Random bipartite matchings and stochastic approximation.
result Easily approximated k-variance measures capture local distributional properties. Comprisk simplifies competing-risks analysis in Python.
problem Analyzing medical time-to-event data with competing risks.
method A scikit-learn-compatible toolkit for competing-risks survival analysis.
result Comprisk provides a unified API for various competing-risks methods.
Study learns Gaussian mixtures from censored data.
problem Learning Gaussian mixtures with incomplete data.
method Proposes an algorithm to estimate weights and means with minimal samples.
result Achieves accurate estimation with very few samples.
OPORP combines permutation and random projection for efficient data vector compression.
problem Efficiently estimating cosine similarity in embedding-based retrieval applications.
method OPORP uses a permutation followed by a random vector dot product, then aggregates and normalizes the results into bins.
result OPORP improves the estimation of cosine similarity, reducing variance and improving accuracy.
A new SGD variant chooses the sample with lowest loss to make the model more robust to outliers.
problem Outliers can skew the parameters of machine learning models trained via SGD.
method Choose a set of k samples, then select the one with the smallest current loss for update.
result The new method makes SGD more robust for ML problems that are sums of convex losses.
We consider two multi-armed bandit problems with n arms: (i) given an ε>0, identify an arm with mean that is within ε of the largest mean and (ii) given a threshold μ0 and integer k, identify k arms with means larger than μ0. Existing lower bounds and algorithms for the PAC framework suggest that both …
A recently proposed SLOPE estimator (arXiv:1407.3824) has been shown to adaptively achieve the minimax ℓ2 estimation rate under high-dimensional sparse linear regression models (arXiv:1503.08393). Such minimax optimality holds in the regime where the sparsity level k, sample size n, and dimension p satisfy …
Adaptive contrastive search improves text generation quality and diversity.
problem Decoding high-quality text from language model outputs.
method Adaptive contrastive search incorporating uncertainty-guided degeneration penalty.
result Enhanced text generation quality and diversity across different models and datasets.
Multi-sample, importance-weighted variational autoencoders (IWAE) give tighter bounds and more accurate uncertainty estimates than variational autoencoders (VAE) trained with a standard single-sample objective. However, IWAEs scale poorly: as the latent dimensionality grows, they require exponentially many samples to r…
We characterize the communication complexity of the following distributed estimation problem. Alice and Bob observe infinitely many iid copies of ρ-correlated unit-variance (Gaussian or ±1 binary) random variables, with unknown ρ∈[−1,1]. By interactively exchanging k bits, Bob wants to produce an estimate $…
A new growth model for dynamic networks using Markovian latent points.
problem Modeling temporal dynamic networks with latent points and distances.
method Markovian latent space dynamic with Euclidean Sphere sampling and connection probabilities based on geodesic distances.
result Theoretical guarantees for non-parametric estimation of the latitude and envelope functions.
New measure FTC quantifies how much a ReLU network can fine-tune.
problem Analyzing memorization capacity in fine-tuned neural networks.
method Defined Fine-Tuning Capacity (FTC) for additive fine-tuning of ReLU networks.
result Upper and lower bounds on FTC for 2 and 3-layer ReLU networks.
Improved linear regression for diverse data batches.
problem Learning from multiple heterogeneous data sources.
method Gradient-based algorithm for different input distributions.
result Significant reduction in the number of required batches and sample size.
Optimal sampling bounds for various classification losses under different regularization terms.
problem Achieving optimal sampling complexity for classification losses under different regularization terms.
method Proved optimal sampling bounds for a broad class of Lipschitz continuous classification loss functions under various regularization terms.
result Proved k2/ε2 upper and lower bounds for ∥⋅∥2/k regularization, and k/ε2 upper and lower bounds for ∥⋅∥1/k regularization. Lower bounds show density estimation requires linear samples or query time.
problem Statistical-computational trade-offs in density estimation.
method Lower bound analysis on data structures.
result Lower bounds demonstrate statistical-computational trade-offs for density estimation.
Study shows inefficiency of sparse linear regression learning with fewer than Ω(k^2) samples.
problem Efficiency of sparse linear regression learning with minimal samples.
method Reduction to sparse PCA problems and lower bounds.
result Efficient algorithms for sparse linear regression require at least Ω(k^2) samples.
Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \mathbf{E}_v [f_v\big(\mathbf{E}_…
Debate over the existence of branches in the stellar activity-rotation diagrams continues. Application of modern time series analysis tools to study the mean cycle periods in chromospheric activity index is lacking. We develop such models, based on Gaussian processes, for one-dimensional time series and apply it to the…
Given data drawn from an unknown distribution, D, to what extent is it possible to ``amplify'' this dataset and output an even larger set of samples that appear to have been drawn from D? We formalize this question as follows: an (n,m) amplification procedure takes as input n independent draws from an …
Estimates linear models from self-selected data, addressing econometric challenges.
problem Estimating linear models from self-selected data with known or unknown selection criteria.
method Developed efficient algorithms for both known and unknown selection criteria.
result Identified and estimated linear models from self-selected data, accommodating various selection criteria.
Estimates population size using capture-recapture designs with binary indicators.
problem Estimating population size from capture-recapture data with binary indicators.
method Proposes a modern method using undersmoothed lasso model to estimate the target parameter of interest.
result The choice of constraint on the K-dimensional distribution significantly impacts the value of the estimand.
Many methods for automated software test generation, including some that explicitly use machine learning (and some that use ML more broadly conceived) derive new tests from existing tests (often referred to as seeds). Often, the seed tests from which new tests are derived are manually constructed, or at least simpler t…
A family of maximum mean discrepancy (MMD) kernel two-sample tests is introduced. Members of the test family are called Block-tests or B-tests, since the test statistic is an average over MMDs computed on subsets of the samples. The choice of block size allows control over the tradeoff between test power and computatio…
USP test improves on Pearson's chi-squared and G-test for independence.
problem Deficiencies in Pearson's chi-squared and G-test for independence. method USP test based on U-statistic estimator of population dependence measure. result USP test controls size, handles small cell counts, and detects minimal violations of independence.
E-C2ST uses E-values for high-dimensional data two-sample tests.
problem Statistical testing for high-dimensional data.
method Combines split likelihood ratio tests and predictive independence tests, using E-values for anytime-valid sequential tests.
result E-C2ST achieves enhanced statistical power by partitioning datasets into multiple batches.
This paper provides a comprehensive survey of Machine Learning Testing (ML testing) research. It covers 144 papers on testing properties (e.g., correctness, robustness, and fairness), testing components (e.g., the data, learning program, and framework), testing workflow (e.g., test generation and test evaluation), and …
Cheap permutation tests speed up distribution testing without sacrificing accuracy.
problem Efficiently testing distribution differences and independence.
method Group datapoints into bins and permute only these bins, using stored sufficient statistics.
result Cheap permutation tests maintain the accuracy and optimality of standard tests but are significantly faster.
The paper tests properties of multiple distributions with limited samples.
problem Testing properties of multiple distributions with few samples.
method Designing testers for uniformity, identity, and closeness testing under specific conditions.
result Sample optimal testers for uniformity, identity, and closeness testing are provided.
Optimizes two-sample tests for non-Euclidean domains using spectral regularization.
problem Optimizing two-sample tests for non-Euclidean domains.
method Spectral regularization of MMD test to achieve minimax optimality.
result Proposes a spectral regularization method that improves test optimality.
DRIFT uses RL to automate functional software testing efficiently.
problem Efficient and reliable automated software testing.
method DRIFT employs Q-learning with Graph Neural Networks on symbolic UI representations.
result DRIFT can robustly test software functionalities in a fully automated manner.
Post hoc test for Sharpe ratio improves pairwise comparisons.
problem Improving pairwise comparisons of Sharpe ratios.
method Analogous to Tukey's test, applied after rejecting equal Signal-Noise ratios.
result Maintains nominal type I rate and is moderately powerful.