Stream::allMatch
In Java 8 you can check that not all lists are empty.
boolean anyNonEmpty = !map.values().stream().allMatch(List::isEmpty);
Notice that Stream::allMatch is a short-circuiting terminal operation. So the stream is efficient, not running any longer than need be.