Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States
This work addresses the efficiency-regret trade-off in online learning for portfolio selection and quantum state estimation, offering significant improvements over prior methods.
The authors tackled the online portfolio selection problem by introducing BISONS, the first efficient algorithm achieving polylogarithmic regret with polynomial memory and runtime, displacing ADA-BARRONS from the Pareto frontier, and extended it to online learning of quantum states with SCHRODINGER'S BISONS, also achieving polylogarithmic regret.
We revisit the classical online portfolio selection problem. It is widely assumed that a trade-off between computational complexity and regret is unavoidable, with Cover's Universal Portfolios algorithm, SOFT-BAYES and ADA-BARRONS currently constituting its state-of-the-art Pareto frontier. In this paper, we present the first efficient algorithm, BISONS, that obtains polylogarithmic regret with memory and per-step running time requirements that are polynomial in the dimension, displacing ADA-BARRONS from the Pareto frontier. Additionally, we resolve a COLT 2020 open problem by showing that a certain Follow-The-Regularized-Leader algorithm with log-barrier regularization suffers an exponentially larger dependence on the dimension than previously conjectured. Thus, we rule out this algorithm as a candidate for the Pareto frontier. We also extend our algorithm and analysis to a more general problem than online portfolio selection, viz. online learning of quantum states with log loss. This algorithm, called SCHRODINGER'S BISONS, is the first efficient algorithm with polylogarithmic regret for this more general problem.