Surprises in Proper Positive-Only Learning

cPU: Consistent Risk Estimator for Positive-Unlabeled Learning.

As one of the classical strategies for positive-unlabeled (PU) learning, the cost-sensitive methods achieve binary classification by minimizing the overall risk. To achieve this goal, the class prior is usually exploited to guide model learning in many state-of-the-art cost-sensitive approaches. However, how to effectively mine the underlying supervision information using the class prior remains a major challenging problem. It is known that the distribution of positive and negative samples is fixed in unlabeled samples when the class prior is available. Based on this knowledge, we derive a novel supervision formulation from a risk perspective: if the class prior is known, the ratio between the positive risk distribution of negative samples and the negative risk distribution of positive samples converges to a fixed value in unlabeled samples. By fully exploiting this brand-new constraint, we construct a consistent risk estimator to impose consistency between the negative expected risk of the positive samples and the positive expected risk of the negative samples. Moreover, we introduce Mixup regularization to mitigate the confirmation bias of the learned model, and meanwhile employ the entropy minimization technique to improve the separability of samples, which can further enhance classification performance. Experimental results on four benchmark datasets demonstrate the advantage of our model over several baseline methods. The code is available at https://github.com/yunbao520/cPU.

Bagging Robustly Learns VC Classes with Linear Sample Complexity

It is proved that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019).

Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning

ADS-C: Antidistillation Sampling for Classification

Knowledge distillation enables an adversary to replicate a proprietary classifier by querying its prediction interface and training a surrogate on the returned probability vectors. Antidistillation sampling, proposed for large language models, counters this threat with an input-dependent, gradient-directed perturbation of the served distribution; its transfer to classification has not been studied. Adapting the defense to classification, we show its behavior is governed by the distribution of the teacher's per-input confidence margins. Because well-trained classifiers are severely overconfident, the direct transfer exhibits an inert window: below a closed-form-predictable threshold, it affects neither attacker nor defender; beyond it, the defense undergoes a phase transition and degrades the teacher faster than the attacker's student. Temperature softening rescales the transition in closed form, and every temperature configuration lies on the same unfavorable trade-off curve. Our method, ADS-C, composes the perturbation under a closed-form, per-input margin budget that provably preserves every served top-1 prediction, so the defended teacher's accuracy equals the undefended teacher's identically. Under this guarantee the distilled student still loses 17.4 percentage points on CIFAR-100, 29.6 on CIFAR-10, and 13.3 on Tiny-ImageNet; matching this degradation with the unmodified defense costs 27.5, 32.9, and 22.2 points of teacher accuracy. Because served labels are unchanged, a hard-label attacker gains nothing, while the defended soft output trains a student up to 29.7 points below that floor: the incentive to distill served probabilities is not merely removed but reversed. To our knowledge, ADS-C is the first antidistillation defense for classification whose utility cost is exactly zero.

Quasibinary Classifier for Images with Zero and Multiple Labels

Optimal Rates for Learning with Monotone Adversaries

This model shows that adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning.