Distribution-Free Sequential Prediction with Abstentions
This work addresses a distribution-free learning challenge for sequential prediction with abstentions, bridging stochastic and adversarial settings, but it is incremental as it builds on prior results by removing the assumption of known distribution.
The paper tackles the problem of sequential prediction with abstentions in a semi-adversarial setting where an adversary injects corrupted instances, and the learner can abstain without penalty on corrupted instances. It proposes an algorithm, AbstainBoost, that achieves sublinear error for general VC classes without prior knowledge of the clean data distribution, with results including lower bounds showing a polynomial trade-off between misclassification error and erroneous abstentions.
We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d.\ instances, but at each round, the learner may also \emph{abstain} from making a prediction without incurring any penalty if the instance was indeed corrupted. This semi-adversarial setting naturally sits between the classical stochastic case with i.i.d.\ instances for which function classes with finite VC dimension are learnable; and the adversarial case with arbitrary instances, known to be significantly more restrictive. For this problem, Goel et al. (2023) showed that, if the learner knows the distribution $μ$ of clean samples in advance, learning can be achieved for all VC classes without restrictions on adversary corruptions. This is, however, a strong assumption in both theory and practice: a natural question is whether similar learning guarantees can be achieved without prior distributional knowledge, as is standard in classical learning frameworks (e.g., PAC learning or asymptotic consistency) and other non-i.i.d.\ models (e.g., smoothed online learning). We therefore focus on the distribution-free setting where $μ$ is \emph{unknown} and propose an algorithm \textsc{AbstainBoost} based on a boosting procedure of weak learners, which guarantees sublinear error for general VC classes in \emph{distribution-free} abstention learning for oblivious adversaries. These algorithms also enjoy similar guarantees for adaptive adversaries, for structured function classes including linear classifiers. These results are complemented with corresponding lower bounds, which reveal an interesting polynomial trade-off between misclassification error and number of erroneous abstentions.