I have also encountered this problem in Android Studio, from version 2.0 Preview 6 all the way up to 2.0 Beta 3 and none of the solutions mentioned here worked for me.
Turned up it had nothing to do with Instant Run. All I had to do was to increase the AVD’s Internal Storage until the following notification disappeared. I also had to perform a data wipe after changing the values.
