# Multi-Objective textitmin-max Online Convex Optimization

arXiv: https://arxiv.org/abs/2510.13560 · HTML: https://mlsanity.com/paper/2510.13560/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 15 Oct 2025.

## Builds on (most cited first, 25 of 25)

- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [The Frontiers of Fairness in Machine Learning](https://mlsanity.com/paper/1810.08810/) (2018)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Multi-Target Tracking Using Recurrent Neural Networks](https://mlsanity.com/paper/1604.03635/) (2016)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Enabling Long-term Fairness in Dynamic Resource Allocation](https://mlsanity.com/paper/2208.05898/) (2022)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization](https://mlsanity.com/paper/2301.09808/) (2023)
- [Beyond tildeO(√T) Constraint Violation for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2505.06709/) (2025)
- [O(√T) Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization](https://mlsanity.com/paper/2502.05019/) (2025)
- [Multi-Objective Non-parametric Sequential Prediction](https://mlsanity.com/paper/1703.01680/) (2017)

## Abstract (arXiv)

In this paper, we broaden the horizon of online convex optimization (OCO), and consider multi-objective OCO, where there are K distinct loss function sequences, and an algorithm has to choose its action at time t, before the K loss functions at time t are revealed. To capture the tradeoff between tracking the K different sequences, we consider the it min-max regret, where the benchmark (optimal offline algorithm) takes a static action across all time slots that minimizes the maximum of the total loss (summed across time slots) incurred by each of the K sequences. An online algorithm is allowed to change its action across time slots, and its it min-max regret is defined as the difference between its it min-max cost and that of the benchmark. The it min-max regret is a stringent performance measure and an algorithm with small regret needs to `track' all loss functions simultaneously. We first show that with adversarial input, it min-max regret scales linearly with the time horizon T for any online algorithm. Consequently, we consider a stochastic i.i.d. input model where all loss functions are i.i.d. generated from an unknown joint distribution and propose a simple algorithm that combines the well-known it Hedge and online gradient descent (OGD) and show via a remarkably simple proof that its expected it min-max regret is O(√T log (T K)). Analogous results are also derived for Martingale difference and Markov input models.