🤖 machine learning

Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

This paper develops a $\delta$ -explicit minimax-quantile theory for interactive statistical decision making under privacy constraints, providing new converse tools and deriving explicit lower bounds that capture rare failures and privacy-induced variance inflation for problems like Gaussian mean estimation and multi-armed bandits.

Original authors: Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering, Mikael Skoglund

Published 2026-06-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering, Mikael Skoglund

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 trying to make a series of decisions in a game where the rules are hidden, and you want to be sure you won't make a catastrophic mistake. Usually, statisticians and computer scientists look at the average performance of their strategies. They ask, "On average, how much money will I lose?"

But the authors of this paper argue that "average" can be misleading. It's like saying, "On average, a plane crash is rare." That's true, but if you are the one in the crash, the average doesn't help you. You care about the worst-case scenario: "What is the maximum amount of loss I could face, and how likely is it that I stay below that limit?"

This paper builds a new mathematical toolkit to answer that specific question, especially when two extra complications are added: interaction (you learn as you go) and privacy (you can't see the raw data).

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Average" Trap

In the old way of thinking (Minimax Risk), researchers calculate the expected loss.

The Analogy: Imagine two drivers. Driver A always drives at a steady 50 mph. Driver B drives at 50 mph 99% of the time, but once in a blue moon, they swerve off a cliff.
The Flaw: If you only look at the average speed or safety, Driver B might look fine. But if you are the passenger, you care about that one time they swerved.
The Solution: The authors introduce Minimax Quantiles. Instead of asking "What is the average loss?", they ask: "What is the loss threshold $r$ such that I am 99% sure (or $1-\delta$ sure) that my loss will not exceed $r$ ?" This focuses on the "tail" of the distribution—the rare but disastrous events.

2. The Setting: Interactive Decision Making

The paper focuses on Interactive Statistical Decision Making (ISDM).

The Analogy: This is like playing a game of "20 Questions" or a slot machine with multiple arms (a "Bandit" problem). You don't get all the data at once. You pull a lever, get a reward, and then decide what to pull next. Your decisions change the data you see next.
The Gap: Previous math tools were great for static data (like looking at a pile of photos) or for average outcomes in games. This paper creates the first rigorous math to predict the worst-case high-confidence outcomes for these interactive games.

3. The Tools: New "Converse" Methods

To prove that a problem is hard (i.e., you cannot do better than a certain limit), the authors developed two new "converse" tools. Think of these as ways to prove a puzzle is unsolvable without actually solving it.

Interactive Fano's Method: Imagine you have a bag of many different possible worlds (models). To win, you must figure out which world you are in. This method proves that if the worlds are too similar (hard to tell apart), you will inevitably make mistakes, and it calculates exactly how big those mistakes will be with high confidence.
Interactive Le Cam's Method: This is a simpler version using just two worlds. It's like a "Heads or Tails" test. If the two worlds are so similar that you can't tell them apart even after many tries, you are forced to guess, and the math tells you exactly how often you will be wrong.

4. The Twist: Privacy Constraints

The paper adds a layer of Privacy.

The Analogy: Imagine you are a doctor trying to estimate the average blood pressure of patients. But, due to privacy laws, you cannot see the raw numbers. Instead, a "privacy machine" adds random static (noise) to every number before showing it to you.
The Challenge: This noise makes it harder to distinguish between patients. The authors show that you can treat this privacy constraint as simply limiting the types of strategies the decision-maker is allowed to use.
The Result: They found a "Variance Inflation Factor." Think of it like a magnifying glass for error. The privacy noise doesn't just add a little bit of error; it inflates the difficulty of the problem. The math shows exactly how much the "worst-case" error grows based on how strict the privacy rules are.

5. The Findings: What They Discovered

The authors applied their new toolkit to three specific scenarios:

Estimating a Mean (Gaussian Mean Estimation):
- Without Privacy: If you want to be 99% sure your estimate is close, the error scales with $\log(1/\delta) / n$ (where $n$ is the number of samples).
- With Privacy: The error is multiplied by a factor representing the "noise floor" created by the privacy mechanism. The stricter the privacy, the larger the noise, and the bigger the potential error.
Two-Armed Bandits (Choosing between two options):
- Without Privacy: The error scales with $\sqrt{T \log(1/\delta)}$ (where $T$ is the number of rounds).
- With Privacy: Again, the privacy noise inflates this error. The math shows that the "cost" of privacy is a direct multiplication of the difficulty.
K-Armed Bandits (Choosing between many options):
- They used their "Fano" tool to show that when you have many options (K arms), the difficulty scales with $\sqrt{K \cdot T \cdot \log(1/\delta)}$ . This captures the extra "exploration cost" of having to test many different options before finding the best one.

Summary

In short, this paper builds a new safety net for decision-making algorithms.

It moves away from "average" performance to "guaranteed safety" (what is the worst I can do with 99% certainty?).
It provides a unified way to calculate these guarantees for interactive games (where you learn as you go).
It proves that privacy acts like a "noise amplifier," mathematically quantifying exactly how much harder it becomes to make safe, high-confidence decisions when you are forced to hide the raw data.

The authors didn't just say "privacy makes things harder"; they gave a precise formula for how much harder, specifically for the rare, high-stakes failures that average statistics miss.

Technical Summary: Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

Problem Statement
Classical minimax risk and regret are expectation-based criteria that characterize the worst-case expected loss but fail to capture rare, high-consequence failures. This limitation is critical in safety-critical or reliability-sensitive settings where two algorithms may share the same expected loss but exhibit vastly different tail behaviors. While recent work has established high-probability minimax quantile lower bounds for non-interactive estimation, and separate frameworks exist for interactive statistical decision making (ISDM) based on expected risk, a unified theory for $\delta$ -explicit minimax quantiles in interactive settings has remained open. Furthermore, the impact of privacy constraints—specifically bounded mutual information (MI)—on these high-confidence guarantees in interactive problems has not been systematically addressed.

Methodology
The paper develops a theoretical framework within the Interactive Statistical Decision Making (ISDM) paradigm, which unifies passive estimation and interactive problems like bandits and reinforcement learning. The methodology proceeds in three stages:

Structural Relations: The authors establish connections between minimax quantiles and classical minimax risk. They define both "strict" minimax quantiles (based on the event $\{L > r\}$ ) and "lower" minimax quantiles. They prove that outside a countable set of confidence levels, these two definitions are equivalent, and they provide a conversion from quantile bounds to expectation bounds.
Converse Tools for ISDM: To derive lower bounds, the paper introduces two high-probability interactive converse techniques:
- Interactive Fano's Method: A prior-based approach suitable for large model classes, yielding explicit lower bounds on the lower minimax quantile.
- Interactive Le Cam's Method: A two-point reduction approach that provides bounds based on the distinguishability (Total Variation or KL divergence) between two models under the induced interactive laws.
Privacy Integration: The paper models MI-private problems as ISDM instances where the class of admissible decision rules is restricted to those satisfying a bounded mutual information constraint ( $I(S; Y) \le \epsilon$ ). For coordinatewise Gaussian privatization, they derive a "two-point template" that isolates the privacy effect as a variance-inflation factor. This allows the application of the general ISDM converse tools to private settings by analyzing the induced output laws of the privatized mechanisms.

Key Contributions

$\delta$ -Explicit Minimax Quantile Theory for ISDM: The paper provides the first systematic development of strict minimax quantile lower bounds for interactive problems, bridging the gap between non-interactive quantile theory and interactive expectation-based theory.
High-Probability Interactive Converse Tools: The derivation of high-probability versions of Fano's and Le Cam's methods specifically tailored for ISDM, providing explicit dependence on the confidence level $\delta$ .
Unified Privacy Framework: A formulation of MI-private decision problems as constrained ISDM instances. This approach separates the generic minimax-quantile arguments from the specific verification of privacy-induced divergence constraints.
Coordinatewise Gaussian Privatization Template: A specific derivation for Gaussian privatization that quantifies the privacy penalty as a multiplicative variance inflation factor, $1 + \sigma^2_{\min}(\epsilon, d)$ , where $\sigma^2_{\min}$ is the minimum noise variance required to satisfy the MI budget.

Results
The authors instantiate their theory across five specific examples, deriving explicit lower bounds that depend on the confidence level $\delta$ , the sample size/horizon, and the privacy budget $\epsilon$ :

Gaussian Mean Estimation (Classical): Recovers the known scaling of $\frac{\log(1/\delta)}{n}$ for squared-error loss using the interactive Le Cam method.
Two-Armed Gaussian Bandits (Classical): Derives a lower bound scaling as $\sqrt{T \log(1/\delta)}$ (truncated at $T$ ), demonstrating the high-confidence regret rate for bounded-mean bandits.
K-Armed Gaussian Bandits (Classical): Uses the interactive Fano method to show that the lower bound scales as $\sqrt{KT \log(1/\delta)}$ , capturing the exploration cost over $K$ arms.
Gaussian Mean Estimation (Private): For coordinatewise Gaussian MI privacy, the lower bound becomes $\frac{1 + \sigma^2_{\min}(\epsilon, n)}{n} \log(1/\delta)$ . The privacy constraint inflates the variance, worsening the bound as $\epsilon$ decreases.
Two-Armed Gaussian Bandits (Private): The lower bound scales as $\sqrt{(1 + \sigma^2_{\min}(\epsilon, T)) T \log(1/\delta)}$ . Similar to the estimation case, the privacy mechanism introduces a variance inflation factor that degrades the high-confidence performance.

Significance and Claims
The paper claims to provide a unifying perspective where tail-sensitive minimax lower bounds for estimation, interaction, and privacy can all be developed within a common ISDM framework. By treating privacy as a restriction on the admissible decision class, the authors demonstrate that the complex machinery of information-theoretic lower bounds (Fano and Le Cam) transfers directly to private settings without requiring a fundamentally new theoretical apparatus.

The results are significant because they move beyond expected risk to provide explicit guarantees on the probability of failure (controlled by $\delta$ ). The paper explicitly notes that while the derived lower bounds are tight for classical Gaussian mean estimation, the matching upper bounds for private bandits under MI constraints are not yet fully established in the literature, positioning their work as a foundational lower-bound theory for future algorithmic development. The framework is presented as a tool to systematically analyze how privacy constraints alter the fundamental difficulty of interactive decision problems in terms of high-confidence performance.