Linear relations between square-loss and Kolmogorov complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear relations between square-loss and Kolmogorov complexity

Full text

Pdf (886 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the twelfth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 226 - 232

Year of Publication: 1999

ISBN:1-58113-167-4

Author

Yuri Kalnishkan

Department of Computer Science, Royal Holloway University of London, Egham Surrey TW20 0EX, United Kingdom

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/307400.307443 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	CBFH+97	Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
	Cou48	R. Courant. Differential and Integral Calculus, volume 1. Blackie & Son, Ltd, London and Glasgo, 1948.
	HKW94	David Haussler , Jyrki Kivinen , Manfred Warmuth, TIGHT WORST-CASE LOSS BOUNDS FOR PREDICTING WITH EXPERT ADVICE, University of California at Santa Cruz, Santa Cruz, CA, 1994
	Hsi81	Chuan-Chin Hsiung. A First Course in Differential Geometry. John Wiley & Sons, Inc, 1981.
	LV97	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	LW94	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	VG99	V. Vovk and A. Gammerman. Complexity eValuation principle. Technical report, Royal Holloway, University of London, 1999.
	Vov90	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	Vov97	V. G. Vovk, Probability Theory for the Brier Game, Proceedings of the 8th International Conference on Algorithmic Learning Theory, p.323-338, October 06-08, 1997
	Vov98	V. Vovk, A game of prediction with expert advice, Journal of Computer and System Sciences, v.56 n.2, p.153-173, April 1998 [doi>10.1006/jcss.1997.1556]
	VW98	V. Vovk , C. Watkins, Universal portfolio selection, Proceedings of the eleventh annual conference on Computational learning theory, p.12-23, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279947]
	V’y94	V.V. V'yugin. Algorithmic entropy (complexity) of finite objects and its applications to defining randomness and amount of information. Selecta Mathematica formerly Sovietica, 13:357-389, 1994.
	ZL70	A.K. Zvonkin and L. A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Math. Surveys, 25:83-124, 1970.