Neural Networks are formally hard to train. How can we circumvent hardness results? • Over specified networks: While over specification seems to speedup training , formally hardness results are valid in the improper model. • Changing the activation function: While changing the activation function from sigmoid to ReLu has lead to faster convergence of SGD methods, formally these networks are still hard.