Learning from First Discrepancies with Joint Reset and Pilot Guarantees
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 , on a fresh record of at most 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 and their risks have infimum at most , one learner uses runs and distinct pilots on every history. It returns a member of the class and an interval of width at most containing, with probability at least , 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
| Symbol | Meaning |
|---|---|
| , | stopping rank of ; number of pairs displayed by pilot |
| , , | loss of at its stopping rank; risk; natural discrepancy probability |
| propensity: -mass of functions that are correct at positions | |
| , | anchor and the numerical bound used by the learner |
| , , | regularizer; potential ; |
| , | logger (a frozen lottery with ); visibility threshold |
Statistical Learning Theory
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
See all 640 papers