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

Aug 30, 2026

Adversarial Online Classification with a Preview

Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length TT, a uniformly random subset of size pTpT is revealed before prediction begins, and the remaining (1−p)T(1-p)T examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the preview rate pp: for binary classes of VC dimension dd, the optimal excess loss is Θ(d/p+dT)Θ(d/p+\sqrt{dT}), up to the trivial cap at TT; for multiclass classes we obtain the corresponding O~(dDS/p+dNatT)\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T}) bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.
Sep 27, 2026

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

We consider binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm using a Gaussian perturbation for each observed context achieves O~(Tlog⁡N)\widetilde O(\sqrt{T\log N}) regret for a class of NN experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class. For an infinite hypothesis class H\mathcal H, the same algorithm achieves O~(TVC⁡(H))\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)}) regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning. As an application, we reduce the problem of contextual bandits with KK actions to classification through uniform exploration, achieving O~(K2/3T2/3(log⁡N)1/3)\widetilde O(K^{2/3}T^{2/3}(\log N)^{1/3}) regret. This matches the best known dependence on the horizon while removing the context-distribution access required by prior oracle-efficient methods.
Feb 20, 2026

Distribution-Free Sequential Prediction with Abstentions

We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d. instances, but at each round, the learner may also abstain from making a prediction without incurring any penalty if the instance was indeed corrupted. This semi-adversarial setting naturally sits between the classical stochastic case with i.i.d. instances for which function classes with finite VC dimension are learnable; and the adversarial case with arbitrary instances, known to be significantly more restrictive. For this problem, Goel et al. (2023) showed that, if the learner knows the distribution μμ of clean samples in advance, learning can be achieved for all VC classes without restrictions on adversary corruptions. This is, however, a strong assumption in both theory and practice: a natural question is whether similar learning guarantees can be achieved without prior distributional knowledge, as is standard in classical learning frameworks (e.g., PAC learning or asymptotic consistency) and other non-i.i.d. models (e.g., smoothed online learning). We therefore focus on the distribution-free setting where μμ is unknown and propose an algorithm AbstainBoost based on a boosting procedure of weak learners, which guarantees sublinear error for general VC classes in distribution-free abstention learning for oblivious adversaries. These algorithms also enjoy similar guarantees for adaptive adversaries, for structured function classes including linear classifiers. These results are complemented with corresponding lower bounds, which reveal an interesting polynomial trade-off between misclassification error and number of erroneous abstentions.