Safe Online Convex Optimization with Heavy-Tailed Observation Noises

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.