Algorithms for portfolio management based on the Newton method

ABSTRACT

We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio determined in hindsight. These algorithms are the first to combine optimal logarithmic regret bounds with efficient deterministic computability. They are based on the Newton method for offline optimization which, unlike previous approaches, exploits second order information. After analyzing the algorithm using the potential function introduced by Agarwal and Hazan, we present extensive experiments on actual financial data. These experiments confirm the theoretical advantage of our algorithms, which yield higher returns and run considerably faster than previous algorithms with optimal regret. Additionally, we perform financial analysis using mean-variance calculations and the Sharpe ratio.

REFERENCES

• 1: Agarwal, A., & Hazan, E. (2005). New algorithms for repeated play and universal portfolio management. Princeton University Technical Report TR-740-05.
• 2: Algoet, P., & Cover, T. (1988). Asymptotic optimality and asymptotic equipartition properties of log-optimum investment. Annals of Probability, 2, 876--898.
• 3: Bell, R., & Cover, T. (1980). Competitive optimality of logarithmic investment. Mathematics of Operations Research, 2, 161--166.
• 4: Robert Bell , Thomas M. Cover, Game-theoretic optimal portfolios, Management Science, v.34 n.6, p.724-733, June 1988
• 5: Avrim Blum , Adam Kalai, Universal Portfolios With and Without Transaction Costs, Machine Learning, v.35 n.3, p.193-205, June 1999 [doi>10.1023/A:1007530728748 ]
• 6: Borodin, A., El-Yaniv, R., & Gogan, V. (2004). Can we learn to beat the best stock. Journal of Artificial Intelligence Research, 21, 579--594.
• 7: Brookes, M. (2005). The matrix reference manual. {online} www.ee.ic.ac.uk/hp/staff/dmb/matrix/intro.html.
• 8: Cover, T. (1991). Universal portfolios. Mathematical Finance, 1, 1--19.
• 9: Hannan, J. (1957). Approximation to bayes risk in repeated play. In M. Dresher, A. W. Tucker and P. Wolfe, editors, Contributions to the Theory of Games, III, 97--139.
• 10: Hazan, E., Kalai, A., Kale, S., & Agarwal, A. (2006). Logarithmic regret algorithms for online convex optimization. To appear in the 19th Annual Conference on Learning Theory (COLT).
• 11: Helmbold, D., Schapire, R., Singer, Y., & Warmuth., M. (1998). On-line portfolio selection using multiplicative updates. Mathematical Finance, 8, 325--347.
• 12: Adam Kalai , Santosh Vempala, Efficient algorithms for universal portfolios, The Journal of Machine Learning Research, 3, 3/1/2003
• 13: Adam Kalai , Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, v.71 n.3, p.291-307, October 2005 [doi>10.1016/j.jcss.2004.10.016]
• 14: Kelly, J. (1956). A new interpretation of information rate. Bell Systems Technical Journal, 917--926.
• 15: David Carl Larson, Growth optimal investment strategies, Stanford University, Stanford, CA, 1986
• 16: Lovász, L., & Vempala, S. (2003a). The geometry of logconcave functions and an O*(n3) sampling algorithm (Technical Report MSR-TR-2003-04). Microsoft Research.
• 17: László Lovász , Santosh Vempala, Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.650, October 11-14, 2003
• 18: Luenberger, D. G. (1998). Investment science. Oxford: Oxford University Press.
• 19: Neri Merhav , Meir Feder, Universal sequential learning and decision from individual data sequences, Proceedings of the fifth annual workshop on Computational learning theory, p.413-427, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130430]
• 20: Erik Ordentlich , Thomas M. Cover, On-line portfolio selection, Proceedings of the ninth annual conference on Computational learning theory, p.310-313, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238161]
• 21: Gilles Stoltz , Gábor Lugosi, Internal Regret in On-Line Portfolio Selection, Machine Learning, v.59 n.1-2, p.125-159, May 2005 [doi>10.1007/s10994-005-0465-4]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms