Most common convolutional neural networks contains pooling layers to reduce the dimensions of output features. Why couldn't I achieve the same thing by simply increase the stride of the convolutional layer? What makes the pooling layer necessary?
You can indeed do that, see Striving for Simplicity: The All Convolutional Net. Pooling gives you some amount of translation invariance, which may or may not be helpful. Also, pooling is faster to compute than convolutions. Still, you can always try replacing pooling by convolution with stride and see what works better.
Apparently max pooling helps because it extracts the sharpest features of an image. So given an image, the sharpest features are the best lower-level representation of an image. https://www.quora.com/What-is-the-benefit-of-using-average-pooling-rather-than-max-pooling
But according to Andrew Ng's Deep Learning lecture, max pooling works well but no one knows why. Quote -> "But I have to admit, I think the main reason people use max pooling is because it's been found in a lot of experiments to work well, ... I don't know of anyone fully knows if that is the real underlying reason."