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

Nov 6, 2026

Marginal-Nonuniform Multiclass Learning

We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest.
Nov 9, 2026

Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class CC. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings. Prior work showed that, when CC has finite diameter KK and VC dimension dd, deterministic labels can improve the sample complexity upper bound from the classical agnostic guarantee O(d/ε2)O(d/\varepsilon^2) to O~(K/ε)\widetilde{O}(K/\varepsilon), but left a large gap between upper and lower bounds. Our main result sharpens this picture. We prove that every class of VC dimension dd and finite diameter KK is learnable with sample complexity O~(K1/3 d2/3ε)\widetilde{O}\left( \frac{K^{1/3} \, d^{2/3}}{\varepsilon} \right), and we construct classes for which this bound is tight up to logarithmic factors. We also study the online analogue of this problem and show that the minimax regret is again partly controlled by the diameter of the class. Technically, our upper bounds are obtained via memorization-based learning algorithms that exploit the deterministic label structure.
Aug 6, 2026

An Optimal Agnostic PAC Algorithm

Let H⊆{−1,+1}XH\subseteq\{-1,+1\}^X be a class of finite VC dimension d≥1d\ge1. Writing LL for the binary risk and L∗=min⁡h∈HL(h)L^*=\min_{h\in H}L(h), we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size nn, for every 0<δ≤1/20<δ\le 1/2, with probability at least 1−δ1-δ, L(h^)≤L∗+7⋅108(L∗(d+log⁡(1/δ))n+d+log⁡(1/δ)n).L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed L∗L^*, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].