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.

Online convex optimization is the standard framework for online decision making problems, and performance is usually measured by regret against the best fixed decision in hindsight. When the environment is non-stationary, this measure is too weak. Switching regret addresses this by splitting the timeline into segments and comparing the learner to the best decision on each segment. Prior work achieved the optimal switching regret for general convex functions, but it was unknown whether the same was possible for other types of functions, such as exp-concave or strongly convex functions, where faster rates are usually expected. We answer this question by proposing IRESET, where we provide a novel analysis for those types of functions. Our main contribution is a new analysis based on a segment-tree structure that expresses the bound in terms of segment lengths. As a result, IRESET achieves nearly-optimal logarithmic switching regret for strongly convex and exp-concave functions, improving the key factor from $\log T$ to the logarithm of the segment length. We also give a universal version that handles all three function types at once without knowing the type in advance.