So last time I introduced the ideas behind CRPs. Now, why don’t they work in practice?
They solve the wrong problem. One of the ideas central to CRP is that they are a long term strategy — that over time they will achieve sublinear regret with the best fixed strategy. But over long periods of time, the best fixed strategy becomes more and more meaningless relative to an adaptive adversary that can change its portfolio. Consider, for instance, investing in tech stocks in the ’90s, then cashing out, then investing in financial or oil companies in the ’00s, and then cashing out. Just because of the way the market is, the best fixed strategy in hindsight becomes less and less meaningful over the same long time spans over which CRPs are supposed to excel. Of course, CRPs do not achieve sublinear regret against the best adaptive strategy in hindsight — but this is, in a larger sense, the correct problem to solve.
The bounds are meaningless. Let’s say we’ll use the Online Newton Step algorithm on the S&P 500, for a year. This algorithm achieves regret no larger than 5(1/a + GD)n log(T) where a, G, and D are pretty technical but take on values of about 1, T is the number of time steps (say 250 trading days in a year), and n is the dimension (here, 500). So, the bound is about 12,500. But this is an additive regret bound in log space. It seems reasonable to assume that even the best fixed CRP will not exceed a 55x return (which is e to the fourth power). Therefore, using this algorithm only proves that for each dollar you put into the algorithm, you will not end the period with fewer than exp(-12,496) dollars, which is close enough to zero to be zero. So just like in many other AI problems, the worst-case bound is meaningless here. Of course, this is not to say that such algorithms will work poorly in practice, but just to argue that there’s nothing magical about using one of these algorithms.
The convex model is fundamentally flawed. Convex optimization requires a convex domain, in this case taken to be the simplex. But in the real world, nobody will let you put 100% of your money into a single name. There is, perhaps, a 10 or 20% maximum, and that’s if you have particularly willing investors. While the domain you are optimizing over is still convex, the optimal CRP in hindsight over the simplex could do much better than the optimal CRP over your restricted domain.
They don’t take into account transaction costs. This is an issue that has been brought up before, notably by Blum and Kalai (warning, that link is a .ps.gz, ew). Essentially, introducing friction into your model slows down (and can even totally erase) your returns. Though this is the only issue that has been brought up in the literature, I think it’s actually the least important. As Cover alluded to in his article, by simply “caching” the moves you would have made and moving only when you have enough benefit to overcome transaction prices, you can accommodate these costs. Also, transaction costs just aren’t that significant anymore for hedge funds — my impression is that they would only slightly lower returns (say, in the 3-6% range).
There’s no way to get the prices you see in hindsight. In the model, the CRP sees the daily return and then moves into the next day losslessly. But in practice, you don’t know the final prices until the end of the day, at which point you’re supposed to have already moved into your new position! This complication could be solved by moving throughout the day, or at the next day’s open, or what have you. Regardless, it’s a significant hit to the model.
They don’t take into account market slippage. Even trading at the end of the day, in the auction, you’re likely to start moving prices if you put a lot of money into a single name. And of course, every time you move prices that hurts your return.
All of these factors combined conspired to kill Cover’s Mountain View Analytics. Still, I think the story is a wonderful illustration of the chasm between interesting, mathematically satisfying theory and nasty, brutish practice.
