Safe Online Convex Optimization with Heavy-Tailed Observation Noises

Abstract

We investigate safe online convex optimization (SOCO), where each decision must satisfy a set of unknown linear constraints. Assuming that the unknown constraints can be observed with a sub-Gaussian noise for each chosen decision, previous studies have established a high-probability regret bound of O(T^{2/3}). However, this assumption may not hold in many practical scenarios. To address this limitation, in this paper, we relax the assumption to allow any noise that admits finite (1+ε)-th moments for some ε∈(0,1], and propose two algorithms that enjoy an O(T^{c_ε}) regret bound with high probability, where T is the time horizon and c_ε=(1+ε)/(1+2ε). The key idea of our two algorithms is to respectively utilize the median-of-means and truncation techniques to achieve accurate estimation under heavy-tailed noises. To the best of our knowledge, these are the first algorithms designed to handle SOCO with heavy-tailed observation noises.