Complexity of Learning in Neural Networks - Theory and Application

摘要

Randomnized algorithms are proposed and analyzed for learning binary weights fora neuron and links to the theory of random graphs are established. Optimal stopping phenomena in gradient descent learning algorithms are characterized and explained in terms of a time-varying effective machine complexity. The finite sample performance of the k-nearest neighbor algorithm for pattern recognition is rigorously characterized. Tradeoffs in learning from mixtures of labeled and unlabeled examples are determined.