Cover Image

The Conditional Regret-Capacity Theorem for Batch Universal Prediction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bondaschi, Marco, Gastpar, Michael
Format:	Preprint
Published:	2025
Subjects:	Information Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Batch Universal Prediction
by: Bondaschi, Marco, et al.
Published: (2024)

Alpha-NML Universal Predictors
by: Bondaschi, Marco, et al.
Published: (2022)

Transformers on Markov Data: Constant Depth Suffices
by: Rajaraman, Nived, et al.
Published: (2024)

Local to Global: Learning Dynamics and Effect of Initialization for Transformers
by: Makkuva, Ashok Vardhan, et al.
Published: (2024)

Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models
by: Nagle, Alliot, et al.
Published: (2024)

Batch Normalization Decomposed
by: Nachum, Ido, et al.
Published: (2024)

Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains
by: Makkuva, Ashok Vardhan, et al.
Published: (2024)

From Markov to Laplace: How Mamba In-Context Learns Markov Chains
by: Bondaschi, Marco, et al.
Published: (2025)

LASER: Linear Compression in Wireless Distributed Optimization
by: Makkuva, Ashok Vardhan, et al.
Published: (2023)

Block-Sample MAC-Bayes Generalization Bounds
by: Frey, Matthias, et al.
Published: (2026)

Universal Batch Learning Under The Misspecification Setting
by: Vituri, Shlomi, et al.
Published: (2024)

Locally Private Parametric Methods for Change-Point Detection
by: Yadav, Anuj Kumar, et al.
Published: (2026)

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

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)

Batched Kernelized Bandits: Refinements and Extensions
by: Ma, Chenkai, et al.
Published: (2026)

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

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)

On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
by: Jia, Zeyu, et al.
Published: (2025)

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)

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

Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Sampling
by: Shah, Mohammad Taha, et al.
Published: (2025)

Predictability Analysis of Regression Problems via Conditional Entropy Estimations
by: Fang, Yu-Hsueh, et al.
Published: (2024)

Time-Series JEPA for Predictive Remote Control under Capacity-Limited Networks
by: Girgis, Abanoub M., et al.
Published: (2024)

Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression
by: Ioushua, Shahar Stein, et al.
Published: (2023)

Innovation Capacity of Dynamical Learning Systems
by: Polloreno, Anthony M.
Published: (2026)

Maximal-Capacity Discrete Memoryless Channel Identification
by: Egger, Maximilian, et al.
Published: (2024)

Tight Regret Bounds for Bayesian Optimization in One Dimension
by: Scarlett, Jonathan
Published: (2018)

Optimal Regret of Bernoulli Bandits under Global Differential Privacy
by: Azize, Achraf, et al.
Published: (2025)

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
by: Zamir, Guy, et al.
Published: (2026)

On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
by: Hou, Yunlong, et al.
Published: (2026)

Learning Capacity: A Measure of the Effective Dimensionality of a Model
by: Chen, Daiwei, et al.
Published: (2023)

Semi-supervised Batch Learning From Logged Data
by: Aminian, Gholamali, et al.
Published: (2022)

Minimizing Queue Length Regret for Arbitrarily Varying Channels
by: Krishnakumar, G, et al.
Published: (2025)

No-Regret Bayesian Recommendation to Homogeneous Users
by: Feng, Yiding, et al.
Published: (2022)

Model non-collapse: Minimax bounds for recursive discrete distribution estimation
by: Kanabar, Millen, et al.
Published: (2025)

Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval
by: Barnfield, Nicholas, et al.
Published: (2026)