BPGrad: Towards Global Optimality in Deep Learning via Branch and Pruning

Abstract

Understanding the global optimality in deep learning (DL) has been attracting more and more attention recently. Conventional DL solvers, however, have not been developed intentionally to seek for such global optimality. In this paper we propose a novel approximation algorithm, BPGrad, towards optimizing deep models globally via branch and pruning. Our BPGrad algorithm is based on the assumption of Lipschitz continuity in DL, and as a result it can adaptively determine the step size for current gradient given the history of previous updates, wherein theoretically no smaller steps can achieve the global optimality. We prove that, by repeating such branch-and-pruning procedure, we can locate the global optimality within finite iterations. Empirically an efficient solver based on BPGrad for DL is proposed as well, and it outperforms conventional DL solvers such as Adagrad, Adadelta, RMSProp, and Adam in the tasks of object recognition, detection, and segmentation.

References in corpus (17)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• Deep Residual Learning for Image Recognition
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Understanding deep learning requires rethinking generalization
• Fully Convolutional Networks for Semantic Segmentation
• The Loss Surfaces of Multilayer Networks
• MatConvNet - Convolutional Neural Networks for MATLAB
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Deep learning with Elastic Averaging SGD
• Global optimization of Lipschitz functions
• Global optimality conditions for deep neural networks
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
• Eve: A Gradient Based Optimization Method with Locally and Globally Adaptive Learning Rates