Efficient Online Portfolio with Logarithmic Regret
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(N ln 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(N 2 (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(T N 2.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.
This paper introduces a new algorithm (BARRONS) for the online portfolio optimization problem. This algorithm obtains logarithmic regret in time quadratic in the number of rounds without any potentially catastrophic dependence on a gradient norm. This is in contrast to the Cover's universal portfolio algorithm, online newton step, and exponentiated gradient, which each achieve at most two of these three goals.  The algorithm itself is an application of the online mirror descent framework, using the less-classical log-barrier regularizer. The paper provides good intuition for how the algorithm is able to avoid dependence on the gradient norm: the gradient norm is only big if a previously poorly-performing stock starts to perform well. As a result the learner has a kind of "surplus" of regret that it can fall back on while adapting to the new stock.  The algorithm still leaves something to be desired: the total running time T^2N^(2.5) where N is the number of stocks (the dimension of the problem) and T is the number of rounds. Both of these dependencies are rather poor (although much better than the universal portfolio algorithm). Also the regret is N^2log^4(T), rather than the ideal N\log(T).   The authors suggest that the T^2 aspect of the runtime might be improved by using more intelligent optimization algorithms in a subroutine of the main algorithm. This may not bear out, but it suggests that there are at least some obvious points of attack for improving the results.  In a pleasant surprise for a theory paper, Most of a complete proof of the regret bound fits into the main text of the paper.  Quality: This is reasonably clean approach to an old problem that achieves non-trivial new bounds. Overall this seemed a good-quality paper.   Clarity: The background and the contrast between prior approaches was well-explained.  Originality: The main original ideas in this paper seems to be the application of the log-barrier potential to this particular problem, and the intuition used to remove the gradient-norm dependence in the regret. I'm not aware of similar results on the problem.  Significance: The main improvement of this paper is to remove the dependence on the gradient norm in the portfolio optimization problem. Both the regret bound and time complexity have some distressing high exponents, so there is still significantly more work to be done. However, the removal of the gradient norm from the bound is important as it gets rid of a kind of "wishful thinking" aspect of other bounds, and it is significantly faster than the only other algorithm to obtain this (universal portfolio, which is abysmally slow), so I think this paper represents a nice step of progress.