Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features
Abstract
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(dlog2 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(dlog T+log(1/δ)), matching the worst-case Ω(dlog(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 Ω(log2 T) bits for uniform sequential approximation at accuracy 1/T.
Related
- Critical Growth for Stochastic Adaptive Stabilization with an Unknown Input Gain
- Learning to Solve Stochastic Controls with Unknown Drifts and Running Rewards: Theory, Algorithms and Convergence
- Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization
- Riemannian Optimization on Unknown Manifolds via Stochastic Proximal Refinement
- Flag Varieties of General Quiver Representations: Characteristic Classes and Semi-Invariants
BibTeX
@misc{wu2026tight,
title = {{Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features}},
author = {Changlong Wu and Wojciech Szpankowski},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00788},
eprint = {2611.00788},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00788},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features
AU - Changlong Wu
AU - Wojciech Szpankowski
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00788
UR - https://arxiv.org/abs/2611.00788
AB - 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(dlog^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(dlog T+log(1/δ)), matching the worst-case Ω(dlog(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 Ω(log^2 T) bits for uniform sequential approximation at accuracy 1/T.
ER -