Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case
Authors: Joon Kwon, Vianney Perchet
JMLR 2016 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We demonstrate that, in the classical non-stochastic regret minimization problem with d decisions, gains and losses to be respectively maximized or minimized are fundamentally different. Indeed, by considering the additional sparsity assumption (at each stage, at most s decisions incur a nonzero outcome), we derive optimal regret bounds of different orders. Specifically, with gains, we obtain an optimal regret guarantee after T stages of order T log s, so the classical dependency in the dimension is replaced by the sparsity size. With losses, we provide matching upper and lower bounds of order pTs log(d)/d, which is decreasing in d. Eventually, we also study the bandit setting, and obtain an upper bound of order pTs log(d/s) when outcomes are losses. This bound is proven to be optimal up to the logarithmic factor p. Keywords: regret minimization, bandit, sparsity |
| Researcher Affiliation | Academia | Joon Kwon EMAIL Institut de mathématiques de Jussieu Université Pierre et Marie Curie 4, place Jussieu 75252 Paris Cedex 05, France. Vianney Perchet EMAIL Centre de recherche en économie et statistique École nationale de la statistique et de l administration économique 3, avenue Pierre Larousse 92245 MalakoffCedex, France |
| Pseudocode | Yes | Algorithm 1: For losses in full information without prior knowledge about sparsity. Algorithm 2: For gains in full information without prior knowledge about sparsity. |
| Open Source Code | No | The paper does not explicitly provide any statement about releasing source code for the methodology described, nor does it include a link to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical analysis of regret minimization problems with 'gain' and 'loss' vectors as outcomes. It does not use or refer to any specific publicly available datasets for experimental evaluation. The 'outcomes' are generated within the theoretical framework, for example, 'Define the sequence of i.i.d. loss vectors ℓt (t 1) as follows. First, we draw a set It [d] of cardinality s uniformly among the d s possibilities.' |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on specific datasets, therefore, there are no mentions of training, test, or validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and algorithm design. It does not mention any specific software or library versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical and focuses on deriving regret bounds for algorithms. It does not describe practical experimental setups with hyperparameters, training configurations, or system-level settings. |