Paradigm "program to interfaces, not implementations" vs. builder pattern

I like the builder pattern (example https://stackoverflow.com/a/1953567) for various reasons, e. g. the fact that I can work with immutable objects and that I can control the object creation in the way that no invalid objects can be created.

However, I try to follow the paradigm "program to interfaces, not implementations" (example https://stackoverflow.com/a/2697810).

I figured, these two guidelines do not play well together.

If I have an interface Person and a class PersonImpl and a builder PersonImplBuilder that builds a PersonImpl. I now can assure that every instance of PersonImpl is valid and immutable. But every return value and particularly every method parameter in my API uses the interface. So I can not depend on a valid object.

Am I missing something respectively is there another way of combining these two very useful guidelines?