Unconstrained Robust Online Convex Optimization
Authors: Jiujia Zhang
Ashok Cutkosky
Venue: ICML 2025 poster (2025)
Keywords: online learning
corrupted feedback
comparator adaptive
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: This paper addresses unconstrained online learning with adversarially ''corrupted'' feedback.

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$.

The inequality above follows by convexity of 4, Classical results this field consider a bounded domain W with Unconstrained Robust Online Convex Optimization
Jiujia Zhang'
Ashok Cutkosky
Abstract
known diameter D and Lipschitz bound G 2 max; |l In this setting, the optimal bound is Rr(u) v (GDVT) (Zinkevich, 2003; Abernethy et al., 2008).
This paper addresses online learning with "cor- rupted" feedback. Our learner is provided with potentially corrupted gradients It instead of the "true" gradients 9r- We make 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 com- parison point [Rd. The unconstrained setting is significantly more challenging as existing al- gorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our al- gorithms guarantee regret [|u]|G[ + k)) when G 2 max; IIgell is known, where a measure of the total amount of corruption. When G is unknown we incur extra additive penalty of [[lul|2 G2)k.
Our work focuses on the unconstrained case W = R2, where is typical to aim for regret guarantee that scales not with a uniform diameter bound D, but with the norm of the comparator ||w/]] Such bounds are often called "comparator adaptive" (because they adapt to the compara- tor u), "parameter-free" (because this adaptivity sug- gests that the algorithms require less hyperparameter tun- ing). In this unconstrained setting, the classical algorithms achieve (u) = 2012; McMahan & Orabona, 2014; Orabona & Pál, 2;;6; Orabona, 2014) (which is also optimal).
(Memahan & Streeter,
We are interested in harder variant of the OCO framework with "corrupted" gradients. Specifically, instead of any direct information about the function é,, after each round the learner is provided with a vector ge that should be interpreted as an estimate of gr = Vlg(w)) Our aim is to obtain a regret that scales as ||u]]G([/ + k) for all u E W, where some measure of the degree to which 9. * 9: that will be formally defined in Section 2. Roughly speaking, k can be interpreted the number of rounds in which ğe # go- Notably, the desired rate is robust to adversarial corruptions in the sense that it allows k = O(vT) before the bound becomes worse than the optimal result without corruptions.
1. Introduction
In this paper, we consider unconstrained online convex opti- mization (OCO) under the presence of adversarial corrup- tions. In general, OCO is a framework in which a learner iter- atively outputs prediction wi E W, then observes a vector gi v (wx) for some convex loss function & W- R,, and then incurs loss of & (wx)) The learner's performance over time horizon T' is evaluated by the regret relative to fixed competitor E W, denoted as (r(:):
Our dual challenges of corrupted 9: and unconstrained W are naturally motivated by problems in practice. The uncon- strained setting is ubiquitous in machine learning consider the classical logistic regression setting, for which it is un- usual to impose constraints. The corrupted ğe 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 out- liers, numerical precision issues in the gradient computation, or mislabeled otherwise damaged data.
T Rr(w)= = Σ (gt, wi u) 2 Σ (ww)) - (u))
T
We distinguish two different settings in our results: one in which the algorithm is provided with prior knowledge of a number G 2 max, l|gell. and one in which it is not. This is a common dichotomy in unconstrained OCO, even without corruptions. In the former case, the classi- cal result of ([[lu]/GVT) obtainable, while in the latter case it is not: instead the optimal results are Rr(u) I
'Dpaatment of Electrical and Computer Engineering, Boston University, Boston, USA. Correspondence to: Jiujia Zhang <jiu- jiaz@bu.cdu>, bu.edu,, Ashok Cutkosky <ashok cutkosky.com>>
Proceedings of the 42 International Conference on Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Unconstrained Robust Online Convex Optimization
([Hii max, l1 IVV + ||u| max, [l (Cutkosky, 2019;
sults in Appendix D. First, we show that our method can be used to solve stochastic convex optimization problems in some of the gradient computations are altered in an ar- bitrary way. Second, we solve a natural "online" version of a distributionally robust optimization problem. Before providing our main results, we introduce notation and define our corruption model in Section 2.
Mhammedi & Koolen, 2020), or [[ max, [| lI VT
|ull² + max, |l by Cutkosky & Mhammedi (2024). The later excels particularly whenever G is not excessively large: G S ||u|vVT
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 set- ting, but assume that 9r is a random value with E[o+] = Jt- In contrast, we assume no such stochastic structure on ğt- On the other hand, van Erven et al. (2021) does not make any assumptions about the nature of the corruptions, but assumes that W has finite diameter D. They achieve gret of O(D((VT + k:). Our development will borrow some ideas from van Erven et al. (2021) with the aim to bound RT(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 challeng- ing; 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.
2. Notation and Problem Setup
Notation For each I, l W - R is convex function, where and W = Rd. Let we E W be iterates from some online learning algorithm and denote 9: = ( as the "true" (sub)gradient. Let dt be the the corrupted gradient observed by the learner. Define (() as the indicator func- tion, where 1 [TRUE]] to denote the cardinality of set. Let || denote the Eu- clidean norm. Denote RR+ = {ir E R : x 2 0). We define shorthand notation for sets [7]
1, [
0. We use |-1
21.2.....7 .T and
(a, T| = {a, a.,...., T for any E [T). We use B C [7) to denote an index set, and B = [T] \ B for its complement. We use O(-) to hide constant factors and (--) to additionally conceal any polylogarithmie factors.
Problem Setup Instead of the true gradients gr. our algo- rithms only receive potentially corrupted gradients g.. Two natural measures to quantify corruptions are:
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:
T
Kenant
Σ
1l + 3.}
(1)
Cook, 2000; Thode, 2002). These insprired broader appli- cation in machine learning, asuch as Robust PCA (Candès et al., 2011), 1), anomaly detection (Raginsky et al., 2012: Delibalta et al., 2016; Zhou & Paffenroth, 2017; Sankarara- man 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 comprehen- sive review of recent advances in this area, see Diakonikolas & Kane (2019).
1 T
kdeviition ==
Uige - rell
(2)
G
where G is a scalar that satisfies G > max, 11 and is often referred as the "Lipschitz constant". The metric Acount counts the rounds in which 9t # 9t but allowing for arbitrarily large deviations ll gel |l in those rounds. This suitable for detecting outlier effects and highlighted in studies such as (van Erven et al., 2021: Sankararaman & Narayanaswamy, 2024). Conversely, Rdeviation measures the cumulative devia- tion, accommodating corruption in every round, making it optimal for identifying subtle yet widespread errors or ma- licious activities, akin to the issues addressed in (Lykouris et al., 2018; Gupta et al., 2019; Ito, 2021: Agarwal et al., 2021; Chang et al., 2022).
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 Rr(u)= = Ó[[[]]]([T + k)) in Section 5.1, with matching lower bound (see Section 5.2). Alternatively, when G' is unknown, regret bound with an additional penalty of ([|ul + G2) is attained (see Section 6.3).
In order to provide a unified way study those two distinct corruption measures in Equation (1) and (2), we assume that our algorithm is provided with a number is that satisfies:
Meanwhile, we provide two specific applications of our re-
B := Ht E [T] : 11:: - gell > GHIS Sh
(3)
2

---

Unconstrained Robust Online Convex Optimization
Regrat comm compptorno
comuption)
Regrett corrpttin) Deggret cemrpption)
50
(with senupciant
300
20"
10"
20'
50
100
150
200
250
300
350
400
50
100
150
200
250
300
350
400
20
40
50
70
(a)
(b)
(c)
Figure 1. KT-bettor with ((w) |w 1| and comparator (a)-(b): 7 400 and corruption happens during t [300, 319]. (c):
Ratio between regrets with and without corruptions with various total corrupted rounds k [20, 30, 40, 50, 60, 70) and T = k²
and also:
The situation is much more difficult in the unconstrained setting. Algorithm for this setting typically produce out- puts w; that potentially grow exponentially fast in order to quickly compete with comparators that are very far from the starting point. However, this also means the algorithm is especially fragile corruption since the growth of we can be highly sensitive to deviations in || - rell- Even a small deviation could cause We to move extremely far away and therefore incur a very high regret. This phenomenon is illus- trated in Figure with the KT-bettor algorithm (Orabona Pál, 2016), which is standard example of unconstrained learner.
G Σ min (11:: rrll. S
(4)
Intuitively, denotes the rounds with a "large" amount of corruption. Notice that
|B < min (Recunts lideviation)
and
T Σ min (119: - 3ell. S min (Kicount Adeviation) )
In Figure we considered fe(w) = | 1| for all t. Figure 1a and 1b demonstrate k = 20 gradients being corrupted by setting 9: -9t during rounds f E 3300 300 + [300, 319] over a time span of k2 400. This results in an exponential deviation away from the comparator u = and so incurs a high regret. Finally, we show that this problem becomes exacerbated k increases by simulating k [20, 30, 40, 50, 60, 70] for T = k² in Figure Ic.
Hence, algorithm whose complexity depends l satis- fying Equation (3) and (4) can be used with either k kcomn or l = Kaeviation depending on which is more appropriate to the problem at hand.
1]
3. Challenges in Unconstrained Domaïn
Dealing with corruptions with an unconstrained domain is significantly more challenging than with bounded domain. As an illustration of the added difficutly, suppose the corruptions are so "small" that ||g. 9. |l < G for all t. Then in bounded W with a diameter D, an algorithm that completely ignores the possibility of corruptions and directly runs on ÿt will have low regret. This can be seen as follows: since ||u welll < for every u, wi E W, we have:
4. Robustification through Regularization
In this section, we outline our general egoorithmddsiige recipe. When receiving possibly corrupted gradients 9r. we first employ gradient clipping step with some threshold hy that outputs "clipped" version Gf, defined follows:
gi
min (he, llăcll)
(5)
T
gr, ui u)
5
(gt, Wi u)
Σ t=1
llge Bell ull
T
This preprocessing step "corrects" some corruption effect when hr is appropriately chosen. For example, in the case of h4 = G 2 max, || 9 then 9f is always "less corrupted" than gr. as |løf- - gell < g - gell- Then gi is used as a feed- back to an online learner, yielding the following expression
<
(Tt, We - u) KGD
In this case, I|u - w.ll || < prevents the algorithm from straying too far from the comparator u.
3

---

Unconstrained Robust Online Convex Optimization
for Rr(u):
hy G for all iterations in the definition of of (see Equa- tion (5)).
T
Rr(u) =
Σ gr, u)
5.1. The Algorithm and Regret Guarantee
The quantity ERROR as defined in Equation (6) can be upper bounded by:
(e W1 u)
Σ
( Di: W2 u)
Next, we incorporate regularization function rt W R. We can re-write RT (u) as the following:
ERROR V
Σ 1EB
llge
9.
+ Σ
l1g. -
Fill
max wswll
1EB
Rr(u)=
9 Wt u) + rr(www) re(u)
11 9ell + G|BI
max wwwll
TEB
=R (u)
S &G max ||w
gt gi. we)-
re(w))
where B is defined Equation (3), and = [7] B. The second line is due to 11.. Tfll S 11 rell S G, Vt B, because he G || The last inequality is due to the corruption model presented in Equation (4). This suggests that the worst case value for ERROR is at most kG max, ||w/]|- This could potentially be exponential in t as shown in Lemma 8 (Zhang & Cutkosky, 2022). On the other hand, no matter which regularizer re we choose, a worst case upper bound on BIAS can be derived:
ERROR
CORRECTION
T
T
9t
+
(e)
t=1
DIAS
The interpretation is that (T( can be controlled through four components ERROR, CORRECTION, BIAS and com- posite regret (w). Here, (w) is the regret of an online learner A with respect to the losses (Øt, w) + re(w). Some information about the structure of rt may be known be- fore Wi is chosen, making this problem similar to online optimization with composite losses (Duchi al., 2010). We summarize the general procedure as Algorithm De- pending whether G max, ||ge|| is known not, the appropriate settings for he, the selection of regularizer Tt and the online learner A differs. We apply this general framework to the case where G is known in Section 5.1 first, and the consider the significantly more challenging unknown-G setting Section 6.
T Σ re(
BIAS S kG|
To enable CORRECTION to cancel ERROR while ensuring BIAS does not grow too large, the ideal choice of regularizer rt should achieve the following bounds simultaneously;
Σ ((()))) 2 52(KG t=1
max max ([wel)), t
Σ
Er((w) s ((K]))u])) d=1
To accomplish this, we choose (ww fe(w) as displayed
in Equation (7), which belongs to family of Huber losses first proposed by (Zhang & Cutkosky, 2022):
Algorithm General Protocol
1: Input:
Clipping thresholds: 0 < hn S hr+1 An online learning algorithms A.
fu(w;c,p,o co.(1:;
pw: a)/S.-1/
A regularizer: ra W - R+
where
2: for t = 1 to 7 do
3: Play we, receive gr
S.
||w a²
(8)
4: Compute De as Eqn. (5)
5: Send of, h441 to and get W141
and a piecewise function oz:
6:
end for
||wl|P (wllwel (p (1))11//aa wx
|||||| S [w/
ox (w;
otherwise
5. Robust Learning with Knowledge of Lipschitz Constant
(9)
In this section, we proceed under the simpler setting that G max, [gge]] || is known priori. We therefore will set
This function behaves polynomially near || and linear otherwise. By setting = kG.p = In T, a = </k: f

---

Unconstrained Robust Online Convex Optimization
achieves the desired properties. See detailed discussion of the characteristics of this family of losses in (Zhang & Cutkosky, 2022). For completeness we include a proof of the relevant properties in Lemma B.1. Overall, these bounds allow ERROR - CORRECTION V Ó(1) and BIAS x [I)
of Theorem 5.1 is tight with respect some comparator u' with any pre-specified magnitude. In addition, we provide second lower bound as Theorem E.5 in Appendix E, which has the matching log factor.
Theorem 5.2. For every D >> 0, there exists a comparator
u' E Rd such that || || = D, 91,-. .ÔT and 01,' ,9T
Armed with this peculiar regularization function, we now need an online learner that can control (u). This is simi- lar to online learning with loss (wx) == Gf we) + r:(w)) at each round t. However, we cannot simply apply any stan- dard OCO algorithm to these losses. The issue is that regu- larizer r, is (AGG) Lipschitz rather than G-Lipschitz. So, naive approach would result in R (u) = ([[lu]]AVVT) but we want our final regret to be only [[Iu|]((VT+ The key to avoid the multiplicative k-factor is to observe that rr is known ahead-of offeddof-time: it is composite term in the loss, and so ideally the regret should only depend on gf- Un- fortunately, composite losses are not as well-studied in the unconstrained online learning literature. Moreover, our com- posite loss is somewhat non-standard in that the shape of the function re depends slightly on wy. Nevertheless, we show that in fact the online mirror descent algorithm developed by (Jacobsen & Cutkosky, 2022) actually does guarantee com- posite regret in our setting. That is (w) S O[[lu]|GVTT (see Theorem C.2, and an explicit algorithmic update proce- dure in Algorithm 2). By combining these ingredients, we are ready to state the overall regret bound, whose proof is deferred to Appendix D.
such that Ilgell < 1, Σ 1 1s + gr) k:
T Σ lg. w - w²) 2 2 [|w'||
[1 (VT+ + k)]
6. Robust Learning with Unknown Lipschitz Constant
In this section, we consider the scenario where G > max; l|g: is unknown. We first discuss the additional chal- lenges must be addressed in Section 6.1, followed by intu- ition of selecting hy, Tt- Finally, we discuss the choice of the base algorithm A and the regret guarantee.
6.1. Challenges with Unknown G
The combination of unconstrained domain, unknown G and corrupted gradients provides a set of challenges that stymie current techniques in the literature. Let us unpack these challenges carefully, starting from where our analysis in Section 5 breaks down.
Previously, we employed a clipping threshold h2 = G to automatically filter out He values that were in some sense "obviously corrupted", replacing them with values that were only corrupted by at most G. Then, we employed a tech- nical regularization scheme by setting r. Se to "cancel" out these bounded corruptions. This strategy is no longer available: we do not know G.
Theorem 5.1, Suppose gt- St. satisfies assumptions in Equa- tion (3) and (4). Setting b2- G,r, fe as defined in kG.p = In a = c/k for some e >> O, set Algorithm 2 algorithm as the base algorithm A.
Equation (7) with
Then Algorithum! 1 guarantees:
RT( s Ô [cc + Iulli (VT+ + k)]
A natural approach would be to maintain a time-varying threshold he that estimates G on-the-fly, and use it in place of the unknown constant G. However, this is harder than it seems because inevitably we will sometimes have h2 < G, and we are likely clip even an uncorrupted gradi- ent: If # ge even when 9. = 9t- This means that unlike the known G-case, our clipping operation is not purely be- nign. Nevertheless, methods in the literature for tackling the unknown-G setting without corruptions often use ex- actly this method with hn = max ||9al| < G (Cutkosky, 2019; Mhammedi & Koolen, 2020; Cutkosky & Mhammedi, 2024).
Theorem 5.1 shows that the penalty for corrupted gradients is at most ([])) This result has few intriguing prop- erties. First, so long as k S VT, the penalty is subasymp- totic to the standard uncorrupted regret bound O([I)]|GVV/) That is. we can tolerate i up to vT essentially "for free"" Next, observe that for u O. the regret is no matter what k is. Constant regret at the origin is typical for unconstrained algorithms, but is especially remarkable for our corrupted setting. Imagine a scenario in which we define 0 to repre- sent some "default" action. Our bound then suggests that no matter how much corruption is present, we never do significantly worse than this default.
Unfortunately, this does not work for corrupted setting. The new difficulty is that we never know the value G, even
in hindsight. The choice h = max; llo: is bad: a single corrupted gradient with ll > G will be catastrophic. Moreover, even we were guaranteed that ll < G for all f, it might be that || 2 he, so that truncation actually
5.2. Lower Bounds
We present a lower bound in Theorem 5.2 with proofs de- ferred in Appendix F. This result shows that the upper bound
5

---

Unconstrained Robust Online Convex Optimization
results in 119-- of 119: -ie--ell dell We will call this additional bias "truncation error". As result, we need to address new challenge:
10
or(w) |wo2
8
6
1. How can we choose h2 in a robust way that serves as good estimate of G without introducing too much truncation error?
4
2
In addition, even if we could address challenge I and have access to h2 S G. the regularizer rz = fc used for our known-G algorithm also required exact knowledge of the value for G. We rely the scaling factor с 2 O(kG) to be big enough to "cancel" the ERROR < kG max, ||well as E, fe(re) 2 Oc [[w.])). Therefore, simply setting c= kh, is not sufficient since h, values are likely smaller than G.
4
w
Figure 2. Comparison of Huber loss ft without scaling factor d. with = 3, |wre] = 1, and | |wol always grow faster than o (w= far away from the origin.
In the known-G case, the Huber regularizer ft almost per- fectly cancels the error by imposing penalty that is also roughly proportional to max, ||w,]]- The challenge in the unknown G-case is that the proportionality constant of &G is unknown, so we cannot perform this cancellation. In- stead, we propose to use a regularizer (w)) = w[]l)] that grows faster than the Huber regularizer ft as illustrated in Figure? 2. This way, kG max, ||we|| I ry (max, [|w, II) for large enough [|we|| matter what G is. By scaling T, appropriately, we would like to ensure rur > Q(k max; |w:e1l?). Then, as long as max; ||w=]| > G, E. ((w) will completely cancel ERROR. So overall, with- out prior knowledge of G, ERROR - CORRECTION x OKKG2) is guaranteed. However, the quadratic growth rt introduces another challenge:
iterations in which ||o.1 2 hr. This mechanism is named as FILTER and is displayed as Algorithm 3 in Appendix F.
Notice that he only doubles if it is guaranteed that some It satisfies hr S |lgrlll rounds where gradients are clipped as P = (t E [T] : g * Ti that P denotes rounds that have h; S gell. The conditional doubling mechanism also ensures |P| S Ō(k) (See Lemma F.2). This means only small fraction of Gt are truncated before he becomes very accurate estimate of G. Hence, the total rounds which are vulnerable to suffering from truncation error is small. This FILTER strategy im- proves upon a method with a similar purpose in van Erven et al. (2021); it uses only constant space rather than O(k) space.
Il. so that he S O(G) always. Denote
2. How can we exploit a more aggressive quadratic regu- larization without introducing too much regularization bias E, (u) for arbitrary u E W/?
As consequence of using hy from FILTER as the clipping threshold, we can decompose the ERROR term defined in Equation (6) by using ğt = of for I P:
Challenge 2:
In particular, notice that any constant regularizer (w) C' would add bias of 3, re( u]] gret, so that we would require C = O(1TT). This in turn is too small to ensure E. (w:)) 2 (2(k: max; ||wre|| ll²). Our so- lution will require a more nuanced time-varying regularizer.
ERROR S
Σ 11g. - Df [lwwell +
Σ 11 De Illl well (10) IEP
12 to the re-
LEP
Exp :truncatioon error
Ep commmpiiionn error
Therefore, we must choose a regularizer to offset those errors. We discuss how each error component is treated and finally reveal the structure of rt-
6.2. Adaptive Thresholding and Error Correction
Challenge To meet the challenge of choosing ht prop- erly, we introduce a "tracking mechanism" that conserva- tively increases hy over time. The key insight is that at most k values of / can have || || > 2G (See Lemma F.1). Based on this observation, we propose simple way to maintain a "threshold" h, which provides a conservative lower bound estimate of G. The threshold h, starts with some small value h TG > and stays constant until we observe +
Truncation error Ep can be reduced by keeping ||w]|| from being too large. Thus, every time we experience some truncation error, would like to use some regularization to force the learner to decrease |/wx]]. To this end, we use quadratic regularization penalty azl ael|w>]|l where a * 0 only when t E P so as to only encourage w, to decrease only when we have "evidence" that truncation error has occurred. Then, for any round t E P we bound the truncation error
6

---

Unconstrained Robust Online Convex Optimization
minus the quadratic regularizer og ///,, as follows:
So, applying a sufficiently large regularization ex- actly the indices in Po will ideally be enough cancel all of the comrpption error. Further, notice that |Pol < ( |[,]]]) I]). Thus, one might hope to apply an ap- proach similar to the one used for truncation error: use a regularizer Bellw[|? with Br = 0 for t & Pu and 3, equal to some constant 3 for E Po- Unfortunately, this will yield a regularization bias of ΣIEP, 3||u|/ I 0 Inmmax, || [[]] While this seems benign, recall that actually max, ||w, may be exponential in T, so that In (max, || (l) is still polynomial in T. To resolve this, we gradually attenuate 33 by choosing:
l1 well - are aellwil12
19 - 1il
l1g. - - ar a,x²= X
sup
4a
such a regularization scheme implies overall:
1 - 11
Ep- - Σ Ealllwel? -
Σ TEP
S SG²
4a
LEP
and additional regularization bias is ||u||2 E. 0r- This means the truncation error will be controlled as O(kG²), and the additional bias from this regularization will also be mild as (( if the following conditions hold simulta- neously:
1 1 # 2
Be 79 1+ Ei 1 12i+1 # 23
(12)
Σ 1//a,5 S OK)), PEP
Σ au S Okk) 1E|2
With this choice, the following are guaranteed:
Σ 1/3s So
Im [|wel]
Notice that I S (k) and that h6+1 # h4 Vt E P. Thus, the following 0₁ fulfills both requirements:
LEPo
and
a+ = Ta - 1(eet1 # he}
(11)
Σ 3: Ö In In max [|wll)) = (k)) <E|2]
by setting 7/- = 0(1)
Next, for managing the corruption error E'p one might at- tempt to take the same approach by imposing an additional quadratic regularizer Bel /,,] 2| Similar calculation as used in the control of truncation error suggests that we can con- trol the corruption error so long LtEP 1/3, < (kk) and Σ. 3, < +Ok)) holds simultancously. Unfortunately, [P] could potentially be as large as ((T), and so is not possi- ble to pick constant 3r, Vt E P that satisfies these desired rates.
with 7 O(k). The first identity guarantees that Ep -, Be (|, 122 is at most Ö(KG² In max, ||w; II), while the second ensures that the additional bias is only Σ E Bellu|22 S Óklllul]²) Now, we still need to han- dle the potentially-large Ö(KG² In max; || I]) term. This remaining corruption bound can be controlled by adding a small multiple of the Huber regularizer St, which satisfies Σ, fw) 2 Ó(KG² In max, ||w; II) even for < G.
To summarize, our solution to solve Challenge 2 is to set regularizer as:
Our remedy is to apply milder regularization by combining the quadratic regularizer which is active only on a smaller subset Po C P and the Huber regularization Si which is active at every round. To see how this will work, suppose we divide the T rounds into N "epochs" in which max; [|wl| E [2N; 22+1 Specifically, we begin with some 21 = tD > O. Whenever |ww|| 2 2t, we set 2++1 = 2/l and 1 2t otherwise (formally summarized as TRACKER as Algorithm 4. Appendix G). We choose Po- = {t 2++1 # 2.). that is time steps Po- = (n...., TN) when threshold doubles. For any two consecutive time steps Ta, Ta+1 E Po. we define [T, 1 1] as a single "epoch" for each n E N. Notice that for E [T.. Tn+1 - 1]. we must have |wrlll < 2||w,, |l. Further, the total corruption error incurred in one such "epoch" is:
Te re(w) = [e() + dcl|w]|2
where a, = Oi + 3r. Overall, the sparsely applied quadratic regulaization and small Huber regularization at every round allow the following bounds as shown in Lemma H.2:
ERROR ERROR-CORRECTION x
(kG)²
1
Σ
fa(w)
ati
B
1:
and
T
T
T
BIAS S |
Σ 04 +
+
fe(w) - kG
-1
l1g. 3fll [wlll < 2lI
Σ t=
99 Ifll
with appropriately chosen constants, and BIAS - Ö(kG||ul|| + ||ul)3)
ERROR
CORRECTION - ÓkK2)) are achieved.
2kGG|
|I
7

---

Unconstrained Robust Online Convex Optimization
6.3. Base Algorithm and the Regret
= =e/k Corollary 6.2. With KTG, T3 = Ka 1,TD==/// and rest of parameters same Theorem 6.1, Algorithm / guarantees regret bound:
With the regularizer ra chosen in the previous section, it remains to choose learner A which guarantees regret:
RT(u)= S 2
e(G]o ofe1che + +|ull[[]ro (VT- -k)
(u)
Te Wt - u) + fe(we) - [u)
+ (k: + 1) (Ilu] (G
Or (1|u>]1* 12- ||u|13)
where [G] := max(Ta: G).
However, the solution of Section 5.1 of learning with com- posite loss (ww) = (0f, wi) + f((w) + a, || is no longer appropriate because it requires the composite term to be known in round Unfortunately, in this case the quadratic component depends on a, ax + Br, which is unknown until of is revealed. Due to the quadratic component, we employ the "epigraph-basee regularization" technique re- cently developed by Cutkosky & Mhammedi (2024) to construct A. Briefly, this technique projects convex op- timization problems in W = d to an augmented space Rd+1. The first d coordinate of the solution in the aug- mented space is the decision variable Wis and the extra coordinate is a technical device that is used to modify the loss in way that makes it easier to control the quadratic penalty. We incorporate this technique in our set up to obtain RA S Ô (1 [Iw]GGvT + [|=] as provided in Theorem 1.3. We leave brief summary of the technique in Appendix I.
Just as in the known-G case, the parameter settings in Corol- lary 6.2 yield ((VT) regret so long as S VT so that we can experience a significant amount of corruption without damaging the asymptoties of the regret bound.
We can also achieve the desirable "safety" property of The- orem 6.1 in which the regret with respect to the baseline point = 0 is constant no matter what k is via a differ- ent setting of the regularization parameters as provided in Corollary 6.3:
Corollary 6.3. With c Ta: 7/8 = k2 To k 1 = and rest of parameters same as Theorem 6.1, Algorithm 1 guarantees a regret bound:
(T s [GGTo O + (I: + 1)(G]To [G]
+ |[lll[GTr (VT+ + 1|u|1 1)2
Combining with the error correction parts from the previous section, we obtain general regret guarantee as follows with free parameters c, Ya. 7/3 that specify the Huber regularizer and quadratic regularizers:
where [G] max(Ta,
However, in this case now pay a larger penalty for / O that scales with k² rather than k. This is natural tradeoff: we ensured constant regret at the origin by increasing the regularization away from the origin. The overall regulariza- tion is stronger, which encourages smaller ||we||. Thus, this algorithm configuration is likely to be advantageous when competing with small [/u]].
Theorem 6.1. Suppose gt. 9r satisfies assumptions in Equa-
tion (3) and (4). Setting Ti (w) = fe(w) + + where St defined in Equation (7) with parameters: a ETG/C,p In T,y To + "13, for some c, Ta: TG; TD 0, set Algorithm 5 algorithm as the base algorithm A. Then Algo-
rithm I guarantees:
Rr(u)= SO $01(Che c/Crr + KTD[G]ro + [| (VT + k)
7. Conclusion
+ +c(1lu) + TD) + (Ta + +1 78) |
In this paper, we considered unconstrained online convex optimization that only have access to potentially corrupted gradients ğe instead of the true gradient gt. in which the corruption level is measured by k. In the case that G > max; ||9: is known, we provide an algorithm that achieves the optimal regret guarantee ||u]]G[VT is unknown it incur an extra additive penalty of ([|u]|2 + G2)k. While the ||u]|2 + G2 is optimal without corruption (Cutkosky & Mhammedi, 2024), it is unclear whether the multiplicative dependence on k is optimal in the presence of corruption.
(k + LIGGE
k22 3/
Ya
7/8
k). When G
Notice that although it appears possible to set c = 0 in the above bound, there is a log(1/ /c) term hidden inside the Ô that prevents excessively small e values.
Next, we provide two different way to set c, 7g. By setting both e, 7/8 O(k) and TD O11k), we obtain:
8

---

Unconstrained Robust Online Convex Optimization
Impact Statement
Cutkosky, A. Artificial constraints and hints for unbounded
online learning. In Proceedings of the Thirty-Secont Conference on Learning Theory, pp. 874-894, 2019.
This paper advances the theoretical understanding of on- line convex optimization, contributing to the mathematical foundations of machine learning. As it does not involve deployable systems datasets, the broader societal and ethical implications are indirect, and no specific concerns need to be highlighted.
Cutkosky, A. and Mhammedi, Fully unconstrained online learning. Advances in Neural Information Processing Systems, 2024.
Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. Con- ference On Learning Theory, pp. 1493-1529, 2018.
References
Abemetth,, J.. Bartlett, P. L., Rakhlin, A., and Tewari, A. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the nineteenth annual conference on computational learning theory, pp. 415- 424, 2008.
Delibalta, I., Gokcesu, K., Simsek, M., Baruh, I.,, and Kozat, S. S. Online anomaly detection with nested trees. IEEE Signal Processing Letters, 23(12):1867-1871 2016.
Diakonikolas, and Kane, D. M. Recent advances in algo- rithmic high-dimensional robust statisties. arXiv preprint urXiv:1911.0541 2019.
Agarwal, A., Agarwal, S., and Patil, P. Stochastic duel- ing bandits with adversarial corruption. In Algorithmic Learning Theory, pp. 217-248. PMLR, 2021.
Duchi, J. C., Shalev-Shwartz, S., Singer, Y., and Tewari, A. Composite objective mirror descent. In COLT, volume 10, pp. 14-26. Citeseer, 2010.
Ben-Tal, A., El Ghaoui, L., and Nemirovski, A. Robust op- limization, volume 28. Princeton university press, 2009.
Gupta, A., Koren, T., and Talwar, K. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 1562-1578. PMIR, 2019.
Ben-Tal, A., Hazan, E., Koren, T., and Mannor, S. Oracle- based robust optimization via online learning. Operations Research, 63(()):28-633, 2015.
Bertsekas, D. Convex optimization theory, volume 1, Athena Scientific, 2009.
Huber, P. J. Robust statistics, volume 523. John Wiley & Sons, 2004.
Candès, E. J., Li, X., Ma, Y., and Wright, J. Robust principal component analysis? Journal of the ACM (JACM), 58(3): 1-37, 2011.
Ito, S. On optimal robustness to adversarial corruption in on- line decision problems. Advances in Neural Information Processing Systems, 34:7409-7422 2021.
Jacobsen, A. and Cutkosky, A. Parameter-free mir- ror descent. In Loh, P.-. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learn- ing Theory, volume 178 Proceedings of Ma- chine Learning Research, pp. 4160-4211. PMLR, 2022. URL W/RLtttps//pprceedii maopggsmmr..... mlr ..lr.pprss/ v1 v jac.bse2oosee22..... html.
Chang, F-CC., Nabiei, F., Wu, P.-Y., Cioba, A., Vakili, S., and Bernacchia, A. Gradient descent: Robustness to adversarial corruption. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022.
Chen, S., Koehler, F., Moitra, A., and Yau, M. Online and distribution- robustness: Regression and contextual bandits with huber contamination. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp.
Jun, K.-S. and Orabona, F. Parameter-fres online convex optimization with sub-exponential noise. In Conference Learning Theory, pp. 1802-1823. PMLR, 2019,
IEEE, 2022.
Cherapanamjeri, Y., Aras, E.,, Tripuraneni, N., Jordan, M. I., Flammarion, N., and Bartlett, P. L. Optimal robust linear regression in nearly linear time. arXiv preprint TPX1::2007.08137,2000
Klivans, A., Kothari, P. K., and Meka, R. Efficient algo- rithms for outlier-robust regression. In Conference Learning Theory, pp. 1420-1430. PMLR, 2018.
Levy, D., Carmon, Y., Duchi, J. C., and Sidford, A. Large- scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33: 8847-8860, 2020.
Cook, R. D. Detection of influential observation in linear regression. Technometrics, 42(1):65-68, 2000.
Cutkosky, A. Algorithms and Lower Bounds for Parameter- free Online Learning. PhD thesis, Stanford University, 2018.
Lugosi, G. and Mendelson, Robust multivariate mean estimation: the optimality of trimmed mean. 2021.

---

Unconstrained Robust Online Convex Optimization
Lykouris, T., Mirrokni, V., and Paes Leme, R. Stochastic bandits robust adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, Pp. 11--122. 2018.
Sankararaman, A., Narayanaswamy, B., Singh, V. Y., and Song, Z.. Fitness:(fine tune to detect anomalies in streams with drift and outliers. In International Conference on Machine Learning, pp. 19153-19177. PMLR, 2022.
and similar samples)
Memahan, B. and Streeter, M. No-regret algorithms for unconstrained online convex optimization. In Advances in neural information processing systems, pp. 2402-2410, 2012.
Thode, H. C. Tesfing for normality. CRC press, 2002.
van der Hoeven, D. User-specified local differential privacy in unconstrained adaptive online learning. In Advances in Neural Information Processing Systems, pp. 14103- 14112, 2019.
McMahan, H. B. and Orabona, F. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In COLT, pp. 1020-1039, 2014.
van Erven, T., Sachs, S., Koolen, W. M., and Kotlowski, W. Robust online convex optimization in the presence of outliers. In Conference on Learning Theory, pp. 4174- 4194. PMLR, 2021.
Mhammedi, Z. and Koolen, W. M. Lipschitz and comparator-norm adaptivity in online learning. Confer- ence on Learning Theory, pp. 2858-2887,20 2020.
Namkoong, H. and Duchi, J. C. Stochastic gradient methods for distributionally robust optimization with divergences. Advances in neural information processing systems, 29,2016 2016.
Xie, S. M., Pham, H., Dong, X., Du, N., Liu, H. Lu, Y., Liang. P. S., Le, Q V., Ma, T., and Yu, A. W. Doremi: Optimizing data mixtures speeds up language model pre- training. Advances in Neural Information Processing Systems, 36, 2023.
Orabona, F. Simultaneous model selection and optimiza- tion through parameter-free stochastic learning. Ad- vances in Neural Information Processing Systems, pp- 1116-1124, 2014.
Zhang. J. and Cutkosky, A. Parameter-free regret high probability with heavy tails. Advances in Neural Infor- mation Processing Systems, 35:8000-8012, 2022.
Orabona, F. A modern introduction to online learning. arXiv preprint 19Xiv:1912.1322 2019.
Zhang, Z.,, Cutkosky, A., and Paschalidis, I. Pde-based optimal strategy for unconstrained online learning. In In- ternational Conference on Machine Learning, pp. 26085
Orabona, F. and Pál, D. Coin betting and parameter-free online learning. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29, pp. 577-585. Curran Associates, Inc., 2016.
26115. PMLR, 2022.
Zhang, Z., Yang, H., Cutkosky, A., and Paschalidis, I. C. Im- proving adaptive online learning using refined discretiza- tion. International Conference on Algorithmic Learn- ing Theory, pp. 1208-1233. PMLR, 2024.
Oren, Y., Sagawa, S., Hashimoto, T. B., and Liang, Dis- tributionally robust language modeling. arXiv preprint arXiv:1909.02000 2019.
Zhou, C. and Paffenroth, R. C. Anomaly detection with robust deep autoencoders. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 665-674, 2017.
Qi. Q. Guo, Z., Xu, Y., Jin, R., and Yang. T. An online method for class of distributionally robust optimiza- tion with non-convex objectives. Advances in Neural Information Processing Systems, 34:10067-10080, 2021.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML- 03), pp. 928-936, 2003.
Raginsky, M., Willett, R. M., Horn, C., Silva, J., and Mar- cia, R. F. Sequential anomaly detection in the presence of noise and limited feedback. IEEE Transactions on Information Theory, 58(8):5544-5566 55662, 2012.
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case gener- alization. arXiv preprint urXiv:1911. 100731, 2019.
Sankararaman, A. and Narayanaswamy, B. Online robust non non-stationary estimation. Advances in Neural Informa- tion Processing Systems, 36, 2024.
10

---

Unconstrained Robust Online Convex Optimization
A. Unconstrained Online Convex Optimization with Hints
In the unconstrained setting, there are algorithms requires a uniform bound G 2 max; | upfront which guarantees O[[[i]]/V/ (McMahan & Orabona, 2014; Orabona & Päl. 2016; Cutkosky & Orabona, 2018; Zhang et al., 2022). In the case where G is unknown, algorithms are usually devised through an intermediate step with slightly ideal scenario, that the algorithm receives gradient Ie with a "hints" h++1 max45++1 IIg:ll || at each iteration t. It turns out by having access to ht to guide the algorithm, same regret Ö([ //rl///// VT) can be achieved (Cutkosky, 2019; Mhammedi & Koolen, 2020; Jacobsen & Cutkosky, 2022; Zhang al., 2024).
In this paper, we also follows the same strategy of assuming good hints he = maxiga l1 is supplied to the algorithm, and eventually investigate the scenario of only the current best estimate he s maxigı-1 II is available. Hence most of the proofs in the appendix are displayed in the way of relying on time varying "hints": < h1 S ...hr S hT+1 to accommodate the design of both known G and unknown G case.
B. Bounds on Regularizer in Equation (7)
Our results are based on appropriate algebraic property of fi displayed in Equation (7) and was firstly studied by Zhang & Cutkosky (2022). We re-stated relevant bounds as Lemma B.1 for completeness.
Lemma B.1 (Lemma and Lemma 13 of Zhang & Cutkosky (2022)). Let St : - RR+ be defined as follows for some
2 a 0 and 2
c(pl|vol - (p 22 II)
||]||| > || || ||/||| < ||w,
[e e.p,e.p.o
(5)
ur 1 +a 175
clwu|| (Ei=: Iwe tap)1+-0))-1011
Then
T
1/8
f(())) 20
Σ | 11 + a²))
||ul|| p.
(0 1)/p
Σ Muu))= s c/llu|/T'//
In +
+
In particular, when In T for T 2 3:
[e(w)) 2 maax |well - a)
(1+
||u|| )) +
Σ ft(u) s 3eIn
In 1+
Proof. The first set of bounds the same Zhang& & Cutkosky (2022) Lemma 13. For the second set of bounds: the 1/r
1/p followed by an application of of Lemma 11 in Zhang
lower bound is due to (>= ||wa|1 + oz))
2 [>=) [|w]|p))
& Cutkosky (2022); the upper bound is due to 2 S for >> and 0 < < 1, where we set In + [w]] P
and q = (p- 1)/p followed by //IIT In
3.
C. Base Algorithms for known G
In this section, we verify the "centered mirror descent" framework (see their Algorithm and we contextualize it as Algorithm 2 here) developed by (Jacobsen & Cutkosky, 2022) automatically guarantee a composite regret (+) "for free" thus is compatible candidate achieving robust unconstrained learning.
Algorithm 2 is explicit update with regularizers vix v()):
1 ((1m)) (((x)dx, (((x) min
In(æ/ac ae +1) + V/V
(e(w)) =3
(13)
151/
11

---

Unconstrained Robust Online Convex Optimization
and some (w) (In their notation as (p(w)) ). That is
Wa+1 argmin (gt, w) + Doy (w wx) + Ar(w) + fe(w)
(14)
where Da b) - (aa) (b)) - (Vo(b), a b) is the Bregman divergence induced by eh, and A.(w) Desss (w w1) -D, (w w1).
Notice the first two terms in Equation (14) corresponds to the classical mirror descent with mirror map the the third term Ax(w) encourages iterate to be close to the initial start wt, thus echoing "centered" mirror descent. and fa being any arbitrary composite regularizer and its structure completely known in time in order to produce Mh+11- shows the above update with ft (i; in their notation) guarantees RT( - O(]]u]//v vT) (Theorem 6), which is optimal. The second composite regularizer fi was specifically tailored as fi(w) O (1 [(]]) in order to attain optimal dynamic regret (See their Proposition 1).
We verify (u) & C.2. In fact, the development of (Jacobsen & Cutkosky, 2022) attains the same bound for any arbitrary composite regularizer St for user to exploit. We first present a helper Lemma that is equivalent to the update in Equation (14) before the theorem:
when ft as defined in Equation (7) for our purpose, which is formalized as Theorem
Lemma C.1. Equation (14) is equivalent to
Wi+1 = argmin (gt, w) + Dos (w we)
(15)
u
Wc+1 argmin De (w wx+1) + (r(w) + [1+1(w)
(16)
u
Proof. By first order optimality, Equation (15) implies
+ - - Vibe(wo)) =
Thus
W VV. (Vth((w)) gt)
Substitute 1.+1 into Equation (16), the equivalence.
Theorem C.2. Suppose ln S ha S ... < hr and gr... ,9 be arbitrary sequence satisfies l|gell he for all (T).
Then Algorithm& 2 guarantees
(T( Σ (gt, Wi u) re(ww)) - re(u)) 5ō (e(i + lulbbrVT
where rt is defined as Equation (7) arbitrary c, O.
Proof. First, we verify Algorithm is indeed the update corresponding to Equation (14). By Lemma C.I, Equation (14) is equivalent to a two step update as shown in Equation (15) and (16).
By first order optimality Equation (15):
W (Ver(())( gt)
Then substitute Equation (16)
V (w++1) + = Vehe(w)) - 9t = 0 1z|--
Define ([ (w) [ |!l||| (x(x) and R++1(x) cp (S.t|z|o 1n- 17 (Notice Vf441())) Reti (I==l)))
thus by substitute derivatives
Wi+1 [w
Vea (1 + Ret1 ([1we+al))
0
12

---

Unconstrained Robust Online Convex Optimization
Thus, the solution W441 satísfies the following for some 2 0:
0. W++1 2 |011
L(+1(x)
|10,11
In partieular, define F. log(1 + =
(x(x) = (VV.F(()) + Re(x)) (3)FF(z)= + 3V. be R((x),
h4 F((x(()) < VV.
otherwise
The boundary case when x² (f(=))((>> = Vv. That is x = (eepp Vi/hg) - 1). Consider by cases,
6V. Lx(x) = |0,11 - L((x") = h
+ Rx(x")
Then r S xx" xx" F((x) < VV. thus the first branch should be evoked. Similarly, consider the other case, the complete update should be:
6 (oV.F(())) + (x), 3V. (x),, The
|0.11 S
nV hr + Re(x*)
(x))) =
(h)F((t)
otherwise
It remains to show the composite regret (u) guaranteed by Algorithm 2. Notice the original proof of Theorem 6 of (Jacobsen & Cutkosky, 2022) relies on their generalized Lemma by setting fi 0 (their sp:). Thus Lemma I of (Jacobsen & Cutkosky, 2022) implies for general fr:
Ry (u) (r+i(u) + Σ
fu( +
Σ 1=1
Me w. we+1) Des (we+1 (.)) Ae(we+1) fe41
Move relative terms to left hand side:
T
Rr(u) (u) + Σ f((w)) - fe(u)= S (1)
(gt, we We+1) Des (Wi+1 wy) A((w))) + f((w1) fr+((ur4))
w1 0, thus (wi) = 0. And ft is non-negative
< (u)
Σ (gt. we W1+1) Des (wi+1 w)) A((w+1)
Thus following the exactly same proof of Theorem of (Jacobsen & Cutkosky, 2022):
Vr+1 in 1+ |uully/ Br+1 In2 (Br+1) hr In 1 || v Br ln? (Br+1)
(u) S 4hr + 61/2u| max
13

---

Unconstrained Robust Online Convex Optimization
Algorithm 2 Robust Online Learning By Exploiting Linear Offset
1: Input: Time horizon T: Initial Value e; Corruption parameter k; Regularization relevant parameters: c, 0z
Hints: 0 < h1 < h2 _ .... S fr+1:
2: Initialize: 01 = 0, C1 = 0, N1 = 4, B1 = 4N1, w1 = 0, So = a².
3: for t= 1 to 7" do
4: Define: Fz(x) = In(1 + z/a;) a,), R(+1(x) cp||>>||>>>>11111> /(S, + |
5: Output wi, receive 9t where || S h4
6: Compute 0c+1 Vidi (wa) 9r
7: Update C++1 = C. |1 2 No+1 N₂ 19 /11 Be+1 B. 4N,
8: Set Vi+1 h1411 + C++1 and 0++1
BBai In? (Bc4s)
9: Compute x= ac+1
-1)
10: Define
6 6/4+1114((2) Re+1(x), ||0e| S 6V.1 + Rx+1(x*)
(1t1(1)=
hef1 otherwise
31 F. (x)) +
Wi11 Ret1(x);
h04t
11: Solve for #z+1 C141 (2++1) |10ell
{solvable via bisection where 2 E (0,5
12: Update We+1 = T++1
[.]] S1+1 St ||
8.
13: end for
We remark that the inverse problem involved in Algorithm Line can be efficiently handled by bisection method since L (ar) is monotonically increasing. Notice that 0 ( < (++1(x++1) O, so 0 can be used initial lower bound. On the other hand Re+1 (#++1) S Li+1 (x+1(x++1)++ = 10,11. thus 2c+1 S R441 ([]01)), where for y 2 0:
Se (w/cp) = (w/cp)
(1)
For simplicity, we can always use S//P as an initial upper bound.
D. Proof to Theorem 5.1 and Applications
We provide the regret guarantee of Algorithm 1 when using an instance of Algorithm 2 as a base learner A as well as two applications when h1 = hT+1 = G
Theorem 5.1. Suppose 9t. ÿt satisfies assumptions in Equation (3) and (4). Setting h; G, ft defined in Equation (7) with e = kG, = In T, a e/ for some >> O, sel Algorithm 2 algorithm as the base algorithm A. Then Algorithm 1 guarantees:
R s 2 0 + | (VI + +k]]
Proof. The proof begins with the regret decomposition in Equation (6) and is displayed below for convenience.
T
T
T
Rr(u)= = Te We - u) + re(we) re(u)= +
(g: T.. w/)
Σ re(w)) +
Σ
9t
Dt
2
(u)
(a)
ERROR
CORRECTIOO
BLAS
Define OFFSET ERROR CORRECTION, and in Section 5.1 we already shown ERROR kG max, || thus
OFFSET kG max ||wlll
Σ r((w)
14

---

Unconstrained Robust Online Convex Optimization
by Lemma B.1 by substituting pa
kG max wwwll
(G(max [0rl - e/k) (cG)
6
Similarly by following the application of Lemma B.1:
T BIAS < kG]|u|| + Σ r(())
1=1
In T
S kG||u|l 3&G In
In 1+
- 2
(kGllull)
In addition, Algorithm 2 is set as A in response o with h2 = G. Thus by Theorem C.2 guarantees
(+) S Ö(EG [|l|GGV)
Combining three parts and complete the proof.
Here, provide implication of Theorem 5.1 to stochastic convex optimization and online version of distributionally robust optimization.
Stochastic convex optimization with corruptions OCO and convex stochastic optimization are connected through the classical Online-to-Batee Conversion (Orabona, 2019). Below, we present the implications of Theorem 5.1 stochastic convex optimization setting where & gradient evaluations are arbitrarily corrupted.
Corollary D.1 (Stochastic Convex Optimization via Online to Batch). Suppose L W - R is convex and [[(((w)) = L(w), gr (wx) and Ex [I]==]]] < G. Algorithm I have access to Jr such that Σt= 1 1( + De} S k, then Algorithm I guarantees
E + | ( (VT +k)
E
c
i== wi T
C(u)
s
T
Proof. The proof leverages the standard online to batch conversion (Theorem 3.1 in (Orabona, 2019) by setting a; = 1), then combining with the regret bounds from Theorem 5.1.
Distributionally robust optimization Distributionally robust optimization a form of robust stochastic optimization on training data sampled from distribution P that is not the same the population distribution Q (Ben-Tal et al., 2009; 2015). Typically, Q is considered uniform, but the actual training data collection process might be biased, meaning P is different to Q. In this situation, stochastic optimization which treats each training example with equal weight is no longer appropriate.
Namkoong & Duchi (2016) formalized this framework as the following model with respect to set of losses f,.... fy, and an uncertainty set Pa = { E AT (QQ s C(kTT); where Dy is the f-Divergence, for a convex function f: + + with f(1) =
T
Σ prle(w)
argmin sup PEP
the decision variable from above formulation takes account into the worst case distributional uncertainty, hence is intuitively associated with improving generalization error given appropriate uncertainty set Pı (Sagawa et al., 2019).
Distributionally robust optimization is increasingly relevant in the training of large language models, where training data are sourced from different domains (Xie et al., 2023). This due to data from some domain are relatively atypical in comparison to others in representing the overall population distribution (Oren et al., 2019). Although empirical gain has been observed by incorporating distributionally robust optimization, the scalability has always been a primary concern for
15

---

Unconstrained Robust Online Convex Optimization
model training (Levy al., 2020: Qi al., 2021). Therefore, consider natural "online" version of distributionally robust optimization model proposed by Namkoong & Duchi (2016), with its online analogous metric formulated as:
sup Σ p fe(u)) PEP t=1
We present the implication of Algorithm 1 to this problem with respect to total variation Drv and Kullback-Leible divergence D LL In particular, we assume & is convex and Q is uniform.
Corollary D.2 (Online Distributionally Robust Optimization). Suppose ge (we(ws and | S G. Algorithm I runs 3t guarantees
T
+ ||u||
(VT + +k)
Σ PEP
pe(l((ur) - -e((((us)-buuu)) le(u)) s ò
sup
T
for Drv S B. T. In addition, in the case where DKL. S T the same guarantee is achieved.
2h
Proof. We begin with the case of D Div(PIIQ) = E qi Ph - 11 4.2 where 9r 7
=
First, link the regret incurred
qr by Algorithm that runs on gt. and we denote the unobservable gradient as g: q 9t
Pt
Rr(u) Σ (cl((w))) -
S
Pe Pelge, ui u.
Σ le (gt wi - +
Σ
9t
Pt
-1
(gee we u)
9t
T
T
T
(gts We - 12 +
Σ
(er
It, Wt
tm1
since 1/2 Σ 11gt -gell St"
2k. Ht, Sr satisfies Equation (2), hence Theorem 5.1 provides the guarantee:
c ||u|| (VT+ +
Σ pe(lo(wr) - E(u)) -((l((=))e(uu) Ō
T
In terms of DKL, we exploit the Pinsker's incquality Drv S 22DKL, Hence DKL <
21 7F
yields to the same results.
E. Lower Bounds
In this section, we present two type of matching lower bounds to Theorem 5.1: Theorem 5.2 provides lower bound for any comparator u Rd with arbitrary magnitude D 0. Theorem E.5 is lower bound with log factors, which appears in unconstrained OCO upper bounds.
We begin by presenting a helper lemma that aids in the analysis of Theorem 5.2, followed by Lemmas required to proof to Theorem 5.2.
Lemma F.1. Suppose 21, "2, 2T E {-1,+1] +1] with equal probability. Then for every & [T) some T 1.
T
sign
zz
Zt
16

---

Unconstrained Robust Online Convex Optimization
Proof. Define St EiE(TTI 2is by conditioning on gr +11,+11;
2 E
sign Σ 27
2t
E sign (ST + 1)] - (sign (ST - 1]]
Σ
(sign 1) sign(k: 1)) P(ST k)
kE(-T,-T+2. .T)
We consider T' by cases: suppose 7' is even, sign(k k +1 sign(k: 1) when k 0, and sign(k + +) sign(k: - 1) otherwise. Thus applying T
(1/2) 2 2T/22 1/2
T
T
E
sign Σ
24
2T
= P(S = 00
2 2 (T/2) 1/2 (T/2
=V 2T
T
Similarly if 7 is odd, by symmetry to ST = +1:
E
sign Σ
(P(ST -1) P(ST 1))
2
T
(T 1 2-
Define T" - thus T" is even
T
+T" 111 20
(1r'+4))
(7)
T
(T (-))
(T
T"
T +1
2 -1""+11)
/2
T442 + 2
21-11
T"
-1/2
T" 1 2 +1)
2
T" +
1
87
8(T
1)
16T
Thus combining two cases:
Σ
E
sign
21
2T
16T
Due to symmetry, S, has the same distribution VI E [T]:
sign
2T
E
sign
21'
vA
[T]
Thus
T
T
E
sign
=
TT
sign
Σ
16
t=1
1=1
Theorem 5.2. For every D > O, there exists a comparator un E dRd such that ||u*||
D, Ø1.
.r and g.. gr such
that [|g:ll |l $ 1, ΣTr L # gr) k:
Σ ge,, wi
-w -² Ω [|r''l (VT+ +b)
17

---

Unconstrained Robust Online Convex Optimization
Proof. Consider the following random sequence: 2k++1; 2k+2." 1. FT {-1,+1} with equal probability and 21 Ai = sign Ei=k+1 zt). And ě = Ei = and b5 = 2t, Vt 2 k + 1. Let E IR" be any unity vector. Suppose
gt 2.q, 9t εgq, Vt T. Select u² - sign( Ei 1 Thus:
E Ry
(u')
E
Σ (9t, - u)
Kge, we)1 -
L u)
Σ
Kgt u)]
1=++1
T Σ
E
(E] (E|20l wi)
+ DK + D
E
sign
t= 1++11
M=
DE + D
E
24 sign
Σ M=-+1
2t
by Lemma E.1
T
2
k
=S2(Iu= VT)
16
The second lower bound in Theorem E.5 has matching log factors by uses the definition of "regret at the origin" of an online learning algorithm, formalized as:
Rr (0)
Σ gt, u4 0) S
(17)
This condition implies that an algorithm maintaining small is inherently conservative: it will perform well if the comparator is close to the origin, but this behavior may come at the cost of performing poorly if the comparator is far from the origin. Before presenting the analysis to Theorem E.5, we first list previously established result on properties of iterates ws produced by any algorithm has constant regret guarantee at the origin as defined in Equation (17). Lemma E.2 was originally appeared (Cutkosky, 2018) then being re-interpreted by (Orabona, 2019). Lemma E.3 from (Zhang & Cutkosky, 2022).
Lemma E.2 (Theorem 5.11 of (Orabona, 2019)). For any OLO algorithm suffers constant regret at the origin (Equation (17)) and Igel < 1, there exist Br E Rd such that ||B:||| and
1-1 (gr, ws)
wi 31
c Σ
for all t E [T).
Lemma E.3 (Lemma 8 of (Zhang & Cutkosky, 2022): Unconstrained OLO Iterate Growth). Suppose assumptions in Lemma E,2 is satisfied. Then for every & E [T), [|w]]]| & e
We first derive an lower bound for algorithms satisfies assumption in Lemma E.2. The construction was originally appeared in Theorem 5.12 from (Orabona, 2019). Finally, the lower bound in the context of adversarial corruptions is presented in Theorem 5.2.
Lemma E.4 (Unconstrained OLO Lower Bound), Suppose assumptions in Lemma E.2 is satisfied, then set [0r,1 .......00000. .0], It,1 = g for all e [T). Then there exists an u" E IRd such that [["") 2ce and
T Σ (g,, u²) 2 |u'll yl
T
1u 12
In
1
+
30
2n
18

---

Unconstrained Robust Online Convex Optimization
Proof. re
Ei= (1bs w.). Then
yrs wi) = e FT-1 (ST; wr)
1=1
by Lemma E.2, there exists some 37 || 1
= -T-1 (gr: (T) rr-1) = - (Wr, 3,)) (E + rT-
Then recursively expand PT-1, " " with Lemma E.2, then for some 3r : || I
T
T
gt, wt) = II
(1
(gt, B.)
t=1
Hence
1gl
ggt w/) S max (1 B1)) II
(1+ (g]) =
1 =e(1+
exxp (1g|2T)
t=1 1
T
1=1
where we used inequality (1 + ) I by setting n =T, x = | for the last step. Rearrange above equation, we have
E 9t,1 12
Σ Me wi) - exxp (1g|2T) exp
=-f(-
ff(( Σ 91,1)
T
1=1
where f(z) exp( x² ) by Theorem K.2 part 1, we have f(x) f (x).
Then by the definition of double conjugate f"
T Le wn) - -
T
- 9t.1) --
sup -- ER
I1,1, un) 5 ((1))
(18)
t=1
1=1
By Theorem K.2 part 2, the supreme achieve at
2
T
Et=1 St,1
ui = vvi-
9t.1) T
2c
Σ
9t,1
exp
2cc T
T
1=1
Substitute uj and set u² = [uj. 0, ... ,0, then Equation (18) becomes:
Σ (gt, wx) 2
Σ (g 1,,,, u) + ("
Σ (gt u²) + (uf)
Rearrange have
T
Σ
(r. w. - 2²) c f*(
(19)
remains to obtain a lower bound to (ut). By Lemma K.4 and Lemma K.3, we have
T
Tlu
f* = 1/2
uill
V
2e
W
T
(1
Tlu
12
1
2
V 2
uiil
0.61m
20a
0.6 In (I+
T2 2c
19

---

Unconstrained Robust Online Convex Optimization
Notice that In (1+ 2 - 0.6 + exp(())2
1.5, hence by Lemma K.5
0.2
Tu 1
wil
In
1+
2
3
2x
T
1
|uily
In
1+
30
2ca
Substitute the lower bound to l (u[) to Equation (19)
T
[1 2T
T
||
12T
gt, we u²) 2 c + luil
1
-
||-0|1
30
2c
30
2c
Theorem E.5. For any algorithm that maintains Equation (17) for some c 0, there exists a sequence of 91, ... 9T and
91. Or such that |19: l. l/ell S 1, Σ 1(3 + g6} = k, and a u² E IRd such that
gt, uy - =x) ② E || (VT+ +k)]
Proof. the proof strategy that algorithm with regret guarantee shown in Equation (17) attains matching lower bound Ô + [|ul|VT) in responding to ge as shown in Lemma E.4. The by reversing the direction of exactly A gradients by taking account into the growth behavior of wa (Lemma E.3) and a particular hard comparator u" constructed in Lemma E.4, we can show regrets during those rounds builds up linearly. Let Ø1, .r,, where || < as defined in Lemma E.4 and suppose algorithm operates on those gradients. Let be the index set S (t E [T] Dt + gr}. Then by the lower bound presented Lemma E.4
Σ ge Wi - u²) Σ
(gt, W. u²) + Σ
(gt 9t: Wi u.
1=1
[=1
2 E(( + || ((v + Σ
(g: Gt, Wt u
EES
for some u² E Rd and ||=||| = 2ce". For t E S, define 9: as follows
Then
T
Σ
(g. we - u²) 2 Ee(c + ||"0 [T) +
u*
we) +
Σ
| || 2*))
||u-|
Y
t5S
2 Ei(c + ||""" ([
Σ
10 || + k||l=*||
CES
Finally, By Lemma E.3 ||w]|| S e2 Hence ||, S |1lu*|1
(gt, wi u²) U(e [|u"||/T) ||u||| k||l=||| á2 (2( ||"x"|| (VT+K))
20

---

Unconstrained Robust Online Convex Optimization
F. Adaptive Thresholding
this section, we formalize the adaptive thresholding and clipping mechanism, namely FILTER, summarized in Section 6.2. This mechanism relies on prior knowledge of big corrupted gradients numbers which is naturally restricted by corruption model in Equation (3). We present this result Lemma F.I, followed FILTER Algorithm and its property in Lemma F.2. Lemma F.1. For 91, ,T and -1.-. gr that satisfies Equation (3), then there are at most &o number of 9t such that || 2G.
Proof. By definition of B (t [T]
19 dell G):
B = {t e [2] 11 0el > G}
= (t E [7] 11: del > G. < [ 1g - del > G, 11 = G}
2 (1 [ [T] [T]
[x] > =
G. Gisinn():))
e [T] |G [ > G}
[t [T] |@dl 2G}
Finally, due to Equation (3), k = [ > {t [T] || > 2GH
Algorithm 3 FILTER: k-lag Thresholding and Gradient Clipping
1: Input: Corruption parameter k, Initial Lipschitz guess: TG > 0.
2: Initialize: Filter threshold h1 = P 0
3: for t= 1 to 7 do
4: Receive Jt-
5: if || > then
6: Set Øi [|ā.]| hrs update counter: n1 1.
7:
n = then
8:
Update Threshold h441 2h,, reset counter: 0.
9:
end if
10:
else
11:
Set of 9t. register rounds P= P (t).
12: Maintain threshold h441 = h4.
13:
endi if
14:
Output gi, hr41-
15:
end for
We display some convenience property of Algorithm FILTERR, notice quantities apart from h, are for assisting analysis only
Lemma F.2. (Algorithm property) Suppose gts Gt satisfies Equation (3), and Algorithm 3 receives Gt, then its per iteration
outputs of h441 satisfies:
(1) h44 h Vt E ==
[T] : 3.)
(2) || S h4, Vt [T]
(3) T = h1 < h2 v ... < hT+1 < max(r, 4G)
(4) [P] T (k + 1) max (fogg 8G $G1,1) 1)
Proof. We show each property in turns.
(1) guaranteed by algorithm line 11-12.
either line line 11 is evoked to compute of
21

---

Unconstrained Robust Online Convex Optimization
he being non-decreasing sequence and h2 is by construction. Hence it remains show upperbound
he; Vt [T 1]. The key to this proof is there are most number of such that |@ > 2G gaurateed by Equation
(3) (See Lemma F.I).
In the case where initial value of 2 2G, then the check point never doubled since each time of doubling requires k ++1 1 number of || exceeds current one. (by line 4-9)
Now, consider 2G, where threshold doubling 1++1 2h, evoked at least once (line 8) with initial value Then hT+11 2% for some N [T', where N is the number of time line 8 was evoked.
On the other hand, least & + number of 9r such that ||xe|| > 2 were observed thus have triggered line 8 so eventually I 2^ Thus by Lemma F.1, 2N S 2G. N S logg 4G
Thus hr+1 2 4G. Moreover, h, is non-decreasing, and we complete the proof.
(4) [P] associated with the number of time which check point doubled. By the proof to property (3) that 2 S 2G, thus N < max (oog, 407.0 1. 1:0) as an upper bound that the number line 8 being executed.
Each execution of line requires exactly ls + 1 number of being clipped. Thus there were (k+1) max (flog, 11.00 number of rounds not being register to P by the time when last time step t" E [T]. when the execution of line 8 happens.
For T 2 >> t", there were less than (k + 1) number of ÿ. not being registered into P, otherwise threshold would have been doubled. Thus
PP S (k + max (loB3> 4G' .0)
(A: + (k max ([noss, 8G') .1
G. Adaptive Tracking
We introduce TRACKER, a simple doubling mechanism for estimating max; ||w, |- as shown Algorithm 4. The properties of TRACKER is displayed in Lemma G.1.
Algorithm 4 TRACKER: Track the Magnitude of wi
1: Input: Initial magnitude guess: TD 0.
2: Initialize: Filter threshold 21 т, (Counter, Set): (n 0, Tv. ()), Checkpoint 1.
3: for (= 1 to T do
4: Receive Wi.
5: if ||w=|| > 2, then
6: Double: 2++1 = 2|[wy]]
7: Update counter: n = n+11
8: Add checkpoint: bn I, initialize new Tn ().
9:
else
10:
Maintain: 2++11 Zt.
11: end if
12:
Register round: T, < Ta U1}.
13: end for
Lemma G.1. (Algorithm 4 property) Algorithm 4 guarantees
(1) [T] is partitioned by To. T2, T2,
Tn, for some N where N I max(0, log, max, l/wall/T).
(2) r = 2t S [w 5 r, Vt E To
(3) || < 2 |1, Vt
Ta, E [N]
(4) 7 = 21 < 22 - ... 2T+1 S max(7, max; [ww]])
22

---

Unconstrained Robust Online Convex Optimization
Proof. We show each property in turns.
(1) partition property can be seen by in the initialization of n. = 0 with increment of (line 6) and whenever counter n updates a new set Tn created (line 7), And E [T] is assigned to Tn for some n (line I1).
As 2T+1 = 2 s 2 max, ||wel|- Thus N I max(0, log, max, [|wx]l/T).
(2) For the time period of n = 0, line was never executed.
(3) By construction Tn [tn,t in ... tn+1 - 11. Vn IN 1I TN [tN,,.. ,T). When & t, the inequality holds. Thus consider 14 E Tn. \ (In), line was triggered, hence 2++1 2t 2t,, and || S zz. On the other hand, by property (2) +1 2 and |lwtt > 2t,, Thus
211 > t +t, +1 2 |wall W Tn (4.)
(4) since and 2++1 is either through line 5 (double) or line 9 (maintain). Thus non-decreasing property holds.
Suppose line was never executed, then #7+1 = 21 = т. Now we consider line was executed at least once. Let t" [2'] be the last time step in which line 5 was executed. Thus
2T+1 = zτ
-- 2z. <2
further upper bound is 2 S max; w for & [t" + 1, 1]. combing with 24 being non-decreasing, we complete the proof.
H. Error Correction
We provides the eπror correction effort as result of trigger signals a 3r from FILTER and tracker, respectively and the chosen regularizer (w) = fi) + w|| as discussed in Section 6.3. We aim to bound OFFSET == ERROR CORRECTION by spliting it into two components:
T Σ 1=1
T t=1
OFFSET
Σ IFP
11.. - of w
Σ wellwell?
+
Σ LE
lige - we
weell Ee(m)
OFFSET;: due to adaptive clipping
OFFSET2:
corruption
and BIAS:
BIAS = ||u|| Σ + E + ||w]|
Σ IEP
119.
Fill +
||
Σ
11gt - FEll
TEP
We begin with helper Lemma followed by the upper bound.
Lemma H.1 (Error of Truncated Gradients). Suppose gt. Ôt satisfies assumptions in Equation (3) and (4). Define z6 as in Equation (5) with d S T for some 0. Then
T
ffll < 2k max(T, G) 11..
Proof. By definition: l|g. 7f < G max G).
Thus
11..
ffll
min (llgr Hfll, max(maaaTT G))
< 2 max T
Σ
min (1lg, - Fill, G)
< 2k max (r, G)
where the last step is due Equation (4).
23

---

Unconstrained Robust Online Convex Optimization
Lemma H.2. Suppose Its It satisfies ussumptions in Equation (3) and (4). Algorithm 3 and 4 initialized with some
TG, TD O. Algorithm in response De and output h441, Algorithm 4 in response to arbitrary sequence we in which max; well S $2", and outputs ze+1- Define
re(w)= = fe(w) + ax|lw]1
where fr is defined as shown in Equation (7) for some c > 0,p = In a= = =TG/ at = at + Br at, S are defined as in Equation (11) and (12). For some "oo+ 7 >
OFFSET 64 64maX(T..
2)
8G' (k: + 1) max (fios:
.1
%
To
16h max (TG. G)
64k max (Ta. G)2
c
+ ETG +
7g In
2 2D + 2KTD max(Ta, G)
CYpTD
and
BIAS S Ô ((Ta(k 1) + (9) [uu1 + e||u|| + maxl:/aax(TTT:000 G))
Proof.
We show three components turn:
OFFSET;:
due to adaptive clipping:
OFFSET,
Σ PEP
119.
Ffll| az a,11u; S EG++hi hy)lluel aellwel1?
(20)
14P
For each fixed E P. we have A4 A - arll upper bound to Equation (20) can be derived by substitute Ya: Vt E P:
w1l2 S supx20 A,X 0₂ 0,
Ai
where A, G + h4 0. Hence an
day'
OFFSET
Σ
(G (G+ h2)2
E(++h(
(G+ hr)²
|P|
64 max G)2
8G (I + 1) max ([nos,
TG .1)
4az
4ra
4%
Ya
EEP
where the last inequality is due to upperbound to |P| by Lemma F2 (4).
OFFSET2: due to corruption:
The upper bound is obtained through two steps. In each step aim to show:
T
T
OFFSET, = Σ
- - 2elll Σ Be
well
Σ
re(w)) o (cck ||
||w; (1)
Σ f((w))
tEP
1=1
E=1
step 1: (O( log(max, [1xx11))
step 2: 50(GRK)
By construction, we have
( 3r 78 1 (1117e))
t= E (N)
B5
0, otherwise
Proceed with analysis step 1, where second line is by Lemma G.I property (1) and value of 3, displayed above:
T Σ
step 1 = Σ
19s
Tell[wwall
Bullwall' ||
TEP
t=1
N
N
Σ 1lg. - de wel
Sen llwe 1|2
n=1
119. &ell[w::1 Σ 21|
Σ
ll.. Tell Σ 3e, | 112
tEPPTo
LEPMYT.
< TD Σ
1g: Hell +
21
Σ
l|9. - ge
Ben 1l we 11
tEPNTo
==1
tEPnTT
==1
24

---

Unconstrained Robust Online Convex Optimization
where the third line is due to Lemma G.I property (3). For the first summand, can define some "imaginary" truncated gradients
9t
2t
min (llrll. TG)
1
Notice ΣtEPnTo 11
3nl1 S Et= 119. -xll S 2k max(Tcx G) by evoking Lemma H.1. Thus,
N
step S 2KTD max G) +
Σ
2/ |l
Σ
19g
- Dell Σ
Be, wlw.,, 11?
(21)
BEPNТ,
n=1
Now we analyze each summands over n in Equation (21). Considering a fixed n E [N]:
wt
Σ
119.
gell
Be,, 1/,,,, 112 sup X
Σ
2 Dell Br.,. X2
X20
tEPNT,
tEPNТH
E ELEPITT 11.r ğrll)
Bip
119c
Dell
1+ Σ
1 # #1)
Y8
MEPNTa
r
11g. - Dell
1+ Σ
1 [2++1 # #2)
MEPNT
i=1
Σ
11g.
Dell
(1 N)
788
MEPNT
where the second to last line is due to number of 241 doubled N = Et 1[2+1 # 2.). Now, we substitute it back to equation (21)
N 2 2(1+N)
step < 2KTD max(TG, G) +
11ge - Tell
n=l
MEPNT
2KTD max(TG, G) 211+N)
119e gell
7
n=1 IEPTT
2
2(1+N)
2kTD max(TG, G)
Σ
11 gell
788
MEP
2 211+ N)
2KTD max(TG, G)
11:: Till
7B
2 NN)
2KTD max G)
(2k max(hr, G))²
7B
25

---

Unconstrained Robust Online Convex Optimization
where the last step is due to Lemma H.1 by noticing |f hy, VI [T]. This mean obtained upper bound step 1:
T
3z wr & 2KTD max(FG. G)+ + 8k max (Te. G) (1 N)
step 1 == Σ
11
3ell|well
Σ
7
EE
8k max (Te. G) (1 + max 10, 2 muxx: 1/ 11
2KTD max(Ta, G)
TD
7/3
8k max (Te. G) 2 loga 2 max. [|
< 2KTD max G) +
TD
7/8
16k max (Ta, G) In 2 +
4 max. ||
2KTD max G)
TD
Y/3
where the second step is due Lemma G.1 (1). Thus, is sufficient bound step 2 defined as follows to obtain bound for OFFSET2 that is independent of max, ||well:
16k max (Te, G)² In (2 + 4 max, l/wel |!
step =
TD
Se(we)
7
evoke Lemma B.I with a = eTG/c
16h² max (Ta, (Ta,G)²1n In (2+ 4max, ||wrell
mmax well + ETG
79
16k max (TG, 2)2
In(2 + X) CTD X + ETG
sup
7/8
for A, B. 0, (2 - BX obtains its supremum
X A/B - ->> 22 Henee supx>-2 Aln(2 + +X) BX
Aln(A/B) - A 2B. By substituting A = 16A
G2)
B we have
7/
16h. max (TG, Gy²
(
64k max (TG, G)2 -1) 1) + 2 eTa
In
7/3
C78TD
Thus step and step 2 implies
16h. max (Te, G)2
64k2 max (rG, G)2
OFFSET2 S CTG +
In
+ TD + 2kTD max(ra, G)
713
CYSTD
BIAS: comparator related term
T
BIAS = ||u||2
at Σ fe(u) + ||u|||
Σ
11ge 96
||||||
Σ
11g.
3.1
1=1
tEP
t
T
T
= -|uu||
Σ
a0 Σ f((u) + ||a||| Σ
11g: - 3ill
1=1
T
||u|23
01 Σ f((u) + || max (hr, G)
T
||]]|
Σ
Σ
f(( + 16 max (TO. G)
(22)
26

---

Unconstrained Robust Online Convex Optimization
where the last It remains to show the first terms in Equation (22) be bounded by desired orders. For the first summand, Ee a+ E. 04 + Ex Sz. Thus by definition and Lemma F.2 (4):
8G Σ on S TalP1 S (k 1) max (loos
= 1) S ( TG
and Lemma G.1 (I) implies N v 0 max, (|w))) and the condition max; | S 122" implies:
T
1 2 # 21) Va In (1 + N) 2 ((1))
Σ Σ 3: = 78 1+
Σ
E 12241 # 21}
t=1
The second term in Equation (22) can be upper bounded by Lemma B.1 by substituting a = cTa/c:
||u|
In
fe(u) s 3c 3/
In 1
+ (cllul)
Thus,
BIAS S Ô ((7) + 1) (e) ||u|| + c|lu|l ||a[(=aaxxFe: G))
I. Base Algorithms for unknown G
In this section, we show the Epigraph-based regularization scheme developed by (Cutkosky & Mhammedi, 2024) guarantees appropriate composite regret defined as:
(A( = Σ (gt, wi - u) rr(we) - re(u)
when re(w) ft(w) az 11 and the sequence a, satisfies assumption in Lemma H.2. That is
(+) (ge, w. u) - fc(wr) - fe(u) + as (1werl ||ul(3)
Thus, can be used as a base algorithm A that can be supplied to Algorithm when the G 2 maxt ||ge|] is unknown. The proof is identical to (Cutkosky Mhammedi, 2024) except a behaves differently here. Nevertheless, we summarize as Algorithm and shows the regret guarantee attained stilled suffices in achieving our aim.
Epigraph-bused Regularization is geometric reparameterization: suffices to design two learners: An, to wy and Ay to produce yr, where (W,, y1) W {(w,y) v) y [|]||?] Id+1, Then it suffices to design algorithm to bound:
(²(2)) ()) S Σ (gt, we u) f((w:) - fe(u)= + at arly ||
(23)
This is sum of two regrets for the pair w. and y subject to 2 ||,, 1|. This problem can be solved by using pair of unconstrained learners (Aw, Ay) that produce (w,, Dt) E Rd+1 and guarantee regret bounds:
R (u) 2 Σ (g wi u) + f((()) fe(u)
27

---

Unconstrained Robust Online Convex Optimization
and
T
17 (u) 2
(r ||ull?)
By a black-box conversion from enforce the constraint: this involves a projection Iw : Rd+1 - :=
learning due to (Cutkosky & Orabona, 2018) (Theorem 3) to
: {(w, y) : y 2 [| (line 7) and a certain technical correction to the gradient feedback (11-15). These procedures output variables (w,, yr) Iw (( 9r)) that satisfies the constraint and guarantees 12 (u) I Pe (u) and PG (u) < ftt'(w). (u). In particular, we choose Algorithm 2 as A and (Jacobsen & Cutkosky, 2022) Algorithm as Av. We summarize the entire procedure as Algorithm 5 and its gaurantee on RtA (u) is displayed as Theorem I.3. We first present useful definition and a helper Lemma.
Definition L.I For the set W = (ww, y) 2 [| S Rd+1, and arbitrary (we, y) E W and (ι,, () E RR+1 and some h,,7 > 0:
(1) norm: (w, v)lle = 1n2 2|011 + ?2y
(2) dual norm: [[(,, g)),,,
||el y² b
72
(3) distance function of (w. () W: Se((t), 0)) inf 12 [[(w,)) (10; 0l
(4) subgradient at (t0, ú): (( ú)) hf -- 2+ 18-8888) 2)a1 killl (
h/(0-w)
72(0- v)
(5) projection map W ((w,, ù)) argmin (w. [1 y) (1ē; D)
Lemma I.2. In the same notation as Definition L.I, if 19 S h and az E 10.7). 7.. and (6,", 6.) = V... 0.))
then
|o S 2h
6 S 22
Proof. Since [| |l < he and a E 7]. (9,, al)l s 2. On the other hand VS:(((, = and
1
18 2
1166,,8))1k, 18,)
h2
72
Thus
| 12
10712
2
7/
1 42
and 16
This implies both
S 2.
Theorem I.3, Suppose gt, 91 satisfies assumptions in Equation (3) and (4), and having access to gf as defined in Equation (5) with he provided by FILTER (Algorithm 3). with =/c,, Jo + 78. for some e, c, Nas Na, TG, TD 0, Algorithm 5 guarantees:
(x) S Ô (shr- + ||ul| |ull (1a
19)) 1))))
In addition, the produced iterate satisfies max, [|wll| 52T
Proof. Notice that we used wh is outputs from some unconstrained learner and wts St being their projection W2 in Algorithm 5 denote. We begin analysis from Equation (23):
RA S
(g,. wi u) + fo(we) f((u) arly [1]l3))
28

---

Unconstrained Robust Online Convex Optimization
By Cutkosky & Orabona (2018) Theorem 3
T
T
-
0r
+ 5. 1 u) + f((w)) fe(u)= +
Σ
(ar + 6 - -1uu(3)
1=1
Notice ||vbz|| < ||wzll, thus fe(we) S S(((ee)
T
1h + 0g W4 - u) + f(())) Se(u)+ +
(ar + 60) - ||ul13)
(24)
Re (w)
12,"(()
Since 7t =3. ar = at + B S Na + 78 = 7. Thus, by Lemma L2, 10 + 85" S h4 + 22he S 3h, and lac + 67 S
+ 2 < 3y. By Theorem C.2:
R$ (u) S Ō (ehr IlullooTT)
and Theorem 10 of Cutkosky & Mhammedi (2024) shown
(
T
R Av (1) 2 ccbr+ (str+
|ull2
72 + Σ
Thus, we can bound Equation (24) by combine both bounds:
T
(4( So ehr + |llllt + |ull2
72
+
ag
[=1
since a,==E a: aa+EE Br, by the same computation as that of Lemma H.2, E. at ((Ta(k+1) and E, 3r s <((g))
< o chr + +lllllllTTTT [I0] /22 + > (17a (k: + + 78)
% and S 7a
<ō chr +||u||br + |uull (Ta + (k) +)+ 70))
29

---

Unconstrained Robust Online Convex Optimization
Algorithm 5 Robust Online Learning By Exploiting In-Time Offset
1: Input: Time horizon T, FILTER (Algorithm 3), TRACKER (Algorithm 4),
an algorithm Ay with optimal rate in parameter-free literature (e.g., Jacobsen & Cutkosky (2022) Algorithm 4), corruption parameter k, base algorithm parameters c, regularization parameters 0, Yax 1-
2: Initialize: Initialize Algorithm as A. with Initialize A, with
Initialize FILTER with TG (outputs b2 as a conservative lower-bound guess for G).
Initialize TRACKER with TD (outputs 2; as a conservative lower-bound guess for max, [tee] I.
3: for t to 7 do
4: Receive vie from Ami Receive dt from Ay-
5: Compute operators in Definition 1.1 with h2 7.
6: # Explicit projection of (ι,, 91) through projection map Hy as in Definition 1.1.
7: Compute projection: (We, yt) = WT ((t0) 9:)).
8: Play we, receive gi h441 from FILTER. Send wy to TRACKER and receive 2++1-
9: Compute at, Be as defined in Equations (11), (12).
Compute quadratic regularizer weights: a, = 04 + Bt.
11:
# Compute gradient correction direction (6t" 8%) with ll+,e and VS, as in Definition I.I.
12:
Compute: (8
(l ae)ll Ve Dt)).
13:
# Send corrected gradients:
14:
Send ( (0f + +(("), 2h(+1) to Aw-
15: Send (a: + 5)) and 31y to Ay.
16: end for
J. Regret Analysis with Unknown G
We provide the regret guarantee of Algorithm 1 when using an instance of Algorithm base learner A. Theorem J.1 (Restated Theorem 6.1). Suppose 9t. St satisfies assumptions in Equation (3) and (4). Setting re(w)
fe(w) + aul[u]] where ft is defined in Equation (7) with parameters: Yas 7a, TG. > 0, there exists an algorithm A as base algorithum such that Algorithm guarantees:
sTa/c,p InT, "aa 718. for some
(u) Ô max rG. G) + || max(TG, Gi (VT+ +k) + cllul| + (Ta + 1) + Ta) [lul(²)
1 max (TG, 2) 64h² max (TG, G)
c ΣTT + 2kTD max(Ta, G)
In
a/
CYSTD ([10g2
64(k + max G)²
8G
.1)
max
Ya
TG
Proof. Note the definition of Rr(u), the proof is completed by combining Lemma H.2 and Theorem L.3
K. Fenchel Conjugate
Here we collects basic properties of Fenchel conjugate, see reference such as (Bertsckas, 2009; Orabona, 2019), and previously established Lemma used Appendix E for completeness.
Definition K.1. Let f gd 1-00, oo), the Fenchel conjugate f* is defined
(0) = sup (0, x) fx)
ZE3d
the double conjugate f* is defined
(*) = sup (0,z) (x)
mcRd
Theorem K.2. Let f Rdd oo)
1. f(x) fr) d iff f convex and lower semicontinuous
30

---

Unconstrained Robust Online Convex Optimization
2. (0,z) (x) achieves its supremum in at xx iff x² (0)
Lemma K.3. (Theorem A.32 of (Orabona, 2019)) The Lambert function W - + R+ is defined as (x)) exp (W (x)), for >
and (x) > 0.61n(1 + + for O.
Lemma K.4. (Theorem A.3 of (Orabona, 2019)) Let a, 0, f(x) b eexp(x* xx? /2a.). Then the Fenchel conjugate is
(0 -va0 valol (1
a02
222
W
002 82
where W.) is the Lambert function. Lemma K.5.
3
V
Vx
2
Proof. The proof is based on rearrange 2 3. the condition is equivalent
=1
Given x > 0, divide both side by v
Vx 1 Vi
1
Rearrange and we complete the proof.
31


Reviews:
[{"review_id": "n87ClDuIPi", "reviewer": "Reviewer_w7uA", "summary": "The paper studies the challenging problem of online convex optimization (OCO) in an unconstrained domain under the presence of adversarially corrupted gradient feedback. Unlike classical OCO, where gradient estimates are assumed to be accurate or only subject to benign noise, this work makes no statistical assumptions on the corruptions. Instead, it considers arbitrary (and potentially adversarial) deviations in the gradient signals. A regret bound is provided in the paper. The matching lower bounds are provided that demonstrate the tightness of the upper bounds under certain regimes.\n\n## update after rebuttal\n\nI appreciate the authors for the rebuttal. Although it does not address my concerns, I found some insight for the parameter setting issue. I decide to keep my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. As this work focuses on the theoretical foundations of robust online convex optimization, we look forward to systematically investigate practical applications in future work.\n\nIn terms of hyper-parameter, the only required user input is the corruption level $k$. Even without exact knowledge of $k$, our theoretical results suggest setting $k = O(\\sqrt{T})$ guarantees the classical OCO regret bound $\\tilde{O}(\\sqrt{T})$ as long as the true corruption level is less than $\\sqrt{T}$, which tolerates a significant range of corruption problems. We also look forward to an empirical study of the impact of mis-specifying $k$.\n\nIn terms of the scenario of gradient-norm being large, existing theory in adversarial online learning suggests regret scales with the maximum gradient norm. Our results actually help combat this somewhat: a few large outlier gradients could be modeled as “corruptions”, and our regret would not scale with their value. Nevertheless, we acknowledge this limitation and are interested in future developments that mitigate this when large gradients are common.", "claims_and_evidence": "The claims of the paper are clear and have evidence.", "methods_and_evaluation_criteria": "The theoretical parts of the paper is clear, but I think this paper lacks some convincing numerical studies to support the theoretical findings.", "theoretical_claims": "While the theoretical contributions of this paper is interesting, the paper would benefit from a more extensive discussion on the practical implications of the algorithms. For example, insights into how the proposed methods perform on real data or in simulated adversarial settings would strengthen the overall impact.\n\nAlthough the paper analyzed the regret bounds under more general assumptions, the bound is still built based on an implicit assumption that the gradient is bounded, which may not be true for some real applications (or the upper-bound is very large).", "experimental_designs_or_analyses": "1. The numerical study of the proposed algorithm is limited. Including more experiments on simulation data and real datasets that illustrate the algorithm’s performance under various corruption regimes could provide practical validation of the theoretical findings.\n 2. Parameter Analysis: A sensitivity analysis regarding the choice of hyperparameters would be a welcome addition, potentially guiding practitioners in implementing the methods.", "relation_to_broader_scientific_literature": "The theoretical findings of this paper are interesting which can contribute to the area of online optimization algorithms.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "Please see the above comments.", "other_comments_or_suggestions": "Please see the comments above. Some numerical evidences are highly recommended to be added.", "questions_for_authors": "Please see the comments above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oq5IIQBIMJ", "reviewer": "Reviewer_Z9rr", "summary": "The authors investigate online convex optimization (OCO) in an unconstrained domain under corrupted gradient feedback. They introduce a new measure of corruption, denoted as $k$, which accounts for both the number of corrupted rounds and the magnitude of gradient deviations. Given $k$, their proposed algorithm achieves a regret bound of $\\mathcal{O}(\\| u \\| G (\\sqrt{T} + k))$ for any comparator, provided the gradient norm bound for uncorrupted rounds is known. In cases where the gradient norm bound is unknown, they propose a filtering approach that guarantees a similar regret bound with an additional term of $\\mathcal{O}( (\\| u \\|^2 + G^2) k)$. Additionally, they establish matching lower bounds (up to logarithmic factors) for any choice of comparator $u$.\n\n## update after rebuttal\nI would like to thank the authors for their response, and I have decided to retain my original positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for validating the theoretical contributions. Regarding the constant regret interpretation after Corollary 6.2, it relies on setting $\\tau_D = O(1/k)$, which is an initialization parameter used in the doubling trick to track $\\max_{i \\le t} |w_t|$. Note that if $k$ is unknown, we may set $\\tau_D=1/\\sqrt{T}$ to achieve constant Regret(0) for and $k\\le \\sqrt{T}$, which the range in which our algorithm suffers $\\tilde O(\\sqrt{T})$ regret overall. Apologies for not specifying this properly in the theorem statement - we will clarify this in the manuscript and correct the noted typos.", "claims_and_evidence": "The claims are theoretical and are supported by thorough discussions and arguments presented in the main text, which appear sound and reasonable. However, I have not reviewed the proofs in the supplementary material in detail.", "methods_and_evaluation_criteria": "The paper only has theoretical contributions.", "theoretical_claims": "The discussions and arguments presented in the main text appear sound and reasonable. However, I have not reviewed the proofs in the supplementary material in detail.", "experimental_designs_or_analyses": "The paper only has theoretical contributions.", "relation_to_broader_scientific_literature": "The paper borrows some ideas from Zhang & Cutkosky (2022), Cutkosky & Mhammedi (2024), and van Erven et al. (2021). In particular, it adopts the composite loss function method from Zhang & Cutkosky (2022) to handle large corrupted gradients. The authors propose a novel filtering technique to handle unknown bounds on the gradient norms of uncorrupted rounds, which serves a similar purpose to the filtering technique used in van Erven et al. (2021).", "essential_references_not_discussed": "The references are cited and discussed adequately.", "other_strengths_and_weaknesses": "In my view, the paper’s primary strength lies in the development of a filtering technique to address the unknown gradient norm bound and associated challenges in an unbounded domain. The paper is well-written, providing a strong motivation for the problem while clearly articulating both the problem itself and the main obstacles in addressing it. The authors effectively discuss their techniques and results, making the work accessible and easy to understand.\n\nThe primary weakness of the paper is its reliance on established ideas, especially their similarities to Zhang & Cutkosky (2022), which diminishes the overall novelty of the work. The key technical tools employed are well-known, which somewhat limits the scope of the contributions.", "other_comments_or_suggestions": "A few minor typos:\n\n1. Line 187, col 2: \\cite should be replaced with \\citep.\n2. Line 330, col 1: \"the a\" appear together", "questions_for_authors": "The paragraph before Corollary 6.3 claims that the regret with respect to the baseline point $u = 0$ is **constant** no matter what $k$ is. However, the regret bound in Corollary 6.3 has a $\\mathcal{O}(k)$ dependency. Is there something that I am missing here?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B8sKedfPHV", "reviewer": "Reviewer_EewU", "summary": "The paper addresses the case of online learning on the unconstrained domain with corrupted gradient feedback with no assumptions on the corruptions nature. The paper provides an algorithm with regret guarantee $\\|u\\|G(\\sqrt{T} + k)$ for the case when the \nLipschitz constant is known, and provide the algorithm extension with adaptive thresholding with an extra additive penalty of $(\\|u\\|^2 + G^2)k$ where $k$ reflects the total corruption level, and $u$ is any comparison point. The paper provides very thorough introduction, discusses all the challenges of the considered problem setup, carefully provides the analysis of both cases of known and unknown Lipschitz constant giving a lot of intuition and clear flow.\n\n## Update after rebuttal:\n\nI thank the authors for the response. I have also read the other reviews, and I decided to keep my initial score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. On the non-differentiable case: we agree that OCO via linearized losses naturally extends to subgradients, and thus our results apply to non-differentiable convex functions as well.\n\nRegarding the term $E_{\\bar P}$ (line 331, left), this should indeed be $g_t - \\tilde{g}_t^c$ as suggested. This was a typo in the main text; the expression was handled correctly in Appendix (line 1282) and was referred to as $offset_1$. We will revise the manuscript accordingly", "claims_and_evidence": "Yes. However, it should be considered that in the non-differentiable case the sub-gradients might be non-unique.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, just the ones in the main body of the paper, I did not check the appendix. There is an unclear part in line 331, I wrote a question regarding it in the questions section.", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "They provide new regret bounds for the unconstrained online convex learning with corrupted feedback. The work in certain sense extends to the setting on the unconstrained OCO and improves upon a method in van Erven et al. (2021) which considered bounded domain. The previous works on unconstrained OCO only considered stochastic unbiased feedback perturbations.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "The paper is very clearly written and is a pleasure to read. All statements seem to be thorough, relations to the previous related works are discussed.", "other_comments_or_suggestions": "- In line 198, right side, I believe that the sum of $r_t$ should be lower bounded not by the $O(\\cdot)$ but rather $\\Omega$ notation since it is a lower bound.  Just a rate in $O$ will not be enough, even if $r_t$ grows with the same rate as error, but slower 2 times, their subtraction with not be cancelled out but growing.\n- line 178 right side: Upper bound on ERROR I believe should be $2kG \\max_t\\|\\omega_t\\|$ instead of $kG \\max_t\\|\\omega_t\\|$. That will influence also on the constant $c$ later in line 218 right side and further.", "questions_for_authors": "- line 331: If we want to bound a truncation error, $E_{\\bar P}$ defined in eq. (10) as $\\|g_t - \\tilde g_t^c\\|$, why here do we bound $\\|\\tilde g_t - \\tilde g_t^c\\|$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tXN9vpyB2y", "reviewer": "Reviewer_h1f3", "summary": "The paper presents an algorithm to solve unconstrained OCO when the observed gradient might be corrupted. They first present an algorithm when $G := \\max_t ||g_t||$ is known, by truncating the observed gradient to ensure the norm is less than a specified $h_t$, and adding a regularizer to limit the growth of $||w_t||$. When using $h_t = G$, this results in a guarantee in $O(||u|| G (\\sqrt{T} + k)$ where $k$ measures the amount of corruption.\n\nWhen $G$ is not known, the authors use a clever doubling trick to ensure that in each epoch to ensure that $h_t$ is close to  $\\max_t ||w_t||$. They also add a quadratic regularizer when doubling to ensure that the error from truncation remains bounded. This result in a similar regret guarantee with an additional $O(||u||^2 + G^2) k$.\n\n## update after rebuttal\n\nI decided to maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the positive feedback. Regarding norms, our algorithm extends to other norm settings as long as $k$ is measured accordingly and dual norms. We will also revise the manuscript to fix typos.", "claims_and_evidence": "All claims seems to be thoroughly proved.", "methods_and_evaluation_criteria": "The criteria used is the regret, which is standard in online learning.", "theoretical_claims": "The authors explain the ideas behind each of the theorems. I read mainly the ideas detailed in the main body of the paper, but not the proofs in appendix.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "As far as I know, this is the first paper to tackle OCO with corrupted gradients in the unconstrained setting.\n- van Erven et al., 2021 tackled the case of potential outliers in the standard constrained setting, which is a special case of this paper.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "Strength:\n1- It is the very first approach to the unconstrained robust OCO in the literature\n2- They combine well several tricks, from unconstrained OCO and robust OCO, to solve it. They also provide new ones that arise from this unique setting\n\nWeaknesses:", "other_comments_or_suggestions": "Typos:\n- line 20, abstract: $||u|| \\to u$.\n- line 69 $1\\{True\\} = 0 \\to 1 \n- Multiple times $|u| \\to ||u||$ or $|w_t| \\to ||w_t||$.\n- line 697: unclear what terms are in the $\\sum_{t=1}^T$, maybe add a parenthesis.", "questions_for_authors": "Your algorithm focus on $|| ||$ being the euclidean norm but could it be applied for other norms with their associated dual norm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies online convex optimization in an unconstrained setting with adversarially corrupted gradient feedback. The authors propose algorithms with provable regret guarantees for both known and unknown gradient bounds, using a novel filtering strategy and tailored regularization to maintain robustness. The work addresses a challenging and underexplored problem and provides tight theoretical guarantees with clear motivation and analysis.

The paper is well-written and makes a solid theoretical contribution. Strengths include the originality of the problem setting, the soundness of the proposed methods, and the clear structure of the presentation. The main weakness is the lack of empirical validation, though the authors position this as future work. Minor issues around notation and clarity were acknowledged and addressed.
Decision: Accept (poster)