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."
Pooling mainly helps in extracting sharp and smooth features. It is also done to reduce variance and computations. Max-pooling helps in extracting low-level features like edges, points, etc. While Avg-pooling goes for smooth features. If time constraint is not a problem, then one can skip the pooling layer and use a convolutional layer to do the same. Refer this.
It really depends on the images. In some scenarios, Max pooling can take away too much info, resulting in worst performance that a CNN without max pooling. See this video for a surprising comparison using the MNIST Fashion dataset: https://www.youtube.com/watch?v=0ixAwVAfejY