Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm
Authors: Changlong Wu, Mohsen Heidari, Ananth Grama, Wojciech Szpankowski
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study sequential general online regression, known also as sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We obtain tight, often matching, lower and upper bounds for sequential minimax regret, which is defined as the excess loss incurred by the predictor over the best expert in the class. After proving a general upper bound we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our main contributions are: (i) constructive proofs through a new smooth truncated Bayesian algorithm; (ii) the novel application of global sequential covering in the context of logarithmic loss; (iii) lower and upper bounds with optimal leading constants; and (iv) novel informationtheoretic techniques for the lower bounds. |
| Researcher Affiliation | Academia | Changlong Wu1 Mohsen Heidari1,2 Ananth Grama1 Wojciech Szpankowski1 1CSo I, Purdue University 2 Indiana University wuchangl@hawaii.edu, {mheidari,ayg,szpan}@purdue.edu |
| Pseudocode | Yes | Algorithm 1 Bayesian predictor, Algorithm 2 Smooth truncated Bayesian predictor |
| Open Source Code | No | The paper does not mention releasing any source code or provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and algorithms; it does not conduct empirical studies using datasets for training. |
| Dataset Splits | No | The paper is theoretical and focuses on mathematical proofs and algorithms; it does not conduct empirical studies using datasets for validation. |
| Hardware Specification | No | The paper is theoretical and focuses on mathematical proofs and algorithms; it does not report on computational experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and algorithms; it does not report on computational experiments that would require software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and algorithms; it does not report on computational experiments, and thus no experimental setup details like hyperparameters or training settings are provided. |