Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation
This work addresses the problem of efficient online optimization with limited information for applications requiring low computational overhead, though it is incremental as it builds on existing switching cost frameworks.
The paper tackles online convex optimization with switching costs under a frugal information setting, where only one function evaluation and gradient are available per round, and achieves optimal order-wise competitive ratios for linear switching costs and a quadratic growth in competitive ratio with noise magnitude for noisy gradients.
Online convex optimization with switching cost is considered under the frugal information setting where at time $t$, before action $x_t$ is taken, only a single function evaluation and a single gradient is available at the previously chosen action $x_{t-1}$ for either the current cost function $f_t$ or the most recent cost function $f_{t-1}$. When the switching cost is linear, online algorithms with optimal order-wise competitive ratios are derived for the frugal setting. When the gradient information is noisy, an online algorithm whose competitive ratio grows quadratically with the noise magnitude is derived.