A computational study on circuit size versus circuit depth

[Please see the article via the link above for the full abstract including mathematical formulae]. We investigate the circuit complexity of classification problems in a machine learning setting, i.e. we attempt to find some rule that allows us to calculate a priori the number of threshold gates that is sufficient to achieve a small error rate after training a circuit on sample data. The particular threshold gates are computed by a combination of the classical perceptron algorithm with a specific type of stochastic local search. The circuit complexity is analysed for depth-two and depth-four threshold circuits, where we introduce a novel approach to compute depth-four circuits. For the problems from the UCI Machine Learning Repository we selected and investigated, we obtain approximately the same size of depth-two and depth-four circuits for the best classification rates on test samples, where the rates differ only marginally for the two types of circuits.