Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation

Online convex optimization with switching cost is considered under the frugal information setting where at time t, before action xt is taken, only a single function evaluation and a single gradient is available at the previously chosen action xt-1 for either the current cost function ft or the most recent cost function ft-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.