mlsanityData to 7 Oct 2026

Smoothed Analysis of Sequential Probability Assignment

arXiv 2303.04845 ↗First posted 8 Mar 2023cs.LG cs.DS cs.ITcited by 7

Not on the map. Why?

Abstract (arXiv)

We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning. This leads to optimal (logarithmic) fast rates for parametric classes and classes with finite VC dimension. On the algorithmic front, we develop an algorithm that efficiently taps into the MLE oracle, for general classes of functions. We show that under general conditions this algorithmic approach yields sublinear regret.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 23 of its 65 references that are in the map. First posted on arXiv 8 Mar 2023.

Builds on

23 of 65 references.

References · 23

  1. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  2. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  4. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  5. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  6. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  7. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  8. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  9. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  10. 2020Smoothed Analysis of Online and Differentially Private Learningcited by 47
  11. 2018Logistic Regression: The Importance of Being Impropercited by 40
  12. 2016Oracle-Efficient Online Learning and Auction Designcited by 32
11 more
  1. 2018Efficient Online Portfolio with Logarithmic Regretcited by 20
  2. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  3. 2022Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum Statescited by 15
  4. 2022Efficient and Near-Optimal Online Portfolio Selectioncited by 13
  5. 2022Expected Worst Case Regret via Stochastic Sequential Coveringcited by 12
  6. 2015Sequential Probability Assignment with Binary Alphabets and Large Classes of Expertscited by 11
  7. 2022Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functionscited by 10
  8. 2023Online Learning in Dynamically Changing Environmentscited by 8
  9. 2022Adaptive Oracle-Efficient Online Learningcited by 7
  10. 2022Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithmcited by 5
  11. 2020Sample Complexity Result for Multi-category Classifiers of Bounded Variationcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 5; 2025: 1.

7 papers.

  1. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  2. 2023Smooth Nash Equilibria: Algorithms and Complexitycited by 3
  3. 2024Oracle-Efficient Hybrid Online Learning with Unknown Distributioncited by 3
  4. 2025Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarkscited by 2
  5. 2024Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihoodcited by 1
  6. 2024Online Distribution Learning with Local Private Constraintscited by 0
  7. 2024The SMART approach to instance-optimal online learningcited by 0