2025/07/05 by Shah, Harsh, Chandrasekhar, Purna, Vaze, Rahul
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2507.04133
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.