Multi-Objective min-max Online Convex Optimization

Abstract

Online Convex Optimization (OCO) traditionally deals with a single loss function per round, but modern applications often involve multiple conflicting objectives like accuracy and latency. This thesis investigates Multi-Objective min-max OCO, where the learner's goal is to minimize the maximum cumulative loss across multiple convex objective functions over a finite time horizon. The performance benchmark is a strict static offline optimal algorithm that knows all functions in advance. A major challenge in this formulation is the non-additive nature of the max operator. Furthermore, we demonstrate that achieving sublinear min-max static regret is impossible in a fully adversarial setting. Consequently, the focus shifts to a stochastic independent and identically distributed (i.i.d.) input model, where the loss functions are drawn from an unknown joint distribution. To solve this, we propose the ``Hedge+OGD'' algorithm. This approach utilizes the Hedge algorithm to dynamically update a probability distribution over the conflicting objectives, and employs projected OGD to optimize the resulting weighted surrogate loss function at each step. Theoretical analysis proves that Hedge+OGD achieves a sublinear expected min-max static regret bound of $\mathcal{O}(\sqrt{T \log T})$ in the general i.i.d. case, and $\mathcal{O}(\sqrt{T})$ under specific functional conditions such as linear losses. Ultimately, this work provides a robust framework for fair and balanced multi-objective sequential decision-making.