# Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 6 Feb 2022.

## Builds on (most cited first, 4 of 4)

- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Efficient Online Portfolio with Logarithmic Regret](https://mlsanity.com/paper/1805.07430/) (2018)
- [Soft-Bayes: Prod for Mixtures of Experts with Log-Loss](https://mlsanity.com/paper/1901.02230/) (2019)

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

- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback](https://mlsanity.com/paper/2310.11550/) (2023)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [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)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [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)
- [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography](https://mlsanity.com/paper/2211.12880/) (2022)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [The Invisible Handshake: Persistent Overpricing by Adaptive Market Agents](https://mlsanity.com/paper/2510.15995/) (2025)

## Abstract (arXiv)

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.