Learning in a large committee machine: worst case and average case

Learning of realizable rules is studied for tree committee machines with continuous weights. No nontrivial upper bound exists for the generalization error of consistent students as the number of hidden units K increases. However, numerical considerations show that consistent students with a value of the generalization error significantly higher than predicted by the average-case analysis are extremely hard to find. An on-line learning algorithm is presented, for which the generalization error scales with the training set size as in the average-case theory in the limit of large K .