The Lazy Online Subgradient Algorithm is Universal on Strongly Convex Domains
Authors: Daron Anderson
Douglas J. Leith
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimisation
online learning
FTRL
subgradient
gradient descent
sequential
machine learning
strongly convex
logarithmic
pseudoregret
expected regret
differential geometry
curvature

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

Online Lazy Gradient Descent is Universal on Strongly Convex Domains
Daron Anderson
Douglas Leith
School of Computer Science and Statistics Trinity College Dublin
School of Computer Science and Statistics Trinity College Dublin
Abstract
We study Online Lazy Gradient Descent for optimisation strongly convex domain. The algorithm is known achieve O(vN) regret against adversarial opponents; here we show it is universal in the sense that it also achieves Olog N) expected regret against i.i.d opponents. This improves upon the more complex meta- algorithm of Huang et [20] that only gets O(vN log N) and O(log N) bounds. In addition we show that, unlike for the simplex, order bounds for pseudo-regret and expected regret are equivalent for strongly convex domains.
1 Introduction
Online linear optimisation is repeated game with one opponent. On turn n know the cost vectors a1, 02,.... an-1 E Rd and select an action In from the domain X C Rd. The opponent observes In and chooses the next cost vector a, Rdd and pay cost an Zn. Our goal is to select actions to make the regret MN a; (x; - x²) small for x argmin />/ 0;
X).
the cost vectors are selected by an adversarial opponent then d1, a2...., an-1 give no information about an and selecting good action seems like an impossible task. Despite this, there are algorithms
that get O(v D(vN) regret against such opponents. The loss in performance against x is O(1/ v N) per turn which vanishes as - 0o. The central algorithms the field are Hedge [8] 34 Prod [); and (sub)Gradien Descent, which has Greedy [41] and Lazy 34] variants. All three algorithms get O(VN) regret. The first two specialised to X the simplex. The latter works for any compact convex domain. The bulk 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 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 01, an provides information about the next cost vector. Indeed ān+1 tu. is an increasingly reliable sequence of estimates for E[an+1] and it seems reasonable to play Fn+1 to minimise t x. This is called Follow-the-Leader (FTL). For example
n
is the simplex FTL gives reeudo-regret E I a-(I, -y>) < O(1) for y argmin x E X Note this is Σi= ag (x; - xx )- On the other hand FTL gives no
weaker than bounding the expected regret E Σ> 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(VN) N) regret but specialises a much stronger bound against i.i.d opponents.
Recently Huang et 20 solved this problem for smooth, strongly convex domains. For these domains they showed FTL gives (loog N) regret if || Σ a:ll grows linearly"" The result was generalised to nonsmooth domains by [22][26 Huang et then combine FTL with the (Aoo meta-algorithm of (31 ensure O(vN log N) regret against adversarial opponents. In this work
Without smoothness they show the growth condition occurs with high probability against i.i.d opponents.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Algorithm 1: Online Lazy Gradient Descent
Data: Cost vectors 1 a2:.... E IRd.. Parameter 1) > 0. Domain X C Rd.
for n 0, do
In+1=1ly 1 Vn 2i=100 a4)
Receive dx++ and pay cost dx++1 2n++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(vN) and O(log N) bounds.
Terminology and Notation
Throughout || I|
is the Euclidean norm, Given a vector subspace C Rd and linear operator A V V write the operator norm as ||A|| max[]]Aul]]
V, ||||| =1]. It is known (see 10 Theorems 4.1 and 4.2) that || max, vDyyl for X, the eigenvalues of A A. Moreover if
is symmetric have || max, |,5 for μ4y the eigenvalues of A. The set Z IR called --strongly convex to mean for each z, E Z and a E [0. 1] the ball B(az a)y, r) is contained in Z for r = aa a)]l yll². The pseudo-regret P[Rx] and expected regret E[Rx] are defined:
P[RN] E Σ a.
min ZEX
E[Rx] E Σ O4
min Σ #EX
a
The Jensen Incquality implies P[Ry] E[ We write IIx for the Euclidean projection onto the domain X. The Online Lazy Subgradient algorithm is given as Algorithm[] Note this is different from the so-called Greedy Subgradient algorithm with starting point æ = 0 and recursive update In+1 ITx (In n/an/ Vn). Section Figure (bb) suggests Greedy Subgradient is not universal.
Summary of Contributions
Throughout make the following assumptions on the domain and cost vectors. Both assumptions are nontrivial. For example Assumption holds on the Euclidean and & balls for p (1, 2] but not for the simplex polytopes. Assumption 2 the cost vectors is typical model of an easy opponent and fails if the opponent intelligent and adapts to our past moves.
Assumption 1. The domain Xdd is compact, m-strongly convex and contains the origin. Write D = max ||- :x, y E X.. The boundary M = 0X is a (d- (0-11)-dime dimensional C2 manifold. Namely each 2 M has a neighborhood U in RR and C function F:U - R with nonzero gradient such that MnU = {a E U F(x)=(())))) =0. Such function is called coordinate patch at 2.
Henceforth write (xx) for the outwards unit normal at M. To represent N:M- Rd locally we can choose coordinate patch F: - at xt and write VN- VF [VF
Since F is C2 the matrix
V.V of partial derivatives exists.
Assumption 2. The cost vectors a1 .2, are i.i.d with expectation B[an] = For all n we have | $ and |a,, all < R and Ellon al I 8. Let x" e argmin(a x x E X3 be the expected minimiser. The domain X being strongly convex implies x" is unique.
Our main result is Theorem which says Online Lazy Gradient Descent achieves O ( a log N) expected-regret under Assumptions and This bound essentially tight by (20 The improved behaviour against i.i.d opponents is remarkable since the algorithm Theorem designed with the adversarial case in mind, and predates the recent interest in universal algorithms. Our second contribution is Theorem which states the gap between expected regret and pseudo-regret is 0 L2 (mmjaaa
Theorem of independent interest since it fails if the domain is the simplex.
for FTL. Their central idea is that the normal vector to M at 2, argmin +a1+ .oaat...t....... t....t.... a.,-1)
From a technical standpoint, our Gradient Descent analysis goes beyond that of 20
22: E X)
points along A,-1 art..te--1 Using A An- ||| 0(1 (n) and how strong convexity says the unit normal changes quickly as we vary the basepoint, they prove |0,, =0+1/==((11n) for the normal vectors O,, O,+1 at Zn, In+1- Summing the resulting series gives logarithmic regret

---

bound. Unfortunately this method is insufficient to analyse Gradient Descent instead of FTL as it only gives ||O,, - =+
and the resulting series give only an D(vN) bound. Thus we = Q(1/Vn) for
follow a new approach where we prove high probability bound [[ N(**)| 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 || - O(1/ and only (11/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 (log N) bound for pseudo-regrer. To convert this into bound for expected regret we use our Theorem 2 which says the gap between expected regret and pscudo-regret is finite.
Our differential geometry methods are more nuanced than existing works. Existing works consider only the magnitude ||r,, Fn+1| || but we consider both the magnitude and direction of Ti, x². The relevant object is (=(e)) in Lemmas 5 and Proposition [ which captures the rate of change of the unit normal as we perturb the basepoint the u-direction.
2 Related Work
The first strand of related work is universal algorithms. That is to say online algorithms with Ö(VN) 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
g
32
33
40 In the
full information setting the FlipFlop algorithm [1] interpolates between FTL and Hedge on the simplex to get O(1) and O( /N log N) regret against i.i.d and adversarial opponents respectively. The (A,B)-Prod meta-algorithm [31] does something similar much greater generality. Another result comes from [16.. They design variant of the Prod algorithm
[9] with different learning rates for each arm. As a corollary they get (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. pseudo-regret on the simplex 27;; and Online Lazy Gradient Descent gets O / A) pseudo-regret on polytoped 12 The latter is notable since it works for domains other than the simplex. Here d the dimension; A the suboptimality gap; and we assume ||a,,]| S T.2 and ||a, llae S L. where appropriate. The above bounds are in addition to the O(vN) regret bounds of Gradient Descent and Hedge (see [3] Chapter 2) against adversarial opponents.
Hedge gets (log(d)
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 lp unit ball with p E (1, 2] in the full-information setting. Another setting of interest 12
19 is when
predictions are available for the direction of the next cost vector. In the bandit setting 7 consider lp 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 I77 show the Frank-Woll method has (11nz²) convergence rates and hence finite regret- when the domain is strongly convex. (23 prove similar results for more general so-called uniformly convex show an exponential convergence rate.
sets. Under additional conditions the older works [3 14 25
3 Bound for Pseudo-Regret
Here we show Online Lazy Gradient Descent gets O(log.V pseudo-regret against i.i.d cost vectors on a C2 strongly convex domain. This is in addition the O(vN) regret bound for adversarial costs. Theorem 1. Under Assumptions and 2, Algorithm with parameter 1) > O achieves pseudo-regret
144 m||all
P[Rx] <
+ 4R²
log N + 01).
"
In particular for hyperparameter 77 = O(D/L) we have P[[N]] S O
( log log.v).
log
12
mmaaa
By 34 Theorem 2.4 hyperparameter 17 7- is optimal for both adversarial and i.i.d bounds.
'Huan et al 20 already proved an 0(1) bound for polytopes with unique optimal vertex. However dependence dimension and suboptimality gap is not obvious.
3

---

We begin with some geometric intuition for our proof strategy. To interpret Lemma it is convenient to imagine the domain translated put at the origin and the outward unit normal [2)) points along the d-th coordinate direction (henceforth called the height). Since (=) has unit length, the left-hand-side of Lemma the height of the boundary at z. The lemma says the height changes quadratically with coefficient depending on the direction v as defined below
Definition 1. Given points 2, y E .M a geodesic from I to is a C² path in M with endpoints x for each 1, and such that y has minimal length among such paths. That length IR4 is called direction from to y to mean there a geodesic y [0, dl(z (z y) + M from x to y with 7/(0) = V.
and y with [+)( is called the geodesic distance d(z,, y). The unit vector
In Lemma 6 we plug the expected minimiser = = 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(z) - Nx==)
Finally we plug z = In into Lemma 6 and use Lemma to see [INV - - with high probability. The idea is to write the unprojected action In vn Σ a4 as yn
nm + Vn 2a= aa)) The first term points along - Taj N(x*) and has length ((
The second term is O(1) with high probability due to the i.idd sum. Hence after normalisation the component of V/. orthogonal to Taī has size D(1vvn) Since the domain is bounded the same holds if we instead normalise yo. w for any E X. In particular taking w Fn get |1 O(I/VT). Since In 1Ix (yn) we have -e- (xx).. Since N(x*) we get N(xx)) - N2 ((1/)) with high probability. Sum the series to get PN = 0 (Σ 4) OloggN)
all
Lemma 1. For each z E M there exists a coordinate patch F U -> such that for each x E UMM and direction e from to we have
10 (2))0l
[x())x=
[VF(2)] 2(x,2)
Lemma iis proved using Lemmas 2 and Proposition | which are in turn proved in Appendix II. The arguments there use only routine di 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 E . and unit vector v tangent to M at we have [ 2 m.
Lemma 3. For each coordinate patch F at = and unit tangent v to M at z we have '''''F(aje 2 [[V[[>]]
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 E M has coordinate patch F B(z,r) r) + with |
I [V'Fl TVFGI
< M for all y E B(z,r).
Lemma 5. Let M be the constant from Lemma
4. For each geodesic y [0, d(x v)] + M from to we have for d = d(x, y) and all t I d the inequalities
(1) (t)l < M
(2) (t) - 7(0) (r)())) s 2 t2
(3) Illy xl| d S d
Proposition 1. Each 2 e M has a neighborhood U in Rd such that for all E M and direction from 2 to we have
[2 d(x,2)
[N((2) - N2)
2
Proof of Lemmal Let F, M, be from Lemma 4 Since F is C2 Taylor's theorem says there is function (t) defined on some neighborhood of the origin with lim (1) and
F F(2) (= 2) + (x V F()((=
+ x>]l= =
2
'It is of course possible to define geodesics and directions using a non non-Euclidean notion of distance. However in this paper only consider Euclidean geodesics.

---

Hence there is r >> 0 such that for all 2 E B22,r) we have 1 z)|
- 4 [VF and so
- VF(=) - [ar (a-=)" ((
V VF
=|1?
Shrink if necessary to ensure r)) has geodesic diameter at most min /2mmM By assumption F(x) = F F(z) = 0. Hence for d(z,2) 2) the above gives
mh (=))((x 2) (x-z)² (x- (= S
|F - 2| 7 (VF
2
1
Let be direction from For [VF(=)(> =)1 FFFs)((
2) du. The reverse triangle inequality gives
V F || + 1 V
I F(s))))
(2)
Lemma 5 says ||/|| < MM&/ /2 and Lemma
says
F(=) [VF
M. Hence we get
I T (2)
s [|]lll
- 2 [F(E]
VF())]|
VF(()
[F(2)] mdd
?
where the last inequality uses the assumption d s m/2M2. Similarly d s /2m/M3/2 V2 z [[V[[=)]] ma? Hence
gives
becomes
VF(2)( 2)1 F
[VF I [VF
I0 | + (VF())))) d? Since the unit normal is (2) = IFl we can divide both sides to get (z) - 2) $ (1"F"2 + m d. Lemma [vF(al
and so [VF(=)(z 2)
(F())
says m < oo" F(zjul This completes the proof.
[VF(]]]
Lemma 6. The minimiser x" has neighborhood U in IR such that each x E U n M has
|||| m
a (x- - x²)
[z(()) N(=))|12
Proof. Let F U + Proposition] Since x= = magmin(a-.. x x E X} the outwards unit normal N(=*)= the lemma gives
IR.. be coordinate patch at x= that meets the conditions in Lemma T and
|||]] and
T FVF((""U
la (x- (t-=x)] S |||||
VF d(x, x²)²
For all x E U and direction v from x: to x the proposition gives d(x, x)) 52 N((z) N(z") the two bounds to get
Combine
Joll
la (ar ( x-)] S 4||a||
[N(x)-
| (x*)
[VN(x*)
To complete the proof Lemma says [[FF(=)
)oll
Hence the middle factor above is at most [[]((=))]] which is at most 1/m by Lemma
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 unbounded but subgaussian
vectors.
Lemma 7, For each 2 16D2 /n || The Online Lazy Gradient Descent actions 21, D2... give
[[ N (Z
|||l
36
[V8TDD DR
+ 4R² )
+ 8exp
32
||a||
n
5

---

Lemma 8. For each neighborhood U of in R the Online Lazy Gradient Descent actions T1, 22,
give Ei=1 P(x, $ U) oc.
Proof Theorem It is enough to prove a tail bound E Σ iono a-(x; - a-(x;-x")
S O(lgg N) for some Let U be a neighborhood of x" that meets the fixed Ro. To use Lemma 7 let = [16 [16D2/v/[lal]" /|/
conditions of Lemma Since each a (In+1 x²) S 2ID we see
E a (In+1 - x²)l & 2LD P(an-1 $ U) +
la (In+1 - x IdP.
IMIIEUU
Lemma 6 says the integral is most
JaNIEW Allal| (
4||a| E (((
m
m
and we see Bla- (Int1- - xx)]
is at most
2LD P(ant1 & U) + 4|la| E (I - 2l
Lemma
8
says the series Σis P(a: U) converges. Lemma 7 gives constants k 2 0 and K
VO
4R²)
such that
- K/n+ Se kn Hence get
N
A|lall 0(1++
NN (K/i+&E*) 8e hi) O(1++ Allall /
E
ax; - x²)
Σ
(K/x SE he)
m
Lioma
4||a| 0(1)+
|all
K log N= 144
VSDDR
Klog N = 0(1) m
+ 4T² +011.
mi|a|l
m
17
4 Equivalence of [[[ and P[RN]
Our Theorem expected regret bound of [20). Here we show the two types of order bounds are in fact equivalent for strongly convex domains.
I gives Oloo N) bound for pseudo-regret. This seems weaker than the Olog N)
Theorem 2. Under Assumptions and 2, Algorithm with parameter vj > 0 gives
R1 m||a|
2
E [Rv] - P[ I
O
(mllaal)
Theorem 2 hholds even for non smooth domains. We need only the following result of Vial [35]. Lemma 9, (Vial Theorem 1(v)) Suppose is m-strongly convex. For all æ, y E OZ and outward unit normals p, q at z, respectively we have ||æ yll lpp 4/1-
To prove Theorem 2 we first put the left-hand-side in a convenient form.
Lemma 10. Let y E argminn EN a x E X}. Under Assumption we have
E[RN] P[RN]] / 11 E Ei (a, -
Proof. By definition [[Rx] - P RN equals E EN a (xi - - E( a - (x,-=")] = N (a, 10..-00 a).x,) +B[ a, (2- - y ] To see the first term is zero recall each x; is function
E E Di=1 of af a;-1- Since 41, a2.... are independent we see each 2; is independent a; and independent of a; Thus the expectation distributes vanishes. Write the second term as E E N (a, a)- (x* y y²]]
the product. Since E Ela;
a)
the first term
E
[>N
N a- (y" =²)] Since
minimises z the second term is positive and get [[ - [P[ I E ii (a: a)-
To complete the proof apply Cauchy-Schwee
the L norm.
According the adversarial bound the regret before turn no is <OW//\))())))

---

To prove Theorem 2 we need the following three results from Appendix III. Like in Section the first two follow from the vector martingale theorems of Pinclis [28]. The third result well known but we were unable to find sufficiently general proof in the literature.
Proposition 2. Suppose X1, X2,..... E Rd are independent random variables with each B[X,) = and |Xx,|| S R. For each >> 0 we have
t?
P
E X: >
s 2 exp
2
Lemma 11. For y² argmin Ei= a::x x the Online Lazy Gradient Descent actions give
144R²
||a|1
8R )
[I - - NI aalL
4 eep
Lemma 12. For X a nonnegative random variable we have E[X] = - P(X > x)dr.
Proof of Theorem
2
Proposition 2 gives (1EM (a: - aa]l >1) - 2 cxx (a: a) >1) I 2 2exp 2N
for all
2N
t. 2 0. Replace 1. with 1² to see P |
Lemma 12 says
Σ 1 a)l Io P(I ΣN (a: - a)l > t) S 4N A² Hence Lemma
10
gives
E[RN] - P[ & 2R N E x+ - yr
For the second factor Lemma gives E x-- 3- v ElI.V(>> [x=)(x)) N Lemma 11 gives
(x)) (3 < K/N 4e for the constants K 144R² / |a|| and & |||| /8R2
Hence / -- s K/N
+
2 (2/22
and so
E[Rv]- 2RVK 4R VNe (4/2)N
24R
4R VN (W/2))
(3)
ml all
To bound the last term consider the function vze dr for 2 It straightforward to see the
function is increasing and then decreasing. By differentiating we see the maximiser is x 1/28
and the function is at most 1/ /2eB. For = k/2 we see (Ne-(t))) <1/vke =
Thus the hand-hann-sdee of (3) is at most 244 + 8/2
R²
31
ml [al
mila||
Finally we can combine Theorems and
Theorem 3. Under Assumptions and 2, Algorithm with parameter 1) > 0 gives
144 VSTDR
E[RN]s
+ 4R²
log N O(1)
m m||a|
"
Numerical Simulations
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- all-purpose Python package to compute minimisers. Performance time can be improved by using the Franke Wolfe method of [1 to simplify the minimisation problems.
NorNorm Balls. Here we examine performance for domains X X= (= (IERd : (x())))))))))) 1/p <1}.
For E (1,2 Corollary of [17] says X is (p 1)d+ strongly convex.
For simplicity we stepsize 1. When searching for worst-case performance it is enough, by symmetry of the domain, to only consider E(a,)] = a with nonnegative nondecreasing components. We consider = b/|lb]l for b(i) (i/d)" and a range of parameters r 2 O. For example three
degenerate cases are a = +
2 1) for r 0; = ā[ (1, (.,,...)) d) for r = and
= (O,...,0, 1) for - xc. We use cost vectors a, = a + pn for two types of noise:
(1) ()) = (BT BT)
(2) (i) = .O.....
........... 0, B7).
7

---

dimension 32. p Samples Type
dimension p Samples Type
20-
1.0
0.5
0.0
100
125
150
175
150
175
200
Number of
Number
(a) Noise type (1)
(b) Noise Type (2)
Figure I: Online Lazy Gradient Descent on the f.s unit ball.
Here B3 are independent and take values #1 with equal probability. In both cases || 1. Noise type (1) perturbs 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 TT) shows that for noise type (I) performance degrades as shrinks, This is consistent with the picture for d = 2 and r where the minimiser (2-1/,, 2 2-\/r) also minimises the curvature, and how Theorem D gives worse bound for small curvature. For noise type (2) Figure [ shows larger r gives worse performance. This can be attributed to how is approximately (O,... 0, 1) and the noise is focused the final component rather than spreading over all components evenly.
For smaller of d, the pattern is the same but takes longer to emerge. In Figure 3 Appendix I, consider the worst cases in Figure I and vary the dimension. For performance improves slightly with large d. This is perhaps due to the higher dimension having regularising effect on the noise. For 8 and noise type (2) the performance deteriorates with large d. This is expected since the curvature (p- - 1)då shrinks in high dimensions. In Figure 4 Appendix I, we vary the parameter In both worst cases the performance deteriorates as p though it also takes longer for the worse performance to emerge.
0 and noise type (1) the
For all cases the growth rates are orders of magnitude below those suggested by Theorem | For example in the setup of Figure [ we have p 1.5, d 32 and the convexity parameter is m (p - 1)d+ = 0.5 - 32- ~ 0.21. This makes the coefficient in Theorem Japroximately 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 Ix+1 I=+1= =1x (x
give the same bound. Figure bb) suggests otherwise. The worst-case regret of Greedy Gradient Descent seems to be ((vn) The coefficients D,, C1 in Figure 2 b) are chosen to match the regret on turns 1000 and 500, and the ((vn) fit very close over the entire range. The coefficient C2 is chosen to match on turns 0 and 1000 and is worse fit.
(zn-
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 real X matrix A there is unique decomposition A = UEV such that V, U are real orthogonal, U is n n, V is m X m, and Σ is n x m with real diagonal entries σ 2 02 2 ... miiu(n,m) and all other entries zero. The are called the singular values of A. For any p20 0 define the Schatten p-norm [A]ls(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 (1) XX E Rdxd =| 1} (p 1)d+ strongly convex. When searching for worst case performance the following lemma says it is enough to only consider when E[a.] is diagonal matrix. See Appendix for proof.

---

J. Samples Type
Samples Type
35
2.0
1.2
Samples
0.-
Mnan of samples
0.0
log (ni 3]
100
125
150
175
200
0000
000
1000
Number
Number
Lazy Gradient Descent the Schatten unit ball Greedy Gradient Descent the Fuclidean unit ball
Figure 2
Lemma 13. Suppose 01, 02,... Rdddd are i.i.d cost vectors with E(a, = a. There another set of i.i.d cost vectors b, bg.... such that E[b,]] = b is diagonal and [|a, al = μbb,, b|l; ||a, = | ||a|| = ||||| and the expected regret playing Online Lazy Gradient Descent (Algorithm 1) on (1) against (1, ..,.... with Zo = 0 is the same as playing against b1, b2,... with 25 0.
Likewise by symmetry simplicity we use stepsize 77 = 1. We consider a = b/ ||6|| for diag((1/d) (2/d)"" ..."",....]) and a range of parameters 2 O. We consider cost vectors a, = a + jı" and noise μ*" v² /|||| for three types of v². Here Bj are independent and take value +1 with equal probability.
assume the diagonal entries nonnegative and nondecreasing, For
(1) V B for all i.j
(2) 1 = Вi for all i and some uniformly chosen j; and v/ for all * j.
(3) V B for some uniformly chosen j; and 1/ for all (1, # (i.j).
Compared to the examples for lp balls, fewer samples are needed to obtain smooth curves. For noise type (1) Figure Z[a) shows the worst performance occurs for 0. The different types of noise make minimal difference to performance. See Figure 5) Appendix I. Thus when varying and we only consider noise type (1). In Figure 6 Appendix I, see large d leads to slightly better performance, and small p leads to worse performance. Though the infuence of and is minimal compared to that in Figures 5 and 2 for ba.balls.
For Schatten balls diagonal noise matrices seem to be the most diffi 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.
Conclusion
Online Lazy Gradient descent on a strongly convex domain is universal the sense that it achieves Olog N) regret against i.id opponents. This is addition to the well-known O D(VN) 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 lp and Schatten unit balls, the growth coefficients 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.
References
[1] Daron Anderson and Douglas Leith. Optimality of the subgradient algorithm in the stochastic setting, Arxiv E-prints, 2020.

---

[2] Daron Anderson and Douglas Leith. Universal algorithms: Beyond the simplex. Arxiv E-prints, 2020.
[3] Andreas Argyriou, Charles A Micchelli, and Massimiliano Pontil. On spectral learning. Journal of Machine Learning Research, ((2), 2010.
[4] Peter Auer and Chao- Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. CoRR, (bs//600500872) 2016.
[5] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online Learning with Imperfect Hints. Proceedings of the 37th International Conference on Machine Learning, Vienna, Austria, 119, 2020.
[6] Sébastien Bubeck, Nicolo Cesa- Desa-Bianchi, and Sham M Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages 41-1, 2012.
[7] Sébastien Bubeck, Michael Cohen, and Yuanzhi Li. Sparsity, variance and curvature in multi- armed bandits. In Algorithmic Learning Theory, pages 111 111-127, 2018.
[8] Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: stochastic and adversarial bandits. CoRR, abs/1 202.4447, 2012.
[9] Nicolo ResacBia Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2-3):321-335 2007.
[10] Mohammed Dahleh, Munther A Dahleh, and George Verghese. Lectures dynamic systems and control. 2011.
[11) Steven De Rooij, Tim Van Erven, Peter D Grünwald, and Wouter M Koolen. Follow the leader you can, hedge if you must. The Journal of Machine Learning Research, 15(1):1281-1311) 2014.
[12] Ofer Dekel, Nika Haghtalab, Patrick Jaillet, et al. Online learning with hint. Advances in Neural Information Processing Systems, pages 5299-5308, 2017.
[13] V. F. Demyanov and A. M. Rubinov. Approximate Methods in Optimization Problems. (Modern Analytic and Computational Methods in Science and Mathematics). IX + 256 S. New York 1970. American Elsevier Publishing Company, Inc. Preis geb. DiL. 77.50. ZAMM Journal of Applied Mathematics and Mechanics Zeitschrift für Angewandte Mathematik und Mechanik, 53(7):499-499, 1973.
[14] Joseph C Dunn. Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM Journal Control and Optimization, 17(2):187-211, 1979.
[15] Ryszard Engelking. General topology. Sigma Series in Pure and Applied Mathematics, Volume 6. Heldermann Verlag Berlin, 1977.
[16] Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. second-order bound with excess losses. In Conference on Learning Theory, pages 176-196, 2014.
[17] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets. In 32nd International Conference on Machine Learning, ICML 2015, 2015.
[18) Geoffrey J Gordon. Regret bounds for prediction problems. In Proceedings of the twelfth annual conference on Computational learning theory, pages 29-40, 1999.
[19] Elad Hazan and Nimrod Megiddo. Online learning with prior knowledge. In International Conference on Computational Learning Theory, pages 499-513, Springer, 2007.
[20] Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. J. Mach. Learn Res., 18(1):5325-3355 January 2017.
10

---

[21] Sham M Kakade, Shai learning with matrices. The Journal of Machine Learning Research, 13(1):1865-1890, 2012.
and Ambuj Tewari. Regularization techniques for
[22] Ehsan Kazemi, Thomas Kerdreux, and Liqiang Wang. Trace-norm adversarial examples. arXiv preprint arXiv:2007.01885, 2020.
[23] Thomas Kerdreux, Alexandre d' Aspremont, and Sebastian Pokutta. Projection- Free Optimiza- tion on Uniformly Convex Sets. arXiv e-prints, page arXiv:2004.1005,, April 2020.
[24] Peter M. Lee. The Probability Integral. York College.
[25] Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
[26] Marco Molinaro. Curvature of feasible sets in offline and online optimization. arXiv preprint WrXiv:2002.03215 2020.
[27] Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
[28) losif Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability, 2274)1167- 10 1994.
[29] Pavel Pokorny. Geodesics revisited. Chaotic Modeling and Simulation (CMSIM) 2012, page 281-298, 2012.
[30] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35 2010.
[3]] Amir Sani, Gergely Neu, and Alessandro Lazaric, Exploiting easy data in online optimization. Proceedings of the 27th International Conference Neural Information Processing Systems- Volume 1, pages 810-818, 2014.
[32] Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. CoRR, abs/1 2017.
[33] Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the 31st International Conference on Machine Learning. volume 32(2), 2014.
[34] Shai Shalev-Shwartz. Online learning and online convex optimization. Found. Trends Mach. Learn., 402):107-19, February 2012.
[35] Jhan-Phil Vial. Strong convexity of sets and functions. Journal of Mathematical Economics, 91122::17-2205 1982.
[36] Zuoqin Wang. Lecture 10: Tubular Neighborhood Theorem. University of Science and Technology of China.
[37] Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. CoRR. abs/1801 032650 2018.
[38] Dmitri Zaitsev. Differential geometry: Lecture notes. Trinily College, Dublin, Ireland, 2003.
[39] Julian Zimmert and Tor Lattimore. Connections between mirror descent, thompson sampling and the information ratio. In Advances in Neural Information Processing Systems, pages 11973-1199 1182, 2019.
[40] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. CoRR, Abs/1807.07623. 2018.
[41] Martin Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. pages 928-935. 2003.


Reviews:
[{"review_id": "zwkg_SA1b6", "reviewer": "Reviewer_grJg", "summary": "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.\n\nSimulations are provided that convincingly argue for the proposed method in the proposed setting. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 introduction is generally well written and the contributions are clearly explained and well-positioned in the literature. I think the results are impressive and that the ideas borrowed from differential geometry would be a great introduction to the neurips community.\n\nHowever, I found the sections requiring differential geometry to be hard to understand. For example, what is y on line 117 (a assume it is a typo for \\alpha)? Why is the statement on l120 \"the line from y_n...to any x has slope of absolute value Omega(\\sqrt{n}) true (in particular, please indicate that this is a high probability statement)? Why does alpha_n = beta_n (this only holds when sum a_n / n is not in \\mathcal X, which does happen with high probability), etc. A picture would help, too. You clearly have a strong geometric intuition, but it does not come through clearly. \n\nWhile I'm excited to see ideas from higher branches of mathematics percolate into this conference, their rarity means that there is significant burden on the authors to explain the ideas in way comprehensible to the community. I'm afraid that I don't feel this burden has been met in this submission. I feel that even the level of detail provided in the appendix may not be sufficient, but the main body definitely needs to be fleshed out. Some other questions I (and I would imagine other readers) would have are:\n-Since \\Vert\\cdot\\Vert is defined as the Euclidean norm, is geodesic distance in Definition 1 is always the Euclidean distance?\n- Please explain l130: the normal direction to the surface. Which surface?\n- How do you define a coordinate patch and what are its derivatives?\n- Additionally, most of the NeurIPS community will not think of derivatives as linear maps, so the notation \\nabla N(z)v will probably be confusing.\n\ntypos/suggestions:\nyou didn't define before using it\n\nIt would also be good to delineate which lemmas and propositions are novel and which are standard results from differential geometry. \n\nSo in summary, I'm very positive about the paper this submission could be if a better introduction to differential geometry were provided.\n\nPost-rebuttal: I believe the authors will revise the paper enough to clarify the presentation, so I increased my score.", "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": "3"}, "extra_text": {}}, {"review_id": "ciNricthRzW", "reviewer": "Reviewer_37jk", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "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 is a neat paper, and is especially cool because it uses differential geometry in a nontrivial way to say something non-obvious about the regret when the costs are stochastic. It is well known that OGD-style algorithms achieve $O(\\sqrt T)$ regret in the worst-case, and FTL gives low regret when the costs are stochastic, but this paper shows that in fact gradient-based algorithms can also achieve low regret when the costs are stochastic, at least if the domain is sufficiently smooth.\n\nA few questions/suggestions: first, I am interpreting the lazy online subgradient algorithm as special case of OGD, but with subgradients instead of gradients. In this case, the costs are linear, so one can just use gradients without resorting to subgradients. Is that correct? How does the lazy version differ from the greedy version? I think it would be helpful to add a few sentences in the introduction explaining the similarities/differences between the lazy online subgradient algorithm, the greedy online subgradient algorithm, and OGD.\n\nI believe that the bandit result of Zimmert and Seldin (2018) only works if one sets the step size knowing whether the instance is adversarial or stochastic. The authors may wish to point out that their analysis does not suffer from this restriction; the same step-size gets the optimal rate in both settings.\n\nIt may be interesting to say something about what goes wrong when the domain is not strongly convex. Can you show an example of a domain where the regret is $\\Omega(\\log T)$?\n\nTrivial points: the standard notation in online learning is to use $\\Pi_S(x)$ to denote the projection of $x$ onto the set $S$. The authors use $P_S(x)$ and may wish to consider altering their notation in the final version. Similarly, people generally use \"orthogonal\" instead of \"perpindicular\", especially when talking about geometries beyond $\\ell_2$.\n\nVerdict: Surprising result, clean analysis, timely problem. Clear accept.", "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": "1"}, "extra_text": {}}, {"review_id": "WZVheFnYAAZ", "reviewer": "Reviewer_e3cw", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "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": "Strengths:\n- The paper improves upon the state of the art results for online linear optimization in the strongly convex case\n- The result is elegant as it pertains to the basic online subgradient descent method instead of a more complicated algorithm\n- Online linear optimization is a significant problem\n\nWeaknesses:\n- My main concern is about the significance of the results given that the paper entirely focuses on the specific case of strongly convex domains. I'm not sure that the authors do enough to justify a paper that focuses entirely on this special case, and therefore I find the significance to be largely limited\n- Additionally, although it is nice that the results pertain to a simpler and more popular algorithm than prior results, the complexity bounds only improve slightly by a factor of $\\sqrt{log{N}}$ in the adversarial case.  \n- The writing of the paper can be improved substantially, both for clarity and language/grammar etc.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "BpuSQWThtPc", "reviewer": "Reviewer_THEd", "summary": "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. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Although the problem setting is very narrow, I feel the result is interesting. Unlike past works which come up with complex algorithms, the paper shows that a simple lazy sub-gradient method works well both in adversarial and stochastic settings.\n\nI found the paper to be a little bit terse. In particular, I'd appreciate a little bit more insights into proof techniques (maybe a high-level proof sketch before jumping into the proof of Theorem 1).  Also, I think a more thorough literature review needs to be performed (more on this below).\n\nHere are my main comments on the paper:\n1)  Regarding the experiments on the lazy subgradient method presented in Figures 1,2: similar to Figure 2b, can the authors try to fit a curve through the points (fit both D1*sqrt{n}+C1 and D2*log(n+1)+C2) and see which is a better fit? Do the experiments support the theory that the regret scales with log{N} in the stochastic setting?\n\n2) Regarding the greedy subgradient method: in line 244, the authors mention that the worst-case regret of this technique could be Omega(sqrt{N}) in the stochastic setting. This seems a bit counterintuitive to me. The greedy subgradient method is nothing but the projected stochastic gradient descent (SGD) method.  Projected SGD is a well-studied problem. Many works have shown that it converges at O(1/N) rate to an optimum for strongly convex losses (for example, see the works of Francis Bach). Given this, I find it a little bit hard to believe that for linear losses on strongly convex domains, SGD only converges at O(1/sqrt{N}) rate to an optimum. Can the authors explain this?\n\n3) I believe a more thorough literature review needs to be performed. One line of work that is missed is the optimistic online learning algorithms of [1]. Look at section 4 in [1] where the algorithms learn to adapt to the adversary. Can these algorithms not be made to adjust to the stochastic setting and achieve O(log{N}) regret?  \nGiven the relation between lazy subgradient method and SGD, some relevant literature on SGD should also be cited.\n\n4) As mentioned before, the setting considered in this paper is a bit narrow. So it would be good to see if the results can be generalized. Can the results be generalized to general convex functions on strongly convex domains? Will the same results hold for lazy Online Mirror Descent? \n\nFinally, please avoid revealing the funding sources in the future. This defeats the purpose of the double-blind review process.\n\n\n[1] Rakhlin, A. and Sridharan, K., 2013, June. Online learning with predictable sequences. In Conference on Learning Theory (pp. 993-1019). PMLR.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors adequately addressed the potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has received mixed reviews; while some reviewers found the results not super significant (essentially simplifying existing results in the literature) and the problem setting restrictive, others found the realization that simple plain lazy OGD is “universal” compelling, and the proof interesting and overall elegant.  All considered---and while I agree with the criticism---I think that there is a fair chance that the paper’s observations will draw some attention and promote further investigation, and I support its acceptance.

One remaining concern the authors should carefully consider is that the differential geometry background, and more importantly - the motivation and justification for appealing to such techniques, is lacking.  I trust the authors to improve this part of their exposition for their final version.

Decision: Accept (Poster)