Deep neural networks have gained tremendous popularity in last few years.They have been applied for the task of classification in almost every domain.Despite the success, deep networks can be incredibly slow to train for evenmoderate sized models on sufficiently large datasets. Additionally, thesenetworks require large amounts of data to be able to generalize. The importanceof speeding up convergence, and generalization in deep networks can not beoverstated. In this work, we develop an optimization algorithm based ongeneralized-optimal updates derived from minibatches that lead to fasterconvergence. Towards the end, we demonstrate on two benchmark datasets that theproposed method achieves two orders of magnitude speed up over traditionalback-propagation, and is more robust to noise/over-fitting.