Universal Online Optimization in Dynamic Environments via Uniclass Prediction
Recently, several universal methods have been proposed for online convex optimization which can handle convex, strongly convex and exponentially concave cost functions simultaneously. However, most of these algorithms have been designed with static regret minimization in mind, but this notion of regret may not be suitable for changing environments. To address this shortcoming, we propose a novel and intuitive framework for universal online optimization in dynamic environments. Unlike existing universal algorithms, our strategy does not rely on the construction of a set of experts and an accompanying meta-algorithm. Instead, we show that the problem of dynamic online optimization can be reduced to a uniclass prediction problem. By leaving the choice of uniclass loss function in the user's hands, they are able to control and optimize dynamic regret bounds, which in turn carry over into the original problem. To the best of our knowledge, this is the first paper proposing a universal approach with state-of-the-art dynamic regret guarantees even for general convex cost functions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite $p$-th central moment for some $p \in (1, 2]$. While static reg…
Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions
To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, …
Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
We consider a generalization of the celebrated Online Convex Optimization (OCO) framework with adversarial online constraints. In this problem, an online learner interacts with an adversary sequentially over multiple rou…
Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, …
Adaptive Variational Particle Filtering in Non-stationary Environments
Online convex optimization is a sequential prediction framework with the goal to track and adapt to the environment through evaluating proper convex loss functions. We study efficient particle filtering methods from the …