Pushing the Efficiency-Regret Pareto Frontier for Online Learning of
Portfolios and Quantum States
- URL: http://arxiv.org/abs/2202.02765v1
- Date: Sun, 6 Feb 2022 12:15:55 GMT
- Title: Pushing the Efficiency-Regret Pareto Frontier for Online Learning of
Portfolios and Quantum States
- Authors: Julian Zimmert, Naman Agarwal, Satyen Kale
- Abstract summary: We revisit the classical online portfolio selection problem.
We present the first efficient algorithm, BISONS, that obtains polylogarithmic regret.
We extend our algorithm and analysis to a more general problem, online learning of quantum states with log loss.
- Score: 33.073320699506326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Second Order Methods for Bandit Optimization and Control [34.51425758864638]
We show that our algorithm achieves optimal (in terms of terms of convex functions that we call $kappa$-2020) regret bounds for a large class of convex functions.
We also investigate the adaptation of our second-order bandit algorithm to online convex optimization with memory.
arXiv Detail & Related papers (2024-02-14T04:03:38Z) - Online Learning Quantum States with the Logarithmic Loss via VB-FTRL [1.8856444568755568]
Online learning of quantum states with the logarithmic loss (LL-OLQS) is a classic open problem in online learning for over three decades.
In this paper, we generalize VB-FTRL for LL-OLQS with moderate computational complexity.
Each of the algorithm consists of a semidefinite program that can be implemented in time by, for example, cutting-plane methods.
arXiv Detail & Related papers (2023-11-06T15:45:33Z) - Damped Online Newton Step for Portfolio Selection [96.0297968061824]
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.
Existing algorithms that achieve a logarithmic regret for this problem have per-round time and space complexities that scale with the total number of rounds.
We 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.
arXiv Detail & Related papers (2022-02-15T17:01:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Entropic barriers as a reason for hardness in both classical and quantum
algorithms [2.062593640149623]
We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs.
By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers.
arXiv Detail & Related papers (2021-01-30T07:58:24Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions.
We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
arXiv Detail & Related papers (2020-10-23T09:12:47Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take.
We propose a novel approach based on Lagrangian Decomposition.
We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.