Search papers, labs, and topics across Lattice.
Addressing the fundamental problem of quantifying non-stationarity without distributional assumptions, this work establishes the exact theoretical boundaries for inferring the number of changepoints $K$ in sequential data. The authors prove an impossibility theorem showing that any distribution-free upper confidence bound on $K$ is necessarily trivial and vacuous. To recover actionable guarantees, they construct the Conformal LOwer bound on Changepoint Count (CLOCC), proving it is the unique, universally valid finite-sample lower confidence bound achievable under segment-wise exchangeability.
Upper-bounding the number of distribution shifts in sequential data is provably impossible without parametric assumptions, but conformal inference can uniquely deliver valid, non-trivial lower bounds.
Suppose we are given an ordered sequence of independent data whose distribution changes $K$ times at unknown locations, for some unknown $K \geq 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.
Stanford HAI