论文标题
推动效率重新格雷帕累托前沿用于在线学习投资组合和量子状态
Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States
论文作者
论文摘要
我们重新审视古典在线投资组合选择问题。人们普遍认为，计算复杂性和遗憾之间的权衡是不可避免的，目前涵盖了普遍的投资组合算法，软湾和Ada-Barrons，目前构成了其最先进的帕累托前沿。在本文中，我们介绍了第一种有效的算法，即bisons，该算法在尺寸中是多项式的记忆和每步运行时间要求，从而获得了多种型号的遗憾，从而将ADA-Barrons置于Pareto Frontier。此外，我们通过表明具有对数栏正则化的特定遵循规范的领导者算法来解决一个柯尔特2020的开放问题，对维度的依赖性大大比以前的猜想更大。因此，我们排除了该算法作为帕累托前沿的候选人。我们还将算法和分析扩展到一个比在线投资组合选择更普遍的问题，即。对数损失的量子状态的在线学习。该算法称为Schrodinger's Bisons，是第一个有效的算法，对这个更一般的问题具有多毛的遗憾。
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.
