Adversarial Resilience in Sequential Prediction via Abstention
Authors: Surbhi Goel, Steve Hanneke, Shay Moran, Abhishek Shetty
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algorithms designed to handle purely stochastic data tend to fail in the presence of such adversarial examples, often leading to erroneous predictions. This is undesirable in many high-stakes applications such as medical recommendations, where abstaining from predictions on adversarial examples is preferable to misclassification. On the other hand, assuming fully adversarial data leads to very pessimistic bounds that are often vacuous in practice. To move away from these pessimistic guarantees, we propose a new model of sequential prediction that sits between the purely stochastic and fully adversarial settings by allowing the learner to abstain from making a prediction at no cost on adversarial examples, thereby asking the learner to make predictions with certainty. Assuming access to the marginal distribution on the non-adversarial examples, we design a learner whose error scales with the VC dimension (mirroring the stochastic setting) of the hypothesis class, as opposed to the Littlestone dimension which characterizes the fully adversarial setting. Furthermore, we design learners for VC dimension 1 classes and the class of axis-aligned rectangles, which work even in the absence of access to the marginal distribution. Our key technical contribution is a novel measure for quantifying uncertainty for learning VC classes, which may be of independent interest. |
| Researcher Affiliation | Collaboration | Surbhi Goel University of Pennsylvania surbhig@cis.upenn.edu Steve Hanneke Purdue University steve.hanneke@gmail.com Shay Moran Technion and Google Research, Israel smoran@technion.ac.il Abhishek Shetty University of California, Berkeley shetty@berkeley.edu |
| Pseudocode | Yes | Algorithm 1: Level-based learning for Prediction with Abstension, Algorithm 2: Structure-based learning for Prediction with Abstention for Unknown Distribution, Algorithm 3: Structure-based learning for Axis-aligned Rectangles |
| Open Source Code | No | The paper is theoretical and does not mention providing any source code. |
| Open Datasets | No | The paper is theoretical and discusses learning in a 'stochastic setting where the data is assumed to be identically and independently distributed (i.i.d) according to some fixed (perhaps unknown) distribution', but does not use or provide access information for any specific real-world or synthetic datasets for empirical training. |
| Dataset Splits | No | The paper is theoretical and does not mention training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies or version numbers. |
| Experiment Setup | No | The paper defines the theoretical models and algorithms (e.g., 'Protocol 1 Sequential Prediction with Adversarial Injections and Abstentions'), but does not describe an empirical experimental setup with hyperparameters or training configurations. |