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

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

URL: http://arxiv.org/abs/2503.17823v1
Date: Sat, 22 Mar 2025 17:26:34 GMT
Title: On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
Authors: Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin,
Abstract summary: We show that the minimax regret for the case of no side information can be upper bounded in terms of sequential square-root entropy.<n>For the problem of sequential probability assignment with side information, we develop both upper and lower bounds based on the aforementioned entropy.
Score: 70.10668953625247
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the problem of sequential probability assignment under logarithmic loss, both with and without side information. Our objective is to analyze the minimax regret -- a notion extensively studied in the literature -- in terms of geometric quantities, such as covering numbers and scale-sensitive dimensions. We show that the minimax regret for the case of no side information (equivalently, the Shtarkov sum) can be upper bounded in terms of sequential square-root entropy, a notion closely related to Hellinger distance. For the problem of sequential probability assignment with side information, we develop both upper and lower bounds based on the aforementioned entropy. The lower bound matches the upper bound, up to log factors, for classes in the Donsker regime (according to our definition of entropy).

Related papers

Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood [28.94461817548213]
We introduce a novel complexity measure, the emphcontextual Shtarkov sum, corresponding to the Shtarkov sum after projection onto a multiary context tree. We derive the minimax optimal strategy, dubbed emph Normalized Maximum Likelihood (cNML) Our results hold for sequential experts, beyond binary labels, which are settings rarely considered in prior work.
arXiv Detail & Related papers (2024-10-04T18:31:12Z)
Dimension reduction and the gradient flow of relative entropy [0.0]
Dimension reduction, widely used in science, maps high-dimensional data into low-dimensional space. We investigate a basic mathematical model underlying the techniques of neighborhood embedding (SNE) and its popular variant t-SNE. The aim is to map these points to low dimensions in an optimal way so that similar points are closer together.
arXiv Detail & Related papers (2024-09-25T14:23:04Z)
Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
arXiv Detail & Related papers (2023-02-02T18:59:30Z)
Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
We introduce a notion of expected worst case minimax regret that generalizes and encompasses prior known minimax regrets. For such minimax regrets we establish tight bounds via a novel concept of upper global sequential covering. We demonstrate the effectiveness of our approach by establishing tight bounds on the expected worst case minimax regrets for logarithmic loss and general mixable losses.
arXiv Detail & Related papers (2022-09-09T17:31:46Z)
A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
This paper develops a dimensionality reduction method that allows us to move the optimization to a finite-dimensional setting with an explicit bound on the dimension. In order to make progress on the problem, we restrict ourselves to Bayesian risks induced by a relatively large class of loss functions, namely Bregman divergences.
arXiv Detail & Related papers (2022-02-23T16:22:28Z)
Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
arXiv Detail & Related papers (2021-11-01T16:35:41Z)
A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs) We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
arXiv Detail & Related papers (2021-06-24T13:46:09Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
arXiv Detail & Related papers (2020-08-28T14:46:56Z)
Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance [37.0414602993676]
We show that for any expert class with (sequential) metric entropy $mathcalO(gamma-p)$ at scale $gamma$, the minimax regret is $mathcalO(np/(p+1))$. As an application of our techniques, we resolve the minimax regret for nonparametric Lipschitz classes of experts.
arXiv Detail & Related papers (2020-07-02T14:47:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.