Unconstrained Robust Online Convex Optimization
Jiujia Zhang, Ashok Cutkosky · 2025
Read Unconstrained Robust Online Convex Optimization by Jiujia Zhang, Ashok Cutkosky (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12781.txt.
Introduction
Zhang and Cutkosky studied online learning with corrupted feedback in twenty twenty-five. In online convex optimization, a learner adjusts step by step from gradient signals, which point toward improvement. Here those signals may be damaged by outliers, mislabeled data, or even attack, with no assumptions on how the damage arises.
They focus on the unconstrained setting, where the comparison point can sit anywhere. That setting is far harder: tiny corruption can cause huge regret in older algorithms, meaning large losses versus the best fixed choice. Their algorithms bound regret using the size of the comparison point, the largest gradient, time, and a measure of total corruption. When that gradient bound is unknown, an extra cost appears but the guarantee still holds.
Catalog record
| CREATOR | Jiujia Zhang, Ashok Cutkosky |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-12781
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unconstrained Robust Online Convex Optimization Jiujia Zhang, Ashok Cutkosky Abstract This paper addresses online learning with “corrupted” feedback. Our learner is provided with potentially corrupted gradients g ~ t \tilde{g}_{t} instead of the “true” gradients g t 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 ∈ ℝ d 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 ( T + k ) \|u\|G(\sqrt{T}+k) when G ≥ max t ‖ g t ‖ G\geq\max_{t}\|g_{t}\| is known, where k k is a measure of the total amount of corruption. When G G is unknown we incur an extra additive penalty of ( ‖ u ‖ 2 + G 2 ) k (\|u\|^{2}+G^{2})k . 1 Introduction In this paper, we consider unconstrained online convex optimization (OCO) under the presence of adversarial corruptions. In general, OCO is a framework in which a learner iteratively outputs a prediction w_{t}\in\mathcal{W} , then observes a vector g_{t}=\nabla\ell_{t}(w_{t}) for some convex loss function \ell_{t}:\mathcal{W}\to\mathbb{R} , and then incurs a loss of \ell_{t}(w_{t}) . The learner’s performance over a time horizon T is evaluated by the regret relative to a fixed competitor u\in\mathcal{W} , denoted as R_{T}(u) : \displaystyle R_{T}(u):=\sum_{t=1}^{T}\langle g_{t},w_{t}-u\rangle\geq\sum_{t=1}^{T}\ell_{t}(w_{t})-\ell_{t}(u) The inequality above follows by convexity of \ell_{t} . Classical results in this field consider a bounded domain \mathcal{W} with known diameter D and a Lipschitz bound G\geq\max_{t}\|g_{t}\| . In this setting, the optimal bound is R_{T}(u)\leq O(GD\sqrt{T}) ( Zinkevich 2003 ; Abernethy et al. 2008 ) . Our work focuses on the unconstrained case \mathcal{W}=\mathbb{R}^{d} , where it is typical to aim for a regret guarantee that scales not with a uniform diameter bound D , but with the norm of the comparator \|u\| . Such bounds are often called “comparator adaptive” (because they adapt to the comparator u ), or “parameter-free” (because this adaptivity suggests that the algorithms require less hyperparameter tuning). In this unconstrained setting, the classical algorithms achieve R_{T}(u)=\tilde{O}(\|u\|G\sqrt{T}) ( Mcmahan & Streeter 2012 ; McMahan & Orabona 2014 ; Orabona & Pál 2016 ; Orabona 2014 ) (which is also optimal). We are interested in a harder variant of the OCO framework with “corrupted” gradients. Specifically, instead of any direct information about the function \ell_{t} , after each round the learner is provided with a vector \tilde{g}_{t} that should be interpreted as an estimate of g_{t}=\nabla\ell_{t}(w_{t}) . Our aim is to obtain a regret that scales as \|u\|G(\sqrt{T}+k) for all u\in\mathcal{W} , where k is some measure of the degree to which \tilde{g}_{t}\neq g_{t} that will be formally defined in Section 2 . Roughly speaking, k can be interpreted as the number of rounds in which \tilde{g}_{t}\neq g_{t} . Notably, the desired rate is robust to adversarial corruptions in the sense that it allows k=O(\sqrt{T}) before the bound becomes worse than the optimal result without corruptions. Our dual challenges of corrupted \tilde{g}_{t} and unconstrained \mathcal{W} are naturally motivated by problems in practice. The unconstrained setting is ubiquitous in machine learning - consider the classical logistic regression setting, for which it is unusual to impose constraints. The corrupted \tilde{g}_{t} in contrast is less commonly studied, but represents a common practical issue: the computed gradients may not be good estimates of a “true” gradient, either due to the presence of statistical outliers, numerical precision issues in the gradient computation, or mislabeled or otherwise damaged data. We distinguish two different settings in our results: one in which the algorithm is provided with prior knowledge of a number G\geq\max_{t}\|g_{t}\| , and one in which it is not. This is a common dichotomy in unconstrained OCO, even without corruptions. In the former case, the classical result of \tilde{O}(\|u\|G\sqrt{T}) is obtainable, while in the latter case it is not: instead the optimal results are R_{T}(u)\leq\tilde{O}(\|u\|\max_{t}\|g_{t}\|\sqrt{T}+\|u\|^{3}\max_{t}\|g_{t}\|) ( Cutkosky 2019 ; Mhammedi & Koolen 2020 ) , or \tilde{O}(\|u\|\max_{t}\|g_{t}\|\sqrt{T}+\|u\|^{2}+\max_{t}\|g_{t}\|^{2}) by Cutkosky & Mhammedi 2024 . The later excels particularly whenever G is not excessively large: G\leq\|u\|\sqrt{T} . To the best of our knowledge, the setting of unconstrained OCO with corruptions has not been studied before. Perhaps the closest works to ours are Zhang & Cutkosky 2022 ; Jun & Orabona 2019 ; van der Hoeven 2019 and van Erven et al. 2021 . ( Zhang & Cutkosky 2022 ; Jun & Orabona 2019 ; van der Hoeven 2019 ) study the unconstrained setting, but assume that \tilde{g}_{t} is a random value with \mathop{\mathbb{E}}[\tilde{g}_{t}]=g_{t} . In contrast, we assume no such stochastic structure on \tilde{g}_{t} . On the other hand, van Erven et al. 2021 does not make any assumptions about the nature of the corruptions, but assumes that \mathcal{W} has finite diameter D . They achieve a regret of O(DG(\sqrt{T}+k)) . Our development will borrow some ideas from van Erven et al. 2021 with the aim to bound R_{T}(u) , but we face unique difficulties. As detailed in Section 3 , the unconstrained setting means that even very small corruptions could have dire consequences (unlike in the constrained setting). Moreover, if the Lipschitz constant G is not known, the problem becomes even more challenging; as detailed in Section 6.1 , prior methods for handling unknown G do not apply because we never learn G even at the end of all T rounds. The notion of adversarial corruption is common in the field of robust statistics, with early efforts focusing primarily on the presence of outliers in linear regression ( Huber 2004 ; Cook 2000 ; Thode 2002 ) . These insprired broader application in machine learning, asuch as Robust PCA ( Candès et al. 2011 ) , anomaly detection ( Raginsky et al. 2012 ; Delibalta et al. 2016 ; Zhou & Paffenroth 2017 ; Sankararaman et al. 2022 ) , robust regression ( Klivans et al. 2018 ; Cherapanamjeri et al. 2020 ; Chen et al. 2022 ) , and mean estimation ( Lugosi & Mendelson 2021 ) . For a comprehensive review of recent advances in this area, see Diakonikolas & Kane 2019 . Adversarial corruption has also been studied in iterative optimization setting other than OCO, such as in stochastic bandits ( Lykouris et al. 2018 ; Gupta et al. 2019 ; Ito 2021 ; Agarwal et al. 2021 ) and stochastic optimization ( Chang et al. 2022 ; Sankararaman & Narayanaswamy 2024 ) . Contributions and Organization In the case that the algorithm is given prior knowledge of G , we provide an algorithm that achieves R_{T}(u)=\tilde{O}(\|u\|G(\sqrt{T}+k)) in Section 5.1 , with a matching lower bound (see Section 5.2 ). Alternatively, when G is unknown, a regret bound with an additional penalty of (\|u\|^{2}+G^{2})k is attained (see Section 6.3 ). Meanwhile, we provide two specific applications of our results in Appendix D . First, we show that our method can be used to solve stochastic convex optimization problems in some of the