Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback
Authors: Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-Ichi Kawarabayashi
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contribution is to propose algorithms that offer optimal regret bounds of O( T) as well as low oracle complexity for both non-stochastic settings and stochastic settings. Our algorithm for non-stochastic settings has an oracle complexity of O(T) and is the first algorithm that achieves both a regret bound of O( T) and an oracle complexity of O(poly(T)), given only linear optimization oracles. |
| Researcher Affiliation | Collaboration | Shinji Ito NEC Corporation, The University of Tokyo i-shinji@nec.com Daisuke Hatano RIKEN AIP daisuke.hatano@riken.jp Hanna Sumita Tokyo Metropolitan University sumita@tmu.ac.jp Kei Takemura NEC Corporation kei_takemura@nec.com Takuro Fukunaga Chuo University, RIKEN AIP, JST PRESTO fukunaga.07s@g.chuo-u.ac.jp Naonori Kakimura Keio University kakimura@math.keio.ac.jp Ken-ichi Kawarabayashi National Institute of Informatics k-keniti@nii.ac.jp |
| Pseudocode | Yes | Algorithm 1 An oracle efficient algorithm for non-stochastic bandit linear optimization |
| Open Source Code | No | The paper does not contain any explicit statements about the release of open-source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper presents theoretical algorithms and does not involve empirical training on specific datasets. Therefore, no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper focuses on theoretical contributions and does not describe empirical experiments that would require validation dataset splits. Therefore, no information regarding training/test/validation dataset splits is provided. |
| Hardware Specification | No | The paper focuses on theoretical algorithms and does not describe any empirical experiments or their computational execution. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and does not mention any specific software dependencies or their version numbers required for replication. |
| Experiment Setup | No | The paper describes theoretical algorithms and their properties, not an empirical experiment. While Algorithm 1 lists theoretical parameters like 'Learning rate η > 0' and 'error bound ε > 0', these are not concrete experimental setup details like hyperparameters used in an actual computational run. |