Hugging Face Trending Papers

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.

arXiv Machine Learning
6d ago

Learning from First Discrepancies with Joint Reset and Pilot Guarantees

The paper studies learning from runs that stop at their first incorrect decision, revealing only the queries and correct labels up to that point. It analyzes how many such runs are required to learn a hypothesis from a fixed binary class of VC dimension at most $d$, providing bounds on the number of runs and distinct pilots needed to achieve a risk estimate within ε of the optimal risk. The results include upper bounds on sample complexity, treatment of unknown cost ceilings, and matching lower bounds for finite classes.

By Michal \v{C}ert\'ik
arXiv Machine Learning
Aug 12

Optimistic Rates for Multiclass PAC Learning

arXiv:2608. 10869v1 Announce Type: new Abstract: Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself.

By Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
arXiv Machine Learning
Sep 25

Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

The paper revisits realizable multiclass PAC learning with bandit feedback, correcting a previously claimed lower bound on sample complexity. It introduces a new anchored dimension, “aBDS,” and establishes a constant‑free three‑part lower bound, while also providing tighter upper bounds that eliminate dependence on the total label count. The authors demonstrate that the optimal sample complexity can vary dramatically even among classes with identical dimensional profiles, revealing a confidence direct‑sum phenomenon and a rank‑saturation phase transition.

By Guangjian Zhang
arXiv Machine Learning
Oct 16

Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

The paper investigates transfer learning in stochastic multi‑armed bandits when historical data come from an unknown adaptive policy. It establishes asymptotic problem‑dependent lower bounds and introduces the KL‑UCB‑Transfer algorithm, which combines online and historical data to achieve logarithmic regret with an improved constant under certain mean‑gap conditions. The study also relaxes the source‑target discrepancy assumption to a one‑sided condition, demonstrating that logarithmic regret can still be achieved under misspecification and identifying regimes of improvement, degradation, or loss of guarantee.

By Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard