cs.LGOct 31, 2026

Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features

Authors: Changlong Wu, Wojciech Szpankowski

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 O(dlog⁡2T)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 dd admits a distribution-blind exact cover with log-size O(dlog⁡T+log⁡(1/δ))O(d\log T+\log(1/δ)), matching the worst-case Ω(dlog⁡(T/d))Ω(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)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⁡2T)Ω(\log^2 T) bits for uniform sequential approximation at accuracy 1/T1/T.

Figures & tables

Explore similar work

CardsList
  1. Adversarial Online Classification with a Preview

    Aug 30, 2026Roi Livni, Sahil SinglaOnline LearningStatistical Learning Theory

  2. Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

    Sep 27, 2026Gon Buzaglo, Elad HazanFollow-the-Perturbed-LeaderBinary Classification

  3. Distribution-Free Sequential Prediction with Abstentions

    Feb 20, 2026Jialin Yu, Moïse BlanchardStatistical Learning TheorySelective Prediction