Research map / Bandits and online learning / Online convex optimization and games
Exploiting Curvature in Online Convex Optimization with Delayed Feedback
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.
Proposes delayed FTRL, delayed ONS with adaptive learning rate, and delayed VAW with clipping for curved losses, achieving regret min{sigma_max ln T, sqrt(d_tot)} (strongly convex) and min{d_max n ln T, sqrt(d_tot)} (exp-concave and online linear regression) under delayed feedback.
Problem
Online convex optimization with delayed gradient feedback where losses are strongly convex, exp-concave, or squared (online linear regression); existing curvature-based delayed bounds scale with the maximum delay d_max and can be much worse than sqrt(d_tot).
Approach
Exploit loss curvature under delays by using FTRL with regularization over all past decisions (bound in terms of the maximum number of missing observations sigma_max and sqrt(d_tot)), an ONS variant with delay-adaptive learning rates that tracks both d_max n ln T and sqrt(d_tot) bounds, and a clipped delayed VAW forecaster for unconstrained regression.
Key results
- Delayed FTRL for strongly convex losses achieves O((G^2/lambda)(ln T + min{sigma_max ln T, sqrt(d_tot)})) regret, removing dependence on the domain diameter.
- Delayed ONS with adaptive learning rate achieves min{d_max n ln T, sqrt(d_tot)} + n ln T regret for exp-concave losses, the first such logarithmic-type delayed bound for exp-concave losses according to the authors.
- Experiments on synthetic streams show the proposed methods outperform DOGD and BOLD-based reductions for exp-concave and online linear regression settings under two delay regimes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use delayed FTRL for strongly convex losses | Strongly convex OCO with delayed feedback · Strongly convex OCO with delayed feedback | regret bound: $\mathcal{O} \left ( \min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}+\ln T\right)$ versus $\mathcal{O}\left(\dmax\ln | Helped |
| use delayed FTRL for strongly convex losses | Strongly convex OCO · Strongly convex losses, experimental delay regimes | cumulative regret | Helped |
| use delayed FTRL instead of DOGD-SC | Strongly convex OCO · Strongly convex losses, experimental delay regimes | cumulative regret | Helped |
| use delayed FTRL instead of SDMD-RSC | Strongly convex OCO · Strongly convex losses, experimental delay regimes | cumulative regret | No clear effect |
| use delayed ONS with adaptive learning-rate tuning | Exp-concave OCO · Exp-concave losses, both delay regimes | cumulative regret | Helped |
| use delayed VAW with clipping and adaptive learning-rate tuning | Online linear regression · Online linear regression with delayed labels, both delay regimes | cumulative regret | Helped |
| use adaptive rather than constant or delay-total-specific learning-rate tuning (ablation) | Delayed ONS · Exp-concave OCO with delayed feedback | regret bound: $\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$ | Helped |
| clip the predicted label using the available label range (ablation) | Delayed VAW · Online linear regression with delayed labels | regret | Helped |
Surprising findings
- Empirically SDMD-RSC performs similarly to the proposed strongly convex method, and the authors argue its O(d_max ln T) analysis is loose, with a refined analysis giving the sigma_max-based bound.
Limitations
- Whether O(min{sigma_max n ln T, sqrt(d_tot)}) is achievable for exp-concave losses remains open.
- Adaptive learning rate requires knowing timestamps of received gradients to compute d_max^{<=t}.
- Experiments are limited to synthetic data with T=10000 and 20 trials.
Experimental setup
Datasets: synthetic linear regression streams with uniform and heavy-tailed delays
Benchmarks: synthetic delayed OCO streams (T=10000)
Metrics: cumulative regret standard deviation over 20 trials
Baselines: DOGD DOGD-SC SDMD-RSC BOLD-OGD BOLD-ONS BOLD-VAW
Builds on: Online Newton Step Vovk-Azoury-Warmuth forecaster Delayed Online Gradient Descent BOLD
Closest papers by meaning
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.93)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.93)
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.92)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.92)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.90)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.90)
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.