Provably Correct Automatic Subdifferentiation for Qualified Programs
The Cheap Gradient Principle [Griewank and Walther, 2008] -the computational cost of computing the gradient of a scalar-valued function is nearly the same (often within a factor of 5) as that of simply computing the function itself -is of central importance in optimization; it allows us to quickly obtain (high dimensional) gradients of scalar loss functions which are subsequently used in black box gradient-based optimization procedures. The current state of affairs is markedly different with regards to computing subderivatives: widely used ML libraries, including TensorFlow and PyTorch, do not correctly compute (generalized) subderivatives even on simple examples. This work considers the question: is there a Cheap Subgradient Principle? Our main result shows that, under certain restrictions on our library of nonsmooth functions (standard in nonlinear programming), provably correct generalized subderivatives can be computed at a computational cost that is within a (dimension-free) factor of 6 of the cost of computing the scalar function itself.
In this submission, the authors consider the problem of computing sub-differentiation for a class of non-smooth functions automatically and correctly. They give a very nice example that illustrates problems with current automated differentiation frameworks, such as tensorflow and pytorch. Then, the authors prove a chain rule for the one-sided directional derivative of a composite non-smooth function satisfying certain assumptions. Based on this rule, the authors derive a (randomized) algorithm for computing such a derivative for a particular kind of programs only with constant overhead. The algorithm is very similar to the one for back-ward automatic differentiation except that its forward computation is based on the newly-proved chain rule in the submission, rather than the standard chain rule for differentiation.  I vote for the acceptance of the submission. Although the message in the submission is unlikely to change the practice of machine-learning engineers, it will at least make them be aware of potential pitfalls arising from differentiating ReLU or other non-smooth functions using tensorflow and pytorch. In the past, I annoyed my colleagues multiple times with the question: why is it ok to differentiate a non-smooth function like ReLU as in tensorflow or pytorch? I got a wide range of answers, such as justification based on sub-differentiation and argument based on measure-zero non-differentiability, but all of them were slightly ad-hoc. This submission seems to give a principled answer and to expose a line of past research and new results on this question. I learned a lot by reading the paper. I feel that other participants in NIPS would experience the same.  * I think that it is better to give the definition of Clark sub-differential of f in the paper or in the appendix.  * Assumption 3.1: How flexible is this requirement?   * Don't Theorem 3.2 and Corollary 3.1 need Assumption 3.1?  * Why do you have to sample v1,...,vd in Algorithm 6 uniformly in the sphere? If not, what would go wrong?  * line 60: software is has ===> software has  * line 101: it computes ===> computes  * line 120: L is used here without definition. Say that it is a set of library functions.  * line 146: a function a function ===> a function  * line 181: allowed use ===> allowed to use  * formula right after line 187: -g(v) ===> -g(x)  * formula right after line 214: partial[f_2;v] ===> partial[f;v]  * line 218: algorithm, that ===> algorithm that  * I found it difficult to follow Example 3.3.