Training Deep Neural Networks via Branch-and-Bound

Abstract

In this paper, we propose BPGrad, a novel approximate algorithm for deep nueral network training, based on adaptive estimates of feasible region via branch-and-bound. The method is based on the assumption of Lipschitz continuity in objective function, and as a result, it can adaptively determine the step size for the current gradient given the history of previous updates. We prove that, by repeating such a branch-and-pruning procedure, it can achieve the optimal solution within finite iterations. A computationally efficient solver based on BPGrad has been proposed to train the deep neural networks. Empirical results demonstrate that BPGrad solver works well in practice and compares favorably to other stochastic optimization methods in the tasks of object recognition, detection, and segmentation. The code is available at \url{https://github.com/RyanCV/BPGrad}.

arXiv comment29 pages, 17 figures. arXiv admin note: substantial text overlap with arXiv:1711.06959

References in corpus (19)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks
• ADADELTA: An Adaptive Learning Rate Method
• An overview of gradient descent optimization algorithms
• The Loss Surfaces of Multilayer Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Essentially No Barriers in Neural Network Energy Landscape
• The loss surface of deep and wide neural networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• ResNet with one-neuron hidden layers is a Universal Approximator
• Sharp Minima Can Generalize For Deep Nets
• Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
• Deep Feature Augmentation for Occluded Image Classification
• Adding One Neuron Can Eliminate All Bad Local Minima
• Topology and Geometry of Half-Rectified Network Optimization
• Deep Frank-Wolfe For Neural Network Optimization
• SGD Converges to Global Minimum in Deep Learning via Star-convex Path