# Expected Worst Case Regret via Stochastic Sequential Covering

arXiv: https://arxiv.org/abs/2209.04417 · HTML: https://mlsanity.com/paper/2209.04417/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 9 Sep 2022.

## Builds on (most cited first, 11 of 11)

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts](https://mlsanity.com/paper/1501.07340/) (2015)
- [Logistic Regression Regret: What's the Catch?](https://mlsanity.com/paper/2002.02950/) (2020)
- [Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm](https://mlsanity.com/paper/2205.03728/) (2022)

## Built on by (most cited first, 12 of 12)

- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [Oracle-Efficient Hybrid Online Learning with Unknown Distribution](https://mlsanity.com/paper/2401.15520/) (2024)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Oracle-efficient Hybrid Learning with Constrained Adversaries](https://mlsanity.com/paper/2603.04546/) (2026)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [Smoothed Online Classification can be Harder than Batch Classification](https://mlsanity.com/paper/2405.15424/) (2024)
- [Robust Online Classification: From Estimation to Denoising](https://mlsanity.com/paper/2309.01698/) (2023)
- [Online Distribution Learning with Local Private Constraints](https://mlsanity.com/paper/2402.00315/) (2024)
- [Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation](https://mlsanity.com/paper/2603.02043/) (2026)
- [Agnostic Smoothed Online Regression with Adversarial Responses](https://mlsanity.com/paper/2609.32478/) (2026)

## Abstract (arXiv)

We study the problem of sequential prediction and online minimax regret with stochastically generated features under a general loss function. We introduce a notion of expected worst case minimax regret that generalizes and encompasses prior known minimax regrets. For such minimax regrets we establish tight upper bounds via a novel concept of stochastic global sequential covering. We show that for a hypothesis class of VC-dimension mathsfVC and i.i.d. generated features of length T, the cardinality of the stochastic global sequential covering can be upper bounded with high probability (whp) by e^O(mathsfVC · log2 T). We then improve this bound by introducing a new complexity measure called the Star-Littlestone dimension, and show that classes with Star-Littlestone dimension mathsfSL admit a stochastic global sequential covering of order e^O(mathsfSL · log T). We further establish upper bounds for real valued classes with finite fat-shattering numbers. Finally, by applying information-theoretic tools of the fixed design minimax regrets, we provide lower bounds for the expected worst case minimax regret. We demonstrate the effectiveness of our approach by establishing tight bounds on the expected worst case minimax regrets for logarithmic loss and general mixable losses.