Logarithmic Switching Regret for Online Convex Optimization

摘要

Online convex optimization in non-stationary environments has garnered considerable attention in the literature. Recently, Pasteris et al. (2024) investigate online convex optimization with the optimal switching regret, defined as the sum of the static regret over each segment, where the segmentation is an arbitrary partition of the entire time horizon. For general convex functions, their work has established an optimal switching regret bound. However, it remains open whether similar bounds are attainable for other types of convex functions, such as exponentially concave or strongly convex functions. In this paper, we affirmatively answer this question by proposing a novel meta-algorithm, termed IRESET, which is used to aggregate the decisions from a group of experts. The essence of our method lies in running multiple experts over a set of intervals, and then employing a meta-algorithm equipped with second-order bounds to sequentially combine their decisions. We leverage the segment tree structure to analyze the switching regret over the entire time horizon, and offer new insights into utilizing recursive equations over the segment tree. By choosing appropriate expert-algorithms for IRESET, our methods achieve logarithmic switching regret bounds for exponentially concave or strongly convex functions, respectively.