  Lipschitz constants are connected to many properties of neural networks, such
as robustness, fairness, and generalization. Existing methods for computing
Lipschitz constants either produce relatively loose upper bounds or are limited
to small networks. In this paper, we develop an efficient framework for
computing the $\ell_\infty$ local Lipschitz constant of a neural network by
tightly upper bounding the norm of Clarke Jacobian via linear bound
propagation. We formulate the computation of local Lipschitz constants with a
linear bound propagation process on a high-order backward graph induced by the
chain rule of Clarke Jacobian. To enable linear bound propagation, we derive
tight linear relaxations for specific nonlinearities in Clarke Jacobian. This
formulate unifies existing ad-hoc approaches such as RecurJac, which can be
seen as a special case of ours with weaker relaxations. The bound propagation
framework also allows us to easily borrow the popular Branch-and-Bound (BaB)
approach from neural network verification to further tighten Lipschitz
constants. Experiments show that on tiny models, our method produces comparable
bounds compared to exact methods that cannot scale to slightly larger models;
on larger models, our method efficiently produces tighter results than existing
relaxed or naive methods, and our method scales to much larger practical models
that previous works could not handle. We also demonstrate an application on
provable monotonicity analysis. Code is available at
https://github.com/shizhouxing/Local-Lipschitz-Constants.
