Cover Image

On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jia, Zeyu, Polyanskiy, Yury, Rakhlin, Alexander
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

High-Rate Quantized Matrix Multiplication II
by: Ordentlich, Or, et al.
Published: (2026)

Price of universality in vector quantization is at most 0.11 bit
by: Harbuzova, Alina, et al.
Published: (2026)

Testing and estimation in orthosymmetric Gaussian sequence model
by: Jia, Zeyu, et al.
Published: (2025)

Optimal Quantization for Matrix Multiplication
by: Ordentlich, Or, et al.
Published: (2024)

WaterSIC: information-theoretically (near) optimal linear layer quantization
by: Lifar, Egor, et al.
Published: (2026)

Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
by: Bongole, Raghav, et al.
Published: (2024)

Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention
by: Yang, Junwen, et al.
Published: (2024)

Minimax Optimality of the Probability Flow ODE for Diffusion Models
by: Cai, Changxiao, et al.
Published: (2025)

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

NestQuant: Nested Lattice Quantization for Matrix Products and LLMs
by: Savkin, Semyon, et al.
Published: (2025)

Online Prediction of Stochastic Sequences with High Probability Regret Bounds
by: Frey, Matthias, et al.
Published: (2026)

Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
by: Liu, Ziyi, et al.
Published: (2024)

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

How Does Variance Shape the Regret in Contextual Bandits?
by: Jia, Zeyu, et al.
Published: (2024)

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
by: Chen, Fan, et al.
Published: (2024)

Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior
by: Polyanskiy, Yury, et al.
Published: (2025)

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

On the Regret of Coded Caching with Adversarial Requests
by: Nayak, Anupam, et al.
Published: (2024)

Best Arm Identification with Minimal Regret
by: Yang, Junwen, et al.
Published: (2024)

On Instability of Minimax Optimal Optimism-Based Bandit Algorithms
by: Praharaj, Samya, et al.
Published: (2025)

Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
by: Makur, Anuran, et al.
Published: (2024)

Probability Tools for Sequential Random Projection
by: Li, Yingru
Published: (2024)

Minimax optimal differentially private synthetic data for smooth queries
by: Ding, Rundong, et al.
Published: (2026)

Minimax optimal submatrix detection: Sharp non-asymptotic rates
by: Knight, Parker, et al.
Published: (2026)

The Conditional Regret-Capacity Theorem for Batch Universal Prediction
by: Bondaschi, Marco, et al.
Published: (2025)

Regret Bounds for Noise-Free Cascaded Kernelized Bandits
by: Li, Zihan, et al.
Published: (2022)

High-Rate Quantized Matrix Multiplication I
by: Ordentlich, Or, et al.
Published: (2026)

Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with $C^{s,λ}$ Targets
by: Lai, Yanming, et al.
Published: (2026)

Unsourced Multiple Access: A Coding Paradigm for Massive Random Access
by: Liva, Gianluigi, et al.
Published: (2024)

Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards
by: Tajdini, Artin, et al.
Published: (2025)

Complexity as Advantage: A Regret-Based Perspective on Emergent Structure
by: Naparstek, Oshri
Published: (2025)

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
by: Panda, Subhodip, et al.
Published: (2026)

Hierarchical Maximum Entropy via the Renormalization Group
by: Asadi, Amir R.
Published: (2025)

TREET: TRansfer Entropy Estimation via Transformers
by: Luxembourg, Omer, et al.
Published: (2024)

Entropy Contractions in Markov Chains: Half-Step, Full-Step and Continuous-Time
by: Caputo, Pietro, et al.
Published: (2024)

Speeding up Speculative Decoding via Sequential Approximate Verification
by: Zhong, Meiyu, et al.
Published: (2025)

Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces
by: Tran-The, Hung, et al.
Published: (2020)

Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions
by: Zhang, Kaihong, et al.
Published: (2024)