Unconstrained Robust Online Convex Optimization

Jiujia Zhang, Ashok Cutkosky
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:74756-74786, 2025.

Abstract

This paper addresses online learning with ”corrupted” feedback. Our learner is provided with potentially corrupted gradients $\tilde g_t$ instead of the ”true” gradients $g_t$. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult “unconstrained” setting in which our algorithm must maintain low regret with respect to any comparison point $u \in \mathbb{R}^d$. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret $ \|u\|G (\sqrt{T} + k) $ when $G \ge \max_t \|g_t\|$ is known, where $k$ is a measure of the total amount of corruption. When $G$ is unknown we incur an extra additive penalty of $(\|u\|^2+G^2) k$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-zhang25o, title = {Unconstrained Robust Online Convex Optimization}, author = {Zhang, Jiujia and Cutkosky, Ashok}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {74756--74786}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/zhang25o/zhang25o.pdf}, url = {https://proceedings.mlr.press/v267/zhang25o.html}, abstract = {This paper addresses online learning with ”corrupted” feedback. Our learner is provided with potentially corrupted gradients $\tilde g_t$ instead of the ”true” gradients $g_t$. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult “unconstrained” setting in which our algorithm must maintain low regret with respect to any comparison point $u \in \mathbb{R}^d$. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret $ \|u\|G (\sqrt{T} + k) $ when $G \ge \max_t \|g_t\|$ is known, where $k$ is a measure of the total amount of corruption. When $G$ is unknown we incur an extra additive penalty of $(\|u\|^2+G^2) k$.} }
Endnote
%0 Conference Paper %T Unconstrained Robust Online Convex Optimization %A Jiujia Zhang %A Ashok Cutkosky %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-zhang25o %I PMLR %P 74756--74786 %U https://proceedings.mlr.press/v267/zhang25o.html %V 267 %X This paper addresses online learning with ”corrupted” feedback. Our learner is provided with potentially corrupted gradients $\tilde g_t$ instead of the ”true” gradients $g_t$. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult “unconstrained” setting in which our algorithm must maintain low regret with respect to any comparison point $u \in \mathbb{R}^d$. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret $ \|u\|G (\sqrt{T} + k) $ when $G \ge \max_t \|g_t\|$ is known, where $k$ is a measure of the total amount of corruption. When $G$ is unknown we incur an extra additive penalty of $(\|u\|^2+G^2) k$.
APA
Zhang, J. & Cutkosky, A.. (2025). Unconstrained Robust Online Convex Optimization. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:74756-74786 Available from https://proceedings.mlr.press/v267/zhang25o.html.

Related Material