Neue Erkenntnisse zum Sample‑Adaptivity‑Tradeoff bei On‑Demand Sampling

In einer kürzlich veröffentlichten Studie auf arXiv wird der Zusammenhang zwischen der benötigten Stichprobengröße und der Anzahl der Runden bei On‑Demand‑Sampling untersucht. Dabei wird ein Lernalgorithmus betrachtet, der aus k verschiedenen Verteilungen gezielt Stichproben zieht, wobei die Rundenzahl begrenzt ist.

Im realizierbaren Rahmen des Multi‑Distribution‑Learning (MDL) zeigt die Arbeit, dass die optimale Stichprobenkomplexität eines r‑Runden‑Algorithmus ungefähr mit dk^{Θ(1/r)} / ε skaliert. Für den allgemeineren agnostischen Fall präsentiert die Studie einen Algorithmus, der eine nahezu optimale Stichprobenkomplexität von ~O((d + k) / ε²) innerhalb von ~O(√k) Runden erreicht.

Ein besonderes Highlight ist die Einführung des neuen Rahmens „Optimization via On‑Demand Sampling“ (OODS). Dieser abstrahiert den Tradeoff zwischen Stichprobe und Rundenzahl und fasst die meisten bestehenden MDL‑Algorithmen zusammen. Im OODS‑Setting werden nahezu optimale Schranken für die Rundenkomplexität aufgestellt. Die oberen Schranken führen direkt zum ~O(√k)-Runden‑Algorithmus für den agnostischen MDL, während die unteren Schranken zeigen, dass ein subpolynomieller Rundenaufwand nur durch völlig neue Techniken möglich wäre, die die inhärente Schwierigkeit von OODS umgehen.