Contaminated Online Convex Optimization
Authors: Tomoya Kamijima
Shinji Ito
Venue: Accepted by TMLR ()

Abstract: In online convex optimization, some efficient algorithms have been designed for each of the individual classes of objective functions, e.g., convex, strongly convex, and exp-concave. However, existing regret analyses, including those of universal algorithms, are limited to cases in which the objective functions in all rounds belong to the same class and cannot be applied to cases in which the property of objective functions may change in each time step. This paper introduces a novel approach to address such cases, proposing a new regime we term as \textit{contaminated} online convex optimization. For the contaminated case, we demonstrate that the regret is lower bounded by $\Omega(\log T + \sqrt{k})$. Here, $k$ signifies the level of contamination in the objective functions. We also demonstrate that the regret is bounded by $O(\log T+\sqrt{k\log T})$ when universal algorithms are used. When our proposed algorithms with additional information are employed, the regret is bounded by $O(\log T+\sqrt{k})$, which matches the lower bound. These are intermediate bounds between a convex case and a strongly convex or exp-concave case.

Published in Transactions on Machine Learning Research (10/2024)
Contaminated Online Convex Optimization
Tomoya Kamijima
kamiijimn---omnoy11100 (ig. wg..ee...e.ooeeoo.o....o. www.ee.lkoooo.............
Deportment of Mathematical Informatics
The University of Tokyo
Shinji Ito
Deportment of Mathematical Informatics
The University of Tokyo
NEC Corporation (affiliation upon submission)
RIKEN AIP
Reviewed on OpenReview: https: // openreviee. net/ formf? id- QdGtwyDgub
Abstract
In online convex optimization, some efficient algorithms have been designed for each of the individual classes of objective functions, e.g., convex, strongly convex, and exp-concave. However, existing regret analyses, including those of universal algorithms, are limited to cases in which the objective functions in all rounds belong to the same class and cannot be applied to cases in which the property objective functions may change in each time step. This paper introduces novel approach to address such cases, proposing a new regime we term as contaminated online convex optimization. For the contaminated case, we demon- strate that the regret is lower bounded by 2(log T vk). Here, h signifies the level of contamination in the objective functions. We also demonstrate that the regret is bounded by O T V log when universal algorithms are used. When our proposed algorithms with additional information are employed, the regret is bounded by O(log T + vk), which matches the lower bound. These are intermediate bounds between a convex case and a strongly convex or exp-concave case.
1 Introduction
Online convex optimization (OCO) is an optimization framework in which convex objective function changes for cach time step E 21, T}. OCO has a lot of applications such as prediction from expert advice (Littlestone & Warmuth 1994 Arora et al., 2012), spam filtering (Hazan) 2016), shortest paths (Awerbuch &
Kleinberg 2004), portfolio selection (Cover 1991 Hazan al.) 2006), and recommendation systems (Hazan
& Kale 2012). The performance of the OCO algorithm is compared by regret (defined Section 3). As shown in Table I it is already known that sublinear regret can be achieved for each function class, such convex, strongly convex, and exp-concave, and the bound depends on the function class. In addition, these upper bounds coincide with lower bounds, so these are optimal. However, these optimal algorithms are applicable to one specific function class. Therefore, we need prior knowledge about the function class to which the objective functions belong.
To solve this problem, many universal algorithms that work well for multiple function classes by one algorithm have been proposed (Hazan et al., 2007 Van Erven & Koolen 2016 Wang et al.) 2020 Zhang et. al. 2022; Yan et al. 2024). For example, the MetaGrad algorithm proposed by Van Erven & Koolen (2016) achieves ((VT)- reggeet for any sequence of convex objective functions and an Ollog -rrrggttt if all the objective functions are exp-concave. Universal algorithms are useful in that they can be used without prior knowledge about the objective functions. Some universal algorithms are introduced in Appendix A.3
A notable limitation of the previous regret analyses about universal algorithms is that they apply only cases where all the objective functions fe.fe.... fr belong to the same function class. Therefore, for example, if some objective functions in limited number of rounds are not strongly convex and if the other

---

Published in Transactions on Machine Learning Research (10/2024)
Table 1: Comparison of regret bounds. The parameter d is the dimension of the decision set.
FUNCTION CLASS
UPPER BOUNDS
LOWER BOUNDS
Convex
(vvT)
((VT)
Zinkevich
2003
Abernethy al. 2008
a-exp-concave
(((d/a) log T
(((d/a) log T)
Hazan al.
2006
Ordentlich & Cover
1998
k-contaminated a-exp-concand
((d/aa) log + Vkd
M(d/a) T Vk) (This work, Corollary
(This work, Corollary
5.5
4.8)
k-contaminated a-cxp-concave (with additional information)
((d/a) log To Vk)
(((d/a)) log vk) (This work, Corollary
(This work, Theorem
6.2
4.8)
>-strongly convex
((1/A) log
(((1/) log 7) Abernethy al.
Hazan al.
2006
2008
I-contaminated A-strongly convex
(((1A) log + log 7)
(((1/A)
T Tog vk)
(This work, Corollary
5.7
(This work, Corollary
4.9
k-contaminated A-strongly convex (with additional information)
log v
logT
(This work, Theorem 6.2)
(This work, Corollary
4.9
objective functions are strongly convex, regret bounds for strongly convex functions previous studies are not always valid. This study aims to remove this limitation.
1.1 Our Contribution
In this study, we consider the situation which the function class of the objective fi may change each time step We call this situation contaminated OCO. More specifically, in k-contaminated OCO with function class F, suppose that the objective function fe does not necessarily belong to the desired function class F (c.g., exp-concave or strongly convex functions) in l rounds out of the total T rounds. Section introduces its formal definition and examples. This class of OCO problems can be interpreted between general OCO problems and restricted OCO problems with FF (F-OCOs). Intuitively, the parameter k E [o, T] represents the magnitude the impurity in the sequence of the objective functions, and measures how close the problems are to F-OCOs; & and k = respectively correspond to F-OCO and general OCO.
intermediate setting
The contribution of this study can be summarized as follows: (i) We introduce contaminated OCO, which captures the situations in which the class of the objective functions may change over different rounds. (ii) We find that the Online Newton Step, one of the optimal algorithms for exp-concave functions, does not always work well in contaminated OCO, as discussed in Section 4.1 (iii) We present regret lower bounds for contaminated OCO in Section 4.2 (iv) We show that some existing universal algorithms achieve better regret. bounds than ONS for contaminated OCO, which details are given in Section (v) We propose an algorithm that attains the optimal regret bounds under the additional assumption that information of the class of the previous objective function is accessible in Section 0
Regret bounds of contaminated cases compared to existing bounds are shown in Table The new upper bounds contain bounds in cxisting studics for exp-concave functions and strongly convex functions as a particular case (A: = 0). Additionally, the new lower bounds generalize bounds in existing studies for convex functions, exp-concave functions, and strongly convex functions. cases where only gradient information is available, there is a multiplicative gap of O O(yTog between the socond terms of the upper bounds and the lower bounds. This gap is eliminated when the information of the class of the previous objective function is available.
2

---

Published in Transactions on Machine Learning Research (10/2024)
To prove regret lower bounds in Table I construct distributions of problem instances of contaminated OCO for which any algorithm suffers a certain amount of regret in expected values. Such distributions are constructed by combining suitably designed problem instances of F-OCO and general OCO.
To derive novel regret upper bounds without additional information in Table 1 we exploit regret upper bounds expressed using some problen-dependent values such as a measure variance (Van Erven & Koolen 2016). By combining such regret upper bounds and inequalities derived from the definition of k-contaminated OCO, obtain regret upper bounds, including the regret itsclf, which can be interpreted as quadratic inequalities in regret. Solving these inequalities leads to regret upper bounds in Table
We develop algorithms that can achieve optimal regret upper bounds, taking into account the function class information of the previous function. To accomplish this, we modified two existing OCO algorithms: the Online Newton Step (ONS), as introduced by Hazan et al. (2006), and the Online Gradient Descent (OGD), presented by Zinkevich (2003). The modification is changing the update process depending on the function class of the last revealed objective function.
2 Related Work
In the context of online learning, adaptive algorithms (Orabona 2019) have been extensively studied due to their practical usefulness. These algorithms work well by automatically exploiting the intrinsic properties of the sequence of objective functions and do not require parameter tuning based on prior knowledge of the objective function. For example, AdaGrad (MeMahan & Streeter 2010 Duchi et al. 2011 is probably one of the best-known adaptive algorithms, which automatically adapts to the magnitude of the gradients. Studies on universal algorithms (Hazan al. 2007 Van Erven & Koolen 2016 Wang et al. 2020 Zhhang et al., 2022 Yan et al. 2024), which work well for several different function classes, can also be positioned within these rescarch trends. Our study shows that some of these universal algorithms have further adaptability, ie., nearly tight regret bounds for contaminated settings.
van Erven et al. 2021) has explored similar setting to ours, focusing on robustness to outliers. They regard rounds with larger gradient norms than some threshold as outliers and denote the number of outliers as k, whose definition differs from ours, They have defined regret only for rounds that are not outliers, terming it robust regret, and have shown that the additional ((k) term is inevitable in bounds on robust regret.
Studies on best-of-both-worlkd (BOBW) bandit algorithms (Bubeck & Slivkins 2012) and on stochastic bandits with adversarial corruptions (Lykouris et al.) 2018 Gupta et al., 2019) are also related to our study. BOBW algorithms are designed to achieve (ncarly) optimal performance both for stochastic and adversarial environments, e.g.. respectively. Stochastic bandits with adversarial corruptions are problems for intermediate environments between stochastic and adversarial ones, in which the magnitude of adversarial components is measured by means of the corruption level parameter C 2 A BOBW algorithm by Bubeec & Slivkins (2012) has shown to have regret bound of O(log T VC 7) as well for stochastic environments with adversarial corruptions, which is also nearly tight [Ito 2021 p. In the proof of such an upper bound, an approach referred to as the self-bounding technique (Gaillard et al. 2014 Wei & Luo 2018) is used, which leads to improved guarantees via some regret upper bounds that include the regret itself. Similar proof techniques are used in our study as well.
for stochastic and O( for adversarial environments,
3 Problem Setting
In this section, we explain the problem setting we consider. Throughout this paper, we assume functions fi, f2, are differentiable and convex.
3.1 OCO Framework and Assumptions
First of all, the mathematical formulation of OCO is follows. At each time step E [T] f1.2..... T)), convex nonempty set X' c IRd and convex objective functions fi, .2,.... - st-1: X - R are known and
3

---

Published in Transactions on Machine Learning Research (10/2024)
is not known. A learner chooses action 2; X and incurs loss fi(z)) after the choice. Since fe is unknown when choosing Tt, it is impossible to minimize the cumulative loss Σ (xx) for all sequences of J.. Instead, the goal of OCO to minimize regret:
R Σ f(()))
Σ f(()). #EA
min
Regret is the difference between the cumulative loss of the learner and that of the best choice in hindsight. The regret can be logarithmic the objective functions are A-strongly convex, i.c., f(y) (Vz)+ y x) + 2 |1 - yll for all æ; y E X, or o-exp-concave, iee, exp(-a](2z) is concave on Remark 3.1. The type of information about Jt that needs to be accessed varies depending the algorithm. Universal algorithms only utilize gradient information, while the algorithm presented in Section c requires additional information besides the gradient, such as strong convexity and exp-concavity. The lower bounds discussed in Section 4.2 are applicable to arbitrary algorithms with complete access to full information about the objective functions.
Next, we introduce the following two assumptions. These assumptions are very standard in OCO and frequently used in regret analysis. We assume them throughout this paper without mentioning them.
Assumption 3.2. There exists constant D > 0 such that || - yll S D holds for all x, E X.
Assumption 3.3. There exists a constant G > 0 such that V ax) < G holds for all x E X and t [2].
These assumptions are important, not only because can bound | yll and [[ but also because we can use the following two lemmas:
Lemma 3.4. Hazan 2016) Let f: R be an o-eer-ccocaae function. Assume that there crist constants D,G > such that x yl & D and [[V](()]] & G hold for all a. E X. The following holds for all I (1/2) min (I/(G), a} and all a, E X:
f(x) 2 f(y) (Vf(y), x 4) 7 (VV(l)) y))
Lemma 3.5. [Hazan] 2016) X IR is tuice differentiable X-strongly convex function salisfying [V]())]] S for all x E X, then il is A/Ge-erp-concave.
Lemma 3.5 means that exp-concavity is milder condition than strong convexity, combining with the fact that log (a is not strongly convex but 1-exp-concave.
3.2
Contaminated Case
In this subsection, define contaminated OCO and introduce examples that belong to this problem class. The definition is below.
Definition 3.6. For some function class F, sequence of convex functions (fi, f2...., fr) belongs to k- contaminated FF if there exists set of indices I c [T'] such that |/| k and ft F holds for all [T]V.
For example, if functions other than k functions of them are a-exp-concave, call the functions k- contaminated a-exp-concave. And especially for OCO problems, if the objective functions are contaminated, we call them contaminated OCO.
The following two examples are functions whose function class varies with time step. These examples motivate this study.
Erample 3.7. (Online least mcan square regressions) Consider the situation where batch of input-output data (ar,s, be,)) E Rd x IR (i E (1))....,,)) is given in each round and we want to estimale æ which enable to predict x (a, x). This can be regarded as an OCO problem whose objective functions are fx()) = (1/m) E ((a,,,
b2 These functions are A-stronggy convex, where X, the minimum cigenvalue of the matrix (2/n) Ei_ a. Let i(A) = I[t [T] X AHl for any > Then (f1, f2...., .....,,y fr) is contamnntee A-strongly convex.

---

Published in Transactions on Machine Learning Research (10/2024)
Erample 3.8. (Online classification by using logistic regression) Consider the online classification problem. A batch of input-output data (t,, E Rd [+1] (i E (1,2....,n) is given in each round & and we want to estimate a which enable to predict b == sgn((ss x)). Suppose that the objective functions are given by ft(x)= = (1/n) Ei= log(1 + exp(-br,s (aL.;. x))) Exp-coneavity of fe(æ) on {a E Rd ||=||| I 1) changes with time step. Especially, in the case a1 Ct: bb, = bb St is exp(-Ilag (ll--llal)-exx--ooeeee l)-xxx--concaee, as proved in Appendix B.1 Let k(()) == 1(t E [T) at < <a] for any a > 0, where at defined so that ft ox-ex-- concave. Then (2........,.r)) is -oottminnm o-exp-coneave.
Remark 3.9. In the two examples above, constants and a in the definition of A-strong convexity and a- exp-concavity can strictly positive for all time steps. However, since the regret bounds are (((I/A) log and (((d/a)(o log T) for A-strongly convex functions and a-exp-concave functions respectively, if and a are O1/TT), then the regret bounds become trivial. Analyses in this paper give nontrivial regret bound to such a casc.
4 Regret Lower Bounds
4.1 Vulnerability of ONS
This subsection explains how Online Newlon Step (ONS) works for contaminated exp-concave functions. ONS is an algorithm for online exp-concave learning. Details of ONS are in Appendix A.2 The upper bound is as follows.
Proposition 4.1. If sequence of objective functions (f1 f2,...,frr is k-contaminated a-erp-concave, the regret upper bound of ONS with 7 = (1/2) min(1/(GD);a) and E = 1/(>>DD)) is (((d/)) ((dd/))log] k).
This proposition is proved by using the proof for noncontaminated cases by Hazan (016)). detailed proof is in Appendix B.2 This upper bound seems trivial, but the bound is tight because of the lower bound stated in Corollary 4.6
Before stating the lower bound, we introduce the following theorem, which is essential in deriving some lower bounds of contaminated cases.
Theorem 4.2. Let FF be an arbitrary function class. Suppose that functions 91.92 are the functions such that (gg (T)) and (TG) are lower bounds for function class F and convex functions, respectively, for some OCO algoritlm. If a sequence of objective functions belongs to k-contaminated F, then regrel in the worst case (gg (T) + 92 (k)) for the OCO algorithms.
Remark 4.3. In Theorem 1.2 if the lower bounds Ogg (T)) and ((ge(T) are for all OCO algorithms, then the lower bound 0(gi (T) + (2)) is also for all OCO algorithms.
To derive this lower bound, we use the following two instances; one is the instance used to prove lower bound
Ry (gg (T)) for function class F, and the other is the instance used to prove R₂ = (gg) (k)) for convex objective functions. By considering the instance that these instances realize with probability 1/2, we can construct instance that satisfies
E[Rr] Nig (T)) + 92(k)),
for all OCO algorithms. A detailed proof of this proposition is postponed to Appendix
B.3
Theorem 4.2 implies that, in contaminated cases, we can derive interpolating lower bounds of regret. The lower bound obtained from this theorem is Mgg (T)) if T, and ((g2(T)) if = T. Since the contaminated case can be interpreted as an intermediate regime between restricted F-OCO and general OCO, this result would seen reasonable. This lower bound applies not only to ONS but also to arbitrary algorithms.
To apply Theorem 4.2 to ONS, we show the following lower bound in the case of convex functions. This lower bound shows that ONS is not suitable for convex objective functions.
Proposition 4.4. For any positive porameters ry and E, ONS incurs Q(T) regret in the worst case.
To prove this proposition, consider the instance as follows:
fe(x)) UKF, E X D-D2 D/2), 21 -G,
5

---

Published in Transactions on Machine Learning Research (10/2024)
where
(-1YGG
t tı; t h1 St, 0,
1/
G
-G
t 11, 2t, <0,
and 4 is a minimum natural number which satisfies 4 2 (1 + (1+2
Then, we can gel
DG2 111T0D/22 2(1 , - log 7 1+ -T
1
G² T
2
G
RT 2
G
2
A detailed proof of this proposition is postponed to Appendix B.4 Remark 4.5. Corollary states states the lower bound that holds only for ONS. However, if some better algorithms are used, the lower bound can be improved. Therefore, it is not a contradiction that the general lower bound in Table is better than that of ONS. This is also true for Corollary 4.6 which is about the contaminated case.
The lower bound of a-exp-concave functions can be derived follows. The lower bound of 1-exp-concave functions is log (Ordentlich & Cover 1998). Here, when divided by a, L-exp-concave functions turn into a-cxp-concave functions, and regret is also divided by a. Hence, the lower bound a-exp-concave functions is (((d/a) T).
We get the following from this lower bound for exp-concave functions, Proposition 4.4 and Thcorem 4.2
Corollary 4.6. If a sequence of objective functions (f1, f., is k-contaminated a-erp-coneave, regret in worst case is (((d/a) log kk,, for ONS.
This proposition shows that the regret analysis in Proposition 4.1 is strict. While ONS does not work well
for contaminated OCO, universal algorithms exhibit more robust performance. In Section 5 some universal algorithms on this point.
analyze
Remark 4.7. For the 1-dimension instance above, ONS can also regarded as OGD (Algorithm 2 in Appendix A.1] with ((1/t) stepsize. This implics that we can show that OGD with @(1/t) stepsize can incur (TT) regret in the worst case. Therefore, for k-contaminated strongly convex functions, regret in worst case is ((11A) log k), for OGD with ((1/t) stepsize.
4.2 General Lower Bounds
In this subsection, we present regret lower bounds for arbitrary algorithms.
Using Theorem we get lower bound of k-contaminated exp-concave functions. As mentioned in Sention 4.1 regret lower bound of n-exp-concave functions is (((d/a) log 7). From this lower bound and that of convex functions is I(GDVT) (Abernethy et al. 2008). we can derive the following lower bound. This corollary shows that k-contamination of exp-concave functions worsems regret lower bound at least Q(GDV)).
Corollary 4.8. Tf GDVR), for all OCO algorithms.
ST) is k-contaminated a-eep-concave,, regret in worst cnse is (((d/o) TogT
According to Abernethy et al. (2008) the regret lower bound in the case of X-strongly convex functions is 2(( log T). Therefore, following a similar corollary is derived in the same way. Corollary 4.9. If a sequence of objective functions (f1, f2...., fr) is k-contaminated X-strongly convez, regret in worst case ((GG/A))oog + GDVR), for all OCO algorithms.
5 Regret Upper Bounds by Universal Algorithms
In this section, we explain the regret upper bounds of some universal algorithms when the objective functions are contaminated. The algorithms we analyze in this paper are multiple cta gradient algorithm (MetaGrad
(Van Erven & Koolen 2016), multiple sub-algorithns and learning rates (Maler) (Wang et al. 2020 and
6

---

Published in Transactions on Machine Learning Research (10/2024)
universal strategy for online convex optimization (USC) Zhang et al. 2022 Though there are two variations
of MetaGrad; full MetaGrad and ding MetaGrad, in this paper, MetaGrad means full MetaGrad. We
denote R7 == 2t= I (f((z)) - fe(x)), R7 = Er= (Vfr(z)), - x), VF = >x ((Vf( x, x))² and
= GD Ei_1 ==12 ==12..
Concerning MetaGrad and Maler, following regret bounds hold without assuming exp-concavity strong convexity:
Theorem 5.1.
Van Erven &
Koolen 2016
For MetaGrad, R is simultaneously bounded by
OGGD/Tlog log ,) and by
R
R
O( O(VVVllogT + GDdlogT),
for any x E R.
Theorem 5.2. WWag et al. 2020 For Maler, R... is simullaneously bounded by O(GDVT),
R S Rs = 0 (1v VVdlog and
R4 S Ri = OVWW/(WWWWW)) logT)
for any x E X.
Though Theorem 5.2 is derived only for x E argmingex* Ei= Jt(2x) in the original paper by Wang et al. 20200, the proof is also valid even when x is any vector in X, so we rewrite the statement in this form. The proof of this generalization provided in Appendix [B.] Further explanations of universal algorithms are
Appendix A.3
Concerning the regret bound of contaminated exp-concavity, the following theorem holds. This theorem's 's assumption is satisfied when using MetaGrad or Maler, and the result for them is described after the proof of this theorem.
Theorem 5.3. Let at be a constant such that Se is ay-erp-coneave (if Se is not exp-coneave, then o is 0) for each I. Suppose that
- rra(i)
R RT O (VV
(1)
holds for some functions Tı, r2, and point a E X. Then, it holds for any 7 > O that
R R= = o (D
where biy = Et max - 7/7, 0}: 7 == (1/2) min(1/ oz).
Before proving this theorem, we prepare lemma. The proof of this lemma is given in Appendix B.6 Lemma 5.4. For all a, 2 0, if x S Vox + b, then I < 3(a + b)/2.
Proof of Theorem
5.3 From Lemma 3.4 we have
RT
(J((z)) fe(x))
((VSi(Z:)) xr -x) (VVi x -xx))
T
R
I v
7-
(VV[(((VV))))))))))))))) xx.)²
7t
2
< Rの
V +
Σ
7 it
n2
2
2
< <
1
h D2
2
2
7

---

Published in Transactions on Machine Learning Research (10/2024)
If RG < <0, O is an upper bound, so it is sufficient to think of the case R7 2 0. In this case, we have
V - Fer + G²
(2)
From equation there exists positive constant such that
R s
( (T)
(
(V (2210g G2D2 (((T)++al))
C Ceri (T)
CGD kyri(T) Cr2(T).
(3)
The second inequality holds from the inequality 2 and the last inequality holds from the inequality Vo+Us vx + Vi for x, y 2
From Lemma 5.4 with a = (2/7) and b CGD Cra(T) we have
PG S ( (C
3
From this inequality and R7 R7. Theorem 5.3 follows.
The core of this proof is inequality 3 which can be regarded as a quadratic inequality. Solving this inequality enables us to obtain a regret upper bound for contaminated cases from a regret upper bound for non-contaminated cases.
Theorem 5.3 combined with Theorem 5.1 Theorem 5.2 and Theorem A.1 in the appendix gives upper bounds for universal algorithms; MetaGrad, Maler, and USC. The following corollary shows that, even if exp-cooncvve objective functions are k-contaminated, regret can be bounded by an additional term of ([Vkllog]) This regret. bound is better than ONS's in the parameter k.
Corollary 5.5. If sequence of objective functions f2....... fr) is k-contominated a-erp-concave, the regret bound of GeadGrad, Maler, and USC with MetaGrad or Maler as an expert algorithm is
Rr O 0 log T GD Todkloo//)))))
(4)
where 7 : (1/2) min(1 o).
We only give proof for MetaGrad and Maler here, and the proof for USC will be provided in Appendix
B.7
Proof. As for MetaGrad and Maler, from Theorem 5.1 and Theorem 5.2
R = VVVoooo GDdlog
holds for any x E X. Thorefore, by Theorem 5.3 we have
R = 0 logT + GD 1o
hiydlogg /oggttDDhy
where GD = 0(1r) is used, which follows from & = (1/2) min min(1/GGD))
Here, by satisfies
kg
T
max
Yt 1
2
0
Σ
11-20 2
< k.
?
#: 77 K
8

---

Published in Transactions on Machine Learning Research (10/2024)
The incquality follows from the fact that if " y, then a2 < a holds. Hence, we have
R$ o 0 log T GDV
especially, we get the regret upper bound
As for strongly convex functions, we can get a similar result as Theorem 5.3
Theorem 5.6. Let d be a constant such that fa is de-strongly conver (if St is not strongly conver, then X is 0) for each t. Suppose that
(WWFm(()+
RG S Rr
holds for some functions rı, r2, and point x E X. Then, it holds for any X > O that
1 = 0 (D
G²
where ly = E max - 0/.
This theorem can be derived in almost the same manner as the proof of Theorem 5.3 other than using the definition of strong convexity and 1x.- A more detailed proof is in Appendix B.8
Theorem 5.2 and Theorem A. in the appendix gives upper bounds for universal algorithms; MetaGrad, Maler, and USC. This corollary shows that, even strongly convex objective functions are k-contaminated, regret can be bounded by an additional term of O( loggT) if Maler or USC with Maler as an expert algorithm is used.
Theorem 5.6 combined with Theorem
Corollary 5.7. If a sequence of objective functions J2...,, ST) is k-comlaminaled A-strongly conver, the regret bound of MeadGrad, Maler, and USC with Maler as an eapert algorithm
R -0(((=to) dlog + GDV kå
T T
where d is d in the case of MetaGrad and in the case of the other two algorithms.
This corollary can be derived from Theorem 5.6 in almost the same manner as the proof of Corollary 5.5 A more detailed proof in Appendix B.9 and Appendix B.10
Remark 5.8. If (fi, J2, fT) is ki-contaminated a-exp-concave and ka-contaminated X-strongly convex, then we have two regret upper bounds:
RT -0 ( GDDD++Gooo
from Corollary 5.5 and
R (
G2 (lGD) ålogT +GV k2dlog
from Corollary 5.7 Here, strongly convex functions are also exp-concave functions from Lemma 3.5 There- fore, if x/G² 2 a, then kj k2.
Remark 5.9. Note that the universal algorithms analyzed in this section do not require additional information other Uhan the gradient, which is a valuable property in practical use. However, comparing lower bounds in Corollary 4.8 and Corollary 1.9 with upper bounds in Corollary 5.5 and Corollary 5.7 respectively, there are gaps between them. This implics that our upper bounds in this section or lower bounds Scction 4.2 4.2 might not be tight. As we will discuss in the next section, this gap can be removed additional information on function classes are available while it is not always the case in real-worle applications.

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm Algorithm using additional information
Input: convex set X C R. #1 E T. D. a, X
1: Set y = (1/2) min( for 1 do
/2G/D, D. Ao = Eld.
Play 2y and observe cost ft (zt). Update:
MIa
tE S
te S2
A, A
ld.
tEU,
D 2 nU
5:
Newton step and generalized projection:
y++1 = 22 A f((()))
II (B+++) = arg min |l++1 - x=12a11 }.
1t+1
#c
6: end for
6 Regret Upper Bounds Given Additional Information
In this section, we propose a method that achieves better bounds than those of universal algorithus discussed in the previous section under the condition that the information of the class of the last objective function is revealed. The experimental performance of this method is shown in Appendix [
We demote S == {L E [T] ft is A-strongly convex), S₂ = {l E [ Js is a-exp-concave), U = (T) U S2), and k = JU]- The algorithm using additional information is shown in Algorithm 1 (Ia is d dimensional identity matrix, and ||- Il' means ()) This algorithm is a generalization of OGD and ONS. Indeed, (S1, S2, U) ([7), 0, 0) gives normal OGD and (S1, S2, U) (6. [T], 0) gives normal ONS.
Before stating the regret upper bounds of Algorithm prepare the following lemma:
Lemma 6.1. Let {aree be the sequence generaled by Algorillm 1 and SI, S2, U, and k be as defined above. Then, the following inequalities hold:
G²
AD
Σ
[V/((a))) 5 S log log
1+
|S1]
(5)
V2G
rES
d
XD
7GD
Σ (x:;)) S - log
1
|S +
12 + vT)
(6)
V2G
122
(ES
Σ ( VVGDD +1 1).
(7)
NEU
Proof. Incquality 3 can be obtained as follows:
S
1111 ds
G²
AD
[++((
A,
G2
Amin A.)
S
2
+
S
6
6 As
X
log 1
V2G (1l
tES,
IES;
where Amin (A.) is the minimum eigenvalue of the matrix A,, which at least increases by À when E S1.
10

---

Published in Transactions on Machine Learning Research (10/2024)
We can bound the left-hand side of the inequality
6
follows:
[V
Σ
tr (A, V
KE
tr tr (A: Ai-1))
7 1ES2
Atl
$
log
7
A
rE92
The first inequality is from Lemma
B.5 in Appendix
B.11
Since | 2 AA-il (Vt S1 UU),
|
T
A
log
S
log
A
A
:ES2
1=1
1
Arl
log
7
Ao
d
XD
7GD
log
1 +
|
+
182] + vk)
/2G
v22
The last inequality is from the fact that the largest eigenvalue of Ar is at most V2G/D + A|S1|| +7 (G/D)v2k.
Inequality 77 can be obtained as follows:
Σ
5
1
Amin (A:)
LEU
LEU
G²
LEU
+ mml
|0
DV2
G
1
G
IEU + 20
GD
V2
1
V2GD(Vk+1
Using this lemma, we can bound the regret of Algorithm ! as follows: Theorem 6.2. Let be defined at the beginning of this section. Algorithm
guarantees
R = <
G + log T + +DVK))
Proof. When S1, from the definition of strong convexity,
((H((x,) - fr(x=)) (2))) xt - -x") - -N1120 x=11
(8)
holds. When E S2, from Lemma 3.4
2(f((z:) f((x") 2 x --)x -V(((((())))) 2 x x2))² holds. When 1 U, since fi is convex,
(9)
G
2(f((z)) - f((x')) < (zi) o - --)=))--- D 2 nu
4 x x1
2 x x112
(10)
D D22
11

---

Published in Transactions on Machine Learning Research (10/2024)
holds. From the update rule of A,, inequalities 88)
can be combined into one inequality 19 and 10
Glu
2(f((z)) f(()))) 2 2 x²) ((A, A (=) x²), I. x²)+ D DV 22 x= 11,
where ly is the indicator function, i.e. Lt(t) e U, and (t(() 0 otherwise. The first and second terms in the right-hand side can be bounded follows:
2 ( fe(xe) Dz - x²) - ((A, A.- 11-1) (2 - xx') )²),,0 Dt - x²)
-x)
= 2 (A,(1 - x1), x² - xxi) - 1| - x²112, + ||=, xt" 11 1
||3/41 2ell2a. || x² x'1.2. + 11 x 2e'11a,. 1
< |/ - 2x.1.3. - -1|024+1 x= == + || - x 11
The first equality is from the algorithm, the second equality from the law of cosines, and the last inequality is from the nonexpansiveness of projection. Therefore, we have
Gle(() DV
2(J((r.) (i(x")) s l1ye+1 a.. 2.1.... [|00+] ""IlA, + ||ac, x0 12
0z xr" a=11
2 no
By summing up from t to T, we can bound regret as follows:
2RT
1i41 zell3, + +1
x'1120 +
Σ
21 x²11
D
/
nu
GD
[ +- + DJE+
V2
Vi
(V)((,,) (1 A- + Σ [[
1 +
Σ
[V
A. + +V2GD(VV++))
LES
IES2
IE
From Lemma 6.1 we can gel
G2
AD
(1+
AD
2GD
S2 + V1)) +2V2GDVR+1
2R -
log
1+
S11
+ log
1+
St
+
X
V2G
V2G
V2
G
d
log T + +DDVK)
=
+
The key point of Theorem 6.2
is that the second term of the regret upper bound is proportional to vk. Compared with Corollary 5.5 we can see that additional information improves the regret upper bound. Remark 6.3. Algorithm
written in general form, and it is better to set S2 = 0 in the contaminated strongly convex case. This is because Algorithm [ needs O(d3) computation to calculate A, if S2 is nonempty. When S = 0 or S2 = 0, the regret bound in Theorem 6.2 is reduced to O((d/)) log T GDVR) or O((G2/A))ogg + GDVk) respectively.
Remark 6.4. As mentioned in Remark 5.9 the algorithms analyzed in this section need information that is not always available in the real world. Therefore, the improved regret bound in Theorem 6.2 is theoretical, and regret bounds for universal algorithms explained Section 5 are more important in real applications. However, the algorithm in this section has the notable advantage that its regret upper bounds match the lower bounds.
7 Conclusion
In this paper, we proposed a problem class for OCO, namely contaminated OCO, the property whose objective functions change in time steps. On this regime, derived some upper bounds for existing and
12

---

Published in Transactions on Machine Learning Research (10/2024)
proposed algorithms and some lower bounds of regret. While successfully obtained optimal upper bounds with additional information of the function class of the last revealed objective function, there are still gaps of O(VdlogT) or O(vlog I') between the upper bound and the lower bound without additional information. One natural future rescarch direction to fill these gaps. We believe there is room for improvement in the upper bounds and the lower bounds seem tight. Indeed, lower bounds in this study interpolate well bet ween tight bounds for general OCO and for (restricted) F-OCO.
Acknowledgments
Portions of this research were conducted during visits by the first author, Kamijima, to NEC Corporation.
References
Jacob D. Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Conference on Learning Theory, pp. 414-424, 2008.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012.
Baruch Awerbuch and Robert D Kleinberg, Adaptive routing with end-to-end feedback: Distributed learn- ing and geometric approaches. In Procecdings of the thirty-siath annual ACM symposium Theory of Compaling, pp. 45 53, 2004.
Sébastion Bubock and Alcksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pp. 42.1-42.23, 2012.
Thomas Cover. Universal portfolios. Mathematical Finance, 1(1):1-29, 1991.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. second-order bound with excess losses. In Conference on Learning Theory, pp. 176-196. 196. PMLR, 2014.
Anupam Gupla, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 1562 1578. PMLR, 2019.
Elad Hazan. Introduction to online convex optimization. Found. Trends Oplim., 2:157-325, 2016.
Elad Hazan and Satyen Kale. Projection-free online learning. In 29th International Conference Machine Learning, TCML, 2012, pp. 521-528 2012.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69:169-192, 2006.
Elad Hazan, Alexander Rakhlin, and Peter Bartlett. Adaptive online gradient descent. Advances in Neural Information Processing Systems, 20, 2007.
Shinji Ito. On optimal robustness to adversarial corruption in online decision problems. Advances in Neural Information Processing Systems, 34:7409-7420, 2021.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and Computation. 108(2):212-261, 1994.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial cor- ruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 114-122, 2018.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. Conference Learning Theory, pp. 244, 2010.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXim:1912.19911 2019.
Erik Ordentlich and Thomas M. Cover. The cost of achieving the best portfolio in hindsight. Math. Oper. Res., 23:960-9822 1998.
Tim Van Erven and Wouter M Koolen. Metagrad: Multiple learning rates in online learning. Aduances in Newral Information Processing Systems, 29, 2016.
Tim van Erven, Sarah Sachs, Wouter M Koolen, and Wojeiech Kotlowski. Robust online convex optimization in the presence of outliers. In Conference Learning Theory, pp.
PMLR, 2021.
Guanghui Wang, Shiyin Lu, and Lijun Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Uncertainty in Artificial Intelligence, pp. 659-668. PMLR, 2020.
Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, pp. 1263 1291. PMLR, 2018.
Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. Universal online learning with gradient variations: A multi-layer online ensemble approach. Advances in Neural Information Processing Systems, 36, 2024.
Lijun Zhang, Guanghui Wang, Jinfeng Yi, and Tianbao Yang. A simple yet universal strategy for online convex optimization. In International Conference on Machine Learning, pp. 26605-26623. PMLR, 2022.
Martin A. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Interna- tional Conference on Machine Learning, 2003.
A Existing Algorithms and Known Regret Bounds
This section introduces existing algorithms for OCO and their regret bounds.
A.1 OGD Algorithm
In OCO, one of the most fundamental algorithms is online gradient descent (OGD), which is shown in Algorithm g An action Ig is updated by using the gradient of the point and projected onto the feasible region X' in each step. all the objective functions are convex and learning rates are set @(1/v(), the regret is bounded by O(VT) (Zinkevich, 2003), and if all the objective functions are X-strongly convex and learning rates are set (1/tt,, the regret bounded by (((1/) Tog (Hazan et al. 2006
A.2 ONS Algorithm
If all the objective functions are a-exp-concave, ONS, shown in Algorithm 3 works well. This is an algorithm proposed by Hazan et al. (2006) as an online version of the offline Newton method. This algorithm needs parameters 7,8 > 0, and if 7 (1/2) min(1/(GD)) a) and = 1/(-2D?) then the regret is bounded by ((d//a)ogg) To
Algorithm 2 Online Gradient Descent (Zinkevich] 2003)
Input: convex set X C Rd T, σ1 E X, parameters 1: for / 1 to do
2: Play æ, and observe cost fxx))). Gradient step and projection:
Vi+1 2, n. (z(x)
x441 = 1x( = min min (1 =
#Ex
4: end for
14

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 3 Online Newton step (Hazan et al.) 2006
Input: convex set X C R T, œ1 X' parameters 7,5 > 0, A. Ela
1: for / = 1 to T do
2: Play 2y and observe cost (xt).
3: Rank-1 update: A, = A + V (V.
4: Newton step and generalized projection:
Vi+1 3t - -9 11-11 A (e(x),,
Lt+1 11 (y++1).
end for
Algorithm MetaGrad Master (Van Erven & Koolen 2016)
Input: T, G. D, C = 1 [11 log2 T))
1: Set 7/ = (0=22//(55)
म.
for i = 0, 0.l......(1))..... [(1/2) log, T
2: for 1= T do
3: Get prediction x," of slave for each i.
Play Zz:
Σ nh nax
3t
Σ a 17
5: Update for each i:
(7 (x).) = -n: (2t xx (x(:)) + +1, 1
2 e(?e""(()?))
T++
6: end for
A.3 Universal Algorithms
In real-world applications, it may be unknown which function class the objective functions belong to. To cope with such cases, many universal algorithms have been developed. Most universal algorithms are con- structed with two lypes of algorithms: a mela-algorithı and expert algorithms. Each expert algorithm is an online learning algorithm and not always universal. In each time step, expert algorithms update at, and meta-algorithm integrates these outputs in some way, such as a convex combination. In the following, explain three universal algorithms: multiple eta. gradient algorithm (MetaGrad) (Van Erven & Koolen 2016), multiple sub-algorithme and learning rates (Maler) (Wang et al. 2020 and universal strategy for online convex optimization (USC) (Zhang et al. 2022
First, MetaGrad is an algorithm with multiple experts, each with a different parameter y as shown in Algorithm g and 5 In contrast to nonuniversal algorithms that need to set parameters beforehand depending on the property of objective functions, MctaGrad sets multiple nj so that users do not need prior knowledge. It known that MetaGrad achieves O(VTlog T), O((d/)) log T') and ((d//a) log regret bounds for convex, A-strongly convex and a-exp-concave objective functions respectively.
Sccond, Maler is an algorithm with three types of expert algorithms: a convex expert algorithm, strongly convex expert algorithms, and exp-concave expert algorithms, as shown in Algorithm D to They are similar to OGD with ((1/Vt) stepsize, OGD with ((1/t) stepsize, and ONS, respectively. Expert algorithms contain multiple strongly convex expert algorithms and multiple exp-coneave expert algorithms with multiple parameters 7 like MetaGrad. It is known that Maler achieves O(VT). ((1/A) log T) and O(d/a) log regret. bounds for convex, X-strongly convex and o-exp-concave objective functions respectively.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 5 MetaGrad Slave (Van Erven & Koolen 2016)
Input: convex set X' C R T, 7. D
1: Set n² = 0, Σ = Da
2: for t = to I" do
3: Issue æ. to master.
4: Update:
D2 Da-d + 2nj² Vel(ax) (V((a))
2 x.
11 1 (1 + 21 V (c x7 - 2x)) Viaa).
x = 11x (
(8%+1).
end for
Algorithm 6 Maler Meta (Wang et al. 2020)
Input: T, G, D, C 1+ 1/(1 (1/2) logg T1)
Set of 1v(2GDvT),
7h = 2 (5GD) for 0, l,.,,... (1122) log2 T7.
Set xe 1/3, nu. = x| 2: = C/(3(i 1) 2)) for 0, 1,..., [(1/2) log, T7.
for t = to do
Get predictions æc, from Algorithm and w.ec xt an from Algorithms and for all i.
Play
gF + E, (T. ma 2h + at mp ni.yy
gbnl Σ, (m
th1 1)1 at mp..mm))
Observe gradient V (xxe) and send it to all experts.
7: Update weights:
nf (w))
Ti-1
D ni. c 07 (zx!
T+
for each i,
4.
T++1
Tid
for each i,
where
Φ Σ
E. (m?ti))))) + ग. ni Σ. 1t (m. + nfe"" Eim ((0.)
((x) au (V 2t x) + (17 GD)2
(0(()) 1h (V/
022 | - 2012
(()) (V.( x;))) 1² (VV (xx),, Ct xx)²
8: end for
Finally, USC is an algorithm with many expert algorithms, as shown Algorithm 10 In contrast to Maler, which contains OGD and ONS as expert algorithms, USC contains more expert algorithms. To integrate many experts, USC utilizes Adapt-ML-Prod (Gaillard et al., (014)) as meta-algorithm, which realizes universal regret bound. Concerning the regret bound of USC, there is theorem as follows.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 7 Maler Convex Expert (Wang et al. 2020)
Input: convex set X C R T, G, D, 77
1: Set iz 0.
2: for t = 1 to 7" do
3: Send of to Algorithu B
4: Receive gradient f((())) from Algorithm 6
Update:
D TFGV
i4
11x os
Vclla)))
6: end for
Algorithm Maler Exp-concave Expert (Wang et al. 2020)
Input: convex set C Rd. T, D.
Set x!! 0, 3 = 1/2, Σ (1/(82D2))LL
for = 1 to do Send x²" to Algorithm
4: Receive gradient (ar, from Algorithm
5: Update:
Σ(+1 = Eg + Ve, (x} (Ve
nh #441
+ x! Σz (((
6: end for
Theorem A.1. Zhang et al. 2022 Let & be set of expert algorithms and æt be output of ith algorithm in time step. Then,
T (f(())) - fc(s)) S Vf((z)) xt) < 4GG
4G + Σ (V - =x
Vlog /log/E/
[=1
where I' O(lg
In USC, expert algorithms are chosen so that [8] O(log T) holds. This theorem holds without assuming exp-concavity or strong convexity. In addition, it is known that USC achieves O(vLT log log T), O((1/A) (min(log Lr, log Vr + log log T)) and (d (log Lr, log Vr + log log T)) regret bounds for convex, >-strongly convex and a-exp-concave objective functions respectively, where L = min Σ f((x) O(T), V1 = DT maxzex [f(x)) - = O(T).
Algorithm Maler Strongly Convex Expert (Wang et al. 2020)
Input: convex set X C Rd T, G,
Set T. 0.
for = to T do
3: Send x=""" to Algorithm
4: Receive gradient (e( from Algorithm t
5: Update:
1
2 IIx
Vs
2
6: end for
17

---

end for Published in Transactions on Machine Learning Research (10/2024)
Algorithm 10 Universal Strategy for Online Convex Optimization (USC) (Zhang al 2022)
Input:
Astr: Aerp, and Acon, which are sets of algorithms designed for strongly convex functions, exp- concave functions and general convex functions respectively; Peer and Peap: which are sets of parameters of strong convexity and exp-concavity respectively. Initialize = 0.
for each algorithm A E Astr do for each À E Pstr do
4: Create an expert (AA, A).
5: Update & U (
6: end for
for each algorithm A Aeap do
for each Pezp do
10: Create an expert (.).
11: Update & = E
12: end for
13: end for
14: for each algorithm A E Acon do
15: Create expert E(A).
16: Update & = E ((A).
17: end for
18: for t= to T do
19: Calculate the weight p of each expert E by
D W 1-1
p
181
j=1
20: Receive of from each expert E E E.
21: Output the weighted average H; Liel plat.
22: Obscrve the loss function ft(.).
23: Send the function fe(-) to each expert E E'E E.
24:
end for
B MISSING PROOFS
In this section, we explain missing proofs.
B.1 Proof of the Exp-Concavity of the Function in Example 3.8
In this subsection, we present the proof of the exp-concavity of the functionf, in Example 3.8 in the case 0e, Oe, bi,; b, Before the proof, we introduce the following lemma.
Lemma B.1. Huzam 2016) buice--dfferenddabll function f: Rd - is a-erp-conenve x if and only if
v²f(2) 2 [V)
Using this lemma, we can check the exp-concavity of the function f..
Proof. By differentiating fer we have
b,0t ff(()) 1 exp(b: (a,, x))
ba exp(bi (ar, x)) fe(r))
(1 + cxxp(b, (a,, x)))²
18

---

Published in Transactions on Machine Learning Research (10/2024)
For all v E R
exp(be (ar, x))
0
bi (a., v),,0)
(1 + exp(b; (ar, a)))
holds, and combined with Lemma B.1 fi is exp(- || |||]=]|xxp-cooccv
B.2 Proof of Proposition 4.1
This subsection presents the proof of Proposition 4.1
Proof. Let x" E arg min #E
Ei. fe(x)). We can bound regret as follows:
RT
(f(())) -f((²))
(V)e(zz), - (2))
(V[(( xx") (V)
7t
((V ((V.)( xx))
x²))²
2
((Vf) x-) x-)- (VV( - -xx0))))))+))))))))
x'))²)
Σ 1:
\ 7
D²
2
2d 1 kGD, $ y logT
where "t defined in the same way as defined in Theorem 5.3 The first incquality is from Lemma 3.4 In the last inequality, the first term is bounded by (2d/7) log T because of the proof of ONS's regret bound by Hazan 2016). The second term is bounded by (1/4)&GD from S 1/(2GD) by definition of 7.
B.3 Proof of Theorem 4.2
This subsection presents the proof of Theorem 4.2
Proof. Let and I2 be instances used to prove lower bound Pr Sgg (T)) for function class F and R& = (g2(k)) for convex objective functions, respectively, and fu, (i 1,2) be objective functions of 4 time step f, and X; be sets which decision variables of I, belong to. Here, take a set X' so that there exist surjections d;: X' + X4. For this X, let I be an instance whose objective function at time step t is f1, o Φ1 and 12 be an instance whose objective function at time step 1 is /2,, Φ2 L < k; and some function in F whose minimizer is the same the minimizer of Σ f2,1 otherwise. For these instances, consider the case that instances J and I realize with probability 1/2. In this case, the expectation of regret satisfies
1
E = (9 (T)) ((o(k))
2
= 2gg (2()),
for all OCO algorithms. Therefore, Theorem 4.2 follows.
B.4 Proof of Proposition 4.4
This subsection presents the proof of Proposition 4.4
Proof. Consider the instance as follows:
fe(x)) U22 X
(- D/2], 21 -D/2
19

---

Published in Transactions on Machine Learning Research (10/2024)
where
(-1YGG
t t1; t h1, 2t, 20,
4/=
G
-G
12 11, 2t, <0,
and 8 is minimum natural number which satisfics t, 2 (1+ D/ -T. Then,
T s (-T 1n)
CD
G2-D22 T +1
GD
min FEA
Σ [(x)
<
(11)
2
1+
2
The second incquality is from t s + 10 (2) - T +1 1. If ni, 20,
T
4-1
T
Σ
f(())) = G
Σ
(-1)( 24 + G
Σ
(12)
Zt.
1=1
1=/
For the first term, since
=
for all L. E (T), and if < 41 we have
V1+1 22 - (0 (-1)-
Now, F441 is defined as
D
D
y141 > 2'
2
D
D
Fe+1=
Vt+1
S Vt+1 S 2'
2
D
D
2
Yl41 <
2' 22'
and therefore, we get
D
(-1)²
1 15
2
St
D
1-1 (-1)"G
(-1)²a
t> 12:
2
7(8 G78)
8=12
where to is a minimum time step which satisfics Gy + Gct)
< ic., t > 1/(1GD) - E/G?. From
this, for sufficiently large T so that l2 S 41 - 2, we have
12
D h-1
D 1-1 (-1)-
Σ (-1)'
x = G
Σ
(-1)
Σ
(-1)
(-1)
Σ
2
2
7(E G2s)
1=1
1=1++1
t2 -
G²
stt+l
GD +
2
7
8 G2
|=1++1 12
1 1
G² 4-
(-1)0t++1
GD +
2
G2s
(=#+1
12
1
G2
1
GD-
2
7
G
sm12
4
G
21-2 ds
2
GD
2
7
4-1 + G2
12 -
1
1
+ (t1 - 2)
GD-
-
log
2
7
6 (12 1)(²
(1 1
G2
log
T
(13)
20

---

Published in Transactions on Machine Learning Research (10/2024)
Next, for the second term of equation 12 if Tt, 2 0 and 2 f1; we then have
Mt+1 = - + G ス 21 7 ---
and since r++1 2 vt+1 holds from 1/+1 S 21 S 2 we have
ye+1 2 24, - (t t1) 2
2 (T - 11 G
T 1 G 3-21
(1+ (1+2G-D/2--T -1
T
1)
G-
D
2
Therefore, from
t-1 7
It
we have
T
T
t-1 Σ
G
Jt = G Σ
F1
7- + +
7
(=h
t=
1
Σ Σ 8-1
7 1=
1 T-1 Σ
T
Σ 8 7 s= 1=
1
Σ
-1+-
T
70
8
T-th
T
T
log
70
70
4
T
(1+
DGD 11----T-2 -2
T
T
log
70
G
(1+3G2D/22)1 IT
T
G2D/2
log + D/2
2
(14)
G
1+
G
We can derive the same bound similarly in the case of It, <0.
From inequality
11
equality
12
inequality
13 and inequality
14
we complete the proof:
G2 1+
G/2
2
Rr 2 log
T
+
1og(1+>G9 G
E
G
1+7G2D/2
D/2 G2
GD
T T+1)
2
GDD ---1
(1
G
(1G2
1
G²
2
GD
T
log
1+
-T)
T
2
2(1 + GDD22)2
5
7G
2
DG2
=T)
G²
2
G
T log 1+
T
2(1 + G2D2222 2222
G
R(T)).
The second inequality follows from the inequality log (1 + D S G2DDD/2 by Taylor's theorem.
(rG
for any 7 > 0
D/27
21

---

Published in Transactions on Machine Learning Research (10/2024)
B.5 Proof of Theorem 5.2
This subsection proves that. Theorem 5.2 holds for any a E X. Before stating the proof of Theorem 5.2 introduce two following lemmas. Here, ct2 oú, li x² sy, and o/" are introduced in Algorithm 6 Lemma B.2. [Wann et al. 2020) For every grid point n, we have
Σ (c((a)) cx(2))) s log 4'
(15)
Σ (x)) - (z( - 2 log (v3 (/(2110)) logg T + +3) +3))
(16)
and
T
Σ (s) - -x( S 2 log V3 (/(22188,))) logg T + +33)
(17)
Remark B.3. According to Wang et al.
2020),
Σ (c((z)) cxx))) <
log
However, the above inequality needs to be corrected. In the last part of the proof of this lemma in their paper, they derived
holds instead inequality 15
5 t=1
(x + log Σ (x + log
From the definition of a and ry = 11((2DDVT) TT), have
T - = -
Σ c.(2))
Σ 4T 4'
though they treated this term as Combining these relationships, we get inequality 15 This mistake seems be mere typo since the regret bound in their paper coincides with the result derived from the inequality (15).
Lemma B.4. WWan el al. 2020 For every grid point n and any æ E X, we have
(c(xf)) - (x)) S 3 4'
(18)
Σ (((2)1))-()) (x)) < 10d log T,
(19)
1=1
and
Σ -((()) < log T.
(20)
t=1
Proof of Theorem
5.2 We can get O(GDVT) bound as follows:
1
R
S R
2 co(x))
T7C
T
1
(x(( - cx(xx)) + Σ (a(a))-ee(a) cx(x))
=
178
t=1
< 2(1 log 3)DDVT,
22

---

Published in Transactions on Machine Learning Research (10/2024)
where the last inequality follows from inequalities 15 and
18
We can get O( W (W T)
bound as follows:
1
R4 S R
(1))) -0112 - =
"1
G2
Σ
(s((
( st(xi)) + Σ (s)(w))) sc(x)))
"
A - n/ + -
where A = 2 2log( (V3((((3))))))))) T' 33) + log T' 2 1 and the last inequality follows from inequalities 17p
and 20 Let f) A/W 2 1/(5GDvT) II f 1/(5GD), there exists grid point up E [f/2,, and we
get
R3 S n W + A
2A $ wWT
V
A
Otherwise, since W - 2 A2A, by taking 171 = 1/(GDD) we get
A
R W
< 10GDA.
Therefore, 1t9 = WWW T) holds.
We get VVVVV T) bound as follows:
R S pz
(VV fx)t), xt -x))² -2)²-(((z))
T
f())) xx)))) 1
Σ [ - (((2()) +
T
T
-(((()))-((11)))
(l(())) - f((x))
= 1)
17
1=1
t=1
B r7*
$ n
where == log (3((122)ll))) log, T 3)) 10d T and the last inequality follows from incqualities 19 By similar arguments, .eş ( VV T) holds.
16 and
B.6 Proof of Lemma 5.4
In this subsection, we prove Lemma 5.4 used in the proof of Theorem 5.3
Proof. Since x S 3(a + b)/2 holds when x < it sufficient to consider the case x >> If S var + b.
then we have
x² - (a + 2b)x + S.
By solving this, we have
S a 26 va 4ab
3
Sa+b+ Vab (a + b). 2
The second inequality holds from the incquality V + y S VI + V/ for x.y 2 0, and the last inequality holds from the inequality of arithmetic and geometric means.
23

---

Published in Transactions on Machine Learning Research (10/2024)
B.7 Proof of Corollary 5.5 for USC
This subsection presents the proof of Corollary 5.5 for USC.
Proof. The regret satisfies
T RT Σ (1.) s((t))
Σ
f(a)))
min TEA
ft(a)
RTT RT
Rexport
where Repeta
Dizii(aa) Ei=1 Se(ar)) and RT Neppent El=1 f((w() min Sc(x)). From Theorem
A.1
Rinta RT
Vf((z))) xi)
r
T (V - -xx))²
< 4TGD +
4G2D2
Vlog E
T
1
2DGD
2+
f((:))) x - xz))?.
Vlog [
log E
Last inequality holds from the inequality v + S V + V for x, 2,y 20
Similar to equation 2 if lepeta > O, inequality
T
2 T
( - x;))?
Vf((zz)) 21 - x24) + D2
holds. By combining these inequalities, we have
r
2 T
ff(x)), - xt) 2IGD
2
(fi((z) x1 - x;) + G2
v log [g]
log E
2 + Vhn
2
T
TGG
4+
+
V fi(()), - x!)
v /log| [8]
7 log
E
From Lemma. 5.4 with 2T 2 log El) and b b= IGD(44 (2 v / v Tog El), have
Rimeta
(V xx. 2ii)
3
2 + Vkn IGD 4+
2 y log |
Vlog [3|
Since | = O(log T') in USC, we obtain the following loose upper bound:
Rmeeaa o of log + GDV kol
On the other hand, by thinking of the case that ith expert is MetaGrad Maler, from Corollary 5.5 for MetaGrad and Maler,
nexport = 0 =0 log T GD /kdlkgg)))
24

---

Published in Transactions on Machine Learning Research (10/2024)
Combining these bounds, get
Rí 0 (0(0 log logT + GDV kd
B.8 Proof of Theorem 5.6
This subsection presents the proof of Theorem 5.6
Proof. From the definition of strong convexity, we have
R Σ (f((z)))((a) - ft(a))
d
(V.c( xz - -x)
x, x
2
T
d
WT +
20 x01
20
2
1=1
1 X1
S M
WT +
Σ
D²
2G
2
t:A <A
< P
WT
D2
2
If RT 0, 0 is the upper bound, it is sufficient think of the case R 2 0. In this case, we have
2G W < X
Ro Gx
From the assumption of Theorem 5.6
there exists a positive constant C such that
i
<
50
2G2
Rep KaG2D2) (T) r2(T))
2G
Crri(T)) + CCGDvkaril + Cr2(TT).
Last inequality holds from the inequality + S vI + Vu for x,y 2 0. Here, we use Lemma 5.4 with (2G and b CGDDGGGVII + Cr2(T),
Pe < 3 20
(Tn(T) CGDV/xuii (T))))())T)T Cra(T))
From this incquality and R$ Rop Theorem 5.6 follows.
B.9 Proof of Corollary 5.7 for MetaGrad and Maler
This subsection presents the proof of Corollary 5.7 for MetaGrad and Maler.
Proof. As for MetaGrad and Maler, from Theorem 5.1 and Theorem 2
Poş O(v W W GDdlog T)
25

---

Published in Transactions on Machine Learning Research (10/2024)
holds for any Ø X, where d is d and in the case of MetaGrad and Maler, respectively. Therefore, by
Theorem 5.6
we have
Rr = (
+GD) dlog + GDV ExdlogT)
Here, ly satisfies
T
11 =
max
d 1
0 = Σ
1-
S k.
t: A
Hence, we have
R7 -0 ((7+G1) +GD) àlog T + GDV kdlog
and especially,
Ry =0 =0( GD d doggT + GDV kdlogT
B.10 Proof of Corollary 5.7 for USC
This subsection presents the proof of Corollary 5.7 for USC.
Proof. The same as the proof of Corollary 5.5 we have
RT Rueta
R
Rexpert
From Theorem
A.1
we have
T
RT
(((t)) xz - xi))
1
T2
2rGD
2
+
Vf((z)) x2 xx)²
Vlog El
log 3
2DGD
2 +
1
+
g2
Σ
| x:/1??
v /lgg El
log [
t=1
From the definition of strong convexity, we have
T
Ry
nmeta_
- -f(z)))
T
(Vf((2))) xx - xii)
X
2 1x - xil13
+ +
T x
max
{
1
-
de
a -0 ||2, - x 1
2
1=1
>
fi x, -z1)
Σ
| x 1|2 +
k2D
2
If Rapeta 0, 0 is the upper bound, so is sufficient to think of the case Rmpeta > 0. In this case, we have
T
T
Σ | 2:|12 <
(f)(())) x, - x:)) + h22
26

---

Published in Transactions on Machine Learning Research (10/2024)
By combining these inqqualtiees we have
G2
2
Vi(())) at m²) STGG
2
+
(at())), as -at) k
Vlog [
log El
X
2 + v kx
Gr
TGD
4
(e((e))) at mi)
Vlog |
Alog [3]
From Lemma 5.4 with a = 2T (0T2G2/AA) (Aloo [E] and DGD(++ + (2+ / Vlgg [E), we have
T
4+ 2 vk
A Alog [3] )
2r
Rimeta
fett)))), z1) - 2
TGD
Vlog {
Since |E] Olog T) in USC, obtain the following loose upper bound:
RT = (0((+GG)) log T + GD log
On the other hand, by thinking of the case that ith expert is Maler, from Corollary 5.7 for Maler, we have
Rexpert = =0(( + GD) log T GD llggllog
Combining these bounds, we get
RT (T=(((++))
+ GD log + GD log
B.11 The Lemma in the Proof of Theorem 6.2
In this subsection, introduce the following lemma used in the proof of Theorem 6.2 We then have
Lemma B.5. HHazn 2016 Let A
B O be positive definite matrices.
tr A -A
(TABB) B)) < log
B
C Numerical Experiments
In this section, explain experimental results. We compare the performances of OCO algorithms; OGD with stepsizes N) D/(GVE), ONS, MetaGrad, Algorithm [ with S = (Con-ONS) and Algorithm [ with S2 = 0 (Con-OGD). We include OGD, ONS, and MetaGrad because OGD and ONS are famous OCO algorithms, and MetaGrad is one of the universal algorithms. All the experiments are implemented in Python 3.9.2 on a MacBook Air whose processor is 1.8 GHz dual-core Intel Core and memory is 8GB.
C.1 Experiment 1: Contaminated Exp-Concave
In this experiment, we set d = 1, X = =00, and the objective function is as follows:
100z
tE T
f((x)
log(æ 0.01) otherwise,
where C [T] is chosen uniformly at random under the condition that [|| k. (f,.2,...., fr) is k- contaminated 1-exp-concave and the minimum value of Σr fa is T 2 (T-k) -k)loo(((? ()/(100k) if
27

---

Published in Transactions on Machine Learning Research (10/2024)
Table 2: Parameter setting in Experiment
T
a
0.02
1000
250
100
1000
OGD
MetaGradd Con-ONS
DGB
MetaGrad Con-ONS
800
ONS
0.15
ONS
600
x 0.10
0.05
0.00
Figure 1: The comparison of the time variation of regret (left) and xı (right) in Experiment 1.
2k T. We repeat this numerical experiment in 100 different random seeds and calculate their mean and standard deviation. Other parameters are shown in Table 2
We compare the performances of 4 OCO algorithms: OGD, ONS, MetaGrad, and Con-ONS, The parameters of ONS set 0.005 and 1 D2) 40000.
The time variation of regret and Iz is shown in Figure [ In the graphs presented in this paper, the error bars represent the magnitude of the standard deviation. Standard deviations in the graphs are large because contamination causes fluctuation in the sequence of solutions. Only points where is a multiple of 25 are plotted to view the graph casily. The left graph shows that the regrets of methods are sublinear. MetaGrad and ONS perform particularly well, followed by Con-ONS. From the right graph, we can confirm that 2, of all methods converge to the optimal solution quickly. OGD seems influenced by contamination little stronger than other methods.
C.2 Experiment 2: Contaminated Strongly Convex
In this experiment, d= 1, x= [0, and the objective function is follows:
x
te I,
f((x)
(r 1)2 otherwise,
where I C [T] is chosen uniformly at random under the condition that |/| k. (f1.2....., fr) is k- contaminated 1-strongly convex and the minimum value of Σ is (2K- 31²)/(2T 2k) if 2h T. We repeat this numerical experiment in 100 different random seeds and calculate their mean and standard deviation. Other parameters are shown in Table 3
We compare the performances of 3 OCO algorithms: OGD, MetaGrad, and Con-OGD.
The time variation of regret and v, is shown Figure Only points where is a multiple of 25 are plotted to view the graph easily. The left graph shows that the regrets of all methods are sublinear. The performance of
Table 3: Parameter setting in Experiment 2.
T
D
G
X
0
2/3
1000
250
1
1
28

---

Published in Transactions on Machine Learning Research (10/2024)
OGD
MetaGrad Con-OGD
0.5
OGD
0.2
MetaGrad
Con Con-OGD
400
600
800
1000
200
400
600
000
1000
Figure 2: The comparison of the time variation of regret (left) and #y (right) Experiment
Table 4: Parameter setting in Experiment
a1
12
k
10
1000
250
v5
Con-OGD is the best, followed by MetaGrad and OGD, showing correspondence with the theoretical results. From the right graph, we can confirm that 2; of all methods converge to the optimal solution quickly.
C.3 Experiment 3: Mini-Batch Least Mean Square Regressions
Experimental settings are follows. We use the squared loss as the objective function:
f((x) :- 1 Σ ((ar, x) - by,i)? b2,,))
which is exemplified in Example 3.7 In this experiment, each component of the vector az is taken from uniform distribution on [1,2] independently. We set X' = [0, 1] and assume there exists an optimal solution xx which taken from a uniform distribution on X, i.c., we take b,, = (a,,,, x*). We set & firstly and compute thresholds a and À based on k, though this is impossible real applications. Parameters G, X, a are calculated for each ar and be,i, e.g., G = 429, À 0.0969, and a 5.28 10-7 for some sequence. The parameters of ONS are as described in Section A.2 Other parameters are shown in Table 4
The time variation of regret and ||x,|| is shown in Figure 3
The performances of OGD, Con-OGD, and Con-ONS are almost the same in this experiment. The left graph shows that OGD's, MetaGrad's, and our proposed method's regrets are sublinear and consistent with the theoretical results. Though this is out of the graph, ONS's regret is almost linear even if we take T = 10000. From the right graph, we can confirm that ||x;|| OGD, MetaGrad, and proposed methods converge to some point quickly, and that of ONS does not change so much. The poor performance ONS because y too small to take large enough stepsizes. This result. shows the vulnerability of ONS.
1400
OGD ONS MetaGrad
Con-O3i0
OGD
Con-OGD
Con-ONS
ONS
Con-ONS
MetaGrad
800
600
400
230
400
600
800
1000
200
400
600
800
1000
Figure The comparison of the time variation of regret (left) and ||>||| (right).
29


Reviews:
[{"review_id": "ZggSciNQuv", "reviewer": "Reviewer_vD1L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nFirst of all, the paper introduces a seemingly interesting problem that could have good relevance in real-world scenarios. The implications of such a problem are also non-trivial, i.e., they show the lower bound, indicating an extra complexity by having contaminated functions. Also, they show the existing popular adaptive algorithms haven’t yet ready to achieve tight result. However, they go on to demonstrate that, with additional information, it is indeed possible to design an algorithm that meets the lower bound.\n\nThe paper is mostly well-written, with clear explanations and a logical flow, making it a pleasant read. Additionally, the work is quite comprehensive, offering a thorough analysis of several adaptive algorithms in this type of contaminated setting.\n\n# Weakness\n\nWhile the paper presents interesting results, there are several parts that could benefit from further clarification and improvement.\n\n- Clarification on OGD in this setting: I might have overlooked, but I think it could be better to also give at least a few words about OGD in this setting.\n\n- Corollary 5.4: In the proof of Corollary 5.4, the term $GDd\\log T$ is discarded quite early. However, it seems necessary to address how $k$ compares with $\\sqrt{d\\log T}$, is it?\n\n- Examples 3.7 and 3.8: The notation, functions, and the flow of the examples can be improved. For instance, the introduction of minibatch data and parameters feels a bit abrupt and unexplained. A smoother transition with clearer definitions and context for the parameters (e.g., minibatch size n) would make these examples more accessible.\n\n- Lemma 6.1 and Theorem 6.2: The statements for these two results seem somewhat incomplete compared to other statements in the paper. In previous results, you provide a more detailed description of the function sequence. However, it is unclear how one would describe the specific scenario outlined in Section 6.\n\n- Theorem 6.2 proof: The first inequality in the proof seems to move rather quickly. I could be missing something but not all functions involved are strongly convex, and it’s unclear how the definition of strong convexity is applied.\n\n- Regret bound of ONS in A.2: Is the regret bound of ONS in A.2 $O((d/\\alpha) \\log T)$ or $O((d/\\gamma) \\log T)$?\n\n\n## Regarding example 3.7, 3.8, Remark 3.9 and Appendix C.3\n\nI decided to extract this part separately since I wasn't sure where it fit.\n\nThe implication of Remark 3.9 quite interesting, as it suggest a tradeoff regarding how small we can take parameters $\\alpha$ or $\\lambda$, and how many contaminated samples we can afford.\n\nHowever, I wonder if you need to explicitly define $\\lambda$ and $\\alpha$ earlier before the algorithm starts, or if you can adapt in some way through learning. With the examples also illustrated in Appendix C.3, I’m still unclear about how these values were chosen or derived.\n\nAs for C.3, I also found some aspects of the results difficult to interpret. First, the overlap of the curves makes them hard to differentiate, especially in regions where they seem to almost coincide. Additionally, it looks like you used a relatively small T in the plot experiments - do you have any specific reason for focusing on such a small time horizon? Would a larger T provide more clarity in the results? You did seem to have a try on that though. Lastly, I noticed that Con-OGD seems to center quite closely with ONS. Do you have any insights or comments on why they appear this way?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the online convex optimization problem, where loss functions may vary between being strongly convex, exp-concave, or simply convex at different time steps. This setting, termed contaminated online convex optimization, introduces greater complexity. The authors establish lower bounds for this problem and demonstrate that the popular Online Newton Step (ONS) algorithm is vulnerable in such a setting. They also show that current adaptive algorithms, based on the analysis in the paper, do not yet reach these bounds. However, they show that with additional information, they can derive an algorithm that achieves the lower bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Main\n\nPlease refer to the comments in the weakness part as well as the comments for example 3.7, 3.8, Remark 3.9 and Appendix C.3.\n\n# Minor\n\n- As you also provide proof of exp-concavity of functions in Example 3.8, it is worth anyways mentioning that in the body.\n\n- There is already the dimension d in Table 1 but it was only mentioned later.\n\n- In the proof of Theorem 5.3, you discussed two cases where R_T^x<0 and R_T^x \\ge 0. In this case, \\tilde R_T^x can still be 0. You might want to change either the inequality for x, y\\ge 0 or change the two cases so that the equality goes with R_T^x<0.\n\n- In the proof of Theorem 5.3, there is a line saying “from Lemma B.2 given in Appendix B.5 with a=…, b=…,” as the statement is not very long, I would personally prefer writing the statements out to make the body a bit more complete.\n\n- Should also include \\lambda in input for Alg 1.", "broader_impact_concerns": "It's fundamental work in online convex optimization, and I don't see direct ethical implications for the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "enwn5PB5WL", "reviewer": "Reviewer_H5j2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths of the paper:\n- The topic of the paper is a very natural question to ask in the context of online convex optimisation.\n- The paper contains a wealth of interesting theoretical results characterising algorithms for the setting introduced.\n- The paper is well structured, and many natural side considerations have been addressed by way of complementary remarks throughout.\n- Results appear to be correct.\n\nWeaknesses:\n- While the analysis is more detailed, the only algorithmic contribution is Algorithm 1 - constituting a slight generalisation of ONS/OCO for strongly convex losses. \n- The algorithm provided requires the function class of the previous objective to be revealed to the algorithm in contrast to the three other comparison algorithms, all of which only require gradient information. This leaves a gap in practicality of Algorithm 1 with respect to the others. The authors have been clear about this discrepancy.\n- As a very mild addition to this list - there does remain an $O(\\sqrt{\\log(T)})$ sub-optimality between the upper and lower bounds, an explanation of which would be extremely interesting. Considering that it turns up in the corruption term in all cases where only gradients (but not the class) of the current iterate is available, an explanation of this would significantly add to our understanding of the interplay between corruption and information passed to the learner. Having said that, this is fine to be left for future work considering the contributions present. Arguably, this paper's having discovered this gap in the first place is a strength.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper deals with contaminated OCO; an intermediate regime between general OCO, where no additional structural assumptions are made on the sequence of convex functions $f_{1},\\dots,f_{T}$ and $\\mathcal{F}$-OCO, whereby all such functions are assumed to be in a function class $\\mathcal{F}$, where curvature may be leveraged to achieve fast $O(\\log(T))$ rates. The contamination $k$ is defined as the number of rounds whereby general OCO is the correct abstraction, and no other additional structure can be usefully exploited. \n\nThe paper provides a general algorithm to deal with arbitrary mixtures of exp-concave, strongly convex and losses from the latter contaminated class. A simple example of this being mini-batch least-square regression, with a corruption defined as the rounds for which the outer product of the sum of features has eigenvalue below the threshold used to tune the algorithm. \n\nThe authors begin by providing a lower bound for any online convex optimisation algorithm demonstrating that the worst-case regret for any OCO algorithm can be decoupled into two terms $g_{1}(T)$-describing the regret for structured losses and $g_{2}(T)$ for corrupted ones, which are additive in the lower bound (i.e. $R_{T}\\geq g_{1}(T)+g_{2}(k)$). With some extra work, the inadequacy of Online Newton Step for sufficiently corrupted sequences is proven in a $\\Omega(T)$ lower bound. It is then demonstrated that some existing \"universal\" algorithms (those which adapt to a _fixed_ function class, without prior knowledge in advance) for OCO (MetaGrad, Maler and USC) are also adaptive in the corrupted case, albeit with an $O(\\sqrt{\\log(T)})$ sub-optimality with respect to Algorithm 1, which leverages additional side information on the function class of the previous objective function to be revealed. Experiments are included to verify theoretical conclusions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have no requested adjustments to this paper. Broadly speaking, results are clear and the paper is well structured; I do not think too much should be added that wouldn't constitute another study altogether.", "broader_impact_concerns": "There are no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ULnfiY8Mlw", "reviewer": "Reviewer_5RWn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths \n\nThe paper studies an interesting generalization of the standard OCO setting and provides reasonable examples where such a setting would\nnaturally be encountered. The paper is easy to read throughout and the proofs easy to follow. The paper provides lower bounds for the new setting, as well as algorithms achieving nearly-matching regret upper bounds and matching upper bounds (provided additional information).\n\n## Weaknesses\n \n- The lower bound is not necessarily tight\n  - The result in section 6 is (seemingly) meant to provide a result that matches the $\\Omega(\\log(T)+\\sqrt{k})$ lower bound derived earlier, indicating that the lower bound is tight. However, the setting with extra information is a strictly easier problem setting, so this result does not actually prove that the lower bound is tight: it could still be the case that the $O(\\log(T)+\\sqrt{k\\log(T)})$ upper bound is tight and the lower bound is loose and should have $\\sqrt{k\\log(T)}$ rather than just $\\sqrt{k}$. \n\n- It is rather annoying that Theorem 5.2 is derived for $x^\\*$, and the reader just has to believe that it holds for arbitrary comparators $x$. I believe this is true, but it feels too hand-wavy for the paper to rely on a result that hasn't been formally proven anywhere. Perhaps Theorem 5.2 could be proven for completeness in an appendix.\n\n\n- Experiments:\n  - all the error bars for ONS and the proposed algorithms seem to overlap --- this suggests there is no statistically significant difference between the performance of the proposed algorithm and naively applying ONS.\n\n- Questions:\n  - The setting described here still has losses with the same property on all rounds except for the contaminated ones. Might it more generally be possible to let the loss type vary on each round --- being either strongly-convex, exp-concave, general convex, etc --- by developing a strongly-adaptive universal algorithm? Then for any partition of $[1,T]$, where the losses are of the same type on each interval, we would be able to make the correct guarantee on that sub-interval. This would be a strictly more general setting and more general result. Do you expect such a result to be achievable?\n  - Theorem 6.2: why restrict to comparing against the argmin $x^\\*$? If the results holds for an arbitrary comparator you should state it that way, otherwise the next paper will again have to state \"their analysis applies not just for $x^\\*$\", as had to be done in this paper when discussing the algorithm of Wang et al. (2020).\n\n- Suggestions (not requests) which I think could improve the clarity of this work\n  - Overall structure:\n    - It feels like sections 7 and 4 should be joined into a single section. That is, provide the lower bound of Theorem 4.2 and\n      its two corollaries from section 7, giving the lower bounds for this new problem setting. This is the more important result as it shows\n      what the optimal result is that any algorithm should be shooting for in this contaminated OCO setting. Then, the\n      vulnerability of ONS can be shown as a special case, as a subsection, demonstrating why the naive approach is insufficient. I think this would be a cleaner layout overall.\n  - Section 5:\n    - I think the core argument is easier to see by just considering the two cases, rather than writing the\n      $\\frac{\\gamma}{2}\\max\\{1-\\gamma_t/\\gamma,0\\}$, which is a bit puzzling to understand. The expression with the max is obviously more concise, but takes more effort for the reader to understand. Given that this proof is given in the main text, it would be ideal for it to be as simple as possible.\n\n      In particular, we always have\n      \\begin{align*}\n          \\sum_t \\ell_t(w_t)-\\ell_t(u)\n          &\\le\n              \\tilde R_T(u) - \\sum_t \\frac{\\alpha_t}{2}\\langle g_t, w_t-u\\rangle^2\\\\\\\\\n          &=\n              \\tilde R_T(u) - \\sum_{t:\\alpha_t\\ge \\gamma}\\frac{\\alpha_t}{2}\\langle g_t, w_t-u\\rangle ^2-\\sum_{t:\\alpha_t<\\gamma}\\frac{\\alpha_t}{2}\\langle g_t, w_t-u\\rangle^2\\\\\\\\\n          &\\le\n              \\tilde R_T(u) - \\frac{\\gamma}{2}V_T-\\sum_{t:\\alpha_t<\\gamma}\\frac{\\alpha_t}{2}\\langle g_t, w_t-u\\rangle^2.\n      \\end{align*}\n      On the $k_\\gamma$ rounds where $\\alpha_t<\\gamma$,\n      we can still expose a $-\\frac{\\gamma}{2}\\langle g_t,w_t-u\\rangle^2$ term by adding and subtracting:\n      \\begin{align*}\n      -\\frac{\\alpha_t}{2}\\langle g_t,w_t-u\\rangle^2= -\\frac{\\gamma}{2}\\langle g_t,w_t-u\\rangle ^2 + \\frac{1}{2}\\left(\\gamma-\\alpha_t\\right)\\langle g_t,w_t-u\\rangle^2\\le -\\frac{\\gamma}{2}\\langle g_t,w_t-u\\rangle^2 + \\frac{\\gamma}{2}G^2D^2,\n      \\end{align*}\n      so overall we have\n      \\begin{align*}\n      \\sum_t \\ell_t(w_t)-\\ell_t(u) \\le \\tilde R_T(u) - \\frac{\\gamma}{2}V_T + \\frac{\\gamma}{2}k_\\gamma G^2D^2.\n      \\end{align*}\n\n\n- Minor details:\n  - p. 11: \"low of cosines\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In the standard OCO setting, it is generally assumed that the losses have the same base properties on all rounds (the losses are all strongly convex, exp-concave, smooth, Lipschitz, etc). This paper investigates the setting where k of the T losses are \"contaminated\" and do not share the same properties as the rest. In this setting, the paper provides a regret lower bound\nof $\\Omega(\\log(T) + \\sqrt{k})$ and algorithms achieving a nearly matching upper bound of $O(\\log(T) + \\sqrt{k\\log(T)})$, for both contaminated strongly convex losses and for contaminated exp-concave losses.\nIt is also shown that a regret bound of $O(\\log(T)+\\sqrt{k})$ can be attained when given the additional information of which type of loss was encountered in each round.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My only request for changes is to discuss the issue with the lower bound, discussed in the weaknesses section above. \n\nSee strengths/weaknesses for suggestions that I think would improve the clarity of the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers were happy with the paper already in its originally submitted form, requiring only small clarifications and adjustments. The authors have addressed these remarks satisfyingly in the updated version of the paper. Eventually, all reviewers recommended acceptance of the paper without changes. I concur with their assessment: this is a great paper that definitely deserves to be published at TMLR.
Decision: Accept (poster)