Expected Worst Case Regret via Stochastic Sequential Covering
Authors: Changlong Wu, Mohsen Heidari, Ananth Grama, Wojciech Szpankowski
TMLR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of sequential prediction and online minimax regret with stochastically generated features under a general loss function. We introduce the 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 further establish upper bounds for real valued classes with finite fat-shattering numbers. Finally, by applying information-theoretic tools for fixed design minimax regrets, we provide lower bounds for expected worst case minimax regret. |
| Researcher Affiliation | Academia | Changlong Wu1 EMAIL Mohsen Heidari1,2 EMAIL Ananth Grama1 EMAIL Wojciech Szpankowski1 EMAIL 1Center for Science of Information (CSo I), Purdue University 2Department of Computer Science, Indiana University, Bloomington |
| Pseudocode | No | The paper describes various algorithms like the Exponential Weighted Average (EWA) algorithm and the Smooth truncated Bayesian Algorithm conceptually, and refers to their application (e.g., "We run the Exponential Weighted Average (EWA) algorithm"), but it does not present any of these algorithms or procedures in structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described, nor does it provide any links to code repositories. |
| Open Datasets | No | The paper is theoretical in nature and focuses on 'stochastically generated features' and 'i.i.d. generated features' within its mathematical framework. It does not utilize or refer to any specific publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper does not describe any experimental setup involving specific datasets, and therefore, no training/test/validation dataset splits are mentioned. |
| Hardware Specification | No | This paper presents theoretical research, focusing on mathematical bounds and complexity measures. It does not describe any experimental work that would require specific hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation or experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical, focusing on mathematical proofs and algorithmic analysis rather than empirical experiments. Therefore, it does not include details on experimental setup, hyperparameters, or training configurations. |