×

On universal algorithms for adaptive forecasting. (English. Russian original) Zbl 1234.62124

Probl. Inf. Transm. 47, No. 2, 166-189 (2011); translation from Probl. Peredachi Inf. 47, No. 2, 90-116 (2011).
Summary: In the last decade, new methods of forecasting were developed different from traditional statistical methods. In particular, it is possible to “efficiently” predict any sequence of outcomes without using any hypothesis on the nature of a source generating it. In the present paper, a modified version of the universal forecasting algorithm is considered. The main part of the paper is devoted to algorithmic analysis of universal forecasting methods and to exploring limits of their performance.

MSC:

62M20 Inference from stochastic processes and prediction
65C60 Computational problems in statistics (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V’yugin V.V. On Sequences with Non-learnable Subsequences, Computer Science-Theory and Applications (Proc. 3rd Int. Computer Science Sympos. in Russia [CSR’2008], Moscow, Russia, 2008), Hirsh, E., Razborov, A., Semenov, A., and Slissenko, A., Eds., Lect. Notes Comp. Sci., vol. 5010, Berlin: Springer, 2008, pp. 302–313. · Zbl 1142.68410
[2] Dawid, A.P., TheWell-Calibrated Bayesian, J. Amer. Statist. Assoc., 1982, vol. 77, no. 379, pp. 605–613. · Zbl 0495.62005 · doi:10.1080/01621459.1982.10477856
[3] Foster, D.P. and Vohra, R.V., Asymptotic Calibration, Biometrika, 1998, vol. 85, no. 2, pp. 379–390. · Zbl 0947.62059 · doi:10.1093/biomet/85.2.379
[4] Sandroni, A., The Reproducible Properties of Correct Forecasts, Int. J. Game Theory, 2003, vol. 32, no. 1, pp. 151–159. · Zbl 1071.62084 · doi:10.1007/s001820300153
[5] Dekel, E. and Feinberg, Y., Non-Bayesian Testing of a Stochastic Prediction, Rev. Econom. Stud., 2006, vol. 73, no. 4, pp. 893–906. · Zbl 1104.62103 · doi:10.1111/j.1467-937X.2006.00401.x
[6] Fortnow, L. and Vohra, R.V., The Complexity of Forecast Testing, Econometrica, 2009, vol. 77, no. 1, pp. 93–105. · Zbl 1160.91396 · doi:10.3982/ECTA7163
[7] Dawid, A.P., Calibration-Based Empirical Probability, Ann. Statist., 1985, vol. 13,no. 4, pp. 1251–1285. · Zbl 0587.60002 · doi:10.1214/aos/1176349736
[8] Uspensky, V.A., Semenov, A.L., and Shen’, A.Kh., Can an Individual Sequence of Zeros and Ones Be Random?, Uspekhi Mat. Nauk, 1990, vol. 45, no. 1, pp. 105–162 [Russian Math. Surveys (Engl. Transl.), 1990, vol. 45, no. 1, pp. 121–189].
[9] Li, M. and Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications, New York: Springer, 1997, 2nd ed. · Zbl 0866.68051
[10] Oakes, D., Self-Calibrating Priors Do Not Exist, J. Amer. Statist. Assoc., 1985, vol. 80, no. 390, pp. 339–342. · Zbl 0576.62006 · doi:10.1080/01621459.1985.10478117
[11] Sandroni, A., Smorodinsky, R., and Vohra, R.V., Calibration with Many Checking Rules, Math. Oper. Res., 2003, vol. 28, no. 1, pp. 141–153. · Zbl 1082.90544 · doi:10.1287/moor.28.1.141.14264
[12] Shiryaev, A.N., Veroyatnost’, Moscow: Nauka, 1980. Translated under the title Probability, New York: Springer, 1984.
[13] Kakade, S. and Foster, D.P., Deterministic Calibration and Nash Equilibrium, Proc. 17th Ann. Conf. on Learning Theory (COLT’2004), Banff, Canada, 2004, Shawe-Taylor, J. and Singer, Y., Eds., Lect. Notes Comp. Sci., vol. 3120, Berlin: Springer, 2004, pp. 33–48. · Zbl 1078.91004
[14] Lehrer, E., Any Inspection Rule Is Manipulable, Econometrica, 2001, vol. 69, no. 5, pp. 1333–1347. · Zbl 1020.91046 · doi:10.1111/1468-0262.00244
[15] Rogers, H., Theory of Recursive Functions and Effective Computability, New York: McGraw-Hill, 1967. Translated under the title Teoriya rekursivnykh funktsii i effektivnaya vychislimost’, Moscow: Mir, 1972.
[16] Zvonkin, A.K. and Levin, L.A., Complexity of Finite Objects and the Algorithmic Concepts of Information and Randomness, Uspekhi Mat. Nauk, 1970, vol. 25, no. 6, pp. 85–127 [Russian Math. Surveys (Engl. Transl.), 1970, vol. 25, no. 6, pp. 83–124].
[17] V’yugin, V.V., Non-Stochastic Infinite and Finite Sequences, Theoret. Comput. Sci., 1998, vol. 207, no. 2, pp. 363–382. · Zbl 0915.68079 · doi:10.1016/S0304-3975(98)00073-5
[18] Vovk, V., Defensive Forecasting for Optimal Prediction with Expert Advice, arXiv e-print 0708.1503v1, 2007.
[19] Cesa-Bianchi, N. and Lugosi, G., Prediction, Learning, and Games, Cambridge: Cambridge Univ. Press, 2006. · Zbl 1114.91001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.