<p>To add to your question - how about pixel perfect accuracy of segmentation boundary !!</p>
<p>Your intuition regarding down-sampling via max-pooling is correct. Normal CNNs have that limit. However, there have been some improvements recently to overcome it.</p>
<p>The breakthrough to this problem came in 2015-6 in the form of <a href="https://arxiv.org/abs/1505.04597" rel="nofollow noreferrer">U-net</a> and atrous/dilated convolution introduced in <a href="https://arxiv.org/abs/1706.05587" rel="nofollow noreferrer">DeepLab</a>.</p>
<p>Dilated convolutions or atrous convolutions, previously described for wavelet analysis without signal decimation, expands window size without increasing the number of weights by inserting zero-values into convolution kernels. Dilated convolutions have been shown to decrease blurring in semantic segmentation maps, and are purported to work at least in part by extracting long range information without the need for pooling.</p>
<p>Using U-Net architectures is another method that seeks to retain high spatial frequency information by directly adding skip connections between early and late layers. In other words, up-sampling followed by down-sampling.</p>
<p>In TensorFlow, atrous convolutions are implemented with function:</p>
<pre><code>tf.nn.atrous_conv2d
</code></pre>
<p>There are many more methods and this is an ongoing research area.</p>
Is there a fundamental limit on how accurate location information is encoded in CNNs
<p>Each layer in a CNN reduces the size of the input via convolution and max-pooling operations. Convolution is translation equivariant, but max-pooling is translation invariant. Correct me if this is wrong : each time  max-pooling applied, the precise location of a feature is reduced. So the feature maps of the final conv layer in a very deep CNN will have a large receptive field (w.r.t the original image), but the location of this feature (in the original image) is not discernible from looking at this feature map alone.</p>
<p>If this is true, how can the accuracy of bounding boxes when we do localisation be so good with a deep CNN? I understand how classification works, but making accurate bounding box predictions is confusing me.</p>
<p>Perhaps a toy example will clarify my confusion;</p>
<p>Say we have a dataset of images with dimension <code>256x256x1</code>, and we want to predict whether a cat is present, and if so, where it is, so our target is something like <code>[sigmoid_cat_present, cat_location]</code>.</p>
<p>Our vanilla CNN (let's assume something like VGG) will take in the image and transform it to something like <code>16x16x256</code> in the last convolutional layer. Each pixel in this final <code>16x16</code> feature map can be influenced by a much larger region in the original image. So if we determine a cat is present, how can the <code>[cat_location]</code> be refined to value more granular than this effective receptive field?</p>