Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations

摘要

We provide upper bounds for the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers whose membership tests are programs described by bounded-depth arithmetic networks. Our upper bounds are of the kind O(k 2 d 2), where d is the depth of the network (representing the parallel running time) and k is the number of parameters needed to codify the concept. This bound becomes O(k 2 d) when membership tests are described by Boolean-arithmetic circuits. As a consequence we conclude that families of concepts classes having parallel polynomial time algorithms expressing their membership tests have polynomial VC dimension.