Unconstrained Robust Online Convex Optimization

This paper considers the problem of online linear optimization with possibly corrupted gradients in an unbounded domain. For this problem, the authors further investigated two setups: known gradient upper bound $G$ and unknown $G$. For the first case, the authors obtained an $O(\|u\| G (\sqrt{T} + k))$, where $\|u\|$ denotes the norm of the unknown comparator that appeared in the definition of regret, and $k$ serves as an upper bound for the number of corruptions or the magnitude of corruptions. Note that the number $k$ is known prior to the algorithm. The authors have also provided a corresponding lower bound to prove the optimality of the obtained guarantee. For the unknown gradient norm upper bound, the authors obtained the above regret with an additive $(\|u\|^2 + G^2) k$ overhead. Finally, the authors have also applied their results to the applications of stochastic convex optimization with corruptions and DRO to validate the effectiveness.

The authors study online convex optimization under corrupted gradient feedback in an unconstrained domain. The proposed algorithm requires prior knowledge of "a measure of total corruption" $k$ and achieves a regret bound of $\mathcal{O}(|| u || G (\sqrt{T} + k))$ for any comparator $u$, assuming the gradient norm bound $G$ is known for the uncorrupted rounds. If $G$ is not known, they propose a filtering approach to guarantee a regret bound of $(|| u ||^2 + G^2) k$. They also provide matching lower bounds (up to logarithmic factors) for any choice of $u$.

This paper studies algorithms with good regret guarantees in a modification of the classical (unconstrained) online convex optimization setting where (roughly, since the definition is more nuanced) $k$ of gradients can be arbitrarily corrupted. Previous work either studied stochastic corruptions and/or a setting where the feasible set of the algorithm/player is bounded. When the algorithm knows a bound $G$ on the norm of the gradients, this paper shows an algorithm whose regret guarantee against a comparator $u$ is (roughly) only a additive factor of $\tilde{O}(Gk \lVert u \rVert)$ worse compared to the regret guarantees of optimal algorithms in the uncorrupted setting. Furthermore, this paper also shows an algorithm that has similar regret guarantees even without prior knowledge of $G$, with an extra penalty of $\tilde{O}((\lVert u\rVert^2 + G^2)k)$ in the regret. Finally, the paper also provides matching lower bounds for the case of known $G$.

This paper studies unconstrained OCO with adversarial corruptions. The auhors provide algorithms that ensures $O(||u||G\sqrt{T}+||u||Gk)$ regret bound, where $k$ is the number of corruptions. They also provide matching lower bounds.

We appreciate reviewers' feedback and have updated the manuscript to incorporate critical changes labelled in red. We address commonly appeared questions here.

[Novelty] Main difference from Zhang and Cutkosky (2022):

Several reviewers addressed the concern that the similarity between this paper and Zhang and Cutkosky (2022), whose techniques indeed play an important role in our results.

In the known G case (sec 4.1), the primary challenge lay in reformulating the problem using clipping and $\tilde g_t^c$ in such a way that it was clear that the techniques of Zhang and Cutkosky (2022) would be applicable.

In the unknown G case (sec 5.2), there were significantly greater technical hurdles to overcome. In this case, the problem is that not only is $G$ unknown at the start of the game, it is never revealed even at the end of the game. We do make use of recent regularization schemes inspired by Zhang and Cutkosky (2022) and Cutkosky and Mhammedi (2024), but on their own would not have solved our problem because they also require knowledge of $G$, either up-front, at least after the current round.

To fix this, we add two new “maximum-tracking” schemes as well as adding a carefully-tuned quadratic regularizer $(\alpha_t + \beta_t)\|w_t\|^2$. As is usual with regularization, we want to add as little regularization as possible to achieve our goals. This is where our new maximum-tracking schemes come in - they enable us to identify rounds in which corruption has caused undue harm, and make corrections on-the-fly.

Specifically, filter tracks gradients provides $h_{t+1}$ to estimated $max_\{i \le t\} | g\_i |$ (although it only sees $\tilde{g}\_i$ not even $g_i$), and tracker keeps track of a slowly-changing estimate of $\max_t \|w\_t\|$ as $z_{t+1}$. As motivated in Eqn (10) until the end of page 8, filter controls ''truncation error'' and tracker controls ''corruption error''. The fundamental difference is that the round which incurs ''truncation error'' is completely predictable (denoted as $\bar{\mathcal{P}}$), but the latter is not since corruption can happen at every single round.

Those two mechanisms are critical and use different analysis techniques in order to achieve regret in Theorem 5. Roughly speaking, with reference to Eqn (14) we can show (details in Appendix I line 1611 - line 1727):

where $\alpha_t, \beta_t$ sequences are defined in Eqn (11) and (12). This is guaranteed by filter and tracker such that rounds that $\alpha\_t, \beta\_t >0$ are small to counteract with predictable rounds that incurs ''truncation error'' and potentially every single rounds which accumulating ''corruption error''.

Algebraically, to achieve the above goal in $**offset**$, we require $\alpha\_t, \beta\_t$ sequences to have interesting properties. Using $\alpha_t$ as an example, we want to achieve the following seemingly-impossible pair of identities:

$\sum_t \alpha_t = \tilde{O}(1), \sum_{t: \alpha_t \neq 0} \frac{1}{\alpha} \le \tilde{O}(\log(h_T / h_1))$

The first inequality was achieved by Cutkosky and Mhammedi (2024), but the the second is the key in achieving the desired bound for $**offset**$ and is completely new. Achieving both bounds simultaneously is not trivial from both algorithm design and analysis point of view.

Clarity of Presentation regarding to Unknown G case:

We appreciate the reviewers' feedback regarding the presentation of Section 5. To address these concerns, we have revised the manuscript to clarify the connection of section 5.1 to the main results, and the key takeaways needed for the following section. For section 5.2, we have updated the ordering of some equations, which better connects section 5.1

Presentation of Algorithm 2:

As reviewer 6WrH spotted, Algorithm 2 involves our new techniques along with several different reductions. Specifically, we employed Cutkosky & Orabona (2018), Cutkosky (2019b) and Cutkosky and Mhammedi (2024) due to specific technical challenges needed to overcome. That means it is not identical to Cutkosky and Mhammedi (2024) section 3.3 (their algorithm 2). We have updated the manuscript with highlights in linking algorithm lines with each reduction.

Confusion in Switching between $\mathbf{R}$ and $\mathbf{R}^d$:

The reduction technique from Cutkosky & Orabona (2018) is standard in designing unconstrained online learning algorithms operating on $\mathcal{R}^d$, allowing us to focus on learners in $\mathcal{R}$. Although we stated in lines 189-191 that Sections 4.1 and 5 consider $\mathcal{W} = \mathbf{R}$ with results extending to $\mathcal{W} = \mathbf{R}^d$, we will make the entire main text as $\mathcal{W} = \mathbf{R}$ to avoid further confusion.

This paper addresses the problem of unconstrained online convex optimization (OCO) with adversarial corruptions, providing algorithms that offer regret bounds dependent on the number of corruptions. The paper presents results for two cases: when the gradient norm upper bound is known and when it is unknown, along with matching lower bounds. The findings are applied to stochastic convex optimization and distributionally robust optimization (DRO).

Reviewers appreciated the novel problem and valuable theoretical contributions of the paper but raised concerns about the heavy reliance on existing techniques, such as those from Zhang & Cutkosky 2022. The presentation was found to be unclear in sections dealing with the unknown gradient norm, making it difficult to distinguish the paper's novel contributions. Additionally, reviewers emphasized the need for clearer examples and a more thorough explanation of assumptions to improve the overall clarity and impact of the paper.

Reject