Approaches for classifying training samples with minimal error in a neural network using a low complexity neural network classifier, are described. In one example, for the neural network, an upper bound on the Vapnik-Chervonenkis (VC) dimension is determined. Thereafter, an empirical error function corresponding to the neural network is determined. A modified error function based on the upper bound on the VC dimension and the empirical error function is generated, and used for training the neural network.