Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness
Authors: Sarah Sachs
Hedi Hadiji
Tim van Erven
Cristóbal A Guzmán
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Convex Optimization

Abstract: Stochastic and adversarial data are two widely studied settings in online learning. But many optimization
tasks are neither i.i.d. nor fully adversarial, which makes it of  fundamental interest to get a better theoretical
 understanding of the world between these extremes.
 In this work we establish novel regret bounds for online convex
 optimization in a setting that interpolates between stochastic
 i.i.d. and fully adversarial losses. By exploiting smoothness of
 the expected losses, these bounds replace a dependence on the maximum
 gradient length by the variance of the gradients, which was previously
 known only for linear losses. In addition, they weaken the i.i.d.
 assumption by allowing, for example, adversarially poisoned rounds,
 which were previously considered in the expert and bandit setting. Our results extend this to the online convex 
optimization framework.  In the fully i.i.d. case, our bounds match the rates one would expect
 from results in stochastic acceleration, and in the fully adversarial
 case they gracefully deteriorate to match the minimax regret.  
We further provide lower bounds showing that our regret upper bounds are
tight for all intermediate regimes in terms of the stochastic variance and the
adversarial variation of the loss gradients.

Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness
Sarah Sachs University of Amsterdam
Hédi Hadiji
University of Amsterdam
Korteweg-de Vries Institute for Mathematics s c. sachseuva.nl
Korteweg-de Vries Institute for Mathematics hedi hadij juatiji@@e jimaii1....... com
Tim van Erven
University of Amsterdam
Korteweg-de Vries Institute for Mathematics tin@timvanerven.cr nl
Cristóbal Guzmán
Pontificia Universidad Católica de Chile Institute for Mathematical and Computational Eng. Facultad de Matemáticas and Escuela de Ingenieria crguzmanp@mat.ucc uc.cl
Abstract
Stochastic and adversarial data two widely studied settings in online learning. But many optimization tasks are neither i.idd nor fully adversarial, which makes it of fundamental interest to get better theoretical understanding of the world between these extremes. In this work, we establish novel regret bounds for online convex optimization in setting that interpolates between stochastic i.i.d. and fully adversarial losses. By exploiting smoothness of the expected losses, these bounds replace dependence on the maximum gradient length by the variance of the gradients, which was previously known only for linear losses. In addition, they weaken the i.i.d. assumption by allowing, for example, adversarially poisoned rounds, which were previously considered in the expert and bandit setting. Our results extend this the online convex optimization framework. the fully i.i.d. case, our bounds match the rates one would expect from results in stochastic acceleration, and the fully adversarial case, they gracefully deteriorate to match the minimax regret. We further provide lower bounds showing that our regret upper bounds are tight for all intermediate regimes in terms of the stochastic variance and the adversarial variation of the loss gradients.
1 Introduction
Two the main approaches for solving convex optimization problems under uncertain data are stochastic convex optimization (SCO) 211 30 and online convex optimization (OCO) (37] These two models are very different in their assumptions and goals, despite the fact that they share many techniques. In SCO it is assumed that the loss functions follow independent, identically distributed (i.i.d.) process, and the goal is to minimize the excess risk, which is the optimization error under the expected loss. By contrast, in OCO the losses can be chosen adversarially and the goal is minimize
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the cumulative regret, which is the difference between the cumulative incurred losses over rounds against the best fixed strategy in hindsight. Much less is known about what happens in between, in scenarios that interpolate between the i.i.d. and adversarial settings. This intermediate setting has drawn major attention in the recent years the expert and bandit setting [14]
however, as mentioned in [14], little is known for online convex optimization. Our work studies this in
2
generalization of the OCO setting, in which nature chooses distributions for the data that may vary arbitrarily over time, and we provide regret bounds in terms of two quantities that measure how adversarial these distributions are. The standard OCO setting corresponds to the case where the distributions point point-masses adversarial data points.
Main Contribution. Our main contribution is a new analysis of optimistic online algorithms that takes advantage of smoothness of the expected loss. This analysis allows for gradual interpolation between worst-case adversarial regret bounds and the best-known expected regret bounds in the stochastic case, and also provides quantifiable improvements for intermediate cases To capture the full range between i.i.d. and fully adversarial settings, we consider a similar adversarial model as in 27), i.e., nature chooses distributions D, in iteration t, and the learner suffers loss fe( with & ~ Dr. Importantly, we do not assume that the distributions Dr are all the same, but they may vary adversarially over time.
25 2
To properly quantify the interpolation between the i.i.d. and fully adversarial settings in the regret bound, we introduce two parameters for the loss sequence. Namely the cumulative variance, Tr- which captures the stochastic aspect of the learning task, i.c., the variance of the Dú; and the cumulative adversarial variation, Er, which captures the adversarial difficulties of the data, i.e., the difference between Eg~D, [V f and Eg-D._, -.. E)]. With these two key quantities, our first main result Theorem 5 shows that the expected regret [E[RT(u) (u)]. that the difference between the cumulative losses of the learner and fixed solution in hindsight, is bounded by
E [Rr(u)] = 0 (D(or + ΣT) + LD?).
where L is the smoothness constant of the expected functions F = EEWD, [f(.,K)] If, in addition. the functions fst are μ-strongly convex, then in Theorem we obtain (below, K == L/μ p is the condition number)
( = (o (o + 52 maax log LDDx log
[[Rr(u)] =
Both bounds tight: prove matching lower bounds in Theorems 6 and X In Section 3.1 we show that our results match the known adversarial regret bounds as well as the best results in the i.i.d. case. For the latter, only the linear case was far obtained directly via regret analysis (see Sec. 5.2 in 25). and prior work [12 4).. Using optimistic mirror descent, they
obtained the regret guarantee of (u) & O(v EL (V Ex) - mm.l?), where my denotes an optimistic guess of the gradient that is chosen before round t. In the i.i.d. case with the prediction my = (f this can be shown to imply that the expected regret is upper bounded by
[[Rr(u)] Oooo + v E (+))) (F((x=)))))), where denotes the variance of the stochastic gradients. This simplifies
which is special case of (.. because for the i.i.d. case with linear functions V
[[Rr(u)] = O(vVT)
ãा and Σr 0 for i..d. losses, and VF*(2,) (x,-)) and L = 0 for linear functions. is not immediately obvious how to generalize this result to general convex functions with smoothness L > 0, however. In this case, can guess the appropriate regret bound based on known convergence results for stochastic accelerated gradient if we knew in advance that the losses would be i.i.d. and we did not care about computational efficiency, then we could run a new instance of SAGD for each round I. Summing the known rate for SAGD over t then gives E (u)] & O + L) (for more details the batch-to-online conversion in Appendix D). This raises the question if similar bound can also be obtained directly via a regret analysis, without assuming i.i.d. observations in advance. This
descent (SAGD) [7 X
It is well weolw that in the fully adversarial case smoothness does not yield asymptotic improvements on regret [Л]. whereas for SCO improvements can be obtained only under low-noise

---

question is then answered by our result T. which indeed reduces to this rate for general convex smooth i.idd functions, matching the aforementioned bound up to constants. We achieve this by using smoothness to bound [ (
(xx-1))l Σ T. E J++ I2- =12), which can be canceled by a negative quadratic term that we obtain from an improved analysis of the regret. The use of this
negative term in the analysis dates back to 20] who used it to achieve an improved ((1/T) rate on
the extra-gradient method.
In addition to unifying the analysis of these two extreme cases and obtaining the best-known results via one algorithm (OFTRL 2 for convex functions and OFTRL on a surrogate loss ( for strongly convex functions), our results give new insight for intermediate cases. Thus, as a second main contribution we shed light on setting that is neither fully adversarial nor i..dd To illustrate this, we highlight some examples here, which received attention in the recent literature.
Adversarial corruptions: Consider i.i.d. functions with adversarial corruptions, as considered in the context of the expert and bandit settings in [4] 2 If the (cumulative) corruption level is bounded by a constant C, in [4] an expected regret bound of IE [RT(v) (u)] ] = O Ree + /CRG) was obtained, where Rł. denotes the regret with respect the uncorrupted data. In [T]. the authors raised the question of whether it is possible to obtain regret bounds with similar square-root dependence
on the corruption level C' for online convex optimization. Indeed, for this intermediate model, we derive a regret bound
TE [R)( & O DVGC),
for the general convex case from our Theorem 5 We elaborate on this in Section
Random order models The random order model (ROM) dates back to T combinatorial online learning. It has drawn attention in the online convex optimization community as an elegant relaxation of the adversarial model [31 3). Complementary to the results in [3I], we show that the dependence on G' in the regret bound can be reduced to a dependence of a. where a denotes the variance of gradients in the uniform distribution over loss functions f1. ... f1....fr fr. That is,
E [RT(w)) < (o log (o))
where ō denotes slightly weaker notion of variance (see Corollary
TC We derive these results from our main theorem under stronger assumptions than in 131, namely, we require individual convexity of the adversarial choices whereas [1] only assume cumulative convexity. However, we also obtain a better rate with a instead of G as the leading factor, so the results are not directly comparable. We also consider variant of the random order model, which we call the multiple pass random order model (multi-pass ROM). This inspired by multiple shuffle SGD and can be considered another intermediate example between adversarial and stochastic data. We elaborate on both examples, i.e., the ROM and multi-pass palti-pass ROM in Section
1.1 Related work
As mentioned in the previous section, our work is inspired by results in the gradual variation and in the stochastic approximation literature. The gradual variation literature dates back (122. with later extensions by [ and |25 (26.. In addition to some technical relation to the aforementioned work, there is also natural relation between our parameters ãт and En and variational parameters in 133 12 or 4 However, we elaborate in Remark g there are some fundamental differences between these variational parameters and ōr, Er, which prevent us from directly obtaining a smooth interpolation from these results. It is also interesting to note that there is relation between Er and the path length parameters considered in dynamic regret bounds 355 [ However, since their analysis targets fundamentally different notion of regret, namely dynamic regret, the results are incomparable.
With respect to the results, our findings are fundamentally different from the stochastic approximation literature, since we do not rely on the assumption that the data following a distribution. However, we were inspired by analysis techniques and the convergence thresholds set by this literature. Our approach of obtaining accelerated rates by negative terms arising from smoothness in a regret bound has previously been used in the context of variational inequalities and saddle-point problems. Using
3

---

this idea, 20 obtained improved rates O(1/T) for the extra strraggaddeet method. More recently [7 showed that acceleration in stochastic convex optimization can benefit from negative terms arising in optimistic FTRL. via an anytime-online-toe online-to-batch conversion [5] Although an important inspiration for our approach, the techniques of [17] do not directly earry over, because they evaluate gradients at the time-average of the algorithm's 's iterates, making them much more stable than the last iterate,
which comes up when controlling the regret. Algorithms used both in SCO and OCO follow a vast
literature stochastic approximation methods, e.g. 228 21 24 For this work, we are particularly interested the more recent literature on acceleration in SCO & 13 I7]. this research field efficiency is traditionally measured in terms of excess risk. On the one hand, regret upper bounds can be converted into excess risk bounds, through the so-called online to--tt--bbat to-batch conversions Bi: on the other hand, excess risk guarantees do not directly lead to regret bounds, and even if they do some key features of the rates might be lost. These latter methods, known as batch-to-online conversions are discussed in Appendix D
Outline In Section 2 after setting up notation and basic definitions, we introduce the stochastically extended adversarial model, generalization of the standard adversarial model similar the model used in smoothed analysis. Our main results can be found in Section 3 In Section f we illustrate our results by highlighting several special cases, such as the random order model and the adversarially corrupted stochastic model. Finally, in Section 5 we set our findings into broader context and give perspective for future work.
2 Setting
We recall the online convex optimization (OCO) problem. Here, we consider sequence of convex functions fr defined over closed and bounded convex set X C Rd which become available to the learner sequentially. then function fe is revealed and the learner suffers loss fe(xx)) The success of the learner is measured against all fixed u E X. Hence, the goal of the learner is to minimize the regret, that is, the difference between their cumulative loss Σ fe(xz) and that of the best fixed choice in hindsight, namely min ET fe.u)
the standard adversarial model, the learner chooses I, E X in round t,
Throughout the paper we use the notation [T) = (1..... denotes a Dirac measure at point and ||
7}. We follow the convention that &c denotes the Euclidean norm.
2.1 Stochastically Extended Adversarial Model
We extend the aforementioned adversarial model by letting nature choose a distribution D, from a set of distributions. Then the learner suffers loss f(x,,{t where & Dr, Note that if the set of distributions is sufficiently rich, this model contains the standard adversarial model and the stochastic model special cases (see Examples 2
We introduce some notation to make this more precise. Let X C Idd be closed convex set and a measurable space. Define x x x= - R and assume f(,,g) is convex over & E Suppose D is a set of probability distributions over E. For any D E D. we denote the gradient mean by
v F (x:) : RewD (v) and the function mean by F (x) == BEWD (s(x, {)]. Furthermore,
denote by o an upper bound on the variance of the gradients
o = max zEX
EE-D [|V - VF (x) (1)
-
We introduce some shorthand notation when distributions are indexed by rounds. Given E [T'), we write Frr and of instead of FP: (z) and o. respectively. Let us now introduce the stochastically extended adversary protocol.
Definition 1 (Stochastically Extended Adversary (SEA)). In each round I, the learner chooses I, X, the SEA picks DD D. The learner and the SEA then both observe a sample & ~ De, and the learner suffers loss (e)
note that the SEA model is closely related to the adversarial model considered in the context of smoothed analysis 2i IC B2] However, in contrast to this line of work, we do not focus on

---

distributions with sufficient anti ooteennncenta (c.f., Def. 1.1 in [TO). Indeed, this restriction would exclude, among others. the fully adversarial case as described below. Note also that we assume that the SEA is an adaptive adversary, which has access to the realizations &t, so the distribution D++1 may depend on Et. This assumption is not relevant for the fully adversarial or the i..dd settings. In the former, because there is no randomness, and in the latter, because there is no change distribution. However, it is important for some the intermediate cases, and in particular for the random order model. The SEA model contains several common settings from the literature as special cases. To illustrate this, we list some examples.
1. Adversarial Model:
The SEA chooses Dirac measure 6c, E D in each round. Then for any & ~ 6e., the SEA selects f(', and the model reduces to an adversary selecting directly the functions fe(.)
2. Stochastic LLD. Model: The SEA chooses fixed D E D and selects D, = D at each round f.
3. Adversarially Corrupted LLD. Model: The adversary selects an i.i.d. source D and perturbs the data with adversarial corruptions. This fits in our framework as follows: given a corruption level C > O, the SEA chooses distributions D, = D @ 6a. such that
Σ" suPaex |I LE V f(z, {)] - EerDD, V ((xxx')))] C.
4. Random Order Model (ROM): Among a fixed family of losses F= (fr. i E [n]). the SEA randomly picks functions in F via sampling without replacement, possibly performing multiple passes over the losses and reshuffling between the passes. Formally, define E = [n]. and [x) = f& for & E E. If f E [nki, nik + 1)] is in epoch A N. then the SEA chooses the distribution D, = Unif(E \ {Es 8 E [nk + n( - 1)]}), which is uniform on the functions that have not yet been sampled in epoch k.
To quantify the hardness of the loss sequence, we introduce the cumulative stochastic variance and adversarial variation; we also define an average of these quantities.
We denote by E the expectation taken with respect to the joint distribution of ( -.,... TT, Er). Note that the choice of the adversary Dr can be random itself, it depends on the past observations (of both the player's s actions and the realizations of the & Ss. In this case, o₁ is also a random quantity.
Definition (Cumulative Stochastic Variance and Cumulative Adversarial Variation). Suppose the SEA chooses distributions DI...., Dr. Recall that of is shorthand for o.. The cumulative stochastic variance and the cumulative adversarial variance are defined as
T E
T
(2) = 11:71
Σ t=1
10
and
(2) [1:T =E
Σ 1=1
sup ZE
We also let oT and Ex denote the square root of the average stochastic variance or adversarial variation, respectively; that is, o.. = = / and E2 = (2) /
Note that in the special case when all fr are fully adversarial, ãT 0. On the contrary. in the stochastic case, i.e., if all for each round the distribution D, equal to a fixed (but arbitrarily chosen) D, then Σy = O. In this case, σÿ reduces to the common definition of the gradient variance upper bound in the SCO literature 7 [ If however, the SEA chooses one distribution D; for the first rounds and then switches to a different distribution D,, then ōт can only be upper bounded by max(o,, ,,). This upper bound can be pessimistic, however, for some results it gives better intuition. For this purpose we also define the maximal stochastic variance and maximal adversarial variation.
Definition 3 (Maximal Stochastic Variance and Maximal Adversarial Variation). Let o be an upper bound on all variances oz. That is,
0 max
max E [[o?] and x [E[T]
Inax = max E EE
sup LEEX
Remark 4. As mentioned in the introduction, the cumulative stochastic variance and the adver- sarial variation have some similarities with parameters in gradual variation regret bounds. For linear functions (pes >), the bounds in (12] involve the parameter Varr = -Er 1|fte Frll where Pr is
5

---

the average of the gradients. For OCO with general convex functions, M provide upper bounds on
the regret terms the L.-deviation D = Ei= supsex - (x) In Lemmas T3
and 14 Appendix we show that in the SEA framework, both of these types of bounds are generally worse than ours, and that the difference can be arbitrarily large.
In 226) the regret is bounded in terms of Ei=t l1ge M, 1la As mentioned in the introduction, unless
the loss functions are linear or the learner has knowledge of the gradient mean, Ei=1 11 M,
cannot directly be reduced of (2)
(1:T) or (2
[1:7]]
2.2 Assumptions
In our analysis, we will frequently use several of the following additional assumptions. Some of these already mentioned in the introduction. We keep them all together here, for the convenience of the reader and for clear reference. For any "D E D:
(A0) the adversary has access independent samples & D.
(A1) the function f(.:E) is convex, and gradients are bounded by G a.s. when & ~~ D.
(A2) the expected function FD I-smooth, i.e, V is L--Lipschitz continuous.
(A3) for any X, the variance Eg-D fz.,) - VF [x) is finite.
(A4) the expected function FD (.()) is p-strongly convex.
We assume that (A0) always holds. Assumptions (A1) (A2) and A3)
standard in stochastic
optimization, and are similar to common assumptions for online convex optimization. There, it is typically assumed that the adversarial samples fx(-) ) are convex (or even linear) and the gradient norms | [-(l)) are bounded. Note that we only require gradient Lipschitz continuity and strong convexity to hold for the expected loss.
3
Algorithms and Regret Bounds
3.1 Convex Smooth Functions
We Optimistic Follow-the- Follow-the-Regulariss Regularised-Leade (OFTRL) (see, e.g.. [16 25
minimize regret. Let (M be a non-decreasing and positive sequence of stepsizes, possibly tuned adaptively with the observations. At each step the learner makes an optimistic prediction M, E Rdd and updates its iterates as
{(x,, [r,,,
L-1 Σ
|
Tt. = argmin ZEX
+
(2)
where denoted gr Vf(=,, E.) the observed gradient at time t. To state our results, denote by E [-] the expectation with respect to the joint distribution of ( Fr. is to bound the average regret:
Er). Fr. Our objective
[ = E
(g,, xz - u)
The following theorem, proved in Appendix is our main result for convex functions.
Theorem 5. Fix user-specified parameter v > 0. Under assumptions (A) (22) (A3) OFTRL,
with M, = 9t-1 and adaptive step-size 1). = D2 (2 + E!=1 7)s llg. - I=) has regret
3/2DG + v + "
1 (AD2 + +TT2
E (Rr)) & D(6rr + 3V VT + 2
(3)
The algorithm needs to know only D. If and L are also known, one can tune y = LD² + G2 to get
E [[] < O(D(a, + Ex)TT + DG DD')
Moreover, if only convexity of the individual losses holds (AI) then luning 2DG ensures the (deterministic) bound RT & 322DGVT 4DG

---

Without prior knowledge of the smoothness parameter, the best the player can do is to tune according to a guessed value Lo. This affects the constants in the bound by an additive term of order (To + 1,2 TT)) ; it would be interesting to determine if this is an inevitable price to pay for the lack of knowledge of L. A similar discussion can be held for G. Note that the worst-case regret bound of order DG always holds every time OFTRL used in this article, even without smoothness. To avoid distraction, we will not recall this fact in the applications.
The algorithm and analysis dwell on two ideas: the adaptive tuning of the learning rate la Ada- Hedge/AdaFTRL [19 23 with optimism, together with the fact that we keep a negative Bregman divergence term in the analysis, which crucial obtain our bound.
Lower Bound. The upper bound in Theorem is tight up to additive constants, as the following result shows.
Theorem 6. For any learning algorithm, and for any pair of positive numbers (a. Σ)
there exists
function f X x== + R. and sequence of distributions satisfying assumptions (1) A2)
(A3)
with or 2 a and Ex > E such that
[[R((u)) > ((D + ST) VT).
The proof, in Appendix B.2 relies on a lower bound from stochastic optimization || 21 together with the fact that we can construct a sequence of convex and L-smooth loss functions such that En in the order of the gradient norms G. Combining these insights with the lower bound &2 (DDVT)
23
gives the desired result.
3.2
Strongly Convex and Smooth Functions
Up to this point, we have only considered functions which satisfy the weaker set of assumptions (AT)
(A2) (A3) In this section, show what improvements be achieved if strong convexity also holds, that is, if (A4) is satisfied with some known parameter > O. For Vf(I,, Et), define the surrogate loss function
+ 11 (xxx) = (gt, x xe))
|| xell2. 2
44)
We Optimistic Follow-the-Leadde (OFTL) the surrogate losses. For each step the learner makes an optimistic prediction of the next gradient Mr E Ra and selects
lx(x) + (M),
Pt arggin aEX
(S)
The next theorem is analogous to Theorem 5 for curved losses, and will be our main tool in establishing results for strongly convex losses; see Appendix B.3 for a proof.
Theorem 7. Under assumptions (Al)
the expected regret OFTL with M, = V f on surrogate loss functions & defined in bounded as
(A4)
VF VF (1)))())
4D2
16L
((TT(u)
80
-ox + 4E
sup ZET
log
1
11
11
1 max + 432
4D21²
16L
(80
T
log
11
4
p
Note that OFTL requires no tuning besides the strong convexity parameter used in the surrogate losses. In particular, it is adaptive to the smoothness L.
Lower Bound The bound in Theorem 7 tight, as the next result, proved in Appendix B.4 shows.
Theorem 8. For any learning algorithm, and for any pair of positive numbers (a. Σ) there exists
function f X x - R and a sequence of distributions satisfying assumptions (AI) A2) (A3) and
A4) with max 2 a and Emax 2 E such that
E [[]T(u)] > (o + 2 logg)
7

---

Implications
We derive consequences of results from Section
Further examples can be found in Appendix
4.1
Interpolating Known Results: Fully Adversarial and i..d. Data
first implication of our analysis is that we recover both the adversarial and i.i.d. rates, via a single adaptive algorithm.
[1:21 & GV2T. Thus, Theorem guarantees bound (u) & O(DGVT), which is known to be the optimal rate up to the additive constants, cf. [37 (note that the expectation does not act on the regret in this case). Simultaneously. if the data is i.i.d., then Theorem 5 guarantees that
Convex Case
For adversarial data, dz = for all t, and S
E [Rr(u)] & O(DDvV DD* + DG).
From standard online-to-batee conversion, this implies an excess risk for the related SCO problem of order ( VT + D(TDD + G)/T), which matches the well-known result by 7 up to lower order terms. On the other hand, using batch-to-online conversion (see Appendix D with the best known accelerated convergence result in SCO, gives O(Do VT + LD2) regret. Therefore, up constant, our result coincides with the best-known results from SCO. Note that also generalizes the improvement obtained for linear functions in the i.i.d. setting in 25
Section 6.2].
Strongly Convex Case The adaptive interpolation between i.i.d. and adversarial rates also holds in the strongly convex case. For adversarial data, the bound of Theorem 7 is of order (G²/p) log T. which is known to be the optimal worst-case rate, cf. [3]. For i.i.d. data, the dependence on G2 improves to o². yielding bound of order (( /p) log + LD2 log This improvement is akin to improvements obtained by accelerated stochastic gradient descent in the context of stochastic optimization [& [7]. In fact, applying batch-to-online conversions and summing the optimization rates would yield a regret bound similar to ours; c.f. Appendix D
4.2 Adversarially Corrupted Stochastic Data
We consider a natural generalization to online convex optimization of the corruption model considered the bandit literature 20 36 also recently studied in [14] for prediction with expert advice. There, the author obtains a regret bound that is the sum of the i.i.d. rate and term of order V where C is the total amount of perturbation. They then raise the open question of whether similar results could be obtained for general convex losses. We provide a positive answer to this question in this section, with the regret bound in Corollary g
In this model, the generating process of the losses is decomposed as combination of losses coming from i.i.d. data, with a small additive adversarial perturbation. This fits in the framework by setting & = (Eid,e ct) ~ Dj- D x 8e, and
[xx
Sma.e) + (xx
where o is the adversarial part of the losses selected by the adversary, and Eua. ~ D is a sequence of identically distributed random variables. Note that, similarly our inspirations [4] 29], and contrary to other corruption models for prediction with expert advice (2). we measure the regret against the perturbed data. Define F E&_DD [h(- {)), that F'(x)= F(x) + ce(x). The amount
of perturbation measured by parameter C > 0 bounding
T
Σ max SEX
[V)( C
which is a natural measure of perturbation on the feedback used by the player (note that adding a constant to the perturbations does not change the regret). In this case, the adversarial perturbation the loss does not affect the variance and of = oz. The perturbation appears in the loss variation as for any t > 2. for any z X,
|VF (x) - ( < V - (x)]
= Vc - Va-1 (0([V + (x))
8

---

Upon taking the supremum over X and summing over t, we get (with the convention that = 0),
(2) [1:T]
Ver(x) Va- (x))2 4GC. Σ sup
Hence, Theorem combined with the bounds on oT and Σr yields the following regret guarantee. Corollary 9. In the adversarially corrupted stochastic model, adaptive OFTRL enjoys the bound
E O(DoVT
This regret bound is the sum of the i.i.d. rate for the unperturbed source with a term sublinear in the amount of perturbations C, achieved without prior knowledge of C. This provides answer to a question by [14]. The construction of the lower bound Theorem 6 also provides a partial
lower bound for the corruption model, proving some worst-case optimality of our upper bound, see Appendix 1
An interesting open question that remains would be extend these results strongly convex losses.
Regret against unperturbed losses Depending on modeling choices, one might consider the perturbations to be a true part of the data that deviate from an i.i.d. model, or one may see them as adversarial noise which should be discarded. In the latter case, regret against the i.i.d. part of the data most relevant. As noticed by [2] Observation 4] and [14] Remark 1]. regret against the unperturbed losses and against the perturbed losses are closely related. Indeed, Corollary implies the bound
E
F(z)) F(u)
< ([ + 2DE
(e((w)))
< O((DoVT DVGC
4.3
Random Order Models
We apply our results from Section the Random Order model. The online ROM was introduced by 6 as a way of restricting the power of the adversary in OCO. Note that the ROM is popular model combinatorial online optimization, e.g., in the context of profit maximization M. Our results highlight that the rates in the ROM model, which is not i.i.d, are almost the same as the rates of the i..d. model obtained via sampling in the same of losses with replacement.
Corollary 10. In the single-pass ROM with convex and L-smooth losses (fw)kE(T), OFTRL (c.f. enjoys the regret bound
E R((( & 0 Dov
<D(Do
log
ōi 01
T
LDD + DG)
where
of max FEX
1 T
1 Σ V((x))
Vz
and o
1 T
Σ
max ZE
Vf((z) Σ
Vf.
We remark that 0n & σ < min { Hence, the logarithm of the ratio log(ō1/ //11) is always under control. The proof of Corollary I0 consists in controlling the adversarial variation and the cumulative variance thanks to the following lemma, proved in Appendix C.I
(2) Lemma 11. In the single-pass ROM, we have - SG2 and pi:7 < Toi (ogg2220///0
We would like to emphasize that our results are complementary to those of 6 31. The focus of these works is to relax the assumption that individual losses are convex, and to only require convexity of the average loss function, leading very different technical challenges. Inquiring if our results can also be achieved under the weaker assumptions of Bl would be an interesting direction for future work.
We also consider the multi-pan pass ROM. Let P E N denote the number of passes. From Lemma and Corollary I0 we directly obtain
E [Rr(")) & <0(Do log (c
21 (=))++
DGVP LD*

---

Combining Lemma with Theorem also gives the following corollary for strongly convex functions; see Appendix for proof.
Corollary 12. Under the same assumption as Theorem bounded by
the expected regret of the ROM is
E [[r(u)) & of o (
G² LD²x
log
/
For multi-pas pass ROM with P passes, obtain
E [[Rr(u)] < 0 of log
G
G2 log P
+ LD
f
nu
5 Conclusion and future work
As showed, the exploitation of smoothness of the expected loss functions reduces the dependence of the regret bound on the maximal gradient norm to dependence on the cumulative stochastic variance and the adversarial variation. Furthermore, we took a step towards a deeper theoretical understanding of the practically relevant intermediate scenarios. Our approach also opens several interesting new research directions. For instance, in the ROM, mentioned in Section 13 an interesting question is whether a regret bound with dependence on a instead of can also be achieved with weaker assumptions as in 3I
Another interesting question is whether it is possible to unify the analyses and algorithms for the strongly convex and convex case. So far our analyses of these cases were intrinsically different and the choice of the algorithm requires the knowledge strong convexity constant μa. Since this knowledge might not be available, it is of practical interest to design adaptive method that can automatically get the best rate without manually tuning for μ.. Furthermore, it would be interesting to investigate if similar or better improvements of the regret bound can be achieved with different optimistic predictions Mr. Our matching lower bounds show that there are instances where M, = 9t-1 captures the right adversarial behavior. However, there are cases where other measures of regularity would be more relevant. One such example would be an adversary oscillating between two distributions. Interestingly, using M, 91-2 would then recover optimal bounds. An interesting future research direction would be to investigate what can be achieved when using linear combinations of past gradients optimistic predictions.
Social impact: this work is theoretical and does not give rise to any direct societal concerns.
Acknowledgments and Disclosure of Funding
Sachs, Hadiji, and Van Erven were supported by the Netherlands Organization for Scientific Research (NWO) under grant number Vidi. 192.095. Guzmán's 's research is partially supported by the INRIA Associate Teams project, FONDECYT 1210362 grant and ANID Anillo ACT210005 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID, Part of this work was done while CG was at the University of Twente.
References
[1] Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory. (8(5):3235-3249) 2012.
[2] Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 14315-14325, 2020.
[3] N. Cesa-Bianchi A. Conconi, and C. Gentile. On the generalization ability of online learning algorithms. Advances in Neural Information Processing Systems 14 (NeurIPS), volume 14, 2002.
10

---

[4] Chao- Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 6.1 6.2. PMIR, 25-27 Jun 2012.
[5] Ashok Cutkosky. Anytime online-to-batch, optimism and acceleration. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1446-1452 1454. PMLR, 09-15 Jun 2019.
[6] Dan Garber, Gal Korcia, and Kfrr Levy. Online convex optimization in the random order model. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3387-3396. PMLR, 13-18 Jul 2020.
[7] S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23:2341-2368, 2013.
[8] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22( 1449)))446-1492, 2012.
[9] Anupam Gupta, Ruta Mehta, and Marco Molinaro. Maximizing profit with convex costs in the random-order model. In ICALP, 2018.
[10] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 943-953. IEEE, 2022.
[11] Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2(324))15773255 aug 2016.
[12] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: regret bounded by variation costs. Machine Learning, 10:165-188, 2010.
[13] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. In Proceedings of the 24th Anmual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 421-436. PMLR, 09-11 1 Jun 2011.
[14] Shinji Ito. On optimal robustness to adversarial corruption in online decision problems. In Advances in Neural Information Processing Systems 34 (NeurIPS), volume 34, pages 7409-7420, 2021.
[15] Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Ac- celerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pages
PMLR, 2018.
[16] Pooria Joulani, András György, and Csaba Szepesvári. modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, and variational bounds. In International Conference on Algorithmic Learning Theory (ALT), pages 681-720. PMLR, 2017.
[17] Pooria Joulani, Anant Raj. Andras Gyorgy, and Csaba Szepesvári. simpler approach to accelerated optimization: iterative averaging meets optimism. In International Conference on Machine Learning, pages 1984-4993. PMLR, 2020.
[18] Claire Kenyon. Best-fit bin-pagking with random order. In In 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 359-364, 1997.
[19] Brendan McMahan. realuatthe-rgullaizee---- leader and mirror descent: Equivalence theorems and 11 regularization. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 525 533. PMLR, 11-13 Apr 2011.
[20] Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. on Optinization, 15(1):229-25LL jan 2005.

---

[21] A.S. Nemirovsky and D.B. Yudin. Problem complexity and method efficiency in optimization. SIAM Review, 27(2):264-265, 1985.
[22] Francesco Orabona. A modern introduction to online learning. arXiv preprint: 1912. 13213, 2021.
[23]
Francesco Orabona and Dávid Pál. Scale-free online learning. Theor, Comput. Sci., 716:50-69, 2018.
[24] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838-855, 1992.
[25] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, PMLR, 2013.
[26] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences, Advances in Neural Information Processing Systems 26 (NeurIPS), pages 3066- 3074, 2013.
[27] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: stochastic, con- strained, and smoothed adversaries. In Advances in Neural Information Processing Systems 24 (NeurIPS), pages 1764-1772, 2011.
[28] H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
[29] Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. Proceedings of the 31tt International Conference on Machine Learning. volume 32 of Proceedings of Machine Learning Research, pages 1287-1295. PMLR, 22-24 Jun 2014.
[30] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Programming: Modeling and Theory, Second Edition. Society for Industrial and Applied Mathematics, USA, 2014.
[31] Uri Sherman, Tomer Koren, and Yishay Mansour. Optimal rates for random order online optimization. In Advances in Neural Information Processing Systems 34 (NeurIPS), volume 34, 2021.
[32] Daniel A Spielman and Shang-Hup Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385 463, 2004.
[33] Tianbao Yang, Mehrdad Mahdavi, Rong Jin, and Shenghuo Zhu. Regret bounded by gradual variation for online convex optimization. Machine Learning, 95(2):183-223, oct 2013.
[34] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 22510-12520 2020.
[35] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non- stationarity: cooblem-dependee dynamic regret for online convex optimization. arXiv preprint arXiv:2112.14368, 2021.
[36] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 467 467-475. PMLR, 16-18 Apr 2019.
[37] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, pages 928-935. AAAI Press, 2003.
12


Reviews:
[{"review_id": "rX1lT5tcosH", "reviewer": "Reviewer_AbNA", "summary": "The paper gives tight results on optimization in a regime between stochastic and adversarial data, interpolating known results in these extremes. Using smoothness of the expected loss, the paper establishes convergence rates depending on stochastic variance and adversarial variation of the gradients via a unifying analysis of OFTRL. The authors discuss applications of the result in the intermediate regime, including adversarial corruption and in the random order model. \n", "questions": "- The regret in the corruption model is against the corrupted data. Could the authors comment on scenarios where this makes sense? \n- Could the authors give some examples of problems where the results for random order models can be applied?\n", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is very clearly written and discusses relevant works.\n- In terms of technical novelty, this work proposes a new analysis of optimistic FTRL that takes into account a negative term not explicitly stated in classical analysis. \n- The regret analysis is unified for the adversarial and stochastic cases, and the regret bounds are not only tight up to constants, but also match known results in the extreme cases. \n\nWeaknesses:\n- See questions.\n\nMinor Typos:\n- Page 7, $\\Sigma_{[1:T]}^2 \\le G\\sqrt{2T}$, should there be a square on the lhs?\n- Appendix Page 16, Eq. (9), should it be $\\frac{6D^2G^2}{\\nu}$?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bdY6NCF-GyX", "reviewer": "Reviewer_nGYM", "summary": "This work studies regret bounds for online convex optimization that interpolates between stochastic i.i.d. and fully adversarial losses. The author leverages the smoothness of the expected loss to reduce the dependence of the regret bound on the maximal gradient norm to the cumulative stochastic variance and the adversarial variation.", "questions": "1. For theorem 5, can you elaborate more on why you specifically choose $\\nu=LD^2+DG^2$ and $\\nu=2DG$ after deriving eq(3)?\n\n2. Why in theorem 6 and theorem 8 we need $\\bar\\sigma_T\\geq\\sigma$ and $\\bar\\Sigma_T\\geq \\Sigma$ since there’s no $\\sigma$ and $\\Sigma$ show up in the bound?\n\n3. It’d be helpful to also provide the lower bound for adversarially corrupted i.i.d. model to see whether the dependence on C is tight. Also, does it natural to bound the sum of perturbation by $C$, instead of per sample perturbation $\\max_{t\\in T}\\max_{x\\in X}\\|\\nabla c_t(x)\\|\\leq C$? Since the latter case might provide an $O(\\sqrt{T})$ bound. It’d also be helpful if we can have a lower bound for Random Order Models.\n\n4. Some typo: in the appendix proof of theorem 5, I think eq(9) the constant before $D^2G^2/\\mu$ should be 6 instead of 4. line 569-571 some of the summation is not consistent, which should be from 1 to $T-1$. It seems a missing constant in front of $G$ in the equation after line 569.\n\n\n\n##############After reading the rebuttal################\nI thank the author for the detailed response to my question. Most of my concerns have been addressed. I therefore raise my score to 6 for now.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work provides upper bound and tight lower bound up to additive constants of regret bounds for (strongly) convex smooth function.\n\n2. Such results can be extended to the intermediate case between stochastic iid to fully adversary.\n\n\nWeaknesses:\n1. The writing needs to be improved. It’s hard to find the definition of some math parameters. For example, there’s no context regarding $D, \\kappa, \\sigma_{max}, \\Sigma_{max}$ when introducing the bound in line 47-49. When comparing with the literature, it’d be helpful to list the concrete differences. For example, line 93 mentioned the main theorem under stronger assumptions than previous literature without mentioning what’s the assumption in this work versus the literature. In Remark 4 line 212, the author does not give any formal definition of $g_t$ and $M_t$.\n\n2. The author introduces the smoothness of the expected loss function as one additional assumption besides bounded gradient. To the best of my knowledge, there exists expected-smoothness assumption [1] that also try to leverage the smoothness of the function, yet can replace the bounded gradient and bounded variance assumption. I’m wondering whether the author considers other methods to try to eliminate some of the assumptions.\n\n\n[1] Gower, Robert Mansel, et al. \"SGD: General analysis and improved rates.\" International Conference on Machine Learning. PMLR, 2019.\n\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ahaN_Qy69Az", "reviewer": "Reviewer_KxnX", "summary": "Examines a range of stochastic optimization settings from IID to Adversarial. \nProvides regret bounds for optimistic FTRL in terms of a combination \"within round variances\" and \"between round variances\", the former representing the stochastic part of the gradients and the latter representing the adversarial part, recovering good known bounds for both of the pure iid and pure adversarial cases if they prevail, and interpolating \"naturally\" between these cases. \nBoth in the convex and strongly convex cases.\nLower bounds that match time-dependent term.\n\n\n\n\n ", "questions": "- unclear why lag-1 variability of the gradient is the right notion of \"adversarial\". if the player has access to f( . , \\xi_t) for all past t, for example, then one could predict with the average of the history instead of the lag-1 predictor. does this lead to a different upper/lower bound? is there a way in which not using all the history is better? I imagine one could do better using the full history.", "limitations": "some discussion of other settings between iid and adversarial that would not be covered, or would not achieve their respective optimal bounds using these methods would be useful to provide context to the reader.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Interesting, novel setting. \n- Results are intuitive and interpretable in the context of related work.\n- \"best of both worlds\" gets optimal rates in multiple settings without knowledge of the setting to tune the algorithm.\n- the examples provided on pgs 4/5 make it clear that this these results are useful and flexible as they can be applied to a wide range of settings that are of practical relevance.\n- proofs seem to me to be correct.\n- topic of \"between iid and adversarial\" is timely and interesting\n\nWeaknesses:\n- The proof techniques are not novel. The novelty of the results is essentially due to the setting that was introduced and application of the corresponding definitions the authors introduced. However, this is not a big detractor, in my opinion, since the results themselves are interesting regardless. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept