Dynamic Regret in Outlier-Oblivious Online Optimization using Nonconvex Robust Losses

Adarsh Barik, Anand Krishna, Vincent Y. F. Tan
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:328-363, 2026.

Abstract

We study a robust online convex optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of rounds $k$, unknown to the learner. In contrast to prior works, we consider both bounded and unbounded domains and allow for large gradients for the losses without relying on a Lipschitz assumption or any prior knowledge of $k$. We introduce the Log Exponential Adjusted Robust and iNvex ({LEARN}) loss, a non-convex (invex) robust loss function to mitigate the effects of outliers and develop a robust variant of the online gradient descent algorithm by leveraging the {LEARN} loss. We establish dynamic regret guarantees with respect to the uncorrupted rounds and conduct experiments to validate our theory. Our upper bound matches the existing lower bound in the bounded domains and is tight (up to logarithmic factors) in the unbounded domains. Furthermore, we present a unified analysis framework for developing online optimization algorithms for non-convex (invex) losses, utilizing it to provide regret bounds with respect to the {LEARN} loss, which may be of independent interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-barik26a, title = {Dynamic Regret in Outlier-Oblivious Online Optimization using Nonconvex Robust Losses}, author = {Barik, Adarsh and Krishna, Anand and Tan, Vincent Y. F.}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {328--363}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/barik26a/barik26a.pdf}, url = {https://proceedings.mlr.press/v337/barik26a.html}, abstract = {We study a robust online convex optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of rounds $k$, unknown to the learner. In contrast to prior works, we consider both bounded and unbounded domains and allow for large gradients for the losses without relying on a Lipschitz assumption or any prior knowledge of $k$. We introduce the Log Exponential Adjusted Robust and iNvex ({LEARN}) loss, a non-convex (invex) robust loss function to mitigate the effects of outliers and develop a robust variant of the online gradient descent algorithm by leveraging the {LEARN} loss. We establish dynamic regret guarantees with respect to the uncorrupted rounds and conduct experiments to validate our theory. Our upper bound matches the existing lower bound in the bounded domains and is tight (up to logarithmic factors) in the unbounded domains. Furthermore, we present a unified analysis framework for developing online optimization algorithms for non-convex (invex) losses, utilizing it to provide regret bounds with respect to the {LEARN} loss, which may be of independent interest.} }
Endnote
%0 Conference Paper %T Dynamic Regret in Outlier-Oblivious Online Optimization using Nonconvex Robust Losses %A Adarsh Barik %A Anand Krishna %A Vincent Y. F. Tan %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-barik26a %I PMLR %P 328--363 %U https://proceedings.mlr.press/v337/barik26a.html %V 337 %X We study a robust online convex optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of rounds $k$, unknown to the learner. In contrast to prior works, we consider both bounded and unbounded domains and allow for large gradients for the losses without relying on a Lipschitz assumption or any prior knowledge of $k$. We introduce the Log Exponential Adjusted Robust and iNvex ({LEARN}) loss, a non-convex (invex) robust loss function to mitigate the effects of outliers and develop a robust variant of the online gradient descent algorithm by leveraging the {LEARN} loss. We establish dynamic regret guarantees with respect to the uncorrupted rounds and conduct experiments to validate our theory. Our upper bound matches the existing lower bound in the bounded domains and is tight (up to logarithmic factors) in the unbounded domains. Furthermore, we present a unified analysis framework for developing online optimization algorithms for non-convex (invex) losses, utilizing it to provide regret bounds with respect to the {LEARN} loss, which may be of independent interest.
APA
Barik, A., Krishna, A. & Tan, V.Y.F.. (2026). Dynamic Regret in Outlier-Oblivious Online Optimization using Nonconvex Robust Losses. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:328-363 Available from https://proceedings.mlr.press/v337/barik26a.html.

Related Material