Damped Online Newton Step for Portfolio Selection

Zakaria Mhammedi, Alexander Rakhlin
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:5561-5595, 2022.

Abstract

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 Luo 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. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-mhammedi22b, title = {Damped Online Newton Step for Portfolio Selection}, author = {Mhammedi, Zakaria and Rakhlin, Alexander}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {5561--5595}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/mhammedi22b/mhammedi22b.pdf}, url = {https://proceedings.mlr.press/v178/mhammedi22b.html}, abstract = {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 Luo 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. 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.} }
Endnote
%0 Conference Paper %T Damped Online Newton Step for Portfolio Selection %A Zakaria Mhammedi %A Alexander Rakhlin %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-mhammedi22b %I PMLR %P 5561--5595 %U https://proceedings.mlr.press/v178/mhammedi22b.html %V 178 %X 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 Luo 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. 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.
APA
Mhammedi, Z. & Rakhlin, A.. (2022). Damped Online Newton Step for Portfolio Selection. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5561-5595 Available from https://proceedings.mlr.press/v178/mhammedi22b.html.

Related Material