Part of Advances in Neural Information Processing Systems 8 (NIPS 1995)
David Helmbold, Jyrki Kivinen, Manfred K. K. Warmuth
We analyze and compare the well-known Gradient Descent algo(cid:173) rithm and a new algorithm, called the Exponentiated Gradient algorithm, for training a single neuron with an arbitrary transfer function . Both algorithms are easily generalized to larger neural networks, and the generalization of Gradient Descent is the stan(cid:173) dard back-propagation algorithm. In this paper we prove worst(cid:173) case loss bounds for both algorithms in the single neuron case. Since local minima make it difficult to prove worst-case bounds for gradient-based algorithms, we must use a loss function that prevents the formation of spurious local minima. We define such a matching loss function for any strictly increasing differentiable transfer function and prove worst-case loss bound for any such transfer function and its corresponding matching loss. For exam(cid:173) ple, the matching loss for the identity function is the square loss and the matching loss for the logistic sigmoid is the entropic loss. The different structure of the bounds for the two algorithms indi(cid:173) cates that the new algorithm out-performs Gradient Descent when the inputs contain a large number of irrelevant components.
310
D. P. HELMBOLD, J. KIVINEN, M. K. WARMUTH