📊 statistics

An Optimal False Discovery Rate Controlling Procedure for Changepoint Detection

This paper introduces Lean Bonferroni Detection - False Discovery Rate (LBD-FDR), a new procedure that guarantees false discovery rate control across diverse distributional settings, achieves optimal detection constants for Gaussian sequences, and outperforms existing minimax optimal methods in specific regimes while offering a computationally feasible algorithm.

Original authors: Louis Davis, Guenther Walther

Published 2026-08-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Louis Davis, Guenther Walther

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery hidden inside a long, noisy stream of data. Maybe it's a heartbeat monitor beeping wildly, a stock market ticker jumping up and down, or a sensor on a satellite picking up strange signals. The data isn't random; it's a story told in numbers, but the story has "chapters" where the rules suddenly change. These sudden shifts are called changepoints. Your job is to find exactly where these chapters begin and end.

The tricky part is that the data is full of static, like a radio tuned between stations. Sometimes the static looks like a real signal, and sometimes a real signal is so quiet it gets lost in the noise. In the past, statisticians had to be extremely cautious. They used a "zero-tolerance" rule: if there was even a tiny chance they were wrong about a signal, they wouldn't report it. This kept them safe from false alarms, but it also meant they missed a lot of real, faint signals. It's like a security guard who refuses to let anyone in unless they have a perfect ID, even if they are just a regular customer who forgot their wallet.

Recently, scientists realized that in a world with massive amounts of data, being too cautious is a waste. Instead of demanding zero mistakes, they started using a strategy called False Discovery Rate (FDR). Think of this as a "good enough" policy: "We might make a few mistakes, but as long as the majority of our findings are correct, we are doing a great job." This allows detectives to spot those faint, whisper-quiet signals that the old, strict rules would ignore. However, finding these signals without getting confused by the noise is a massive mathematical puzzle, especially when the noise is weird or the signals are packed tightly together.

The Paper's Big Idea: The Lean Detective

In this paper, Louis Davis and Guenther Walther from Stanford University introduce a new, super-smart detective tool called LBD-FDR (Lean Bonferroni Detection - False Discovery Rate). Their goal is to find changepoints in a sequence of data that are both accurate (they actually found the shift) and precise (they can tell you exactly where it happened, not just "somewhere in this neighborhood").

The authors propose that their new method is better than the current top-tier tools because it is "count-adaptive." Here is a simple way to visualize the difference:

The Old Way (Type I Error Control): Imagine a strict bouncer at a club who checks every single person's ID against a massive list of known fakes. If the list is huge, the bouncer becomes super strict and turns away many real customers just to be safe. This works great if there are only a few fake IDs, but if the club is packed with thousands of people, the bouncer misses almost everyone.
The New Way (LBD-FDR): Imagine a smarter bouncer who knows that in a huge crowd, it's okay to let a few people slip through if it means catching the real troublemakers. This bouncer looks at the pattern of the crowd. If they see a group of people acting suspiciously together, they can lower their guard just a tiny bit to catch the whole group, rather than checking every single person individually with a magnifying glass.

How LBD-FDR Works:
The method breaks the long stream of data into many overlapping "triplets" (groups of three sections). It checks each triplet to see if a change happened in the middle.

The "Lean" Part: Instead of checking every possible combination of data (which would take forever), it uses a clever, sparse grid of intervals. It's like searching for a lost key in a house by checking specific, high-probability spots rather than every single dust mote.
The "FDR" Part: It uses a special mathematical trick called IndBH (Independent Benjamini-Hochberg). This trick looks at the "dependency graph" of the data. If two data chunks overlap, they are connected; if they don't, they are independent. The method finds groups of independent chunks and applies the "good enough" rule to them. This allows it to detect signals that are too weak for the old, strict methods to see.

What They Found:
The authors proved mathematically that LBD-FDR works in a wide variety of situations, including when the data is "heavy-tailed" (meaning it has extreme, wild outliers that break standard math models).

The "Undetectable" Problem: They showed that their method can find changepoints even when those changepoints are so close together or so weak that other methods would give up. Specifically, if changepoints are very close to each other, LBD-FDR can still find them, whereas the old "strict" methods often fail.
The "Optimal" Claim: In certain scenarios (like when the data follows a normal Gaussian distribution), they proved that LBD-FDR hits the "optimal detection constant." This means it finds the faintest possible signal that is theoretically possible to find. It doesn't just find some signals; it finds the weakest ones that any method could possibly hope to catch.
The Simulation Results: In computer simulations, they tested LBD-FDR against five other famous methods (including SMUCE, FDRSeg, and MUSCLE).
- When the noise was normal (Gaussian), LBD-FDR was often as good as or better than the others in finding the signals.
- When the noise was weird (like a "heavy-tailed" distribution where extreme values happen often), LBD-FDR stayed reliable. In contrast, some other methods (like FDRSeg) started making too many mistakes and losing their "guarantee" of accuracy.
- LBD-FDR was also very good at pinpointing the exact location of the change, not just saying "it's somewhere in this big block."

What They Argue Against:
The paper explicitly argues against the idea that we must always use the strict "Type I error" control (the zero-tolerance bouncer) when dealing with a large number of changepoints. They show that being too strict actually hurts your ability to find real signals when the data is complex. They also point out that while some existing methods (like FDRSeg) are powerful, they can fail to control their error rates when the data doesn't follow a perfect bell curve, making them unreliable in real-world messy situations.

How Sure Are They?
The authors are very confident in their mathematical proofs for the Gaussian (normal) data case; they have derived theorems showing that their method is optimal in specific regimes. For the more complex, non-standard data (like heavy tails), they rely on simulations to show that the method works well and stays valid, while other methods fail. They don't claim it works for every possible scenario in the universe, but they have proven it works for a very wide and challenging range of them, including cases where the number of changepoints is growing and they are packed closely together.

In short, LBD-FDR is a new, flexible, and mathematically rigorous tool that lets statisticians find more hidden signals in messy data without getting lost in the noise. It's a step forward from "playing it safe" to "playing it smart."

Title: An Optimal False Discovery Rate Controlling Procedure for Changepoint Detection

Problem Statement
The paper addresses the problem of detecting and localizing a growing number of changepoints in a sequence of independent observations. The authors consider a piecewise constant signal plus noise model ( $X_k = \mu_k + \varepsilon_k$ ) where the number of changepoints $N_n$ is unknown and potentially large. The goal is to provide a collection of localized intervals such that, in expectation, a high proportion of them contain a true changepoint.

A central challenge identified is the trade-off between Type I error control and statistical power. Existing methods that strictly control the Type I error (Family-Wise Error Rate, FWER), such as SMUCE and Lean Bonferroni Detection (LBD-FWER), can be overly conservative when the signal-to-noise ratio is modest and the number of changepoints is large. In such regimes, these methods may fail to detect weaker signals. Conversely, while False Discovery Rate (FDR) controlling methods (e.g., FDRSeg, MUSCLE) offer higher power, they often lack tight localization regions with finite-sample guarantees or rely on stronger distributional assumptions. Furthermore, many existing FDR methods do not provide "tight" confidence regions around the estimated changepoints, as their intervals are derived by inverting FDR-controlling procedures rather than Type I error controlling ones.

Methodology: LBD-FDR
The authors propose Lean Bonferroni Detection - False Discovery Rate (LBD-FDR), a new methodology that combines the structural advantages of LBD with a graphical FDR control procedure.

Bonferroni Triplets: The method utilizes a sparse collection of "Bonferroni triplets" $(s, m, e)$ , which are intervals constructed by adjoining an extension to a Bonferroni interval. These triplets approximate the local geometry around potential changepoints, allowing for optimal testing of the hypothesis that no changepoint exists within the interval $(s, e)$ with a split at $m$ .
Local Testing: For each triplet, a local test statistic is computed. In the Gaussian setting, this is the generalized likelihood ratio statistic (equivalent to a two-sample $t$ -statistic). For heavy-tailed or non-parametric settings, the authors utilize the two-sample Kolmogorov-Smirnov statistic or Wilcoxon rank-sum statistic, ensuring validity under exchangeability assumptions.
Graphical FDR Control (IndBH): Instead of combining local tests via a weighted Bonferroni correction (as in LBD-FWER), LBD-FDR employs the IndBH (Independent set Benjamini-Hochberg) procedure introduced by Nguyen and Fithian [2025].
- The dependency structure of the local $p$ -values is encoded in an undirected graph where nodes represent triplets and edges connect triplets with overlapping data stretches.
- IndBH controls the FDR by identifying independent sets within this dependency graph and applying the Benjamini-Hochberg procedure to the masked $p$ -values of these independent sets.
Pruning: The method outputs a set of rejected intervals. To provide interpretable localization, the authors define two pruned rejection sets:
- Minimal intervals: The subset of rejected intervals that are minimal with respect to inclusion (shortest intervals detecting a signal).
- Disjoint intervals: The largest subset of rejected intervals that are mutually disjoint.

Key Contributions and Theoretical Results

Finite-Sample FDR Control: Theorem 3.2 establishes that LBD-FDR controls the False Discovery Rate at level $\alpha$ for the collections of all, minimal, and disjoint rejected intervals. This validity holds in a wide range of distributional settings, including non-parametric and heavy-tailed data, provided the data are independent (or exchangeable within null intervals).
Consistency and Detection Thresholds: In the canonical Gaussian mean-shift model, the authors derive sufficient conditions for the detection of "high-energy" changepoints (Theorem 4.1). They show that LBD-FDR can detect changepoints with energy $E_k$ satisfying:
$E_k \geq \left(2 \log \frac{n}{K_n}\right)^{1/2} + \sqrt{2 \log K_n} + c_n$
where $K_n$ is the number of detectable changepoints.
Optimality and Comparison to FWER: The paper demonstrates that LBD-FDR is more powerful than Type I error controlling methods (like LBD-FWER) in regimes where changepoints are closely spaced or numerous. Specifically, if the spacing between changepoints is small relative to the total number of changepoints ( $(\tau_k - \tau_{k-1}) \wedge (\tau_{k+1} - \tau_k) < K_n$ ), LBD-FDR can detect signals with energy below the minimax detection boundary required for FWER control. This is attributed to the data-dependent threshold of IndBH, which aggregates moderate signals, whereas FWER methods must protect against the maximum of null statistics.
Impossibility Results: Theorem 4.2 provides a scale-dependent impossibility theorem, establishing necessary conditions for any FDR-controlling procedure to localize changepoints. The authors show that LBD-FDR attains the optimal detection constant ( $\sqrt{2}$ ) in specific sparse regimes, matching the lower bounds derived for FDR procedures.
Computational Efficiency: While the general IndBH algorithm is NP-hard for arbitrary graphs, the authors exploit the interval overlap structure of the dependency graph to develop a computationally feasible algorithm using dynamic programming. The time complexity is $O(n^2)$ in the worst case but reduces to nearly linear time $O(n \log^{7/2} n)$ for exponential family data with moderate signal-to-noise ratios.

Empirical Results
The authors conduct a simulation study comparing LBD-FDR against five existing methods: LBD-FWER, SMUCE, FDRSeg, MQS, and MUSCLE.

Power and Precision: LBD-FDR consistently achieves power comparable to or better than FDRSeg and MUSCLE, particularly under Gaussian noise, while maintaining superior localization precision (tighter intervals) compared to these methods.
Robustness: In settings with heavy-tailed noise (e.g., $t$ -distributions with low degrees of freedom), LBD-FDR maintains valid error rate control. In contrast, FDRSeg and SMUCE are shown to empirically violate their error rate guarantees (Type I error or FDR) when the noise lacks a second moment.
Localization: The method successfully produces tight localization regions for true changepoints, even in scenarios with a large number of closely spaced changepoints where other methods fail to detect any.

Significance
The paper claims that LBD-FDR offers a significant advancement by bridging the gap between the strict validity of Type I error controlling methods and the high power of FDR methods. It provides the first finite-sample FDR control guarantee for changepoint localization that yields tight intervals and remains valid under non-parametric and heavy-tailed assumptions. The method is particularly significant for applications involving high-frequency changepoints or weak signals where traditional FWER methods are too conservative, and for applications involving non-Gaussian data where existing FDR methods may lack theoretical validity. The authors note that their approach is "count adaptive" (adapting to the number of signals) rather than "scale adaptive," allowing it to "pay" less to detect a growing number of moderate signals.

The Paper's Big Idea: The Lean Detective

More like this