Feedback-Enhanced Online Multiple Testing with Applications to Conformal Selection

This paper proposes GAIF, a feedback-enhanced generalized alpha-investing framework that leverages revealed hypothesis outcomes to dynamically adjust thresholds for finite-sample false discovery rate control, and extends this approach to online conformal testing to improve model selection and statistical power.

The Gist

Imagine you are the manager of a massive, never-ending hiring process. Every day, a new candidate walks in, and you have to decide instantly: "Do we hire this person?"

You have a rule: You can't make too many bad hires. If you hire too many unqualified people, the whole company suffers. In statistics, this is called controlling the False Discovery Rate (FDR).

Now, here's the twist: You don't know if you made a mistake immediately.

• Sometimes, you find out the next day if the new hire was a genius or a disaster.
• Sometimes, you only find out if they were a disaster if you hired them (you never see the resume of the person you rejected).
• Sometimes, the feedback takes weeks to arrive.

This paper introduces a new, smarter way to make these decisions called GAIF (Generalized Alpha-Investing with Feedback).

Here is the breakdown in simple terms:

1. The Old Way: "Blind Betting"

Imagine you have a budget of "Hiring Tokens" (let's call them Alpha-Wealth).

• Every time you hire someone, you spend a token.
• If you hire a good person (a "True Discovery"), you get a few tokens back as a bonus.
• If you hire a bad person (a "False Discovery"), you lose tokens and get no bonus.

The old methods (like LORD++ or SAFFRON) were like gamblers who only knew if they won or lost after the game was over. They had to be very conservative, spending very few tokens just to be safe. This meant they missed out on hiring many great candidates because they were too afraid of running out of money.

2. The New Way: "The Feedback Loop" (GAIF)

The authors realized: "Wait, we often get feedback sooner than we thought!"

• The Metaphor: Imagine you are a detective solving a mystery. In the old way, you had to wait until the end of the book to see if your suspect was guilty. In the new way, as soon as you arrest someone, the police call you back and say, "Actually, this guy is innocent."
• The Magic: Because you know immediately (or with a short delay) that a specific hire was a mistake, you can adjust your strategy.
  • If you know a past hire was a mistake, you don't have to "pay" for that mistake in your future budget calculations.
  • This frees up more "Hiring Tokens" for future candidates.
  • Result: You can be bolder, hire more people, and still stay within your safety budget.

3. The "Smart Score" Selector

The paper also tackles a problem where the "best" way to judge a candidate changes over time.

• The Metaphor: Imagine you are hiring athletes. In January, you need runners, so you judge them by speed. In July, you need swimmers, so you judge them by swimming speed. If you keep using the "running" test in July, you'll pick the wrong people.
• The Solution: The new method uses Feedback-Driven Score Selection. It looks at the recent hires that did succeed and asks: "Which test (speed vs. swimming) worked best for them recently?" It then automatically switches to the best test for the next batch of candidates.

4. Real-World Applications

The authors tested this on three very different scenarios:

• Hiring (Candidate Screening): Filtering thousands of resumes in real-time to find the best interviewees without hiring too many unqualified people.
• LLM Alignment (AI Safety): Imagine an AI writing medical advice. You want to flag the answers that are wrong (hallucinations) before they go to the patient. The AI gives an answer, a doctor checks it later (feedback), and the system learns instantly to flag similar wrong answers in the future.
• Anomaly Detection (Fraud/Health): Spotting a credit card fraud or a machine failure. Once a human confirms it was a real fraud, the system learns to spot similar patterns faster next time.

The Bottom Line

This paper is about learning from your mistakes faster.

By building a system that listens to feedback (even if it's delayed or partial), we can make more correct decisions (higher power) without breaking the rules of safety (controlling errors). It turns a rigid, cautious process into a dynamic, learning machine that gets smarter with every single decision it makes.

In short: It's the difference between a manager who blindly follows a rulebook and a manager who learns from every hire, adjusts their strategy on the fly, and ends up with a much better team.

Technical Summary

1. Problem Statement

The paper addresses the challenge of Online Multiple Testing, where a stream of hypotheses $\{H_{0t}\}_{t=1}^\infty$ is tested sequentially in real-time. The goal is to control the False Discovery Rate (FDR) or Marginal FDR (mFDR) while maximizing statistical power (the number of true discoveries).

Key Innovation: Unlike traditional online testing which relies solely on past decisions and p-values, this work incorporates feedback. After a decision $\delta_t$ is made, the true state of the hypothesis $\theta_t$ (whether $H_{0t}$ is true or false) is revealed, either:

• Instantly or with a delay.
• Fully (all past $\theta$ revealed) or Partially (e.g., Bandit setting where $\theta_t$ is only revealed if $\delta_t=1$).

The authors aim to leverage this feedback to dynamically adjust testing thresholds, thereby reducing the "slack" in FDR estimation and improving power without violating error rate guarantees.

2. Methodology

The proposed framework consists of three main methodological pillars:

A. Generalized Alpha-Investing with Feedback (GAIF)

The authors extend the classic Generalized Alpha-Investing (GAI) framework (e.g., LORD++, SAFFRON) by integrating feedback into the False Discovery Proportion (FDP) estimator.

• Mechanism: In standard GAI, the FDP estimator assumes all past rejections could be false discoveries. GAIF refines this by using revealed feedback $\{\theta_j\}_{j \in I_t}$ (where $I_t$ is the set of indices with known states).
• FDP Estimator:
  $$\widehat{\text{FDP}}_{\text{GAIF}}(t) = \frac{\sum_{j \in I_t} (1-\theta_j)\alpha_j + \sum_{j \in \bar{I}_t} \alpha_j}{1 \vee R(t)}$$
  Here, terms where $\theta_j=1$ (true non-nulls) contribute 0 to the numerator, while unknown terms contribute $\alpha_j$.
• Threshold Adjustment: This refined estimator allows for a less conservative upper bound on the testing level $\alpha_t$, effectively "releasing" more $\alpha$-wealth for future tests when feedback confirms true discoveries.
• Variants: The framework handles Full/Instant, Bandit/Instant, Full/Delayed, and Bandit/Delayed feedback settings.

B. Adaptive GAIF (Adaptive Alpha-Wealth Allocation)

To further improve power, the authors introduce an adaptive weighting scheme inspired by SAFFRON.

• Weighting Function: Uses a function $\kappa(p) = \frac{I\{p > \lambda\}}{1-\lambda}$ to down-weight tests with large p-values (likely nulls) and reserve wealth for promising tests.
• Combined Effect: The Adaptive GAIF (e.g., SF, SF-BI) simultaneously utilizes feedback to reduce FDP slack and adaptive weighting to optimize wealth allocation based on p-value patterns.

C. Online Conformal Testing with Feedback (OCTF)

The framework is applied to Online Conformal Selection, a setting where decisions are made on whether an observation satisfies a target region $A$ (e.g., high-risk diabetes), and the true label $Y_t$ is revealed later.

• Challenge: Standard conformal p-values in online settings often suffer from dependence issues or lack finite-sample guarantees when feedback is used for thresholding.
• Solution:
  1. Dynamic Calibration: Construct online conformal p-values using a calibration set $C'_t$ that is updated sequentially with past null samples ($\theta_j=0$).
  2. Safe Procedures (LFS/SFS): To ensure rigorous finite-sample mFDR control, the authors propose "Safe" variants (LFS, SFS) where the testing levels $\alpha_t$ depend only on the history of true null rejections (denoted $\tilde{\tau}_j$), decoupling the threshold from non-null decisions.
• Optimized OCTF (Opt-OCTF): A feedback-driven score selection strategy is introduced. It adaptively selects the best conformity score (from $K$ candidates) using an Exponentially Weighted Moving Average (EWMA) of past auxiliary non-null p-values. This allows the system to adapt to distribution shifts in non-null data.

3. Key Contributions

1. GAIF Framework: First work to systematically integrate feedback into online FDR control thresholds. It provides finite-sample mFDR control under independence and local dependence, and strict FDR control under independence.
2. Adaptive Variants: Development of Adaptive GAIF (SF) which combines feedback with adaptive wealth allocation, significantly outperforming non-adaptive baselines.
3. Conformal Integration: Extension of GAIF to Online Conformal Testing (OCTF). The paper constructs valid, independent online conformal p-values and proves finite-sample mFDR control even when feedback is used for dynamic thresholding.
4. Score Selection & Optimality: Proposes a feedback-driven score selection criterion (EWMA-based) for handling distribution shifts. Theoretical analysis (Theorem 5) proves the consistency of this selection strategy under slowly varying non-null distributions.
5. Robustness: Handles various feedback regimes (instant/delayed, full/bandit) and local dependence structures.

4. Experimental Results

The authors validate their methods through extensive simulations and real-world applications:

• Synthetic Data:

  • Independence: GAIF (LF) and Adaptive GAIF (SF) consistently achieve higher power than LORD++, SAFFRON, and LOND while maintaining FDR $\le \alpha$.
  • Local Dependence: Dependence-aware variants (LFdep, SFdep) successfully control FDR, whereas standard methods fail.
  • Feedback Types: Bandit and delayed feedback settings show that even partial or delayed feedback significantly boosts power compared to no-feedback baselines.
  • Conformal Setting: In binary classification and regression tasks, OCTF methods (LFS, SFS) outperform standard conformal testing approaches.
  • Distribution Shift: The Opt-OCTF (with score selection) significantly outperforms random score selection when non-null distributions drift over time.

• Real-World Applications:

  • Datasets: Candidate screening, Diabetes risk identification, High-income selection, and Airfoil noise detection.
  • Findings: The proposed methods (Opt-SF, Opt-SFS) consistently achieve the highest power among all benchmarks. Notably, "Safe" variants (SFS, LFS) maintain strict FDR control even in difficult real-data scenarios where non-safe variants showed slight inflation, validating the theoretical guarantees.

5. Significance and Impact

• Bridging Theory and Practice: The paper bridges the gap between theoretical online FDR control and practical applications where feedback is abundant (e.g., medical diagnosis, LLM alignment, anomaly detection).
• Efficiency: By utilizing feedback to "spend" less alpha-wealth on confirmed true discoveries, the methods allow for more aggressive testing of future hypotheses, leading to substantial gains in discovery power.
• Model Agnosticism: The integration with Conformal Prediction provides distribution-free, model-agnostic guarantees, making the approach applicable to complex machine learning pipelines (e.g., neural networks, random forests) without assuming specific data distributions.
• Adaptability: The score selection mechanism addresses the critical issue of non-stationarity in real-world data streams, ensuring the testing procedure remains effective even as data distributions evolve.

In summary, this work establishes a new paradigm for online decision-making where feedback is not just a byproduct but a core resource for optimizing statistical power while rigorously controlling error rates.