Exploiting Curvature in Online Convex Optimization with Delayed Feedback

• URL: http://arxiv.org/abs/2506.07595v1
• Date: Mon, 09 Jun 2025 09:49:54 GMT
• Title: Exploiting Curvature in Online Convex Optimization with Delayed Feedback
• Authors: Hao Qiu, Emmanuel Esposito, Mengxiao Zhang,
• Abstract summary: We study the online convex optimization problem with curved losses and delayed feedback.<n>We propose a variant of follow-the-regularized-leader that obtains regret of order $minsigma_maxln T, sqrtd_mathrmtot$.<n>We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning.
• Score: 6.390468088226495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we study the online convex optimization problem with curved losses and delayed feedback. When losses are strongly convex, existing approaches obtain regret bounds of order $d_{\max} \ln T$, where $d_{\max}$ is the maximum delay and $T$ is the time horizon. However, in many cases, this guarantee can be much worse than $\sqrt{d_{\mathrm{tot}}}$ as obtained by a delayed version of online gradient descent, where $d_{\mathrm{tot}}$ is the total delay. We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$, where $\sigma_{\max}$ is the maximum number of missing observations. We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret $\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$ where $n$ is the dimension. To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses. We further consider the problem of unconstrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury-Warmuth forecaster with a clipping trick. Finally, we implement our algorithms and conduct experiments under various types of delay and losses, showing an improved performance over existing methods.

Related papers

• Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
  We study online learning with oblivious delays under a novel clairvoyance'' that limits how many past rounds can be tracked simultaneously for delayed feedback.<n>Our algorithms achieve minimax regrets across all capacity levels, with performance degrading gracefully under suboptimal capacity.
  arXiv  Detail & Related papers  (2025-03-25T17:20:39Z)
• Full Swap Regret and Discretized Calibration [18.944031222413294]
  We study the problem of minimizing swap regret in structured normal-form games.<n>We introduce a new online learning problem we call emphfull swap regret minimization<n>We also apply these tools to the problem of online forecasting to calibration error.
  arXiv  Detail & Related papers  (2025-02-13T13:49:52Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  We study Online Convex Optimization (OCO) with adversarial constraints.<n>We focus on a setting where the algorithm has access to predictions of the loss and constraint functions.<n>Our results show that we can improve the current best bounds of $ O(sqrtT) $ regret and $ tildeO(sqrtT) $ cumulative constraint violations.
  arXiv  Detail & Related papers  (2024-12-11T03:06:42Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  We investigate the dynamic regret of online Frank-Wolfe (OFW), which is an efficient projection-free algorithm for online convex optimization. In this paper, we derive improved dynamic regret bounds for OFW by extending the fast convergence rates of FW from offline optimization to online optimization.
  arXiv  Detail & Related papers  (2023-02-11T07:19:51Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  We propose a variant of the drift-plus-penalty algorithm that guarantees $O(sqrtT)$ expected regret and zero constraint violation. Our algorithm is oblivious to the length of the time horizon $T$, in contrast to the vanilla drift-plus-penalty method.
  arXiv  Detail & Related papers  (2023-01-26T18:04:26Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  We consider optimization with delayed gradients where, at each time stept$, the algorithm makes an update using a stale computation - d_t$ for arbitrary delay $d_t gradient. Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.
  arXiv  Detail & Related papers  (2021-06-22T15:50:45Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  We investigate the problem of online convex optimization with unknown delays. We first extend the delayed variant of OGD for strongly convex functions. We establish a better regret bound of $O(dlog T)$, where $d$ is the maximum delay.
  arXiv  Detail & Related papers  (2021-03-21T10:16:15Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems [14.924672048447334]
  We propose an optimistic Newton method for the case when the first and second order information of the function sequence is predictable. By using multiple gradients for OGD, we can achieve an upper bound of $O(minC*_2,T,V_T)$ on regret.
  arXiv  Detail & Related papers  (2020-06-06T16:37:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.