Complexity of pattern classes and the Lipschitz property

• Published in: Theoretical computer science 2007-09, Vol.382 (3), p.232-246
• Main Authors: Ambroladze, Amiran, Parrado-Hernández, Emilio, Shawe-Taylor, John
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Artificial intelligence; Computer science; control theory; systems; Empirical complexity; Exact sciences and technology; Learning and adaptive systems; Lipschitz functions; Miscellaneous; Rademacher complexity; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2007.03.047

Rademacher and Gaussian complexities are successfully used in learning theory for measuring the capacity of the class of functions to be learnt. 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 case for the other properties) and it is believed that the proof in the Gaussian case is conceptually more difficult than the one for the Rademacher case. In this paper we give a detailed proof of the Lipschitz property for the general case of a symmetric complexity measure that includes the Rademacher and Gaussian complexities as special cases. We also consider the Rademacher complexity of a function class consisting of all the Lipschitz functions with a given Lipschitz constant. We show that the complexity of the class is surprisingly low in the one-dimensional case. Finally, we introduce a relaxation of the definition of Rademacher complexity to Rademacher Free Complexity and show that not only can this complexity replace the standard definition in the key theorem, but also the bounds for composed function classes are tighter.