Optimal Rates for Random Order Online Optimization
Year: 2022

Abstract:
We study online convex optimization in the random order model, recently proposed by Garber et al. [8], 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. [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 to those studied in the with-replacement i.i.d. setting, as well as on a refined average stability analysis of stochastic gradient descent.

text: We study online convex optimization in the random order model, recently proposed by Garber et al. [8], 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. [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 to those studied in the with-replacement i.i.d. setting, as well as on a refined average stability analysis of stochastic gradient descent.

heading: 1 Introduction
text: Online convex optimization [25, 12] studies the iterative process of decision making as data arrives in an online fashion. The model posits a game of ) rounds, where in each round the learner chooses a decision FC from a convex set , ⊆ ℝ3 , after which she observes a loss function 5C : , → ℝ, and incurs loss 5C (FC ). The learner’s objective is to minimize her regret, defined as her cumulative loss minus that of the best decision in hindsight F∗ = arg minF ∈, ∑) C=1 5C (F). In the prototypical setting, the individual loss functions are assumed to be convex and adversarially chosen by an opponent—commonly known as nature or the adversary—who has knowledge of the learner’s algorithm. While this setup is fundamental enough to accommodate a 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—a property the authors refer to as 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)) regret in expectation. However, as it turns out, in the fully adversarial model the cumulative strong convexity assumption is too weak: Garber et al. [8] show that in this case there is a linear regret lower bound. Consequently, they propose the random order model, where ) losses are 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 on 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 $ ((3 2/λ3) log)) w.h.p. for -Lipschitz λ-cumulative-strongly convex losses. It is informative to compare the random order model with the i.i.d. stochastic case, where on every round a new loss is sampled uniformly and independently from the set of losses, that is, with-replacement. By contrast, the random order model specifies that on every round a new loss is sampled uniformly without-replacement, an in particular not independently. Concretely, let L be an arbitrary set of ) smooth and Lipschitz continuous loss functions. Set (F) B 1
)
∑ 5 ∈L 5 (F),
and assume is λ-strongly-convex over, . The learner’s goal is to minimize her regret on the loss sequence 51, . . . , 5) obtained from a uniformly random ordering of L. As noted previously, if the losses 5C were drawn i.i.d., SGD obtains the optimal $ (log)) regret even though the losses are not individually convex. In a nutshell, when losses are i.i.d., the gradients used in the SGD update are 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 51, . . . , 5C−1, the next loss is uniform over the complement L \ { 51, . . . , 5C−1}, and thus ∇ 5C (FC ) is 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 a discretization argument necessary to ensure convergence over the entire domain. Here we choose a 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.

heading: 1.1 Our results
text: We present and analyze two algorithms for random order online optimization, the first of which obtains the optimal regret up to additive factors. Let 51, . . . , 5) be a random order sequence of -Lipschitz, β-smooth losses, where 5C : , → ℝ for all C ≤ ) . Assume the domain, ⊂ ℝ3 is convex, and has diameter bounded by . Further, assume the average loss 1
)
∑) C=1 5C is λ-strongly convex. We prove;
Theorem (informal). There exists an algorithm (Algorithm 1) for random order online optimization that obtains regret of $ ( ( 2/λ) log) ) in expectation.
Although the above result matches the optimal result for the individually strongly convex setting (up to additive factors), Algorithm 1 requires memory linear in ) . This disadvantage motivates another algorithm, which trades off an extra factor of κ = β/λ in the regret for lower memory requirements.
Theorem (informal). There exists an algorithm (Algorithm 2) for random order online optimization that requires memory linear in 3, and obtains regret of $ ( (β 2/λ2) log) ) in expectation.
Big-$ notation in both theorems hides additive factors polynomial in problem parameters β, and (but does not hide multiplicative factors in these parameters). By comparison, Garber et al. [8] obtain a regret bound of$ ((3 2/λ3) log)) w.h.p. for this setting. Both of our algorithms completely remove the dimension factor 3, 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 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 $̃ ( √ )), matching up to logarithmic and additive factors the optimal rate for the individually convex setting. Similarly, the second theorem implies a $̃ ()2/3) regret algorithm which is also memory efficient for the convex case. Notably, a similar reduction applied to the results of Garber et al. [8] would yield a regret bound of $̃ (3)3/4). This highlights the significance of our improvement to the dependence on λ. Finally, we note it remains an open question to determine whether vanilla without-replacement SGD achieves optimal regret in the random-order model (our results leave a multiplicative gap of order 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 $ (log)/λ) regret bound (up to logarithmic terms).

heading: 1.2 Overview of techniques
text: Our approach builds on 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 to a suitable notion of algorithmic stability, mimicking in a sense a well known argument previously employed in the context of i.i.d. sampled training sets [3, 21]. 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 in practice is uniform stability, where sensitivity is measured w.r.t. the worst case small change in the training dataset; max(⊆Z(<) ‖ 5 (A(() − 5 (A((′)))‖. Our key insight is that while we 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; E(∼Z(<) ‖ 5 (A(()) − 5 (A((′))‖ ≤ ²(<). In particular, we prove the gradient update is contractive in expectation; E ‖G−η∇ 5 (G) − (H−η∇ 5 (H))‖ E ‖G− H‖ under the cumulative strong convexity assumption. In turn, this yields a stability result which implies regret that scales with 1/C for the early rounds up to C ≈ )/κ, where κ 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.i.d. uniform samples from a random order distribution, effectively ensuring unbiased gradient estimates throughout all ) rounds, and consequently optimal regret up to additive factors. Finally, our approach allows us to develop an analysis framework that naturally accommodates SGD based algorithms in the random order model, and in a broader sense establish stability of SGD in a new, relatively general setting.

heading: 1.3 Related work
text: Random-Order Online Optimization was proposed in the recent work of [8] (where it is referred to as ROOCO), who establish an $ ((3 2/λ3) log)) regret upper bound for -Lipschitz λ-cumulativestrongly convex losses. In the classical OCO setup [25, 12], under the assumption the losses are λ-strongly convex individually, it is well known the minimax regret scales as Θ(( 2/λ) log)), 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 defined 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 [11] 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 a similar approach to gain further insight into stability and generalization properties of SGD, e.g., [15, 7, 2]. A related line of work [9, 22, 16, 20, 18] studies SGD without-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 is 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 a single epoch, albeit only for individually convex loss functions. Recently, a number of papers study SGD without-replacement and attempt to relax the convexity assumption [10, 17, 1], but the bounds they obtain are under conditions inapplicable for our setting.
1The lower bound given in Hazan and Kale [13] uses quadratic (hence, smooth) losses, and is easily extensible to without-replacement sampling, and therefore applies in our setting.
Specifically, they impose a requirement that the number of epochs passes a certain threshold strictly larger than one. Moreover, state-of-the-art bounds achieved by [1] are suboptimal w.r.t ours even had we ignored the epoch requirement.

heading: 2 Setup: Random-Order Online Optimization
text: In this section, we 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 ) different datapoints, and denote by , ⊆ ℝ3 a closed convex set with diameter bounded by B maxG,H∈, ‖G − H‖. In addition, we let Π(G) B Π, (G) B arg minF ∈, ‖G − F‖2 denote the orthogonal projection onto, . We consider a loss function 5 : , × / → ℝ, and denote the average (also expected / population) loss by (F) B 1
)
∑ I∈/ 5 (F; I). We make the following assumptions;
Assumption 1 (Individual Lipschitz Continuity). For all I ∈ / , 5 ( · ; I) is -Lipschitz; namely ‖∇ 5 (F; I)‖ ≤ for all F ∈ , . Assumption 2 (Individual smoothness). For all I ∈ / , 5 ( · ; I) is β-smooth; namely ‖∇ 5 (G; I) − ∇ 5 (H; I)‖ ≤ β‖G − H‖ for all G, H ∈ , . Assumption 3 (Cumulative strong convexity). is λ-strongly convex; namely (H) ≥ (G) + ∇ (G)T (H − G) + λ2 ‖H − G‖ 2 for all G, H ∈ , .
In addition, we define the condition number of by κ B β/λ. We will be primarily interested in the random sequence of losses 5 ( · ; IC ) obtained from uniformly random orderings of / . Let I1, . . . , I< ∼ Z(<) denote a random sequence of < datapoints, where IC = ζσC ∈ / and σ : [)] → [)] is a uniformly random permutation. Equivalently, Z(<) may be also considered as the distribution of < datapoints sampled sequentially without-replacement from / . Omitting the number of samples parameter and writing I ∼ Z denotes a uniformly random sample of a single datapoint from / . In addition, if ( = (I1, . . . , I<) is a sequence of datapoints, I ∼ Z \ ( denotes a uniformly random sample of a single datapoint from / \ (. In sake of conciseness, we write (, Ĩ ∼ Z(<, 1) to denote a sample of a sequence ( ∼ Z(<), followed by a sample from the complement Ĩ ∼ Z\ (. We writeF< = σ(I1, . . . , I<) to denote the filtration given by the sequence of σ-algebras generated by the random variables (I1, . . . , I<). This, of course, is equivalent to sampling I1, . . . I<+1 ∼ Z(< + 1), and then setting ( = (I1, . . . , I<) and Ĩ = I<+1. Given a random order sequence I1, . . . , I) ∼ Z()), we consider the problem of minimizing the expected regret with an online algorithm. We denote the minimizer of the population loss by F∗ B arg minF ∈, (F), and let FC denote the iterates produced by an online algorithm A. The expected regret of A on Z()) is defined as;
R) B E [ )∑ C=1 5 (FC ; IC ) − 5 (F∗; IC ) ] ,
where the expectation is over the random order sequence and any randomness potentially introduced by A. Finally, when a sequence of realized datapoints I1, . . . , I< is clear from context, we let < (F) B 1< ∑< C=1 5 (F; IC ) denote their empirical average loss.

heading: 3 Stability and Generalization Without Replacement
text: 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 ( = (I1, . . . , I<) to make the ordering explicit in our notation. When such a training set is in context along with another datapoint Ĩ8 , we define ( (8) B (I1, . . . , I8−1, Ĩ8 , I8+1, . . . , I<) to be the new training set formed by taking ( and swapping the 8’th datapoint I8 with Ĩ8 . Finally, we say A is a learning algorithm if it maps training sets of any length to a decision; A : /∗ → , .

heading: 3.1 Recap: Stability and generalization in the i.i.d. setting
text: In this section we recall the relevant definitions previously studied in the i.i.d. setting. Here, we assume the training set ( = (I1, . . . , I<) ∼ D< is an i.i.d. sample of < datapoints from some predefined distribution D over elements of / .
Definition (on-average generalization; [21, 3]). We say a learning algorithmA on-average-generalizes with rate ²gen (<) if for all <;
| E(∼D< [ < (A(()) − (A(())] | ≤ ²gen (<).
The definition of stability that follows relates a small change in the training set ( → ( (8) to the change in the learning algorithm’s performance. Here, as one would expect, the swapped datapoint Ĩ8 ∼D is sampled independently from the original training set sample (. Definition (average-RO stability; [21, 3]). We say a learning algorithm A is average-replace-one stable with rate ²stab (<) if for all <; 1< <∑
8=1 E(∼D< , Ĩ8∼D [ 5 (A((); Ĩ8) − 5 (A(( (8) ; Ĩ8)] ≤ ²stab (<). With the above definitions, it is well known stability and generalization are in fact equivalent (e.g., [21]).

heading: 3.2 Stability and generalization without replacement
text: In this section we discuss the analogous notions suitable for sampling without-replacement. We adopt the term out-of-sample (oos) to distinguish the without-replacement setting, and say A on-average-generalize-oos with rate ²gen (<) if E(,Ĩ∼Z(<,1) [ 5 (A((); Ĩ) − < (A(())] ≤ ²gen (<). (1) Note that here, generalization is measured w.r.t. a datapoint drawn out-of-sample, and in particular not independently of (. The situation is similar for the notion of stability; while in the i.i.d. case the “non-coupled” index 8 in ( (8) hosts a different datapoint sampled independently, here this datapoint is sampled from the complement / \ (. The analogous definition for stability without-replacement says a learning algorithm A is average-replace-one-oos stable with rate ²stab if 1< <∑
8=1 E(,Ĩ8∼Z(<,1) [ 5 (A((); Ĩ8) − 5 (A(( (8) ); Ĩ8)] ≤ ²stab (<). (2) However, it will be more convenient in our case to work with a 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 : /∗ ×X→ , , where ξ ∈ X denotes the internal random seed used byA. For convenience, we slightly overload notation and let ξ ∼ X denote the distribution over A’s random seeds. Definition 1 (on-average-oos stability). A learning algorithmA is on-average-oos stable with rate ²stab (<) on random order distribution Z if
max 8≤<
E(,Ĩ8∼Z(<,1) ,ξ∼X [ ‖A((; ξ) −A(( (8) ; ξ)‖ ] ≤ ²stab (<).
We wish to draw the reader’s attention to two important aspects of 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 in the definition relates to the index of the swapped sample, and not to the training sets (, ( (8) . Second, the same random seed ξ is fed to A on both training sets, that is, we measure the expected distance between outputs subject to a maximal coupling of the algorithm’s randomness. When we discuss an online algorithm A and a random order sequence I1, . . . , I) ∼ Z()) is in context, we denote by I1:< = (I1, . . . , I<) the prefix of length <. In addition, if F<+1 = A(I1:<; ξ), we denote the coupled iterate by
F (8) <+1 B A(I (8) 1:<; ξ) = A(I1, . . . , I8−1, Ĩ8 , I8+1, . . . , I<; ξ), where Ĩ8 = I<+1. (3)
With this notation, ifA satisfies Definition 1 with rate ²(<), we have E ‖F<+1 − F (8)<+1‖ ≤ ²(<) for all 8 ≤ <. 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.
Lemma 1. AssumeA is on-avg-oos stable with rate ²(<), and let ` : , × / → ℝ be any !-Lipschitz loss function. Then; E(,Ĩ∼Z(<,1) ,I∼Z [`(A((); Ĩ) − `(A((); I)] ≤ !<
) ²(<).
IfA is an online algorithm producing iterates FC and I1, . . . , IC ∼ Z(C) is a random order sample, this immediately implies
E[ 5 (FC ; IC ) − (FC )] ≤ (C − 1)
) ²(C − 1).
We provide the proof in the full version of the paper [23].

heading: 3.3 Average stability of SGD
text: In this section, we develop the basic tools employed to establish that under appropriate conditions, SGD is algorithmically stable in the sense of Definition 1. Crucially, by considering average stability we are able to leverage strong convexity of the expected function and prove the desired result. For F ∈ , and ψ : , → ℝ, we denote by G(F;ψ, η) = Π(F − η∇ψ(F)) a projected gradient descent step from F. Our key lemma stated below and proved in the full version of the paper [23], says a gradient step on a random function ψ is contractive in expectation when ψ is strongly convex in expectation, and the step-size is sufficiently small. Lemma 2. Consider an arbitrary discrete distribution P of -Lipschitz and β-smooth functions ψ : , → ℝ such that Ψ(F) B Eψ(F) is µ-strongly-convex. Then for any G, H ∈ , , a gradient descent step with step-size η ≤ µ/β2 satisfies;
Eψ∼P ‖G(G;ψ, η) − G(H;ψ, η)‖ ≤ ( 1 − ηµ
2
) ‖G − H‖.
Notice that the above result dictates for the step-size to be lesser than µ/β2, which is roughly a factor of 1/κ smaller than needed to ensure (deterministic) contractivity under the assumption of individually strongly convex losses (see [11]). Lemma 2 serves as a building block to prove stability of SGD subject to relatively generic conditions, which we 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((;F1, <, {ηC }) the iterate F<+1 ∈ , produced by executing < projected gradient descent steps on a sequence of datapoints ( = (I1, . . . , Iτ), τ ≥ <, starting at the initial point F1 ∈ , , with step-sizes {ηC }. When any one of F1, < or {ηC } 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 the appropriate conditions, if we swap just a single training index 8 ≤ <, the sequence of gradient steps arrives at the same output up to distance $ (1/<). Lemma 3. Let 8 ≤ < ∈ ℕ, and ( = (I1, . . . , I<), (′ = (I′1, . . . , I ′ <) be two random datapoint sequences. Further, assume that for 0 < µ and 0 ≤ δ ≤ µ/2β, it holds that
(i) Pr(IC ≠ I′C | FC−1) ≤ δ for all C ≠ 8; (ii) E [ 5 (F; IC ) | FC−1 ] is µ-strongly convex as a function of FC−1-measurable F ∈ , ,
where FC−1 B σ(I1, I′1, . . . , IC−1, I ′ C−1). Then, for step-size schedule ηC = min
{ µ̃/β2, 2/µ̃C } with
µ̃ B µ − δβ, and any F1 ∈ , , we have;
E ‖GD((;F1, <) − GD((′;F1, <)‖ ≤ 4 µ̃< (1 + 4δ<).
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 (, (′. 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 a simple corollary of Lemma 3, establishing stability of SGD when the number of steps taken is sufficiently small.
Corollary 1. Let F1 ∈ , , and set ηC = min { λ/2β2, 4/λC } . Then the SGD update defined by FC+1 = Π(FC − ηC∇ 5 (FC ; IC )) is on-avg-oos stable with rate
²stab (<) ≤ 8 λ< ,
for all < ≤ )/2κ. Proof. Fix 8 ≤ <, let A denote the SGD algorithm, and consider a random order sequence I1, . . . , I) ∼ Z()). We have F<+1 = A(I1:<), and F (8)<+1 = A(I (8) 1:<) as defined in Eq. (3) (note that here though,A has no internal randomness). Next, we verify conditions for Lemma 3 are satisfied with the two sequences ( B I1:< and (′ B (I′1 . . . , I ′ <) B I (8) 1:<. Let FC−1 B σ(I1, I′1, . . . , IC−1, I ′ C−1), and by definition of ( and (
′, we have that IC = I′C for all C ≠ 8, hence clearly Pr(IC ≠ I′C | FC−1) = 0 for all C ≠ 8. For the second condition, let FC−1 denote the set of all datapoints observed prior to round C; FC−1 B {I ∈ / | I ∈ (I1, I′1, . . . , IC−1, I ′ C−1)}. This means FC−1 contains exactly {I1, . . . , IC−1}, and perhaps Ĩ8 depending on whether C > 8, hence : B |FC−1 | ∈ {C, C − 1}. Now, given FC−1, we have that IC is uniform over Z \ FC−1, therefore
E[ 5 (F; IC ) | FC−1] = 1 ) − : ∑
I∈/\FC−1
5 (F; I) = ) ) − :
( (F) − 1
) ∑ I∈FC−1 5 (F; I) ) .
By our smoothness assumption, 1 ) ∑ I∈FC−1 5 (F; I) is (:β/))-smooth, and in addition :β/) ≤ <β/) ≤ (λ/2β)β = λ/2. Therefore, by λ-strong convexity of we get that the last term in the above derivation is at least λ/2-strongly-convex (this follows from a standard argument, see Lemma 10). Therefore, by Lemma 3 with µ B λ/2, δ B 0 it now follows that
E ‖F<+1 − F (8)<+1‖ = E ‖GD(() − GD(( ′)‖ ≤ 8
λ< ,
which completes the proof.

heading: 4 SGD for Random Order Online Optimization
text: In this section, we present two algorithms for random order online optimization. Lemma 1 motivates us to derive SGD based algorithms that obtain low regret w.r.t. the population loss , and are algorithmically stable in the sense of Definition 1. Given a random order sequence I1, . . . , I) ∼ Z()), the SGD update with gradient estimates {6̂C } and step sizes {ηC } is given by
FC+1 ← Π(FC − ηC 6̂C ). It is not hard to show that the regret w.r.t. of SGD is directly related to the error terms introduced by using 6̂C in place of the true population loss gradients ∇ (FC ). This fact is made formal in the lemma below, which serves as a 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 4. Consider τ iterations of SGD with gradient estimates {6̂C } and step-size schedule ηC = min { µ̃/β2, 2/(µ̃C) } . We have that the following bound holds with probability one;
τ∑ C=1 (FC ) − (F∗) ≤ β2 2 2µ̃ + 2 µ̃ (1 + log τ) + τ∑ C=1 (∇ (FC ) − 6̂C )T (FC − F∗). (4)

heading: 4.1 Reservoir SGD
text: In light of Corollary 1, it is evident that a different strategy is necessary to achieve stability in late rounds of the online game. As a solution, Algorithm 1 presented here employs a sampling procedure reminiscent of reservoir sampling [24], which results in gradient estimates 6̂C that are conditionally unbiased estimates of ∇ (FC ) throughout all ) rounds. This ensures the conditionally expected function on 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 ) to the i.i.d. setting. Consequently, a regret bound will follow from a batch-to-online conversion supported by Lemma 1 and Lemma 3. Our first lemma given below, shows that the intermediate sequence of datapoints I′C generated in line 4 are i.i.d. uniformly distributed, which immediately implies that E 6̂C = ∇ (FC ).
Algorithm 1 ReservoirSGD 1: input: step-sizes η1, . . . , η) ∈ ℝ+, F1 ∈ , 2: for C = 1 to ) do 3: Play FC , Observe IC
4: Set 6̂C B ∇ 5 (FC ; I′C ), where I′C = { IC w.p. 1 − C−1) Unif (I1, . . . , IC−1) w.p. C−1) 5: FC+1 ← Π(FC − ηC 6̂C ) 6: end for
Lemma 5. The {I′C } intermediate sequence produced by Algorithm 1 in line 4 is uniform over / and i.i.d.; ∀I ∈ /; Pr(I′C = I) = Pr(I′C = I | I<C ) = 1) . Proof. Fix the first C − 1 sampled datapoints I1, . . . , IC−1 ∼ Z(C − 1). Then for all I ∈ {I1, . . . , IC−1},
Pr(I′C = I | I1:C−1) = C − 1 ) · 1 C − 1 = 1 ) .
In addition, since I1, . . . , IC ∼ Z(C), it follows that IC is uniform over / \ I1:C−1. (Note that as we are conditioning on I1:C−1, we have that / \ I1:C−1 is deterministic.) Hence, for all I ∈ / \ I1:C−1 we have
Pr(I′C = I | I1:C−1) = ) − C + 1 ) · 1 ) − C + 1 = 1 ) .
The above implies that Pr(I′C = I | I1:C−1) = 1/) for all I ∈ / . Finally, the by the law of total probability;
Pr(I′C = I) = EI1 ,...IC−1∼Z(C−1) [ Pr(I′C = I | I1:C−1) ] =
1 ) ,
as desired.
Next, we argue Algorithm 1 maintains average stability with the desired rate throughout all ) rounds. Lemma 6. Assume ) ≥ 2β/λ, and set µ̃ B λ − β/) . Then Algorithm 1 with step-size schedule ηC = min { µ̃/β2, 2/(µ̃C) } is on-avg-oos stable (Definition 1) with rate
²stab (<) ≤ 40 λ< .
Proof. Let 8 ≤ < ≤ ) , and recall the definition of the coupled iterate in Eq. (3). We have that
E ‖F<+1 − F (8)<+1‖ = E ‖GD(( ′) − GD((′′)‖,
where (′ = (I′1, . . . , I ′ <) and (′′ = (I′′1 , . . . , I ′′ <) denote the intermediate sequences (line 4) produced when running Algorithm 1 on I1:< and I (8)1:< respectively. Now, consider the indexes of datapoints selected by the sampling mechanism on line 4 which we denote by 9C , meaning 9C = ; when I′C = I; . Since the same random seed is used for each coupled iterate, we have that the indexes 9C from both execution paths are the same. Next, we will show (′, (′′ satisfy the conditions of Lemma 3. Indeed, denote by FC the filtration encapsulating all randomness (random order and algorithm) up to and including round C. Then by Lemma 5 and since I1:< and I (8)1:< differ only at index 8, we have for any C > 8; Pr(I′C ≠ I′′C | FC−1) = Pr( 9C = 8 | FC−1) = 1) . In addition, it trivially follows that Pr(I′C ≠ I′′C | FC−1) = 0 for all C < 8. Owed to our assumption on ) , we have 1/) ≤ λ/2β, and so the first condition is satisfied. For the second condition, note that again by Lemma 5, E[ 5 (F; I′C ) | FC−1] = (F) for any FC−1-measurable F ∈ , , which immediately implies λ-strong convexity of the conditionally expected function. By the above, we obtain that (′, (′′ follow a distribution satisfying conditions required by Lemma 3 with µ B λ, δ B 1/) , therefore,
E ‖GD((′;<) − GD((′′;<)‖ ≤ 4 (λ − (1/))β)<
( 1 + 4<
)
) ≤ 40
λ< ,
and we are done.
A regret bound for Algorithm 1 readily follows, as we have essentially established both convergence rate and stability of the algorithm. Below, we state and prove our main result concluding this section. Theorem 1. Running Algorithm 1 with step-size schedule ηC = min { µ̃/β2, 2/(µ̃C) } where µ̃ B λ − β/) , it is guaranteed that;
E [ )∑ C=1 5 (FC ; IC ) − 5 (F∗; IC ) ] ≤ 2 2 λ (1 + log)) + 40 2 + β2 2 + 2β λ
.
Proof. By Lemma 5, we have that for all C ≤ ) ,
E[∇ 5 (FC ; I′C ))T (FC − F∗)] = E[EC [∇ 5 (FC ; I′C )])T (FC − F∗)] = E[∇ (FC )T (FC − F∗)],
where EC [·] = E[ · | I1, I′1, . . . , IC−1, I ′ C−1] denotes the conditional expectation w.r.t. all rounds up to and not including C. This implies the gradient error terms on the RHS of Eq. (4) vanish. In addition, note we may assume ) ≥ 2β/λ, for otherwise it trivially follows that ∑) C=1 5 (FC ; IC ) − 5 (F∗; IC ) ≤
) ≤ 2β λ
. Hence δ B 1/) ≤ λ/2β, and by Lemma 4 we obtain the following bound on the regret w.r.t. the population loss ;
E [ )∑ C=1 (FC ) − (F∗) ] ≤ β 2 2 λ + 2 2 λ (1 + log)).
To establish online performance, observe that by Lemma 1 and Lemma 6 we have
E[ 5 (FC ; IC ) − (FC )] ≤ (C − 1)
) ²stab (C − 1) = (C − 1) ) 40 λ(C − 1) = 40 2 λ) .
Therefore,
E [ )∑ C=1 5 (FC ; IC ) − 5 (F∗; IC ) ] = )∑ C=1 E[ 5 (FC ; IC ) − (FC )] + E [ )∑ C=1 (FC ) − (F∗) ]
≤ 40 2
λ + β
2 2
λ + 2
2
λ (1 + log)),
and the result follows.

heading: 4.2 SGD without replacement
text: While Algorithm 1 obtains regret which is optimal up to additive factors, it is memory intensive due to the sampling procedure requiring the history of the entire loss sequence. This motivates Algorithm 2 which uses the random order gradients as they arrive, and sacrifices a factor of κ in the regret bound for lower memory requirements.
Algorithm 2 SGD-without-replacement 1: input: τ, ) ∈ ℕ, step-sizes η1, . . . , ητ ∈ ℝ+, F1 ∈ , 2: for C = 1 to τ do 3: Play FC , Observe IC 4: FC+1 ← Π(FC − ηC 6̂C ), where 6̂C B ∇ 5 (FC ; IC ) 5: end for 6: for C = τ + 1, . . . , ) : play FC ≡ F̄ B 1τ ∑τ 8=1 F8 .
With Corollary 1, we already know Algorithm 2 is stable with rate $ (1/<) for τ ≤ )/2κ, at least for all iterates excluding F̄. However, it is not clear a priori whether these iterates also obtain good convergence rate—to prove this we must control the gradient error terms on the RHS of Eq. (4). Evidently, with random order gradient estimates the behavior of these error terms is also related to stability in the same sense that the actual losses are. By Lemma 1 with `(F; I) B ∇ 5 (F; IC )T (F−F∗), 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 a step-size schedule ηC = min { λ/2β2, 4/λC } and τ = )/2κ, we have that the gradient error terms on the RHS of Eq. (4) are bounded, for all C ≤ τ, as
E[(∇ (FC ) − 6̂C )T (FC − F∗)] ≤ 8 ( + β )
λ) .
The proof of Lemma 7 is given by arguments following the above discussion, and is deferred to the full version of 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 a step-size schedule ηC = min { λ/2β2, 4/λC } and τ = )/2κ, it holds that
E [ )∑ C=1 5 (FC ; IC ) − 5 (F∗; IC ) ] = $ ( β 2 λ2 log) + β λ + β 3 2 λ2 ) .
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.

heading: 4.3 The convex case
text: Given Algorithms 1 and 2, we can derive as an immediate corollary regret bounds for the case where the loss function 5 is only assumed to be convex in expectation, but not strongly convex. This is achieved by adding L2 regularization; pick F0 ∈ , arbitrarily, and consider 5 α(F; I) B 5 (F; I) + α2 ‖F−F0‖
2. By transforming the gradient estimators 6̂C ← 6̂C + α(FC − F0) in both algorithms, we optimize for the regularized random order loss sequence 5 α(·; I1), . . . 5 α(·; I) ), and obtain regret bounds for suitable choices of α. Corollary 2. Assume the loss function 5 : , × / → ℝ is -Lipschitz and β-smooth for all I ∈ / individually (Assumption 1 and Assumption 2), and that 1
)
∑ I∈/ 5 (·; I) is convex over, . Then, we
have the following guarantees for running Algorithms 1 and 2 on the regularized loss sequence:
(i) for Algorithm 1 and α = 1/ √ ); E [∑) C=1 5 (FC ; IC ) − 5 (F∗; IC ) ] = $̃ ( √ )),
(ii) for Algorithm 2 and α = 1/)1/3; E [∑) C=1 5 (FC ; IC ) − 5 (F∗; IC ) ] = $̃ ()2/3) ,
where big-$̃ hides polynomial dependence on the problem parameters β, , , and logarithmic dependence on ) . Proof. To ease notational clutter denote 5C (F) B 5 (F; IC ) and 5 αC (F) B 5 α (F; IC ) = 5C (F) + α2 ‖F − F0‖2. Let α(F) B 1) ∑ I∈/ 5 α (F; I), then α (F) = (F) + α2 ‖F − F0‖ 2, which implies that α is α-strongly convex. Therefore,
E [ )∑ C=1 5 αC (FC ) − 5 αC (F∗) ] ≤ R) (α),
where R) (α) denotes the regret w.r.t. the regularized loss sequence 5 αC . In addition; )∑ C=1 5C (FC ) − 5C (F∗) = )∑ C=1 5C (FC ) − 5 αC (FC ) + )∑ C=1 5 αC (FC ) − 5 αC (F∗) + )∑ C=1 5 αC (F∗) − 5C (F∗)
= α
2 )∑ C=1 ‖FC − F0‖2 + )∑ C=1 5 αC (FC ) − 5 αC (F∗) + α 2 )∑ C=1 ‖F∗ − F0‖2
≤ )∑ C=1 5 αC (FC ) − 5 αC (F∗) + α 2)
≤ R) (α) + α 2). The result follows after substituting for the values of α specified in the statement of the theorem, and the regret bounds of Theorems 1 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/λ dependence allows for regularization that guarantees optimal (up to logarithmic factors) performance w.r.t. ) in the non-strongly convex setting.
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.

Review summaries:
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.  Assumptions: 1. $f_t$ is Lipschitz  2. $f_t$ is smooth 3. $\sum_{t=1}^{T} f_t$ is $\lambda$-strongly convex.  Approach: 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.   By 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.  Contributions: 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:  1. 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.  2. In Theorem 1 (page 8) they improved the results in Garber et al. (2020) up to a factor $1/\lambda^2$  3. In Theorem 1 (page 8) they improved the results in Garber et al. (2020) up to a factor $1/\lambda$  4. 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. 

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

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

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.