📊 statistics

Online monotone density estimation and log-optimal calibration

This paper introduces two online estimators for monotone density estimation that achieve optimal $O(n^{1/3})$ log-likelihood gaps and $\sqrt{n\log{n}}$ regret bounds, while demonstrating their application in constructing empirically adaptive, log-optimal p-to-e calibrators for sequential hypothesis testing.

Original authors: Rohan Hore, Ruodu Wang, Aaditya Ramdas

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rohan Hore, Ruodu Wang, Aaditya Ramdas

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 figure out the "shape" of a hidden distribution based on clues that arrive one by one. In statistics, this is called density estimation. Usually, you wait until you have all the clues (data) before you draw your conclusion.

But what if you have to make a guess right now, before the next clue arrives? And what if you know for a fact that the hidden shape is monotone? That means it's always going down (or staying flat) as you move from left to right, like a slide or a waterfall. It never goes back up.

This paper tackles that exact problem: How do you learn a "downward-sloping" shape in real-time, as data trickles in?

Here is the breakdown of their solution, using some everyday analogies.

1. The Two Detectives (The Algorithms)

The authors propose two different "detectives" (algorithms) to solve this puzzle.

Detective A: The "Re-do-er" (The Online Grenander Estimator)

Imagine a student taking a test. Every time a new question comes in, this student throws away their old answer sheet, re-reads every single question from the beginning, and writes a brand new answer sheet from scratch.

How it works: At every step, it looks at all the past data and calculates the "best possible" downward-sloping shape that fits everything seen so far.
Pros: It's very accurate if the data is stable.
Cons: It's slow and rigid. If the rules of the game change halfway through, this detective is stuck looking at the old rules and takes a long time to catch up.

Detective B: The "Team of Experts" (The Expert Aggregation Estimator)

Imagine a hiring manager who doesn't try to be the expert themselves. Instead, they hire a team of 100 different "experts" (each with their own theory about what the shape looks like).

How it works:
- Every day, the manager asks all experts for their prediction.
- If an expert was right yesterday, the manager gives them more money (weight).
- If an expert was wrong, they get fired (or their budget is cut).
- The final prediction is a weighted average of the whole team.
Pros: It's incredibly fast and adaptable. If the data suddenly changes (like a sudden shift in the weather), the "experts" who predicted that change get more money immediately, and the team's prediction shifts instantly.
Cons: It requires setting up the team of experts first.

2. The Big Win: The "Speed Limit" of Learning

The authors proved mathematically that both detectives are good, but they have different strengths.

The "Perfect World" Scenario: If the data is coming from a stable, predictable source, both detectives learn the shape at a specific speed (mathematically, a rate of $n^{1/3}$ ). This is the best possible speed for this type of problem.
The "Chaos" Scenario: If the data is messy or the rules change, the "Team of Experts" (Detective B) wins hands down. The paper proves that this team can track the best possible shape (even if that shape was only obvious after seeing all the data) with a very small error margin. It's like having a GPS that instantly reroutes you when traffic changes, while the "Re-do-er" is still trying to recalculate the whole map from scratch.

3. The Real-World Application: The "Magic Converter"

The most exciting part of the paper is how they used this to fix a problem in Scientific Testing.

The Problem: Scientists often use P-values to decide if a drug works or if a theory is true.

The Catch: P-values are designed for fixed experiments (e.g., "I will test 100 people, then stop"). If you peek at the results early and decide to stop because things look good, your P-value becomes invalid. This is called "peeking," and it breaks the math.

The Solution: There is a newer, more flexible tool called an E-value. E-values can handle "peeking" (stopping whenever you want).

The Bridge: To turn a P-value into an E-value, you need a "converter" (a calibrator).
The Twist: The authors realized that the best possible converter is actually a downward-sloping shape (a monotone density).
The Result: By using their "Team of Experts" algorithm, they built a self-learning converter.
- It watches the P-values come in.
- It learns the shape of the data in real-time.
- It converts them into E-values that are mathematically perfect for sequential testing.

Why this matters: This allows scientists to run experiments that stop the moment they find the answer, without breaking the rules of statistics. It makes research faster and safer.

Summary

The Goal: Learn a "downward-sloping" shape from data that arrives one by one.
The Method: They created two ways to do it. One is a "do-it-all-from-scratch" method, and the other is a "smart team of experts" method.
The Winner: The "Team of Experts" is faster, more adaptable, and handles changing data much better.
The Impact: They used this to build a "magic converter" that lets scientists stop experiments early without cheating, making modern data science more efficient and reliable.

In short, they taught computers how to learn a specific type of curve in real-time, and used that skill to fix a major headache in how we test scientific theories.

1. Problem Statement

The paper addresses the problem of online monotone density estimation.

Setting: Data $X_1, X_2, \dots$ arrive sequentially. The goal is to construct a sequence of density estimators $\hat{f}_t$ that are predictable (i.e., $\hat{f}_t$ depends only on past observations $X_1, \dots, X_{t-1}$ ).
Constraint: The true underlying density $q$ is assumed to be non-increasing (monotone) and supported on the interval $[0, 1]$ .
Objective: Minimize the cumulative log-loss (negative log-likelihood) relative to benchmarks. The paper analyzes performance in two regimes:
1. Stochastic (Well-specified): $X_i \sim Q$ i.i.d. with a monotone density $q$ . The benchmark is the true density $q$ .
2. Adversarial (Hindsight-optimal): No distributional assumptions. The benchmark is the best offline monotone density estimator (constrained Grenander estimator) chosen with full knowledge of the data up to time $n$ .

2. Methodology

The authors propose two distinct online algorithms:

A. Online Grenander (OG) Algorithm

Concept: A direct online adaptation of the classical offline Grenander estimator (the maximum likelihood estimator for monotone densities).
Mechanism: At each time step $t$ , the algorithm computes the constrained MLE using all past observations $\{X_1, \dots, X_{t-1}\}$ .
Formulation:
$\hat{f}^{OG}_t \in \arg\max_{f \in \mathcal{D}_{a,b}} \sum_{i=1}^{t-1} \log f(X_i)$
where $\mathcal{D}_{a,b}$ is the class of monotone densities bounded by $[a, b]$ .
Limitation: It requires recomputing a full monotone MLE at every step, which can be computationally intensive and slow to adapt to distributional shifts.

B. Expert Aggregation (EA) Algorithm

Concept: An aggregation-based approach inspired by exponential weighting methods in online learning.
Mechanism: The algorithm maintains a finite pool of "expert" monotone histogram densities. It updates weights based on the likelihood of past observations.
Formulation:
$\hat{f}^{EA}_t(u) = \sum_{f \in \mathcal{E}_m} w_t(f) f(u)$
where weights $w_t(f)$ are proportional to the cumulative likelihood $\prod_{i=1}^{t-1} f(X_i)$ .
Expert Construction: The experts are carefully constructed monotone histograms with breakpoints on a specific grid and discretized heights, ensuring the class size is manageable while approximating the optimal offline estimator.

3. Key Contributions

First Systematic Study: This work fills a gap in the literature by providing the first systematic theoretical analysis of monotone density estimation in the online setting.
Statistical Guarantees (Stochastic Setting):
- For both OG and EA, the authors prove that the excess KL-risk (the gap between the online estimator's risk and the true density's risk) scales as $O(n^{1/3})$ .
- This matches the known convergence rates of the offline Grenander estimator in Hellinger distance, translated to KL divergence.
Regret Bounds (Adversarial Setting):
- For the EA algorithm, the authors establish a pathwise regret bound of $O(\sqrt{n \log n})$ relative to the best offline constrained Grenander estimator.
- This bound holds under mild regularity conditions (data points are well-spaced and bounded away from the boundary).
- Theoretical analysis suggests EA has better finite-sample adaptivity than OG, particularly in misspecified settings.
Application to Sequential Testing (p-to-e Calibration):
- The authors demonstrate a novel connection: constructing log-optimal p-to-e calibrators for sequential hypothesis testing is mathematically equivalent to online monotone density estimation.
- A p-to-e calibrator must be a non-increasing function (a monotone density) to transform p-values into valid e-values.
- The proposed online estimators (OG and EA) are adapted to create empirically adaptive calibrators.

4. Key Results

Risk Bounds: In the well-specified stochastic setting where $q \in \mathcal{D}_{a,b}$ , both estimators satisfy:
$\text{Risk}_Q(\hat{f}; n) \leq \Gamma(a,b) n^{1/3}$
Regret Bounds: For the EA algorithm, under mild spacing conditions on the data sequence:
$\text{Regret}(\hat{f}^{EA}; n) \leq \Gamma(a,b,\beta) \sqrt{n \log n}$
Asymptotic Log-Optimality: When applied to sequential testing where p-values are i.i.d. with a monotone density $q$ , the proposed adaptive calibrators are asymptotically log-optimal. Specifically:
$\lim_{n \to \infty} \frac{1}{n} (\log M_n(\hat{h}) - \log M_n(h_{opt})) = 0 \quad \text{Q-almost surely}$
where $M_n$ is the accumulated e-process (wealth).
Empirical Performance:
- In simulations, EA consistently outperforms OG in finite samples, exhibiting smaller regret.
- In misspecified settings (e.g., a change-point in the data distribution), EA adapts significantly faster than OG because it reweights experts based on recent data, whereas OG is heavily influenced by the entire history.

5. Significance and Impact

Theoretical Advancement: The paper bridges the gap between classical non-parametric statistics (Grenander estimation) and modern online learning, providing rigorous regret and risk bounds for monotone constraints.
Practical Utility in Sequential Inference: The application to p-to-e calibration is highly significant. E-values are the standard for valid sequential testing (handling optional stopping). By showing that optimal calibration reduces to density estimation, the authors provide a data-driven method to construct powerful sequential tests without needing to know the alternative distribution in advance.
Adaptivity: The results highlight the superiority of aggregation-based methods (EA) over direct MLE updates (OG) in dynamic environments, offering a robust tool for real-world scenarios where data distributions may shift or be only approximately monotone.

In summary, this work provides a rigorous framework for estimating monotone densities online, proves their optimality, and leverages these results to solve a critical problem in sequential hypothesis testing: the construction of adaptive, log-optimal calibrators.