The cheapest video card for rendering Premiere Pro

Actually, the GT 710 is completely useless for GPU acceleration - to the point where it might actually be even slower and weaker than software-only (CPU-only) rendering. And what's more, almost all GT 710s only come with extremely slow DDR3 RAM that's actually slower and more constrained than even your PC's main system RAM! That severely bottlenecks the performance of even everyday apps - those that don't even utilize the GPU at all whatsoever. These actually decelerate overall system performance, to the point where overall performance would actually be as slow as or slower than a mainstream system that's 14 years old. I would not take the GT 710 even if it were completely free. And to top that off, driver support will be EOL'd for all remaining Kepler desktop GPUs, including that GT 710, within the next few months (with the GPU support first going into the legacy support phase while driver improvements will continue with Maxwell and newer GPUs).

And even a newer GT 1030, despite being more powerful than that GT 710 (which IMHO is now a total waste of money at any price), still barely performs on a par with current integrated Intel UHD Graphics. That makes it a waste of money at its current street price.

So, if those cheap GPUs totally suck (or at the very least a ripoff at their current street prices), then what to get?

You will not like my answer, but you will have to spend at least triple that budget just to get a GPU that does not slow down your overall system performance.