Error-Tolerant E-Discovery Protocols
Open Access
- 12 March 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Abstract
We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) in the context of electronic discovery (e-discovery). Based on a request for production from the requesting party, the responding party is required to provide documents that are responsive to the request except for those that are legally privileged1. Our goal is to find a protocol that verifies that the responding party sends almost all responsive documents while minimizing the disclosure of non-responsive documents. We provide protocols in the challenging non-realizable setting, where the instance may not be perfectly separated by a linear classifier. We demonstrate empirically that our protocol successfully manages to find almost all relevant documents, while incurring only a small disclosure of non-responsive documents. We complement this with a theoretical analysis of our protocol in the single-dimensional setting, and other experiments on simulated data which suggest that the non-responsive disclosure incurred by our protocol may be unavoidable.Keywords
All Related Versions
Funding Information
- NSF (National Science Foundation) (ECCS 221697)
- NSF (CCF 1934931)
This publication has 14 references indexed in Scilit:
- Solving tall dense linear programs in nearly linear time2020
- Towards Question-based High-recall Information RetrievalACM Transactions on Information Systems, 2020
- The Power of Localization for Efficiently Learning Linear Separators with NoiseJournal of the ACM, 2017
- Evaluation of machine-learning protocols for technology-assisted review in electronic discovery2014
- Hardness of Learning Halfspaces with NoiseSIAM Journal on Computing, 2009
- Agnostically Learning HalfspacesSIAM Journal on Computing, 2008
- More output-sensitive geometric algorithms2002
- Toward efficient agnostic learning1992
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- How to play ANY mental game1987