Fully Unconstrained Online Learning
Authors: Ashok Cutkosky
Zakaria Mhammedi
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
online convex optimization
parameter-free
Primary area: online_learning
TL;DR: We provide regret guarantees without prior bounds on Lipschitz constants of comparator norms.

Abstract: We provide a technique for OLO that obtains regret $G\|w_\star\|\sqrt{T\log(\|w_\star\|G\sqrt{T})} + \|w_\star\|^2 + G^2$ on $G$-Lipschitz losses for any comparison point $w_\star$ without knowing either $G$ or $\|w_\star\|$. Importantly, this matches the optimal bound $G\|w_\star\|\sqrt{T}$ available with such knowledge (up to logarithmic factors), unless either $\|w_\star\|$ or $G$ is so large that even $G\|w_\star\|\sqrt{T}$ is roughly linear in $T$. Thus, at a  high level it matches the optimal bound in all cases in which one can achieve sublinear regret.

Fully Unconstrained Online Learning
Ashok Cutkosky Boston University ashok6cctkkosky.. com
Zakaria Mhammedi Google Research mhammedi@gooe com
Abstract
We provide technique for online convex optimization that obtains regret Gl w. wu.IyTlogg Tlo([Il.. [|V/ 1= G on G-Lipschitz losses for any com- parison point w. without knowing either G or ||w.]]l Importantly, this matches the optimal bound G| IVT available with such knowledge (up logarithmic factors), unless either |w. or so large that even w. IVT is roughly linear in T. Thus, at high level it matches the optimal bound in all cases in which one can achieve sublinear regret.
Unconstrained Online Learning
This paper provides new algorithms for online learning, which is a standard framework for the design and analysis of iterative first-order optimization algorithms used throughout machine learning. Specifically, we consider variant of online learning often called "online convex optimization" [1 2 Formally, an online learning algorithm is designed to play kind of "game" between the learning algorithm and the environment, which we can describe using the following protocol:
Protocol 1, Online Learning/Online Convex Optimization.
Input: Convex domain W c Rd number rounds
For t I..
1. Learner outputs w; W.
2. Nature reveals loss vector gr dl, for some convex function 4, W R to the learner.
3. Learner suffers loss (gt, w.).
The learner is evaluated with the regret (4 (www) against comparators w. W. By convexity, the regret is bounded by the linearized regret ΣT_ (gc. w. - w.). Our goal is to ensure that for w, simultaneously:
T Regret, (w.) Σ (gr, W. w.)
T Σ
S δ goal
I|w.
11g, 2-1
12
(I)
Qualitatively, we consider a learner be performing well if + ET - (w.)) is very small, usually going to zero T - This indicates that the average loss of the learner is close to the average loss of any chosen comparison point w. W. This property is called "sublinear regret". The bound (I) is unimprovable in general
5]. and clearly implies sublinear regret.
Algorithms that achieve low regret are used in a variety of machine learning applications. Perhaps the most famous such application is in the analysis of stochastic gradient descent, which achieves ① for appropriately tuned learning rate 66. More generally, stochastic convex optimization can be reduced
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to online learning via the online to batch conversion 77. Roughly speaking, this result says that an online learning algorithm that guarantees low regret can be immediately converted into a stochastic convex optimization algorithm that converges at a rate of [[Regret,[w.)] where w, is the minimizer of the objective. Online learning can also be used to solve non-convex optimization problems (8) and 12]. In all of these cases, achieving T
can even be used to prove concentration inequalities [1
the bound (T) produces methods that are optimal for their respective tasks. Thus, it is desirable be able to achieve ① in as robust manner possible.
Our goal is come close as possible to achieving the bound (1) while requiring minimal prior user knowledge about the loss sequence 91,.... and w., In the past, several prior works have achieved the bound (I) when given prior knowledge of either [w. or max; [ [13 14 15
16
17 18 19 20 21J. However, such knowledge is frequently unavailable. Instead, many problems are "fully unconstrained" in the sense that we do not have any reasonable upper bounds on either ||.I|| or max, [ In particular, when considering the application to stochastic convex optimization, the values for w. and maxe || can be interpreted as knowledge the correct learning rate for stochastic gradient descent [6]. Thus, achieving the bound (I) with less prior knowledge roughly corresponds to building algorithms that are able to achieve optimal convergence guarantees without requiring manual hyperparameter tuning. For this reason, it is common to refer to such algorithms as "parameter-free" free"" This paper focuses on this difficult but realistic setting.
Our new upper bound. Unfortunately, the bound ( is actually unobtainable in general without prior knowledge of either the magnitude ||w. or the value of max, lIgell [18 22]. Nevertheless, we will obtain a new compromise bound. For any user-specified y > 0, our method will achieve:
(gn w.) s o max 11 12/7 + w//w,, 12+ 1|.. Σ
Σ t=1
(2)
[c[T]
To dissect this compromise, let us consider the case I G for all t and = 1. In this situation,
our bound 2 is roughly G2 ||.,12 2 |w., IGVT, while the "ideal" bound 1 is merely [w,, I..I.VT.
However, for our bound be significantly worse than (1). we must have either G 2 ||.. Vic.l/VT or ||.,|| 2 GVT. In either case, we might expect that |w. is roughly (2(T) (assuming that neither G' nor |w.|| is very small). So, intuitively the only cases in which our bound is worse than the ideal bound are those for which the ideal bound already rather large-the the problem is in some sense "too hard".
Comparison with previous bounds Our bound is not the first attempted compromise in our fully unconstrained setting. Prior work 118 23 instead provides the bound:
T Σ (gt. wi w.) s δ ( max 1-1
1 (E[T]
Σ Ieell + +2? max [ge [.. 1 l| sc[2]
Σ
19
(3)
In fact, readers familiar with this literature may be surprised that our bound even possible; [18] show that the bound (3) is optimal for the fully-unconstrained case. However, the lower-bound provided by [18) actually has small loophole; it only applies to algorithms that insist on a linear dependence max, |.ge|l- Our method avoids this lower bound by instead suffering quadratic dependence on max, [9e]-
While our new bound (2) does not uniformly improve the prior bound (3) it has several qualitative differences that may be more appealing.
1. The bound ( does not have the desirable property outlined above for our new bound; for 19el G. is possible for the bound (3) to much greater than the ideal bound (T) even when ( small.
2. The dependency comes at LGVT cost while increasing gamma comes an >²|[w_]
the user-specified value y is arguably more sensitive; in 3 decreasing ? Iv..|$
cost. In contrast, in our
bound 3 the 7-dependencies are milder; G²/7 // for decreasing (which does not depend on T)
and 7 lt. for increasing 7-
The previous compromise bound has a term that depends on max, ll9.ll (ET (Iaell) rather than Σ/ 2 The dependence on the second power of [ is sometimes referred to

---

"second-order" bound and is known to imply constant regret in certain settings I 24 (so-called
"fast rates").
Consider the case that both bounds are tuned with their respective "optimal" values for y. Our
new bound would then reduce to Ö (1ta.. II Σi |1 + l|.. [IG] while the previous bound
1/3) ) Thus, our new bound would instead become δ [w., V Ei 1 lw, www.IG. ||| (Σ | appears more desirable even with individually optimal tuning.
5. Our bound ensures that when 0, the dependence T is O(1). This has a number of useful consequences, For example, by running separate instance of our algorithm for each dimension of d-dimensional problem,
achieve:
T Elgr we w.) Ō
d
T Σ gt
Σ max Ii.s
Σ
w.
1-1 re[T]
Attempting this with the bound 3 would incur significant dependence the dimension d. More generally, this property means that our bound fits into the framework for "combining" regret bounds of [25]
Notation
Throughout this paper, we use W to refer to convex domain contained in RRd Our results can in fact be extended Banach spaces relatively easily using the reduction techniques of [16). but we focus on Rd here to keep things more familiar. We use |. to indicate the Euclidean norm. Occasionally also make use other norms- will always be indicated by some subscript (e.g. ||. (|x). We use Reo to indicate the set of non-negative reals. For a convex function F over Id the Fenchel conjugate of F is F (0) s (0,v)) Fzz). We occasionally make use of a "compressed sum" notation: Pad == Σh_ 9t. We use O to hide constant factors and Õ to hide both constant and logarithmic factors. All proofs not present the main paper may be found in the appendix.
We will refer to the values provided to an online learning algorithm interchangeably as "gradients", "feedback" and "loss" values. We will refer online learning algorithms occasionally either "learners" or just "algorithms".
Overview of Approach
Our overall approach to achieve (2) is sequence of reductions. As first step, we observe that it suffices to achieve our goal the special case W E. Specifically, (16) Theorems 2 and 3 reduce the general W case to W R case. We provide an explicit description of how to apply these reductions Section C So, we focus our analysis on the case of the online learning protocol in which we also must contend with some potentially non-Lipschitz regularization function (Section B.I. Finally, we show how achieve low regret in this special
R. Next, we reduce the problem a variant
regularized setting (Section 3.3
3.1 Hints and Regularization
Our bound is achieved via reduction to a variant of Protocol [ with two changes. First, the learner is provided with prior access to magnitude hints h R that satisfy 1g: s h4 This notion of magnitude hints is also a key ingredient in the previous bound 3 Our second change is that the loss is not only the linear loss (ge, w), but a regularized non-linear loss (St, w) arr(ww) for some fixed function rb W E&o that we call a "regularizer". Formally, this protocol variant is specified in Protocol

---

Protocol 2. Regularized Online Learning with Magnitude Hints. Input: Convex function gi W For t I..
Rg0-
1. Nature reveals magnitude hint hy 2 h4-1 2 0 to the learner.
2. Learner outputs Wt e W.
3. Nature reveals loss 9t. with [@ell he and az [0,7] the learner.
4. Learner suffers loss (ōe, wx) awp(w)).
The learner is evaluated with the regularized regret Ei=lihh wi - -w.) + ax)((w)) - art(w..) The goal is to obtain:
T 1iall2
T
(ūr, Wt w.) ) arr((w)) arb(w. & o
Slwlly |ww
h
(b(w))
72
0i
goal
(4)
In the special case that (w) 0 (i.e. the a are irrelevant, or all 0) then various algorithms achieving
the desired bound (4) are available in the literature [18) 21 23 26). We provide in Algorithm 3
new algorithm for this situation that achieves the optimal logarithmic pareto-frontic of incomparable bounds that differ in the logarithmic factors. (26) provides the first algorithm to reach this frontier, while our method can achieve all points the fronticr" We include this result because it is of some independent interest, but it not the major focus of our contributions. Any of the prior work in this area would roughly suffice for our broader purposes; the difference is only in the logarithmic terms.
is in fact
Challenge of achieving (4) Achieving the bound 4 is challenging when |ww||| is not known ahead of time. To see why, let us briefly consider two potential solutions.
The most immediate approach might be to reduce Protocol to the case in which = 0 for all t by replacing 9. with ğr + a, Vei and then possibly modifying the magnitude hint h, in some way to now be a bound on llāell. However, this approach is problematic because the expected bound would now depend on ΣT= 1ge + ar Vv((() rather than Σd l0ell and Σ af. This means that the naive regret bound would be very hard to interpret as w, would appear on both the left and right hand sides of the inequality.
Another possibility is follow-the hhelowtthe-reulariizeee leader/potential-basee algorithm, making updates:
Wp++ argmin Pr(w) Σ (ūi, w) awv(w),
weW
for some sequence of "potential functions" P.: - R. In fact, this approach can be very effective; this is roughly the method employed by (7 for a similar problem. However, deriving the correct potential Pt and proving the desired regret bound can be very difficult, and could casily require separate analysis for each different possible & function. For example, [27]s 's analysis specifically applics to v () = |w|2. There is other work on similar protocols using approximately this method, such as [28 29 that also requires particular analysis for each setting. Finally, even if the bound can be achieved in general using this scheme, solving the optimization problem (5) may incur some undesirable computational overhead, even for intuitively "simple" regularizers such (((w) || In fact, the method of (27) suffers from exactly this issue, which is why we provide an alternative approach in Section 3.3 for the special case of interest that W IR.
Re-pa pe-rarmmetriiing to achieve
In order to achieve the bound (4 in the special case W = R. we will employ a standard trick in convex optimization: re re-parametrizing the objective as a convex constraint using the fact that the epigraph of a convex function is convex. Instead of having our learner output W; W. we will output (z),81) W x R. but subject to the constraint that yı (xx). We provide details this approach in Section 3.3
It is likely that the approach of [26 in concert with the varying potentials of 20 would achieve all points on the frontier as well, although our analysis takes a different direction using the centered mirror descent method of 21

---

With all of these technicalities introduced, we are ready to provide an outline of our method. The key idea to show that for a very peculiar choice of coefficients 01...., or and some simple clipping of the gradients Gt. we are able to achieve the following result.
Theorem 1. There exists an online learning algorithm that requires (dd) space and takes (dd) time per update, takes as imput scalar values y, h and e and ensures that for any sequence 91. 92. : C Rd. the outputs wi, w1,-.. R satisfy for all w, and T::
T Σ (gt, wi w.) s J eG +GeEIG+ e
G Llog(e: (et
G )
IV..VVIn log 2 (T)
||c,111
Vlog
V
e
7
h1
h1c
lw. IVVlog
Iw.,1" e2
G c+
Am ]
Htw.IGlog/ c+
+ + s/w.
1 12
c+
log
hic
where G = maxer]) (1 and V G2 ETe 19el?
[Tx
Before proving this result, let us briefly unpack the algebra in the statement to see how it relates to our originally stated bound (2). Notice that if we drop all the logarithmic terms, the bound becomes:
T Σ (gc. wi - ) s ó eG + e2 G + leo. ?
V
Σ 1 2 Iw. || 2/,,,
Here if we should think of li and as conservative under-estimates of max, l1 and l|.. I. Notice that decreasing hı and e only increases the terms inside the logarithms, so that in some sense the algorithm is very robust to even extremely conservative under-estimation. When it holds that h1 S max, [ige|] and < w. []. then the above bound is exactly the previously stated equation (2)
3.2 Proof Sketch of Theorem
Let us suppose for now that we have access to an algorithm that achieves the bound 44 under Protocol 2 Let us call it REG. In this section, we will detail how to use REG to achieve our desired goal 22) under Protocol [ with W = R: in this sketch, we treat all values as sealars, and never vectors. Recall that it suffices to consider W = R to achieve the result in general. Given output wy from REG, we play Wi and observe the gradient gt- We will then produce modified gradient 9s. a scalar at. and magnitude hint h4+1 to provide REG such that 인. and a satisfy the constraints of Protoco! 2 We will set vo( (w)) = w², and then by careful choice of gt. at and h41,, we will be able to establish Theorem [
There are two key steps in our reduction. The first step is now a standard trick originally used by [18, 23 30 to reduce the original Protocol [ to Protocol 2 The idea is as follows: let us set 14 = max (i,,
19t--l)) for some given "initial value" hn O. Notice that dy may be computed before 9i is revealed and that the value G specified in the theorem satisfies G = hT--1- Then, upon
1911,--............... 1911
receiving gradient It, we replace Jt. with the "'lipped" gradient J. = (1 (n)) - Ir- The clipped
gradient ÿe satisfies |ğel & h2 by definition. We then pass ÿ in place of ge to an algorithm that interacts with Protocol
2 It is then relatively straigh straightforward to see that for all w. W:
T
T
Σ ge: - w.) s
Σ Je (wi- w.)
l3e gell + 1-1
Σ
loe gall wall Σ 1
1
$
(he+1 - h:) Σ Je (wi w. + hT Σ
1
At this point, prior work [18 maximum value D, then the final summation above is at most h. By carefully choosing D in tandem with an algorithm that achieve (4) in the case (ww) = 0, one can achieve the previous "compromise" bound 3).
23 observed that if we could constrain |wy| to have some chosen
This is where our second key step (which is our main technical innovation) comes in. Instead of explicitly enforcing |wr] D, we will apply a "soft constraint" by adding regularizer. Surprisingly, we will add a very tiny amount of regularization and yet still achieve meaningful regret bounds.
5

---

Recall that we are assuming access to an algorithm that achieves the bound 4 when interacting with Protocol 2
Let us set (w)) w². Then, observe that for any choices of a1 ,1....,,77 ar:
T
T Σ 1=1
T
Σ 96 wi - w.)
Σ
(āl (w - w. + ar.(() +
90 gulloa1 1 + w Σ
1-1
T (lō+ gellvorl arw)))
+
Σ
t=1
(ge(wr - w. + (w:) (w.) + +hr+1/
w
Σ t=
+ Σ a1
(h1+11 lw0d aww,
t=
cuntrolled by
needs small
needs big
From the above decomposition, a such that Σt a, is small, but also a, is large enough that Σi ((he-1 he hh))lu axu?) is also small. It turns out that this is accomplished by the following choice for a,:
that to make the overall regret small, would like to choose
(be-1 he) he)/he-1
a = 7 1 +L (h++1 ha)/hat1
Here, y is an arbitrary eser-specified constant. Notice that the value of he-1 available immediately after is revealed, so that it is possible to set this value of a, Moreover, it is clear that [0. 7] for all I.
Let us see how this value for 0r satisfies our desired properties. First, recall the bound log(p + g) log(g) 2 _ for any p.q 0, which implies Σ Σ.no I log (E Pt/Po) for any sequence of positive numbers .o..... ... PT.
p+g
From this, have:
(he he)/
Σ 1-1
at Σ
1 (hir h&) (heri
1-1
$ y log
1+
E
S yoo (1 + log (G/ha)).
Thus, Di, Og is in fact doubly logarithmic in the ratio between hy and hr+11 max(hi, max; [9:)) G.
Next, let us check that is "large enough" to make Ehe - -ho)lwal a:w, small. To this end, observe that:
(het1 h4) hoee aw sup(h4+1- -h)) xxx2
X
(he+1 - h1)²
4az
h (he+1 (911-hi) h1))
1+
Σ
(hit1 ha)/
47
F=1
hT+ (ba-1 -1e)
(1
1+
Σ (hitz h1)) ht))/
47
G(hu+1-1u (1 log(G//g)))
47
where we used that G = hr Thus, we have:
T Σ ((h41 (hhna-ha)lodd amw?) 4y
G²
(1 (1+log(//ha))
This shows that o is large enough that is able to counteract the effect of ΣT= (he+1 -hx)lwxl (which makes the regret large if |uy| large). is tempting to conclude that the regularizer is somehow "implicitly constraining" W, to be small enough that the regret is bounded. However, it is difficult

---

to envision exactly what constraint is being enforced; notice that to make Σ (h++1 bo)/ Ö(G²/>) by applying some constraint |wy] D, we would need to set D Ö(G/)) However, such an aggresive constraint would surely prevent us from achieving low regret for even relatively moderate |w.| G/y. So, our regularization seems to be doing something more subtle than simply applying a global constraint to the W, s. Indeed, notice that in the case [9t| $ h1 for all t, we actually have a, 0 and
constraint effect at all is enforced!
The final step we need to check is bounding Σ/- 9e (w, - w. au w.) - at u (w.). ) To this end, we provide in Section 3.3 an algorithm that achieves the following bound, which is slightly weaker than
(ār (wi w.) + acc((ws) (w.)(
Ww.lVV log"((? (T)
lwa VVloVologeee logg((() hie
0 cvr |w:ly
Vlog
+ lu-l/er log
hie
|w. |w.I2//1og (1055())
lw. PiV (7)
+c² w.y Slog
c+
ww, 11 log
c+
y
7e2
where S ==2 7 Et Og. This bound is weaker than (4) due the presence of S rather than
y² Σi- az. Nevertheless, by our bound on Σin as, we have:
S + log (1 + log (G/h1))
so that combining all of the above calculations we establish Theorem
Thus, it remains to establish how we achieve (4) the slightly weaker (but sufficient) statement above. We accomplish this next in Section 3.3
3.3 Regularized Online Learning via Epigraph Constraints
Recall that our approach to obtaining is replace the regularization terms in the loss with constraints. Formally, consider the following protocol:
Protocol 3. Epigraph-based Regularized Online Learning for W R. Input: Convex function d/ IR TR.
For t I....,T:
1. Nature reveals magnitude hint h2 2 h/-1 to the learner.
2. Learner outputs (It, Vi) R x R with 2 (1xx)..
3. Nature reveals [-h,, he] and a, [0, 7 to the learner.
4. Learner suffers loss ğr3,+ deft.
The learner evaluated with the linear regret ΣT, gt (x+ w.) + ax(ur - (w.))) The goal is to obtain:
T
T
(g, 1o--w w.) ae( (.w s
l.w.lly
1 Σ ot + v(w.)
V
72
Σ
a
(6)
goal
The key fact about this protocol the observation that by setting w, Fe, the bound 6 immediately
implies 4 To see this, recall that (ww) 2 O, 0. and vxxx)) = 2 ww)) so that:
Σ ((r, - w.) axp((w)) a, d (w.)) s Σ ((g,, Lt - w.. + arht awb((w)))
So, achieve under Protocol it suffices achieve the bound 6 under Protocol
There is one tempting approach that almost, but not quite, achieves this goal. One could employ the "constraint-set reduction" developed in [16] that converts algorithm that operates on the

---

that "unconstrained" domain R x R to one respecting the constraint 2 (xx). In particular, it is relatively straightforward to build an algorithm that achieves (6) without requiring yr 2 (xx). This unconstrained setting can be handled by the classic "coordinate- wise updates" trick in which we run two instances of an algorithm achieving (4) the special case that ((()) O, one of which will output 2; and receive feedback It. and the other will output y/ and receive feedback dr- Then, by the individual regret bounds on both coordinates, we would have:
I g( (20 - -.. Σ
Σ (06(2 - w.) av( (l(())))))))))))))))))))))))))
Σ ge
aell - v(w)))
sō
11 +
g0 + (ww)
72+
Σ o
Then, one might hope that applying the constraint-set reduction of [16] would allow us to apply the constraint W without damaging the regret bound. Unfortunately. this reduction will modify the feedback yt and in such way that Σt oz could become much larger, which makes this approach untenable in general.
Fortunately, it turns out that our particular usage will enforce some favorable conditions make the above strategy viable. Specifically, the choices of St. hú and a, described in Section 3.2 satisfy the condition that 0 unless ( ft. By careful inspection of the constraint-set reduction, is possible show that the above strategy achieves slightly weaker version of (6):
I Σ gc(xx - w.) ae (ww))) s S 1=1
[...
Σ 96 + (w.)
y Σ T=1
at
(7)
As detailed in Section 3.2 this weaker bound suffices for our eventual purposes. Nevertheless, for the reader interested in fully general solution, in Appendix H. we provide method for achieving (6) without restrictions. We do not employ it in our main development because involves solving convex subproblem at each iteration and so may be less efficient in some settings. This technique does however involve small improvement to so-called "full-matrix" regret bounds (31), and so may be of some independent interest.
Lower Bounds
In this section, we show that the result of Theorem [ tight. In fact, we show stronger result that generalizes our extra penalty term from / 7/|w,, to (p([w,]) yab" (G/7) for any symmetric convex function v5, where 1 (x) = sup, zz - (=)) the Fenchel conjugate of t. That is, we provide a Pareto frontier of different lower bounds and Theorem is but one point on this frontier. In Appendix A we extend our upper-bound results to match any desired point on this frontier (up to logarithmic factor). We also provide matching upper bounds (up to logarithmic factor) in Theorem I6 as well as more simplified
+ is convex, symmetric, differentiable, non-negative, achieves its minimum at (0) = O, and (xx) is strictly increasing for non-negative x. Further suppose that for any X, Y, O, there is some T such that for all T 2 T,
Theorem 2. Suppose
exp(T) 1 XVTV (YT)
X (YTZ)2TZ
where 32' sup is the Fenchel conjugate of v). Let h 0, and e 0 be given. For any online learning algorithm A interacting with Protocol 7 with W R. there a To such that for any T To. there is sequence of gradients . ,T and such that the outputs W1 W1,.... WT of A satisfy:
T Σ ge wt w. 22G 2 I Iw(w))
+ Glw,1
Glw.lvT hiE
Tlog 1
4
4
8

---

where G = max(h1.9x ................................ .r)) In particular, with (xxx) x1 for any > O, we can ensure:
T Σ C - w.) 1 eG + 7/11 7/0,1100 Glw.lyy IN Tlog 1
G1-1/9
Glw.lvT)
The conditions on vi" in this bound are relatively mild. The first condition says that the gradient V should not grow exponentially fast. The second condition says that vे should grow faster than some linear function. So, any polynomial of degree greater than satisfies these conditions.
We note that this lower bound leaves something to be desired in terms of the quantification of the terms. Here, the value of G and |w, depends on the algorithm A. This is a critical factor in the proof; roughly speaking, the proof operates by providing the algorithm with a constant gradient 9i = h1 at every round. Then, if the iterates Wi; grow in some sense "quickly", we "punish" the algorithm with very large negative gradient, which causes high regret if w. 0. Alternatively, if the iterates do not grow quickly, then we show that the regret is large for some w. >> 1. This approach is common idiom for lower bounds in the fully unconstrained setting [18] 22
However, a much better bound might be possible; ideally, it would hold that for any G and ||w. | and algorithm A. we can find sequence of gradients Si that enforces either |/. or max; [g.. is provided to the algorithm, the lower bounds available do take this form We leave as open question whether it is possible to do so in our setting.
desired regret. Indeed, when
3 [1.
5
Discussion
We have provided a new online learning algorithm that achieves a near-optimal regret bound (2)- Our algorithm is "fully unconstrained". or "fully purameter-free", in the sense that we achieve near-optimal regret bound without requiring bounds on the gradients Ji or the comparison point w..
Prior work in this setting [18 21 22 23 26] achieve bounds that technically incomparable, but may be aesthetically less desirable, as detailed in the discussion following (3). Nevertheless, ideally we would have a unified algorithm framework capturing both our old and new bounds. It is an open question whether more careful choice of regularization in our approach could achieve this goal.
Our algorithm takes as input parameters /1 and 7. All of these have pleasingly small impact on the regret bound. e and h2 can be interpreted as very rough estimates of [w. and G. As these quantities go to zero, the regret bound increases only logarithmically. Moreover, these estimates can be too high by a factor of /T while still maintaining O(1 |ww |GVT) regret. The quantity ? represents an estimate of G/ [l.... I.- As discussed in Section this value does not appear in any term that has T -deepeddnnce in the regret bound and so also has very mild impact on the regret.
While our bound has several intuitively desirable characteristics, it is missing one important property: our bound suffers from an issue highlighted by (18) called the "range-ratio" problem. That is, the bound depends on the ratio G/hh, which could be very large if the losses are rescaled by some arbitrary large number without rescaling h1 This issue is at the heart of how we are able to sidestep the lower-bound of [8]. which appears to apply to all algorithms that do not suffer from the range-ratio problem.
5.1 Other forms of Unconstrained Online Learning
Our results focus on the case that we have no prior bounds on the value of |[w.]] or l[ge and our bounds eventually depend on max, |. One might worry that this is too conservative in some settings. For example, it might be that g: known to be a random variable with bounded mean [[9:]] & G and variance Var(g:) s o² for some known G and a. In this case, max, I might become large even though intuitively our regret should still depend only on G + a. This is the setting considered by several prior work on online learning with unconstrained domains (9]
17 32). Under various assumptions, these results all achieve an in-expectation regret bound of E Regretty(w..). S Õ( [I T))TT.
In fact, our results come close to this ideal even without knowledge of G. For example, (9 17 study the case of sub-exponential gi that satisfy sup]alsı [[(xp(5(0: E[9+],a))] & exp( (32 (2) for all
| 1/6 for some b O. In this case, for I-dimensional gt. we have m[[ g Ō(G² x²) and

---

so in expectation we achieve Ö( IG arbitrary dimensions can then be achieved via the black-box reduction of [16). However, in the case that Dr has some heavy-tailed distribution such studied by (32). it is less clear that our bounds achieve the desired result out-of-the box. Discovering how to achieve this is an interesting direction for future study.
+lww,11) (the extension from 1-d to
5.2 Parameter-free Algorithms and Stochastic Convex Optimization
As discussed in the introduction, common motivation for the study of online learning is its immediate application to stochastic convex optimization through various online-to-bated conversions, The classic conversion of [7). as well few more recent results [33 34 35| 36) all show that if g: is the output of stochastic gradient oracle for a convex function F. then for any w. argmin F
E [Regret((..)
E
F
Mix - F(w.)
T
If Igd S G with probability 1 (for an unknown G), our Theorem immediately implies F
Zinl F(w..) T
s s
[m, |G
G//+tpllul"") The first term is the optimal rate for stochas-
VT
|w. if G and [|w., tic convex optimization that can be achieved via SGD with learning rate 1) GVT are known ahead of time, and the second term is lower-order "penalty" for not having up-front knowledge of these quantities.
Convergence results that match that of optimally tuned SGD are often called "parameter- (the parameter in question is the learning rate). As mentioned in the introduction, there has been a long line of works that attempt to achieve this goal by matching the regret bound (T.. which can then be applicd to the stochastic setting via online-to-batch conversion. More recent work parameter-fre optimization has considered the stochastic case (37,38) 38). or deterministic case (39 directly without passing through general regret bound. Many of these algorithms have shown significant empirical promise, even for non-convex deep learning tasks [38
Almost all of these results
require apriori knowledge of the value C
To place our results this context, let us focus on the case a known G value, this case, [37 show that by eschewing regret analysis and focusing specifically on the stochastic setting, it is possible to achieve a high begb-brobability guarantee that improves upon the logarithmic factors achieved by our result, and so there seems be something lost by focusing regret bounds. However, in surprising counterpoint, [44) shows that if one is interested in an in-expectation result, then there is actually no way improve upon the logarithmic factors achieved via online-to-batch conversion when applied to parameter- free regret bounds. Thus, our ex-eeeectaiion stochastic convergence rate is optimal even up to logarithmic factors, while also do not require prior knowledge of G.
Finally, let us evaluate the optimality of our bound in the stochastic setting while accounting for the fact that our methods do not get to know either G or |/ |l. Here, we can again make use of the lower bounds developed by [44). Consider the class of stochastic convex optimization objectives with Lipschitz constant G between and L and www
RJ. The "price of adaptivity" (4] is the maximum over this class of the ratio between the convergence guarantee of an algorithm that does not know ||w.] and G with respect to the minimax optimal convergence guarantee for an algorithm that does know these values (which is RG/VT). We achieve price of adaptivity of Ō(1+ max(T. [L, R)/VT). The best-known lower bound for this class Q + min(L. R)/VT) [44] Thus, there is gap here-althougll we provide matching lower bounds for the online setting, it is possible that in the stochastic setting, one can improve our bounds. That said, the stochastic lower bound is derived for algorithms that are given the ranges L] and [1, RJ. Our algorithm does not use this information and also plausible that without such knowledge the lower bound itself would improve.
defined by
Acknowledgements
AC supported by NSF grant number CCF-2211718.
Thhe difference hetween these conversions lies where the stochastic gradients g, are computed.
A few exceptions achieve the prior bound 18
21
23
43
10

---

References
[1] Francesco Orabona. "A modern introduction to online learning". In: arXiv preprint
arXiv:1912.13213 (2019).
[2] Elad Hazan. "Introduction to online convex optimization". In: arXiv preprint 1rXiv:1909.0000 (2019).
[3] Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. "Optimal strategies and minimax lower bounds for online convex games". In: Proceedings of the nineteenth annual conference compulational learning theory. 2008, pp. 415-424.
[4] Brendan Mcmahan and Matthew Streeter. "No-regret algorithms for unconstrained online convex optimization". In: Advances in neural information processing systems. 2012, pp. 2402- 2410.
[5] Francesco Orabona. "Dimension-Fe free exponentiated gradient". In: Advances in Neural Infor- mution Processing Systems. 2013, pp. 1806-1814.
[6] Martin Zinkevich. "Online Convex Programming and Generalized Infinitesimal Gradient Ascent". In: Proceedings of the 20th International Conference on Machine Learning (ICML- 03). 2003, pp. 928 936...
[7] Nicolo Cesa-Bianche Alex Conconi, and Claudio Gentile. "On the generalization ability of on-line learning algorithms". In: Information Theory, IEEE Transactions on 50.9 (2004),
pp. 2050-2057.
[8] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. "Optimal Stochastic Non-smooth Non- convex Optimization through Online-to-Non-comme Conversion", In: International Conference on Machine Learning (ICML). 2023.
[9] Kw Kwang-Sung Jun and Francesco Orabona. "Parameter-frre online convex optimization with sub-exponential noise". In: Conference on Learning Theory. PMLR. 2019, pp. 1802-1823. [10] Zakaria Mhammedi. "Risk monotonicity in statistical learning". In: Advances in Neural Information Processing Systems 34 (2021), pp. 10732-10744.
[11] Francesco Orabona and Kwang- -ung Jun. "Tight concentrations and confidence sequences from the regret of universal portfolio". " In: JEEE Transactions on Information Theory (2023).
[12] Gábor Lugosi and Gergely Neu. "Online-to-PAC conversions: Generalization bounds via regret analysis". In: arXiv preprint arXiv:2305. 19674 (2023).
[13] Elad Hazan, Alexander Rakhlin, and Peter Bartlet. "Adaptive online gradient descent". In:
Advances in Neural Information Processing Systems. 2008, pp. 65-72.
[14] J. Duchi, E. Hazan, and Y. Singer. " "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization". In: Conference on Learning Theory (COLT). 2010, pp. 257-269..
[15] H. Brendan McMahan and Matthew Streeter. "Adaptive Bound Optimization for Online Convex Optimization". In: Proceedings of the 23rd Annual Conference on Learning Theory (COLT). 2010, pp. 246-256.
[16] Ashok Cutkosky and Francesco Orabona. "Black-Bo Reductions for Parameter-fre free Online Learning in Banach Spaces". In: Conference On Learning Theory. 2018, pp. 1493-1529.
[17] Dirk van der Hoeven. "User-specified local differential privacy in unconstrained adaptive online learning". In: Advances in Neural Information Processing Systems. 2019, pp. 14103- 14112.
[18] Zakaria Mhammedi and Wouter M Koolen. "Lipschitz and Comparator-Norm Adaptivity in Online Learning". In: Conference on Learning Theory (2020), pp. 2858-2887.
[19] Liyu Chen, Haipeng Luo, and Chen-Yu Wei. "Impossible tuning made possible: A new expert algorithm and its applications". In: Conference on Learning Theory. PMLR. 2021, pp. 1216- 1259.
[20] Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis. "Pde-based optimal strategy for unconstrained online learning". In: International Conference on Machine Learning. PMLR. 2022, pp. 26085-261 15.
[21] Andrew Jacobsen and Ashok Cutkosky. "Parameter- free Mirror Descent". In: Proceedings of Thirty Fifth Conference on Learning Theory. Ed. by Po-Ling Loh and Maxim Raginsky. Vol. 178. Proceedings of Machine Learning Research. PMLR, 2022, pp. 4160
[22] Ashok Cutkosky and Kwabena Boahen. "Online Learning Without Prior Information". In: Conference on Learning Theory. 2017, pp. 643-677.
11

---

[23]
Ashok Cutkosky. "Artificial Constraints and Hints for Unbounded Online Learning". In Proceedings of the Thirty-Secone Conference on Learning Theory. 2019, pp. 874-894. Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. "Smoothness, low noise and fast rates".
[24]
In: Advances in neural information processing systems. 2010, pp. 2199-2207.
[25] Ashok Cutkosky. "Combining Online Learning Guarantees". In: Proceedings of the Thirty- Second Conference on Learning Theory. 2019, pp. 895-913.
[26] Zhiyu Zhang, Heng Yang, Ashok Cutkosky, and loannis Ch Paschalidis. "Improving Adaptive Online Learning Using Refined Diseretization". In: arXiv preprint arXiv:2309. (2023).
[27] Andrew Jacobsen and Ashok Cutkosky. " "Unconstrained online learning with unbounded losses". In: International Conference on Machine Learning. PMLR. 2023, pp. 14590-14630.
[28] Jack J Mayo, Hédi Hadiji, and Tim van Erven. "Scale-free unconstrained online learning for curved losses". In: Conference on Learning Theory. PMLR. 2022, pp. 4464-4497.
[29] Gergely Neu and Nneka Okolo. "Dealing With Unbounded Gradients in Stochastic Saddle- point Optimization". In: Proceedings of the 41 International Conference on Machine Learn- ing. PMLR. 2024, pp. 37508-377 -35000
[30] Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. "Lipschitz adaptivity with multiple learning rates in online learning". In: Conference on Leurning Theory, PMLR. 2019, pp. 2490- 15
[31] Ashok Cutkosky. "Better full-matrix regret via parameter- free online learning.. In: Advances in Neural Information Processing Systems 33 (2020), pp. 1336-8866.
[32] Jiujia Zhang and Ashok Cutkosky. "Parameter-free regret in high probability with heavy tails". In: Advances in Neural Information Processing Systems 35 (2022), pp. 8000-8012.
[33] Ashok Cutkosky. "Anytime Anline-to-Batche Optimism and Acceleration". In: International Conference on Machine Learning. 2019, pp. 1446-1454.
[34] Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. "UniXGrad: Universal, Adap- tive Algorithm with Optimal Guarantees for Constrained Optimization." In: NeurIPS. 2019,
pp. 6257-6266.
[35] Aaron Defazio, Ashok Cutkosky, Harsh Mehta, and Konstantin Mishchenko. "When, Why and How Much? Adaptive Learning Rate Scheduling by Refinement". In: arXiv preprint urXiv:2310.0783 (2023).
[36] Aaron Defazio, Harsh Mchta, Konstantin Mishchenko, Ahmed Khaled, Ashok Cutkosky, et al. "The Road Less Scheduled".. In: arXiv preprint arXiv:2405. 15682 (2024).
[37] Yair Carmon and Oliver Hinder. "Making SGD Parameter-Free In: Conference on Learning Theory (2022).
[38] Maor Ivgi, Oliver Hinder, and Yair Carmon. "Dog is sgd's best friend: A parameter-free dynamic step size schedule". In: International Conference on Machine Learning. PMLR. 2023, pp. 14465-14499.
[39] Aaron Defazio and Konstantin Mishchenko. "Learning-rate-fffe free learning by d-adaptation". In: International Conference on Machine Learning. PMLR. 2023, pp. 7449-7479.
[40] Francesco Orabona and Tatiana Tommasi. "Training Deep Networks without Learning Rates Through Coin Betting". In: Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach,
CA, USA. 2017, pp. 2157-2167
[41] Konstantin Mishchenko and Aaron Defazio. "Prodigy: An expeditiously adaptive parameter- free learner". In: arXiv preprint arXiv:2306. 06101 (2023).
[42] Ashok Cutkosky, Aaron Defazio, and Harsh Mehta. "Mechanic; A Learning Rate Tuner". In: Advances in neural information processing systems 36 (2023).
[43] Zhiyu Zhang, Heng Yang, Ashok Cutkosky, and Ioannis C Paschalidis. "Improving adaptive
online learning using retined discretization". In: International Conference on Algorithmic Learning Theory. PMLR 2024, pp. 1208-1233.
[44] Yair Carmon and Oliver Hinder. "The Price of Adaptivity in Stochastic Convex Optimization". 1408.
In: arXiv preprint Urruty and Claude Lemaréchal. Fundamentals of convex analysis.
(2024).
[45] Jean- -an-tBptiste Hiriart-Urutty
Springer Science& & Business Media, 2004.
[46] Ashok Cutkosky and Tamas Sarlos. "Matrix-Free Preconditioning in Online Learning". In: International Conference on Machine Learning. 2019, pp. 1455-1464.
12

---

[47] Zakaria Mhammedi and Alexander Rakhlin. "Damped online Newton step for portfolio selec- tion". In: Conference on Learning Theory. PMLR. 2022, pp. 5561-5595.
[48] Zakaria Mhammedi and Khashayar Gatmiry. "Quasi-newton steps for efficient online exp-
concave optimization". In: The Thirty Sixth Annual Conference Learning Theory. PMLR. 2023, pp. 4473-4503
[49] Khashayar Gatmiry and Zak Mhammedi. "Projection- Online Convex Optimization via Efficient Newton Iterations", In: Advances in Neural Information Processing Systems 36 (2024).
[50] Francesco Orabona and Dávid Pál. "Coin Betting and Parameter- Freee Online Learning". In: Advances in Neural Information Processing Systems 29. Ed. by D. D. Lee, M. Sugiyama, U. V. Luxburg. I. Guyon, and R. Gamettt. Curran Associates, Inc., 2016, pp. 577-585.
13

---

A Generalized Upper Bounds
In Theorem T we provide bound that achieves the "ideal bound" of (T) with an extra penalty term of roughly / w. It turns out that this penalty is but one point on frontier of potential choices that are all immediately accessible by simply changing 4 (w) from |wl to any other symmetric convex function, outlined in the lower bounds of Section Here we state formally that each of these bounds is achievable. particular, by setting (b(w) = w|l" I+q for any q > O, we have:
Theorem 3. There an online learning algorithm that takes as input positive scalar values q, 7s his and and ensures that for any sequence 91 19,, -- RR, the outputs w1; W1, ... c R satisfy for all w, and T:
[w. Iw.IvV log (I)
Σ (gt, We w.) S0
eG 1w-ll
V log
e+
hic
ww.llv Iw.lvVlog (T)
+ +||u,|| Glolg
c+
hiE
/w.111g clay
log (e+ G hm )
Gl-1/1
G G//1/97 h1
1/9
+ y/w.11 "00
71/0 log
1+ log
where G = max maxx max (1 and V = G2 Et-1 loel1..
Finally, it is also the case that the logarithmic terms in our bounds can be adjusted to remove the T' dependencies, at the cost increasing the regret in the case w, 0. This is achieved simply by
adjusting the logarithmic factors achieved by the algorithm for regularized online learning (Protocol
manner similar to other recent works in unconstrained online optimization 20 26). Formally,
we can achieve:
Theorem 4. There is an online learning algorithm that takes as input positive scalar values hi and and ensures that for any sequence -..92.-.. Rd, the outputs w1, w,, R satisfy for all w. and T:
T
)
|w-||
)+ + ||.. Gl
( Wi w.) s O
EVV
/w-lly
V Vlog
+c m
1 log log
(
G
+ +y|w,1 100 log c+ Iwo 11 log
e
G
111
elog
h1
G1+1/g
G
1/4
+ 7//9
log 1 log
h1
where G = maax(h,,) max, Igrl) and V G2 ΣT, 19
Both of these results are immediate corollaries Theorem 16
14

---

B Proof of Lower Bound
We restate and prove Theorem 2
Theorem 2. Suppose & R R is convex, symmetric, differentiable, non-negative, achieves its minimum at (0) = O, and (x) is strictly increasing for non-negative a. Further suppose that for any X, Y, Z O, there is some such that for all T
exp(T) X (YTZ) TZ
X (YT)
where 3i z zz=z(zz) is the Fenchel conjugate of tb. Let h1 > 0, > and > 0 be given. For any online learning algorithm A interacting with Protocol 7 with W R, there is To such that for any T Ty. there is a sequence of gradients 9 9r and a w. such that the outputs W1..... WT A satisfy:
Σ se( w.) 2 cG ww (Gh)) + (w.)) Gwv.
Glw.lVT
Tlog +
4
h
where G = max 001. (1..9)......9 gT) In particular, with vxxx) 1 for any q > 0, we can ensure:
T Σ ge w.) 2 eG + 7//9 7/w,11 1 Glw.ly Tlog 1
G1-1/1
Glw.lv/
h
Proof. First, let us define (x) (x)) Let V (x) and (0) indicate the derivatives of t) and oi. The following properties are standard facts about the Fenchel conjugate (see e.g. [45
(0) rp- (0/7).
(0) 0,
(1(x) 0 for all x,
(x(x) (ei(()) - (V,
(0) vv) -0) (v
Moreover, Vely and V are inverses of each other and are odd functions, and (x) is strictly increasing for non-negative x.
Next, observe that for any X,Y,X' Y', Z', there is a such that for all T2 T:
exp(T) 11 XVTV0' X' (Y'TZ') 2 TZ'.
(8)
(9)
To see this, observe that by assumption, there is a тı such that (8) holds for all T T2, and also a T2 such that (9) holds for all T T2. may take max (T, T2) achieve both simultaneously.
From this, we see that there is some To such that for all T To:
2/T
2/T
exp (7) 12
Vo
(2Th,/7)
(2Thn)
(10)
2Thh
The S
(2Thi)
(11)
32c
7
32c
We now construct the algorithm-dependee sequence 91, ... that satisfies the claim of the theorem.
1. Define Do and
2. Algorithm A outputs Wi-
3. If w, <-2c- Vy, (2h, 1)), set ge -2(t 1)h, and for all k 1 set g4tk 0.
4. Else gt h1-
15

---

5. Set t + ++ and go to Item 2
Suppose that the condition in Item has not been triggered for the first iterations. Then, we have:
gt 1
Σ (2)( (1)(t)))))))) 2h1.
1=1
2 --2th11
Σ (b), (2th1) 1)1)).
(by convexity of (57))
t=1
-2 2 (27h1).
(12)
Now, suppose that the condition in Item and with W. = O, we have:
B is triggered at some iteration 7+ 1 1. Then G 2rh1
T
7+1 Σ
Σ 9: (wi w.)
9:
wt:
1=1
= +r+1 1++1 +
W/ It:
1=1
1
2 4crh1 V (2th1) 2Th1 2cth1 2 (2Thn)), (by (12)
1 1 (2Th1);
2erhi (2rh1) 2rh1 (2
thy (VV, (2hh))
= 2erhy , (2Th1) + bhy (2 ~/x
1 , (2rh1))
2 2erhi
2 2 (2Th1),
(13)
= cG 2 1h (G).
Therefore, overall we have for w. 0:
T Σ 9t (w: w.. 2 cG+ 2 (G/)) re(w.) l..GG Tlog 1+ lw. IVTT
bie
Alternatively, suppose the condition in Item is never triggered. In this case, let w. 2V Then, G = hı and by (12 we have:
9t (w: w.. 2 (2T())))) 2Th - (2Th:) 2eTh1 1=1
Σ
Using that V (x) (x) display can be bounded below by O)
" (x) by convexity of いंद and o; 0, the right-hand side of the previous
1
(2Th)) - 2Th 2 ,; 2eTh,
2 , (2Th1);
1
(G)
(2Thhi) 2
1
=4
Applying Eq. |I
2 1
(G)+ + +8 - 22Th
2
7
3¹ (G//) + 46TT..
(14)
4
16

---

Further, since V7 Vyy we have:
V22 -2hh (, (2; TTh (Vii, 27h, - -2)(2)))))
vvg(2Th) (.thii)-7 -Th iy (Vy; (2Th1));
v2; .Th1 24 (-w.)
Il. The + 2 (w.) 2
Finally, let bound Hw.l1 91- using our choice of w.. By definition, have:
MTTT-VV.TI
hi Vog/Too(( (exp(T) 1)),
applying Eq. 110
Tlog 2/ThW;2(Th))
2 h1
[ua IT
h1
Tlog
1
GlwalvV
G
Plog 1+
(15)
h1c
Therefore, combining Eq.
14 with Eq. (15)
(2T(1)) 2Th1
2 b
(2Th1) - 2
2 [I ( (G/)))
+
1
7
(ww.
G G/w.]
Tlog 1+
Glw. G...VVT h1e
4cTh1
2 4
2
7 (w.) Glw.1
Glw.lVT hie
2 3eThh W (G/7)
Tlog 1
4
Glv.l|
(1+ +
GlwlVV) hie
2 cG + ? (G(()) + 7 ((w.)+ +
Tlog
8
4
C Reduction to W- = RR
As first step in our algorithm design, we observe that the application of some known reductions from [16] can significantly simplify our task. (16) show that to build an algorithm whose regret bound depends on S: only through the norms [oel]. it suffices to consider exclusively the case W = R. We provide the formal reduction in Algorithm which ensures the following regret bound.
Theorem 5 (16).. Algorithm ensures that (g. s 21]gr and also for all W:
magninude
Σ (gt, wi w.) s <411w.1
IV
2 [-]
ge
91
magnitude magnitude || Il)-
17

---

Algorithm Reduction From General W to R
Input:
Convex domain W IR online learning algorithm ALD with domain Initialize wifircctiion = 0 F
for ....T do Receive magnitudo
IR from AA
Set Wi magniudde direction R we
Set wi = Tw = argmin wew I wi|--
Output wi, receive feedback 9t-
Set gt
ommonstraiined 9t 199.
We-10 1
Set direction =
II wi|s1 wullssuugiietin diroccionn
2-1
Ei. (s. (g.oommnneng
Set 9t
magnitude
directionn E IR. W to A as the 7th feedback.
(g) momoonsttaieed
Send 9t
magnitude
end for
clear that achieve low regret on W, we need only bound ΣT 9t mugnitude (w), [uggiiigiialeee - -lw,). which exactly the regret of a 1-dimensional learner. So, our final results will be established by considering the case of W = IR. although we will define many intermediate problems for general W as they may have other applications for which the general setting is of interest.
From Theorem
D An Efficient Algorithm for Protocol 2 With Restricted (But Sufficient) Assumptions
In this section, we describe our algorithm for Protocol 2 in the special case that W = R and a; = hs
whenever [0el h, where 9. (1 that 0₁ 0 for all t. This is an important special case that has actually also been previously considered provide it separate Protocol below:
[o. 9t- Our algorithm is in fact reduction the special case
in the literature (see e.g. the discussion in Section 3.1
Protocol 4. Online Learning with Magnitude Hints. Input: Convex domain W (recall that we focus on W R).
For t I..
1. Nature reveals magnitude hint hy 2 h the learner.
2. Learner outputs w, W.
3. Nature reveals loss scalar gi with 1g: h4 to the learner.
4. Learner suffers loss (gt, wz).
The learner is evaluated with the regret Σt (ww W. The goal is to obtain:
I (a, w.) s δ goal
T Σ
I.w.
h
9
2
(16)
1-1
we provide an explicit algorithm (Algorithm 3 for Protocol 4 that suffices for our purposes and achieves the bound (16). In the rest of this section, we take the existence of such an algorithm as given, and use it to build our method for Protocol 2
In Section E|
Our algorithm for Protocol is given in Algorithm 2 The full regret bound is provided by Theorem 10 However, before providing the general bound, which is somewhat technical, we provide two more interpretable corollaries in order to provide preview of what the method is capable of.
18

---

Corollary 6. For any with (b() > O, there exists an algoritim for Protocol 2 such that for all t, the
outputs ;,,...,27
2T satisfy:
Σ De (2z - x.) (1((())))) ((r)))
Ix.ly V (T)
+ |oo log e+ I..lv log² (T)
(T)
s 0 clr + +x)))))))))))))) + l2oly 1o Vi log e+
h1E
h1E
+zb(xa)) Sa log e+ (x.)) log (T)
+bx()))))))))))))))))))) (xx)))) (e c+
(xx)) log (I)
(ogg(())))
TV(E)
mb(())
Where Vig = h Σi=1 oe and S. 7² + Ei_1 ac.
Proof. Apply Algorithm 2 with the BASE set Algorithm using p 1/2. Then, in the notation of Theorem 10. the regret bound of Theorem 11 shows that A, B, C are all O(1) while D is O(log" (T)
and p = 1/2. Set e, = c and Eg = (c)). The result immediately follows.
Corollary 7. For any with (c) O, there exists algorithm for Protocol 2 such that for all t, the outputs Fi,..., ET satisfy:
Σ (x - x.) (a)))((((((() (<((()))))) (xx)))
Vg log c+ [ta]]
|x. lhr log e+ [ra]
s0 Vg + +()+ -t
+ Sa log c ((x)) (b(e)
((x.)) +EE)
+ (ha (xx 1o1g
e
where Vú, = h Etn oe and So =2² + Ei= a.
Proof. Apply Algorithm with the BASE set to Algorithm Jusin p = O. Then, in the notation of Theorem 10 the regret bound of Theorem 11 shows that A, A, C and D are all O(1) while p 0.
Set 6 and c (c). The result immediately follows.
Lemma 8. Suppose d - TR is a convex function that achieves its minimum at 0. Let h > 0 and y > 0 be given and define the norm [xx, h²2² ?222² and the distance finncion S(ā. () y(()) || [x, y) - (#, 911 For any (ă, ÿ). let (5", 88) be an arbitrary subgradient of S at (f. Ú).
Then, 8" 5 5.
Proof. Throughout this proof, we will assume é > 0. The proof is completely symmetric in the sign of a.
First, we dispense with the case in which there is no projection: suppose I 2 (2). Then we must
have f= = y and f and S(4, 5) O. Further, for any ÿ > g. S( v) = 0. However, 6, then by definition of subgradient, we must have 0= = ((a 5) 2 S(a Ø) + by (ū 9) > 0, which cannot be. Therefore 6, So. remains consider the case ÿ (.).
Define (x, y) argmin (2)(w) [[x, v) (.. Further, by 16 Theorem 4], we have:
2² x:) (8",8") h2 2)2 20 u)² Vh2(x 8)2 2 4)
22(0 y)
Therefore, it suffices to show that á S y-
To start, consider the case (=)) > ý. Then, we have و (0) s (xx) y as desired. So, in the following consider the remaining case (0)) ÿ (2).
19

---

Algorithm 2 Algorithm for Protocol 2 (REG)
Initial online learning algorithm BASE for Procotol with domain & taking initialization parameter BASE Non-negative convex function vb. Parameters O, cg 0 and Ev. Initialize two copies of BASE: BASE, with EASE and BASE, with EBSSE cV f do
Input:
Receive h4 /bz-1 R
Send 3h, to BASE, as the ith magnitude hint.
Send 3ry to BASEg as the fth magnitude hint.
Get 2, from BASE,
Get IR from BASEY.
Define the norm (<x, v) f 12 +?? with dual norm [(,,a) o/z S
Define ( 1) g2v()) (1x, y) - (#. D)
Compute Tt, 1/+ argmin (z) [ 1/. (2, 1e
Receive feedback gt. [[-t,, h,
]. az [0, 7]. such that a, unless |ga| h4.
Compute (8, 55)) 1 V,,,
Send gr 6 to BASE, as tth feedback.
Send 67 to BASE, ith feedback.
end for
Observe that since 1 is convex, it must be continuous. Therefore, by intermediate value theorem there must be some 5 2 0 with (()) = ý. Further, we have vi(5) = < (+),, so that < & Now, by convexity, if x 2 c, we must (x) 2 (()) because yb must be non-decreasing for positive since it achieves its minimum at Therefore, y (xx) 2 (T) = ý and so we are done. So, let us suppose < T.
Further, suppose that á y. Then, observe that:
A² ( - 2 + +7² (max(y, v*))) - (x (x=))==+++ so that the point (ū. max (y, 1h (ā))) would contradict the optimality of (2,,). Thus, it also cannot be that ÿ > y and so we are done.
Lemma 9. Let h 0 and 7 corresponding dual norm I|- l.. Let (g, a) be any point satisfying [g] s h, E [0,7]. and a 0 unless |gl h. Let (8", 88) be any points satisfying 188" 8" (g a) lI. Then,
be given and define the norm (x. v) 122x2 ? with
16a1 1glv2.
|5y| S 2
Proof. The dual norm || is (()
f.r S..
So, we have:
(8))²
(8
g² a
+
2.
42
22
h
22
This immediately implies |6y| s 2 We also have
h²a²
( S
72
Now, since a 0 unless g² h² this yields either | s Ig lgl horr [gl = h, so either way 1 s l2
s h2a2112 hv2
Theorem 10. Let A, B, CD,cD c> 0, and p 2 1, be given. Suppose that for any sequence .1,..., 2T and magnitude hints mi ... S mr satisfying 1ea my BASE outputs wi...., WT and guarantees regret:
T Σ
De 2p mi CBSS
Blucho lor log e+ D/u|Z
2 (w: - u) EBASS Cm 2/2-p Alul Z Zlog
m CBASE
20

---

for any u E IR, where Z = m + Ets1 2i.
Let Cr. 6o and be given non-negative inputs to Algorithm
Then, for any T, with V 117 +1== g
and S. 70 + Et=1 ar Algorithm 2 output sequence 2 21..... TT guarantees:
T Σ g0 x.) tc((((())) (xx))
Da cgpqg 22
Dalx,1Vy
C Art2.lly
Vg log
c+
B B.
log
c+
co
(u.((.) co7
Dv.((r))
+CDEsT 20 2 App(ZE))
Solog e+
(xx log c+
cup21
for any J, I, where the constants in the above expression are given by:
A, = 33,
B, 3B,
C2 3C,
D, D,
A = 2
144A3,
B 144A2 24B,
1-2p
(144A² + +24B) log (e 12CD( 48pb)?) 1 (2p 1)(2 - 4p)
1+
C. 30
2
Do 4D 1152AAp [182A""+
Proof. First, observe that since (Ie, yt) is the result of a projection to the domain 2 (x), it must hold that y/ 2 (xx)) for all t. Thus, since a, > and v non negative, we have for any z.:
g( - x.) + (v((()) (xxx)) )) ge(2, - x.) + ar - xx.).
Therefore, suffices to bound Σ (x - x. ) a (Vr x.), which we will now accomplish.
By [16. Theorem 3), have for any E IR
T Σ E9 (I= a.. + a3 (b )) < (gt 02: x.) Σ (a 8 (x.)))
T
and also 11 le, (()),a))) l., by
16 Proposition 1]. Therefore, by Lemma we have
I9t 671 3/91| 3h, Defining V, = h Ein(g =,7) and by the guarantee of BASE, we have for any I.:
Σ (g) (ā: xx.)
11
T
1/2-p
< <((3rr) 20
9h
Σ
(g. + 8g)
Er
[-]
T "g 54)2
D|r. [9h + ΣT (g. + 55)
*Alo, /
log
(3h1)22e)
1=1
D|a,1 9h2 ΣT
(9. (9:1))+)2)))7 52))2
+ 1/Blg/o.. log
c+
(3x
DVP
D|x. VP
33C12VV1/2-p + 33A/x/1 /
Vg Voyog
3/3 [r.
log E
h/
21

---

Next, observe that by Lemma
9
ai 6.1 s 3%, We also have for any x, 6 IR:
T
7
T
Σ (a+ + + - (x.))
(at + 62) (v= 21((x)))
0% y/r
2 f-1
1-|
1
T
T
Σ 2 1
a + 6 (v+- - -2)(
Σ
(a. 8 (1+ 2y.) + -(a 6%)
2 E1
F-1
Now, define V₂ = + Σt- + 8.)2. By the guarantee of BASE applied twice, we have that for any F, E R (v(x.)) ) 0 below represents the comparator for the regret of BASE):
Σ 1=1
a1 ( +xx)))
1/2-D
9r² + " (ac + 08)2 s SC(3) 3p
E
1-1
(0.2
T E(a+ E(ar+ 8893
2Dr(2.)) [9/2+ + ΣT (ar + +
log c+
32072REW
El
2Dv(x.) [972
(ar + 84)2|"
+3yBub(r. log
32
6/'2 log e+ 2Dy. 1972 ET. (ax 8% 23)
AAy
E(at+ (at (9)=+[(a
(992
32072PEN
1=1
2ny. [992 Σts (at + o8)
B33BBy. log
32072DED
+ y/ Σ
aa + 00))
1=1
c+ 2D. VV?
2D.(II) 72
2 $3C
$ <30
+ (A.((z))))
Va log
+ +..B)(x.) log e+
g2vew
Va log c+ 2Dy. V2"
V8 72PEN
+ +3Ay.
+ By.By. log
e
6V
Σ (a, 004)
s 33A((())))))))++++))++)))))))))) +v.) Va log e+ 2D(x(x.) ) + ya V2
+3B(((a.) + v.) log log e 2D.(I.)
+ y, (a,+ 0a))
Now, we observe:
1
T
[a + 6/¹ =
Σ
(a, + 8% + +7)² -2]
Σ
(az + 8/)2
2n [=]
27 t=1
1
T
7 1
Σ
[ + 8 + +7)² -2?]
Va.
2 [m]
2 27
Next, we bound (a, 8% + 7) -2
72:
(a, 6%¹ + +7)² - = a? + (6 + 54 2 + 2754
22

---

using og & O (from Lemma 8 amd 16 S 1/2 2 2n (from Lemma
$ a 20,04 + 2700
using 0 d₁ $ 74
$ 33ya,,
so that have (recalling that S, -² + Σt O+i
1/
Σ
T
41 + 5/) S
y Va
31- Sa. 2n
2%
t=1
So, overall we have:
T
Σ (a + 6 - vvx)))
[=1
2D(1((x))
+ y0 V
s 3C 1 3A(+(xx))++++ v..)
Va log
e
-20
3B (x.) y. log
2D.(x.)
y Va
3y. Sa.
22
27
27
Since the above holds for any y. 2 0, we may write:
T Σ (a= + 5,))) ( (xx))
1
2D(((x.) + V
inf sup y. Va
20222v1122 3A((((x))++))) +
Va log
c+
+3B(w(x.) v.) log e 2Dr(I.)
yz 2n
3y, 27
Va
So
P2
Now, applying Lemma 20 to bound the minimax expression above, we have:
(a 5t) - (xx)) ( +1441A (1444)(((0.)))
(Dv(c.)88 2
(xxx)
S. So
[1152A2p 48pB]²
4Dr(I.)S
+ (1.4A 24B) log
1152A 48pb)))
2D
-/ (141A² 24B) (e 12CD(1152p + + 2
488p))P)
1
(2p + 1)(2 4p)
1+2p
2
So, overall we achieve:
Σ (xt x.) ar avr - (x.))
D/P.IV2
< 33hhh 3p /1p-1//-ee +3A/x.1
V,, log
e
3Bhr (z, |oog
6
20 cz.
1 Exx
((2 +1441)) (b((2))) (xx)))
(D.()))
So log
c+
[1152A4p
48pB]]
2D
4Dv(r.)S? 2v
+ +20(22) 24B) log
11522Ap 4
1-2p 1:35
1
(2p + 1)(2 4p)
(141A²+24) 24B) log (e+ 12CDD1152p4 488p))) + 2
2
23

---

So, with:
A = 3A,
By 3B,
C2 3C,
D. D,
A 2
144A",
B 144A +4BB
(2p 1)(2 4p)
1+2F
C2 3C (144,² + +44B) log (e 12C +88pb)²) + 2 2
D3 4D 1152AAp 48pB)"
we have
Σ (( (0) a:(: (xx))
e+ Dz|0r. VV
Dz/2.117
$ C. 2/2 + Auto.ly
Vg log
+ B2 x. [1.gg
c+
hx
cahi 2p
S. E+ Dup(E,) SS
Cyper 22 Ap)((z)))
2
+ BB. log c+ DoM(x))
from which the conclusion follows.
E A Parameter-Free Algorithm With Optimal Log Factors for Protocol 4
In this section we quote an algorithm that obtains a performance guarantee suitable for use as BASE in Theorem [0] We emphasize that the development in this section is only very mild improvement (affecting only logarithmic factors) on previous work: our key contribution is how to use this algorithm obtain better adaptivity unknown Lipschitz constants.
In fact, algorithms satisfying the requirements of Theorem up up to logarithmic factors have been
described by several previous authors: see [18] 21 23 26 Here, provide slightly improved analysis of the algorithm [2I] which achieves lighter (and in fact optimal) logarithmic terms.
Theorem 11. Suppose 91...., gr is any sequence of real numbers and < h4 S... & hr is another sequence of real numbers satisfying Igr) s hr. Then, ip 1/2, Algorithm 3
3 guarantees for all
(ng.
T Σ o
|ul/33 3+ Σt log (3 Σt gi/h?) +1
Σ (w: - u) S 8hype + 6/u|,
log
Jul/3+ 3+ Ete, of 12/ log² (3+ ΣT. 92/h?)
Glu(he log
24

---

Algorithm 3 I-Dimensional Learner for Protocol (BASE)
Input: <> <>0, e [0, 1/2]
Initialize ho = 0, 3 1/2 p then Define constant c else
Define constant c = end if
for 1 ....Tooo do
Receive h4 h4-1 R
Define 1i2 = he Dis1
if p= 1/2 then
Set oz
Ve+E%ul of/h (ctE:)
else
Define az (ctELl (f/1))"
end if'
(Ei-l 9:)
if E 9a
2
Define O Ei 9i Vi
V
h,
otherwise
khi
N?
Output W, = -sign |E-1 9i) a (cxp(0,)-1) 11)
Receive 9r with 19:1 1 14. end for
while if p 1/2 Algorithm 3 guarantees instead:
4h2f c (ET-) 9:) 1/2-p
g) ww u) s Σ 1-|
1- 2p
|u|
ΣT= 1b)) -11 (1+
+ 6/2g
Σ gt [=1
log
[u| Σt 96 ///11)/
+ 6) log
+
Notice that the term log² (3+ ΣT= ///1) s log log2 7), and so we upper bound this term with a
constant for the purposes of use in Theorem 10 Further, the term ΣT, /2/ s ΣT oe /hi and so the logarithmic terms always fit into the framework of Theorem 10
Proof. Observe that Algorithm is instance of FTRL with regularizer:
ve(w) k Lo
log(z/or+ 1)
min 1/
n/V dæ.
That
argmin thes (w)
gaw.
In the "centered mirror descent" framework 21 (their Algorithm 1), this corresponds to setting (ww)= O. Further, (21) provides analysis of this update for the particular family of regularizer functions vi we consider above their Theorem 6. Although formally speaking, their Theorem 6 specifies a particular equation for a4, inspection of the proof shows that most of their argument applies so long as 0g is non-increasing. We reproduce this verification in Lemmal 12 which yields:
T 20
Σ g. - u) (r(()) + Σ 1= VV.
25

---

Next, define hr-1 = 0 and 9r+1 0 in order to define 4r+1 and thr-1 2 P/.. So, we can replace (u) with uhr+1 (u) in the above expression. Next, to bound 4/T+1 (2)) we observe that:
(T) So
log(z/at-1++ 11) 11
min nslfberaa
dæ,
log(u/oT+1++ + v,//+11
k/ul
min 1/11/bre11
log(u/arri+1)
Now, notice that if the minimizing 7 of minng///rrs ary = 1/hrr41, then it must be that log(w/orant)) 1744, since log(w/orH=)) is decreasing in 7) and v is increasing in y, Thus in this case m 2hg log(u/or+1 + 1). Alternatively, when the minimizing 7 not on the boundary we have log Jog(w/or-1-1) n/Vr+1 =2 (og(u/ar-11 1). So, in general we have:
n/r+1 occurs the bound-
"
log(u/ar-rt1) -yVr+1
minnst//
"
(u) S 2k/uly Vr+1 Log(uu//or-1 + 1) 2k/u//rr log([ul/or=+) 1).
So far this analysis identical that of (21), and has been agnostic to the value of at so long as on is non-increasing. Now, however, we come to the place at which we diverge in analysis: our choice of a is slightly larger and so results in better logarithmic factors in tb. The trade-off is that we need to provide fresh analysis of Σi=1
2a.gi
to show that this term is still controlled. We accomplish this
VM
in Lemma 21 (for p 1/2) and Lemma 22 (for p < 1/2). For = 1/2, we then obtain:
|u/y
3+ Σt of mi log (3+ Σt= 07/1.)
Σ 91 (er ur - u) s 8hiee 2klul, [-]
h1 + m-1
Σg of
log
+1
|ul/33 Et 9b/h3 log" (3+ Σi= (
2k/u[/rr log
+1
while for < 1/2 we obtain:
Σ g( u) 4h e (Σt11 92 12--
T
2p
T
|u| (1+ ΣT, g2 +1
2k/ul
11
log
e
|ul| (1 Σt= n?)
+ 2k/uu//T log
The conclusion now follows by substituting in 3.
The following technical Lemma is lifted almost entirely from 21 Unfortumately, this result was not explicitly declared as a separate Lemma in the prior literature and is instcad merely a subset of the proof of larger Theorem (specifically, Theorem 6 of (2I)). So, we include the argument here for completeness. The steps are nearly identical to the prior literature, with only very mild improvement to some constants.
Lemma 12. Let 91....,9r be an arbitrary sequence of scalars. Suppose O < bı S ... S hr is non-decreasing sequence with 1grl s hy for all t, and let 0q 2.. 2 CT,, be non-increasing sequence. Let k Set V, h Etzl dh and define
(w) = k J
log(z/ar +
min gs1/hg
Vi dr
1
W. argmin (((w) (w) Σ g.w.
im1
26

---

Then for all u R:
T Σ C u) vT)
T 20.g.
Proof. Define dTr-1= the and let D (alb) indicate the Bregman divergence D -(a))
fa(b((a - b). Define A.(w)= Den.s (oeri(wluu (w)wr). Then, by (21) Lemma 1, we have:
T
T
[ (wr u) s (br( Σ ge(wu; (wr we+l) Der (wo-ile)) Ar(wer)
So, it suffices to establish that:
(w Wx+1) 1- Dv, 12041/20))> D. (we+)) 5 20r
(17)
VV.
Following the notation and argument of (21). define Fi(w) = log(ll//o + 1) and
(x(x)= k So
F1(x) + v dx
min ns1/h
"
Then we have v(w)= V.((1uo]) and elementary calculation yields:
2k.//.B...)) kh,Fe(x)
(z)) s VV,
V((x)) =
RV.
otherwise
b
RVV. (z+a:)VF.CC)
if (1(x) S VV.
(x))
kitt. xtt
otherwise
(VV((12F((O))
hf (1) S VV.
((rta))
-KkI
otherwise
(2+a))²
Therefore, (x) 2 O. (x) 2 O, (x) 2 0 and (x) s 0. Further, if we define xo = ax - 1), then for any To we have / /F((T) 2
and:
Valla
(x)
( (()((())
if (x()) VV. otherwise
2LVV
(x)))
(.)(()) RhVV kh+
if hf S VV otherwise
using &: 2 3:
F((x)
1
min
Ve
he
Now, if we define Z,(x) - min
F((Z) 1
dæ, then we have
TH' (x)
(x)) (x)))
Clearly Z, is convex, 1/h, Lipschitz, and achieves its minimum value of 0 at 0. Therefore, by 21
Lemma 2, we have:
2g
96(w; (w: wt-1) Der (Wmrlw):) Ze((
v'ro)))
2g (xo + a.)
$
lVV.
2g one
k
s 20
VV.
27

---

So. now if we could show that A((w) ((w)))) this would establish 17
In turn, since
A,(w) 2 ((w)) ((wo)) suffices establish:
P((x) 1
(z) (x) 2 (x)
oe min (V
Vi he
To this end, we compute:
Fi-1(x)
F((x)
W ( (x( h min ns 1
+ +VVe+11
k min 951//e
+ v
(x=
F+(x:)
k min 751/h
+ n1Ve+1
k min 1/1l
1)
"
Next, let us define dm - - h2 so that V2+1 Vn + 8m o.. Then we have Fun((r) + 11
miny (())(a)
1 + v/V 17 9t). Armed with this calculation, proceed:
(x,((:) - (x(x) kmom + 9 min [
Fe+1()) (x)
Fa+1(x)
Fe(x))
k min ns1fh,
n
- k min
n/V
Ven
he
1
//1/h,
"
now, since at 0t+1, we have F411 2 F2 so that:
(
x)
1
2 k(8m + 9i) min
Vi+
hi
Next, observe that
d
8m gt
82h 2V, +
d8m
Vv, + 8m + gi
2(Vi 8m +g,)3/2
Therefore
8m + gi
5m + g
VV=1
Vv. + 8m gi
gi
VV gt
d6
V1
VV.
V1 + gi
9
h2
VV,
g
/2V,
This implies that
F((x))
F((x)
(6m 9t VV
V1+1
V2
So, altogether we have:
kgł
(x=1
1
V + (x) -V(x)) 2
min
Vr
Fro (x)
2 gi min
V2
= (2)x)
as desired,
28

---

Fully Unconstrained Learning via Regularization
In this section, we provide formal description how to achieve fully unconstrained bound via application of some peculiar regularization terms, sketched in Section 3.2 The goal to ensure regret given by (4). restated below:
T Σ o + + 2p 1=1
Σ Eg(w, - u) + +a(((w)) (w)) S
July
h2
Σ a
In Section H will see how obtain the bound via general technique for obtaining constrained "full-matrix" regret bounds (which of independent interest). However, this approach comes with a mild computational overhead. To counteract this, in Section B we provide alternative approach that has the same computational complexity as gradient descent, but achieves the slightly weaker bound:
E aa( su - u) + (((((w())))))))))) v()) SŌ
|uly
hG
+ Σ ot
+
72
> 1-1
at
(18)
Fortunately, (8) will also be sufficient for our purposes.
Armed with an algorithm that achieves 18 we are ready to describe our approach for fully uncon- strained learning.
Corollary 13. There exists an online learning algorithm that requires O(d) space and takes O time per update, takes as input scalar values h1, and and ensures that for any sequence g1,92, Rdd the outputs wi, "..... c Rd satisfy for all w. and T:
T Σ (9,, w.)ss00ee evv + Iw-1y
|w.1|
e+ |wall
V Vlog
||w., |Glog
G
G²
G h1
[w.12 E
G e+
h1 ]
+e? +e2rv log E+
log log c+
log
E
+ zwr
log
log
h1
?
c²
where G = hy max, lod and V G2 Σイ 19
Proof. Apply Algorithm [5 with g 1, and REG set to Algorithm using Algorithm
3 with p = BASE The result in 1 dimension then follows from Theorem T6 and Corollary reduction from d-dimensional online learning to 1-dimensional online learning result in high dimensions also follows.
6 Then by the
[16] Theorem 2), the
There exists an online learning algorithm that requires (dd) space and takes O(d) time per update, takes as input scalar values 7, hr, and e and ensures that for any sequence I1. 92, .. Rd the outputs wi, wi, Rd satisfy for all w. and T:
Theorem 1.
@ log los(et Σ (gi, wy w.) o [ cG+ eG+
T
G ()++ ||w.|1 I Vlog 1n + +r/wa | 2log e 2
|w./VVlog' (olo?(() hie
c
?
Iw. IVV log2(T))
log (
c+ ]
+||w. (tw.|Gloo/ c+
- h
hnc
where G = max(hi, [ [[ and V G2 ET loel?
Proof. Apply Algorithm 5 with - 1, and REG set to Algorithm 2 Juiin Algorithm with p 1/2 BASE The result in dimension then follows from Theorem 16 and Corollary reduction from d-dimensional online learning to 1-dimensional online learning ( [16] Theorem 2), the result in high dimensions also follows.
Then by the
29

---

Algorithm 4 Fully Unconstrained Learning in One Dimension
Input: Regularized learning algorithm REG with domain I. Parameter 7 > 0, h1 > 0.
Initialize REG with parameters e and ?.
for part1....2 do
Send to REG as the ith magnitude hint.
Get W, from REG.
Play wi, see feedback gt-
Set h4-1 = max 19:l).
Set 9. clip (hi.1 -he)/
Set a₁ = 7 T+E1
(h::1 --ha)/aar11
Send ft, dz, to REG as ith loss and regularization coefficient.
end for
Theorem 14. There exists online learning algorithm that requires (d) space and takes ((d) time per update, takes as input scalar values 7, h1, and e and a symmetric convex function and ensures that for any sequence 91. C IR., the outputs w1, W1.".. R satisfy for all w. and T:
(9t, w.) :0 c Iwwlly [
lws. Jw..VVlog"( ( /w.1Glogg (et
Iwa. MVlVVVll hie
Vlog c+
c+
hie
++(c) ((( log "([u,]) log (et ((e)
G h ())+ + yoo (1+ 1 log G 111 (())) 20 ( 1
nn (cn)))
G
|o log
where 4/" (0) sup Ow (w) is the Fenchel conjugate of vb, G max (11, max; 19e)) and V G + Et 19.12
3 with 1/2 as BASE, The result in dimension then follows from Theorem 16 and Corollary Then by the reduction from d-dimensional online learning to I-dimensional online learning ( [16 Theorem 2), the result in high dimensions also follows.
Proof. Apply Algorithm 5 with REG set to Algorithm 2 usiig Algorithm
Theorem 15. Suppose vb is a symmetric convex function. Suppose that so long as h2 2 10cl. REG ensures for some A, C,
T Σ go (wi w.) (e((b(we)) (k(w)))
D VV
$
Cxb(c)) 22 + Alwaly
Vg Vg
c
DlwalVy hipe
shrrww/log
c+
9
e+ Dv(w.) p2p((c)
AAr((w.)
S, log
Sp
Dil(..) sp
BBB((w.) log c+ (pp((())
where Vg = h3 Σtz Je and S. =g² +, Σt ar Then Algorithm 4 ensures:
hr
Sa s 2² + +7² log 1
log
T
h
Vg s h + Σ g/
1-|
30

---

and:
Dlw+1 V7 11
(e 1 w.)
Cehi C (P + Alwalyy IV
Vg V2
BBrlww.llog
hypt
So log e+ Drb(w)) Sh
Av((w)))) )
(2P((E)
c+ Dow(.) Sh (2)(b(c)
(B.( [w)
hrruul + ((..)S.
hT T 2p"
hT ("T
( )
+ y log + min
log
log
h1
7
hy
In the special case that (xx)
Ix 1-g
can replace the final term
ltg )]
y ylog (1+ min [og
hr hi
) .T) v/- (hr [1 + log
loT ho
the above expression by:
br
1+1/2
1 log
Az 1/9
h1
)
(1+ 1/9) 1/9
Proof. We have:
Σ 9r(w: u)
= Σ 1=1
gi (wi - u) + ar(((()))))))) v(()) + arv(u) + (gi - (w) u) - awv(w))
T
$ (w)
Σ
de + [u]
Σ
1t - del
Σ
Jr (w: (w: u) + ar(((w;)))))) - (v)()::)))))))))))))))))))))))))
1=1
t=1
1=1
T
Σ
9t
rell
wrl
a (wpp(w))
Observing that 1gt Tel he+11 h4:
T at + [u] Elh++
T
T
T + Σ Cc - u) (x(((w:)) - (l)))
= (w) Σ 1-1
h4] + Σ 1m1
(het1 he)lurel - (w:)
1-1
Next, we will bound the terms Σts (1) and uu| ΣT - Moreover, hn- so that [u] ΣI 19: Hel s |u/hr.
Further, notice that for any 81, ST. Σx= log
5e Eino
s log(sT/5o), so that:
I
T herr - hig herl
Σ
log
1+
Notice that [[gd] he]-/hes1 so also have:
h he min
Nr hn
log
hen
so that overall:
hT
S, 72= + Σ aj S 2²2 + + log
1 min
log
.T
h
twl
31

---

Next, we bound the terms (hx-1 - he)/ (wp())) Let vi (w) be the Fenchel conjugate of a/. Recall that symmetric that eb(w,) 4. (*((er)).. This also implies that if is symmetric and minimized at zero. Thus:
(h+-1 he) wwall (we)) (h++1 ha)l aeds(werl
hx+1 - he 0t
azab
he-1
hit1 h4
axvp
1 Σ
het
iml
So, in general we have:
T
h4-1
hit1 h4
Σ (bea1 ns))uusl ar((ww))
$
Σ
a
+ Σ
hi+1
1=1
i=1
T
hT
10T
)1)
$ Σ
a
+
log
1111
1=1
hT
(T)]
hr
hr
$ 7 log
+
min
log
1/"
+
log
h1
h1
juft*
In the special case that (>w))= factors and simplify the calculation:
we have 8/* (h)
that improve the logarithmic
1+q
1-1//
1
Σ
t.
h - hi
)
a, 11/tt//
1+ Ei=1
hai
2+1/4
h
(1+1/9) (4+1/g))+11/
1=1
(het1 - ho) 1/9
+ E/=1
hip h,
1/9
Ass2
(1+ 1/9)>1/8
(hot1 - h4 1/9
+ Σim1
hir-h
1/9
(1 1/9)>1/s
1/9
- (ho11
(he+1
ho)h 1/9
1 log
hn
(1 1/9) 1/4
T Σ (he-1 - he) he)lwal a.)((w))) s
1+1/q
hr 1 log
hn
1/9
(1+1/g)>21
Finally, it is clear that gual hy the summation ΣT, 0c(w, u) ax(((w:))ede +u)) is controlled by the regret bound of REG:
D|r, V2
Σ (w: u) + aa (v((w) - v(u)) s Ceh Ceh2pv1/22 Cc(())) g///2 AAzz,1 [-]
Vy Volog e
1,20
D|r. VV
Blrlor/
e
he
c+ De(r.))
+A((z.) /
S, log
DV((:.). 5h
+ +,B+b(x. log
e (2
32

---

Algorithm 5 Fully Unconstrained Learning
Input: Symmetric convex function IR R with 0 v0()). Scalars 0, h1. 7 > 0, pe [0, 1/2].
Let REG be an instance of Algorithm 6 with input v/, 7, p. Ex and Ev 2e(c).
Set vector uidirection 0
Send h1 to REG as the first magnitude hint.
for 1...7 do
// Apply reduction to 1-dimensional learning from 16 using adaptive gradient descent as "direction learner".
magmitude E be the ith output of REG. Let Wi
Set W; we - -t
magnitude direection
Play We, see feedback gt.
Set adirection 2-1
-I7 [[|
dddrectionn
91 /2EL. l0:1l
I/ Compute feedback for "magnitude learner"
Set gt = (9t,de) II Apply
new fully unconstrained magnitude learner.
Set h4-1 = max (g lg!
Set 9: = clip ku
(hr.1 1ha.1-1.//m Mheer
Set Gr T+ 1+ (bar hha)/aa
Send Gt, az to REG Ith loss and regularization coefficient.
Send h++1 to REG as the f + 1st magnitude hint.
end for
Finally, we also have:
T Σ
Vg = 12
-2
91
T h Σ gt.
E1
F.1 Full Statement of Main Result in High Dimensions
Throughout this paper, we have considered the special case that W = R. This suffices due to the reductions of [16] as discussed in Section C However, here we provide more complete theorem and algorithm for the case W = Rd. The pseudocode is provided in Algorithm and the regret bound is stated in Theorem 16 Note that the regret bound follows essentially immediately from Theorem [5]
Theorem 16. There exists universal constants A, B, C, such that Algorithm guarantees for all T:
T Σ (gt, wt w.) Cch 2 2 A Alw.lk ll
||w_/|| ||
Vg log
h
||wa|| VP
Bly [w log
h:?"
((ww
S. log
e
(( 5
((1l S p2m
+>Bu([uu log
+brlul+ + w([w.. S).s
hr
Ar
hT h
y log 1 min
log
I
1 +
log
7
33

---

where
So 722 +
min
log
hr h1
r))
Vg s 11 +
Dt
t=1
lxc 1-g
In the special case that (xx)
can replace the final term
ltq
y yoog (1 min log
Ar h1
Tl) 2b (hr 1 log
)}
in the above expression by:
hes
lo
1+1//
1 log (1+ 1/4)
hr 1/9
h1
Proof. Algorithm55 is applying the dimension- ciimennioo-free-t-oo-------- free-too-nneddmmesson reduction provided by Theorem 2 of [16]. So overall the reduction tells us that the regret is bounded by
T ld magnsttde - -Il.. w 1] + l|w. We
(g,, we w.) Elgt"
(ge, wa dddrectionn w. /lw, II)
In this case, the "direction" learner's iterates w ddirectioon are generated by standard adaptive gradient
descent 13 which guarantees the regret bound: Σt= (gt, wdirection w./lw. 1) s 2 Σi= 11 12
For the first sum Σi= (gt" " magnitade -Iw,, |]). notice that magnstude is simply an application of
Algorithm 4 Jusing an instance of Algorithm [ The first sum is bounded by application of Theorem 15
noticing that |g!'| s |gg.].. So, putting the two bounds together we have the stated result.
G Technical Lemmas
Lemma 17. Let A, B, C, D, E be positive numbers and let e be the base of the natural logarithm.
Then:
A²
AC
2CB
sup MMggee DMC) B Blgg(e+ DMC) - E.M M
+ B log
e D
E
E2
E
Proof. First, by Young inequality xy inf x²2/2x + >y² we have for all M:
M 2
A² log (e DM
Mlog(e+ + DM
+
4.22
F2
Then using the identity vx us vx+ vj:
AA
log(e+ DM EM
sup Av A Mlgg(e+ DM B log(e= DM EM sup M E
B
M
Now, from first order optimality conditions we are looking for a solution to:
A²
B
DCMC-1
E
E
DMC
2
A
+
+
DCMC-1
E E
c+
DMC
E
2
Notice that for any M
2CA²a E
+
2CB F
we have:
A
E _
+
B
CDs
DM
E
2
A2
B
DCMC-1
E
DMC
E
2
A22
+
B
DCMC-1
E
e+
E
DMC
E
2
2
34

---

Therefore, the optimal value for M can be most
2C,²² g
2CB
Now, notice that ( log(e+ E
DM is strictly increasing in M. Thus, our quantity of interest is upper-bounded by substituting in + 2C into this increasing term:
M 2C
E
21 B
A12 B D
2CA E²
2CB
sup M
log(e+ DM EMS
log
E
E
Lemma 18. Let A, B 1, C' be positive numbers. Then:
BA
1/(1B)
(1 (1-3)
sup AM CCM
CB
B
Proof. We differentiate with respect to M:
ABMB-1
C
1/(B-))
M
AB
So, plugging in this optimal M value we have: SupM AM
CM
CB
1/(B-1)
11
BA
Lemma 19. Let A, B, C. D. G be positive numbers and let be the base of the natural logarithm. Then:
EM
sup A (c+ DMC) Blog M
(e (e+ DM
FM
2
4A22
A2CA2
8CB
GFGF
1/(1-)
G-G
<
+
log e+ D
E
E
E
EG
G
When G 0, the last term
(4 Eo
1/(1-G)
(1 1) should be replaced with the limiting value F.
Proof. Notice that
EM
sup Av M log (e DMC)+ Blog (e+ (C+DMM++ FMG
EM
FM 4
s sup A Mlog (e B Blog(e (c+ DM
sup FMG M
M
The result now follows from Lemmas 17 and 18 F.
Alternatively. G = 0, clearly sup FMG EM
Lemma 20. Let th, A, B, C, D, S. y, and p s 1/2 be positive numbers with S 2 22, and let e be the base of the natural logarithm. Then:
D(1b F.)
By((+ E3) log e+ D(v + F.) yp
EV
F.S
inf sup A(V E) Vlog c+
VB
2/
24 +
E
72p
720
2"
2DDSP
s (1/2+ 16A²) v/
Slog
(128pA2th
+1pp))))
72p
2D05"
+7 (16A² +BB) log
(128pA² 16pB)p
e+
72p
+ (1168 (1o4++2) +BB log (e+ 2DF (128pA² + 16pB)
(2p+ 1)(2 4p)
1-2p
2D 1/22-
2
35

---

Proof. By Lemma 19 we have:
Vlog et D( + F))
D( + F.)
FV
sup A( + E)
M
B, + E) log
c+
M
+F FF22V11/2
7:20
7/2
24
4A E)8 + -B( E) log
D( E)
332p7 2 A E)
8p7² B (6 +1)
)r
c+
E
72p
E
4//2 21/2-
1439 2p+1 1 1- 2p
(E17))12-P
(v+ E + BT( + B)
32p (+++ (
E)²
SpB(v+ +)
log
D(u E)
E
E
E
(+)
(2p + 1)(2 - 4p)
I+2p
F
1o2p
E1/2-D
(*+)
Now, set:
y?b S
2D 222
y1.20 F
E= max
min
log
(128pA² + 16pB)²)
1122
We will bound the above expression by first considering (*) and then (**). Now, if E sh we have:
(+) = 7 (16A4= + 2B) log (e 2D (128pA² 16pB)")
recalling that S 72:
2DthSP (128pA² 16pB)²)
$ 7 ( (16.22 + 2BB log e+
720
Alternativlly, if == T
log
(e+ leg(e+
20WS" 72n
(128pA2 + 166B))) then we have + to s 2 and so:
w62
128pA2232
16pB
(+) s
+ BByb log e 2D
(19)
E
E
E
Before we bound this expression, let us consider just the value inside the logarithm:
1 E
16pBub
S + 16pB VS
s 128pA2
E
72 7
now, since S S210 2
s
$ (128pA2 u 16pB3
72
So, putting this back in the previous expression:
128pA2uu2
16p
)7) log (ee
2D0SP ypp
log e + 2D
1))BB)
E2
E
from which we conclude:
2DrSS Slog e+
(+) 16A w/
(128p121h 16pB)²)
720
+2Byrb log
(0
2D
(128pA21 16pB)p)
22p
36

---

Finally, let consider the F.
- To handle this situation, will work with more
subcases: either E s 30 not. If E then E v 2tb.
Therefore:
(+) 16A4
A28pA 62
16p P
2B log
e 2D
E²
However, if E s vb, then it must be that E exact same analysis following equation
log
2D 75
(128pA² 16pB)")
Thus by the
vs
19
we again have
2D
(x) 16.4 v/
S llog
e+
(128pA2t 16pB)p
722
2DESP
+ 22 log
e 22p
(128pA 16pB)p)
So, for our final subcase we consider E= F and also E 2 v. Then a s 2E, which yields:
8
(+) (+) + log (e+ 2DE S3DDE(188))) 1128pA 16pB)))
Since S2,?, E F and so:
$ S +BB (
2DF (128pA² 16pB)
So, in all cases we have:
2D
(+) 16A4 vy
Slog
E+
(128p42 16pB))
32p
2Dth5"
+ (16A2 2B) log e
(128pA (1)pB)))))))))))))))))))))
72p
+7F(1642 2B) log (e (e+ 2DF (128pA² 1128pA2+100 16pB)))
Where the last term 7F(16A2 + 2B) log (e 2DF (128pA² 16pB))) only present if # 1/2.
2//2FF s -
Notice that we must have E
Therefore:
F 1-3p
S 22 SPS
7
E-2pp
2g
(**) s (2p+ 1)(2 4p) T+
7
2p
F 12-p
So, overall it holds that:
2DDSF (+)+ (*+) 16A7 /y Slog Slog(e+
(128pA2
16pB)²
720
2D
+ Y (16A22 2B) log e+
(128pA + 16pB)²)
720
FF16A2 + 2B log (e 2DF (128pA² 16pB)")
J-2n mry
(2p+ 1)(2 4p)
2p
To conclude, let
us bound
ES
If E
then it must be that E m
log
2D 720
(128pA² 1
Therefore:
ES
v
SD Slog
(128pA² 16pB3)
c+
27
2
222
37

---

Alternatively, if F F. In this case:
8 1420
ES
F
27 2
So, combining all these facts, we have when p 1/2:
D(1b E)
(V log E+ D( + F),
EV
ES
inf snf A( E)
V log
c+
MP + By E)
MD +
1/2
E
g2p
72p
2y 27
ES
inf (x) (**)
27
2DbsS
s $16A2v //
Slog c+
(128pA34- 16pB)²
y2p
2D
47 (16A² -2B) log
(128pA² 16pB)p
72p
+*F(16A + 2B) log
E 2DF (128pA² 16pB)")
(2p + (2 4p) 1729
2p FS
7 1/2-p
vb
2DtSS
Slog
e+
(128pA2 16pB)"
2 2
72p
grouping terms, and using 7 s 2
2D.sSP
01/2+
Glog e
(128pA2p) 16pB)p 16pBB)
720
2D1DS"
+yo (16A2 + 2B) log e+
(128pA 16pB3)
72p
1-22
+ (166A + 2B) log (e+ 2DF (128pA² + 16pB)²)
1
(2p + 1)(2-)1222) - 4p)
7 29 S
+ 2
2
Lemma 21. Suppose 91,...,9h and < h1 S h2 S ... $ fr are such that [gel s for all t. Define
V, ch² + git-1 Define at V c- o2/ log lo Ett n?/)?)
for some 2 3. Then:
Ongi VV.
4chT
Proof. Let 1 .i...., S T be the set of indices such that h > 2h,, and h S 2h, with Tk-1 defined equal to 7 + for convenience. Note that this implies hrz h/g//', Further, h $ hy,, so overall we have for all h S h2//2'. We will show that
aggi
Σ 1=
2eh
(20)
VV
38

---

Once established, this implies:
2
k
T--1-1
aigi 2
VV2
VVi
2E
hr,
i-]
k-
2e
Σ
i=0
k-1
2chvr
2-
8=0
Achrr
So, to establish 20). we observe that for any E [Tá, Ti-1 - 1] we have
142 (c- 1)h2+ + Σ oj
j-
C- 1
Σ 9j
T+i-1
2
j-
and also:
04
c- 1 Σj-n 13 log" 2 (c - 1+ E--1+ Ei-ns,1113 071113)
c-1 2
+ Ejer, 97 7-1-1 log"
( + Ejen زن 1 112 1
ch
c-1 12 7w + Ejer, 92 log" 2 (22 Ejer, 2
2
Combining these yields:
aggi VV
eh e
[ 2 h
Ej=r. 97) log 2
2
Ejer. 87 02/
2
7a1-1
p-dl =
Ejen. 12
log
p-dl
+ Ejzr, E h3//mmm 2
2
using e 2.3 3
12
s chiuuil
(1+ E1+ 17
log
+ (1+ 87 ((
T-1-11
9e 12/ 711-1
2eeh
[1 E1
93/12
93
112
log (1+ Σd Eizn, 93 1
2
So, now if we define v, - 1/2
then we have:
1- 1
$ 2ch
Σ
(1+ E+ Usf 2x) log" (1 + Ed Iw)
And, by Lemma 4.13:
$ S Ex1
dx
(1+ E.
x
log² 2 (1 Ex
xz)
(1 x log (1 + x)
7el1 z.
log( 1 + x)
<
So, in the end we have I1=1-1 s 2eh,, as desired.
39

---

Lemma 22. Suppose 91...... and 0 < h1 s h2 S. S hr are such that (gel & for all t. Define
V2 = chi + Ga--1. Define at [.tE: o2/h)) for some cz 1 and p [0. 1/2). Then:
o.g 2ch 20 (E)=18)) 2/2-1
Σ
1 2p
Proof. Similar the proof of Lemma 21 we have:
V22 2 (c- 1)h2 + Σ 9j
j-1
2 Σ of
j-m;
and also:
0 5
( 03112)
eli 2p
$
(E--193) 93)
Combining these yields:
019i
eliy
VV.
(Σ)= 93)
1/2-p
Further, by Lemma 4.13 we have:
T
Jo Einl o7
dr
Σ
$
122
1/1p2
E 03)
1/2-p
1=1 gt)
1/2 -
from which the conclusion immediately follows.
H Regularized Regret via Full-Matrix Bound With Constraints
In this section, we provide an alternative approach to solving the "epigraph- based regularized regret" game specified by Protocol 3 Our approach actually involves a generic improvement to the class of so-called "full-matrix" regret bounds, and so may be of independent interest.
Specifically, we will provide an algorithm for online learning with "magnitude hints" (Protocol that ensures the regret bound:
T Ee w. W.) s elT.I+ eluT.
(gt, )2 log([|w. (T/e)
(21)
This type of bound is sometimes called "full-matrix" bound as the term inside the square root can be expressed as w Ew, where Σ is the matrix of gradient outer products Σ Σt= g:gl Bounds of
this form have appeared before in the literature. For the case that W is an entire vector space, [16
18] both provide full-matrix bounds. For the case in which W is not an entire vector space, [3T] provides knowledge the only full-matrix bound. However, their algorithm suffers a suboptimal logarithmic factor: the log(T) term appears outside rather than inside the square root. We provide a method that fixes this issue.
However, before delving into the technical details of our approach, us explain how achieving a full-matrix bound allows us to solve Protocol 3 The argument is nearly immediate: observe that in
the 2-d game, we would have w. + (w., 12( w. )) and gi - (gt, a.). Then the bound 6 immediate from 21.. So, without further ado, let provide our bound and analysis.
40

---

H.1 Full Matrix Algorithm and Analysis
Assume that W R is closed convex set that contains the origin within its interior. Further, let Pbar be a self-concordant barrier for W with parameter > 0. In this section, we present an algorithm that achieves (2T). The algorithm Follow-The- Thr-ThhulRarrizee Leeuderrzed-Leadrr Leader (FTRL) with specific regularizer we define next.
Regularizers. For 2 IRd and Z, 0, O, define the regularizer:
x(wi w (E Af)we det(o-
w (E+ AT)w x @ Yw;;E,,00 2, = sup
(22)
g²
A20
where X(0) W (0) W (0) (0)-1/2 and W is the Lambert function; W(x) is defined the principal solution to W(z)e x.
Lemma 23. For any E Raxd and e, 0, the Fenchel dual of the function P(; 2,0,)) in satisfies:
e.exp (e G+ AZ
VGER" ('G::E,Z,0,E) = inf
A20
(o
Proof. See 18
FTRL. We will consider the FTRL algorithm with regularizer 0(; Z, +)++ Poar (+), for some
choices of E, Z, a, and To specify these choices, let
( / (1-e2r
(23)
for 1. With this, and given the history of gradients 91, ...-1 up to round (- and parameters 7, 7,0,8 8 and hint h4 O, the algorithm outputs:
We argmin(GG.1, w-w:;; Ve,,, weBd
(24)
where
(w; V,,,V,,,, " (V,, o,,)) + (bar(-w),
(25)
and
G Σ ge and V Σ g.gt.
(26)
We note that without the barrier term Pear in 25 the iterates in (24) can be computed in closed-form; in this case, the iterates exactly matches those of the Matrix- Feeiiix--reeraad algorithm by [18) for imconstrained Online Convex Optimization (the connection to FTRL was not made explicit in (18). The advantage of adding barrier oer that it ensure that the iterates (w:) are always in the feasible set without requiring any sophisticated iesarrainnd-t-unnonsttiiii
Remark (Connection to Matrix-FreeGrreee
reductions that may lead sub-optimal logarithmic terms in the regret (46) (see Remark in in the sequel).
Lemma 24 (Monotocity of potential). Let a, O and 7 > be given. For all gr. Rd and 14 > such that [[ge]] S hú, we have
(gr, (.) W (Gr-ii Vei V (G Ve, V,,
(27)
where G+ V'' (V denotes the Fenchel dual of w (w;; V,h,
The proof lemma is in Appendix H.3 By summing 27 over and using Fenchel duality, we obtain the following regret bound for the FTRL iterates in (4
Theorem (Regret with valid hints). Let 0,8 0 and >> given. The FTRL iterates (w:) in
24h in response to any sequence (gt) such that [[9e| s hts for all 2 1, satisfy: for all T N and
W int W:
Σ (gt. Wi w) S (0) + L (bbr(w)= V In, (det(o (o))))-2)))))))) Q+).
(28)
41

---

where I.) = 0v In(),, = -0= +VV,, and
1
{ h /wll
h7 wl E² =²p(
QT max w Erw,
In det(( 2
w ETTw
(29)
2
p())
Remark 2 (Comparison to previous miaurxx" bounds in the constrained setting). We note that by having the (log factor in (28) inside the square root, the bound in (28) improves previous "full-matrix" bounds in the constraint setting [46]. which have the log factor outside.
H.2 Implementation Considerations
As stated in Remark 2 if we remove Pear from the regularizer, then iterates in 24 match those of Fraddd which are available in closed-form. Unfortunately, in the presence of bar (which ensures that the iterates are always in the feasible set W), the iterate WN in (24 admits a closed-form expression, and computing Wr, / e [T]. now requires solving convex optimization problem. This is not ideal from computational perspective; most first-order OCO algorithms require only (dd operation per round. might be possible (at least the case where is bounded) to efficiently approximate (w;) without solving optimization problem at each step and without sacrificing the regret by much using Newton steps such as in the recent works of 47 48 49
no longer
We leave this investigation for future work.
H.3
Proof of Lemma 24
Proof. By Lemma
23 we have that for all V and h, V (; V,,,, 8) satisfies
V/" (G;VV,,
inf 4' (G u; u; vV,VV 8, + Diar (-u);
weRd
exep
(d (G-w) Ap(r)) 2h
inf A20,ueR
T bar (-u).
deet 27
(30)
We will use this to prove
Let (A.,u,) E Rgo x IRd be the minimizer in the problem 1 (G--1; Vt-1, O,E) With this notation, we have
Wr
argmin(GG.11,o)) V w.; h,),,
weltd
arrgmax(G 1 (-ww;; 11); weRd
=-argmax ( (0; V2 hz))
uaRd
=-VV" V-1, (C--iiiii-
and by Lemma 26
-
(G - I 1
(31)
Moving forward, we define
Gr-,, := Gr-1 and Gr, G u.
To prove the lemmsa, it suffices to prove the stronger statement obtained by picking the sub-optimal choice (),u) = (h., u.) for the problem TT" (G,, Vi, h4, o,5); that is,
(w+.9t)
(o +1,)) G.-1, + A.p())² 2h
Diar (-u.)
x.1) GG,, 1...+ ).p(7)2
2h
bar (-W+),
V dett(1 +0-771
o ((7) "1
42

---

and so dividing by 4- ( 1(),, and using 31 this becomes
9t - 10- Gt-,,
exp
+ + Ge,, Asp(a)² 2h 2 Indel (1+ o o
$
exp C (0 yV x.1) +X.I) Gr-1, + ).P(7)² In + -y
26g
Let us abbreviate Σ = - VV-1 A.I. The matrix determinant lemma and monotonicity of matrix
inverse give
det(I+o ng. (o2 9.) 2 In(1 1. E- 9t).
In del(1 + 2-V,11
Then Sherman-Morrison gives
Eg.
(o Ge, GT,
1+ Yg. Σ-
and splitting off the last round Gr,, G(-1,+ St gives
2G 2,,-, E- 9r 0e
1.000.1110 5 9t- 79) E9 Gr-1,)
(IIT Gr, E
1 1+79 D-1
All in all, it suffices to show
2G 2-,,
Σ- 9r 5.-5111 9t -9) Gr-1,.² ".
In + 70, I (3'1 mn)) 2
G $ 11-exp exp
2(1 79: g-)
Introducing scalars = g 2-2--1 and z 2- gr, this simplifies
2r 2r 11² -r $ 1 exp
In in(1 |n(1+
2(1+72)
Being square, 2 is positive. In addition, optimality of x. ensures that Σ- Gr-1,-||
p(x) this
v2h."
follows from the fact that ax (VN))=***V =11E- with [g < h2, we find
+V
In combination
p(>p\\//22111 1 <1
(32)
The above requirement may hence be further reorganized to
2r 2r- & - = (1 +1=+((nn11111)) (1 +~=)
21n + +r)).
The convex right hand side is minimized subject to z 0 at
1-1-21n(1-r)
max 0,
so it remains to show
2
ir 12 21n r); otherwise.
2r 2r² s
(33)
22m(1+
Note that
32 have 2 2 1 + +r) 2 1 &
and the condition in the previous display reduces
the second case; that
2r-2r² & log(1+r), V|rl 1 -
(34)
which is satisfied for the hardest case, where
27 + -1.
43

---

H.4 Proof of Theorem 23
Proof. Fix w R
Using that V V" is decreasing in h, we can telescope
27 in
Lemma 24 to obtain
T Σ g Th & V (0, V' (GrvVr,ha,,,33
By 30 we have v (0;0, h1, 0, se Bar (0) yielding:
Σ 96 14 S Bar (0)
v (Gr; VT, hT, o),
$ E oar
inf (Gr, u) V (- hr,,,,,,,))
weR
= 4 bar
inf (Gr, u) 2 -² y /V /b) Pbrr
ueRd
S 2ar (0)
Grr, w) 2 -
(or (setting u w)
T bar (0) (Gr, w) sup V w M X w (ET AZr det(a Exr)
Az0
82
+ Dar (w).
(35)
where Ex = 0² VVr and Zr /(7))/12.. Zero derivative of the above objective for À occurs at
In |=
w "ew
A
27T
2|| 2
and hence the optimum for is either that point zero, whichever is higher, with the crossover w ETE. w. Plugging that in, we find that for C' =
point at
1=12
In
|=|
|w
In l=
we have
2x
2r
Zr 2r
w (ET + Ai)we AZr del(o ET)
Vu (2T Al)w X
sup
A20
E²
In Iwl?
([C++ -X
(C u Erwwe
Zy yoy
det
if w Erw;
det(or
X(w Erw- $ VOT det(o= ²5x) QT
otherwise.
6²
(36)
E²
where Q7 max un Erw, 1w|2 In 2r w Erw) }: in the last inequality, we used that X(0) increasing drop the exponential in its argument. Combining (36) with (35) and using that
1w|2
2r
(() (0) (see Lemma 27p. we obtain the desired bound.
H.S Helper Lemmas for Full-Matrix Analysis
Lemma 26. Let W c Rd and y = R. Further, let f x R be differentiable functiooo such that for all x e X, the problem inf f(z y) has a unique minimizer y(z). Then,
V. x())) = (,,((x,(x)))
(37)
Lemma 27. For 2 0, define X(0) = sup, a-e - In0 Then X(!) (VV) Vln o(1).
Proof. The fact that X(0) (2 (W())) -1/2 follows from 50 Lemma 18). Recall that
sup yT ex y ylay-1 y
44

---

Hence
22 ln8
x(0) sup
a²
1 InO
sup
1)
+ m-nn-1
" In + +n
inf 2n 2
< min VIn 1+ 2
Inln
v0
Vho
2
v0)
$ Vl..
where plugged in the sub-optimal choices 1) Vind stick in Viuter" -0)
(this requires 0 2 1) and rj
1 v8
When
we find
In + +0) Ino In In(nne=* + +0)) -2 s Vin(ee" + +0)
X(0) &
2 In( e +0)
Note that e
1.14492. This is less than 2, the value of 0 where v0/2-1/VB becomes positive. 17
I Complete Psuedocode for Regularized 1-Dimensional Learning
In Algorithm 6 we provide self-contained implementation of an algorithm for regularized online
learning (Protocol The algorithm is obtained by combing Algorithm 3 with Algorithm
L.1 Efficient Projections for (=) =
Our algorithms for regularized online learning via epigraphs (Protocol 3 require projections the set {yy (x)).. While in general this projection may be expensive, for simple function vA of interest, such as vi(2 ((2 =², this projection is relatively straightforward. In the following we provide a formula for this projection that is easy to compute (if a little ungainly to look at).
Proposition 28. Let th R R be given by (())= x² Define the norm (x, 22 hx² + 722y² u the
function S( )) = inf ynf))v(x) [1x,,) y) (ă, 1, and the projection P( 9) = argmin (2)(x)) (x,
(.. 1. Then for any < ((), we have P( 9) (x.1) with y x² and:
2//3 GG2 -22-21
2
T=
71/3
6 61/32222
with
Z = - 29160222222222 (6G2 -
Moreover, VS(2,0)
(3aax)
72(0-) ((
Proof. Since the (x, y) is on the boundary of the constraint, we clearly have y = 2 Note that (+. 1 Thus, by LaGrange multipliers, we have for some A:
(x, u) = argmin (zx(z) [ (x.
2G 5) > 2
2y 9) = --
45

---

Algorithm 6 Regulaarzed 1-dimensional learner (REG) for Protocol 2
Input: Non-negative convex function & IR R. Parameters 7 0, e [0, 1/2]. c 0 and
Es 0 Initialize =
if p- 1/2 then
Define constant 3
else
Define constant end
for I 1 T do
Receive h4 hi-11 R.
Set h 3h2. Set h. = =37
Define V," = -h62
Σ1 (1,))
Define V." = 97
E1=1(0))
if pp= 1/2 then
Set of
C+ (9F) log (oe
Set o.-
(e)
else
Define of
c+ ((:))))))))))))
Define a.
o(e)
(+tE. - + ())))))
end if
(EL 9²
if 1 g
2 by
Define O7
4R2V=
S
Eiig 97
v
otherwise
khg
(b))z
[x==) x!)
if 2---1 0 2
Define 07
1k2V"
V
otherwise
(
Set 8. sign
E gf) of (exp(07) 1)
Set 01 = sign
[E=1 9. of (exp(()))1) 11)
Define the norm (Ix, 1/22 + +22y². with dual norm [(g,a)
o² 2
67 72.
Define S, ( 5) -nn i= ( 1) (1.
Compute Tt, y/+ argminggwitc
(xt. (f.
Output w, 2t, receive feedback g: ([- a [0, 7], such that a, unless I h4.
Compute (8,,5%) ) I9ull.,e (S, 0c)
Set gf gi + 87
Set 0e 8.
end for
46

---

This implies:
G
G2 X
y= 27
Moreover, also must have y x², that:
G
G²
-
(G² X)2
272
272
(G² -)a
G 27²
(G - - G²
2y2
This is clearly cubic equation X, and so we can apply the cubic formula (via Mathematica) to obtain the following result:
2G
2729
25/3 22 2
22/3
23/3
9 9-25/372
where
Z = 108G
2. 2/291602, (6G2,2- 12>^D)3
which yields:
212
-2720)
2/3
Z1/3
6 2/3/2
and y = 2
The expression for VS($,)) follows directly from 16 Theorem 4.
47

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims do accurately reflect the paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, see the discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
48

---

We provide a proof-sketch in the main paper and detailed proof's in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
49

---

Answer: [NA]
This paper has only mathematical congtent. There are no experiments this paper.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
Sooliic/uuides/Cod@uubbsa
cocc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
ssionlolccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are no experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by eπror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
50

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///arrrp..cooo//////cccccaa
Answer: [Yes]
Justification:
This paper does conform to the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper provides a purely mathematical contribution. As such, it subject to the standard ethical concerns present for all mathematical papers, but no further ones.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
51

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recogmize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
52

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this рaper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are no experiments this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
53

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
54


Reviews:
[{"review_id": "F5Rem73wFz", "reviewer": "Reviewer_xTkL", "summary": "This paper considers the fully unconstrained online convex optimization. At each round, the learner needs to choose a vector w_t and then observes the loss vector g_t and suffers the loss of the inner product of w_t and g_t. The goal is to design a learning algorithm to minimize the regret with respect to a comparator w*.\n\nPrevious work provides algorithms that require prior knowledge of either the length of w*, or the maximum length of loss vectors g_t. This work provides an online learning algorithm that achieves the regret bound of G^2+|w*|^2+ |w^*| G sqrt{T} where G is the maximum length of loss vectors.", "questions": "1 What is the regime that the new bound is significantly better than the previous bound? How should I think about those regimes and connect them to some specific examples or applications?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1 This paper provides an algorithm that improved the regret bound for the fully unconstrained online convex optimization. It achieves the optimal bound for all sublinear regret regimes. The previous work for fully unconstrained online learning has a larger additive term G|w*|^3, which can not get the optimal bound for all sublinear regimes.", "weaknesses": "1 The paper introduces a lot of notations before defining them properly. It is not easy to read and have a general idea about the techniques. \n\n2 The paper did not provide a detailed discussion about why the prior knowledge of the length of w* and the maximum length of the less vectors is unavailable in practice. It makes it hard for the reader to understand the merit of the new algorithm in this problem and the real-world applications. Especially, the bound in previous work for a fully unconstrained setting also gets the optimal bound for a wide-range regime. What is the regime in which the new bound is significantly better than the previous bound? How should I think about those regimes and connect them to some specific examples or applications?\n\n-------------------\nafter the response:\nThey discussed the regimes where their bound is much better than the previous bounds. They also explained the unavailability of prior knowledge in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your work reviewing our paper! Regarding the unvailability of prior knowledge of $\\|w_\\star\\|$ and $G$ in practice, let's think about the stochastic optimization setting. In this case, the unavailability of $G$ in practice is *exactly* the problem that popular methods like AdaGrad (the precurser to Adam) actually solve. However, these algorithms still require tuning a learning rate scalar, which roughly corresponds to selecting the value for $\\|w_\\star\\|$. In fact, we actually have trouble coming up with many compelling examples in which $\\|w_\\star\\|$ *is* available ahead of time.\n\nRegarding your question, the new bound is better in two important regimes:\n1. When the $\\|w_\\star\\|$ is large or $\\gamma$ is small, so that the difference between the $\\|w_\\star\\|^3/\\gamma^2$ penalty incurred by the previous bounds is large compared to the $\\|w_\\star\\|^2/\\gamma$ penalty we incur. See also the response to review 1CHH, in which we observe that if both our bound and the previous bound are provided the optimal tuning for $\\gamma$, our bound is always better.\n2. For a more intuitive setting, consider a stochastic optimization problem in which the losses are *smooth* and $\\ell_t(w_\\star)=0$ for all $t$. In this case, by applying standard self-bounding arguments (e.g. see section 4.2 of [A modern Introduction to Online Leraning](https://arxiv.org/pdf/1912.13213)), we will actually obtain *constant* regret due to our dependence on $\\sum_{t=1}^T \\|g_t\\|^2$, while the previous bound that depends on $\\sum_{t=1}^T G \\|g_t\\|$ will at best obtain $O(T^{1/3})$ regret.", "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": "", "extra_scores": {}}, {"review_id": "YkSLUgGVRa", "reviewer": "Reviewer_q7Dc", "summary": "The authors consider the task of unbounded online convex optimization\nwithout prior knowledge of the magnitude of the comparator nor the largest gradient. \nIn this context, they propose a parameter-free method whose regret against any arbitrary comparator \n$w_*$ matches the optimal bound of $\\mathcal{O}(G||w_{\\*}||\\sqrt{T})$ up to logarithmic factors when considering \n$G$-Lipschitz losses. Their method has access to internally constructed hints at each time step -- which serve to control the gradients in the learning process, and regret bound. From prior works, learning with such hints is enough to derive reasonable regret bounds when the magnitude of the learners actions $||w_{t}||$ is small. To this end, the authors focus on controlling $||w_{t}||$ in the regret bound. They propose to optimize a regularized loss, which for a specific choice of the regularization parameter eliminates $||w_{t}||$ for the bound at the cost of additional factors of $||w_{\\*}||$ and the largest hint. Finally, they implement this regularization trick with constraints and prove tightness of their result with lower-bounds.", "questions": "I have some clarification questions, and comments below.\n1. Just for clarification, can the authors explain why it is necessary to replace the regularization terms in the loss with constraints?\n2. From the analysis of [1], it seems plausible that, for quadratic\n\tlosses at least, regularization can be applied to completely eliminate the \n\tmagnitude of the iterates in the regret bound at the cost of an additional \n\tfactor of the magnitude of the comparator, but not the largest gradient.\n        Actually, having the largest gradient in the upper-bound might not be good, for example in the case of quadratic losses, as the gradients may scale with $||w_{t}||$ as well. What are the authors thoughts on the dependence of $G$ in the regret bound especially for quadratic losses?\n3. Can this method be directly extended to work with noisy gradients?\n\n**Comments**\n1. In Equation 1, the inequality should be an equality. Same holds for Equation 4, the expression in Theorem 1, e.t.c.\n2. In line 66, do you mean \"... in our bound (2)\"?\n3. Line 4 of Protocol 2 should read \"loss vector $\\tilde{g}\\_{t}$\" not \n\t\"loss $\\tilde{g}\\_{t}$\".\n4. Line 231 should be \"... the outputs \n\t$w_1,w_2,\\cdots\\in\\mathbb{R}^d$...\"\n5. Line 104 should be \"... but is not a major focus...\"\n\n[1] Neu, G., & Okolo, N. (2024). Dealing with unbounded gradients in stochastic saddle-point optimization. arXiv preprint arXiv:2402.13903.", "limitations": "Nil", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This paper contributes to the budding line of work on near-optimal parameter-free online convex optimization. The authors build on the seminal work of Ashok Cutkosky on Artificial Constraints and Hints for Unbounded Online Learning, and address, in a unique way, a significant constraint in that work. \n2. The paper is technically sound. The authors are honest about their methodology and adequately cite related works. Also, the submission was clearly written.\n3. Overall, the authors address an important yet complex task by combining existing techniques in an unconventional way.", "weaknesses": "1. The authors discuss a number of preliminary ideas and independently interesting techniques which might be useful \n\tfor some to understand their thought process, but distracting for others who are more interested in the main claims, method and result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review! Below we answer your questions.\n\nQ1: It is may not be strictly \"necessary\" to replace the regularization with a constraint - we suspect that in fact a suitable variation on e.g. FTRL based algorithms would also achieve the same goals. However, the constraint approach led to an algorithm that does not require solving a complex subproblem, and we also feel it is inherently interesting as it is a technique less commonly deployed in online optimization.\n\nQ2: We agree, the technique of [1] is essentially to apply an extra quadratic regularizer to an FTRL update. We believe an approach along these lines could achieve the same results we have for the quadratic case without using constraints. However, it would probably not remove the $G^2$ dependence on its own because the $G^2$ dependence arises from the calculuation that makes eliminating $\\|w_t\\|^2$ a useful thing to do.", "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": "", "extra_scores": {}}, {"review_id": "EFt23hDyHE", "reviewer": "Reviewer_Wuav", "summary": "The authors propose a new algorithm for parameter-free online convex optimization without knowing the Lipschitzness of losses. Here, parameter-free online learning refers to a framework that achieves the optimal regret upper bound without knowing the magnitude of an (optimal) comparator. \nThe new parameter-free bound in the paper achieves a regret upper bound very close to the optimal regret upper bound $\\|| w_* \\|| G \\sqrt{T}$ obtained when the magnitude of the comparator $\\|| w_* \\||$ and the Lipschitz continuity $G$ of losses are given before the game starts. The resulting regret upper bound is the first second-order bound in parameter-free learning without knowing the Lipschitzness of losses, and the dependency on the user-defined tradeoff parameter $\\gamma$ is improved. To achieve this upper bound, the authors consider sequentially reducing general online convex optimization to one-dimensional online convex optimization, to a regularized online learning with magnitude hints, and to an epigraph-based regularized online learning setting, and derive the desired regret upper bound by effectively combining the latest techniques in existing online convex optimization.", "questions": "It is expected that the authors will address the questions mentioned in the Weakness section.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors make a solid contribution to parameter-free online learning under the assumption that both the magnitude of the comparator $\\|| w_* \\||$ and the Lipschitz continuity $G$ of the loss are unknown. In particular, the second-order bound, which is one of the main differences from existing bounds, is an important contribution.\n\nThe quality of the paper is high. Although the presentation is very dense, it is clear, and the flow of the sequence of reductions and their motivations are explained in a comprehensive manner. The proof sketch of Theorem 1 in Section 3.2 is clearly given while explaining the existing techniques in online convex optimization. I have only partially reviewed the proofs in the appendix, but they appear to be correct.", "weaknesses": "A potential weakness of this paper is the density of the presentation.\nIt appears that the authors assume a significant level of knowledge from the readers about parameter-free online learning and general online convex optimization. The sequence of reductions is particularly dense and closely related to very recent research, which is not widely familiar within the community. It would be beneficial to provide more explanation especially concerning Epigraph-based Regularized Online Learning (in Protocol 3) (and Protocol 2 if possible).\n\nThe sequence of reductions begins with the reduction to one-dimensional OCO in Algorithm 1 in Appendix B. However, $w^{1d}_t$ does not seem to be defined in or around Algorithm 1. Can the authors provide an explanation for this?\n\nMinor issues:\n- Line 86: [15] Theorems 2 and 3 (similar typos are present in several places in the appendix)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your work reviewing our paper!\n\nW1 (Regarding the density of the presentation): We chose a presentation intended to communicate all of the ideas, but it might become difficult to follow and we will work to make things clearer in the revision. For the epigraph-based learning, the idea is the following:\nSuppose you are interested in an online learning problem with losses of the form $\\ell_t(w) = \\langle g_t, w\\rangle + a_t \\psi(w)$ for some *known* function $\\psi$. We are guaranteed $\\|g_t\\|\\le 1$ and $a_t \\in[0,1]$, but $\\psi$ may not be Lipschitz. This means that we cannot apply the standard linearization trick $\\ell_t(w)-\\ell_t(w_\\star) \\le \\langle \\hat g_t, w-w_\\star\\rangle$ with $\\hat g_t= g_t +a_t \\nabla \\psi(w)$ and then run an OLO algorihtm using $\\hat g_t$ because $\\hat g_t$ is not bounded. To fix this, we instead consider the 2-dimensional problem with parameter $(w_t, y_t)$ subject to the constraint $y_t \\ge \\psi(w_t)$ and *linear* losses $\\hat \\ell_t(w_t, y_t) = \\langle g_t, w_t\\rangle + a_t y_t$. This has the property that $\\hat \\ell(w_t, y_t) - \\hat \\ell_t(w_\\star, \\psi(w_\\star)) \\ge \\ell_t(w_t) - \\ell_t(w_\\star)$, so it suffices to control the regret on the constrained linear problem.\n\nFor protocol 2, the idea is that when one checks the analysis of essentially any algorithm that assumes a fixed Lipschitz constant, it is usually fairly easy to change the algorithm to allow for the Lipschitz constant to grow over time. Protocol 2 captures this by letting $h_t$ describe the growth in the Lipschitz constant. Of course, in general we do not know how it might grow over time, which is what the clipping technique in our final analysis addresses.\n\nW2 (definition of $w^{1d}_t$ in Algorithm 1): We apologize for the typo here: $w^{1d}$ is the same as $w^{\\text{magnitude}}$. In the revision we will only mention $w^{\\text{magnitude}}$ and convert all the $1D$ superscripts to $\\text{magnitude}$. Intuitively, the idea is that the 1-dimensional learner $\\mathcal{A}^{1D}$ is responsible for learning the magnitude of the comparison point $u$, while the direction $u/\\|u\\|$ is learned by a standard mirror descent algorithm in $w^{\\text{direction}}$. See also the development in Sections 3 and 4 of https://arxiv.org/pdf/1912.13213, which is where we got these reductions.", "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": "", "extra_scores": {}}, {"review_id": "M9X9s8C6nB", "reviewer": "Reviewer_1CHH", "summary": "This paper studies online convex optimization without prior knowledge of the Lipschitz constant of the losses or constraints on the magnitude (in $\\ell_2$-norm) of the competitor. They provide a regret bound that almost matches the optimal regret with knowledge of these quantities (with some additive terms independent of the time-horizon), which improve on similar bounds from prior work. They also provide matching lower-bounds.", "questions": "See some questions in the weaknesses section.\n- What happens if the competitor $w_\\star$ becomes very small (or even exactly 0), do the bounds still hold ? Similarly if the $g_t$’s are all $0$, then the bound (3) goes to 0 but your bound does not, is this a problem with your analysis or is there an easy fix ?\n- The bounds apply to the linearised version of the regret, which usually means that properties of the losses such as strong convexity cannot be exploited to achieve better than $\\sqrt{T}$ regret. How would your bounds / algorithm behave in such settings ?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "- The regret bounds significantly improve upon prior work in certain settings, e.g. when $||g_t||=G$ for all $t$ or can have milder dependence on the $\\gamma$-parameter.\n- A lower-bound is provided to establish the tightness of their bounds.\n- They exploit reductions from prior works that make some aspects of the analysis easier to present and follow. Their proposed regularisation of the losses  is an interesting technical contribution.", "weaknesses": "- The improvement upon prior work is only relevant under specific conditions.  In particular, if $||g_t||$ is not constant and many are small (or even 0) and only a few are large, it is unclear which bound is better. It would also be interesting to have a comparison of the bounds for the “optimal” value of $\\gamma$ (which of course is not of practical use but may help provide some intuition).\n- The focus is only on the constraints expressed w.r.t. the $\\ell_2$-norm and it is unclear if these results extend to arbitrary norms.\n\nThe presentation and clarity of some parts of the paper: the introduction is rather clear but the links between the different parts of the rest of the paper could be improved: \n- It could be made clearer when introducing protocol 2 that you will use the original problem to generate these values of $h_t$ and $a_t$ to feed to an algorithm solving protocol 2. As it stands, as a reader it is unclear how/why “nature” generates or reveals these things. I wonder if going down this line of using a reduction is really the best way to present it and if immediately explicitly giving what these quantities will be ($h_t, a_t$) is not a clearer (and simpler) way to do it. This is explained in lines 142-144 but something like this should be explained at least at the beginning of Section 3 or 3.1. The link between protocol 1 and 2 does not come across that clearly (and in particular that Protocol 2 is an easier problem). It is also not clear why (4) is our goal - I guess the point is that this reduction and achieving (4) implies (2) but this is not explicitly said when presenting Protocol 2. (again this is discussed somewhat in the proof of Theorem 1 (lines 139-140) but Protocol 2 is introduced beforehand and it would help to have some context).\n- Similarly, in the introduction, your results are presented in (2) and in the main paper in Theorem 1 but the relation between the two is not mentioned. In particular, Theorem 1 is quite a complicated looking bound and so it would be nice to have the implication explicitly stated.\n- The paper is presented as solving two main challenges, not knowing $||g_t||$ and $||w_\\star||$ ahead of time. However, dealing with the former seems to be already well understood (e.g. lines 147-157) and it is really the latter that is the challenge in this paper (lines 107-108 - correct me if I have misunderstood). The distinction between these two is not clear from reading the introduction.\n- I am confused by lines 109-111: if $a_t = 0$ then $\\tilde{g}_t + a_t \\nabla \\psi(w_t) = \\tilde{g_t}$ ?\n- At the start of the proof of Theorem 1 (section 3.2), you define the notation REG for the algorithm solving protocol 2. But then in lines 186-188, I believe you want to show a regret bound for REG on protocol 2 (i.e get the bound (4)), why not use the notation you defined to link these different parts and provide better guidance on the steps of the proof? In this section, you also show a “weaker” version of (4), which to me seems stronger because the presence of $\\gamma < 1$ means it is a smaller upper-bound than (4) - maybe I am misunderstanding your use of “weaker” (this is also the case in section 3.3 for (6) vs (7)) ? In any case, if the proven bound is (7) instead of (6) (or the one in line 188 with S instead of (4)) and this is a smaller upper-bound, why not only consider this one ? Is there a specific reason why the ones presented in (4) and (6) are more interesting ?\n- Similarly to the comment on linking Theorem 1 to (2), it would help to have something like this for Theorems 2 and 3 (and 4). For example, does Theorem 2 also lead to (2) or if not how do they differ in these simplified forms ? Given the amount of terms in these theorems, it is hard to assess if Theorem 4 is tight compared to the other Theorems.\n- It would also be useful to have pointers to where the proofs of some of the later Theorems could be found.\n- It would be nice to have a dedicated related works section that contextualises your results in the context of other works. This is done im some parts of the paper but having a dedicated section solely to this would improve clarity.\n- Calling the (sub)-gradients of the losses $g_t$ loss vectors can be a bit confusing at first (especially that $\\partial \\ell_t$ is not defined anywhere I believe).\n\nTypos:\n- Line 66: “in our bound (3)” - which should be (2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your very detailed review and you careful comments on the presentation. We will work hard to incorporate your comments into the final version. In the interest of brevity, below we respond to just a few of your comments:\n\n* For the \"optimal\" value of $\\gamma$ our bound is always better. This is because for the optimal $\\gamma$ value the previous bound is $O\\left[\\|w_\\star\\|\\sqrt{\\sum_{t=1}^T \\|g_t\\|^2} + \\|w_\\star\\| G^{2/3}\\left(\\sum_{t=1}^T \\|g_t\\|\\right)^{1/3}\\right]$ while ours is $\\tilde O\\left[\\|w_\\star\\|\\sqrt{\\sum_{t=1}^T \\|g_t\\|^2} + G\\|w_\\star\\|\\right]$ where $G=\\max_t\\|g_t\\|$. Thanks for suggesting this comparision!\n* We can actually deal with arbitrary Banach spaces (so any reasonable norm). This is because the reduction in Section 3 of https://arxiv.org/pdf/1802.06293 shows that to solve an online learning problem in a Banach space, you need only be able to solve it in 1-dimension. We focused on the familiar L2 case here to tame the complexity a little bit.\n* There are by now many algorithms that deal with either unknown $G$ or unknown $\\|w_\\star\\|$ ahead of time - it is dealing with both at once that is somewhat more rare. That said, the unknown $\\|w_\\star\\|$ case is arguably more challenging. Our particular approach works by improving algorithms that deal with known $\\|w_\\star\\|$, which is why our exposition focuses on these problems.\n* Regarding Lines 109-110: That's right. In these lines we are suggesting a straw-man algorithm: replace $\\tilde g_t$ with $\\hat g_t= \\tilde g_t + a_t \\nabla \\psi(w_t)$. Then we could try to solve the problem by considering the pure linear losses $\\langle \\hat g_t, w\\rangle$, which would be equivalent to the case $a_t=0$.\n* The weaker bound (7) vs the bound (4). We believe (4) is actually smaller than (7), not the other way around. This is because (7) depends on $\\gamma \\sum_{t=1}^T a_t$ while (4) depends on $\\sum_{t=1}^T a_t^2$, and $a_t\\le \\gamma$ for all $t$. We chose to present (4) first because it is the true \"ideal\" bound, and we can in fact achieve it with a more computationally expensive algorithm.\n\n\nQuestions:\n1. Yes, the bounds hold for all $w_\\star$ simultaneously, including 0. In the case $w_\\star=0$, our bound achieve *constant* regret, while the previous approach achieves $O(\\sqrt{T})$ regret. For the case $G\\to 0$, you're right our bound appears to not go to zero. However, we believe this is an artifact of analysis: notice that *all algorithms* achieve zero regret when $G\\to 0$. In our particular case, the algorithm will set $w_t=0$ for all $t$, as one might intuitively expect.\n2. The unconstrained strongly convex setting is perhaps understudied in online learning: even the standard $G^2\\log(T)$ bound doesn't really make sense since $G$ is unbounded in the unconstrained setting. We would suffer from this same issue. It's an interesting open problem to deal with this!", "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": "", "extra_scores": {}}, {"review_id": "3ow8kCymrO", "reviewer": "Reviewer_itTv", "summary": "The paper presents the first $\\tilde{O}(G \\lVert w_\\star \\rVert \\sqrt{T} + \\lVert w_\\star \\rVert^2 + G^2)$ guarantee for online convex optimization without assuming known-in-advanced bounds of either the gradients or comparator norms. This result matches the best possible rate given known bounds in the main regime of interest where sub-linear regret is possible (while $G \\lVert w_\\star \\rVert$ are not overly small). Additional results include a generalization of the method to a frontier of bounds using parametric regularization and a complementary lower bound.", "questions": "4. Considering the stochastic case (with online-to-batch) with crude bounds of the comparator and stochastic gradient norms, [1] can obtain a price-of-adaptivity of $\\widetilde O(R/\\sqrt{T})$ instead of the $\\widetilde O(\\max\\{L,R\\}/\\sqrt{T})$ mentioned in the discussion. Can such knowledge be used to obtain a similar result using the approach presented in the paper?\n\n5. Again considering the stochastic case (with online-to-batch), recent results [2-4] with crude bounds depend on the noise bound (a stronger noise assumption) instead of the bound of the stochastic gradient norms. Is there a possibility for a better online-to-batch conversion which enjoys such refined guarantees using online parameter-free algorithms? Or, alternatively, a direct application of the techniques in the stochastic setting?\n\nOverall, the paper presents a clear picture of the current state of ''fully parameter-free'' optimization for online learning and presents a new guarantee with desirable properties (and a more general frontier using parametric regularization), both of value to the online parameter-free literature.\n\n[1] Ashok Cutkosky. “Artificial Constraints and Hints for Unbounded Online Learning”. In: Proceedings of the Thirty-Second Conference on Learning Theory. 2019, pp. 874–894.\n\n[2] Attia, A. and Koren, T., 2024. How Free is Parameter-Free Stochastic Optimization?. arXiv preprint arXiv:2402.03126.\n\n[3] Khaled, A. and Jin, C., 2024. Tuning-Free Stochastic Optimization. arXiv preprint arXiv:2402.07793.\n\n[4] Kreisler, I., Ivgi, M., Hinder, O. and Carmon, Y., 2024. Accelerated Parameter-Free Stochastic Optimization. arXiv preprint arXiv:2404.00666.", "limitations": "Incomparable results with previous work, which are discussed in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper unrolls a detailed discussion and comparison with previous work, providing an in-depth understanding of the problem, including both results and techniques.\n\n2. The guarantee is new and possesses several properties that are more appealing than previous ''fully parameter-free'' results, including a nicer symmetry between $G$ and $\\lVert w_\\star \\rVert$ without a dependence in $T$ on the excess terms.", "weaknesses": "3. As the authors mention, an ideal result would also include previous results that are incomparable with the new bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\nQ1: Yes, in a certain sense. The way to to obtain the improved PoA using [1] is simply to only do the clipping suggested by [1] and not the artificial constraints - instead just rely upon the coarse bound on $\\|w_\\star\\|$. We could do the same thing by just replacing our regularization with a constraint to the coarse bound, which makes the two algorithms the same. That said, it would better to have a \"cleaner\" way to do this.\n\nQ2: Yes, our bound implies this sort of result immediately. In general, \"variance of gradients\"-style bounds for smooth losses are implied by any online algorithm whose regret bound depends on $\\sum_{t=1}^T \\|g_t\\|^2$. \n\nTo see this, let $L$ be the expected loss. Then we have $\\sum_{t=1}^T \\|g_t\\|^2 \\sim \\sum_{t=1}^T \\|\\nabla L(w_t)\\|^2 + T\\sigma^2 \\le \\sum_{t=1}^T L(w_t) -L(w_\\star) + T\\sigma^2$. So, our regret bound looks like $\\sum_{t=1}^T L(w_t) - L(w_\\star) \\le O(\\sqrt{T\\sigma^2 + \\sum_{t=1}^T L(w_t) - L(w_\\star)})$, which implies $\\sum_{t=1}^T L(w_t) - L(w_\\star) \\le O(1+\\sqrt{T\\sigma^2})$. This is one motivation for why we wanted to achieve the $\\sum_{t=1}^T \\|g_t\\|^2$ in the regret bound rather than $G\\sum_{t=1}^T \\|g_t\\|$ as obtained by the previous work.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies online learning without knowing either an upper bound on the norm of the loss vector or the norm of the optimal solution and provides a protocol with regret that, in some regimes, can match the optimal regret bounds when these quantities are known. Though the reviewers agree that the theoretical contribution of the paper is qualitatively significant, there is also a majority consensus that the presentation of the paper needs attention.

I suggest the authors incorporate reviewer feedback to improve the overall presentation and strengthen the potential impact of the work.
Decision: Accept (poster)