2025/06/09 by Hao Qiu, Qiu, Hao, Emmanuel Esposito +3 · 1 citation
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2506.07595
openalex publication_date 2025/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 dmax ln T, where dmax is the maximum delay and T is the time horizon. However, in many cases, this guarantee can be much worse than √dtot as obtained by a delayed version of online gradient descent, where dtot is the total delay. We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order min\σmaxln T, √dtot\, where σ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\dmax nln T, √dtot\ 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.