  This paper discovers that the neural network with lower decision boundary
(DB) variability has better generalizability. Two new notions, algorithm DB
variability and $(\epsilon, \eta)$-data DB variability, are proposed to measure
the decision boundary variability from the algorithm and data perspectives.
Extensive experiments show significant negative correlations between the
decision boundary variability and the generalizability. From the theoretical
view, two lower bounds based on algorithm DB variability are proposed and do
not explicitly depend on the sample size. We also prove an upper bound of order
$\mathcal{O}\left(\frac{1}{\sqrt{m}}+\epsilon+\eta\log\frac{1}{\eta}\right)$
based on data DB variability. The bound is convenient to estimate without the
requirement of labels, and does not explicitly depend on the network size which
is usually prohibitively large in deep learning.
