Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
Authors: Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Let d denote the dimensionality and PT the path length of comparators that reflects the environmental non-stationarity. We demonstrate that an exponential-weight method with fixed-share updates achieves an O(d T 1/3P 2/3 T log T) dynamic regret for mixable losses, improving upon the bestknown O(d10/3T 1/3P 2/3 T log T) result (Baby & Wang, 2021) in d. More importantly, this improvement arises from a simple yet powerful analytical framework that exploits the mixability, which avoids the Karush-Kuhn-Tucker-based analysis required by existing work. Theorem 1. Under Assumption 1, 2 and 3, for any ut W, Algorithm 1 with µ = 1/T ensures D-REGT ({ut}T t=1) O d log T (1 + T 1/3P 2/3 T ). Theorem 3. Under Assumptions 1, 4 and 5, Algorithm 3 with µ = 1/T ensures D-REGT O d log T (1 + T 1/3P 2/3 T ) for any comparator sequence u1, . . . , u T W. |
| Researcher Affiliation | Academia | 1RIKEN AIP, Japan 2National Key Laboratory for Novel Software Technology, Nanjing University, China 3The University of Tokyo, Japan. Correspondence to: Yu-Jie Zhang <EMAIL>, Peng Zhao <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Fixed-share For Continuous Space Algorithm 2 Follow-the-Leading-History Algorithm 3 Projected Fixed-share with Surrogate Loss |
| Open Source Code | No | A future direction is to develop computationally more efficient methods for the logistic loss and the general OCO setting. |
| Open Datasets | No | No specific datasets are mentioned for empirical evaluation. The paper is theoretical in nature and analyzes different loss functions (squared loss, logistic loss, etc.) without performing experiments on specific datasets. |
| Dataset Splits | No | No information about dataset splits is provided as the paper does not conduct empirical experiments with data. |
| Hardware Specification | No | No specific hardware details are mentioned as the paper is theoretical and does not report experimental results. |
| Software Dependencies | No | No specific software dependencies with version numbers are mentioned, as the paper is theoretical and does not describe an implementation. |
| Experiment Setup | No | No specific experimental setup details, such as hyperparameter values or training configurations, are provided as the paper is theoretical. |