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.
A new approach for anytime prediction using thin sub-networks and sparsity.
problem Efficient anytime prediction for deep neural networks.
method Training thin sub-networks and forcing sparsity on multi-branch network parameters.
result Thin sub-networks significantly outperform state-of-the-art dense architectures for anytime prediction.
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.
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.
Optimal algorithm found for anytime regret with two experts.
problem Minimizing regret in prediction with two experts when time horizon is unknown.
method Designing a minimax optimal algorithm using ideas from stochastic calculus.
result Proved the optimal regret is γ√t / 2 for all time steps t.
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.
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
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.
Extends FC-RAG to anytime-valid sequential coverage for language model swarms.
problem Maintain distribution-free coverage for a swarm of weak language models over time.
method Introduces Anytime-FC-RAG, a sequential extension with a summable calibration-deviation budget.
result Achieves time-uniform alarm validity and safety under predictable adaptive control.
Develops anytime-valid conformal and PAC prediction for streaming data.
problem Lack of guarantee in traditional conformal methods for sequential settings.
method Extends conformal and PAC prediction frameworks to handle streaming data.
result Provides anytime-valid prediction sets for sequential settings.
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. 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.
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.
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.
Paper studies continuous prediction with experts' advice using differential equations.
problem Continuous prediction with experts' advice in online learning.
method Continuous-time stochastic calculus and differential equations.
result Improved guarantees for quantile regret with continuous-time algorithm.
Extends risk control to adaptive data collection, anytime-valid guarantees.
problem Ensuring safety of machine learning models with critical risk measures.
method Sequential risk controlling prediction sets (RCPS) for adaptive data collection and active labeling.
result Anytime-valid guarantees for risk control in sequential data collection.
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.
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.
Hedge algorithm proves optimal in stochastic expert advice problems.
problem Prediction with expert advice in stochastic setting.
method Analyzed Hedge algorithm with decreasing learning rate in online stochastic setting.
result Hedge algorithm is worst-case optimal and adaptive in stochastic setting.
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.
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.
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.
Paper proposes an online transfer learning framework using online bagging.
problem Difficulty in obtaining sufficient labeled data in the target domain.
method Ensemble approach with online bagging for anytime transfer learning.
result Effectiveness of the proposed algorithms demonstrated on real data sets.
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 …
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…
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.
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.
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.
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.
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.
Procedure confirms covariate balance anytime from unlabeled data.
problem Ensuring covariate balance in sequential data.
method Time-uniform confidence sequences for continuous monitoring.
result Probability of false confirmation controlled.
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…
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.
A new method for multiple testing reduces false discoveries while maximizing power.
problem Maximizing statistical power while controlling false discoveries in multiple testing scenarios.
method Adaptive sampling approach inspired by multi-armed bandits to minimize sample size.
result The method achieves sample complexity close to information theoretic lower bounds and outperforms uniform sampling.
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.
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 …
E-values enhance conformal prediction methods.
problem Distribution-free uncertainty quantification.
method Reformulation of conformal prediction using e-values.
result E-values offer new theoretical and practical capabilities.
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 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.
Paper develops an efficient online watermark detection for AI-generated text.
problem Detecting AI-generated text from human-written content efficiently.
method Rao-Blackwellized e-processes for anytime-valid inference in streaming generation.
result The method enables recursive token-level evidence updates without storing full history.
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.
The paper extends conformal risk control to be valid with high probability over a growing calibration dataset.
problem Valid risk control over a growing calibration dataset.
method Quantile-based arguments for anytime-valid control.
result Guarantees remain valid with high probability over a cumulatively growing calibration dataset.
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 …
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.
Efficiently learns loss functions for better model performance.
problem Finding an optimal loss function for model validation.
method Asymptotically optimal anytime algorithm in worst case, provably efficient in idealized case.
result Significantly faster than state-of-the-art alternatives for tuning loss function hyperparameters.
EENNs improve inference efficiency but need nested prediction sets for reliable uncertainty estimates.
problem Non-nested prediction sets from standard uncertainty quantification methods in EENNs.
method Introduced anytime-valid confidence sequences (AVCSs) tailored for EENNs.
result AVCSs generate nested prediction sets across EENN exits, addressing the issue of non-nested sets.