.png){kind=icon}
.png){kind=icon}
Return
Switching constrained OCO with predictions and feedback delays
.png){kind=icon}
PRE
AI
DOI：10.1016/j.peva.2025.102524.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We examine Online Convex Optimization (OCO) problems with feedback delay and a strict limit on decision switching, which exists in applications such as smart grid and learning. Existing algorithms developed for traditional OCO struggle in this setting, often violating switching constraints or incurring high regrets, as evidenced by simulations. In this paper, we establish a new algorithm, Follow-the-Maximally-Coupled-Latest-Leader (FMCLL), achieving a near-optimal regret of O(T/S) for such problems with delayed feedbacks and a bound of O(T/S - tau) for problems with predictions of tau rounds, even though the player is only allowed to move at most.. times in expectation across T rounds. FMCLL meets performance bounds in scenarios with delays and predictions by using maximal coupling sampling to inform algorithm design for switching-constrained problems. To better apply our framework to practical applications, we also extend the algorithm and results to the bandit feedback setting. Simulations demonstrate FMCLL's superiority over traditional Gradient Descent or Follow-the-Leader algorithms, excelling under adversarial or stochastic losses and reducing constraint violations.
Keywords:
Online Convex Optimization
Feedback delay
Adaptive online algorithms
Regret minimization
Journal
P
IF:
0.8
Papers:
38
Citations:
851