I agree with Chris-Jr. If you are using Firebase to embed your AdMob ads (or even if you are not) the play-services-analytics includes the play-services-ads even though you don't add that as a dependency. Google have obviously made a mistake in their 11.4.0 roll-out as the analytics is including version 10.0.1 of ads, not 11.4.0 (the mouse over hint in the gradle shows this).
I manually added compile 'com.google.android.gms:play-services-ads:11.4.0' at the top which worked, but only after I disabled Instant Run: http://stackoverflow.com/a/35169716/530047
So its either regress to 10.0.1 or add the ads and disable Instant Run. That's what I found if it helps any.