Tight Bounds for the VC-Dimension of Feedforward and Recurrent Networks of Piecewise Polynomial Activation Function Units

. We consider the VC-dimension of a set of the neural networks of depth s with w adjustable parameters that has h hidden units of activation functions of at most q segments of degree at most d polynomials. When d 2 and q 2, the VC-dimension is O(ws(s log d + log(qh=s))), O(ws((h=s) log q) + log d), and\Omega ws log(dqh=s)). When d 2 and q = 1, it is 2(ws log d). When d = 1 and q 2, it is 2(ws log(qh=s)). When d = 0 and q ? 2, it is O(ws log(qh=s)) and \Omega w log h). When d = 0 and q = 2, it is 2(w log h). The recurrent networks we consider is the feedforward network equiped with feedback connections with unit time delay. Let r be the number of repetitions along the feedbacks. Then the VC-dimension is O(wrs(log r + s log d + log(qh=s))), O(wrs((h=s) log q) + log rd), and\Omega wrs log(dqh=s)) for d 2 and q 2; 2(wrs log d) for d 2 and q = 1; 2(wrs log(qh=s)) for d = 1 and q 2; O(wrs log(qh=s)) and\Omega wr log h) for d = 0 and q ? 2. O(wr log(rh), O(wh) (for any r), ..