Safe Online Convex Optimization with Heavy-Tailed Observation Noises
Yunhao Yang, Bo Xue, Yunzhi Hao, Ying Li, Yuanyu Wan
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.
BibTeX
@article{Yang_Xue_Hao_Li_Wan_2025, title={Safe Online Convex Optimization with Heavy-Tailed Observation Noises}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34357}, DOI={10.1609/aaai.v39i21.34357}, abstractNote={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.}, number={21}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Yang, Yunhao and Xue, Bo and Hao, Yunzhi and Li, Ying and Wan, Yuanyu}, year={2025}, month={Apr.}, pages={22047-22055} }