Adversarial Online Classification with a Preview

• URL: http://arxiv.org/abs/2608.29503v1
• Date: Sun, 30 Aug 2026 01:38:49 GMT
• Title: Adversarial Online Classification with a Preview
• Abstract summary: Worst-case online classification is governed by sequential complexity, such as Littlestone dimension.<n>We show that a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order.
• Score: 17.495168716195476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(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 $p$: for binary classes of VC dimension $d$, the optimal excess loss is $Θ(d/p+\sqrt{dT})$, up to the trivial cap at $T$; for multiclass classes we obtain the corresponding $\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.

Related papers

• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice.<n>Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable.<n>Larsen, Pabbaraju, and Shetty, who introduced this model, show that empirical risk minimization attains expected error $O((d/n)log(n/d))$ for classes of VC dimension $d$.
  arXiv  Detail & Related papers  (2026-08-06T17:45:32Z)
• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  We study the sample complexity of learning an $$-optimal policy in the Shortest Path (SSP) problem.<n>We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.<n>Surprisingly, this implies that whenever $c_min = 0$ an SSP problem may not be learnable.
  arXiv  Detail & Related papers  (2026-04-17T14:47:52Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  We study the problem of contextual semi-bandits, where input contexts are mapped into subsets of size $m$ of a collection of $K$ possible actions.<n>Motivated by prototypical applications of contextual bandits, we focus on the $s$-sparse regime.<n>Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors.
  arXiv  Detail & Related papers  (2025-02-13T12:13:25Z)
• Agnostic Smoothed Online Learning without Knowledge of the Base Measure [5.167069404528051]
  We propose an algorithm to guarantee sublinear regret for smoothed online learning without prior knowledge of $mu$.<n>R-Cover has adaptive regret $tilde O(sqrtdT/sigma)$ for function classes with dimension $d$, which is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2024-10-07T15:25:21Z)
• Self-Directed Linear Classification [50.659479930171585]
  In online classification, a learner aims to predict their labels in an online fashion so as to minimize the total number of mistakes. Here we study the power of choosing the prediction order and establish the first strong separation between worst-order and random-order learning.
  arXiv  Detail & Related papers  (2023-08-06T15:38:44Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  We study the sample complexity of learning an $epsilon$-optimal policy in the Shortest Path (SSP) problem. We derive complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.
  arXiv  Detail & Related papers  (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. We work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. For every fixed $k$ the class of $k$-decision lists has sample complexity against a $log(n)$-bounded adversary.
  arXiv  Detail & Related papers  (2022-05-12T14:40:18Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  We consider the problem of online classification under a privacy constraint. In this setting a learner observes sequentially a stream of labelled examples $(x_t, y_t)$, for $1 leq t leq T$, and returns at each iteration a hypothesis $h_t$ which is used to predict the label of each new example $x_t$. The learner's performance is measured by her regret against a known hypothesis class $mathcalH$.
  arXiv  Detail & Related papers  (2021-06-25T09:08:33Z)
• Robust learning under clean-label attack [26.323812778809913]
  We study the problem of robust learning under clean-label data-poisoning attacks. The learning goal is to minimize the attackable rate, which is more difficult than optimal PAC learning.
  arXiv  Detail & Related papers  (2021-03-01T00:21:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.