Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features
Organizations: University of Arizona · Purdue University · Jagiellonian University
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 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 admits a distribution-blind exact cover with log-size , matching the worst-case 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 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 bits for uniform sequential approximation at accuracy .
Figures & tables
| Work | Feature law | Access | Rate |
|---|---|---|---|
| Bhatt and Kim (2021) | unknown | causal | |
| Bhatt et al. (2023b) | unknown | causal | square-root |
| Bhatt et al. (2023a) | known | causal | |
| Qian et al. (2026) | any | design | |
| Wu et al. (2023b) | unknown | causal | |
| This paper | unknown | causal |
Statistical Learning Theory
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
See all 633 papers