This is definitely not coming from your phone's OS (unless you have a modified OS version with ads). So let's try to figure which app is pushing ads here. (If none of these help, try snapping a picture when they appear and post here without personal info and we'll keep trying!)
1) Are these ads over a specific app, or do they appear over any app, the homescreen of your phone included? If it's a specific app, you know which one to target. If it's over every app, let's keep digging.
2) Do they show up as overlays on the screen, or as notifications? If overlays, you can check the list of apps that are allowed such permission on your phone and that will narrow it down to a more manageable list.
3) If it's a notification, is there a "Play store" icon next to them? If so, they should only be ads recommending apps you may be interested in or events related to your own apps. You can turn this off in the Play Store settings.
4) If it's a notification with a browser icon, most likely you enabled push notifications for a malicious site via said browser. The list of sites that are enabled these can be checked (and disabled) through the browser app that's pushing them.
5) If there are no known icons on the notification banner, try long-pressing it and see the options that come up. That likely will tell you which app is pushing them and furthermore, can tell you which 'category' it belongs to.
6) Less likely, but check your data connection settings. If a malicious app changed the DNS address, they may be redirecting your traffic through a server that injects ads into your datastream.
Facebook
Twitter
Instagram