cs.LGNov 10, 2026

Learning from First Discrepancies with Joint Reset and Pilot Guarantees

Authors: Michal Čertík

Organizations: The World bank Group

Abstract

A run that stops at its first wrong decision shows the queries and their correct labels up to and including that decision, and nothing after it. We study how many such runs are needed for learning. Each run tests a hypothesis, the pilot, chosen beforehand from a fixed binary class of VC dimension at most dd, on a fresh record of at most DD queries drawn from one unknown distribution that does not depend on the pilot. The terminal information of a record is shown only if the pilot makes no discrepancy, and a bounded loss, fixed in advance, is attached to the position where a hypothesis stops. If the discrepancy probabilities of members of the class have infimum at most ff and their risks have infimum at most rr, one learner uses O~((d+1)[D(f+ε)+r]/ε2)\widetilde O((d+1)[D(f+\varepsilon)+r]/\varepsilon^2) runs and O~(D(1+f/ε))\widetilde O(D(1+f/\varepsilon)) distinct pilots on every history. It returns a member of the class and an interval of width at most ε\varepsilon containing, with probability at least 1−δ1-δ, both the output's risk and the optimal risk. We also treat unknown ceilings and expected costs. Lower bounds for finite classes show that each order is necessary in the worst case, possibly on different instances, at positive dimension, small accuracy and fixed confidence. The learner enumerates label patterns of the class on displayed queries, possibly in exponential time; the results, under standard measurability conditions, concern statistical resources only. The proof combines a gain computable from stopped displays, exponential weights, a sparse depth-robust graph and a harmonic-mean bound.

Figures & tables

Explore similar work

Aug 6, 2026

Optimal Rates for Learning with Monotone Adversaries

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error O((d/n)log⁡(n/d))O((d/n)\log(n/d)) for classes of VC dimension dd, and that every known optimal learner can be pushed away from the Θ(d/n)Θ(d/n) rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension dd and over known finite insertion budgets, the minimax expected error is Θ(1/n)Θ(1/n) at d=1d=1 and Θ((d/n)log⁡(n/d))Θ((d/n)\log(n/d)) for d≥2d\geq 2. The same rates hold with Littlestone dimension dLd_{\mathrm L} in place of dd, so the clean online-to-batch rate O(dL/n)O(d_{\mathrm L}/n) is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.
Oct 16, 2026

PAC Learning with Query Feedback

We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of Ω(D/ε)Ω(D/\varepsilon) and an upper bound of O~(D2/ε)\widetilde{O}(D^2/\varepsilon), suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to O~(D/ε)\widetilde{O}(D/\varepsilon), yielding a characterization up to logarithmic factors.
Apr 2, 2026

Robust Learning with Optimal Error

We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of randomized hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For ηη-rate malicious noise, we show the optimal error is 12⋅η/(1−η)\frac{1}{2} \cdot η/(1-η), improving on the optimal error of deterministic hypotheses by a factor of 1/21/2. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of 6/76/7. - For ηη-rate nasty noise, we show the optimal error is 32⋅η\frac{3}{2} \cdot η for distribution-independent learners and ηη for fixed-distribution learners, both improving upon the optimal 2η2 η error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026). - For ηη-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is ηη, improving upon the optimal 2η2η error of deterministic hypotheses. All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.