Metraipolis › archive › dc_f034383742c4
Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features — arXiv:2611.00788
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.00788
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:35:25.075Z
- SHA-256 of the archived text
21c49e2b33e493b561112e09d81e6d5836887277a74e7004e9d16038572842e0- Stable URL of this page
https://metraipolis.com/documento/dc_f034383742c4
How to cite
Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features — arXiv:2611.00788 — arXiv (en), https://arxiv.org/abs/2611.00788 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f034383742c4 (Metraipolis archive dc_f034383742c4, sha256 21c49e2b33e493b561112e09d81e6d5836887277a74e7004e9d16038572842e0)
BibTeX
@misc{dcf034383742c4,
title = {Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features — arXiv:2611.00788},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.00788},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f034383742c4; sha256 21c49e2b33e493b561112e09d81e6d5836887277a74e7004e9d16038572842e0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00788. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study hybrid online learning with stochastic features and adversarial labels when the feature distribution is unknown. Prior work gave stochastic sequential covers of log-size $O(d\log^2 T)$ for a general VC class and logarithmic bounds only under stronger star-type structure. We show that finite VC dimension alone is enough: every binary class of VC dimension $d$ admits a distribution-blind exact cover with log-size $O(d\log T+\log(1/\delta))$, matching the worst-case $\Omega(d\log(T/d))$ dependence on the horizon. The key ingredient is a new local cube weight that counts Boolean subcubes incident to each realizable trace. Unlike the equal splits used in earlier constructions, we split mass unevenly according to these cube weights; a coordinate-deletion inequality shows that VC dimension controls the total cost of these splits. This yields, to our knowledge, the first tight $O((d+1)\log T)$ expected worst-case log-loss regret for general VC partitions with unknown i.i.d. features, and an exact polynomial-time implementation for planar affine halfspaces. We also show that the binary phenomenon does not extend from VC dimension to pseudo-dimension: a fixed pseudo-dimension-one sigmoid class requires $\Omega(\log^2 T)$ bits for uniform sequential approximation at accuracy $1/T$. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno). Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2611.00788 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T18:12:54.456Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).