Safe Online Convex Optimization with Heavy-Tailed Observation Noises
Authors: Yunhao Yang, Bo Xue, Yunzhi Hao, Ying Li, Yuanyu Wan
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | we investigate SOCO under heavy-tailed observation noises that admit only finite (1 + ϵ)-th moments for some ϵ (0, 1], and develop two novel algorithms that enjoy an O(T cϵ) regret bound where cϵ = (1 + ϵ)/(1 + 2ϵ), while satisfying the safety constraints in all rounds with high probability. Specifically, to estimate the unknown safety constraints under heavy-tailed noises, our first algorithm divides the exploration phase of SO-PGD into several groups, and takes the median of means of the estimations within these groups. For the same goal, our second algorithm refines SO-PGD by simply truncating the extreme values of the safety constraints received during the exploration phase. Note that both the median-of-means and truncation techniques have been extensively utilized to address bandits with heavy-tailed feedback another paradigm of online learning (Shao et al. 2018; Lu et al. 2019; Xue et al. 2021, 2023). However, to the best of our knowledge, this is the first work to demonstrate their benefits in SOCO with heavy-tailed observation noises. |
| Researcher Affiliation | Collaboration | 1School of Software Technology, Zhejiang University, Ningbo, China 2Department of Computer Science, City University of Hong Kong, Hong Kong, China 3Big Graph Center & School of Computer and Computing Science, Hangzhou City University, Hangzhou, China 4State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China 5Bangsheng Technology Co., Ltd., Hangzhou, China 6Hangzhou High-Tech Zone (Binjiang) Institute of Blockchain and Data Security, Hangzhou, China |
| Pseudocode | Yes | Algorithm 1: SO-PGD Algorithm 2: SOMM Algorithm 3: SOTM |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide a link to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and mathematical proofs. It does not conduct experiments using any specific dataset, therefore, no information regarding dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets, therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper presents theoretical algorithms and mathematical proofs, and does not include any experimental results that would require specific hardware for execution. |
| Software Dependencies | No | The paper focuses on theoretical development and mathematical proofs of algorithms, and therefore does not specify any software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithm design and mathematical proofs, and does not include an experimental setup with specific hyperparameter values or training configurations. |