UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Proceedings paper #79149

Ambroladze, A; Shawe-Taylor, J; (2004) UNSPECIFIED In: (Proceedings) Complexity of pattern classes and Lipschitz property.

Full text not available from this repository.

Abstract

Rademacher and Gaussian complexities are successfully used in learning theory for measuring the capacity of the class of functions to be learned. One of the most important properties for these complexities is their Lipschitz property: a composition of a class of functions with a fixed Lipschitz function may increase its complexity by at most twice the Lipschitz constant. The proof of this property is non-trivial (in contrast to the other properties) and it is believed that the proof in the Gaussian case is conceptually more difficult then the one for the Rademacher case. In this paper we give a detailed prove of the Lipschitz property for the Rademacher case and generalize the same idea to an arbitrary complexity (including the Gaussian). We also discuss a related topic about the Rademacher complexity of a class consisting of all the Lipschitz functions with a given Lipschitz constant. We show that the complexity is surprisingly low in the one-dimensional case. The question for higher dimensions remains open

Type:Proceedings paper
Event:Complexity of pattern classes and Lipschitz property
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record