Regret Lower Bound
A metric in online learning theory that characterizes a lower bound on algorithm performance, namely the minimum possible rate of the cumulative loss gap of any algorithm relative to the best strategy in hindsight. Regret lower bounds characterize the intrinsic difficulty limit of a problem, and matching an algorithmic upper bound indicates minimax optimality.
Timeline (last 90 days)
The paper establishes for the first time a regret lower bound for online learning of quantum states under the logarithmic loss.
For a quantum system of dimension d, the regret lower bound for online learning of quantum states grows at a rate of at least Ω(√T), where T is the number of rounds.
The paper points out that whether the regret lower bound applies to other loss functions (such as squared loss) remains unclear.
Prior to this paper, regret lower bounds for general kernels had been missing, with nearly matching lower bounds derived only for specific kernels such as the squared exponential kernel and the Matérn kernel.
All Facts (4)
The paper establishes for the first time a regret lower bound for online learning of quantum states under the logarithmic loss.
50%UnverifiedFor a quantum system of dimension d, the regret lower bound for online learning of quantum states grows at a rate of at least Ω(√T), where T is the number of rounds.
50%UnverifiedThe paper points out that whether the regret lower bound applies to other loss functions (such as squared loss) remains unclear.
50%UnverifiedPrior to this paper, regret lower bounds for general kernels had been missing, with nearly matching lower bounds derived only for specific kernels such as the squared exponential kernel and the Matérn kernel.
50%