What types of functions can be implemented in a layer of a Neural Networks? One of the most common algorithms for training Neural Networks is back propagation, which essentially does (stochastic) gradient descent on the training objective function. Gradient descent can be used to optimize any objective function, as long as we can evaluate the function and compute its (sub-)gradient at any given point in the solution space.
My question is: are there specific types of functions/layers that are believed to be hard/impossible to train in neural nets and using back propagation? Is it likely to get much better results using neural nets if we were to use more sophisticated optimization methods?
Follow up comments: I am asking this because before neural nets became epidemic the most important step in designing new models was to make sure that training the model leads to a simple optimization problem (e.g. LP, QP, convex, bi-convex, etc.); even if doing gradient descent on more complex objective functions was possible. You wouldn't just do gradient descent unless you had a customized optimization procedure (with careful initialization and what not) to do training, otherwise you would very likely get stuck in a bad local minima. But I see people becoming as creative as they can get with neural nets and throw in any function in the training objective as long as they can compute the gradient so that they can do back propagation. 
Is there something special about back propagation that makes it different from gradient descent and protects it against issues like sensitivity to initialization, getting stuck in bad local minima, etc.? Or are we just excitedly enjoying the leap in the performance of neural nets, and being oblivious to those issues?
 A: There are plenty of functions that are hard to optimise. In fact when you look at the successful implementation, they are mainly image/signal processing using sigmoid or ReLU activation functions. (maybe you want to clarify what your target function is. I.e. do you mean the function you want to approximate or are you including the activation functions- i.e. minimising error for fixed network structure).
So a classic target function that NNs cannot approximate by gradient descent is the spiral (i.e. input is (x, y) coordinates and output is if input lies on spiral band). If you Google cascade correlation you will find pictures... 
A: 
My question is: are there specific types of functions/layers that are
  believed to be hard/impossible to train in neural nets and using back
  propagation? Is it likely to get much better results using neural nets
  if we were to use more sophisticated optimization methods?

With backpropagation alone you can't compute the argmax, argmin and similiar positional functions for example. But people got really creative in this front too.
These days people can backpropagate through distributions (VAEs), physical simulations (ray tracing for example), fixed point problems (DEMs) and differential equation solvers (NeuralODEs).

Follow up comments: I am asking this because before neural nets became
  epidemic the most important step in designing new models was to make
  sure that training the model leads to a simple optimization problem
  (e.g. LP, QP, convex, bi-convex, etc.); even if doing gradient descent
  on more complex objective functions was possible. You wouldn't just do
  gradient descent unless you had a customized optimization procedure
  (with careful initialization and what not) to do training, otherwise
  you would very likely get stuck in a bad local minima. But I see
  people becoming as creative as they can get with neural nets and throw
  in any function in the training objective as long as they can compute
  the gradient so that they can do back propagation.

I think the key innovation here was stochastic gradient descent.
Since we cannot guarantee convexity, people moved on from it and, with SGD, they found that local optima are just as fine in many cases, and that batch-learning helps the optimizer being stuck in saddle points and "shallow" optima.
We have now several methods to optimize networks with good probability of convergence to flat local minima.
Piecewise differentiability is still necessary, though, for most functions.
