Distribution-Free Conditional Median Inference

We consider the problem of constructing confidence intervals for the median of a response $Y \in \mathbb{R}$ conditional on features $X = x \in \mathbb{R}^d$ in a situation where we are not willing to make any assumption whatsoever on the underlying distribution of the data $(X,Y)$. We propose a method based upon ideas from conformal prediction and establish a theoretical guarantee of coverage while also going over particular distributions where its performance is sharp. Further, we provide a lower bound on the length of any possible conditional median confidence interval. This lower bound is independent of sample size and holds for all distributions with no point masses.