Optimal Rates for Random Order Online Optimization
Authors: Uri Sherman
Tomer Koren
Yishay Mansour
Venue: NeurIPS 2021 Oral (2021)
Keywords: Online Learning
Convex Optimization
Algorithmic Stability
Stochastic Gradient Descent

Abstract: We study online convex optimization in the random order model, recently proposed by Garber et al. (2020), where the loss functions may be chosen by an adversary, but are then presented to the online algorithm in a uniformly random order. Focusing on the scenario where the cumulative loss function is (strongly) convex, yet individual loss functions are smooth but might be non-convex, we give algorithms that achieve the optimal bounds and significantly outperform the results of Garber et al. (2020), completely removing the dimension dependence and improve their scaling with respect to the strong convexity parameter. Our analysis relies on novel connections between algorithmic stability and generalization for sampling without-replacement analogous to those studied in the with-replacement i.i.d. setting, as well as on a refined average stability analysis of stochastic gradient descent.

Optimal Rates for Random Order Online Optimization
Uri Sherman
Tomer Koren
Blavatnik School of Computer Science Tel Aviv University
Blavatník School of Computer Science Tel Aviv University, and Google Research tkoren@tauex ac.
uri sherman@@al... tau.ac. il.
Yishay Mansour
Blavatnik School of Computer Science Tel Aviv University, and Google Research mansour. y wisyyysshhsyaaaa com.
Abstract
We study online convex optimization the random order model, recently proposed Garber al. [8], where the loss functions may be chosen by adversary, but are then presented to the online algorithm in a uniformly random order. Focusing on the scenario where the cumulative loss function is (strongly) convex, yet individual loss functions are smooth but might be non-convex, we give algorithms that achieve the optimal bounds and significantly outperform the results of Garber al. [8], completely removing the dimension dependence and improving their scaling with respect to the strong convexity parameter. Our analysis relies on novel connections between algorithmic stability and generalization for sampling without-replacement analogous those studied in the with-replacement i.i.d. setting, as well as on a refined average stability analysis of stochastic gradient descent.
Introduction
Online convex optimization [25, 12] studies the iterative process of decision making as data arrives in an online fashion. The model posits game of T rounds, where in each round the learner chooses a decision w, from a convex set W S Rd after which she observes loss function fi - R. and incurs loss fr (w;)). The learner's objective is to minimize her regret, defined as her cumulative loss minus that of the best decision in hindsight w" arg min E/= (w). the prototypical assumed be convex and adversarially chosen by
setting, the individual loss functions opponent commonly known as nature or the adversary- who has knowledge of the learner's algorithm. While this setup is fundamental enough to accommodate diverse set of applications (see, e.g., [12)), studying variants of the basic model promotes modeling flexibility, and further broadens the set of problems to which optimization techniques may be applied.
Recently, Garber et al. [8] consider relaxing the convexity assumption by requiring that only on average the loss is (strongly) convex- property the authors refer to cumulative (strong) convexity- but do not require that the losses are convex individually. It is well known (e.g., [4]) that under these assumptions, if the losses are sampled i.i.d. from some distribution, stochastic gradient descent (SGD) obtains the optimal (log 7') regret in expectation. However, as turns out, the fully adversarial model the cumulative strong convexity assumption is too weak: Garber al. [8] show that in this case there is linear regret lower bound. Consequently, they propose the random order model, where T losses chosen adversarially but then revealed to the learner in uniformly random order. Within this model, under the relaxed convexity assumption Garber et al. [8] obtain sub-linear regret for a number of specialized settings, differing in their assumptions the structure of the individual loss functions.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

In the most general case (the one we consider in this paper), they prove online gradient descent obtains regret O(dG2 /2 log T) w.h.p. for G-Lipschitz d-cumulative-sttrone convex losses.
is informative to compare the random order model with the i.i.d. stochastic case, where on every round new loss is sampled uniformly and independently from the set of losses, that is, with-replacemmet By contrast, the random order model specifies that on every round a new loss is sampled uniformly
crehaouttrellccmmnttt an in particular not independently. Concretely, let L be an arbitrary set of T smooth and Lipschitz continuous loss functions. Set F(w) / Lrec f(w), and assume F is A-strongly-convex over W. The learner's s goal is to minimize her regret on the loss sequence fi..... obtained from uniformly random ordering of L. As noted previously, if the losses f, were drawn i.i.d., SGD obtains the optimal (log 7') regret even though the losses are not individually convex. In nutshell, when losses are i.i.d., the gradients used in the SGD update conditionally unbiased estimates of the gradient of the average (strongly convex) loss, hence the optimal regret is achieved in expectation. The difficulty in the random order model stems from the fact that random order gradients are not conditionally unbiased; given any set of past losses fr.....f-I.. the next loss is uniform over the complement
(fi..... fi-1), and thus ffi (w,) biased.
To overcome this complication, Garber et al. [8] work via the uniform convergence route, and build on concentration bounds applied to Hessians of the losses. As a result, they achieve suboptimal bounds, particularly in the general case where a dimension factor is introduced by discretization argument necessary ensure convergence over the entire domain. Here we choose different strategy, and draw connections to notions of algorithmic stability and generalization studied in statistical learning theory. Our approach introduces significant improvements compared to prior work, and achieves regret bounds optimal up to additive factors.
1.1 Our results
We present and analyze two algorithms for random order online optimization, the first of which obtains the optimal regret up to additive factors. Let ft.....f fr be a random order sequence of G-Lipschitz, f-smooth losses, where : W - R for all $ T. Assume the domain W Rd is convex, and has diameter bounded by D. Further, assume the average loss + ΣT f. is A-strongly convex. We prove;
Theorem (informal). There exists algorithm (Algorithm 1) for random order online optimization that obtains regret of O ((G² /A) log in expectation.
Although the above result matches the optimal result for the individually strongly convex setting (up to additive factors), Algorithm requires memory linear in T. This disadvantage motivates another algorithm, which trades off an extra factor of k = B/ A in the regret for lower memory requirements.
Theorem (informal). There exists an algorithm (Algorithm for random order online optimization that requires memory linear in d, and obtains regret of O ((GG2/ log 7) in expectation.
Big-O notation in both theorems hides additive factors polynomial in problem parameters p. G and D (but does not hide multiplicative factors in these parameters). By comparison, Garber et al. [8] obtain a regret bound of ((dd) /2 log 7) w.h.p. for this setting. Both of our algorithms completely remove the dimension factor d. and reduce scaling w.r.t. the strong convexity parameter by a factor of 1/2 and 1/ respectively. Moreover, their results require the losses to have a Lipschitz Hessian (see 8, Theorem A.3), an assumption we do not make.
In addition, we consider the case that F is convex (but not strongly convex), and apply our above results by means of regularization. As a corollary of the first theorem, we obtain for this setting regret that scales as Ō Ō(VT), matching up to logarithmic and additive factors the optimal rate for the individually convex setting. Similarly, the second theorem implies a O(T2/3) regret algorithm which is also memory efficient for the convex F case. Notably, a similar reduction applied to the results of Garber et al. [8] would yield regret bound of 3dd33/4) This highlights the significance of our improvement to the dependence on A.
Finally, we note it remains an open question to determine whether vanilla without- without-replacementt replacement SGD achieves optimal regret the random-order model (our results leave a multiplicative gap of order 1/1 between the upper and lower bounds). For the case of quadratic losses, however, using our techniques combined with a concentration argument it is possible to show that SGD indeed achieves optimal Oloo A) regret bound (up to logarithmic terms).
2

---

1.2 Overview of techniques
Our approach builds the observation that regret on a random order loss sequence may be expressed as the average generalization error w.r.t a without-replacement training sample. In light of this, we relate random order regret suitable notion of algorithmic stability, mimicking in sense well known argument previously employed in the context of i.i.d. sampled training sets [3, 21J. At a high level, stability measures the sensitivity of an algorithm to small changes in its training set, and is a classical approach to proving generalization bounds [3, 21]. More often than not, the particular notion used practice is uniform stability, where sensitivity is measured w.r.t. the worst case small change in the training dataset; (mx)e%(m) (I - f(A(S))
Our key insight is that while cannot hope for uniform stability as losses are not assumed to be convex individually, we may exploit strong convexity of the population loss to show SGD admits average stability; Es- (m) (S) ((A(S))
& e(m). In particular, we prove the gradient update is contractive in expectation; E [ -y--n/((>) S EE ||x->|| under the cumulative strong convexity assumption. In turn, this yields a stability result which implies regret that scales with 1/r for the early rounds up to x T/x, where K is the condition number of the problem. In short, as the game progresses the bias of the random order gradient estimates increases, and the gradient update becomes unstable.
To overcome the loss of stability in later rounds, we devise a simple online sampling mechanism that generates i.dd uniform samples from a random order distribution, effectively ensuring unbiased gradient estimates throughout all 7' rounds, and consequently optimal regret up to additive factors. Finally, our approach allows us to develop an analysis framework that naturally accommodates SGI) based algorithms in the random order model, and in broader sense establish stability of SGD in new, relatively general setting.
1.3 Related work
Random-Order Online Optimization was proposed in the recent work of [8] (where it is referred to as ROOCO), who establish an O( /A9) log 7) regret upper bound for G-Lipschitz A-cumulative- strongly convex losses. In the classical OCO setup [25, 12], under the assumption the losses are A-strongly convex individually, it is well known the minimax regret scales as @(( /A) log T), and that the lower bound also applies under the assumption the adversary is i.i.d. stochastic [14, 13]. 1 In addition, it is well known (see e.g., [4]) that the upper bound for the i.i.d. adversary is obtained in expectation by SGD also for non-convex losses, as long as the expected loss is strongly convex. In this work, we show that the same regret upper bound also holds for the random order adversary.
Also relevant to our work is the study of stability and generalization [3. 21] in modern learning theory, and in particular stability properties of SGD. Proving generalization bounds with stability arguments is a well known approach dating back at least to [19, 5, 6]. The specific notion of average stability in the i.i.d. setting we draw upon was defindd in [21], though many similar measures have appeared in the literature long before their work (see [3, 21] for an overview). The influential work of [1] gave the first generalization bounds for general forms of SGD with an analysis relying on the notion of uniform stability [3]. Since then, several works have used similar approach to gain further insight into stability and generalization properties of SGD, e.g., [15, 2.
A related line of work [9, 22, 16, 20, 18] studies SGD hithoue-replacement for solving finite-sum optimization problems, a setting commonly encountered in offline machine learning applications. Here, multiple epochs of SGD are executed over a given training set, with the objective to produce a single output (approximately) minimizing the average loss. However, the majority of the results are obtained under the (vastly simplifying) assumption that the individual loss functions are convex, and therefore do not apply in our setting. In addition, the performance metric of interest convergence rate, and not regret which is the focus of our paper. In particular, Nagaraj et al. [16] employ the method of exchangeable pairs to relate the average and random order loss to a stability-like property, and obtain optimal (up to polylogarithmic factors) convergence rate for single epoch, albeit only for individually convex loss functions.
Recently, a number of papers study SGD wiihouttreplacemmnt and attempt to relax the convexity assumption [10, 17, 1J. but the bounds they obtain are under conditions inapplicable for our setting.
'The lower bound given in Hazan and Kale [13] uses quadratic (hence, smooth) losses, and is easily extensible to witthout-replacemet sampling, and therefore applies in our setting.
3

---

Specifically, they impose a requirement that the number of epochs passes a certain threshold strictly larger than one. Moreover, satte-of-the-are bounds achieved by [1] are suboptimal w.r.t ours even had we ignored the epoch requirement.
2 Setup: Random-Order Online Optimization
In this section, review notation and assumptions used throughout the paper, and give the formal definition of the model we consider. We let = -.1...., . denote an arbitrary set of 7 different datapoints, and denote by W Rd closed convex set with diameter bounded by
D = maX ||x - yll. In addition, we let [xxx) = IT (x) = arg win ||x - w|| denote the orthogonal projection onto W.
We consider loss function f W Z - R. and denote the average (also expected / population) loss by F(w) = Zez f(w; z). We make the following assumptions;
Assumption (Individual Lipschitz Continuity). For all Z, f(,;z) is G-I.ipschiz;; namely [Vf(w;:))| S G for all w E W.
Assumption (Individual smoothness). For all E Z. f(::2) is f-smooth; namely [V Vf(;:)) $ f||xx yll for all x. E W.
Assumption 3 (Cumulative strong convexity). F is A-strongly convex; namely F(y) F(x)
(y-x) y for all x, W.
In addition, we define the condition number of by K == B/A.
We will be primarily interested in the random sequence of losses f(,;zz) obtained from uniformly random orderings of Let Zi...... ... Zm (mm) denote random sequence of m datapoints, where = Ca, E Z and a : [T] - [T] is a uniformly random permutation. Equivalently, 2(m) may be also considered as the distribution of m datapoints sampled sequentially without--eelacemmet from Z. Omitting the number of samples parameter and writing z Z denotes uniformly random sample of single datapoint from In addition, if S (ZI...., Zm) a sequence of datapoints, ~ 2 \ denotes a uniformly random sample of single datapoint from Z \ S. In sake of conciseness, we sequence 5 ((), followed by a sample from the complement - S. We write Fm = OZ1..... 2m) to denote the filtration given by the sequence of o-algebras generated by the random variables (Z),..., Zm). This, of course, is equivalent to sampling Z1.... 2m+1 Z(m 1), and then setting S (Z),..., Zm) and Zm+1-
write S. 2 Z(m, 1) to denote a sample
Given a random order sequence Zi..... 2T Z(T), we consider the problem of minimizing the expected regret with an online algorithm. We denote the minimizer of the population loss F by w* arg min F(w), and let w, denote the iterates produced by an online algorithm A. The expected regret of A on Z(T) is defined as;
Ry = Σ (wwiz))(ww'' 1=1
where the expectation is over the random order sequence and any randomness potentially introduced by A. Finally, when a sequence of realized datapoints Zm clear from context, we let Fm (w) E" fww; denote their empirical average loss.
3 Stability and Generalization Without Replacement
In this section, we discuss notions of stability and generalization when sampling without-replacement, and give basic results relating to stability of SGD in the setting under consideration. We work with ordered training sets, and write S = (EI..... 2m) to make the ordering explicit in our notation. When such training set is in context along with another datapoint ε, we define 5(0 == (Zi..... Zi-1. ži, Zi+l. ..., 2m) to be the new training set formed by taking S and swapping the i'th datapoint 2 with ε,. Finally, we say A learning algorithm if maps training sets of any length decision; A Z" - W.
3.1 Recap: Stability and generalization in the i.i.d. setting
In this section we recall the relevant definitions previously studied in the i.i.d. setting. Here, we assume the training set S = (ZI...., Zm) DD an i.i.d. sample of m datapoints from some predefined distribution D over elements of Z.

---

Definition (on-average generalization; [21, with rate Egen(m) if for all m: EESDD -F(A(()))))(((S))) S (gen(m).
We say a learning algorithm A avveage-gennraaiee
The definition of stability that follows relates small change in the training set S 5(0 to the change in the learning algorithm's performance. Here, as one would expect, the swapped datapoint 2; D is sampled independently from the original training sample S.
Definition (average-RO Rongge-ROOoo stability; [21, 3D. We say a learning algorithm A is average-replace-one stable with rate Stbb (m) if for all m;
m
-
s (m).
M
With the above definitions, well known stability and generalization are in fact equivalent (e.g.. [21]).
3.2 Stability and generalization without replacement
In this section we diseuss the analogous notions suitable for sampling without- replacmett We adopt the term out-of-sample (oos) to distinguish the without-replacemmnt setting, and say A on-average- no-average-generaalzee- generalize-oos with rate (me) if
(ss,--((m.)) (f(())) Fm (A(S))] Egen( (m).
(1)
Note that here, generalization is measured w.r.t. datapoint drawn out-of-sample, and in particular not independently of S. The situation is similar for the notion stability; while in the i..d. case the "non-coupled" index in (()) hosts a different datapoint sampled independently. here this datapoint sampled from the complement Z S. The analogous definition for stability without-replacemenn says a learning algorithm A is average-replace-one- stable with rate 6aab if
( f(A(S)): s Estab (m).
(2)
F=1
However, it will be more convenient in case work with slightly different definition, which relates to the distance between outputs of the learning algorithm, rather than to the change in out-of-sample loss. We consider w.l.o.g. randomized learning algorithms A Z X W, where g E X denotes the internal random seed used by A. For convenience, we slightly overload notation and let ç X denote the distribution over A's random seeds.
Definition (on-average stability). A learning algorithm A is on-average-oos stable with rate Esab (m) on random order distribution % if
max -,, [I)A A(s :0I] (maa
We wish draw the reader's attention two important aspects the above definition. First, note that the measure is w.r.t. random training sets, which significantly differs from uniform stability where worst case training sets are considered. The maximum the definition relates to the index of the swapped sample, and not the training sets S. S()) Second, the same random seed & fed A both training sets, that is, we measure the expected distance between outputs subject to maximal coupling of the algorithm's randomness.
When we discuss an online algorithm and random order sequence .I. (T)) in context, denote by Zl:m (Z), (ZI...., 2m) the prefix of length m. In addition, if W A(Z1mi E), we denote the coupled iterate by
w m+1 A(1 = A(zI.... Zi-1s ži Zitls Zmi E), where ž, Zm+1-
With this notation, if A satisfies Definition with rate e(m), we have E [| - w (1)
m+] e(m) for
all 5 m. Note that an online learning algorithm is nothing more than a learning algorithm that respects the order of the samples it is given as input. To conclude this section, we relate the population and out-of-sample performance gap to stability of the learning algorithm, as provided by the below lemma
5

---

Lemma 1. Assume A is on-avg-ann oos stable with rate e(m), and let é: w R be any L L-Lisschitz
loss function. Then;
(9.2-Z(m.1).--2 (((A()):))((ACC))) -
Lm T c(m).
If A is online algorithm producing iterates W, and 21, , (x()) is random order sample, this immediately implies
G(I - 1)
E[((w;z)) F(w,)] -(nn:)))FF((,)))
e(t 1).
T
We provide the proof in the full version of the paper [23].
3.3 Average stability of SGD
In this section, develop the basic tools employed to establish that under appropriate conditions, SGD is algorithmically stable in the sense of Definition I. Crucially, by considering average stability able to leverage strong convexity of the expected function F and prove the desired result. For w E W and v + R, we denote by S(w; w. 17) = II(w v)))(w)) a projected gradient descent step from Our key lemma stated below and proved in the full version of the paper [23], says gradient step on a random function y is contractive in expectation when y is strongly convex in expectation, and the step-size is sufficiently small.
Lemma 2. Consider arbitrary discrete distribution P of G-Lipschitz and f-smooth functions // W + such that ((w) = (w)( is p-strongly-coovvex Then for any x. E W. a gradient descent step with step-size r /// //B² satisfies;
IE Ev-W [[ w. 9(y: W. mill (1- 1/ 11 yll-
Notice that the above result dictates for the step-size to be lesser than p/ which roughly factor of 1/x smaller than needed to ensure (deterministic) contractivity under the assumption of individually strongly convex losses (see [11]). Lemma serves as a building block to prove stability of SGD subject to relatively generic conditions, which do next. Loosely speaking, if two training sequences do not differ too much, and the conditional expected loss is strongly convex, the expected distance between SGD iterates shrinks proportionally to the number of iterations executed.
We denote by GD(S; w1, m. {T. }) the iterate w Wm+1 E W produced by executing m projected gradient descent steps on sequence of datapoints S (21, ............................. 2,), T 2 m, starting at the initial point E W, with step-sizes (n:). When any one of w1. m or (n,) are clear from context, they may be omitted in sake of conciseness. Our next lemma quantifies how small perturbations in random training sets translate to the expected change in outputs of SGD. Informally, it says that under appropriate conditions, if we swap just single training index S the sequence of gradient steps arrives at the same output up to distance O1/mm).
Lemma 3. Let S m N, and (Z1...., Zm), S' (z/....., z'm) be two random datapoint sequences. Further, assume that for 0 < μ and 0 I 8 - μ/26, it holds that
(i) Pr(a, # z/ F-11) S 6 for all
(ii E [[[[wz F--1] is p-strongly convex as function F W,
Then, for step-size schedule n, min ( 2/ with p == H 1- 88. and any w E W, we have;
where F,-1 0 2/.-.... Z1-1, 24..
2. 2,-1,
4G (1 + 48m).
[[GD(S; w1, m) GD(S": :1, s jim
The proof of the above lemma is given by following the recursive relation specified by Lemma 2 and the conditions imposed on the random sequences S' The details are rather technical and are thus deferred to the full version of the paper [23]. To conclude this section, we state and prove simple corollary of Lemma 3, establishing stability of SGD when the number of steps taken is sufficiently small.

---

Corollary 1. Let w1 E W. and set min /A/2p". 10/2p".4/// ,4/Ar/ W1+1 II(,,, (z))))) is on-avg-oos stable with rate
Then the SGD update defined by
8G
Estab (m)
Am
for all m S <//KK. Proof. Fix i s m, let A denote the SGD algorithm, and consider random order sequence 21....:27 ........---. 2(T). We have Wm+1 = A(Z1m), and w =A( as defined in Eq. (3) (note that here though, A has no internal randomness). Next, m+1 with the two sequences $ == Zi:m and S' = (2) ..... =iom
verify conditions for Lemma 3 are satisfied
and by definition S and S', we have that & 2/ for all r hence clearly Pr(z, z ( .) for all r * i. For the second condition, let F,-1 denote the set of all datapoints observed prior to round r; Fy-1 == (z E Z This means F1-1 contains exactly (21, (21..... 2-11, and perhaps depending 24..24......22.... 2,-1, 2,-1,,,,111 == |F,-1l E {1,1- 1). Now, given F1, we have that 2, is uniform over 2 \ F₁-1, therefore
Let Fイ-1 (Zz 21-...
whether > i, hence
[[f((;z,,) 1-,11= T
Σ ZEZIFi-1
f(wi2)
T T (F(W) --x(F(m))
Σ f(w:2)). 26FF-1
By our smoothness assumption, + L..ef.,, f(w;2) is (kB/T) and in addition kß/T S mß/T= & (A/20)5= = 2/2. Therefore, by 1-strong convexity of F we get that the last term the above derivation is at least 4/2-strrongly-convex (this follows from standard argument, see Lemma 10). Therefore, by Lemma 3 with μ == 1/2, 6 = 0 it now follows that
8G
E W w m+1 || = [[GD(S) GD(S')I s Am
which completes the proof.
4 SGD for Random Order Online Optimization
In this section, we present two algorithms for random order online optimization. Lemma motivates derive SGD based algorithms that obtain low regret w.r.t. the population loss F, and algorithmically stable the sense of Definition 1. Given a random order sequence 21, 2(T), the SGD update with gradient estimates {&r} and step sizes {nr) is given by
Wr+1 I(w, 71r8;).
is not hard to show that the regret w.r.t. of SGD directly related the error terms introduced
by using & in place of the true population loss gradients VF(w,). This fact is made formal in the lemma below, which serves as starting point for the analysis of both algorithms we present. The proof follows from standard arguments, and is deferred to the full version of the paper [23].
Lemma Consider T iterations of SGD with gradient estimates {&r} and step-size schedule min fp//p,,0 (ff)((()). We have that the following bound holds with probability one;
1²12 G²
Σ F(w,) F(w")
+
(1+logT).
((F((w))- -g:) (ww--w)..
(4)
20 P
4.1 Reservoir SGD
In light of Corollary 1, it is evident that different strategy is necessary to achieve stability in late rounds of the online game. As a solution, Algorithm presented here employs a sampling procedure reminiscent of reservoir sampling [24], which results in gradient estimates & that are conditionally unbiased estimates of (ww,,) throughout all rounds. This ensures the conditionally expected function every round is strongly convex, thereby implying stability is maintained for the duration of the game. As another implication, the error terms on the RHS of Eq. (4) vanish, which essentially reduces the optimization problem (i.e., regret w.r.t. the population loss F) to the i..d. setting. Consequently, regret bound will follow from a batch-to-online conversion supported by Lemma 1 and Lemma
Our first lemma given below, shows that the intermediate sequence of datapoints 2 generated line 4 are i..d. uniformly distributed, which immediately implies that E g, VF(w,).
7

---

Algorithm ReservoirSGD
1: input: step-sizes 771, ................................ AT Rt, W
2: for /= to do
3: Play w,, Observe 2
w.p. - d
4: Set &, vf((wiz)) where 2/ (Unif (4-1))
w.p. 1-1
5: W,+1 [[w,; - 7(8{)
6: end for
Lemma 5, The {z/} intermediate sequence produced by Algorithm in line 4 is uniform over and i.idd;;
Vz Z: Pr(z) = =) = Pr(z, z| (<t) = =
Proof. Fix the first sampled datapoints 21. .1.......- -1-1 2(1 1). Then for all
Z1-h
1
Pr(z) Z
7-1
In addition, since 2. 2(r), it follows that is uniform over Z 21--11 (Note that as we conditioning on Z14-11, we have that 21:-1 deterministic.) Hence, for all z \ 21z-1 we have
Pr(z) = Eiu-1) = T - 1+
T T-1+1 T
The above implies that Pr(z) 2 Z1=-1) 1/T for all Z. Finally, the by the law of total probability;
1 -
Pr(z) =) 2 Pr(z// = (11-1)
as desired.
Next, we argue Algorithm maintains average stability with the desired rate throughout all T rounds. Lemma 6. Assume T 2 28/A, and set ÿí p Then Algorithm with step-size schedule T), = min (2 on-avg-oos stable (Definition 1) with rate
40G
Estab (m)
Am
Proof. Let i S m < T, and recall the definition of the coupled iterate in Eq. (3). We have that
[|Wmell w (i)
m+1 || E (GD(S') GD((')lI..
where S'= (zf...... and S (zi...... 2 denote the intermediate sequences (line 4) produced when running Algorithm 1 on 21:m and 21mm respectively. Now, consider the indexes of datapoints selected by the sampling mechanism on line 4 which we denote by jr. meaning j, = when z; = zı- Since the same random seed is used for each coupled iterate, we have that the indexes from both execution paths are the same. Next, we will show S", satisfy the conditions of Lemma 3.
(i)
Indeed, denote by F, the filtration encapsulating all randomness (random order and algorithm) to and including round Then by Lemma 5 and since 21:m and (i) any > i;
2 differ only at index i, have for
Pr(z) # z!" (r,1) = Pr( = In addition, it trivially follows that Pr(z) z FF-1) for all r T, we have 1/T < A/26, and so the first condition is satisfied. For the second condition, note that again Lemma [[] zf) Fr,1] = F(w) for any F--r-measurable implies A-strong convexity of the conditionally expected function.
< i. Owed to assumption
W, which immediately
By the above, obtain that S" follow a distribution satisfying conditions required by Lemma with μ = 2, = 1/T, therefore,
4G
(1+4 m s
40G
E [IGD(S': m) GD(S": : m) (1. (1/7)
Am
and we done.

---

G(r- A regret bound for Algorithm 1 readily follows, we have essentially established both convergence rate and stability of the algorithm. Below, we state and prove our main result concluding this section. where ji
Theorem 1. Running Algorithm with step-size schedule ti min A - B/T, it is guaranteed that:
2G (1 logg) 40G² + f² + I ((wiz))- f(w":
A
Proof. By Lemma 5, we have that for all T
E(VS(w))))) (w, w*)] [VE, (V) (w) (w)-
- w")],
where E.I.] = 21, Z4.24...... 2,-1, و denotes the conditional expectation w.r.t all rounds up to and not including This implies the gradient error terms the RHS of Eq. (4) vanish. In addition, note may assume T 2 2p/A. for otherwise it trivially follows that Σ f(w,;z)) f(w": 2rGD Hence = 1/T & A/2p, and by Lemma 4 we obtain the following bound on the GDT & A regret w.r.t. the population loss F;
B²D² 2G A
F(w,)- - F(w') Σ
(1 log 7). A
f=1
To establish online performance, observe that by Lemma and Lemma we have
Estab 1) G(1 - 1) 40G
40G
T
A AT
Therefore,
T
T
E
(wiiz))
=
- FF:)) +
Σ
F(w.)- F(w*))
1=1
1=1
1=1
40G²
B2D 2
2G2
A A (1 +og7)),
A
and the result follows.
4.2 SGD without replacement
While Algorithm obtains regret which is optimal up to additive factors, it memory intensive due to the sampling procedure requiring the history of the entire loss sequence. This motivates Algorithm which uses the random order gradients as they arrive, and sacrifices a factor k in the regret bound for lower memory requirements.
Algorithm 2 SCDD-without-replaemmnn
input: T.7 E N, step-sizes .7 R4, W1 E
2: for f = to T do
3: Play w,, Observe 2,
4: W1+1 < Π(w, 7I&1), where &, == Vf(wiz))
5: end for
6: for -or+=
play w, w E wi.
With Corollary we already know Algorithm 2 is stable with rate 0(1/m) for T/2x, least for all iterates excluding W. However, it is not clear priori whether these iterates also obtain good convergence rate to prove this we must control the gradient error terms on the RHS Eq. (4). Evidently, with random order gradient estimates the behavior of these error terms is also related to stability the same sense that the actual losses are. By Lemma with f(w; z) = Vf T (w- w"), it only remains to derive the appropriate Lipschitz constant, which is done in our next lemma. Notably, this means that the two sources of error, gradient estimates and the batch-to-online gap, both hinge on the very same stability property of the algorithm.

---

Lemma 7. Running Algorithm 2 with step-size schedule n, min (2/2B². /4/Ar) and 7 7/2x, we have that the gradient ervor terms on the RHS of Eq. (4) are bounded, for all S T, as
8G + BD)
E[(VF(w;)- - -g,) -,)T((w, -Wi-w>
AT
The proof of Lemma 7 is given by arguments following the above discussion, and is deferred to the full version the paper [23]. Next, we state and prove our main theorem for this section providing the regret guarantees for Algorithm 2.
Theorem 2. Running Algorithm 2 with step-size schedule b, min 10/22/.4//0 and T T/2x, holds that
|6 12
BDG
B²D²
(winz)) - f(w" =
log T
A. +
12
E=1
The proof of Theorem 2 provided in the full version of the paper [23], hinges on the ingredients discussed thus far, along with the fact that averaging preserves stability.
4.3 The convex case
Given Algorithms and 2, we can derive as an immediate corollary regret bounds for the case where the loss function I' is only assumed to be convex in expectation, but not strongly convex. This is achieved by adding L.2 regularization; pick wo E arbitrarily, and consider f (w;;2 == fw: 2) + fllw - woll?. By transforming the gradient estimators & +- gr a(w, wo) in both algorithms, we optimize for the regularized random order loss sequence (1:z))....... ((;z))) and obtain regret bounds for suitable choices of a.
Corollary 2. Assume the loss function f W x R is G-Lipschitz and f-smooth for all Z. individually (Assumption I and Assumption 2), and that } L f(;;z) is convex over W. Then, have the following guarantees for running Algorithms and 2 on the regularized loss sequence:
(i) for Algorithm I and 1/VT; E ΣL f(wiiz)) f((w=;a)) =Õ(VT).
(ii) for Algorithm 2 and 1/3 f(writ) f(w":ar) Ō(T213).
where big-ō hides polynomial dependence on the problem parameters B, G, D, and logarithmic dependence on T.
Proof. To ease notational clutter denote fi(w f(w;z,) and ft (w) (w: fi(w)) ||w woll?. Let (w) = + Ezez (w( then ("(w) F(w)++++++)))))))) + ||w woll?. which implies that F a-strongly convex. Therefore,
Σ ( (1 s Ry (a). r=1
where (a) denotes the regret w.r.t. the regularized loss sequence fi" In addition;
Σ (((w))-f(ww)
Σ f(w,,) fw,,) Σ (w f1 (w") Σ (ww)--f(ww)
I Σ
T
a
||w, - woll +
a (w,(w) f. (w")
||
woll?
2 1=1
2
1=1
1=1
(w,,) (w") aD2
$ (a) + aD²T.
The result follows after substituting for the values of a specified in the statement of the theorem, and the regret bounds of Theorems and 2.
We conclude by noting the above result underscores the importance of obtaining bounds with good dependence on the strong convexity parameter. In particular, only the optimal 1/2 dependence allows for regularization that guarantees optimal (up to logarithmic factors) performance w.r.t. in the non-strongly convex setting.
10

---

Acknowledgements and funding disclosure
This work was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grants number 993/17 and 2549/19), by the Len Blavatnik and the Blavatnik Family foundation, and by the Yandex Initiative in Machine Learning at Tel Aviv University.
References
[1] K. Ahn, C. Yun, and S. Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. arXiv preprint arXiv:2006. 2020.
[2] R. Bassily, Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neurul Information Processing Systems, 33, 2020.
[3] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Reseurch, 2:499-526, 2002.
[4] Bubeck al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4))231-3577 2015.
[5] L. Devroye and T. Wagner. Distribution-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory. 25(2):202-207, 1979.
[6] L.. Devroye and T. Wagner. Distribution-free performance bounds with the resubstitution error estimate (corresp.). IEEE Transactions on Information Theory, 25(2):208-210, 1979.
[7] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
[8] D. Garber, G. Korcia, and K. Levy. Online convex optimization in the random order model. In International Conference Machine Learning, pages 3387-3396. PMLR, 2020.
[9] M. Gürbüübalaban, A. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, pages 1-36, 2019.
[10] Haochen and S. Sra. Random shuffling beats SGD after finite epochs. In International Conference Machine Learning, pages 2624-2632 PMLR, 2019.
[11) M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. International Conference on Machine Learning, pages 1225-1234 PMLR, 2016.
[12] E. Hazan. Introduction to online convex optimization. arXiv preprins arXiv: /tt.//999000000 2019.
[13] E. Hazan and S. Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. In Proceedings of the 24th Annual Conference on Learning Theory, pages 421 1436. JMLR Workshop and Conference Proceedings, 2011.
[14] E. Hazan, A. Agarwal, and Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-
2007.
[15] B. London. pac-bayesian analysis of randomized learning with application to stochastic gradient descent. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 2935-2944, 2017.
[16] D. Nagaraj. P. Jain, and P. Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In International Conference Machine Learning, pages 4703-4711. PMLR, 2019.
[17] L. M. Nguyen, Q. Tran-Dinh D. T. Phan, P. H. Nguyen, and M. van Dijk. A unified convergence analysis for shuffling-ty typp gradient methods. arXiv preprint arXiv:2002.08246. 2020.
[18] S. Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pages 7964-7973. PMLR, 2020.
[19] W. H. Rogers and T. J. Wagner. A finite sample distribution free performance bound for local discrimination rules. The Annals of Statistics, pages 506-514, 1978.
[20] Safran and O. Shamir. How good SGD with random shuffling? Conference on Learning Theory, pages 3250-3284 PMLR, 2020.

---

[21] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670 2670, 2010.
[22] O. Shamir. -ephemetre sampling for stochastic gradient methods. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 46-54, 2016.
[23] U. Sherman, T. Koren, and Y. Mansour. Optimal rates for random order online optimization. arXiv preprint arXiv:2106.15207 2021.
[24] Vitter. Random sampling with a reservoir. ACM Trunsactions on Mathematical Software (TOMS), 11(1):37-57, 1985.
[25] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In Proceedings of the 20th international conference machine learning (ICML103), pages
928-936, 2003.
12


Reviews:
[{"review_id": "ymm_l3YP3t9", "reviewer": "Reviewer_JxoJ", "summary": "Problem description: The paper studies the problem of online convex optimization in the random order model. This problem was recently proposed by Garber et al. (ICML 2020). It is a generalization of online convex optimization, where at each step the learner incurs a loss function $f_t$ and the goal is to minimize the cumulative loss $\\sum_{t=1}^{T} f_t$. The authors inspired by Garber et al. (2020), considered the scenario in which each $f_t$ is smooth and Lipschitz but not necessarily (strong) convex. However, they imposed this assumption that $\\sum_{t=1}^{T} f_t$ is (strongly) convex. Garber et al. (2020) assumed that at each step $t$, a new loss function $f_t$ is sampled uniformly without replacement from $\\{f_t\\}_t=1^T$, and they call this setting random order online optimization. The same setting is peruse by the authors of this paper and they improved the results in Garber et al. (2020), under the same assumptions.\n\nAssumptions: 1. $f_t$ is Lipschitz \n2. $f_t$ is smooth\n3. $\\sum_{t=1}^{T} f_t$ is $\\lambda$-strongly convex.\n\nApproach: Their main idea is to use the stability properties of stochastic gradient descent, see Shalev-Shwartz et al. (JMLR 2010). The authors defined a new notion of stability (page 5, line 176). This new definition of stability is suitable for sampling without replacement, which is beneficial for random order online optimization. Note that relevant definitions of stability Shalev-Shwartz et al. (2010), works only for i.i.d sampling. \n\nBy this conviction, they proposed Algorithm 1 (page 7) which is inspired by Vitter (1985). They proved the stability property of Algorithm 1 in Lemma 6 (page 7), which implies their main result in Theorem 1 (page 8). Since Algorithm 1 requires an intense memory usage, they proposed Algorithm 2 (page 9), which is more economical in that regard. Theorem 2 (page 9) uses Algorithm 2 but with a worse dependency w.r.t $\\lambda$ (strong convexity parameter), compare to Theorem 1.\n\nContributions: With a different and a novel approach, they studied the problem proposed by Garber et al. (2020) and they could improve the results which I summarize as follows:\n\n1. The upper bounds in Garber et al. (2020) have a linear dependency with respect to the dimension of $f_t$. They could remove this dependency and the rates are dimension free.\n\n2. In Theorem 1 (page 8) they improved the results in Garber et al. (2020) up to a factor $1/\\lambda^2$\n\n3. In Theorem 1 (page 8) they improved the results in Garber et al. (2020) up to a factor $1/\\lambda$\n\n4. As a corollary (page 9) of Theorems 1 and 2, they could obtain similar results for the case when $\\sum_{t=1}^{T} f_t$ is convex but not necessarily strongly convex. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Originality: They proposed a new notion of stability which yields to a novel approach for solving random order online convex optimization.\n\nQuality: 1. The theoretical claims are well supported. \n\n2. Authors mentioned Garber et al. (2020) assumed that each loss function has a Lipschitz Hessian, which I do not see this in that paper. I encourage the authors to discuss this.\n\n3. The quality of the paper is fairly high. Their novel approach and improvements were impressive to me. \n\nClarity: The article is well written. While the notations were complicated, the authors managed to state their results with clarity and least amount of errors. The technical parts are self-contained and easy to follow. The authors provide an adequate literature review. \n\nI have some questions/ comments/ suggestions, which I encourage the authors to discuss or modify:\n\nQuestions: \n\n1. line 499: In Lemma 9, why you did not consider conditional probability and expectation for items (i) and (ii)? \n2. In Lemma 9, why item (i) holds for $\\delta$? Since in Lemma 3, it is valid for the conditional probablity.\n3. line 507: why $\\delta' < \\delta$?\n4. line 510: by the definition of $\\tilde{\\mu}$, how can you show $\\alpha = \\tilde{\\mu}/(1-\\delta')$? \n5. line 510: under this line and in the equation, according to question 4 how do you manage to obtain the third equality?\n\nComments/ suggestions:\n\n1. line 67: $\\mathcal{O}$ notation hides additive $\\beta$ and $D$, but not $G$.\n2. line 357: algorithms ----> Algorithms\n3. line 469: under this line and in the equation, the term $\\ell_S$ should be $\\ell$.\n4. line 473: under this line and in the equation, the term $A(S, \\zeta)$ should be $A(S)$, according to the definition in lines 461 and 462. \n5. line 480: in the last equality it would be nice if authors provided a short explanation about why the exchange of the integral and derivative is possible.\n6. line 510: by the definition of $\\tilde{\\mu}$,  $\\alpha \\geq \\tilde{\\mu}/(1-\\delta')$. By this, in the equation below the third equality should be inequality.\n7. line 588: second inequality should be $\\eta_{t_0}$, instead of $\\eta_1$.\n\n\nSignificance: With a different method they could significantly improve the results in Garber et al. (2020). I like their idea to use stability properties and their novel definition of stability was quite nice. I couldn't understand some parts I mentioned in clarity section and outlined them as Questions. I'm looking forward to their discussion about these questions.\n\nI would like to thank the authors for their response. The authors addressed my concerns in the rebuttal. After reading other reviews and the authors' feedback, my assessment of the paper remains unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discuss the limitations of their work. I also pointed out some, along with suggestions to improve the paper in the Main Review section.\n\nSince the paper is quite technical, I except no direct social impact at this point.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "iInSsHq5KNo", "reviewer": "Reviewer_4xgq", "summary": "In this paper the authors tackle the problem of online optimization with functions (picked by an adversary) arriving uniformly at random. Moreover, instead of assuming each function is (strongly) convex individually, they assume only that the sum of these functions is (strongly) convex, as recently proposed in previous work. Their main results are two algorithms for the random order model with strongly convex cumulative loss function, one of them attaining regret matching the assymptotics of the traditional adversarial case and the second only paying an extra $1/\\lambda$ factor (both up to lower-order terms) but with a smaller memory footprint. As a corollary they obtain two algorithms for the plain convex case with regret bounds on the order of $\\tilde{O}(\\sqrt{T})$ and  $\\tilde{O}(T^{2/3})$, respectively. To obtain these results they extend the connection between generalization and stability to the \"out-of-sample\"/sampling without replacement case, which may be interesting by itself.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "# Strengths\n- Clear (and significant) contribution to the field, with simple algorithms, an interesting analysis, and with bounds matching the ones of the adversarial case;\n- Although dense, the paper is clear and well-written;\n- The technique used is by itself interesting and may be of great interest for researchers in related fields.\n\n# Weaknesses\n- The lower-bound that justifies optimality does not assume (at least explicitly) smoothness of the functions. Maybe discussing a bit how smoothness does not affect (or how it does affect) the lower-bound would be helpful;\n- (Minor problem) some comments before some claims/result statements would ease the task of parsing the results;\n\n# Detailed comments\n\nThe results of the paper are very relevant with clear improvements on previous results, the techniques are elegant, and the algorithms are surprisingly simple (the last one in particular is so simple it looks wasteful, although the analysis and discussion make it clear why doing nothing near the end of the game may be useful). That is why I consider this paper to be very strong and a clear accept.\n\nThe point I was more confused with was the claim of optimality of the regret bounds for the strongly convex case. In particular, the lower-bound from Hazan and Kale (2011) does not explicitly assume smoothness of the functions. I didn't have the time to check the details on their lower-bound, but I believe this shouldn't be a problem. Yet, I think a discussion regarding this would be interesting.\n\nFinally, this paper is very dense, so using some of the extra-space in the camera-ready version to ease readability would be very helpful.  I have only a couple of suggestions, but you should use your better judgement to improve the readability in the way you think would be best.\n\n- Do the functions need to be 2-times differentiable? Assumption 3 makes it seem like it, but I've not seen the hessian being used explicitly anywhere (even in the appendix). I may have missed some use of it in some proof in the appendix, but I think you should make it clear whether the functions are doubly differentiable or not;\n- Typo on line 170 (relvant);\n- The notation for filtrations is a bit messy. Filtration is the ordered set of $\\sigma$-algebras, not a single $\\sigma$-algebra as you make it sound at some points. Defining a $\\sigma$-algebra as a sequence of random variables is weird, so maybe explicitly show that it is the $\\sigma$-algebra generated by these random variables would be better (that is, $\\mathcal{F}_t = \\sigma(z_1, \\dotsc, z_t)$ instead of $\\mathcal{F}_t = (z_1, \\dotsc, z_t)$ ). This would be explicitly useful when you have to differentiate between the set of random variables and the $\\sigma$-algebra;\n- A brief discussion before or after Lemma 3 of what is the role of $i$. At some point we realize it is the point that is certainly going to change in the dataset, but since it doesn't appear very explicitly in the results of the lemma, a discussion of what is the role of this $i$ would be helpful;\n- Reiterate either in sec 1.1 or right before the statement of the logarithmic regret result why your regret bound is asymptotically optimal. You mention this on  sec 1.3, but this is an important point worth repeating and going into details about (I was briefly confused whether the lower-bounded cited worked for this setting, but the authors do mention that it holds even for i.i.d. funcionts.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "eAOb7Ar8xVv", "reviewer": "Reviewer_ssvj", "summary": "The paper studies the problem of random order online convex optimization introduced previously by Garber et. al in 2020. Random order online convex optimization is a variant of standard online convex optimization where the loss functions may be chosen by an adversary (and do not even need to be individually convex), but the order in which they arrive is uniformly random.  This modification allows one to obtain efficient algorithms with stronger guarantees than for true worst-case analysis.  \n\nThis paper improves upon the guarantees obtained by Garber et. al, getting nearly optimal rates in the general setting that essentially match offline/stochastic rates.  They remove a factor of $d$ and a factor of $1/\\lambda^2$ (where $\\lambda$ is the strong convexity parameter) from the regret guarantee.  However, their optimal algorithm requires remembering all previous observations (so $O(dT)$ memory).  Thus, the authors also give an efficient algorithm that requires only $O(d)$ memory but sacrifices a $1/\\lambda$ factor in the regret guarantee (which is still better than the result in Garber et. al).   Roughly, the authors draw a parallel to stochastic online convex optimization.  The difference in the random order model is that the observations are not  independent but are instead sampled from a set \\textit{without replacement}.  However, the authors are able to modify  techniques from the stochastic case to this without replacement setting.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper is generally well-written and easy to understand.  The proofs seem correct although I did not check all of them carefully.  I think the overall result is ok.   However,  the paper does fall a bit short in that it does not quite close the random order OCO problem.  In particular, the main question seems to be whether there is a linear memory and runtime algorithm that matches the offline rate of $\\log T/\\lambda$.  Also, while there are some  nontrivial ideas, I found them a bit unsatisfying and not particularly novel or insightful.  The first algorithm just remembers all previous gradients in order to be able to generate an unbiased estimator of the gradient at each step.\n\n\nQuestions for the Authors:\nBoth of the algorithms are modifications to online gradient descent.  Do the authors believe that vanilla online gradient descent does not achieve $\\log T/\\lambda$ or are the modifications more for ease of analysis?\n\nRandom order OCO feels quite similar to the stochastic model.  Do the authors have any concrete examples where the random order model would be appropriate but the stochastic model does not suffice? \n\nAfter Author Response: Thanks for the clarifications!  My opinion remains that this paper is a solid, but not quite spectacular contribution.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0QZ-H87rlVv", "reviewer": "Reviewer_zUYG", "summary": "The authors study a variant of OCO introduced by Garber, Korcia, and Levy in which the costs are adversarial but are revealed to the online learner in a uniformly random order. The authors propose a new gradient-based algorithm for this model and claim that the regret incurred by their algorithm has a strict improvment on the problem parameters compared to that of Garber et al. Specifically, the regret of the new algorithm does not depend on the ambient dimension $d$ at all and has improved dependence on the strong convexity parameter $\\lambda$.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper studies an interesting problem and is well-written.  The main two contributions are 1) the paper obtains the optimal minimax regret rate in random order online optimization, significantly improving on the work of Garber et al, and 2), the paper introduces a new stability analysis of gradient descent, which will almost certainly be of broader interest to the learning theory community. The connection between regret minimization and generalization theory is very cool and I am sure will be the focus of much future work.\n\n\nVerdict: The results and proof technique presented in this paper are interesting and novel. After reading the other reviewer's comments and the author responses, it is clear that I misunderstood the results of this paper in my initial review. I am increasing my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problem here.", "review_text": "", "extra_scores": {"ethical_concerns": "No problem here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper eventually received uniformly positive evaluation, with two of the reviewers rating it to be within top 50% of accepted papers.

There is clear and significant contribution to the random-order Online Convex Optimization, with the results improving upon previously known by Garber (2020), and getting nearly optimal rates in the general setting.

Decision: Accept (Oral)