Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

2026-06-22 · Source: Takara TLDR - Daily AI Papers · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Cybersecurity & Data Privacy, Mathematics & Computational Sciences · Depth: Expert, medium

Summary

A δ-explicit minimax-quantile theory is developed for interactive statistical decision making (ISDM), addressing the inability of expectation-based criteria like minimax risk to capture rare but consequential failures. The theory establishes structural relations between minimax quantiles and risk, including a quantile-to-expectation conversion. It introduces high-probability interactive Fano's and Le Cam's methods as converse tools for ISDM, integrating mutual-information (MI) privacy by restricting the admissible decision class. For coordinatewise Gaussian privatization, a two-point template is derived to isolate privacy-induced variance inflation, applied to Gaussian mean estimation and two-armed Gaussian bandits. The study provides a minimax quantile lower bound for the K-armed Gaussian bandit problem, showing the interactive Fano method captures exploration costs. These bounds are explicit in confidence level δ and privacy budget, yielding log(1/δ)/n for Gaussian mean estimation and √Tlog(1/δ) or √KTlog(1/δ)-type scaling for Gaussian bandits, with privacy as a Gaussian variance-inflation factor.

Key takeaway

For AI Scientists designing robust and private interactive statistical decision-making systems, this work provides critical theoretical lower bounds. You should consider the δ-explicit minimax-quantile theory to account for rare but consequential failures, moving beyond expectation-based risk metrics. Incorporate the derived Gaussian variance-inflation factor when implementing coordinatewise Gaussian privatization, and leverage the specific scaling laws like log(1/δ)/n for Gaussian mean estimation to better understand privacy-utility trade-offs in your models.

Key insights

The paper develops a minimax-quantile theory for ISDM that accounts for rare failures and integrates MI privacy.

Principles

• Minimax quantiles capture rare, consequential failures.
• MI privacy can be integrated via decision class restriction.
• Interactive Fano method quantifies exploration costs.

Method

The method involves deriving a two-point template for coordinatewise Gaussian privatization to isolate privacy-induced variance inflation, then instantiating it for Gaussian mean estimation and bandit problems.

In practice

• Apply δ-explicit bounds for high-stakes ISDM.
• Use Gaussian variance-inflation factor for private problems.
• Consider log(1/δ)/n scaling for private mean estimation.

Topics

• Minimax Quantile Theory
• Interactive Statistical Decision Making
• Privacy-Preserving AI
• Gaussian Bandits
• Lower Bounds
• Mutual Information Privacy

Best for: Research Scientist, AI Scientist, AI Security Engineer, AI Ethicist

Related on AIssential

• Differentially Private Bootstrap: New Privacy Analysis and Inference Strategies — A new differentially private bootstrap method enables robust statistical inference with strong privacy guarantees.
• Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation — The paper provides information-theoretic lower bounds for bit-constrained stochastic optimization, linking it to compressed Gaussian mean estimation.
• Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails — Optimal pure ε-DP heavy-tailed SCO rates are achieved via Lipschitz extensions and double output perturbation.
• On Stability and Decomposition of Sample Quantiles under Heavy-Tailed Distributions — This paper addresses the instability of sample quantiles, particularly Value-at-Risk (VaR), when estimated parameters like projection direction and quantile threshold are derived from heavy-tailed financial returns.
• Federated Gaussian Process Learning via Pseudo-Representations for Large-Scale Multi-Robot Systems — pxpGP enables scalable, privacy-preserving Gaussian Process learning for large multi-robot systems via pseudo-representations and optimized ADMM.
• Minimax Optimal Two-Sample Testing under Local Differential Privacy — Minimax optimal two-sample tests under LDP are developed for multinomial and continuous data.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Takara TLDR - Daily AI Papers.