BPGrad: Towards Global Optimality in Deep Learning via Branch and Pruning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Object RecognitionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Training Deep Neural Networks via Branch-and-Bound
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 co…
Object RecognitionStochastic OptimizationEfficient Pruning LMI Conditions for Branch-and-Prune Rank and Chirality-Constrained Estimation of the Dual Absolute Quadric
We present a new globally optimal algorithm for self-calibrating a moving camera with constant parameters. Our method aims at estimating the Dual Absolute Quadric (DAQ) under the rank-3 and, optionally, camera centers ch…
A Complexity Efficient DMT-Optimal Tree Pruning Based Sphere Decoding
We present a diversity multiplexing tradeoff (DMT) optimal tree pruning sphere decoding algorithm which visits merely a single branch of the search tree of the sphere decoding (SD) algorithm, while maintaining the DMT op…
DiversityDecision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection
The branch-and-bound algorithm based on decision diagrams introduced by Bergman et al. in 2016 is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a ser…
Improving the filtering of Branch-And-Bound MDD solver (extended)
This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by …