Dynamic Regret of Strongly Adaptive Methods
Authors: Lijun Zhang, Tianbao Yang, jin, Zhi-Hua Zhou
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper makes a step towards understanding their connections. Specifically, we show that the strongly adaptive regret in (1), together with the functional variation, can be used to upper bound the dynamic regret in (2). Thus, an algorithm with a small strongly adaptive regret is automatically equipped with a tight dynamic regret. As a result, we obtain a series of algorithms for minimizing the dynamic regret that do not need any prior knowledge of the functional variation. The main contributions of this work are summarized below. We provide a general theorem that upper bounds the dynamic regret in terms of the strongly adaptive regret and the functional variation. For convex functions, we show that the strongly adaptive algorithm of Jun et al. (2017) has a dynamic regret of O(T 2/3V 1/3 T log1/3 T), which matches the minimax rate (Besbes et al., 2015), up to a polylogarithmic factor. For exponentially concave functions, we propose a strongly adaptive algorithm that allows us to control the tradeoff between the adaptive regret and the computational cost explicitly. Then, we demonstrate that its dynamic regret is O(d TVT log T), where d is the dimensionality. To the best of our knowledge, this is the first time that exponential concavity is utilized in the analysis of dynamic regret. For strongly convex functions, our proposed algorithm can also be applied and yields a dynamic regret of O( TVT log T), which is also minimax optimal up to a polylogarithmic factor. |
| Researcher Affiliation | Collaboration | 1National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China 2Department of Computer Science, The University of Iowa, Iowa City, USA 3Alibaba Group, Seattle, USA. |
| Pseudocode | Yes | Algorithm 1 Improved Following the Leading History (IFLH) |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not mention specific datasets (public or otherwise) used for training experiments. It discusses theoretical properties of functions (convex, exp-concave, strongly convex) but not concrete data. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental setups with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental hardware used. |
| Software Dependencies | No | The paper is theoretical and does not mention any software dependencies with specific version numbers that would be needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe specific experimental setups, hyperparameters, or training configurations. It focuses on theoretical guarantees and algorithm design. |