Using the notion of conservative gradient, we provide a simple model to
estimate the computational costs of the backward and forward modes of
algorithmic differentiation for a wide class of nonsmooth programs. The
overhead complexity of the backward mode turns out to be independent of the
dimension when using programs with locally Lipschitz semi-algebraic or
definable elementary functions. This considerably extends Baur-Strassen's
smooth cheap gradient principle. We illustrate our results by establishing fast
backpropagation results of conservative gradients through feedforward neural
networks with standard activation and loss functions. Nonsmooth
backpropagation's cheapness contrasts with concurrent forward approaches, which
have, to this day, dimensional-dependent worst-case overhead estimates. We
provide further results suggesting the superiority of backward propagation of
conservative gradients. Indeed, we relate the complexity of computing a large
number of directional derivatives to that of matrix multiplication, and we show
that finding two subgradients in the Clarke subdifferential of a function is an
NP-hard problem.

本文提出了一种用保守梯度模型来估计算法分化的计算成本的方法，并且较为详细地描述了其在反向传播和前向传播中的应用。主要方法是基于局部 Lipschitz 半代数或可定义基本函数的方法，可以极大地加速了反向传播过程。