← 研踪 PaperTrailarXiv:2611.13913 · v1
Learning from First Discrepancies with Joint Reset and Pilot Guarantees
首次提交 2026-11-10 19:05
版本更新 2026-11-10 19:05
雷达观测 2026-11-11 11:04
摘要
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 $d$, on a fresh record of at most $D$ 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 $f$ and their risks have infimum at most $r$, one learner uses $\widetilde O((d+1)[D(f+\varepsilon)+r]/\varepsilon^2)$ runs and $\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-δ$, 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 19:05 · 最新观测版本
Learning from First Discrepancies with Joint Reset and Pilot Guarantees
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 $d$, on a fresh record of at most $D$ 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 $f$ and their risks have infimum at most $r$, one learner uses $\widetilde O((d+1)[D(f+\varepsilon)+r]/\varepsilon^2)$ runs and $\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-δ$, 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.
查看此版本解读 →查看此版本原文 ↗