# Efficient and Near-Optimal Online Portfolio Selection

arXiv: https://arxiv.org/abs/2209.13932 · HTML: https://mlsanity.com/paper/2209.13932/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2022.

## Built on by (most cited first, 13 of 13)

- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [Quasi-Newton Steps for Efficient Online Exp-Concave Optimization](https://mlsanity.com/paper/2211.01357/) (2022)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [Online learning of a panoply of quantum objects](https://mlsanity.com/paper/2406.04245/) (2024)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Optimistic Interior Point Methods for Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2502.07774/) (2025)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [Online Learning Quantum States with the Logarithmic Loss via VB-FTRL](https://mlsanity.com/paper/2311.04237/) (2023)
- [Variational Bayes Portfolio Construction](https://mlsanity.com/paper/2411.06192/) (2024)
- [The Invisible Handshake: Persistent Overpricing by Adaptive Market Agents](https://mlsanity.com/paper/2510.15995/) (2025)

## Abstract (arXiv)

In the problem of online portfolio selection as formulated by Cover (1991), the trader repeatedly distributes her capital over  d  assets in each of  T > 1  rounds, with the goal of maximizing the total return. Cover proposed an algorithm, termed Universal Portfolios, that performs nearly as well as the best (in hindsight) static assignment of a portfolio, with an  O(dlog(T))  regret in terms of the logarithmic return. Without imposing any restrictions on the market this guarantee is known to be worst-case optimal, and no other algorithm attaining it has been discovered so far. Unfortunately, Cover's algorithm crucially relies on computing certain  d -dimensional integral which must be approximated in any implementation; this results in a prohibitive  tilde O(d4(T+d)14)  per-round runtime for the fastest known implementation due to Kalai and Vempala (2002). We propose an algorithm for online portfolio selection that admits essentially the same regret guarantee as Universal Portfolios -- up to a constant factor and replacement of  log(T)  with  log(T+d)  -- yet has a drastically reduced runtime of  tilde O(d2(T+d))  per round. The selected portfolio minimizes the current logarithmic loss regularized by the log-determinant of its Hessian -- equivalently, the hybrid logarithmic-volumetric barrier of the polytope specified by the asset return vectors. As such, our work reveals surprising connections of online portfolio selection with two classical topics in optimization theory: cutting-plane and interior-point algorithms.