Optimal No-Regret Learning for One-Sided Lipschitz Functions
Authors: Paul Duetting, Guru Guruganesh, Jon Schneider, Joshua Ruizhi Wang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our primary contribution is the construction of an efficient algorithm for this problem with an asymptotically optimal regret bound. In particular, we show it is possible to optimize any L-left(/right)-Lipschitz continuous function from [0, 1] to [0, L] while incurring at most O(L log log T) regret: Theorem 1.1 (Restatement of Corollary 3.2 and Theorem 5.1). There exists a deterministic and efficient online algorithm (Algorithm 2) for maximizing an L-left-Lipschitz continuous function mapping [0, 1] [0, L] over T rounds that incurs at most O(L log log T) regret. Moreover, any learning algorithm must incur at least Ω(L log log T) for this problem. |
| Researcher Affiliation | Industry | Paul D utting * 1 Guru Guruganesh * 2 Jon Schneider * 3 Joshua R. Wang * 2 *Equal contribution 1Google Research, Z urich, Switzerland 2Google Research, Mountain View, USA 3Google Research, New York City, USA. Correspondence to: Joshua R. Wang <joshuawang@google.com>. |
| Pseudocode | Yes | Algorithm 1 Sweep Using Maximum Value Hint, Algorithm 2 Hybrid Binary and KL Search. These are presented in pseudocode format in the paper. |
| Open Source Code | No | The paper does not provide any concrete statement about the availability of its source code or a link to a code repository. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments involving datasets, therefore no information about public dataset availability is provided. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments, therefore no information about training/test/validation splits is provided. |
| Hardware Specification | No | This is a theoretical paper describing algorithms and proofs, and does not involve experimental runs requiring specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper and does not discuss software implementations or dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper that focuses on algorithm design and proofs, and does not describe an experimental setup with specific details like hyperparameters or training configurations. |