You could argue (wrongly) that Earth's gravity is being overcome because the balloon is rising. The same argument could apply to rising air bubbles in water or an ascending submarine.
Rather than consider the balloon as a rising object consider the denser air around the balloon descending. Gravity pulls the denser air downwards allowing the balloon to rise. Similarly, when an air bubble rises in water the denser water around it is pulled downwards by gravity.
These examples all result in the system achieving the lowest state of gravitational potential energy.