# Efficient Online Portfolio with Logarithmic Regret

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2018.

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

- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States](https://mlsanity.com/paper/2202.02765/) (2022)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Online Strongly Convex Optimization with Unknown Delays](https://mlsanity.com/paper/2103.11354/) (2021)
- [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)
- [Damped Online Newton Step for Portfolio Selection](https://mlsanity.com/paper/2202.07574/) (2022)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States](https://mlsanity.com/paper/2210.00997/) (2022)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (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)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [The Hidden Cost of Approximation in Online Mirror Descent](https://mlsanity.com/paper/2511.22283/) (2025)
- [Variational Bayes Portfolio Construction](https://mlsanity.com/paper/2411.06192/) (2024)
- [Duality and Policy Evaluation in Distributionally Robust Bayesian Diffusion Control](https://mlsanity.com/paper/2506.19294/) (2025)

## Abstract (arXiv)

We study the decades-old problem of online portfolio management and propose the first algorithm with logarithmic regret that is not based on Cover's Universal Portfolio algorithm and admits much faster implementation. Specifically Universal Portfolio enjoys optimal regret O(Nln T) for N financial instruments over T rounds, but requires log-concave sampling and has a large polynomial running time. Our algorithm, on the other hand, ensures a slightly larger but still logarithmic regret of O(N2(ln T)4), and is based on the well-studied Online Mirror Descent framework with a novel regularizer that can be implemented via standard optimization methods in time O(TN2.5) per round. The regret of all other existing works is either polynomial in T or has a potentially unbounded factor such as the inverse of the smallest price relative.