We provide valid confidence intervals for adaptive data analysis.
problem Lack of valid confidence intervals for adaptive statistical queries.
method General framework for instance-specific confidence intervals.
result Orders of magnitude better guarantees than worst-case bounds.
Near-optimal confidence intervals for bounded data.
problem Online inference for sequential decision problems like A/B testing.
method Utilizing Bentkus' concentration results to improve on existing methods.
result Near-optimal confidence intervals confirmed favorable in synthetic and practical applications.
A new differentiable UCB algorithm for linear bandits learns adaptive confidence bounds.
problem Inability of UCB to strike optimal exploration-exploitation due to confidence bounds.
method Proposes a differentiable linear bandit algorithm and a gradient estimator for learning adaptive confidence bounds.
result Achieves a i l d e O ( β ^ d T ) ilde{\mathcal{O}}(\hatβ\sqrt{dT}) i l d e O ( β ^ d T ) upper bound of T T T -round regret. Novel confidence sets improve linear bandit performance by adapting to unknown noise levels.
problem Adapting to unknown noise levels in sequential decision-making.
method Proposed semi-adaptive and variance-adaptive confidence sets.
result Improved regret bounds and better performance in Bayesian optimization tasks.
LqgOpt learns optimal control in unknown LQG systems with minimal regret.
problem Adaptive control in partially observable linear quadratic Gaussian systems with unknown dynamics.
method Optimism in the face of uncertainty, predictor state evolution, closed-loop system identification, confidence bounds.
result Proves a regret upper bound of i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) for LQG systems. Proposes online debiasing estimators for adaptive linear regression.
problem Adaptive data collection leads to non-normal asymptotic behavior in simple methods.
method Online debiasing estimators that correct distributional anomalies.
result Asymptotic normality and minimax lower bound for proposed estimators.
Data-driven method for error estimation without needing class complexity.
problem Constructing confidence intervals for a class of estimates.
method Data-driven approach to derive high-probability upper bounds on maximum error.
result Method naturally adapts to unknown correlation structures and works for finite and infinite classes.
Improved algorithms for stochastic linear bandits using tighter confidence sequences.
problem Stochastic linear bandits with improved worst-case regret guarantees.
method Novel tail bound for adaptive martingale mixtures to construct tighter confidence sequences.
result Linear bandit algorithm achieves competitive worst-case regret.
Designs adaptive controller for networked control systems with wireless data transmission.
problem Adaptive control in networked systems with unreliable wireless channels.
method Upper Confidence Bounds for Networked Control Systems (UCB-NCS) learning rule.
result Non-asymptotic performance guarantees with a regret bound of O(C√T).
Adapts model-based advice to stabilize black-box policies for nonlinear control.
problem Stabilizing machine-learned policies for nonlinear control with limited model information.
method Proposes an adaptive λ λ λ -confident policy to combine black-box and model-based advice. result Proves the stability of the adaptive λ λ λ -confident policy and its competitive ratio. 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.
New method for linear bandits with unknown sparsity, improving sparse regret bounds.
problem Sparse regret bounds for unknown sparsity and adversarial action sets.
method Combines online to confidence set conversions with randomized model selection over nested confidence sets.
result First sparse regret bounds for unknown sparsity and adversarial action sets.
Study optimal adaptive allocation for multi-armed bandits with Markovian rewards.
problem Optimal adaptive allocation for multi-armed bandits with Markovian rewards.
method Round-robin Kullback-Leibler upper confidence bounds for optimal adaptive allocation.
result Logarithmic dependence of regret on time horizon, asymptotically optimal.
Paper proposes a new UCB approach for estimating maximum mean.
problem Estimating the maximum mean in various applications.
method Upper Confidence Bound (UCB) approach with adaptive sampling.
result LSA estimator shows faster bias decay compared to GA.
Study on confidence intervals for Sliced Wasserstein distance, with optimal risk bounds.
problem Statistical inference for the Sliced Wasserstein distance.
method Construct minimax confidence intervals with adaptive lengths.
result Minimax optimal confidence intervals for the Sliced Wasserstein distance.
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.
Adaptive kernel regression with streaming data and unknown variance.
problem Tackling adaptive regularization in streaming kernel regression with unknown noise variance.
method Generalized finite-dimensional linear regression to kernel setup, using self-normalized inequalities for variance estimation and adaptive regularization.
result Valid uniform bounds on mean function value at all points and time steps, leading to improved kernel bandit procedures.
Algorithm aggregates rewards from multiple players to learn related tasks in online bandit learning.
problem Learning related but slightly different tasks in an online setting with heterogeneous feedback.
method RobustAgg ( ε ) (ε) ( ε ) algorithm that aggregates rewards from different players. result Achieves instance-dependent regret guarantees and nearly matching lower bounds.
The paper studies privacy-protected BAI with fixed confidence, deriving lower bounds and proposing an adaptive algorithm.
problem Privacy-protected Best Arm Identification (BAI) in data-sensitive applications.
method Derives lower bounds on sample complexity, proposes AdaP-TT algorithm with Laplace noise, and validates with experiments.
result AdaP-TT matches the sample complexity lower bound up to constants in the high-privacy regime.
The paper proposes an efficient method for estimating ATEs using adaptive experiments.
problem Estimating average treatment effects (ATEs) with minimal sample size and high accuracy.
method The paper defines and uses the efficient treatment-assignment probability to sequentially assign treatments, estimating ATEs using an Adaptive Augmented Inverse Probability Weighting (A2IPW) estimator.
result The proposed experimental design and A2IPW estimator achieve the minimized semiparametric efficiency bound and provide anytime valid confidence intervals for early stopping.
The paper develops adaptive confidence intervals for Efron's Gaussian two-groups model with unknown contamination.
problem Developing robust uncertainty quantification for Efron's Gaussian two-groups model with unknown contamination fraction.
method The approach involves Fourier-based certification procedures to find minimax-optimal adaptive confidence intervals.
result The minimax-optimal length of adaptive confidence intervals is polynomially worse than when contamination fraction is known.
EB-TCε identifies the best arm with ε confidence in stochastic bandits.
problem Identifying the best arm in stochastic bandits with a fixed level of confidence.
method EB-TCε is a novel sampling rule for ε-best arm identification in stochastic bandits.
result EB-TCε is the first anytime algorithm for fixed confidence or fixed budget identification.
Develops method to correct bias in adaptive linear models.
problem Bias in adaptive linear models persists even in infinite data limit.
method W-decorrelation method using coarse-grained data collection policy information.
result Demonstrates empirical benefits in multi-armed bandit and autoregressive time series settings.
New method improves conditional coverage of conformal prediction.
problem Improving conditional coverage in conformal prediction.
method Trainable transformation of conformity scores to improve conditional coverage.
result Highly adaptive to local data structure, outperforming existing methods.
New method optimizes offline linear bandits using different confidence sets.
problem Optimizing offline learning for linear contextual bandits.
method Introduces a family of pessimistic learning rules based on ℓ p \ell_p ℓ p confidence sets. result The π ^ ∞ \hatπ_\infty π ^ ∞ rule achieves minimax performance and strictly dominates other predictors. Improved algorithm for Lipschitz bandit optimization with reduced complexity.
problem Efficiently solving the Lipschitz bandit optimization problem.
method Tree UCB-Hoeffding algorithm with adaptive partitions and tree-based search strategy.
result Achieves the regret lower bound up to a logarithmic factor with O ( T log T ) \mathcal{O}(T\log T) O ( T log T ) computational cost. The paper improves confidence set construction for statistical inference.
problem Constructing reliable confidence sets in statistical inference.
method Establishes a finite-sample bound using effective dimension and generalized self-concordance.
result Developed a confidence set adapted to optimization landscapes.
This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistence, and e…
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.
Calibrates network confidence for unsupervised domain adaptation.
problem Calibrating a model trained on a source domain to a target domain without labeled data.
method Estimates network accuracy on the target domain and calibrates prediction confidence directly in the target domain.
result Significantly outperforms existing methods across standard datasets.
The paper proposes using a discriminator for both domain adaptation and pseudo labeling confidence.
problem Improving generalization of classifiers trained on labeled source data to unlabeled target data.
method Multi-purposing the discriminator to learn domain-invariant feature representations and generate pseudo labels based on confidence.
result The approach enhances classifier performance by providing confidence measures for pseudo labels.
New RL method tackles dynamic MDPs with evolving rewards and states.
problem Dynamic MDPs with evolving rewards and states.
method Sliding Window Upper-Confidence bound for Reinforcement Learning (SWUCRL2-CW) and Bandit-over-Reinforcement Learning (BORL).
result Achieves dynamic regret bound for non-stationary MDPs.
New method predicts sets under unknown covariate shift with high confidence.
problem Adapting to unknown covariate shift in prediction sets.
method PredSet-1Step, a flexible distribution-free method.
result Achieves asymptotic probably approximately correct coverage.
BaNk-UCB tackles batched nonparametric bandits with k-NN regression and UCB.
problem Sequential decision-making with limited online feedback in domains like medicine and marketing.
method Combines k-NN regression with UCB principle for fully nonparametric, adaptive, and simple implementation.
result Near-optimal regret guarantees under Lipschitz smoothness and margin assumptions, with minimax-optimal rates.
Study explores how to efficiently explore communities with limited budget.
problem Maximizing the number of members met with limited budget in community exploration.
method Systematic study from offline optimization to online learning, including greedy methods and upper confidence algorithms.
result Achieved logarithmic and constant regret bounds in online learning setting.
New method for testing graph invariants under undirected models.
problem Testing graph invariants under undirected models.
method Skip-down algorithm for monotone graph invariants.
result Optimal and adaptive confidence intervals for graph invariants.
ARTEO algorithm optimizes safety-critical systems with uncertainty.
problem Decision-making under uncertainty with safety constraints in real-time optimization.
method ARTEO algorithm uses multi-armed bandits as a mathematical programming problem subject to safety constraints, learning unknown characteristics through exploration and incorporating uncertainty quantification.
result ARTEO achieves less cumulative regret with accurate and safe decisions.
LinUCB algorithm handles adaptive sampling biases for linear bandits.
problem Adaptive sampling introduces biases in statistical inference.
method LinUCB algorithm with stability property for linear bandits.
result LinUCB achieves asymptotic normality with Wald-type confidence sets.
Upper and lower bounds on regret for noisy optimization of Brownian motion.
problem Optimizing a one-dimensional Brownian motion with noisy observations.
method Upper bound uses confidence bounds and Markov property; lower bound uses hypothesis testing reduction.
result Upper and lower bounds are tight up to a factor of O ( ( log T ) 1.5 ) O((\log T)^{1.5}) O (( log T ) 1.5 ) . New method constructs confidence sets for GLMs via game theory.
problem Developing reliable confidence intervals for GLM parameters.
method Reduction to sequential prediction games with low regret.
result Online-to-confidence-set conversions provide new types of intervals.
We consider the setting of linear regression in high dimension. We focus on the problem of constructing adaptive and honest confidence sets for the sparse parameter θ, i.e. we want to construct a confidence set for theta that contains theta with high probability, and that is as small as possible. The l_2 diameter of a …
New tighter confidence bounds for sequential kernel regression.
problem Quantifying uncertainty in sequential learning algorithms.
method Martingale tail inequalities and conic programming.
result New confidence bounds are tighter than existing ones.
New algorithm resists corruption in linear contextual bandits.
problem Adversarial corruption in linear contextual bandits.
method Variance-aware algorithm with multi-level partition and adaptive confidence sets.
result Regret bound of i l d e O ( C 2 d ∑ t = 1 T σ t 2 + C 2 R d T ) ilde{O}(C^2d\sqrt{\sum_{t = 1}^T σ_t^2} + C^2R\sqrt{dT}) i l d e O ( C 2 d ∑ t = 1 T σ t 2 + C 2 R d T ) . New confidence intervals improve treatment effect estimation in randomized experiments.
problem Improving confidence intervals for treatment effects in randomized experiments.
method Systematic exploitation of negative dependence or variance adaptivity.
result Achieved nonasymptotic confidence intervals with the same effective sample size as asymptotic ones.
This paper analyzes the multi-armed bandit problem using frequency-domain methods.
problem The exploration-exploitation trade-off in sequential decision-making.
method Proposes a frequency-domain analysis framework, reformulating the bandit process as a signal processing problem.
result Confidence bound term in UCB algorithm is equivalent to a time-varying gain in frequency domain.
New algorithm for active learning in multiple matrix completion problems.
problem Simultaneous matrix completion with unknown ranks and varying sizes.
method MAlocate algorithm that adapts to unknown ranks and sizes.
result Minimax-optimal performance demonstrated with lower-bound analysis.
CONTINA provides adaptive confidence intervals for traffic demand prediction.
problem Uncertainty in future traffic demand predictions and the need for valid confidence intervals.
method Adaptive confidence interval method that adjusts based on deployment errors.
result Valid confidence intervals with shorter lengths and theoretical coverage guarantee.
FAWMF adapts weights for implicit feedback recommendation efficiently.
problem Challenges in treating unobserved data as negative in implicit feedback recommendation.
method FAWMF uses a variational auto-encoder with a parameterized neural network to adaptively assign personalized data confidence weights, and fBGD for efficient learning.
result FAWMF and fBGD outperform existing methods in real-world datasets.