Randomized Thresholding for Algorithmic Stability and Statistical Power

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 138 papers55 conceptsfrozen 2026-10-04

In classical algorithm design, we often rely on deterministic decision boundaries: a job is scheduled if its predicted runtime is below a limit; a hypothesis is rejected if its p-value is less than 0.05; an item is included in a knapsack if it fits within a fixed capacity.

While these "hard" thresholds are intuitive, they are fundamentally brittle. A tiny fluctuation in data—noise in a sensor, a single different sample in a dataset, or a minor prediction error—can flip a decision entirely. This brittleness leads to three major problems: a lack of replicability across scientific studies, a loss of statistical power in discrete settings, and sensitivity where small input changes cause massive output reshuffling.

A growing body of research across bandits, testing, and optimization suggests a shared solution: replacing fixed thresholds with randomized thresholds. By injecting controlled noise into the decision boundary itself, researchers can "smooth" the transition between states, ensuring that algorithms are robust to noise and more efficient in their use of data.

The Mechanism: Smoothing the Decision Edge

The core intuition behind randomized thresholding is to prevent the "test statistic" from landing exactly on the decision boundary. If a threshold is fixed at $c$, any value $c \pm \epsilon$ is highly sensitive. However, if the threshold $\tau$ is sampled from a distribution (often a uniform interval $[c-\eta, c+\eta]$), the probability that a specific data point falls exactly on the boundary becomes negligible.

As Noah Fleming and Yuichi Yoshida demonstrate in Sensitivity Lower Bounds for Approximaiton Algorithms, this mechanism ensures that the expected change in an algorithm's output remains small even when the input is modified. This "probabilistic smoothing" transforms sharp performance drops into graceful, linear degradations.

Achieving Replicability in Adaptive Learning

Replicability is the requirement that two researchers, running the same algorithm on different samples from the same distribution, should reach the same conclusion. In stochastic settings like Multi-armed Bandits, this is notoriously difficult because early random rewards can lead different runs down entirely different exploration paths.

To solve this, Hossein Esfandiari, Andreas Krause, and their colleagues introduced replicable policies in Replicable Bandits. Their approach uses a shared random seed to pick a decision boundary from a uniform interval. This creates a "buffer" zone: if two researchers observe slightly different mean rewards for an arm, the randomized threshold ensures they are still highly likely to land on the same side of the boundary (e.g., both deciding to keep or both deciding to eliminate the arm).

This concept has been extended to various domains:

Squeezing Power from Statistical Budgets

In classical statistics, particularly with discrete data, deterministic thresholds are often "conservative." If you need to control the False Discovery Rate (FDR) at 0.05, but your discrete test statistic can only jump from 0.03 to 0.06, a deterministic rule must stop at 0.03, wasting the remaining "error budget."

Aaditya Ramdas and Ziyu Xu have pioneered the use of randomization to reclaim this lost power. In More powerful multiple testing under dependence via randomization, they describe stochastic rounding: using a random variable to decide between two thresholds such that the expected error rate exactly matches the target. This ensures the randomized test is strictly more powerful—identifying more true discoveries—than its deterministic counterpart while maintaining the same rigorous guarantees.

Similarly, Nick Heard and Patrick Rubin‐Delanchy explore this in Meta-analysis of mid-p-values, showing that adding artificial noise to discrete data allows for more sensitive meta-analyses. While practitioners historically avoided "injecting randomness" into science, these works argue that controlled randomization is a mathematical necessity for optimal sensitivity.

Robustness in Learning-Augmented Algorithms

The utility of randomized thresholds extends to "learning-augmented" algorithms, where predictions about the future (like job runtimes) are used to improve performance. Deterministic strategies here are often "brittle"—if a prediction is slightly off, the algorithm might make a catastrophic scheduling mistake.

In On Tradeoffs in Learning-Augmented Algorithms, Ziyad Benomar and Vianney Perchet demonstrate that randomized prediction perturbation—modifying a prediction with noise before acting on it—prevents performance cliffs. This ensures the algorithm's competitive ratio changes continuously rather than abruptly as prediction error increases, providing a safety net for imperfect machine learning models.

Summary of Benefits

Problem Deterministic Approach Randomized Thresholding
Replicability Small data changes flip results. Shared randomness buffers the boundary.
Statistical Power Wastes "leftover" error budget. Uses the full budget via stochastic rounding.
Sensitivity Cascading reshuffling of outputs. Decouples output from exact boundaries.
Brittleness Performance cliffs on prediction error. Smooth, graceful performance degradation.

By moving from fixed points to distributions, this research direction suggests that the "noise" we usually try to eliminate from data can be countered by strategically adding a different kind of "noise" to our decision-making processes. As Max Hopkins and Shay Moran conclude in The Role of Randomness in Stability, randomness is not just a source of variance to be managed, but a fundamental tool for achieving algorithmic stability.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_thresholding_for_algorithmic__32f5a648,
  title = {Randomized Thresholding for Algorithmic Stability and Statistical Power},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-thresholding-for-algorithmic-stability-and-statistical-power/rdr_32f5a648a4384113861237fc405b180d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_thresholding_for_algorithmic__32f5a648_v1,
  title = {Randomized Thresholding for Algorithmic Stability and Statistical Power},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-thresholding-for-algorithmic-stability-and-statistical-power/rdr_32f5a648a4384113861237fc405b180d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}