Safe Online Convex Optimization with Heavy-Tailed Observation Noises

Yunhao Yang; Bo Xue; Yunzhi Hao; Ying Li; Yuanyu Wan

doi:10.1609/aaai.v39i21.34357

Safe Online Convex Optimization with Heavy-Tailed Observation Noises

Yunhao Yang
, Bo Xue
, Yunzhi Hao
, Ying Li
, Yuanyu Wan^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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²/³). 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.

© 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Original language	English
Title of host publication	Proceedings of the 39th AAAI Conference on Artificial Intelligence
Editors	Toby Walsh, Julie Shah, Zico Kolter
Publisher	AAAI Press
Pages	22047-22055
Volume	39
ISBN (Print)	1-57735-897-X, 978-1-57735-897-8
DOIs	https://doi.org/10.1609/aaai.v39i21.34357
Publication status	Published - 2025
Event	39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025) - Pennsylvania Convention Center , Philadelphia, United States Duration: 25 Feb 2025 → 4 Mar 2025 https://aaai.org/conference/aaai/aaai-25/

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Publisher	Association for the Advancement of Artificial Intelligence
ISSN (Print)	2159-5399

Conference

Conference	39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025)
Abbreviated title	AAAI-25
Place	United States
City	Philadelphia
Period	25/02/25 → 4/03/25
Internet address	https://aaai.org/conference/aaai/aaai-25/

Funding

This work was partially supported by the Pioneer R&D Program of Zhejiang (No.2024C01021), and the National Natural Science Foundation of China (62306275). The authors would like to thank the anonymous reviewers for their helpful comments.

Access Output

10.1609/aaai.v39i21.34357

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Yang, Y., Xue, B., Hao, Y., Li, Y., & Wan, Y. (2025). Safe Online Convex Optimization with Heavy-Tailed Observation Noises. In T. Walsh, J. Shah, & Z. Kolter (Eds.), Proceedings of the 39th AAAI Conference on Artificial Intelligence (Vol. 39, pp. 22047-22055). (Proceedings of the AAAI Conference on Artificial Intelligence). AAAI Press. https://doi.org/10.1609/aaai.v39i21.34357

@inproceedings{711d061dd5f24170ba51ba387dabb1c0,

title = "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 (T2/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 (Tcϵ) 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. {\textcopyright} 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.",

author = "Yunhao Yang and Bo Xue and Yunzhi Hao and Ying Li and Yuanyu Wan",

year = "2025",

doi = "10.1609/aaai.v39i21.34357",

language = "English",

isbn = "1-57735-897-X",

volume = "39",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

pages = "22047--22055",

editor = "Walsh, \{Toby \} and Julie Shah and Zico Kolter",

booktitle = "Proceedings of the 39th AAAI Conference on Artificial Intelligence",

note = "39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025), AAAI-25 ; Conference date: 25-02-2025 Through 04-03-2025",

url = "https://aaai.org/conference/aaai/aaai-25/",

}

Yang, Y, Xue, B, Hao, Y, Li, Y & Wan, Y 2025, Safe Online Convex Optimization with Heavy-Tailed Observation Noises. in T Walsh, J Shah & Z Kolter (eds), Proceedings of the 39th AAAI Conference on Artificial Intelligence. vol. 39, Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, pp. 22047-22055, 39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025), Philadelphia, Pennsylvania, United States, 25/02/25. https://doi.org/10.1609/aaai.v39i21.34357

Safe Online Convex Optimization with Heavy-Tailed Observation Noises. / Yang, Yunhao; Xue, Bo; Hao, Yunzhi et al.
Proceedings of the 39th AAAI Conference on Artificial Intelligence. ed. / Toby Walsh; Julie Shah; Zico Kolter. Vol. 39 AAAI Press, 2025. p. 22047-22055 (Proceedings of the AAAI Conference on Artificial Intelligence).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Safe Online Convex Optimization with Heavy-Tailed Observation Noises

AU - Yang, Yunhao

AU - Xue, Bo

AU - Hao, Yunzhi

AU - Li, Ying

AU - Wan, Yuanyu

PY - 2025

Y1 - 2025

N2 - 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 (T2/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 (Tcϵ) 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. © 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

AB - 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 (T2/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 (Tcϵ) 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. © 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

UR - https://www.scopus.com/pages/publications/105003993437

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105003993437&origin=recordpage

U2 - 10.1609/aaai.v39i21.34357

DO - 10.1609/aaai.v39i21.34357

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 1-57735-897-X

SN - 978-1-57735-897-8

VL - 39

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 22047

EP - 22055

BT - Proceedings of the 39th AAAI Conference on Artificial Intelligence

A2 - Walsh, Toby

A2 - Shah, Julie

A2 - Kolter, Zico

PB - AAAI Press

T2 - 39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025)

Y2 - 25 February 2025 through 4 March 2025

ER -

Safe Online Convex Optimization with Heavy-Tailed Observation Noises

Abstract

Publication series

Conference

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this