Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
This work addresses a gap in dynamic regret minimization for non-stationary online learning with curved losses, offering improved theoretical bounds for researchers in optimization and machine learning, though it appears incremental as it builds on existing concepts like mixability.
The paper tackles the problem of non-stationary online learning for curved losses, such as squared or logistic loss, by leveraging mixability to improve dynamic regret bounds. It achieves an O(d T^{1/3} P_T^{2/3} log T) dynamic regret, improving upon the previous best O(d^{10/3} T^{1/3} P_T^{2/3} log T) result in dimensionality d.
Non-stationary online learning has drawn much attention in recent years. Despite considerable progress, dynamic regret minimization has primarily focused on convex functions, leaving the functions with stronger curvature (e.g., squared or logistic loss) underexplored. In this work, we address this gap by showing that the regret can be substantially improved by leveraging the concept of mixability, a property that generalizes exp-concavity to effectively capture loss curvature. Let $d$ denote the dimensionality and $P_T$ the path length of comparators that reflects the environmental non-stationarity. We demonstrate that an exponential-weight method with fixed-share updates achieves an $\mathcal{O}(d T^{1/3} P_T^{2/3} \log T)$ dynamic regret for mixable losses, improving upon the best-known $\mathcal{O}(d^{10/3} T^{1/3} P_T^{2/3} \log T)$ result (Baby and 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.