I was getting the same on my Samsung S7. They started just after I ran updates for Google Play Store a few weeks ago in the 1st half of May 2018.
Ran several different anti-virus/malware apps & nothing. Cleared cache, uninstalled recent apps, etc, still getting them.
Then I found one way to stop the ads.... Disable Google Play Store!!
I no longer get the annoying ads... BUT, several other apps now keep leaving notes... 'xxx won't run unless you update Google Play Store.'
Tough titties Google! If you can't run a system without pushing ads forget it!
If I enable Google Play Store I then get random ads for Google Play Store, Google Home Mini, Wish, Uber, etc... Some of which are video with sound... EXTREMELY annoying whilst in a meeting!
Disable Google Play Store & all fixed!