Wednesday, July 02, 2014

Another "universal" capital allocation algorithm

Financial engineers are accustomed to borrowing techniques from scientists in other fields (e.g. genetic algorithms), but rarely does the borrowing go the other way. It is therefore surprising to hear about this paper on a possible mechanism for evolution due to natural selection which is inspired by universal capital allocation algorithms.

A capital allocation algorithm attempts to optimize the allocation of capital to stocks in a portfolio. An allocation algorithm is called universal if it results in a net worth that is "similar" to that generated by the best constant-rebalanced portfolio with fixed weightings over time (denoted CBAL* below), chosen in hindsight. "Similar" here means that the net worth does not diverge exponentially. (For a precise definition, see this very readable paper by Borodin, et al. H/t: Vladimir P.)

Previously, I know only of one such universal trading algorithm - the Universal Portfolio invented by Thomas Cover, which I have described before. But here is another one that has proven to be universal: the exceedingly simple EG algorithm.

The EG ("Exponentiated Gradient") algorithm is an example of a capital allocation rule using "multiplicative updates": the new capital allocated to a stock is proportional to its current capital multiplied by a factor. This factor is an exponential function of the return of the stock in the last period. This algorithm is both greedy and conservative: greedy because it always allocates more capital to the stock that did well most recently; conservative because there is a penalty for changing the allocation too drastically from one period to the next. This multiplicative update rule is the one proposed as a model for evolution by natural selection.

The computational advantage of EG over the Universal Portfolio is obvious: the latter requires a weighted average over all possible allocations at every step, while the former needs only know the allocation and returns for the most recent period. But does this EG algorithm actually generate good returns in practice? I tested it two ways:

1) Allocate between cash (with 2% per annum interest) and SPY.
2) Allocate among SP500 stocks.

In both cases, the only free parameter of the model is a number called the "learning rate" η, which determines how fast the allocation can change from one period to the next. It is generally found that η=0.01 is optimal, which we adopted. Also, we disallow short positions in this study.

The benchmarks for comparison for 1) are, using the notations of the Borodin paper,

a)  the buy-and-hold SPY portfolio BAH, and
b) the best constant-rebalanced portfolio with fixed allocations in hindsight CBAL*.

The benchmarks for comparison for 2)  are

a) a constant rebalanced portfolio of SP500 stocks with equal allocations U-CBAL,
b) a portfolio with 100% allocation to the best stock chosen in hindsight BEST1, and
c) CBAL*.

To find CBAL* for a SP500 portfolio, I used Matlab Optimization Toolbox's constrained optimization function fmincon.

There is also the issue of SP500 index reconstitution. It is complicated to handle the addition and deletion of stocks in the index within a constrained optimization function. So I opted for the shortcut of using a subset of stocks that were in SP500 from 2007 to 2013, tolerating the presence of surivorship bias. There are only 346 such stocks.

The result for 1) (cash vs SPY) is that the CAGR (compound annualized growth rate) of EG is slightly lower than BAH (4% vs 5%). It turns out that BAH and CBAL* are the same: it was best to allocate 100% to SPY during 2007-2013, an unsurprising recommendation in hindsight.

The result for 2) is that the CAGR of EG is higher than the equal-weight portfolio (0.5% vs 0.2%). But both these numbers are much lower than that of BEST1 (39.58%), which is almost the same as that of CBAL* (39.92%). (Can you guess which stock in the current SP500 generated the highest CAGR? The answer, to be revealed below*, will surprise you!)

We were promised that the EG algorithm will perform "similarly" to CBAL*, so why does it underperform so miserably? Remember that similarity here just means that the divergence is sub-exponential: but even a polynomial divergence can in practice be substantial! This seems to be a universal problem with universal algorithms of asset allocation: I have never found any that actually achieves significant returns in the short span of a few years. Maybe we will find more interesting results with higher frequency data.

So given the underwhelming performance of EG, why am I writing about this algorithm, aside from its interesting connection with biological evolution? That's because it serves as a setup for another, non-universal, portfolio allocation scheme, as well as a way to optimize parameters for trading strategies in general: both topics for another time

===
Workshops Update:

My next online workshop will be on  Mean Reversion Strategies, August 26-28. This and the Quantitative Momentum workshops will also be conducted live at Nanyang Technological University in Singapore, September 18-21.

===
Do follow me @chanep on Twitter, as I often post links to interesting articles there.

===
*The SP500 stock that generated the highest return from 2007-2013 is AMZN.

29 comments:

ezbentley said...

Just FYI, there has been a lot of other universal algorithms: http://arxiv.org/pdf/1212.2129v2.pdf

Ernie Chan said...

Good to know, ezbentley! Thanks for the link.
Ernie

Theo said...

Thanks for sharing that Ernie. 1 quick question:
if you target a volatility level in your portfolio and you rebalance your portfolio positions to keep the overall vol constant, aren't you following a similar process to Universal Portfolios? Of course the weights by targeting vol can be sub-optimal compared to Universal weights. My point is that a portfolio that targets a vol. level (usually the case in futures) can be one possible solution of the Universal portfolios but probably sub-optimal.

Ernie Chan said...

Hi Theo,
Rebalancing to keep the volatility constant may accidentally be similar to a constant rebalanced portfolio with fixed weights, but is unlikely to be universal in general. It will be sub-optimal in the long run, but then even universal portfolios take many years to outpace other allocation methods!
Ernie

Unknown said...

Thanks for the link ezbently, bookmarked it.
You guys may also want to see through my blog @ http://www.johnsdaytrades.com

CHeers!

Anonymous said...

Hi Ernie,

If I have an intraday pairs strategy but each pair may not have trades every day, I wonder how I can allocate buying powers to each trade.

Ernie Chan said...

Since you cannot predict each day which pair you will enter into, you have to pre-allocate capital to all the pairs, even if most of them do not have positions. Or you can find out in backtest the maximum number of positions and allocate according to that.

Ernie

Anonymous said...

Hi Ernie,

Thank you for quick response.

Since some of intraday pairs do not have positions, I may not use all buying power each day.

Is it better to use all buying power each day? (so we monitor more pairs)

Ernie Chan said...

There is no requirement that one should use all buying power each day. Of course, one should optimize leverage and capital allocation so that as much buying power is used as possible.

Ernie

Anonymous said...

Hi Ernie,

Shall we stop trading the stock on its dividend ex-date for one day?

Thanks.

Ernie Chan said...

Why would you want to do that?
Ernie

Anonymous said...

Hi Ernie,

because we need to do dividend adjustment for data. Otherwise we may get false buy/sell signals.
Or we can do it the day before ex-date since we have the information already.

Ernie Chan said...

Yes, you can do the adjustment on the ex-date, before you place your trades.

Ernie

Anonymous said...

Hi Ernie,

Recently, there are some earnings
announcement in energy sector.

Shall we avoid trading energy stocks
pairs during this period?

Btw, where could we find earnings
announcement dates in advance on internet?

Thanks.

Ernie Chan said...

Generally speaking, we would want to avoid earnings (or other events) when running a mean reversal strategy. But of course, you need to backtest your strategy to find out if that is ncessary.

E.g. http://biz.yahoo.com/research/earncal/20140807.html gives tomorrow's earnings calendar.

Ernie

Anonymous said...

Hi Ernie,

Have you heard about laser trading platform and its api?

Where can we learn to use it?

Thanks.

Ernie Chan said...

I think Laser is the platform for Genesis Securities. I have not used it myself, but a Google search reveals numerous references to its features and documentation.

Ernie

Anonymous said...

Hi Ernie,

What is ECNs for US stocks, such as BATS?

What is the difference between ECNs and NYSE exchange?

It seems some prop trading firms use laser platform to connect with ECNs.

What is the advantage?

Thanks.

Ernie Chan said...

To a trader, there is no difference between an exchange and an ECN. (Here is a good reference: http://www.slate.com/articles/news_and_politics/explainer/2005/04/markets_vs_exchanges.html concerning the difference in other aspects irrelevant to us.)

Most brokerages (e.g. Interactive Brokers) catering to professional retail traders allow direct routing to ECNs. You would only want to route there if you think they have lower fees for your particular order type, or if you are a HFT who knows how to exploit the special order types or fee structure on that ECN.

Ernie

Anonymous said...

Hi Ernie,

What are you favourite sources (blogs, forums etc) for following marketplace and generating strategy ideas?

There is quite an information overflow in this space do you have any tips how to deal with this?

Many thanks

Ernie Chan said...

My favorite blog is thewholestreet.com, because it is a consolidator which links to many other very useful blogs such as www.jonathankinlay.com

Also, nowadays I find Twitter the best source to investment ideas and articles. E.g. @quantivity @alphaarchitect and of course yours truly's @chanep

Ernie

Unknown said...

Hi Ernie,

Do you have backtest pair trading sample in excel, instead of matlab? I read your first book and the example 3.6 is only in matlab.

Thanks so much

Ernie Chan said...

Hi Sonny,
I am afraid I don't have Excel version of that program. By the way, Matlab is selling for only $150: it is well-worth it.
Ernie

Unknown said...

Thanks Ernie. Ok I will get Matlab.

I have a quick question about spread. I did plot the spread stock1 - hedgeratio*stock2
Calculated the mean and std about a year worth of daily data. (GLD and GDX)
I plot the spread from the last 2 years. I can see about a year ago, The spread spent most time way below negative area and keep climbing up.

http://screencast.com/t/KuHu58W8xsW

The older data is at the right (sorry, i didn't reverse sort it)

Does this mean this pair was not cointegrated during that 'trending' time?

Do we have to run linear regression with high R2 so that we can trade this?
I am just guessing... What's the right method?

Thanks!

Ernie Chan said...

Hi Sonny,
Yes, the trending period is not stationary. This pair's cointegration broke down from time to time. For e.g. see my explanation of the breakdown in early 2008 on page 61 of Algorithmic Trading.

This is no general way to trade a pair with broken cointegration: you would have to know the fundamental reason for the breakdown as noted on p. 61. If you know the fundamental reason, you can often add an additional instrument to the portfolio to restore cointegration.

Ernie

Anonymous said...

Hi Erine

Have you ever implemented the pairs trading algorithm with structure break feature? How you rate it?

Ernie Chan said...

No, I haven't.
Ernie

James said...

Hi Ernie

I know it's a relatively old post now, but thanks for a great write-up. I find universal portfolio schemes fascinating, despite their apparent lack of profitability under real-world conditions.

I'm writing to ask what the non-universal portfolio allocation scheme is that you allude to at the end of your post, and how it might be applied to both portfolio selection and parameter optimisation?

Ernie Chan said...

Hi James,
Thanks for your kind words.

I think I was referring to my next post on Kelly vs Markowitz portfolio optimization: http://epchan.blogspot.com/2014/08/kelly-vs-markowitz-portfolio.html

By the way, there was a keynote address on such universal portfolio allocation schemes by Dr. Michael Kearns at Quantcon.com: ""Trading without Regret" Very interesting talk.

Ernie