Gradient-Variation Online Learning under Generalized Smoothness
Authors: Yan-Feng Xie, Peng Zhao, Zhi-Hua Zhou
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we systematically study gradient-variation online learning under generalized smoothness. We extend the classic optimistic mirror descent algorithm to derive gradient-variation regret by analyzing stability over the optimization trajectory and exploiting smoothness locally. Then, we explore universal online learning, designing a single algorithm with the optimal gradient-variation regrets for convex and strongly convex functions simultaneously, without requiring prior knowledge of curvature. This algorithm adopts a two-layer structure with a meta-algorithm running over a group of base-learners. To ensure favorable guarantees, we design a new Lipschitz-adaptive meta-algorithm, capable of handling potentially unbounded gradients while ensuring a second-order bound to effectively ensemble the base-learners. Finally, we provide the applications for fast-rate convergence in games and stochastic extended adversarial optimization. |
| Researcher Affiliation | Academia | Yan-Feng Xie, Peng Zhao, Zhi-Hua Zhou National Key Laboratory for Novel Software Technology, Nanjing University, China School of Artiļ¬cial Intelligence, Nanjing University, China {xieyf, zhaop, zhouzh}@lamda.nju.edu.cn |
| Pseudocode | Yes | Algorithm 1 Lipschitz Adaptive Optimistic Adapt-ML-Prod; Algorithm 2 Universal Gradient-Variation Online Learning under Generalized Smoothness |
| Open Source Code | No | This paper does not include experiments, and no data or code will be provided. |
| Open Datasets | No | This paper does not include experiments. |
| Dataset Splits | No | This paper does not include experiments. |
| Hardware Specification | No | This paper does not include experiments. |
| Software Dependencies | No | This paper does not include experiments. |
| Experiment Setup | No | This paper does not include experiments. |