Research map / Bandits and online learning / Online convex optimization and games
Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that exponential-weight with fixed-share over continuous Gaussian-mixture distributions, analyzed via mixability rather than KKT conditions, gives O(d T^{1/3} P_T^{2/3} log T) dynamic regret for mixable/curved losses, improving the dimension dependence from d^{10/3} to d.
Problem
Dynamic regret minimization for curved losses (squared, logistic, exp-concave) in non-stationary online learning, where prior bounds have poor dimension dependence (d^{10/3}) and rely on involved KKT-based analysis.
Approach
Use mixability of the loss and an exponential-weight distribution learner with fixed-share updates over continuous space; decompose dynamic regret into mixability gap, mixability regret against Gaussian comparators Q_t centered at the comparators with time-varying variance, and a comparator gap; this yields the path-length bound without KKT analysis and without knowing P_T. The method is equivalen
Key results
- For least-squares and logistic regression, the method achieves Õ(d + d T^{1/3} P_T^{2/3}) dynamic regret, improving the best-known Õ(d + d^{10/3} T^{1/3} P_T^{2/3}) dependence on dimension.
- For the 1-dimensional squared loss, a proper-learning greedy-forecaster variant achieves Õ(1 + T^{1/3} P_T^{2/3}), matching the best-known bound without KKT analysis.
- The general exp-concave OCO extension with projection and surrogate loss achieves Õ(d + d T^{1/3} P_T^{2/3}) under proper learning without smoothness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use mixability-based fixed-share updates instead of the prior method | 1-dimensional squared loss · 1-dimensional squared loss | dynamic regret bound: \widetilde{\O}(1 + T^{1/3}P_T^{2/3}) -> \widetilde{\O}(1 + T^{\frac{1}{3}} P_T^{\frac{2}{3}}) | No clear effect |
| Use mixability-based fixed-share updates instead of the prior exp-concavity method | Least-squares regression · Least-squares regression | dynamic regret bound: \widetilde{\O}(d + d^{10/3} T^{1/3}P_T^{2/3}) -> \widetilde{\O}(d + dT^{\frac{1}{3}} P_T^{\frac{2}{3}}) | Helped |
| Use mixability-based fixed-share updates instead of the prior exp-concavity method | Logistic regression · Logistic regression | dynamic regret bound: \widetilde{\O}(d + d^{10/3} T^{1/3}P_T^{2/3}) -> \widetilde{\O}(d + dT^{\frac{1}{3}} P_T^{\frac{2}{3}}) | Helped |
| Add a projection step and use a surrogate loss | Fixed-share method for general OCO · General exp-concave OCO | dynamic regret bound: \widetilde{\O}(d + d^{{10/3}}T^{1/3}P_T^{2/3}) -> \O\Big(d \log T \cdot(1+ T^{\frac{1}{3}}P_T^{\frac{2}{3}}) \Big) | Helped |
Surprising findings
- The algorithm needs no prior knowledge of the path length P_T, despite being a single-layer exponential-weight method over distributions, yet it is algorithmically equivalent to a two-layer FLH-type ensemble.
Limitations
- Online prediction results rely on improper learning for least-squares and logistic regression.
- Logistic loss requires sampling-based computation without closed form; computational efficiency left open.
- Requires smoothness of loss functions in the main analysis; general OCO result needs projection step with computational challenges.
Experimental setup
Metrics: dynamic regret
Baselines: KKT-based strongly adaptive dynamic regret method for exp-concave losses two-layer dynamic regret for squared loss proper least-squares dynamic regret method logistic regression dynamic regret method
Builds on: fixed-share follow-the-leading-history Vovk aggregating algorithm online gradient descent dynamic regret
Closest papers by meaning
- Efficient Methods for Non-stationary Online Learning (NeurIPS 2022 · similarity 0.91)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.91)
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.90)
- Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.90)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.89)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.