Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one of Lutz and Mayordomo's "Twelve Problems in Resource-Bounded Measure" (1999).

Keywords

Computational Complexity, Machine Learning

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/105728

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0512053
 http://arxiv.org/abs/cs/0512053

Collections

arXiv