Distribution-free inference on the number of changepoints

Suppose we are given an ordered sequence of independent data whose distribution changes K times at unknown locations, for some unknown K at least 0. In this paper, we study the problem of performing distribution-free inference on K. First, we show an impossibility result: any distribution-free upper confidence bound on K must be trivial and uninformative. Then, using conformal p-values, and under only the assumption that the data segments induced by the changepoints are exchangeable (within themselves) and mutually independent, we construct a finite-sample valid lower confidence bound on K, which we call the Conformal LOwer bound on Changepoint Count (CLOCC). We show that CLOCC is the only feasible way to provide a lower bound on K under the stated assumptions, a property we refer to as its universality. We provide practical guidelines for choosing score functions that yield efficient and tight lower bounds. We evaluate CLOCC in several synthetic and real-data experiments, where it provides informative lower bounds on K, demonstrating its practical applicability.