Paper offers anytime-valid inference for causal parameters using DML.
problem Classic DML is only valid asymptotically for a fixed sample size.
method Time-uniform DML results for anytime-valid inference.
result Valid inference at any arbitrary stopping time.
GAAVI offers anytime-valid tests for CMF global null and contrasts.
problem Inference on the conditional mean function for high confidence decisions.
method Asymptotic anytime-valid tests for CMF global null and contrasts.
result Achieves asymptotic type-I error guarantees, power one, and optimal sample complexity.
Optimizes random forest inference by defining step order to maximize accuracy.
problem Limited inference time in resource-constrained systems.
method Designs anytime random forest algorithm on step granularity, proposing optimal step order.
result Backward Squirrel Order performs nearly as well as the optimal step order.
Paper develops a new watermarking framework for LLMs.
problem Efficiently distinguishing machine-generated from human text.
method Develops Anchored E-Watermarking framework for anytime-valid inference.
result Framework enables valid, anytime-inference with reduced sample efficiency.
Belief Propagation has been widely used for marginal inference, however it is slow on problems with large-domain variables and high-order factors. Previous work provides useful approximations to facilitate inference on such models, but lacks important anytime properties such as: 1) providing accurate and consistent mar…
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.
Four geometries govern sequential and distribution-free inference.
problem Sequential and distribution-free inference challenges.
method Four distinct admissibility geometries.
result Four classes of admissible procedures are pairwise non-nested.
Adaptive auditing improves AI robustness testing with anytime-valid guarantees.
problem Cost and time of annotation limit rigorous AI failure mode characterization.
method Introduces hypothesis testing framework for adaptive audits using SAVI.
result Proves anytime-valid type-I error control and robustness certification.
Improves decision tree performance by correcting split selection errors.
problem Invalid statistical guarantees in split selection for decision trees.
method Introduces anytime-valid inference to provide valid statistical guarantees.
result Provides anytime-valid control of false splits under arbitrary data streams.
Predictive e-values enhance statistical inference across various tasks.
problem Insufficient data limits traditional statistical inference.
method Apply prediction-powered inference to e-values.
result Every e-value-based inference has a prediction-powered counterpart.
CITE algorithm provides anytime-valid certification of model outputs.
problem Challenges in controlling error levels in LLM self-consistency.
method Certification by Intersection-union Testing with E-processes (CITE) algorithm.
result Provable control of false certification at any prescribed level under arbitrary stopping rules.
This paper presents a new anytime algorithm for the marginal MAP problem in graphical models. The algorithm is described in detail, its complexity and convergence rate are studied, and relations to previous theoretical results for the problem are discussed. It is shown that the algorithm runs in polynomial-time if the …
New methods for anytime-valid off-policy inference in contextual bandits.
problem Estimating properties of hypothetical policies in adaptive experiments.
method Modern martingale techniques for comprehensive OPE inference.
result Valid anytime inference for off-policy mean reward values and entire reward distributions.
This work accelerates gradient descent with anytime convergence guarantees.
problem Improving the convergence rate of gradient descent methods.
method Proposes a stepsize schedule for gradient descent that achieves anytime convergence rates.
result Gradient descent can achieve convergence rates of O(T−1.119) for any stopping time T. Develops an anytime-valid framework for optimal policy identification from logged contextual bandit data.
problem Selecting the optimal policy from a candidate policy class while monitoring evidence continuously.
method Constructs a time-indexed set that retains the true optimal policy set uniformly over time.
result The procedure allows the analyst to monitor policy values, eliminate clearly suboptimal policies, and stop at data-dependent times without invalidating inference.
Optimizes SGD for anytime neural networks, improving accuracy.
problem Training networks that produce increasingly accurate outputs over time.
method Orthogonalized SGD optimizer for nested architectures.
result Significantly improves generalization accuracy of anytime networks.
Enhances early-exit neural networks for anytime classification.
problem Lack of guaranteed prediction quality improvement with longer computation time.
method Post-hoc modification based on Product-of-Experts to enforce conditional monotonicity.
result Achieves conditional monotonicity in prediction quality, enabling anytime classification.
The study introduces anytime learning schedules for large language models without fixed horizons.
problem Training large language models without knowing the total training horizon.
method Theoretical analysis and weight averaging to create anytime learning schedules.
result Theoretical and empirical evidence shows that weight averaging with simple step sizes can achieve comparable final loss to well-tuned cosine schedules.
This work creates a CS for non-negative heavy-tailed data with bounded mean.
problem Constructing a confidence sequence for non-negative heavy-tailed data with bounded mean.
method Non-parametric, non-asymptotic lower confidence sequence construction.
result The constructed CS is efficient and can be converted into a closed-interval CS.
Efficiently audits model fairness with continuous monitoring and flexible data collection.
problem Continuous monitoring and flexible data collection for fairness auditing.
method Sequential, anytime-valid inference and game-theoretic statistics.
result Demonstrated efficacy on three fairness datasets.
We describe an embarrassingly parallel, anytime Monte Carlo method for likelihood-free models. The algorithm starts with the view that the stochasticity of the pseudo-samples generated by the simulator can be controlled externally by a vector of random numbers u, in such a way that the outcome, knowing u, is determinis…
The pioneer deep neural networks (DNNs) have emerged to be deeper or wider for improving their accuracy in various applications of artificial intelligence. However, DNNs are often too heavy to deploy in practice, and it is often required to control their architectures dynamically given computing resource budget, i.e., …
We introduce a new sequential Monte Carlo algorithm we call the particle cascade. The particle cascade is an asynchronous, anytime alternative to traditional particle filtering algorithms. It uses no barrier synchronizations which leads to improved particle throughput and memory efficiency. It is an anytime algorithm i…
APGAI identifies good arms anytime with fixed budget.
problem Identifying a good arm with a fixed sampling budget.
method An anytime algorithm for good arm identification in stochastic bandits.
result APGAI achieves efficient detection of good arms with upper bounds on probability of error and sampling complexity.
We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree---"Extremely Fast Decision Tree", a minor modification to the MOA implementat…
New algorithm guarantees performance on noisy data.
problem Learning with noisy data and heavy-tailed distributions.
method Anytime online-to-batch conversion for smooth objectives.
result Stochastic gradient-based algorithm with sub-Gaussian error bounds.
Extends PPI to sequential setting, improving inference over time.
problem Sequential data growth with unlabelled data.
method Prediction-powered confidence sequence procedures using Ville's inequality and the method of mixtures.
result Asymptotically valid uniformly over time, accommodating prior knowledge.
A universal framework for constructing confidence sets using sequential likelihood mixing.
problem Constructing reliable confidence sets for realizable likelihood functions.
method Sequential likelihood mixing, integrating Bayesian inference and regret inequalities.
result Establishes fundamental connections and provable coverage guarantees for various inference techniques.
We consider the classical problem of prediction with expert advice. In the fixed-time setting, where the time horizon is known in advance, algorithms that achieve the optimal regret are known when there are two, three, or four experts or when the number of experts is large. Much less is known about the problem in the a…
This paper studies the deviations of the regret in a stochastic multi-armed bandit problem. When the total number of plays n is known beforehand by the agent, Audibert et al. (2009) exhibit a policy such that with probability at least 1-1/n, the regret of the policy is of order log(n). They have also shown that such a …
CSA fills a gap in RLVR-trained LLM deployment by providing anytime-valid selective risk control.
problem Deployment of RLVR-trained LLMs in regulated organizations requires a safety certificate for every round without waiting for long-run averages.
method CSA uses a (test statistic, validity guarantee, deployment rule) framework to fill the gap, maintaining a Ville-type e-process per threshold on a Bonferroni grid.
result CSA provides the first anytime-valid selective risk control for RLVR-trained LLMs, matching the long-run average certification rate and satisfying pathwise validity and non-refusing deployment on every cell.
Efficient inference method for adaptive experiments with tighter confidence sequences.
problem Efficient inference of Average Treatment Effect in a changing policy sequential experiment.
method Semiparametric efficient inference using Adaptive Augmented Inverse-Probability Weighted estimator and asymptotic confidence sequences.
result Derives tighter confidence sequences for adaptive experiments under data-dependent stopping times.
I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is simple, intuitive (in hindsight) and comes with the strongest finite-time regret guarantees for a hori…
Anytime MiniBatch speeds up online distributed optimization by handling slow nodes.
problem Mitigating the impact of slow nodes (stragglers) in distributed optimization.
method Proposes an online distributed optimization method that averages minibatch gradients via consensus rounds.
result Prevents stragglers from slowing progress without wasting work.
We propose a general method for constructing hypothesis tests and confidence sets that have finite sample guarantees without regularity conditions. We refer to such procedures as "universal." The method is very simple and is based on a modified version of the usual likelihood ratio statistic, that we call "the split li…
New findings show many popular bandit algorithms are unstable, contradicting minimax optimality.
problem Challenges in statistical inference from bandit algorithms due to adaptive, non-i.i.d. nature.
method Analysis of stability properties of optimism-based bandit algorithms.
result Widely used minimax-optimal UCB-style algorithms are unstable.
Transfer learning techniques have been widely used in the reality that it is difficult to obtain sufficient labeled data in the target domain, but a large amount of auxiliary data can be obtained in the relevant source domain. But most of the existing methods are based on offline data. In practical applications, it is …
Transform non-private e-values into differentially private ones.
problem Leaking sensitive data through non-private e-values.
method Developed a novel biased multiplicative noise mechanism.
result Differentially private e-values maintain strong statistical power and asymptotic equivalence to non-private ones.
An online reinforcement learning algorithm is anytime if it does not need to know in advance the horizon T of the experiment. A well-known technique to obtain an anytime algorithm from any non-anytime algorithm is the "Doubling Trick". In the context of adversarial or stochastic multi-armed bandits, the performance of …
This work optimizes identifying good arms in nonparametric multi-armed bandits.
problem Efficiently identifying arms with high means in nonparametric settings.
method Combining reward-maximizing sampling with a nonparametric sequential test for anytime-valid labeling.
result Achieves minimax optimal stopping times for identifying arms above a threshold.
BRACE addresses noncompliance in bandits, offering methods for recommendation and treatment policies.
problem Noncompliance in bandit problems complicates learning objectives and treatment effects.
method BRACE formalizes objective-choice, identifies direct-control regimes, and proposes a phase-doubling algorithm for IV inversion.
result BRACE delivers valid policy values and structural uncertainty, even under weak identification and homogeneity failure.
Develops anytime-valid stopping rules for SGD based on observed trajectory.
problem Stopping stochastic gradient descent (SGD) based on observed trajectory.
method Develops anytime-valid confidence sequences for stochastic gradient methods.
result Statistically valid, time-uniform stopping rules for SGD across convex and nonconvex settings.
New flexible confidence sequences for robust statistical inference.
problem Creating robust statistical inference methods that work under mild assumptions.
method Proposed a new class of asymptotic time-uniform confidence sequences.
result Sharp asymptotic time-uniform confidence sequences achieved under mild assumptions.
New algorithm identifies best arm with optimal budget usage.
problem Identifying the arm with the highest mean reward from multiple options.
method Proposes Almost Tracking, a closed-form algorithm for anytime best arm identification.
result Proven to be rate-optimal and outperforms existing algorithms.
We study the problem of instance segmentation in biological images with crowded and compact cells. We formulate this task as an integer program where variables correspond to cells and constraints enforce that cells do not overlap. To solve this integer program, we propose a column generation formulation where the prici…
Anytime-valid confirmation of label-shift corrections
problem Small-batch scientific deployments with scarce labeled outcomes
method Conditional e-value and martingale-based rule
result Nonnegative martingale and anytime-valid confirmation rule
Paper improves PAC-Bayes bounds for various loss types.
problem Improving PAC-Bayes bounds for different types of losses.
method Introducing new high-probability PAC-Bayes bounds for bounded and general tail behaviors losses, and extending to anytime-valid bounds.
result New fast-rate and mixed-rate bounds for losses with bounded ranges, and parameter-free bounds for losses with general tail behaviors.
We propose a new anytime hierarchical clustering method that iteratively transforms an arbitrary initial hierarchy on the configuration of measurements along a sequence of trees we prove for a fixed data set must terminate in a chain of nested partitions that satisfies a natural homogeneity requirement. Each recursive …