Research map / Adversarial robustness and security / Certified and empirical robustness

On the Adversarial Robustness of Benjamini Hochberg

NeurIPS 2024 · Adversarial robustness and security › Certified and empirical robustness · approach: Theory of adversarial risk · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows the Benjamini-Hochberg procedure can be broken by an adversary who perturbs very few test p-values (even one), via INCREASE-c and MOVE-1 algorithms, with non-asymptotic lower bounds on the induced FDR increase.

Problem

Whether the false detection rate control of the Benjamini-Hochberg procedure remains valid when an adversary can perturb a small number of test p-values before BH is applied.

Approach

Reframes BH as a balls-into-bins process and uses a stopping-time argument (optional stopping on a martingale) plus generalized ballot theorems to design simple adversarial perturbations (INCREASE-c, and an optimal MOVE-1 for c=1) that inflate the expected FDR, with non-asymptotic lower bounds.

Key results

• On the credit card fraud task with BH at q=0.10, expected FDP rose from 0.09 to 0.23 after a 10-p-value INCREASE-10 perturbation and to 0.31 with c=20.
• For iid z-score p-values with mu_1=0, a single perturbation (MOVE-1 / INCREASE-1) raised expected FDR to about 0.99 at q=0.10, N=1000.
• Non-asymptotic lower bound L_c on the adversarial FDR increase Delta_c is derived via ballot theorem and KL/Pinsker arguments for low sub-uniformity alternatives.

Measured effects reported in the paper

Surprising findings

• BH's FDR control can be broken by perturbing as few as one p-value when alternatives are close to the null.
• BH is robust when alternatives are far from the null, since the adversary must then expand the rejection region substantially.

Limitations

• Adversary assumed omniscient (knows null/alternative labels); oblivious case handled only approximately.
• INCREASE-c is suboptimal in general; only MOVE-1 is optimal and only for c=1.
• Robustness depends strongly on alternative separation; lower bounds are conservative and analysis focuses on i.i.d. and PRDS settings.

Experimental setup

Datasets: Credit Card Fraud Detection (Kaggle) synthetic z-score p-values

Benchmarks: Credit Card Fraud Detection (Kaggle) synthetic z-score simulations

Metrics: false detection proportion (FDP) false detection rate (FDR) expected rejection count

Baselines: MOVE-1

Builds on: Benjamini-Hochberg procedure PRDS dependence conformal p-values isolation forest

Closest papers by meaning

• Certified Adversarial Robustness with Additive Noise (NeurIPS 2019 · similarity 0.86)
• Certifying Some Distributional Robustness with Principled Adversarial Training (ICLR 2018 · similarity 0.86)
• Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks (ICML 2020 · similarity 0.86)
• Adversarial Robustness Against the Union of Multiple Perturbation Models (ICML 2020 · similarity 0.85)
• Precise Accuracy / Robustness Tradeoffs in Regression: Case of General Norms (ICML 2024 · similarity 0.85)
• Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.85)