Please use this identifier to cite or link to this item:
|Title:||Improved bounds about on-line learning of smooth-functions of a single variable||Authors:||Long, P.M.||Issue Date:||2000||Citation:||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.
checked on Sep 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.