The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension

✍ Scribed by Vitaly Maiorov; Joel Ratsaby

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 872 KB
• Volume: 86
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00015-8

✦ Synopsis

The degree of approximation of infinite-dimensional function classes using finite n-dimensional manifolds has been the subject of a classical field of study in the area of mathematical approximation theory. In Ratsaby and Maiorov (1997), a new quantity p,(F, L,) which measures the degree of approximation of a function class F by the best manifold H" of pseudo-dimension less than or equal to n in the &-metric has been introduced. For sets F C KY" it is defined as pH(F, 1,") = infHn dist(F, H"), where dist(F, H") = supXEF inf,tHn Ilx-_vll,; and H" C iw" is any set of VC-dimension less than or equal to n where n cm. It measures the degree of approximation of the set F by the optimal set H" C R" of VC-dimension less than or equal to n in the /r-metric. In this paper we compute p, (F, 1,") for F being the unit ball BT = {x E W' : Ilxl(l; < 1) for any I< p, q <co, and for F being any subset of the boolean m-cube of size larger than 2":', for any i <y < 1.