Online Lazy Gradient Descent is Universal on Strongly Convex Domains
Year: 2022

Abstract:
We study Online Lazy Gradient Descent for optimisation on a strongly convex domain. The algorithm is known to achieve O( √ N) regret against adversarial opponents; here we show it is universal in the sense that it also achieves O(logN) expected regret against i.i.d opponents. This improves upon the more complex metaalgorithm of Huang et al [20] that only gets O( √ N logN) and O(logN) bounds. In addition we show that, unlike for the simplex, order bounds for pseudo-regret and expected regret are equivalent for strongly convex domains.

text: √ N) regret against adversarial
opponents; here we show it is universal in the sense that it also achieves O(logN) expected regret against i.i.d opponents. This improves upon the more complex metaalgorithm of Huang et al [20] that only gets O( √ N logN) and O(logN) bounds. In addition we show that, unlike for the simplex, order bounds for pseudo-regret and expected regret are equivalent for strongly convex domains.

heading: 1 Introduction
text: Online linear optimisation is a repeated game with one opponent. On turn n we know the cost vectors a1, a2, . . . , an−1 ∈ Rd and select an action xn from the domain X ⊂ Rd. The opponent observes xn and chooses the next cost vector an ∈ Rd and we pay cost an · xn. Our goal is to select actions to make the regret ∑N i=1 ai · (xi − x∗) small for x∗ ∈ argmin{ ∑N i=1 ai · x : x ∈ X}.
If the cost vectors are selected by an adversarial opponent then a1, a2, . . . , an−1 give no information about an and selecting a good action seems like an impossible task. Despite this, there are algorithms that get O( √ N) regret against such opponents. The loss in performance against x∗ is O(1/ √ N) per turn which vanishes as N → ∞. The central algorithms in the field are Hedge [18, 34]; Prod [9]; and (sub)Gradient Descent, which has Greedy [41] and Lazy [34] variants. All three algorithms get O( √ N) regret. The first two are specialised to X the simplex. The latter works for any compact convex domain. The bulk of online optimisation literature is refinements of the central algorithms.
In many cases however the cost vectors are non adversarial. For example they might be determined by fluctuations in traffic, the weather or the stock market over a short period of time. The standard model of easy opponents is cost vectors drawn independently from some fixed distribution. In the easy setting the history a1, . . . , an provides information about the next cost vector. Indeed ãn+1 = a1+...+ann is an increasingly reliable sequence of estimates for a = E[an+1] and it seems reasonable to play xn+1 to minimise ãn+1 · x. This is called Follow-the-Leader (FTL). For example if X is the simplex FTL gives pseudo-regret E [ ∑N i=1 a·(xi−y∗)] ≤ O(1) for y∗∈argmin{a·x : x∈X}. Note this is
weaker than bounding the expected regret E [∑N i=1ai · (xi − x∗) ] . On the other hand FTL gives no guarantee against adversarial opponents, and we might not know in advance whether the opponent is i.i.d or adversarial. Hence we would like an algorithm that is universal in that it always gets O( √ N) regret but specialises to a much stronger bound against i.i.d opponents.
Recently Huang et al [20] solved this problem for smooth, strongly convex domains. For these domains they showed FTL gives O(logN) regret if ‖ ∑n i=1 ai‖ grows linearly.1 The result was generalised to nonsmooth domains by [22, 26]. Huang et al then combine FTL with the (A,B)-Prod meta-algorithm of [31] to ensure O( √ N logN) regret against adversarial opponents. In this work
1 Without smoothness they show the growth condition occurs with high probability against i.i.d opponents.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Algorithm 1: Online Lazy Gradient Descent Data: Cost vectors a1, a2, . . . ∈ Rd. Parameter η > 0. Domain X ⊂ Rd.
1 for n = 0, 1, . . . do 2 xn+1 =ΠX ( − η√
n
∑n i=1 ai ) 3 Receive an+1 and pay cost an+1 · xn+1
we improve and extend their results. In particular we show the meta-algorithm is unnecessary as the much simpler Online Lazy Gradient Descent already achieves O( √ N) and O(logN) bounds.
Terminology and Notation
Throughout ‖ · ‖ is the Euclidean norm. Given a vector subspace V ⊂ Rd and linear operator A : V → V write the operator norm as ‖A‖ = max{‖Av‖ : v ∈ V, ‖v‖ = 1}. It is known (see [10] Theorems 4.1 and 4.2) that ‖A‖ = maxj √ |λj | for λj the eigenvalues of ATA. Moreover if A is symmetric we have ‖A‖ = maxj |µj | for µj the eigenvalues of A. The set Z ⊂ Rd is called λ-strongly convex to mean for each x, y ∈ Z and α ∈ [0, 1] the ballB(αx+(1−α)y, r) is contained in Z for r = λ2α(1− α)‖x− y‖ 2. The pseudo-regret P[RN ] and expected regret E[RN ] are defined:
P[RN ] = E [ N∑ i=1 a·xi −min x∈X N∑ i=1 a·x ] E[RN ] = E [ N∑ i=1 ai ·xi −min x∈X N∑ i=1 ai ·x ] (1)
The Jensen Inequality implies P[RN ] ≤ E[RN ]. We write ΠX for the Euclidean projection onto the domain X . The Online Lazy Subgradient algorithm is given as Algorithm 1. Note this is different from the so-called Greedy Subgradient algorithm with starting point x1 = 0 and recursive update xn+1 =ΠX(xn−ηan/ √ n). Section 5 Figure 2(b) suggests Greedy Subgradient is not universal.
Summary of Contributions
Throughout we make the following assumptions on the domain and cost vectors. Both assumptions are nontrivial. For example Assumption 1 holds on the Euclidean and `p balls for p∈(1, 2] but not for the simplex or polytopes. Assumption 2 on the cost vectors is a typical model of an easy opponent and fails if the opponent is intelligent and adapts to our past moves. Assumption 1. The domain X⊂Rd is compact, m-strongly convex and contains the origin. Write D = max{‖x‖ :x, y∈X}. The boundaryM = ∂X is a (d−1)-dimensional C2 manifold. Namely each z∈M has a neighborhood U in Rd and C2 function F :U→R with nonzero gradient such that M∩U={x ∈ U : F (x)=0}. Such a function is called a coordinate patch at z.
Henceforth write N(x) for the outwards unit normal at x∈M. To represent N :M→Rd locally we can choose a coordinate patch F :U→R at x∗ and write∇N= ∇F‖∇F‖ . Since F is C
2 the matrix ∇N of partial derivatives exists. Assumption 2. The cost vectors a1, a2, . . . are i.i.d with expectation E[an] = a. For all n we have ‖an‖ ≤ L and ‖an−a‖ ≤ R and E‖an−a‖ ≤ δ. Let x∗ ∈ argmin{a ·x : x ∈ X} be the expected minimiser. The domain X being strongly convex implies x∗ is unique.
Our main result is Theorem 3 which says Online Lazy Gradient Descent achieves O ( L2 m‖a‖ logN ) expected-regret under Assumptions 1 and 2. This bound is essentially tight by [20] Theorem 9. The improved behaviour against i.i.d opponents is remarkable since the algorithm was designed with the adversarial case in mind, and predates the recent interest in universal algorithms. Our second contribution is Theorem 2 which states the gap between expected regret and pseudo-regret is O ( L2 m‖a‖ ) . Theorem 2 is of independent interest since it fails if the domain is the simplex.
From a technical standpoint, our Gradient Descent analysis goes beyond that of [20, 22, 26] for FTL. Their central idea is that the normal vector toM at xn ∈ argmin{(a1+ . . .+an−1) · x : x ∈X} points along An−1 =−a1+...+an−1n . Using ‖An−An−1‖=O(1/n) and how strong convexity says the unit normal changes quickly as we vary the basepoint, they prove ‖Θn−Θn+1‖=O(1/n) for the normal vectors Θn,Θn+1 at xn, xn+1. Summing the resulting series gives a logarithmic regret
bound. Unfortunately this method is insufficient to analyse Gradient Descent instead of FTL as it only gives ‖Θn−Θn+1‖=O(1/ √ n). and the resulting series give only an O( √ N) bound. Thus we
follow a new approach where we prove a high probability bound ‖N(xn)−N(x∗)‖ = O(1/ √ n) for the unit normals. For comparison existing works do not mention the expected minimiser x∗ at all. Then we use strong convexity to see the boundary surface locally looks like a quadratic with axis pointing along −a. Hence ‖xn−x∗‖ = O(1/ √ n) and only O(1/n) of the displacement is in the a-direction; and the larger orthogonal component does not contribute to pseudo-regret. Summing the series gives an O(logN) bound for pseudo-regret. To convert this into a bound for expected regret we use our Theorem 2 which says the gap between expected regret and pseudo-regret is finite.
Our differential geometry methods are more nuanced than existing works. Existing works consider only the magnitude ‖xn − xn+1‖ but we consider both the magnitude and direction of xn − x∗. The relevant object is∇N(z)v in Lemmas 1-5 and Proposition 1 which captures the rate of change of the unit normal as we perturb the basepoint in the v-direction.

heading: 2 Related Work
text: The first strand of related work is universal algorithms. That is to say online algorithms with Õ( √ N) regret against adversarial opponents that specialise to get stronger bounds against i.i.d opponents. The original research focus was on the simplex and bandit feedback [4, 8, 32, 33, 37, 40]. In the full information setting the FlipFlop algorithm [11] interpolates between FTL and Hedge on the simplex to get O(1) and O( √ N logN) regret against i.i.d and adversarial opponents respectively. The (A,B)-Prod meta-algorithm [31] does something similar in much greater generality. Another result comes from [16]. They design a variant of the Prod algorithm [9] with different learning rates for each arm. As a corollary they get O(1) expected regret against i.i.d opponents with a unique best arm. Apart from [31] all the above algorithms apply only to the simplex.
However recent results suggest such complicated algorithms are unnecessary. In the full information setting it was recently proved that two of the central algorithms do much better against i.i.d opponents. Hedge gets O(log(d)L2∞/∆) pseudo-regret on the simplex [27]; and Online Lazy Gradient Descent gets O(L22/∆) pseudo-regret on polytopes
2 [1, 2].The latter is notable since it works for domains other than the simplex. Here d is the dimension; ∆ the suboptimality gap; and we assume ‖an‖ ≤ L2 and ‖an‖∞ ≤ L∞ where appropriate. The above bounds are in addition to the O( √ N) regret bounds of Gradient Descent and Hedge (see [34] Chapter 2) against adversarial opponents.
The second strand of related work is the study of online algorithms on strongly convex domains. Typically these are unit balls with respect to some norm. For example [39] consider the `p unit ball with p ∈ (1, 2] in the full-information setting. Another setting of interest [5, 12, 19] is when predictions are available for the direction of the next cost vector. In the bandit setting [7] consider `p balls; [6] consider the Euclidean ball; and [30] consider general strongly convex sets. They allow infinitely many arms but require the cost vectors be stochastically generated. In the offline setting [17] show the Frank-Wolfe method has O(1/n2) convergence rates − and hence finite regret − when the domain is strongly convex. [23] prove similar results for more general so-called uniformly convex sets. Under additional conditions the older works [13, 14, 25] show an exponential convergence rate.

heading: 3 Bound for Pseudo-Regret
text: Here we show Online Lazy Gradient Descent gets O(logN) pseudo-regret against i.i.d cost vectors on a C2 strongly convex domain. This is in addition the O( √ N) regret bound for adversarial costs.
Theorem 1. Under Assumptions 1 and 2, Algorithm 1 with parameter η > 0 achieves pseudo-regret
P[RN ] ≤ 144
m‖a‖
(√ 8πDR
η + 4R2
) logN +O(1).
In particular for hyperparameter η = Θ(D/L) we have P[RN ] ≤ O ( L2 m‖a‖ logN ) .
By [34] Theorem 2.4 hyperparameter η=Θ(D/L) is optimal for both adversarial and i.i.d bounds. 2Huang et al [20] already proved an O(1) bound for polytopes with unique optimal vertex. However dependence on dimension and suboptimality gap is not obvious.
We begin with some geometric intuition for our proof strategy. To interpret Lemma 1 it is convenient to imagine the domain is translated to put z at the origin and the outward unit normal N(z) points along the d-th coordinate direction (henceforth called the height). Since N(z) has unit length, the left-hand-side of Lemma 1 is the height of the boundary at x. The lemma says the height changes quadratically with coefficient depending on the direction v as defined below.3
Definition 1. Given points x, y ∈ M a geodesic from x to y is a C2 path inM with endpoints x and y with ‖γ′(t)‖ = 1 for each t, and such that γ has minimal length among such paths. That length is called the geodesic distance d(x, y). The unit vector v ∈ Rd is called a direction from x to y to mean there is a geodesic γ : [0, d(x, y)]→M from x to y with γ′(0) = v.
In Lemma 6 we plug the expected minimiser z = x∗ into Lemma 1. The height then points along a and the left-hand-side of the bound becomes the pseudo-regret of x. We then (a) remove the dependence on direction and bound the coefficient by 1/m and (b) use strong convexity to convert the right-hand-side into the squared difference ‖N(x)−N(x∗)‖2. Finally we plug x = xn into Lemma 6 and use Lemma 7 to see ‖N(xn) − N(x∗)‖2 = O(1/n) with high probability. The idea is to write the unprojected action yn = − η√n ∑n i=1 ai as yn = −η √ na + η√
n
∑n i=1(a − ai). The first term points along − a ‖a‖ = N(x ∗) and has length Ω( √ n).
The second term is O(1) with high probability due to the i.i.d sum. Hence after normalisation the component of yn orthogonal to − a‖a‖ has size O(1/ √ n). Since the domain is bounded the
same holds if we instead normalise yn − w for any w ∈ X . In particular taking w = xn we get∥∥ yn−xn ‖yn−xn‖ − ( − a‖a‖ )∥∥ = O(1/√n). Since xn = ΠX(yn) we have yn−xn‖yn−xn‖ = N(xn). Since − a‖a‖ = N(x
∗) we get ‖N(xn)−N(x∗)‖2 = O(1/n) with high probability. Sum the series to get PN = O (∑N n=1 1 n ) = O(logN). Lemma 1. For each z∈M there exists a coordinate patch F : U → R such that for each x ∈ U ∩M and direction v from z to x we have
|N(z)(x− z)| ≤ |v T∇2F (z)v| ‖∇F (z)‖ d(x, z)2.
Lemma 1 is proved using Lemmas 2-5 and Proposition 1 which are in turn proved in Appendix II. The arguments there use only routine differential geometry, but we provide self-contained proofs, since the literature focuses on intrinsically defined surfaces, rather than surfaces embedded in Rd. Lemma 2. For each z ∈M and unit vector v tangent toM at z we have ‖∇N(z)v‖ ≥ m.
Lemma 3. For each coordinate patch F at z and unit tangent v toM at z we have v T∇2F (z)v ‖∇F (z)‖ ≥m.
Lemma 4 says the unit normal function has bounded second derivative, despite any complications caused by the function being only locally defined. Lemma 4. There exist constants M, r > 0 such that each z ∈ M has a coordinate patch F : B(z, r)→ R with ‖∇N(y)‖, ‖∇
2F (y)‖ ‖∇F (y)‖ ≤M for all y ∈ B(z, r).
Lemma 5. Let M be the constant from Lemma 4. For each geodesic γ : [0, d(x, y)]→M from x to y we have for d = d(x, y) and all t ≤ d the inequalities
(1) ‖γ′′(t)‖ ≤M (2) ‖γ(t)− γ(0)− tγ′(0)‖ ≤ M2 t 2 (3) ∣∣‖y − x‖ − d∣∣ ≤ M2 d2 Proposition 1. Each z ∈M has a neighborhood U in Rd such that for all x ∈ U ∩M and direction v from z to x we have
‖N(x)−N(z)‖ ≥ ‖∇N(z)v‖ 2 d(x, z)
Proof of Lemma 1. Let F,M, r be from Lemma 4. Since F is C2 Taylor’s theorem says there is a function ψ(t) defined on some neighborhood of the origin with limt→0 ψ(t) = 0 and
F (x) = F (z) +∇F (z)(x− z) + (x− z) T∇2F (z)(x− z)
2 + ψ(z − x)‖z − x‖2
3It is of course possible to define geodesics and directions using a non-Euclidean notion of distance. However in this paper we only consider Euclidean geodesics.
Hence there is r > 0 such that for all x ∈ B(z, r) we have |ψ(z − x)| ≤ m4 ‖∇F (z)‖ and so∥∥∥F (x)− F (z)−∇F (z)(x− z)− (x−z)T∇2F (z)(x−z)2 ∥∥∥ ≤ m4 ‖∇F (z)‖‖x− z‖2. Shrink r if necessary to ensure B(z, r) has geodesic diameter at most min{m/2M2, √ 2m/M3/2}. By assumption F (x) = F (z) = 0. Hence for d = d(x, z) the above gives∥∥∥∇F (z)(x− z)− (x−z)T∇2F (z)(x−z)2 ∥∥∥ ≤ m4 ‖∇F (z)‖‖x− z‖2 ≤ m4 ‖∇F (z)‖d2. Let v be a direction from z to x. For w = (x− z)− dv. The reverse triangle inequality gives∥∥∥ |∇F (z)(x− z)|− |(dv)T∇2F (z)(dv)|2 ∥∥∥≤ m4 ‖∇F (z)‖d2+|wT∇2F (z)(dv)|+ |wT∇2F (z)w|2 . (2) Lemma 5 says ‖w‖ ≤Md2/2 and Lemma 4 says ‖∇
2F (z)‖ ‖∇F (z)‖ ≤M . Hence we get
|wT∇2F (z)(dv)| ≤ ‖w‖‖∇2F (z)‖‖dv‖ ≤ M2 ‖∇2F (z)‖ ‖∇F (z)‖ ‖∇F (z)‖d 3
≤ M 2 2 ‖∇F (z)‖d 3 ≤ ‖∇F (z)‖4 md 2.
where the last inequality uses the assumption d ≤ m/2M2. Similarly d ≤ √
2m/M3/2 gives |wT∇2F (z)w| ≤ ‖∇F (z)‖2 md
2. Hence (2) becomes∥∥∥ |∇F (z)(x− z)| − |vT∇2F (z)v|2 d2∥∥∥ ≤ m4 ‖∇F (z)‖d2 + m4 ‖∇F (z)‖d2 = m2 ‖∇F (z)‖d2. and so |∇F (z)(x − z)| ≤ ( |vT∇2F (z)v|
2 + m 2 ‖∇F (z)‖
) d2. Since the unit normal is
N(z) = ∇F (z)‖∇F (z)‖ we can divide both sides to get N(z)(x− z)| ≤ 1 2 ( |vT∇2F (z)v| ‖∇F (z)‖ +m ) d2. Lemma 3 says m ≤ |v T∇2F (z)v| ‖∇F (z)‖ . This completes the proof.
Lemma 6. The minimiser x∗ has a neighborhood U in Rd such that each x ∈ U ∩M has
a · (x− x∗) ≤ 4‖a‖ m ‖N(x)−N(x∗)‖2.
Proof. Let F : U → R be a coordinate patch at z = x∗ that meets the conditions in Lemma 1 and Proposition 1. Since x∗ = argmin{a · x : x ∈ X} the outwards unit normal is N(x∗)=− a‖a‖ and the lemma gives
|a · (x− x∗)| ≤ ‖a‖ |v T∇2F (x∗)v| ‖∇F (x∗)‖ d(x, x∗)2.
For all x ∈ U and direction v from x∗ to x the proposition gives d(x, x∗)≤2‖N(x)−N(x ∗)‖
‖∇N(x∗)v‖ . Combine the two bounds to get
|a · (x− x∗)| ≤ 4‖a‖ ( |vT∇2F (x∗)v| ‖∇F (x∗)‖
1
‖∇N(x∗)v‖2
) ‖N(x)−N(x∗)‖2.
To complete the proof Lemma 3 says |v T∇2F (x∗)v| ‖∇F (x∗)‖ = |v T∇N(x∗)v|≤‖v‖‖∇N(x∗)v‖≤‖N(x∗)v‖. Hence the middle factor above is at most 1‖N(x∗)v‖ which is at most 1/m by Lemma 2.
The proofs of Lemmas 7 and 8 in Appendix III follow easily from the vector martingale theorems of Pinelis [28]. The use of these theorems − stated only for bounded martingales − is the major obstruction to generalising our main results to unbounded but subgaussian cost vectors. Lemma 7. For each n≥16D2/η2‖a‖2. The Online Lazy Gradient Descent actions x1, x2... give
E‖N(x∗)−N(xn+1)‖2 ≤ 1
n
36
‖a‖2
(√ 8πDR
η + 4R2
) + 8 exp ( − ‖a‖ 2
32R2 n
) .
Lemma 8. For each neighborhoodU of x∗ in Rd the Online Lazy Gradient Descent actions x1, x2, . . . give ∑∞ i=1 P (xi /∈U) <∞.
Proof of Theorem 1. It is enough to prove a tail bound E [∑N
i>n0 a·(xi − x∗)
] ≤ O(logN) for some
fixed n0. To use Lemma 7 let n0 =b16D2/η2‖a‖2c.4 Let U be a neighborhood of x∗ that meets the conditions of Lemma 6. Since each a · (xn+1 − x∗) ≤ 2LD we see
E|a · (xn+1 − x∗)| ≤ 2LD · P (xn+1 /∈ U) + ∫ xn+1∈U |a · (xn+1 − x∗)|dP.
Lemma 6 says the integral is at most∫ xn+1∈U 4‖a‖ m ‖N(xn+1)−N(x∗)‖2dP ≤ 4‖a‖ m E|N(xn+1)−N(x∗)‖2.
and we see E|a · (xn+1 − x∗)| is at most
2LD · P (xn+1 /∈ U) + 4‖a‖ m E‖N(xn+1)−N(x∗)‖2.
Lemma 8 says the series ∑∞ i=1P (xi /∈ U) converges. Lemma 7 gives constants k ≥ 0 and K =
36 ‖a‖2 (√ 8πDR η + 4R 2 ) such that E‖N(xn+1)−N(x∗)‖2 ≤ K/n+8e−kn. Hence we get
E
[ N∑
i>n0
a·(xi − x∗) ] = O(1)+
4‖a‖ m N∑ i=n0 ( K/i+ 8e−ki ) = O(1)+ 4‖a‖ m ∫ N n0 ( K/x+ 8e−kx ) dx
= O(1) + 4‖a‖ m K logN = O(1) + 4‖a‖ m K logN = 144 m‖a‖
(√ 8πDR
η + 4R2
) +O(1).
4 Equivalence of E[RN ] and P[RN ]
Our Theorem 1 gives an O(logN) bound for pseudo-regret. This seems weaker than the O(logN) expected regret bound of [20]. Here we show the two types of order bounds are in fact equivalent for strongly convex domains. Theorem 2. Under Assumptions 1 and 2, Algorithm 1 with parameter η > 0 gives
E[RN ]− P[RN ] ≤ 31R2
m‖a‖ = O
( L2
m‖a‖
) .
Theorem 2 holds even for non smooth domains. We need only the following result of Vial [35]. Lemma 9. (Vial Theorem 1(v)) Suppose Z is m-strongly convex. For all x, y ∈ ∂Z and outward unit normals p, q at x, y respectively we have ‖x− y‖ ≤ 1m‖p− q‖.
To prove Theorem 2 we first put the left-hand-side in a convenient form. Lemma 10. Let y∗ ∈ argmin {∑N i=1 ai · x : x ∈ X } . Under Assumption 2 we have
E[RN ]− P[RN ] ≤ √ E‖x∗ − y∗‖2 √ E ∥∥∑N i=1(ai − a) ∥∥2.
Proof. By definition E[RN ]− P[RN ] equals E [∑N i=1 ai · (xi − y∗) ] − E [∑N i=1 a · (xi − x∗) ] =
E [∑N i=1(ai−a)·xi ] +E [∑N i=1 ai ·(x∗−y∗) ] . To see the first term is zero recall each xi is a function of a1, . . . , ai−1. Since a1, a2, . . . are independent we see each xi is independent of ai and independent of ai − a. Thus the expectation distributes over the product. Since E[ai − a] = 0 the first term vanishes. Write the second term as E [∑N i=1(ai−a) · (x∗−y∗) ] −E [∑N i=1 a · (y∗−x∗) ] . Since x∗
minimises a·x the second term is positive and we get E[RN ]−P[RN ] ≤ E [∑N i=1(ai−a)·(x∗−y∗) ] . To complete the proof apply Cauchy-Schwarz to the L2 norm. 4According to the adversarial bound the regret before turn n0 is O( √ n0)≤O(D/η‖a‖).
To prove Theorem 2 we need the following three results from Appendix III. Like in Section 3 the first two follow from the vector martingale theorems of Pinelis [28]. The third result is well known but we were unable to find a sufficiently general proof in the literature. Proposition 2. Suppose X1, X2, . . . ∈ Rd are independent random variables with each E[Xn] = 0 and ‖Xn‖ ≤ R. For each t > 0 we have
P (∥∥∥ 1 n n∑ i=1 Xi ∥∥∥ > t) ≤ 2 exp(− t2 2R2 n ) .
Lemma 11. For y∗=argmin {∑N i=1ai ·x : x∈X } the Online Lazy Gradient Descent actions give
E‖N(x∗)−N(y∗)‖2 ≤ 144R 2
‖a‖2N + 4 exp
( −‖a‖ 2
8R2 N
) .
Lemma 12. For X a nonnegative random variable we have E[X] = ∫∞ 0 P (X > x)dx.
Proof of Theorem 2. Proposition 2 gives P ( ‖ ∑N i=1(ai − a)‖ > t ) ≤ 2 exp ( − t 2 2NR2 ) for all
t ≥ 0. Replace t with t2 to see P (∥∥∑N i=1(ai−a) ∥∥2 > t) ≤ 2 exp (− t2NR2 ) . Lemma 12 says
E‖ ∑N i=1(ai − a)‖2 ≤ ∫∞ 0 P ( ‖ ∑N i=1(ai − a)‖2 > t ) dt ≤ 4NR2. Hence Lemma 10 gives
E[RN ]− P[RN ] ≤ 2R √ N √ E‖x∗ − y∗‖2.
For the second factor Lemma 9 gives √ E‖x∗ − y∗‖2 ≤ 1m √ E‖N(x∗)−N(y∗)‖2. Lemma 11 gives E‖N(x∗) − N(y∗)‖2 ≤ K/N + 4e−kN for the constants K = 144R2/‖a‖2 and k = ‖a‖2/8R2. Hence √ E‖x∗ − y∗‖2 ≤ 1m √ K/N + 4e−kN ≤ 1m √ K N + 2 me −(k/2)N and so
E[RN ]− P[RN ] ≤ 2R √ K
m +
4R
m
√ Ne−(k/2)N = 24R2
m‖a‖ +
4R
m
√ Ne−(k/2)N . (3)
To bound the last term consider the function √ xe−βx for β ≥ 0. It is straightforward to see the function is increasing and then decreasing. By differentiating we see the maximiser is x = 1/2β and the function is at most 1/ √ 2eβ. For β = k/2 we see √ Ne−(k/2)N ≤ 1/ √ ke = 2 √ 2R/ √ e‖a‖.
Thus the right-hand-side of (3) is at most (
24 + 8 √ 2√ e
) R2
m‖a‖ ≤ 31R2 m‖a‖ .
Finally we can combine Theorems 1 and 2: Theorem 3. Under Assumptions 1 and 2, Algorithm 1 with parameter η > 0 gives
E[RN ]≤ 144
m‖a‖
(√ 8πDR
η + 4R2
) logN +O(1).

heading: 5 Numerical Simulations
text: Here we present numerical simulations for Online Lazy Gradient Descent, using a range of strongly convex domains and i.i.d opponents. The higher dimensional simulations ran on the order of minutes, due to use of an all-purpose Python package to compute minimisers. Performance time can be improved by using the Franke Wolfe method of [17] to simplify the minimisation problems.
`p-Norm Balls. Here we examine performance for domains X= { x∈Rd : (∑d i=1 |x(i)|p )1/p≤1}. For p ∈ (1, 2 ] Corollary 1 of [17] says X is (p− 1)d 1 2− 1 p strongly convex.
For simplicity we use stepsize η = 1. When searching for worst-case performance it is enough, by symmetry of the domain, to only consider E[an] = a with nonnegative nondecreasing components. We consider a = b/‖b‖ for b(i) = (i/d)r and a range of parameters r ≥ 0. For example three degenerate cases are a = 1√
d (1, . . . , 1) for r = 0; a =
√ 2
d(d+1) (1, 2, . . . , d) for r = 1 and
a = (0, . . . , 0, 1) for r →∞. We use cost vectors an = a+ µn for two types of noise: (1) µn(j) =
1√ d (Bn1 , . . . , B n d ) (2) µn(j) = (0, . . . , 0, B n d ).
Here Bnj are independent and take values ±1 with equal probability. In both cases ‖µn‖ = 1. Noise type (1) perturbs all components equally and individual perturbations are small for large d. Type (2) perturbs only the largest with size 1. We run several instances (samples) of each online problem and plot the average pseudo-regret over instances.
Figure 1(a) shows that for noise type (1) performance degrades as r shrinks. This is consistent with the picture for d = 2 and r = 0 where the minimiser (2−1/p, 2−1/p) also minimises the curvature, and how Theorem 1 gives a worse bound for small curvature. For noise type (2) Figure 1(b) shows larger r gives worse performance. This can be attributed to how r is approximately (0, . . . , 0, 1) and the noise is focused on the final component rather than spreading over all components evenly.
For smaller of d, p the pattern is the same but takes longer to emerge. In Figure 3, Appendix I, we consider the worst cases in Figure 1 and vary the dimension. For r = 0 and noise type (1) the performance improves slightly with large d. This is perhaps due to the higher dimension having a regularising effect on the noise. For r = 8 and noise type (2) the performance deteriorates with large d. This is expected since the curvature (p− 1)d 1 2− 1 p shrinks in high dimensions. In Figure 4, Appendix I, we vary the parameter p. In both worst cases the performance deteriorates as p → 1 though it also takes longer for the worse performance to emerge.
For all cases the growth rates are orders of magnitude below those suggested by Theorem 1. For example in the setup of Figure 1 we have p = 1.5, d = 32 and the convexity parameter is m = (p− 1)d 1 2− 1 p = 0.5 · 32− 14 ' 0.21. This makes the coefficient in Theorem 1 approximately 6180.
Comparison with Greedy Gradient Descent. Theorem 3 says Online Lazy Gradient Descent gives logarithmic expected regret on a strongly convex domain against i.i.d cost vectors. One can ask does Online Greedy Gradient Descent with update xn+1 =ΠX ( xn−ηan/ √ n )
give the same bound.
Figure 2(b) suggests otherwise. The worst-case regret of Greedy Gradient Descent seems to be
Ω(
√
n). The coefficients D1, C1 in Figure 2(b) are chosen to match the regret on turns 1000 and 500,
and the Θ( √ n) fit is very close over the entire range. The coefficient C2 is chosen to match on turns 0 and 1000 and is a worse fit.
Schatten Matrix Norms. Schatten matrix norms are well-studied as regularisers in the context of machine learning. For example see [3, 21] and the citing works.
Definition 2. Given a real n×m matrix A there is a unique decomposition A= UΣV such that V,U are real orthogonal, U is n×n, V is m×m, and Σ is n×m with real diagonal entries σ1≥σ2≥ . . .≥σmin(n,m) and all other entries zero. The σi are called the singular values of A. For any p≥0 define the Schatten p-norm ‖A‖S(p) =‖σ‖p as the p-norm of the vector of singular values.
For simplicity we only consider square matrices. Corollary 2 of [17] says the Schatten unit balls Bp(1) = {X ∈ Rd×d : ‖X‖S(p) ≤ 1} are (p− 1)d 1 2− 1 p strongly convex. When searching for worst case performance the following lemma says it is enough to only consider when E[an] is a diagonal matrix. See Appendix I for proof.
(a) Lazy Gradient Descent on the Schatten unit ball (b) Greedy Gradient Descent on the Euclidean unit ball
Figure 2
Lemma 13. Suppose a1, a2, . . . ∈ Rd×d are i.i.d cost vectors with E[an] = a. There is another set of i.i.d cost vectors b1, b2, . . . such that E[bn] = b is diagonal and ‖an − a‖ = ‖bn − b‖; ‖an‖ = ‖bn‖; ‖a‖ = ‖b‖ and the expected regret of playing Online Lazy Gradient Descent (Algorithm 1) on Bp(1) against a1, a2, . . . with x0 = 0 is the same as playing against b1, b2, . . . with x0 = 0.
Likewise by symmetry we can assume the diagonal entries are nonnegative and nondecreasing. For simplicity we use stepsize η = 1. We consider a = b/‖b‖ for b = diag ( (1/d)r, (2/d)r, . . . , 1 ) and a range of parameters r ≥ 0. We consider cost vectors an = a+ µn and noise µn = νn/‖νn‖ for three types of νn. Here Bnij are independent and take value ±1 with equal probability.
(1) νnij = B n ij for all i, j (2) νnij = B n ij for all i and some uniformly chosen j; and ν n ik = 0 for all k 6= j. (3) νnij = B n ij for some uniformly chosen i, j; and ν n lk = 0 for all (l, k) 6= (i, j).
Compared to the examples for `p balls, fewer samples are needed to obtain smooth curves. For noise type (1) Figure 2(a) shows the worst performance occurs for r = 0. The different types of noise make minimal difference to performance. See Figure 5, Appendix I. Thus when varying p and d we only consider noise type (1). In Figure 6, Appendix I, we see large d leads to slightly better performance, and small p leads to worse performance. Though the infuence of p and d is minimal compared to that in Figures 5 and 2 for `p-balls.
For Schatten balls diagonal noise matrices seem to be the most difficult to deal with. In that case all an are also diagonal and the Schatten norm reduces to the p-norm of the diagonal entries.

heading: 6 Conclusion
text: Online Lazy Gradient descent on a strongly convex domain is universal in the sense that it achieves O(logN) regret against i.i.d opponents. This is in addition to the well-known O( √ N) regret bound against adversarial opponents. Moreover for strongly convex domains, order bounds for pseudo-regret and expected regret are equivalent. For various types of noise on `p and Schatten unit balls, the growth coefficients are orders of magnitude smaller than those suggested by our analysis.
Disclosure of Funding. This work was supported by Science Foundation Ireland grant 16/IA/4610.
Broader Impact. This is theoretical work on special cases of online optimisation, with no particular application in mind. We do not forsee the work having any direct impact on society. The only ethical concerns are those related to the use of online optimisation in general.

Review summaries:
They authors show that for linear optimization on strongly convex domains the lazy subgradient method achieves a best-of-both-worlds behavior of a expected regret bound of O(\sqrt{N}) and O(\log(N)) for adversarial and stochastic adversaries, respectively. The best known prior bounds were O(\sqrt{log(N)}) adversarial regret with a more complicated algorithm (based on A,B-prod). On a technical side, the analysis for lazy subgradient is much more intricate and considers loss contributions in the direction of the comparator separately from other directions, and may be of interest in other online linear optimization settings.  Simulations are provided that convincingly argue for the proposed method in the proposed setting.  

The authors study online linear optimization in the case of known strongly convex constraints sets. They show that the simple method of online subgradient descent, which is known to achieve $O(\sqrt{N})$ regret in the adversarial case, also achieves $O(\log(N))$ regret in the i.i.d. case. This result is more elegant than and slightly improves upon existing results in the strongly convex case.

The paper considers the problem of online linear optimization under a full information feedback setting on a strongly convex domain. In this setting, the authors show that the classical lazy subgradient method is optimal both in the adversarial and stochastic settings.  In particular, the authors show that for the same choice of hyper-parameters, the lazy sub-gradient method achieves O(\sqrt{N}) regret in the adversarial setting and O(log{N}) regret in the stochastic setting. To show this result, the authors have to do a more nuanced analysis of the algorithm (that relies on differential geometry methods) than existing works.   

The authors study online linear optimization and show that the Lazy Online Subgradient Algorithm is *universal* on strongly convex domains: it simultaneously achieves the optimal $O(\sqrt T)$ regret when the costs are adversarial and the optimal $O(\log T)$ regret when the costs are stochastic. This result is a clear improvement over previous work of Huang et al, who described a more complex algorithm and didn't achieve the optimal rates. The proof is based on an intricate analysis, drawing from differential geometry, of the points selected by the algorithm, and in particular, how much of each step affects regret against the minimizer $x^*$ and how much is orthogonal to the direction $x_i - x^*$ and doesn't affect regret. This technique may be of interest to the broader ML community.