Unified framework for anytime-valid PAC-Bayes bounds.
problem Deriving time-uniform PAC-Bayes bounds for stochastic processes.
method Combines four tools: nonnegative supermartingales, method of mixtures, Donsker-Varadhan formula, and Ville's inequality.
result Unified PAC-Bayes theorem for a wide class of discrete stochastic processes.
We develop time-uniform confidence spheres for estimating means of random vectors.
problem Sequential mean estimation in high-dimensional spaces.
method Derive time-uniform confidence sphere sequences (CSSs) for various types of random vectors.
result Optimal CSSs for log-concave, sub-Gaussian, and sub- ψ ψ ψ random vectors. New methods for private statistical inference under local differential privacy.
problem Private statistical inference for population means with bounded observations.
method Nonparametric, nonasymptotic statistical inference using a generalized randomized response mechanism.
result Private confidence intervals and sequences for population means under LDP constraints.
Unified stability bounds for noisy SGD across convex and non-convex losses.
problem Deriving generalization bounds for noisy stochastic gradient descent.
method Unified approach using Lyapunov functions and applied probability.
result Time-uniform stability bounds for SGD on various loss functions.
This paper introduces time-uniform CLT-based confidence intervals for statistical inference.
problem Developing valid statistical inference methods for sequential data.
method Time-uniform central limit theory and strong invariance principles.
result Asymptotic confidence sequences (CSs) that are uniformly valid over time.
Paper improves CI and CS for bounded means using betting and mixtures.
problem Estimating means of bounded random variables.
method Composite nonnegative martingales, testing by betting, method of mixtures.
result Empirically outperforms existing CI and CS methods.
The paper provides bounds on the CDF of a variable under nonstationary conditions.
problem Estimating the complete distribution of a random variable under nonstationary conditions.
method Time-uniform and value-uniform bounds on the CDF of the running averaged conditional distribution.
result Presented computationally efficient bounds that are always valid and sometimes trivial.
This study uses neural networks to approximate Bayesian filtering problems.
problem Estimating latent time-series signal statistics from observation sequences.
method Formulated a generic recurrent neural network framework to learn recursive mappings directly.
result Approximation error bounds for filtering in non-compact domains and strong time-uniform bounds.
Unified high-probability regret bounds for online convex optimisation with randomised gradient estimators.
problem Online convex optimisation with randomised gradient estimators for ℓ q \ell_q ℓ q -Lipschitz losses. method FTRL with randomised two-point finite-difference gradient estimators based on cone-measure sampling from ℓ r \ell_r ℓ r -spheres. result Unified high-probability regret bounds for all p , q , r ∈ [ 1 , ∞ ] p,q,r \in [1,\infty] p , q , r ∈ [ 1 , ∞ ] . 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.
The paper develops time-uniform inference methods for stochastic approximation parameters.
problem Statistical inference for parameters in stochastic approximation problems.
method Analysis of averaged iterates convergence rates and construction of asymptotic confidence sequences.
result Valid asymptotic confidence sequences for parameters in stochastic approximation problems.
In this paper, we prove the equivalent of ultracontractive bound of heat semigroup or the uniform upper bound of the heat kernel with the Nash inequality, Log-Sobolev inequalities on graphs. We also show that under the assumption of volume growth and nonnegative curvature C D E ′ ( n , 0 ) CDE'(n,0) C D E ′ ( n , 0 ) the Sobolev inequality, Nash inequa…
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.
We consider the setup of stochastic multi-armed bandits in the case when reward distributions are piecewise i.i.d. and bounded with unknown changepoints. We focus on the case when changes happen simultaneously on all arms, and in stark contrast with the existing literature, we target gap-dependent (as opposed to only g…
UCRL3 improves UCRL2's efficiency in reinforcement learning by reducing exploration.
problem Long burn-in phases in numerical experiments of UCRL2.
method UCRL3 uses state-of-the-art time-uniform concentration inequalities and adaptive support computation to tighten exploration.
result UCRL3 achieves a better numerical improvement over UCRL2 in standard environments.
The paper provides Gaussian approximations for decentralized Federated Learning.
problem Lack of asymptotic statistical guarantees for local SGD in Federated Learning.
method Two generalized Gaussian approximation results for local SGD trajectories.
result Valid multiplier bootstrap procedures and Gaussian bootstrap-based tests for detecting adversarial attacks.
Paper shows how online betting algorithms' regret can be used to create tight confidence sequences.
problem Estimating the expectation of random variables from samples and creating time-uniform confidence sequences.
method Converts the regret guarantee of universal portfolio algorithms into time-uniform concentration inequalities and confidence sequences.
result Numerically obtained confidence sequences are never vacuous and satisfy the law of iterated logarithm.
Develops a parameter-free SGD algorithm with optimal convergence rate.
problem Optimizing parameters in stochastic convex optimization.
method A novel parameter-free algorithm for SGD with high-probability guarantees and adaptive properties.
result Achieves optimal convergence rate with only a double-logarithmic factor increase compared to known-parameter settings.
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.
ES reduces high-probability regret in stochastic linear bandits.
problem High-probability regret in stochastic linear bandits.
method Linear ensemble sampling with standard Gaussian perturbations, analyzing m = Θ ( d log n ) m=Θ(d\log n) m = Θ ( d log n ) ensemble size. result ES achieves i l d e O ( d 3 / 2 n ) ilde O(d^{3/2}\sqrt n) i l d e O ( d 3/2 n ) high-probability regret, closing the gap to Thompson sampling. We consider the evolution of hypersurfaces on the unit sphere S n + 1 \mathbb{S}^{n+1} S n + 1 by smooth functions of the Weingarten map. We introduce the notion of `quasi-ancient' solutions for flows that do not admit non-trivial, convex, ancient solutions. Such solutions are somewhat analogous to ancient solutions for flows such a…
Develops hypothesis tests for conditional distributions using learning-theoretic bounds.
problem Testing differences in conditional distributions and functionals.
method Transforming learning-theoretic bounds into hypothesis tests for conditional expectations.
result Establishes comprehensive foundation for conditional testing, including theoretical guarantees and practical implementations.
Develops a hypothesis testing framework for generalized Thurstone models.
problem Determining whether pairwise comparison data fits a generalized Thurstone model.
method Introduces separation distance and derives upper and lower bounds for testing.
result Critical threshold for testing depends on observation graph topology and scales as Θ ( ( n k ) − 1 / 2 ) Θ((nk)^{-1/2}) Θ (( nk ) − 1/2 ) for complete graphs. Bayes-assisted confidence sequences improve efficiency for bounded means.
problem Efficient uncertainty quantification for bounded IID means without parametric assumptions.
method Bayesian working predictive model selects adaptive martingale updates maximizing predictive log-growth.
result Asymptotically log-optimal performance with informative priors reducing width and sampling effort.
The betting CI outperforms classical methods in constructing confidence intervals for bounded means.
problem Constructing nonasymptotic confidence intervals for bounded means.
method A betting-based approach to define and time-uniform variants of confidence intervals (CSs).
result The betting CI matches the fundamental limits, outperforming existing empirical Bernstein CIs.
Unified stopping rules ensure accurate policies in contextual learning.
problem Stopping data collection to ensure accurate policies in personalized decision problems.
method Developed unified stopping rules based on GLR statistics for pairwise action comparisons.
result Unified stopping rules achieve target precision with fewer samples than benchmarks.
Unified CS for GLMs improves bandit regret bounds.
problem Improving regret bounds for GLMs in bandit settings.
method Unified likelihood ratio-based CS with PAC-Bayesian bound.
result Unified CS attains poly(S)-free regret for Bernoulli.
Detects harmful distribution shifts in deployed models without false alarms.
problem Detecting harmful distribution shifts in deployed models without false alarms.
method Sequential tools for testing if the difference between source and target distributions leads to a significant increase in a risk function.
result Demonstrated the efficacy of the proposed framework through extensive empirical studies.
Unified technique for sequential estimation of convex divergences.
problem Estimating convex divergences between distributions.
method Martingale methods and maximal inequalities for reverse submartingales.
result Valid time-uniform confidence sequences for arbitrary stopping times.
New algorithm improves online learning with reduced discretization.
problem Improving adaptive online learning with refined discretization.
method Continuous time approach to online learning, followed by a new discretization argument.
result Optimal regret bound with O ( V T ) O(\sqrt{V_T}) O ( V T ) dependence on gradient variance. M-FISHER detects and adapts to streaming data shifts with statistical validity and stability.
problem Detecting and adapting to distributional shifts in streaming data.
method Constructs an exponential martingale from non-conformity scores and applies Ville's inequality for detection. Fisher-preconditioned updates for adaptation.
result Establishes M-FISHER as a principled approach for robust, anytime-valid detection and geometrically stable adaptation.
The paper introduces methods to quantify uncertainty in sampling without replacement.
problem Accurately estimating parameters from finite populations sampled without replacement.
method Develops confidence sequences using Bayesian and empirical methods.
result Improved confidence intervals and sequences for sampling without replacement.
Paper tightens PAC-Bayes bounds using coin-betting for better estimates.
problem Estimating mean of random elements with possibly S-dependent parameters.
method Refined PAC-Bayes proof strategy based on coin-betting framework.
result Derives tighter concentration inequalities for all sample sizes.
Deep neural nets approximate random dynamical system trajectories uniformly in time.
problem Approximating trajectories of random dynamical systems over infinite time horizons.
method Recurrent neural networks with simple feedback structures.
result Certain random trajectories can be approximated uniformly in time to any desired accuracy.
Adaptive PCR improves panel data analysis with uniform guarantees.
problem Adaptive data collection in panel data settings.
method Adapting PCR to online settings using martingale concentration.
result Time-uniform guarantees for adaptive PCR in panel data.
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.
Paper tackles unknown variances in best-arm identification.
problem Identifying the best arm with unknown variances in Gaussian distributions.
method Two approaches: empirical variance plugging or adapting transportation costs.
result The impact of unknown variances is small on sample complexity.
New filters match advanced composition for adaptive privacy, with practical constants.
problem Limitations of existing adaptive composition methods.
method Constructed new filters and odometers that match advanced composition rates, including constants.
result Achieved fully adaptive privacy with practical filters and odometers.
Recurrent neural networks' hidden state can be reconstructed from its past, providing a theoretical framework for stability and tracking.
problem Hidden-state stability in RNNs
method Backward coherence analysis
result Almost-sure convergence, rates under mixing, interpretable limiting representation, finite pathwise stopping times, and theoretical framework for time-uniform confidence sequences.
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.
ALEXP improves model selection in linear bandits with exponential regret improvement.
problem Model selection in linear bandits is challenging due to balancing exploration and exploitation.
method ALEXP uses online learning with favorable bias-variance trade-off to emulate full-information feedback.
result ALEXP achieves an exponentially improved ( log M \log M log M ) regret dependence on the number of models M M M . 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.
The paper develops statistical inference for gradient flows in optimization.
problem Uncertainty quantification along the entire optimization path.
method Uniform central limit theorem and algorithm-aware covariance estimator.
result Asymptotically valid confidence intervals for target parameter.
New theory sharpens Q-learning with LDTZ rate, proving it's best of both worlds.
problem Improving Q-learning's theoretical and practical performance.
method Developed a sharp non-asymptotic error bound and central limit theory for Q-learning with PD2Z-ν schedule.
result Q-learning with LDTZ schedule achieves rapid decay and asymptotic convergence guarantees.
Paper tackles SMPC for linear systems with unknown noise distribution.
problem Stochastic MPC for linear systems with chance state constraints and unknown noise distribution.
method Reformulate chance constraints, design robust benchmark SMPC, and develop adaptive SMPC with online noise statistics learning.
result Adaptive SMPC guarantees time-uniform satisfaction of unknown reformulated state constraints with high probability.
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.
Paper proposes a new dynamic pricing method with always-valid online statistical learning.
problem Designing dynamic pricing policies that adapt to online uncertainty and maintain validity.
method Regularized online statistical learning with theoretical guarantees and three major advantages.
result Proposed OORMLP pricing policy secures logarithmic regret in decision horizon.
The study optimizes bounds for comparing training and population loss.
problem Optimizing bounds for comparing training and population loss.
method Derives generic information-theoretic and PAC-Bayesian generalization bounds using convex comparator functions.
result The tightest possible bound is obtained with the comparator being the convex conjugate of the CGF of the bounding distribution.