  For a regression problem with a binary label response, we examine the problem
of constructing confidence intervals for the label probability conditional on
the features. In a setting where we do not have any information about the
underlying distribution, we would ideally like to provide confidence intervals
that are distribution-free---that is, valid with no assumptions on the
distribution of the data. Our results establish an explicit lower bound on the
length of any distribution-free confidence interval, and construct a procedure
that can approximately achieve this length. In particular, this lower bound is
independent of the sample size and holds for all distributions with no point
masses, meaning that it is not possible for any distribution-free procedure to
be adaptive with respect to any type of special structure in the distribution.
