Lune

KDD2022Top-tier venue

PAC-Wrap: Semi-Supervised PAC Anomaly Detection

Shuo Li, Xiayan Ji, Edgar Dobriban, Oleg Sokolsky, Insup Lee

Abstract

Anomaly detection is essential for preventing hazardous outcomes for safety-critical applications like autonomous driving. Given their safety-criticality, these applications benefit from provable bounds on various errors in anomaly detection. To achieve this goal in the semi-supervised setting, we propose to provide Probably Approximately Correct (PAC) guarantees on the false negative and false positive detection rates for anomaly detection algorithms. Our method (PAC-Wrap) can wrap around virtually any existing semisupervised and unsupervised anomaly detection method, endowing it with rigorous guarantees. Our experiments with various anomaly detectors and datasets indicate that PAC-Wrap is broadly effective.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Conformal Structured Prediction cites PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction
  • Conformal Information Pursuit for Interactively Guiding Large Language Models cites iDECODe: In-Distribution Equivariance for Conformal Out-of-Distribution Detection
  • Conformal Information Pursuit for Interactively Guiding Large Language Models cites PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction
  • Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization cites iDECODe: In-Distribution Equivariance for Conformal Out-of-Distribution Detection
  • Unsupervised Anomaly Detection with Rejection cites Deep Semi-Supervised Anomaly Detection
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Unsupervised Anomaly Detection with RejectionLorenzo Perini, Jesse DavisNeurIPS 2023 · 17 citations
  2. Probabilistic Stability Guarantees for Feature AttributionsHelen Jin, Anton Xue, Weiqiu You, Surbhi Goel et al.NeurIPS 2025 · 12 citations
  3. Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio RegularizationSunay Joshi, Shayan Kiyani, George J. Pappas, Edgar Dobriban et al.NeurIPS 2025 · 12 citations
  4. Conformal Information Pursuit for Interactively Guiding Large Language ModelsKwan Ho Ryan Chan, Yuyan Ge, Edgar Dobriban, Hamed Hassani et al.NeurIPS 2025 · 9 citations
  5. Conformal Structured PredictionBotong Zhang, Shuo Li, Osbert BastaniICLR 2025

Builds on4

  1. Deep Semi-Supervised Anomaly DetectionLukas Ruff, Robert A. Vandermeulen, Nico Görnitz, Alexander Binder et al.ICLR 2020 · 678 citations
  2. Conformal prediction interval for dynamic time-seriesChen Xu, Yao XieICML 2021 · 174 citations
  3. PAC Confidence Sets for Deep Neural Networks via Calibrated PredictionSangdon Park, Osbert Bastani, Nikolai Matni, Insup LeeICLR 2020 · 77 citations
  4. iDECODe: In-Distribution Equivariance for Conformal Out-of-Distribution DetectionRamneet Kaur, Susmit Jha, Anirban Roy, Sangdon Park et al.AAAI 2022 · 53 citations

Related papers

  1. Is Out-of-Distribution Detection Learnable?Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong et al.NeurIPS 2022 · 188 citations
  2. Towards neural networks that provably know when they don't knowAlexander Meinke, Matthias HeinICLR 2020 · 151 citations
  3. AutoUAD: Hyper-parameter Optimization for Unsupervised Anomaly DetectionWei Dai, Jicong FanICLR 2025
  4. Scaling Out-of-Distribution Detection for Real-World SettingsDan Hendrycks, Steven Basart, Mantas Mazeika, Andy Zou et al.ICML 2022 · 653 citations
  5. Lifelong Anomaly Detection Through UnlearningMin Du, Zhi Chen, Chang Liu, Rajvardhan Oak et al.CCS 2019 · 145 citations
Dusk over the sea between two cliffs drawn in fine vertical lines