It's perfectly possible to do targeted ads without collecting personal data! You just keep personal data where it belongs - on the user's computer/phone - rather than stealing it.
Keep the personal data in local storage, have the logic that chooses ads run locally, and you have targetted ads without invading anyone's privacy.
I don't know if that satisfies the GDPR - not a lawyer. But it would satisfy me.
Unless you are unconditionally loading all possible ads into that code that runs locally, it still betrays the result of the local code's analysis when it loads the specific ad. This kind of request is already used to exfiltrate personal information. Even if it isn't explicitly sending personal encoded into the choice of ad, simply sending coarse data about someone is still an unacceptable betrayal of privacy. Small, currently insignificant pieces of data become revealing specific life details when joined with other databases.
In addition to the choice of ad, the server can also log at least a timestamp, the IP Source Address, the {TCP,UDP} Source and Destination Ports, and any other interesting features in the IP protocol headers[1]. With some effort, this is probably enough to allow the ad requests to be correlated with other sources of personal data.
> you have targetted ads without invading anyone's privacy.
No, you only made it very slightly more difficult to invade privacy. This would only result in a minor rate limit to exfiltrate personal data, and added the need for a few more INNER JOIN clauses.
[1] This may include a significant amount of identifying entropy. For example, nmap's -O uses the variations in the IP headers and protocol implementation to guess the remote host's OS (sometimes to specific versions).
You're still processing the data on your system, even if you're not storing it. This approach takes care of deletion rights but not processing.
(Unless you move the entire list of ad inventory to the user's computer and let it pick the ad to load?)
Yes, it would be hugely challenging to implement, but it definitely seems possible to do something along these lines.