Cover Image

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Fan, Foster, Dylan J., Han, Yanjun, Qian, Jian, Rakhlin, Alexander, Xu, Yunbei
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Information Theory Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Estimation via Offline Estimation: An Information-Theoretic Framework
by: Foster, Dylan J., et al.
Published: (2024)

Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
by: Xu, Yunbei, et al.
Published: (2020)

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
by: Chen, Fan, et al.
Published: (2026)

Refined Risk Bounds for Unbounded Losses via Transductive Priors
by: Qian, Jian, et al.
Published: (2024)

A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
by: Jia, Zeyu, et al.
Published: (2025)

Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
by: Chen, Fan, et al.
Published: (2025)

Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
by: Réveillard, William, et al.
Published: (2025)

The van Trees inequality in the spirit of Hajek and Le Cam
by: Elisabeth, Gassiat, et al.
Published: (2024)

Approximate Computation via Le Cam Simulability
by: Akdemir, Deniz
Published: (2025)

Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits
by: Rajaraman, Nived, et al.
Published: (2023)

High-accuracy sampling for diffusion models and log-concave distributions
by: Chen, Fan, et al.
Published: (2026)

Rate of convergence of the smoothed empirical Wasserstein distance
by: Block, Adam, et al.
Published: (2022)

Adaptive Algorithms for Infinitely Many-Armed Bandits: A Unified Framework
by: Pilliat, Emmanuel
Published: (2025)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
by: Tang, Runshi, et al.
Published: (2026)

Pointwise Generalization in Deep Neural Networks
by: Li, Shaojie, et al.
Published: (2026)

On the Variance, Admissibility, and Stability of Empirical Risk Minimization
by: Kur, Gil, et al.
Published: (2023)

Information Lower Bounds for Robust Mean Estimation
by: Degenne, Rémy, et al.
Published: (2024)

Bayesian Design Principles for Frequentist Sequential Learning
by: Xu, Yunbei, et al.
Published: (2023)

Interactive Learning of Single-Index Models via Stochastic Gradient Descent
by: Rajaraman, Nived, et al.
Published: (2026)

Sharp mean-field analysis of permutation mixtures and permutation-invariant decisions
by: Liang, Yiguo, et al.
Published: (2025)

Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
by: Chen, Fan, et al.
Published: (2025)

Le Cam Distortion: A Decision-Theoretic Framework for Robust Transfer Learning
by: Akdemir, Deniz
Published: (2025)

$L_q$ Lower Bounds on Distributed Estimation via Fisher Information
by: Chen, Wei-Ning, et al.
Published: (2024)

An Improved Lower Bound on Cardinality of Support of the Amplitude-Constrained AWGN Channel
by: Wang, Haiyang, et al.
Published: (2025)

Demonstration Experiments
by: Imbens, Guido, et al.
Published: (2026)

Lower Bounds for Kernel Density Estimation on Symmetric Spaces
by: Asta, Dena Marie
Published: (2024)

Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes
by: Han, Yanjun, et al.
Published: (2024)

Two New Families of Local Asymptotically Minimax Lower Bounds in Parameter Estimation
by: Merhav, Neri
Published: (2024)

Approximate independence of permutation mixtures
by: Han, Yanjun, et al.
Published: (2024)

General Lower Bounds for Differentially Private Federated Learning with Arbitrary Public-Transcript Interactions
by: Li, Yicheng
Published: (2026)

High-accuracy log-concave sampling with stochastic queries
by: Chen, Fan, et al.
Published: (2026)

Near-Optimal Learning and Planning in Separated Latent MDPs
by: Chen, Fan, et al.
Published: (2024)

Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits
by: Gu, Yuzhou, et al.
Published: (2025)

An Empirical Bayes Perspective on Heteroskedastic Mean Estimation
by: Han, Yanjun, et al.
Published: (2026)

On the Natural Gradient of the Evidence Lower Bound
by: Ay, Nihat, et al.
Published: (2023)

Optimal Lower Bounds for Online Multicalibration
by: Collina, Natalie, et al.
Published: (2026)

Hyperbolic Network Latent Space Model with Learnable Curvature
by: Li, Jinming, et al.
Published: (2023)

Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression
by: Chen, Fan, et al.
Published: (2025)

A Generalisation of Ville's Inequality to Monotonic Lower Bounds and Thresholds
by: Koolen, Wouter M., et al.
Published: (2025)

The Fragility of Optimized Bandit Algorithms
by: Fan, Lin, et al.
Published: (2021)