You can mine on a VPS, just beware that the service provider may throttle your CPU usage.

I tried that on an Amazon VPS and after about an hour they started limiting my CPU to about 20% of max. Several later tries produced the exact same result.