cs.LGNov 9, 2026

Agnostic Marginal-Nonuniform Learning

Authors: Tanmay Devale, Steve Hanneke, Amirreza Shaeiri

Organizations: Department of Computer Science, Purdue University

Abstract

We study the problem of binary classification in the marginal-nonuniform learning framework in the agnostic setting. In this model, the constants in the learning rate may depend on the marginal distribution of the unlabeled data, but the guarantee must hold uniformly over all conditional distributions of the labels. We also study fine-grained rates. We consider two criteria. (1) The standard agnostic setting, where the learner competes with the best concept in the class. In this setting, an immediate consequence of standard agnostic PAC learning results gives us the optimal rate of 1n\tfrac{1}{\sqrt{n}} for every class H\mathcal{H} with finite VC(H)\mathrm{VC}(\mathcal{H}) and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of VC(H)n\sqrt{\tfrac{\mathrm{VC}(\mathcal{H})}{n}}. Therefore, the dependence on the marginal distribution does not help, which is in contrast to the realizable setting. (2) In the relaxed agnostic setting, where the learner competes with (1+λ)(1+λ) times the error of the best concept for a fixed λ∈(0,1]λ\in (0,1], the picture from the realizable setting reappears. We obtain a trichotomy of the achievable optimal rates: exponential rates of the form e−ne^{-n} arise precisely when the class is finite; linear rates of the form 1n\tfrac{1}{n} arise when the class is infinite but VC(H)\mathrm{VC}(\mathcal{H}) is finite; and arbitrarily slow rates occur when VC(H)=∞\mathrm{VC}(\mathcal{H})=\infty. We also obtain the optimal fine-grained rate of uVCE(H)λn\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}, where uVCE(H)\mathrm{uVCE}(\mathcal{H}) is a recently introduced combinatorial complexity dimension called the uncentered VC\mathrm{VC}-eluder dimension.

Explore similar work

CardsList
  1. Marginal-Nonuniform Multiclass Learning

    Nov 6, 2026Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri +1Statistical Learning TheoryMulticlass Classification

  2. Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

    Nov 9, 2026Shai Ben-David, Steve Hanneke, Farnam Mansouri +1Agnostic LearningPAC Learning

  3. An Optimal Agnostic PAC Algorithm

    Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyPAC LearningStatistical Learning Theory