VPN Access is provided with VPS's as well as Dedicated Servers. Therefore, one can consider either of the hosting solutions for VPN, however, if one needs better performance, a Dedicated Server is always recommended because the Hardware as well as the entire resources of the server belong to the customer and there are less limitations
Please feel free to post if you have any further questions.