  It has been attracting more and more attention to understand the global
optimality in deep learning (DL) recently. However, conventional DL solvers,
have not been developed intentionally to seek for such global optimality. In
this paper, we propose a novel approximation algorithm, {\em BPGrad}, towards
optimizing deep models globally via branch and pruning. The proposed BPGrad
algorithm is based on the assumption of Lipschitz continuity in DL, and as a
result, it can adaptively determine the step size for the current gradient
given the history of previous updates, wherein theoretically no smaller steps
can achieve the global optimality. We prove that, by repeating such a
branch-and-pruning procedure, we can locate the global optimality within finite
iterations. Empirically an efficient adaptive 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. The code is available at \url{https://github.com/RyanCV/BPGrad}.
