论文标题
缩水在线牛顿选择投资组合选择
Damped Online Newton Step for Portfolio Selection
论文作者
论文摘要
我们重新审视了经典的在线投资组合选择问题，在每个回合中，学习者在一组投资组合上选择分布来分配其财富。众所周知，对于这个问题而言，使用通用投资组合选择算法可以实现对数的遗憾。但是，所有现有的算法对此问题产生对数后悔的时间和空间复杂性，可以随着回合的总数进行多项范围，使其不切实际。在本文中，我们基于Haipeng等人最近的工作。 2018年，介绍了第一个实用的在线投资组合选择算法，并具有对数遗憾，并且其每轮的时间和空间复杂性仅取决于对数的地平线。我们的方法背后是独立兴趣的两个关键技术新颖性。我们首先表明，在在线牛顿台阶的衰减镜头下降也可以很好地迭代迭代，即使处理时间变化的正规化器。其次，我们提出了一种新的元算法，它实现了适应性的对数遗憾（即，在任何子间隔上对对数的遗憾），以实现可混合的损失。
We revisit the classic online portfolio selection problem, where at each round a learner selects a distribution over a set of portfolios to allocate its wealth. It is known that for this problem a logarithmic regret with respect to Cover's loss is achievable using the Universal Portfolio Selection algorithm, for example. However, all existing algorithms that achieve a logarithmic regret for this problem have per-round time and space complexities that scale polynomially with the total number of rounds, making them impractical. In this paper, we build on the recent work by Haipeng et al. 2018 and present the first practical online portfolio selection algorithm with a logarithmic regret and whose per-round time and space complexities depend only logarithmically on the horizon. Behind our approach are two key technical novelties of independent interest. We first show that the Damped Online Newton steps can approximate mirror descent iterates well, even when dealing with time-varying regularizers. Second, we present a new meta-algorithm that achieves an adaptive logarithmic regret (i.e. a logarithmic regret on any sub-interval) for mixable losses.
