Learning from First Discrepancies with Joint Reset and Pilot Guarantees

Michal ČertíkarXiv 2026 · arXiv

This paper, titled "Learning from First Discrepancies with Joint Reset and Pilot Guarantees," explores a challenging but common scenario in machine learning: learning from a process that stops and hides all subsequent information the moment a mistake is made.

Imagine trying to teach a robot to navigate a corridor, but the moment it bumps into a wall, the experiment ends, and you get no data about the rest of the path. This is "stopped feedback," and this paper provides the first tight statistical bounds on how to learn effectively in this environment.

TL;DR

The paper provides a minimax-optimal algorithm for learning from "stopped feedback," where a trial terminates at the first error. It establishes tight upper and lower bounds on both the total number of trials (resets) and the number of distinct models (pilots) required to find a near-optimal decision rule within a VC-class.

What Problem Does This Paper Address?

In standard supervised learning, we assume we can see the full set of labels for a given input. However, in many real-world "checking" procedures—like software testing, medical diagnostics, or sequential decision-making—a failure at step $j$ prevents us from seeing what would have happened at steps $j+1$ through $D$.

This creates a severe selection bias. If your current model (the "pilot") is bad and fails early, you remain "blind" to the rest of the data distribution. To learn a better model, you must perform "deliberate exploration," but every trial is costly. The authors specifically look at two resource constraints:

  1. $N$ (Resets): The total number of runs performed.
  2. $V$ (Distinct Pilots): The number of unique hypotheses tested. This measures the "breadth" of exploration.

The goal is to return a hypothesis with low risk and a "certificate" (a confidence interval) that accurately locates the optimal risk, even when the optimal model might still fail occasionally.

Methods

The authors propose a learner that operates in six primary steps, combining classical learning theory with novel structural arguments:

  • The Coarse Anchor: The learner first identifies an "anchor" hypothesis that has a reasonably low probability of failing early. This is done using an ownership argument, where the loss of a candidate is assigned to the first pilot in a sequence that reaches the candidate's stopping position.
  • Legal Gain Estimation: To learn beyond what the current pilot sees, the algorithm uses a "logger" (a mixture of pilots). It estimates the "gain" of moving the visibility frontier one step further. Crucially, it uses a "one-position shift" where a discrepancy at position $j$ is used to estimate potential at position $j+1$.
  • Depth-Robust Graphs: To avoid a cost that grows polynomially with the sequence length $D$, the learner arranges acquisition stages along a sparse depth-robust directed acyclic graph. This ensures that even if some stages fail to "see" far enough due to early discrepancies, a long path of successful stages will eventually cover the entire horizon $D$.
  • Harmonic Recovery: The final estimate is a lottery that mixes the anchor with the outputs of the various graph stages. The authors use a harmonic-arithmetic mean inequality to recover the sample efficiency lost during the mixing process.
  • Pattern Oracle: The learner assumes access to an oracle that can list representatives for all label patterns the hypothesis class can realize on the observed queries (a standard, though computationally expensive, assumption in VC-theory).

Datasets

This is a theoretical paper and does not use empirical datasets. Instead, it uses:

  • Finite families of instances: Specifically constructed mathematical "worlds" used to prove lower bounds. These include "threshold paths" (binary search trees) and "contextual combination locks" designed to force any learner to spend a minimum amount of $N$ and $V$.

Key Insights and Ideas

  • The Cost of Exploration ($V$): The paper highlights that simply counting total runs ($N$) isn't enough; the number of different models you have to try ($V$) is a distinct and necessary bottleneck in stopped-feedback settings.
  • Visibility Frontiers: Learning is viewed as a process of pushing a "visibility frontier" forward through the sequence of $D$ queries.
  • Decoupling Risk and Discrepancy: The paper treats the probability of making a mistake ($F^*$) and the actual loss ($R^*$) as two separate optima. A model might be great at the final task (low risk) but prone to early mistakes (high discrepancy), making it hard to train.
  • The "Aha" Moment on $D$: By using depth-robust graphs, the authors show that the dependence on the sequence length $D$ can be kept linear (up to log factors) in the reset count, rather than quadratic or worse.

Key Results

The paper proves that for a hypothesis class with VC dimension $d$ and a sequence length $D$, a learner can achieve accuracy $\varepsilon$ with:

  • Resets ($N$): $\widetilde{O}\left((d+1)\frac{D(f+\varepsilon)+r}{\varepsilon^2}\right)$
  • Distinct Pilots ($V$): $\widetilde{O}\left(D(1 + f/\varepsilon)\right)$

Where $f$ and $r$ are ceilings on the optimal discrepancy probability and risk, respectively.

The lower bounds match these orders, proving that these rates are minimax optimal. Specifically, they show that the $D$ factor is unavoidable because you need to "re-learn" or "re-verify" bits of information as you move deeper into the sequence.

Limitations and Future Work

  • Computational Complexity: The algorithm relies on a pattern oracle which, for general VC classes, may require exponential time. Finding computationally efficient versions for specific classes (like intervals or half-spaces) remains an open question.
  • Large Constants: The authors acknowledge that the constants in their "depth-robust graph" construction are currently quite large, making the linear dependence on $D$ an asymptotic result rather than a practical one for short sequences.
  • Common Record Law: The analysis assumes the distribution of queries does not depend on the pilot. If the pilot's actions change the future queries (as in Reinforcement Learning), the current proofs would not hold.
  • Exact Truth: The model assumes labels are deterministic functions of the queries. Extending this to noisy labels would require new concentration arguments.

Summary updated

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 $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.
BibTeX
@misc{certik2026learning,
  author = {Michal Čertík},
  title = {{Learning from First Discrepancies with Joint Reset and Pilot Guarantees}},
  year = {2026},
  eprint = {2611.13913},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13913},
}
Figure