Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39553
Title: Improved bounds about on-line learning of smooth-functions of a single variable
Authors: Long, P.M. 
Issue Date: 2000
Source: Long, P.M. (2000). Improved bounds about on-line learning of smooth-functions of a single variable. Theoretical Computer Science 241 (1-2) : 25-35. ScholarBank@NUS Repository.
Abstract: We consider the complexity of learning classes of smooth functions formed by bounding different norms of a function's derivative. The learning model is the generalization of the mistake-bound model to continuous-valued functions. Suppose Fq is the set of all absolutely continuous functions f from [0,1] to R such that ∥f′∥q≤1, and opt(Fq,m) is the best possible bound on the worst-case sum of absolute prediction errors over sequences of m trials. We show that for all q≥2, opt(Fq,m) = Θ(√logm), and that opt(F2,m)≤(√log2 m)/2 + O(1), matching a known lower bound of (√log2 m)/2 - O(1) to within an additive constant. © 2000 Elsevier Science B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39553
ISSN: 03043975
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

44
checked on Dec 8, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.