Don Kimber
ABSTRACT
We study the on-line learning of classes of functions of a single real variable formed through bounds on various norms of functions' derivatives. We determine the best bounds obtainable on the worst-case sum of squared errors (also “absolute” errors) for several such classes.
- Bar91.A. Barron. Approximation and estimation bounds for artificial neural networks. The 1991 Workshop on Computational Learning Theory, 1991. Google Scholar
Digital Library
- FM91.V. Faber and J. Mycielski. Applications of learning theorems. Fundamenia Informaticae, 15(2):145-167, 1991.Google Scholar
- Har91.W. Hardle. Smoothing Techniques. Springer Verlag, 1991.Google Scholar
- Hau89.D. Haussler. Generalizing the PAC model: sample size bounds from metric dimensionbased uniform convergence results. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989.Google ScholarDigital Library
- Lei81.G. Leitmann. The Calculus of Variations and Optimal Control. Plenum Press, 1981.Google ScholarCross Ref
- Lit89.N. Littlestone. Mistake Bounds and Logarithmic Linear-threshold Learning Algorithms. PhD thesis, UC Santa Cruz, 1989. Google ScholarDigital Library
- LLW91.N. Littlestone, P.M. Long, and M.K. Warmuth. On-line learning of linear functions. Proceedings of the ~3rd ACM Symposium on the Theory of Computation, pages 465-475, 1991. Google ScholarDigital Library
- LW89.N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989.Google ScholarDigital Library
- MT89.W. Maass and G. Turan. On the complexity of learning from counterexamples. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989.Google ScholarDigital Library
- Myc88.J. Mycielski. A learning algorithm for linear operators. Proceedings of the American Mathematical Society, 103(2):547-550, 1988.Google ScholarCross Ref
- WH60.B. Widrow and M.E. Hoff. Adaptive switching circuits. 1960 IRE WESCON Cony. Record, pages 96-104, 1960.Google ScholarCross Ref
Index Terms
- The learning complexity of smooth functions of a single variable
Recommendations
Online learning of smooth functions
AbstractIn this paper, we study the online learning of real-valued functions where the hidden function is known to have certain smoothness properties. Specifically, for q ≥ 1, let F q be the class of absolutely continuous functions f : [ 0 , 1 ] → R such ...
Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions
ITCS '16: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer ScienceA natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A ...
Comments