In addition to the great advice goodplay has given, as a RX 580 owner I off this:
Unfortunately this is a common issue. It is power related typically and nothing wrong likely with your system. My RX 580 exhibits the same behavior.
Most of the RX 580's sold are overclocked out of the box and as such the vanilla drivers don't supply a high enough power ceiling.
This is quickly fixed by raising the Red Power Limit Sider to it's maximum. Slide the slider all the way to the right to 50. This is still well withing normal range and is not over volting in any way. It is dynamic and doesn't even mean your card is constantly using more power. Only that it can use more when needed.
This setting is in Radeon Setings / Gaming / Global Settings / Global Wattman : down below the fan settings.
If this alone does not help there are several other things you can do to get it stable. Let us know how this works for you first please.