CS Paper Radar

Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning

Shaddin Dughmi, Alireza F. Pour

cs.LG stat.ML ·submitted 2026-09-09 22:45 UTC · v2

Abstract

We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-fixed error guarantee soundly certifiable from unlabeled data. They showed that the One-Inclusion Graph (OIG) learner is relatively smart with a quadratic sample-complexity blowup, and that no relatively smart learner can do better, leaving open whether ERM or another natural or tractable learner achieves comparable guarantees. They also left open whether the blowup can be restricted to unlabeled data. Our firs results shows that ERM---and in fact any proper consistent learner---is relatively smart for binary classification in the distribution-free setting. We show that a small certifiable error with $m$ samples implies a similarly small error on the uniform distribution over a random sample of size $O(m^2)$, yielding a cover of size at most $2^{m+1}$ on that sample. This suffices to control the error of proper consistent learners with $O(m^2)$ samples. We then show that semi-supervised relatively smart learning is information-theoretically possible with a quadratic blowup only in unlabeled sample complexity and no blowup in labeled sample complexity. The learner uses a natural generalization of OIG to a leave-most-out transductive problem, where labels of part of a finite pool are revealed and the remaining labels are predicted. Finally, this label efficiency comes at a cost in simplicity and tractability. If the hypothesis class is accessed only through an agnostic ERM oracle, any semi-supervised relatively smart learner with substantially sub-quadratic labeled-sample blowup requires super-polynomially many oracle calls. This holds even when the marginal is given explicitly, and thus also yields an intractability result for distribution-fixed learning that may be of independent interest.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Robust Learning at the Information-Theoretic Limit

cs.DS cs.LGstat.ML ·2026-09-15 ·Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
similarity 0.68
Abstract · Corrected the arXiv abstract to match the pdf

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $η+ \varepsilon$ where $η$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2η+ \varepsilon$. Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). Here we resolve this problem and give such an algorithm. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits low-degree polynomial approximators with respect to hypercontractive distributions. This captures basic settings including halfspaces with respect to Gaussian marginals. Our techniques make new connections to various types of online convex optimization algorithms. As a surprising consequence, we show that efficient SQ learnability in the agnostic setting implies efficient learning with contamination (with respect to Gaussians or uniform over the hypercube).

0.37

Agnostic Marginal-Nonuniform Learning

cs.LG ·2026-11-09 ·Tanmay Devale, Steve Hanneke, Amirreza Shaeiri
similarity 0.65
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 $\tfrac{1}{\sqrt{n}}$ for every class $\mathcal{H}$ with finite $\mathrm{VC}(\mathcal{H})$ and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of $\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+λ)$ times the error of the best concept for a fixed $λ\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^{-n}$ arise precisely when the class is finite; linear rates of the form $\tfrac{1}{n}$ arise when the class is infinite but $\mathrm{VC}(\mathcal{H})$ is finite; and arbitrarily slow rates occur when $\mathrm{VC}(\mathcal{H})=\infty$. We also obtain the optimal fine-grained rate of $\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}$, where $\mathrm{uVCE}(\mathcal{H})$ is a recently introduced combinatorial complexity dimension called the uncentered $\mathrm{VC}$-eluder dimension.

0.06

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning

cs.LG stat.ML ·2026-08-27 ·Julian Asilis, Shaddin Dughmi, Vatsal Sharan, Alec Sun, Shang-Hua Teng +1 more
similarity 0.63
Abstract · 62 pages

Two of the most fundamental questions in statistical learning theory are the following: which prediction problems are learnable, and how should they be learned? For the former, elegant answers often take the form of combinatorial dimensions. The latter question, however, has proved considerably more elusive: all known general-purpose multiclass learners rely on intricate orientations of exponentially large one-inclusion structures, and familiar algorithmic principles such as proper learning and regularization remain poorly understood. Motivated by prior work, we ask whether learning reduces to proper learning---possibly over a larger hypothesis class---and whether proper or improper multiclass learning can ultimately be captured by suitable regularizers. Our primary results answer both questions negatively, resolving three open problems from prior work. First, we exhibit a learnable multiclass problem that cannot be embedded in any properly learnable class, meaning learning cannot be reduced to proper learning by enlarging the hypothesis class. Second, we demonstrate that proper learning can require training error and characterize this phenomenon precisely: every properly learnable class admits a proper learner making $o(m)$ errors on samples of size $m$, but every prescribed sublinear scale $a_m=o(m)$ is necessary for some properly learnable problem. Third, regularization is not a general learner: we exhibit a properly learnable class that cannot be learned by any Structural Risk Minimization (SRM) learner, and a learnable class that cannot be learned by any local regularizer. We complement these impossibility results with a positive theory that gives two sufficient conditions for SRM learnability and characterizes SRM representability through integrability of revealed preferences.

0.40

Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness

cs.LG stat.ML ·2026-10-18 ·Guangjian Zhang
theoryhot direction similarity 0.62
Abstract · 68 pages

Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity $Θ(((\log M)^2/ρ^2+\log(1/δ))/\varepsilon)$ for classes of cardinality at most $M$, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general $ρ^{-1}$ dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses $O(((1+\log M)^{3/2}/ρ+\log(1/δ))/\varepsilon)$ samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of $d$ finite threshold chains of length $k$, we determine the exact rate $Θ((dk\log(1+\sqrt d/(kρ))+\log(1/δ))/\varepsilon)$. We also characterize deterministic learning, the very-small-$ρ$ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent $3/2$ independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.

0.30

Sequential Probability Assignment against Smoothed Adversaries with Unknown Base Measure

cs.LG stat.ML ·2026-11-19 ·Ziyi Liu, Daniel M. Roy
publishedtheory similarity 0.61
Abstract · NeurIPS 2026

Smoothed online learning has recently been studied as a way to bypass hardness results for the fully adversarial setting, which can be overly pessimistic. In this framework, the adversary is constrained to generate contexts from distributions having a bounded density with respect to some fixed base measure $μ$. Prior work makes the strong assumption that $μ$ is known to the learner, with notable exceptions including Block et al. (2024) and Blanchard (2025). In this paper, we study sequential probability assignment (a.k.a., online learning with log loss) with smooth, well-specified data in the more general setting where $μ$ is \emph{unknown}, without the Lipschitz condition imposed in the work of Block et al. (2024) and Blanchard (2025). We prove regret upper bounds against both adaptive and oblivious smoothed adversaries: the adaptive bound is controlled by empirical $\ell_\infty$ Hellinger entropy, while the oblivious bound improves this dependence to empirical $\ell_2$ Hellinger entropy, the notion that has been shown to characterize the complexity of learning with i.i.d. data (Bilodeau et al., 2023). Both bounds are obtained through algorithms based on truncated empirical Hellinger covers. We complement these results with a general lower bound, showing that our upper bounds are essentially tight for some natural classes, which implies a separation in the difficulty of smoothed online learning between regimes where $μ$ is known and where it is unknown.

0.15

On the Computational Tractability of Robust Bandits

cs.LG ·2026-10-06 ·Vanessa Kosoy, Vinayak Pathak
similarity 0.61
Abstract

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a $Θ(\sqrt{T})$ regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with $\tilde{O}(\sqrt{T})$ regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.

0.20

Combinatorial Characterizations of the Learnability of Conditional Distributions

cs.LG stat.ML ·2026-10-22 ·Mihir Dhanakshirur, Ambuj Tewari
similarity 0.61
Abstract

We study the PAC-learnability of function classes that map inputs to probability distributions over a finite space. The learner observes i.i.d. input-label pairs, with each label sampled from the conditional distribution of an unknown target hypothesis in the class. We measure learning through excess risk under a bounded proper loss that satisfies two mild assumptions. We introduce the \textbf{fat$_γ$Natarajan dimension}, which generalizes both fat$_γ$ and Natarajan dimension, and prove that its finiteness at every positive scale is necessary and sufficient for learnability. We also introduce a \textbf{fat$_γ$Graph} dimension extending the classical \gra dimension and establish inequalities comparing the two dimensions at different scales, leading to an equivalent characterization of learnability. Finally, we show that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.

0.15

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

cs.LG ·2026-10-18 ·Guangjian Zhang
theory similarity 0.60
Abstract · 92 pages

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

0.30