Second Order Path Variationals in Non-Stationary Online Learning

2022/05/04 by Baby, Dheeraj, Wang, Yu-Xiang · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2205.01921

Abstract

We consider the problem of universal dynamic regret minimization under exp-concave and smooth losses. We show that appropriately designed Strongly Adaptive algorithms achieve a dynamic regret of O(d² n^1/5 C_n^2/5 \vee d²), where n is the time horizon and C_n a path variational based on second order differences of the comparator sequence. Such a path variational naturally encodes comparator sequences that are piecewise linear -- a powerful family that tracks a variety of non-stationarity patterns in practice (Kim et al, 2009). The aforementioned dynamic regret rate is shown to be optimal modulo dimension dependencies and poly-logarithmic factors of n. Our proof techniques rely on analysing the KKT conditions of the offline oracle and requires several non-trivial generalizations of the ideas in Baby and Wang, 2021, where the latter work only leads to a slower dynamic regret rate of O(d^2.5n^1/3C_n^2/3 \vee d^2.5) for the current problem.

Cited by

• Dynamic Regret Reduces to Kernelized Static Regret

Related

• Optimal Dynamic Regret in Exp-Concave Online Learning
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond
• A closer look at temporal variability in dynamic online learning
• Online Learning with Continuous Variations: Dynamic Regret and\n Reductions
• Adaptive Online Learning in Dynamic Environments