What type of functions can/cannot be handled by backprop? I have a very basic question about backprop, which is what type of function it can and cannot calculate the gradient of, and whether if anyone have examples of such functions.
I interpret backprop as basically the "black-box" algorithm that modern machine learning framework uses in order to compute the partial gradients with respect to learnable parameters in a system.
Obviously to calculate backprop, you have to be able to take the partial derivative of its variables, which means that the variables have to come from a continuous space. Ok, so "continuously differentiable functions over continuous (say, convex) spaces". Hence any network that is composed of add, multiply and continuous activation functions can be handled by backprop.
But it seems that the backprop algos implemented by many frameworks does more. For example, a network containing Relu is not differentiable in the ordinary sense. It is subdifferentiable. So our class of functions that can be handled by backprop extends to "subdifferentiable functions over continuous spaces", or maybe "Lipschitz continuous functions over continuous spaces".
Is this the largest class of function we can use the backprop algo on? What about discontinuous functions? What are the limits of backpropagation?
 A: Depends on what you mean by "handled". If you mean "provably converges to a local/global minimum", then yes, you may need your function to have a gradient or subgradient. If you mean "we can train a neural network which does useful and interesting things", then it turns out all you need is a reasonable estimate or heuristic that allows the "error signal" to keep flowing through the computation graph. Some common examples:

*

*To backpropagate through $y =\text{sign}(x)$ (returns -1,0,1 depending on the sign of $x$), use $x$ as the gradient.


*To backpropagate through the sampling operation $y \sim \text{Bernoulli}(x)$, use $x$ as the gradient.


*To backpropagate through $y \sim \text{Categorical}(x)$, use the gumbel-softmax trick.


*To backpropagate through $E_{z \sim p(z;\theta)}[f(z)]$ for some arbitrary $f$, use $E_{z\sim p}[f(z) \nabla_\theta \log p(z;\theta)]$
The authors of RELAX write:

Unfortunately, there are many objective functions relevant to the machine learning community for
which backpropagation cannot be applied. In reinforcement learning, for example, the function being optimized
is unknown to the agent and is treated as a black box (Schulman et
al., 2015a). Similarly, when fitting probabilistic models with
discrete latent variables, discrete sampling operations create
discontinuities giving the objective function zero gradient with
respect to its parameters. Much recent work has been devoted to
constructing gradient estimators for these situations. In
reinforcement learning, advantage actor-critic methods (Sutton et al.,
2000) give unbiased gradient estimates with reduced variance obtained
by jointly optimizing the policy parameters with an estimate of the
value function. In discrete latent-variable models, low-variance but
biased gradient estimates can be given by continuous relaxations of
discrete variables (Maddison et al., 2016; Jang et al., 2016).

You may also be interested in REBAR, MuProp, gumbel-sinkhorn, straight-through estimators.
