A note on the richness of convex hulls of VC classes

We prove the existence of a class A of subsets of ℤ^d of vc dimension 1 such that the symmetric convex hull F of the class of characteristic functions of sets in A is rich in the following sense. For any absolutely continuous probability measure μ on ℤ^d, measurable set B ⊂ ℤ^d and ε > 0, there exists a function f ∈ F such that the measure of the symmetric difference of B and the set where f is positive is less than ε. The question was motivated by the investigation of the theoretical properties of certain algorithms in machine learning. Let A be a class of sets in ℝ^d and define the symmetric convex hull of A as the class of functions absconv(A) = (Σ_i=1^k a_i A_i(x): k > 0, a_i ∈ ℝ, Σ_i=1^k|a_i| = 1, A_i∈A) where A(x) denotes the indicator function of A. For every f ∈ absconv(A), define the set C_f = (x ∈ ℝ^d: f(x) > 0) and let C(A) = (C_f: f ∈ absconv(A)). We say that absconv(A) is rich with respect to the probability measure μ on ℝ^d if for every ε > 0 and measurable set B ⊂ ℝ^d there exists a C ∈ C(A) such that μ(BΔC) < ε where BΔC denotes the symmetric difference of B and C. Another way of measuring the richness of a class of sets (rather than the density of the class of sets) is the Vapnik-Chervonenkis (vc) dimension.