Online Learning Quantum States with the Logarithmic Loss via VB-FTRL
Wei-Fu Tseng Kai-Chun Chen Zi-Hong Xiao Yen-Huan Li
Online learning quantum states with the logarithmic loss (LL-OLQS) is a
quantum generalization of online portfolio selection, a classic open problem in
the field of online learning for over three decades. The problem also emerges
in designing randomized optimization algorithms for maximum-likelihood quantum
state tomography. Recently, Jezequel et al. (arXiv:2209.13932) proposed the
VB-FTRL algorithm, the first nearly regret-optimal algorithm for OPS with
moderate computational complexity. In this note, we generalize VB-FTRL for
LL-OLQS. Let $d$ denote the dimension and $T$ the number of rounds. The
generalized algorithm achieves a regret rate of $O ( d^2 \log ( d + T ) )$ for
LL-OLQS. Each iteration of the algorithm consists of solving a semidefinite
program that can be implemented in polynomial time by, e.g., cutting-plane
methods. For comparison, the best-known regret rate for LL-OLQS is currently $O
( d^2 \log T )$, achieved by the exponential weight method. However, there is
no explicit implementation available for the exponential weight method for
LL-OLQS. To facilitate the generalization, we introduce the notion of
VB-convexity. VB-convexity is a sufficient condition for the logarithmic
barrier associated with any function to be convex and is of independent
interest.