Fully Unconstrained Online Learning

Authors: ashok  cutkosky
zakaria  mhammedi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:04:01

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.

Main paper: 
 notation: 
 Throughout this paper, we use W to refer to a convex domain contained in R d . Our results can in fact be extended to Banach spaces relatively easily using the reduction techniques of [15] , but we focus on R d here to keep things more familiar. We use ∥ ⋅ ∥ to indicate the Euclidean norm. Occasionally we also make use of other norms-these will always be indicated by some subscript (e.g. ∥ ⋅ ∥ t ). We use R ≥0 to indicate the set of non-negative reals. For a convex function F over R d , the Fenchel conjugate of F is F ⋆ (θ) = sup x∈R d ⟨θ, x⟩ -F (x). We occasionally make use of a "compressed sum" notation: g a∶b ∶= ∑ b t=a g t . We use O to hide constant factors and Õ to hide both constant and logarithmic factors. All proofs not present in the main paper may be found in the appendix.We will refer to the values g t provided to an online learning algorithm interchangeably as "gradients", "feedback" and "loss" values. We will refer to online learning algorithms occasionally as either "learners" or just "algorithms".A outputs w t .3. If w t < -2ϵ -∇ψ ⋆ γ (2h 1 (t -1)), set g t ← -2(t -1)h 1 and for all k ≥ 1 set g t+k ← 0. 4. Else g t ← h 1 .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 are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
overview of approach: 
 Our overall approach to achieve (2) is a sequence of reductions. As a first step, we observe that it suffices to achieve our goal in the special case W = R. Specifically, [15] Theorems 2 and 3 reduce the general W case to W = R case. We provide an explicit description of how to apply these reductions in Section C. So, we focus our analysis on the case W = R. Next, we reduce the problem to a variant of the online learning protocol in which we also must contend with some potentially non-Lipschitz regularization function (Section 3.1). Finally, we show how to achieve low regret in this special regularized setting (Section 3.3).Our bound is achieved via a reduction to a variant of Protocol 1 with two changes. First, the learner is provided with prior access to magnitude hints h t ∈ R that satisfy ∥g t ∥ ≤ h t . 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 ⟨g t , w⟩, but a regularized non-linear loss ⟨g t , w⟩ + a t ψ(w) for some fixed function ψ ∶ W → R ≥0 that we call a "regularizer". Formally, this protocol variant is specified in Protocol 2.Protocol 2. Regularized Online Learning with Magnitude Hints. Input: Convex function ψ ∶ W → R ≥0 . For t = 1, . . . , T :1. Nature reveals magnitude hint h t ≥ h t-1 ≥ 0 to the learner. 2. Learner outputs w t ∈ W.3. Nature reveals loss gt with ∥g t ∥ ≤ h t and a t ∈ [0, γ] to the learner. 4 . Learner suffers loss ⟨g t , w t ⟩ + a t ψ(w t ).The learner is evaluated with the regularized regret ∑ T t=1 ⟨g t , w tw ⋆ ⟩ + a t ψ(w t )a t ψ(w ⋆ ). The goal is to obtain:EQUATIONIn the special case that ψ(w) = 0 (i.e. the a t are irrelevant, or all 0), then various algorithms achieving the desired bound (4) are available in the literature [17, 20, 22, 25] . We provide in Algorithm 3 a new algorithm for this situation that achieves the optimal logarithmic factors-there is in fact a pareto-frontier of incomparable bounds that differ in the logarithmic factors. [25] provides the first algorithm to reach this frontier, while our method can achieve all points on the frontier1 . 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 as the difference is only in the logarithmic terms.Challenge of achieving (4) . Achieving the bound ( 4) is challenging when ∥w ⋆ ∥ 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 2 to the case in which a t = 0 for all t by replacing gt with gt + a t ∇ψ(w t ), and then possibly modifying the magnitude hint h t in some way to now be a bound on ∥g t ∥. However, this approach is problematic because the expected bound would now depend on ∑ T t=1 ∥g t + a t ∇ψ(w t )∥ 2 rather than ∑ T t=1 ∥g t ∥ 2 and ∑ T t=1 a 2 t . This means that the naive regret bound would be very hard to interpret as w t would appear on both the left and right hand sides of the inequality.Another possibility is a follow-the-regularized leader/potential-based algorithm, making updates:EQUATIONfor some sequence of "potential functions" P t ∶ W → R. In fact, this approach can be very effective; this is roughly the method employed by [26] for a similar problem. However, deriving the correct potential P t and proving the desired regret bound can be very difficult, and could easily require separate analysis for each different possible ψ function. For example, [26] 's analysis specifically applies to ψ(w) = ∥w∥ 2 . There is other work on similar protocols using approximately this method, such as [27] , 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 as ψ(w) = ∥w∥ 2 . In fact, the method of [26] 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 = R.Re-parametrizing to achieve (4) . In order to achieve the bound (4) in the special case W = R, we will employ a standard trick in convex optimization: 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 t ∈ W, we will output (x t , y t ) ∈ W × R, but subject to the constraint that y t ≥ ψ(x t ).We provide details of this approach in Section 3.3.With all of these technicalities introduced, we are ready to provide an outline of our method. The key idea is to show that for a very peculiar choice of coefficients a 1 , . . . , a T and some simple clipping of the gradients g t , we are able to achieve the following result. Theorem 1. There exists an online learning algorithm that requires O(d) space and takes O(d) time per update, takes as input scalar values γ, h 1 , and ϵ and ensures that for any sequence g 1 , g 2 , ⋅ ⋅ ⋅ ⊂ R d , the outputs w 1 , w 1 , ⋅ ⋅ ⋅ ⊂ R d satisfy for all w ⋆ and T :EQUATION))] ,whereG = max(h 1 , max t∈[T ] ∥g t ∥) and V = G 2 + ∑ T t=1 ∥g t ∥ 2 .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 ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ Õ ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵG + ϵ 2 γ + G 2 γ + ∥w ⋆ ∥ T ∑ t=1 ∥g t ∥ 2 + ∥w ⋆ ∥G + γ∥w ⋆ ∥ 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦Here if we should think of h 1 and ϵ as conservative under-estimates of max t ∥g t ∥ and ∥w ⋆ ∥. Notice that decreasing h 1 and ϵ 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 h 1 ≤ max t ∥g t ∥ and ϵ ≤ ∥w ⋆ ∥, then the above bound is exactly the previously stated equation (2).Let us suppose for now that we have access to an algorithm that achieves the bound (4) under Protocol 2. Let us call it REG. In this section, we will detail how to use REG to achieve our desired goal (2) under Protocol 1 with W = R: in this sketch, we treat all values as scalars, and never vectors.Recall that it suffices to consider W = R to achieve the result in general. Given an output w t from REG, we play w t and observe the gradient g t . We will then produce a modified gradient gt , a scalar a t , and a magnitude hint h t+1 to provide to REG such that gt and a t satisfy the constraints of Protocol 2. We will set ψ(w) = w 2 , and then by careful choice of gt , a t , and h t+1 , we will be able to establish Theorem 1.There are two key steps in our reduction. The first step is now a standard trick originally used by [17, 22, 28] to reduce the original Protocol 1 to Protocol 2. The idea is as follows: let us seth t = max(h 1 , |g 1 |, . . . , |g t-1 |) for some given "initial value" h 1 ≥ 0. Notice that h t may be computed before g t is revealed and that the value G specified in the theorem satisfies G = h T +1 . Then, upon receiving a gradient g t , we replace g t with the "clipped" gradient gt = (1 ∧ ht |gt| ) ⋅ g t . The clipped gradient gt satisfies |g t | ≤ h t by definition. We then pass gt in place of g t to an algorithm that interacts with Protocol 2. It is then relatively straightforward to see that for all w ⋆ ∈ W:T ∑ t=1 g t (w t -w ⋆ ) ≤ T ∑ t=1 gt (w t -w ⋆ ) + T ∑ t=1 |g t -g t ||w ⋆ | + T ∑ t=1 |g t -g t ||w t |, ≤ T ∑ t=1 gt (w t -w ⋆ ) + h T +1 |w ⋆ | + T ∑ t=1 (h t+1 -h t )|w t |.At this point, prior work [17, 22] observed that if we could constrain |w t | to have some chosen maximum value D, then the final summation above is at most h T +1 D. By carefully choosing D in tandem with an algorithm that achieve (4) in the case ψ(w) = 0, one can achieve the previous "compromise" bound (3). This is where our second key step (which is our main technical innovation) comes in. Instead of explicitly enforcing |w t | ≤ D, we will apply a "soft constraint" by adding a regularizer. Surprisingly, we will add a very tiny amount of regularization and yet still achieve meaningful regret bounds.Recall that we are assuming access to an algorithm that achieves the bound (4) when interacting with Protocol 2. Let us set ψ(w) = w 2 . Then, observe that for any choices of a 1 , . . . , a T :T ∑ t=1 g t (w t -w ⋆ ) ≤ T ∑ t=1 (g t (w t -w ⋆ ) + a t ψ(w t ) -a t ψ(w ⋆ )) + T ∑ t=1 |g t -g t ||w ⋆ | + w 2 ⋆ T ∑ t=1 a t + T ∑ t=1 (|g t -g t ||w t | -a t w 2 t ) , ≤ T ∑ t=1 (g t (w t -w ⋆ ) + a t ψ(w t ) -a t ψ(w ⋆ ))controlled by ( 4)+h T +1 |w ⋆ | + w 2 ⋆ T ∑ t=1 a t needs small at + T ∑ t=1 ((h t+1 -h t )|w t | -a t w 2 t )needs big at .From the above decomposition, we see that to make the overall regret small, we would like to choose a t such that ∑ T t=1 a t is small, but also a t is large enough that∑ T t=1 ((h t+1 -h t )|w t | -a t w 2 t) is also small. It turns out that this is accomplished by the following choice for a t :a t = γ ⋅ (h t+1 -h t )/h t+1 1 + ∑ t i=1 (h i+1 -h i )/h i+1 .Here, γ is an arbitrary user-specified constant. Notice that the value of h t+1 is available immediately after g t is revealed, so that it is possible to set this value of a t . Moreover, it is clear that a t ∈ [0, γ] for all t.Let us see how this value for a t satisfies our desired properties. First, recall the bound log(p + q)log(q) ≥ p p+q for any p, q > 0, which implies ∑ T t=1 pt ∑ t i=0 pi ≤ log (∑ T t=1 p t /p 0 ) for any sequence of positive numbers p 0 , . . . , p T . From this, we have:T ∑ t=1 a t = γ T ∑ t=1 (h t+1 -h t )/h t+1 1 + ∑ t i=1 (h i+1 -h i )/h i+1 , ≤ γ log (1 + T ∑ t=1 (h t+1 -h t )/h t+1 ) , ≤ γ log (1 + log (G/h 1 )) .T t=1 a t is in fact doubly logarithmic in the ratio between h 1 and hT +1 = max(h 1 , max t |g t |) = G.Next, let us check that a t is "large enough" to make∑ T t=1 (h t+1 -h t )|w t | -a t w 2t small. To this end, observe that:(h t+1 -h t )|w t | -a t w 2 t ≤ sup X (h t+1 -h t )X -a t X 2 , = (h t+1 -h t ) 2 4a t , = h t+1 (h t+1 -h t ) 4γ (1 + t ∑ i=1 (h i+1 -h i )/h i+1 ) , ≤ h T +1 (h t+1 -h t ) 4γ (1 + T ∑ i=1 (h i+1 -h i )/h i+1 ) , = G(h t+1 -h t ) 4γ (1 + log(G/h 1 )) ,where we used that G = h T +1 . Thus, we have:T ∑ t=1 ((h t+1 -h t )|w t | -a t w 2 t ) ≤ G 2 4γ (1 + log(G/h 1 )) .This shows that a t is large enough that it is able to counteract the effect of ∑ T t=1 (h t+1h t )|w t | (which makes the regret large if |w t | is large). It is tempting to conclude that the regularizer is somehow "implicitly constraining" w t 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 ∑ T t=1 (h t+1h t )|w t | = Õ(G 2 /γ) by applying some constraint |w t | ≤ 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/γ. So, our regularization seems to be doing something more subtle than simply applying a global constraint to the w t 's. Indeed, notice that in the case |g t | ≤ h 1 for all t, we actually have a t = 0 and so no constraint effect at all is enforced! The final step we need to check is bounding ∑ T t=1 gt (w tw ⋆ ) + a t ψ(w t )a t ψ(w ⋆ ). To this end, we provide in Section 3.3 an algorithm that achieves the following bound, which is slightly weaker than (4):T ∑ t=1 (g t (w t -w ⋆ ) + a t ψ(w t ) -a t ψ(w ⋆ )) ≤ O ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵh T + |w ⋆ | V log (e + |w ⋆ | √ V log 2 (T ) h 1 ϵ ) + |w ⋆ |h T log (e + |w ⋆ | √ V log 2 (T ) h 1 ϵ ) +ϵ 2 γ + w 2 ⋆ S log (e + |w ⋆ | 2 √ S log 2 (T ) γϵ 2 ) + ∥w ⋆ ∥ 2 γ log (e + |w ⋆ | 2 √ S log 2 (T ) γϵ 2 ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦, where S = γ 2 + γ ∑ T t=1 a t . This bound is weaker than (4) due to the presence of S rather thanγ 2 + ∑ T t=1 a 2t . Nevertheless, by our bound on ∑ T t=1 a t , we have:S ≤ γ 2 + γ 2 log (1 + log (G/h 1 ))so that combining all of the above calculations we establish Theorem 1.Thus, it remains to establish how we can achieve (4), or the slightly weaker (but sufficient) statement above. We accomplish this next in Section 3.3.Recall that our approach to obtaining (4) is to 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 ψ ∶ R → R. For t =EQUATIONThe key fact about this protocol is the observation that by setting w t = x t , the bound (6) immediately implies (4). To see this, recall that ψ(w) ≥ 0, a t ≥ 0, and y t ≥ ψ(x t ) = ψ(w t ) so that:T ∑ t=1 (⟨g t , w t -w ⋆ ⟩ + a t ψ(w t ) -a t ψ(w ⋆ )) ≤ T ∑ t=1 (⟨g t , x t -w ⋆ ⟩ + a t y t -a t ψ(w ⋆ )) .So, to achieve (4) under Protocol 2, it suffices to achieve the bound (6) under Protocol 3.There is one tempting approach that almost, but not quite, achieves this goal. One could employ the "constraint-set reduction" developed in [15] that converts an algorithm that operates on the "unconstrained" domain R d × R to one respecting the constraint y ≥ ψ(x). In particular, it is relatively straightforward to build an algorithm that achieves (6) without requiring y t ≥ ψ(x t ). This unconstrained setting can be handled by the classic "coordinate-wise updates" trick in which we run two instances of an algorithm achieving (4) in the special case that ψ(x) = 0, one of which will output x t and receive feedback g t , and the other will output y t and receive feedback a t . Then, by the individual regret bounds on both coordinates, we would have:T ∑ t=1 (g t (x t -w ⋆ ) + a t (y t -ψ(w ⋆ ))) = T ∑ t=1 g t (x t -w ⋆ ) + T ∑ t=1 a t (y t -ψ(w ⋆ )), ≤ Õ ⎛ ⎜ ⎝ ∥w ⋆ ∥ √ h 2 T + ∑ t=1 g2 t + ψ(w ⋆ ) γ 2 + T ∑ T =1 a 2 t ⎞ ⎟ ⎠ .Then, one might hope that applying the constraint-set reduction of [15] would allow us to apply the constraint W without damaging the regret bound. Unfortunately, this reduction will modify the feedback g t and a t in such a way that ∑ T t=1 a 2 t could become much larger, which makes this approach untenable in general.Fortunately, it turns out that our particular usage will enforce some favorable conditions on a t that make the above strategy viable. Specifically, the choices of gt , h t and a t described in Section 3.2 satisfy the condition that a t = 0 unless ∥g t ∥ = h t . By careful inspection of the constraint-set reduction, it is possible to show that the above strategy achieves a slightly weaker version of (6):EQUATIONAs detailed in Section 3.2, this weaker bound suffices for our eventual purposes. Nevertheless, for the reader interested in a fully general solution, in Appendix H, we provide a method for achieving (6) without restrictions. We do not employ it in our main development because it involves solving a convex subproblem at each iteration and so may be less efficient in some settings. This technique does however involve a small improvement to so-called "full-matrix" regret bounds [29] , and so may be of some independent interest.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). Justification: This paper provides a purely mathematical contribution. As such, it is subject to the standard ethical concerns present for all mathematical papers, but no further ones. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
lower bounds: 
 In this section, we show that the result of Theorem 1 is tight. In fact, we show a stronger result that generalizes our extra penalty term from G 2 /γ + γ∥w ⋆ ∥ 2 to γψ(∥w ⋆ ∥) + γψ ⋆ (G/γ) for any symmetric convex function ψ, where ψ ⋆ (x) = sup z xzψ(z) is the Fenchel conjugate of ψ. That is, we provide a Pareto frontier of different lower bounds and Theorem 1 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 a logarithmic factor). . We also provide matching upper bounds (up to a logarithmic factor) in Theorem 16, as well as more simplified Theorem 2. Suppose ψ ∶ R → R is convex, symmetric, differentiable, non-negative, achieves its minimum at ψ(0) = 0, and ψ(x) is strictly increasing for non-negative x. Further suppose that for any X, Y, Z > 0, there is some τ such that for all T ≥ τ ,exp(T ) -1 ≥ X √ T ∇ψ ⋆ (Y T ) Xψ ⋆ (Y T Z) ≥ T Zwhere ψ ⋆ (z) = sup zxψ(x) is the Fenchel conjugate of ψ. Let h 1 > 0, γ > 0 and ϵ > 0 be given.For any online learning algorithm A interacting with Protocol 1 with W = R, there is a T 0 such that for any T ≥ T 0 , there is a sequence of gradients g 1 , . . . , g T and a w ⋆ such that the outputs w 1 , . . . , w T of A satisfy:T ∑ t=1 g t (w t -w ⋆ ) ≥ ϵG + γ 8 ψ ⋆ (G/γ) + γ 4 ψ(w ⋆ ) + G|w ⋆ | 4 T log (1 + G|w ⋆ | √ T h 1 ϵ ),where G = max(h 1 , g 1 , . . . , g T ). In particular, with ψ(x) = x 1+q for any q > 0, we can ensure:T ∑ t=1 g t (w t -w ⋆ ) ≥ Ω ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵG + G 1+1/q γ 1/q + γ|w ⋆ | 1+q + G|w ⋆ | T log (1 + G|w ⋆ | √ T h 1 ϵ ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦.The conditions on ψ ⋆ in this bound are relatively mild. The first condition says that the gradient ∇ψ ⋆ should not grow exponentially fast. The second condition says that ψ ⋆ should grow faster than some linear function. So, any polynomial of degree greater than 1 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 g t = h 1 at every round. Then, if the iterates w t grow in some sense "quickly", we "punish" the algorithm with a 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 a common idiom for lower bounds in the fully unconstrained setting [17, 21] .However, a much better bound might be possible; ideally, it would hold that for any G and ∥w ⋆ ∥ and algorithm A, we can find a sequence of gradients g t that enforces our desired regret. Indeed, when either ∥w ⋆ ∥ or max t ∥g t ∥ is provided to the algorithm, the lower bounds available do take this form [3, 5] . We leave as an open question whether it is possible to do so in our setting. 
discussion: 
 We have provided a new online learning algorithm that achieves a near-optimal regret bound (2). Our algorithm is "fully unconstrained", or "fully parameter-free", in the sense that we achieve a near-optimal regret bound without requiring bounds on the gradients g t or the comparison point w ⋆ . Prior work in this setting [17, 20, 21, 22, 25] achieve bounds that are 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 ϵ, h 1 and γ. All of these have a pleasingly small impact on the regret bound. ϵ and h 1 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 Õ(∥w ⋆ ∥G √ T ) regret. The quantity γ represents an estimate of G/∥w ⋆ ∥. As discussed in Section 1, this value does not appear in any term that has a T -dependence in the regret bound and so also has a 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 [17] called the "range-ratio" problem. That is, the bound depends on the ratio G/h 1 , which could be very large if the losses are rescaled by some arbitrary large number without rescaling h 1 . This issue is at the heart of how we are able to sidestep the lower-bound of [17] , which appears to apply to all algorithms that do not suffer from the range-ratio problem.Our results focus on the case that we have no prior bounds on the value of ∥w ⋆ ∥ or ∥g t ∥, and our bounds eventually depend on max t ∥g t ∥. One might worry that this is too conservative in some settings. For example, it might be that g t is known to be a random variable with bounded mean ∥ E[gt]∥ ≤ G and variance Var(g t ) ≤ σ 2 for some known G and σ. In this case, max t ∥g t ∥ might become large even though intuitively our regret should still depend only on G + σ. This is the setting considered by several prior work on online learning with unconstrained domains [9, 16, 30] . Under various assumptions, these results all achieve an in-expectation regret bound ofE[Regret T (w ⋆ )] ≤ Õ(∥w ⋆ ∥(G + σ) √ T ).In fact, our results come close to this ideal even without knowledge of G. For example, [9, 16] study the case of sub-exponential g t that satisfysup ∥a∥≤1 E[exp(β⟨gt -E[gt], a⟩)] ≤ exp(β 2 σ 2 /2) for all |β| ≤ 1/b for some b > 0. In this case, for 1-dimensional g t , we have E[maxt g 2 t ] ≤ Õ(G 2 + σ 2 ), and so in expectation we achieve Õ(∥w⋆ ∥(G + σ) √ T + G 2 + σ 2 + ∥w ⋆ ∥ 2) (the extension from 1-d to arbitrary dimensions can then be achieved via the black-box reduction of [15] ). However, in the case that g t has some heavy-tailed distribution such as studied by [30] , 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.As discussed in the introduction, a common motivation for the study of online learning is its immediate application to stochastic convex optimization through various online-to-batch conversions. The classic conversion of [7] , as well as a few more recent results [31, 32, 33, 34] all show that if g t is the output of a stochastic gradient oracle for a convex function F , then for any w ⋆ ∈ argmin F :2 E [F ( ∑ T t=1 wt T ) -F (w ⋆ )] ≤ E[Regret T (w ⋆ )] TIf ∥g t ∥ ≤ G with probability 1 (for an unknown G), our Theorem 1 immediately impliesE [F ( ∑ T t=1 wt T ) -F (w ⋆ )] ≤ Õ ( ∥w⋆∥G √ T + G 2 /γ+γ∥w⋆∥ 2 T). The first term is the optimal rate for stochastic convex optimization that can be achieved via SGD with learning rate η = ∥w⋆∥ G √T if G and ∥w ⋆ ∥ are known ahead of time, and the second term is a 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-free" (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 (1) , which can then be applied to the stochastic setting via an online-to-batch conversion. More recent work on parameter-free optimization has considered the stochastic case [35, 36] , or deterministic case [37] directly without passing through a general regret bound. Many of these algorithms have shown significant empirical promise, even for non-convex deep learning tasks [36, 37, 38, 39, 40] . Almost all of these results require apriori knowledge of the value G3 To place our results in this context, let us focus on the case of a known G value. In this case, [35] show that by eschewing regret analysis and focusing specifically on the stochastic setting, it is possible to achieve a high-probability guarantee that improves upon the logarithmic factors achieved by our result, and so there seems to be something lost by focusing on regret bounds. However, in a surprising counterpoint, [42] shows that if one is interested in an in-expectation result, then there is actually no way to improve upon the logarithmic factors achieved via online-to-batch conversion when applied to parameter-free regret bounds. Thus, our in-expectation stochastic convergence rate is optimal even up to logarithmic factors, while we 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 ∥w ⋆ ∥. Here, we can again make use of the lower bounds developed by [42] . Consider the class of stochastic convex optimization objectives with Lipschitz constant G between 1 and L and ∥w ⋆ ∥ ∈ [1, R]. The "price of adaptivity" as defined by [42] 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/ √ T ). We achieve a price of adaptivity ofÕ(1 + max(L, R)/ √ T ). The best-known lower bound for this class is Ω(1 + min(L, R)/ √ T ) [42]. Thus, there is a gap here-although 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 [1, L] and [1, R]. Our algorithm does not use this information and it is also plausible that without such knowledge the lower bound itself would improve.In Theorem 1, we provide a bound that achieves the "ideal bound" of (1) with an extra penalty term of roughly G 2 /γ + γ∥w ⋆ ∥ 2 . It turns out that this penalty is but one point on a frontier of potential choices that are all immediately accessible by simply changing ψ(w) from ∥w∥ 2 to any other symmetric convex function, as outlined in the lower bounds of Section 4. Here we state formally that each of these bounds is achievable. In particular, by setting ψ(w) = ∥w∥ 1+q for any q > 0, we have: Theorem 3. There is an online learning algorithm that takes as input positive scalar values q, γ, h 1 , and ϵ and ensures that for any sequence g 1 , g 2 , ⋅ ⋅ ⋅ ⊂ R d , the outputs w 1 , w 1 , ⋅ ⋅ ⋅ ⊂ R d satisfy for all w ⋆ and T :EQUATION))1/q ] ,whereG = max(h 1 , max t∈[T ] ∥g t ∥) and V = G 2 + ∑ T t=1 ∥g t ∥ 2 .Finally, it is also the case that the logarithmic terms in our bounds can be adjusted to remove the T dependencies, at the cost of 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 2) in a manner similar to other recent works in unconstrained online optimization [19, 20, 25] . Formally, we can achieve: Theorem 4. There is an online learning algorithm that takes as input positive scalar values q, γ, h 1 , and ϵ and ensures that for any sequenceEQUATION))EQUATION))1/q ] where G = max(h 1 , max t ∥g t ∥) and V = G 2 + ∑ T t=1 ∥g t ∥ 2 .Both of these results are immediate corollaries of Theorem 16.We restate and prove Theorem 2. Theorem 2. Suppose ψ ∶ R → R is convex, symmetric, differentiable, non-negative, achieves its minimum at ψ(0) = 0, and ψ(x) is strictly increasing for non-negative x. Further suppose that for any X, Y, Z > 0, there is some τ such that for all T ≥ τ ,exp(T ) -1 ≥ X √ T ∇ψ ⋆ (Y T ) Xψ ⋆ (Y T Z) ≥ T Z where ψ ⋆ (z) = sup zx -ψ(x)is the Fenchel conjugate of ψ. Let h 1 > 0, γ > 0 and ϵ > 0 be given.For any online learning algorithm A interacting with Protocol 1 with W = R, there is a T 0 such that for any T ≥ T 0 , there is a sequence of gradients g 1 , . . . , g T and a w ⋆ such that the outputs w 1 , . . . , w T of A satisfy:T ∑ t=1 g t (w t -w ⋆ ) ≥ ϵG + γ 8 ψ ⋆ (G/γ) + γ 4 ψ(w ⋆ ) + G|w ⋆ | 4 T log (1 + G|w ⋆ | √ T h 1 ϵ ),where G = max(h 1 , g 1 , . . . , g T ). In particular, with ψ(x) = x 1+q for any q > 0, we can ensure:T ∑ t=1 g t (w t -w ⋆ ) ≥ Ω ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵG + G 1+1/q γ 1/q + γ|w ⋆ | 1+q + G|w ⋆ | T log (1 + G|w ⋆ | √ T h 1 ϵ ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . Proof. First, let us define ψ γ (x) = γψ(x). Let ∇ψ γ (x) and ∇ψ ⋆ γ (θ) indicate the derivatives of ψ γ and ψ ⋆ γ .The following properties are standard facts about the Fenchel conjugate (see e.g. [43] ):ψ ⋆ γ (θ) = γψ ⋆ (θ/γ), ψ ⋆ γ (0) = 0, ψ ⋆ γ (x) ≥ 0 for all x, ψ γ (x) = ∇ψ γ (x) ⋅ x -ψ ⋆ γ (∇ψ γ (x)), ψ ⋆ γ (θ) = ∇ψ ⋆ γ (θ) ⋅ θ -ψ γ (∇ψ ⋆ γ (θ)). Moreover, ∇ψ γ and ∇ψ ⋆ γ 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 T ≥ τ :EQUATIONEQUATIONTo see this, observe that by assumption, there is a τ 1 such that (8) holds for all T ≥ τ 1 , and also a τ 2 such that ( 9) holds for all T ≥ τ 2 , so we may take τ = max(τ 1 , τ 2 ) to achieve both simultaneously.From this, we see that there is some T 0 such that for all T ≥ T 0 :EQUATIONEQUATIONWe now construct the algorithm-dependent sequence g 1 , g 2 , . . . that satisfies the claim of the theorem.1. Define g 0 ← 0 and set t ← 1.Suppose that the condition in Item 3 has not been triggered for the first τ iterations. Then, we have:EQUATIONNow, suppose that the condition in Item 3 is triggered at some iteration τ + 1 ≥ 1. Then G = 2τ h 1 and with w ⋆ = 0, we have:T ∑ t=1 g t ⋅ (w t -w ⋆ ) = τ +1 ∑ t=1 g t ⋅ w t , = g τ +1 ⋅ w τ +1 + τ ∑ t=1 w t ⋅ g t , ≥ 4ϵτ h 1 + ∇ψ ⋆ γ (2τ h 1 ) ⋅ 2τ h 1 -2ϵτ h 1 - 1 2 ψ ⋆ γ (2τ h 1 ), (by ( 12))EQUATION= ϵG + 1 2 ψ ⋆ γ (G).Therefore, overall we have for w ⋆ = 0:T ∑ t=1 g t ⋅ (w t -w ⋆ ) ≥ ϵG + γ 2 ψ ⋆ (G/γ) + γψ(|w ⋆ |) + |w ⋆ |G T log (1 + |w ⋆ |G √ T h 1 ϵ).Alternatively, suppose the condition in Item 3 is never triggered. In this case, let us set w ⋆ = -2∇ψ ⋆ γ (2T h 1 ) . Then, G = h 1 and by (12) we have:T ∑ t=1 g t ⋅ (w t -w ⋆ ) ≥ ∇ψ ⋆ γ (2T h 1 ) ⋅ 2T h 1 - 1 2 ψ ⋆ γ (2T h 1 ) -2ϵT h 1 .Using that ∇ψ ⋆ γ (x) ⋅ x ≥ ψ ⋆ γ (x) by convexity of ψ ⋆ γ and ϕ ⋆ γ (0) = 0, the right-hand side of the previous display can be bounded below by ():∇ψ ⋆ γ (2T h 1 ) ⋅ 2T h 1 - 1 2 ψ ⋆ γ (2T h 1 ) -2ϵT h 1 ≥ 1 2 ψ ⋆ γ (2T h 1 ), ≥ 1 4 ψ ⋆ γ (G) + 1 4 ψ ⋆ γ (2T h 1 ) -2ϵT h 1 .Applying Eq. ( 11):EQUATIONFurther, since ψ ⋆⋆ γ = ψ γ , we have:∇ψ ⋆ γ (2T h 1 ) ⋅ 2T h 1 - 1 2 ψ ⋆ γ (2T h 1 ) = ∇ψ ⋆ γ (2T h 1 ) ⋅ T h 1 + 1 2 (∇ψ ⋆ γ (2T h 1 ) ⋅ 2T h 1 -ψ ⋆ γ (2T h 1 )) , = ∇ψ ⋆ γ (2T h 1 ) ⋅ T h 1 + 1 2 ψ γ (∇ψ ⋆ γ (2T h 1 )), = ∇ψ ⋆ γ (2T h 1 ) ⋅ T h 1 + 1 2 ψ γ (-w ⋆ ), = 1 2 |w ⋆ | ⋅ T h 1 + γ 2 ψ(w ⋆ ).Finally, let us bound 1 2 |w ⋆ | ⋅ g 1∶T using our choice of w ⋆ . By definition, we have:h 1 T = h 1 √ T ⋅ T , = h 1 √ T log(1 + (exp(T ) -1)),applying Eq. ( 10):EQUATIONTherefore, combining Eq. ( 14) with Eq. ( 15):∇ψ ⋆ γ (2T h 1 ) ⋅ 2T h 1 - 1 2 ψ ⋆ γ (2T h 1 ) -2ϵT h 1 ≥ 1 2 ( γ 4 ψ ⋆ (G/γ) + 6ϵT h 1 ) + 1 2 ⎛ ⎜ ⎝ γ 2 ψ(w ⋆ ) + G|w ⋆ | 2 T log (1 + G|w ⋆ | √ T h 1 ϵ ) -4ϵT h 1 ⎞ ⎟ ⎠ , ≥ 3ϵT h 1 + γ 8 ψ ⋆ (G/γ) + γ 4 ψ(w ⋆ ) + G|w ⋆ | 4 T log (1 + G|w ⋆ | √ T h 1 ϵ ), ≥ ϵG + γ 8 ψ ⋆ (G/γ) + γ 4 ψ(w ⋆ ) + G|w ⋆ | 4 T log (1 + G|w ⋆ | √ T h 1 ϵ).As a first step in our algorithm design, we observe that the application of some known reductions from [15] can significantly simplify our task. [15] show that to build an algorithm whose regret bound depends on g t only through the norms ∥g t ∥, it suffices to consider exclusively the case W = R. We provide the formal reduction in Algorithm 1, which ensures the following regret bound.Theorem 5 ([15] ). Algorithm 1 ensures that |g magnitude t | ≤ 2∥g t ∥, and also for all w ⋆ ∈ W:T ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ 4∥w ⋆ ∥ 2 T ∑ t=1 ∥g t ∥ 2 + T ∑ t=1 g magnitude t (w magnitude t -∥w ⋆ ∥). Algorithm 1 Reduction From General W to R Input: Convex domain W ⊆ R d , online learning algorithm A 1D with domain R. Initialize w direction 1 = 0 ∈ R d for t = 1 . . . T do Receive w magnitude t ∈ R from A 1D . Set ŵt = w magnitude t ⋅ w direction t ∈ R d . Set w t = Π W ŵ = argmin w∈W ∥w -ŵ∥. Output w t , receive feedback g t . Set g unconstrained t = g t + ∥g t ∥ wt-ŵt ∥wt-ŵt∥ . Set w direction t+1 = Π ∥w∥≤1 w direction t - g unconstrained t √ 2 ∑ t i=1 (g unconstrained i ) 2 . Set g magnitude t = ⟨g unconstrained t , w direction t ⟩ ∈ R.Send g magnitude t to A 1D as the tth feedback. end for From Theorem 5, it is clear that to achieve low regret on W, we need only bound ∑ T t=1 g magnitude t (w magnitude t -∥w ⋆ ∥), which is exactly the regret of a 1-dimensional learner. So, our final results will be established by considering the case of W = R, although we will define many intermediate problems for general W as they may have other applications for which the general setting is of interest.In this section, we describe our algorithm for Protocol 2 in the special case that W = R and a t = 0 whenever |g t | ≠ h t , where gt = (1 ∧ ht |gt| ) ⋅ g t . Our algorithm is in fact a reduction to the special case that a t = 0 for all t. This is an important special case that has actually also been previously considered in the literature (see e.g. the discussion in Section 3.1), so we provide it as a separate Protocol below: Protocol 4. Online Learning with Magnitude Hints. Input: Convex domain W (recall that we focus on W = R). For t = 1, . . . , T :1. Nature reveals magnitude hint h t ≥ h t-1 to the learner. 2. Learner outputs w t ∈ W.3. Nature reveals loss scalar g t with ∥g t ∥ ≤ h t to the learner. 4. Learner suffers loss ⟨g t , w t ⟩.The learner is evaluated with the regret ∑ T t=1 g t (w tw ⋆ ). The goal is to obtain:EQUATION)In Section E, 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.Our algorithm for Protocol 2 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 a preview of what the method is capable of.Corollary 6. For any ϵ with ψ(ϵ) > 0, there exists an algorithm for Protocol 2 such that for all t, the outputs x 1 , . . . , x T satisfy:T ∑ t=1 g t (x t -x ⋆ ) + a t (ψ(x t ) -ψ(x ⋆ )) ≤ O ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ϵh T + ψ(ϵ)γ + |x ⋆ | V g log ⎛ ⎝ e + |x ⋆ | √ V g log 2 (T ) h 1 ϵ ⎞ ⎠ + |x ⋆ |h T log ⎛ ⎝ e + |x ⋆ | √ V g log 2 (T ) h 1 ϵ ⎞ ⎠ +ψ(x ⋆ ) S a log (e + ψ(x ⋆ ) √ S a log 2 (T ) γψ(ϵ) ) + ψ(x ⋆ )γ log (e + ψ(x ⋆ ) √ S a log 2 (T ) γψ(ϵ) ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ Where V g = h 2 T + ∑ T t=1 g 2 t and S a = γ 2 + γ ∑ T t=1 a t .Proof. Apply Algorithm 2 with the BASE set to Algorithm 3 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 2 (T )) and p = 1/2. Set ϵ x = ϵ and ϵ ψ = ψ(ϵ). The result immediately follows.Corollary 7. For any ϵ with ψ(ϵ) > 0, there exists an algorithm for Protocol 2 such that for all t, the outputs x 1 , . . . , x T satisfy:T ∑ t=1 g t (x t -x ⋆ ) + a t (ψ(x t ) -ψ(x ⋆ )) ≤ O ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵ √ V g + ψ(ϵ) √ S a + |x ⋆ | V g log (e + |x ⋆ | ϵ ) + |x ⋆ |h T log (e + |x ⋆ | ϵ ) +ψ(x ⋆ ) S a log (e + ψ(x ⋆ ) ψ(ϵ) ) + ψ(x ⋆ )γ log (e + ψ(x ⋆ ) ψ(ϵ) ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , where V g = h 2 T + ∑ T t=1 g 2 t and S a = γ 2 + γ ∑ T t=1 a t .Proof. Apply Algorithm 2 with the BASE set to Algorithm 3 using p = 0. Then, in the notation of Theorem 10, the regret bound of Theorem 11 shows that A, B, C and D are all O(1) while p = 0. Set ϵ x = ϵ and ϵ ψ = ψ(ϵ). The result immediately follows.Lemma 8. Suppose ψ ∶ R → R is a convex function that achieves its minimum at 0. Let h > 0 and γ > 0 be given and define the norm ∥(x, y)∥ = h 2 x 2 + γ 2 y 2 and the distance function S(x, ŷ) = inf y≥ψ(x) ∥(x, y) -(x, ŷ)∥. For any (x, ŷ), let (δ x , δ y ) be an arbitrary subgradient of S at (x, ŷ).Then, δ y ≤ 0.Proof. Throughout this proof, we will assume x > 0. The proof is completely symmetric in the sign of x.First, we dispense with the case in which there is no projection: suppose ŷ ≥ ψ(x). Then we must have ŷ = y and x = x and S(x, ŷ) = 0. Further, for any ỹ > ŷ, S(x, ỹ) = 0. However, if δ y > 0, then by definition of subgradient, we must have 0 = S(x, ỹ) ≥ S(x, ŷ) + δ y (ỹŷ) > 0, which cannot be. Therefore δ y ≤ 0. So, it remains to consider the case ŷ < ψ(x).Define (x, y) = argmin y≥ψ(x) ∥(x, y) -(x, ŷ)∥. Further, by [15, Theorem 4], we have:(δ x , δ y ) = ⎛ ⎝ h 2 (x -x) √ h 2 (x -x) 2 + γ 2 (ŷ -y) 2 , γ 2 (ŷ -y) √ h 2 (x -x) 2 + γ 2 (ŷ -y) 2 ⎞ ⎠ .Therefore, it suffices to show that ŷ ≤ y.To start, consider the case ψ(0) > ŷ. Then, we have ŷ < ψ(0) ≤ ψ(x) ≤ y as desired. So, in the following we consider the remaining case ψ(0) ≤ ŷ < ψ(x). Observe that since ψ is convex, it must be continuous. Therefore, by intermediate value theorem there must be some x ≥ 0 with ψ(x) = ŷ. Further, we have ψ(x) = ŷ < ψ(x), so that x < x. Now, by convexity, if x ≥ x, we must ψ(x) ≥ ψ(x) because ψ must be non-decreasing for positive x since it achieves its minimum at 0. Therefore, y ≥ ψ(x) ≥ ψ(x) = ŷ and so we are done. So, let us suppose x < x.+ a 2 γ 2 . Define S t (x, ŷ) = inf ŷ≥ψ(x) ∥(x, y) -(x, ŷ)∥ t . Compute x t , y t = argmin y≥ψ(x) ∥x t , y t ) -(x, ŷ)∥ t . Receive feedback g t ∈ [-h t , h t ], a t ∈ [0, γ], such that a t = 0 unless |g t | = h t . Compute (δ x t , δ y t ) = ∥g t ∥ ⋆,Further, suppose that ŷ > y. Then, observe that:h 2 (x -x) 2 + γ 2 (max(y, ψ(x)) -ŷ) 2 < h 2 (x -x) 2 + γ 2 (y -ŷ) 2 ,so that the point (x, max(y, ψ(x))) would contradict the optimality of (x, y). Thus, it also cannot be that ŷ > y and so we are done. Lemma 9. Let h > 0 and γ > 0 be given and define the norm ∥(x, y)∥ = h 2 x 2 + γ 2 y 2 with corresponding dual norm ∥ ⋅ ∥ ⋆ . Let (g, a) be any point satisfying |g| ≤ h, a ∈ [0, γ], and a = 0 unless |g| = h. Let (δ x , δ y ) be any points satisfying ∥(δ x , δ y )∥ ⋆ = ∥(g, a)∥ ⋆ . Then,|δ x | ≤ |g| √ 2, |δ y | ≤ γ √ 2. Proof. The dual norm ∥ ⋅ ∥ ⋆ is ∥(g, a)∥ ⋆ = g 2 h 2 + a 2 γ 2. So, we have:(δ x ) 2 h 2 + (δ y ) 2 γ 2 = g 2 h 2 + a 2 γ 2 ≤ 2.This immediately implies |δ y | ≤ γ √ 2. We also have(δ x ) 2 ≤ g 2 + h 2 a 2 γ 2 .Now, since a = 0 unless g 2 = h 2 , this yields either|δ x | ≤ |g| if |g| < h or |δ x | ≤ √ g 2 + h 2 a 2 /γ 2 = h √ 2 if |g| = h, so either way |δ x | ≤ |g| √ 2.Theorem 10. Let A, B, CD, ϵ > 0, and p ≥ 1, be given. Suppose that for any sequence z 1 , . . . , z T and magnitude hints m 1 ≤ ⋅ ⋅ ⋅ ≤ m T satisfying |z t | ≤ m t , BASE outputs w 1 , . . . , w T and guarantees regret: T ∑ t=1 z t (w t -u) ≤ ϵ BASE Cm 2p T ZT ∑ t=1 g t (x t -x ⋆ ) + a t (ψ(x t ) -ψ(x ⋆ )) ≤ C x ϵ x h 2p T V 1/2-p g + A x |x ⋆ | V g log (e + D x |x ⋆ |V p g ϵ x h 2p 1 ) + B x |x ⋆ | log (e + D x |x ⋆ |V p g ϵ x h 2p 1 ) + C ψ ϵ ψ γ 2p S 1/2-p a + A ψ ψ(x ⋆ ) S a log (e + D ψ ψ(x ⋆ )S p a ϵ ψ γ 2p ) + B ψ ψ(x ⋆ ) log (e + D ψ ψ(x ⋆ )S p a ϵ ψ γ 2p ) ,for any x ⋆ ∈ R, where the constants in the above expression are given by:A x = 3A, B x = 3B, C x = 3C, D x = D, A ψ = 1 2 + 144A 2 , B ψ = 144A 2 + 24B, C ψ = 3C ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (144A 2 + 24B) log (e + 12CD(1152pA 2 + 48pb) p ) + 1 2 + (2p + 1)(2 -4p) 1-2p 1+2p 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , D ψ = 4D [1152A 2 p + 48pB] p .Proof. First, observe that since (x t , y t ) is the result of a projection to the domain y ≥ ψ(x), it must hold that y t ≥ ψ(x t ) for all t. Thus, since a t > 0 and ψ is non-negative, we have for any x ⋆ :g t (x t -x ⋆ ) + a t (ψ(x) -ψ(x ⋆ )) ≤ g t (x t -x ⋆ ) + a t (y t -x ⋆ ).Therefore, it suffices to bound ∑ T t=1 g t (x tx ⋆ ) + a t (y tx ⋆ ), which we will now accomplish. By [15, Theorem 3], we have for anyx ⋆ ∈ R T ∑ t=1 g t (x t -x ⋆ ) + a t (y t -ψ(x ⋆ )) ≤ T ∑ t=1 (g t + δ x t )(x t -x ⋆ ) + T ∑ t=1 (a t + δ y t )(ŷ t -ψ(x ⋆ )),and also ∥(δ x t , δ y t )∥ t,⋆ = ∥(g t , a t )∥ t,⋆ by [15, Proposition 1] . Therefore, by Lemma 9, we have|g t + δ x t | ≤ 3|g t | ≤ 3h t . Defining V g = h 2 T + ∑ T t=1 (g t + δ x t ) 2, and by the guarantee of BASE, we have for any x ⋆ :T ∑ t=1 (g t + δ x t )(x t -x ⋆ ) ≤ C(3h T ) 2p [9h 2 T + T ∑ t=1 (g t + δ x t ) 2 ] 1/2-p ϵ x + A|x ⋆ | [9h 2 T + T ∑ t=1 (g t + δ x t ) 2 ] log ⎛ ⎝ e + D|x ⋆ | [9h 2 T + ∑ T t=1 (g t + δ x t ) 2 ] p (3h 1 ) 2p ϵ x ⎞ ⎠ + 3Bh T |x ⋆ | log ⎛ ⎝ e + D|x ⋆ | [9h 2 T + ∑ T t=1 (g t + δ x t ) 2 ] p (3h 1 ) p ϵ x ⎞ ⎠ ≤ 3Ch 2p T V 1/2-p g ϵ x + 3A|x ⋆ | V g log (e + D|x ⋆ |V p g h 2p 1 ϵ x ) + 3Bh T |x ⋆ | log (e + D|x ⋆ |V p g h 2p 1 ϵ x )Next, observe that by Lemma 9, |a t + δ y t | ≤ 3γ. We also have for any x ⋆ ∈ R:T ∑ t=1 (a t + δ y t )(ŷ t -ψ(x ⋆ )) = 1 2 T ∑ t=1 (a t + δ y t )(y t -2ψ(x ⋆ )) + 1 2 T ∑ t=1 (a t + δ y t )y t = 1 2 T ∑ t=1 (a t + δ y t )(y t -2ψ(x ⋆ )) + 1 2 T ∑ t=1 (a t + δ y t )(y t -2y ⋆ ) + y ⋆ T ∑ t=1 (a t + δ y t ) Now, define V a = γ 2 + ∑ T t=1 (a t + δ y t ) 2. By the guarantee of BASE applied twice, we have that for any x ⋆ ∈ R (ψ(x ⋆ ) ≥ 0 below represents the comparator for the regret of BASE):T ∑ t=1 (a t + δ y t )(ŷ t -ψ(x ⋆ )) ≤ C(3γ) 2p [9γ 2 + T ∑ t=1 (a t + δ y t ) 2 ] 1/2-p ϵ ψ + Aψ(x ⋆ ) (9γ 2 + T ∑ t=1 (a t + δ y t ) 2 ) log ⎛ ⎝ e + 2Dψ(x ⋆ ) [9γ 2 + ∑ T t=1 (a t + δ y t ) 2 ] p 3 2p γ 2p ϵ ψ ⎞ ⎠ + 3γBψ(x ⋆ ) log ⎛ ⎝ e + 2Dψ(x ⋆ ) [9γ 2 + ∑ T t=1 (a t + δ y t ) 2 ] p 3 2p γ 2p ϵ ψ ⎞ ⎠ + Ay ⋆ (9γ 2 + T ∑ t=1 (a t + δ y t ) 2 ) log ⎛ ⎝ e + 2Dy ⋆ [9γ 2 + ∑ T t=1 (a t + δ y t ) 2 ] p 3 2p γ 2p ϵ ψ ⎞ ⎠ + 3γB|y ⋆ | log ⎛ ⎝ e + 2Dy ⋆ [9γ 2 + ∑ T t=1 (a t + δ y t ) 2 ] p 3 2p γ 2p ϵ ψ ⎞ ⎠ + y ⋆ T ∑ t=1 (a t + δ y t ) ≤ 3Cγ 2p V 1/2-p a ϵ ψ + 3Aψ(x ⋆ ) V a log (e + 2Dψ(x ⋆ )V p a γ 2p ϵ ψ ) + 3Bψ(x ⋆ ) log (e + 2Dψ(x ⋆ )V p a γ 2p ϵ ψ ) + 3Ay ⋆ V a log (e + 2Dy ⋆ V p a ϵ ψ ) + 3γBy ⋆ log (e + 2Dy ⋆ V p a γ 2p ϵ ψ ) + y ⋆ T ∑ t=1 (a t + δ y t ) ≤ 3Cγ 2p V 1/2-p a ϵ ψ + 3A(ψ(x ⋆ ) + y ⋆ ) V a log (e + 2D(ψ(x ⋆ ) + y ⋆ )V p a γ 2p ϵ ψ ) + 3B(ψ(x ⋆ ) + y ⋆ ) log (e + 2Dψ(x ⋆ )V p a γ 2p ϵ ψ ) + y ⋆ T ∑ t=1 (a t + δ y t )Now, we observe:T ∑ t=1 (a t + δ y t ) = 1 2γ T ∑ t=1 [(a t + δ y t + γ) 2 -γ 2 ] - 1 2γ T ∑ t=1 (a t + δ y t ) 2 , = 1 2γ T ∑ t=1 [(a t + δ y t + γ) 2 -γ 2 ] + γ 2 - 1 2γ V a .Next, we bound (a t + δ y t + γ) y ⋆ T ∑ t=1 (a t + δ y t ) ≤ - y ⋆ 2γ V a + 3y ⋆ 2γ S a .So, overall we have:T ∑ t=1 (a t + δ y t )(ŷ t -ψ(x ⋆ )) ≤ 3Cγ 2p V 1/2-p a ϵ ψ + 3A(ψ(x ⋆ ) + y ⋆ ) V a log (e + 2D(ψ(x ⋆ ) + y ⋆ )V p a γ 2p ϵ ψ ) + 3B(ψ(x ⋆ ) + y ⋆ ) log (e + 2Dψ(x ⋆ )V p a γ 2p ϵ ψ ) - y ⋆ 2γ V a + 3y ⋆ 2γ S a .Since the above holds for any y ⋆ ≥ 0, we may write:T ∑ t=1 (a t + δ y t )(ŷ t -ψ(x ⋆ )) ≤ inf y⋆ sup Va ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 3Cγ 2p V 1/2-p a ϵ ψ + 3A(ψ(x ⋆ ) + y ⋆ ) V a log (e + 2D(ψ(x ⋆ ) + y ⋆ )V p a γ 2p ϵ ψ ) +3B(ψ(x ⋆ ) + y ⋆ ) log (e + 2Dψ(x ⋆ )V p a γ 2p ϵ ψ ) - y ⋆ 2γ V a + 3y ⋆ 2γ S a ]Now, applying Lemma 20 to bound the minimax expression above, we have:T ∑ t=1 (a t + δ y t )(ŷ t -ψ(x ⋆ )) ≤ ( 1 2 + 144A 2 ) ψ(x ⋆ ) S a log (e + 4Dψ(x ⋆ )S p a ϵ ψ γ 2p [1152A 2 p + 48pB] p ) + γψ(x ⋆ )(144A 2 + 24B) log (e + 4Dψ(x ⋆ )S p a ϵ ψ γ 2p [1152A 2 p + 48pB] p ) + 3Cγ 2p S 1/2-p ϵ ψ ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (144A 2 + 24B) log (e + 12CD(1152pA 2 + 48pb) p ) + 1 2 + (2p + 1)(2 -4p) 1-2p 1+2p 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ So, overall we achieve: T ∑ t=1 g t (x t -x ⋆ ) + a t (y t -ψ(x ⋆ )) ≤ 3Ch 2p T V 1/2-p g ϵ x + 3A|x ⋆ | V g log (e + D|x ⋆ |V p g h 2p 1 ϵ x ) + 3Bh T |x ⋆ | log (e + D|x ⋆ |V p g h 2p 1 ϵ x ) + ( 1 2 + 144A 2 ) ψ(x ⋆ ) S a log (e + 4Dψ(x ⋆ )S p a ϵ ψ γ 2p [1152A 2 p + 48pB] p ) + γψ(x ⋆ )(144A 2 + 24B) log (e + 4Dψ(x ⋆ )S p a ϵ ψ γ 2p [1152A 2 p + 48pB] p ) + 3Cγ 2p S 1/2-p ϵ ψ ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (144A 2 + 24B) log (e + 12CD(1152pA 2 + 48pb) p ) + 1 2 + (2p + 1)(2 -4p) 1-2p 1+2p 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .So, with:A x = 3A, B x = 3B, C x = 3C, D x = D, A ψ = 1 2 + 144A 2 , B ψ = 144A 2 + 24B, C ψ = 3C ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (144A 2 + 24B) log (e + 12CD(1152pA 2 + 48pb) p ) + 1 2 + (2p + 1)(2 -4p) 1-2p 1+2p 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , D ψ = 4D [1152A 2 p + 48pB] p ,we haveT ∑ t=1 g t (x t -x ⋆ ) + a t (y t -ψ(x ⋆ )) ≤ C x ϵ x h 2p T V 1/2-p g + A x |x ⋆ | V g log (e + D x |x ⋆ |V p g ϵ x h 2p 1 ) + B x |x ⋆ | log (e + D x |x ⋆ |V p g ϵ x h 2p 1 ) , + C ψ ϵ ψ γ 2p S 1/2-p a + A ψ ψ(x ⋆ ) S a log (e + D ψ ψ(x ⋆ )S p a ϵ ψ γ 2p ) + B ψ ψ(x ⋆ ) log (e + D ψ ψ(x ⋆ )S p a ϵ ψ γ 2p) .from which the conclusion follows.In this section we quote an algorithm that obtains a performance guarantee suitable for use as BASE in Theorem 10. We emphasize that the development in this section is only a very mild improvement (affecting only logarithmic factors) on previous work: our key contribution is how to use this algorithm to obtain better adaptivity to unknown Lipschitz constants.In fact, algorithms satisfying the requirements of Theorem 10 up to logarithmic factors have been described by several previous authors: see [17, 20, 22, 25] . Here, we provide a slightly improved analysis of the algorithm of [20] which achieves tighter (and in fact optimal) logarithmic terms. ' Theorem 11. Suppose g 1 , . . . , g T is any sequence of real numbers and 0< h 1 ≤ ⋅ ⋅ ⋅ ≤ h T is another sequence of real numbers satisfying |g t | ≤ h t . Then, if p = 1/2, Algorithm 3 guarantees for all u T ∑ t=1 g t (w t -u) ≤ 8h T ϵ + 6|u| (h 2 T + T ∑ t=1 g 2 t ) log ⎛ ⎜ ⎝ |u| √ 3 + ∑ T t=1 g 2 t /h 2 t log 2 (3 + ∑ T t=1 g 2 t /h 2 t ) ϵ + 1 ⎞ ⎟ ⎠ + 6|u|h T log ⎛ ⎜ ⎝ |u| √ 3 + ∑ T t=1 g 2 t /h 2 t log 2 (3 + ∑ T t=1 g 2 t /h 2 t ) ϵ + 1 ⎞ ⎟ ⎠ , Algorithm 3 1-Dimensional Learner for Protocol 4 (BASE) Input: ϵ > 0, p ∈ [0, 1/2] Initialize h 0 = 0, k = 3 if p = 1/2 then Define constant c = 3 else Define constant c = 1 end if for t = 1 . . . T do Receive h t ≥ h t-1 ∈ R Define V t = h 2 t + ∑ t-1 i=1 g 2 i if p = 1/2 then Set α t = ϵ √ c+∑ t-1 i=1 g 2 i /h 2 i log 2 (c+∑ t-1 i=1 g 2 i /h 2 i ) else Define α t = ϵ (c+∑ t-1 i=1 g 2 i /h 2 i ) p end if Define Θ t = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ (∑ t-1 i=1 gi) 2 4k 2 Vt if |∑ t-1 i=1 g i | ≤ 2kVt ht |∑ t-1 i=1 gi| kht -Vt h 2 t otherwise Output w t = -sign (∑ t-1 i=1 g i ) α t (exp(Θ t ) -1) Receive g t with |g t | ≤ h t . end for while if p < 1/2 Algorithm 3 guarantees instead: T ∑ t=1 g t (w t -u) ≤ 4h 2p T ϵ (∑ T t=1 g 2 t ) 1/2-p 1 -2p + 6|u| (h 2 T + T ∑ t=1 g 2 t ) log ⎛ ⎝ |u| (1 + ∑ T t=1 g 2 t /h 2 t ) p ϵ + 1 ⎞ ⎠ + 6|u|h T log ⎛ ⎝ |u| (1 + ∑ T t=1 g 2 t /h 2 t ) p ϵ + 1 ⎞ ⎠ .Notice that the term log 2 (3 + ∑ T t=1 g 2 t /h 2 t ) ≤ log 2 (3 + T ), and so we upper bound this term with a constant for the purposes of use in Theorem 10. Further, the term∑ T t=1 g 2 t /h 2 t ≤ ∑ T t=1 g 2 t /h 2 1, and so the logarithmic terms always fit into the framework of Theorem 10.Proof. Observe that Algorithm 3 is an instance of FTRL with regularizer:ψ t (w) = k ∫ |w| 0 min η≤1/ht [ log(x/α t + 1) η + ηV t ] dx.That is,w t = argmin w ψ t+1 (w) + t-1 ∑ i=1 g i w.In the "centered mirror descent" framework of [20] (their Algorithm 1), this corresponds to setting φ(w) = 0. Further, [20] provides an analysis of this update for the particular family of regularizer functions ψ t we consider above in their Theorem 6. Although formally speaking, their Theorem 6 specifies a particular equation for α t , inspection of the proof shows that most of their argument applies so long as α t is non-increasing. We reproduce this verification in Lemma 12, which yields:T ∑ t=1 g t (w t -u) ≤ ψ T (u) + T ∑ t=1 2α t √ V t .Next, define h T +1 = 0 and g T +1 = 0 in order to define α T +1 and ψ T +1 ≥ ψ T . So, we can replace ψ T (u) with ψ T +1 (u) in the above expression. Next, to bound ψ T +1 (u), we observe that:ψ T +1 (u) = k ∫ |u| 0 min η≤1/h T +1 [ log(x/α T +1 + 1) η + ηV T +1 ] dx, ≤ k|u| min η≤1/h T +1 [ log(u/α T +1 + 1) η + ηV T +1 ] .Now, notice that if the minimizing η of min η≤1/h T +1 [ log(u/α T +1 +1) η + ηV T +1 ] occurs on the boundary η = 1/h T +1 , then it must be that log(u/α T +1 +1) η > ηV T +1 , since log(u/α T +1 +1) η is decreasing in η and ηV T +1 is increasing in η. Thus in this case min η≤1/h T +1 [ log(u/α T +1 +1) η + ηV T +1 ] ≤ 2h T log(u/α T +1 + 1). Alternatively, when the minimizing η is not on the boundary we havemin η≤1/h T +1 [ log(u/α T +1 +1) η + ηV T +1 ] = 2 √ V T +1 log(u/α T +1 + 1). So, in general we have:ψ T +1 (u) ≤ 2k|u| √ V T +1 log(|u|/α T +1 + 1) + 2k|u|h T log(|u|/α T +1 + 1).So far this analysis is identical to that of [20] , and has been agnostic to the value of α t , so long as α t is non-increasing. Now, however, we come to the place at which we diverge in analysis: our choice of α t is slightly larger and so results in better logarithmic factors in ψ. The trade-off is that we need to provide a fresh analysis of ∑ T t=12αtg 2 t √Vt to show that this term is still controlled. We accomplish this in Lemma 21 (for p = 1/2) and Lemma 22 (for p < 1/2). For p = 1/2, we then obtain:T ∑ t=1 g t (w t -u) ≤ 8h T ϵ + 2k|u| (h 2 T + T ∑ t=1 g 2 t ) log ⎛ ⎜ ⎝ |u| √ 3 + ∑ T t=1 g 2 t /h 2 t log 2 (3 + ∑ T t=1 g 2 t /h 2 t ) ϵ + 1 ⎞ ⎟ ⎠ + 2k|u|h T log ⎛ ⎜ ⎝ |u| √ 3 + ∑ T t=1 g 2 t /h 2 t log 2 (3 + ∑ T t=1 g 2 t /h 2 t ) ϵ + 1 ⎞ ⎟ ⎠, while for p < 1/2 we obtain:T ∑ t=1 g t (w t -u) ≤ 4h 2p T ϵ (∑ T t=1 g 2 t ) 1/2-p 1 -2p + 2k|u| (h 2 T + T ∑ t=1 g 2 t ) log ⎛ ⎝ |u| (1 + ∑ T t=1 g 2 t /h 2 t ) p ϵ + 1 ⎞ ⎠ + 2k|u|h T log ⎛ ⎝ |u| (1 + ∑ T t=1 g 2 t /h 2 t ) p ϵ + 1 ⎞ ⎠ .The conclusion now follows by substituting in k = 3.The following technical Lemma is lifted almost entirely from [20] . Unfortunately, this result was not explicitly declared as a separate Lemma in the prior literature and is instead merely a subset of the proof of a larger Theorem (specifically, Theorem 6 of [20] ). 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 g 1 , . . . , g T be an arbitrary sequence of scalars. Suppose 0 < h 1 ≤ ⋅ ⋅ ⋅ ≤ h T is non-decreasing sequence with |g t | ≤ h t for all t, and let α 1 ≥ ⋅ ⋅ ⋅ ≥ α T , be a non-increasing sequence.Let k ≥ 3. Set V t = h 2 t + ∑ t-1 i=1 g 2 i and define ψ t (w) = k ∫ |w| 0 min η≤1/ht [ log(x/α t + 1) η + ηV t ] dx w t = argmin w ψ t (w) + t-1 ∑ i=1 g i w.Then for all u ∈ R:T ∑ t=1 g t (w t -u) ≤ ψ T (u) + T ∑ t=1 2α t g 2 t √ V t . Proof. Define ψ T +1 = ψ T and let D f (a|b) indicate the Bregman divergence D f (a|b) = f (a)-f (b)- f ′ (b)(a -b). Define ∆ t (w) = D ψt+1 (w|w 1 ). Then, by [20] Lemma 1, we have:T ∑ t=1 g t (w t -u) ≤ ψ T (u) + T ∑ t=1 g t (w t -w t+1 ) -D ψt (w t+1 |w t ) -∆ t (w t+1 )So, it suffices to establish that:EQUATIONFollowing the notation and argument of [20] , define F t (w) = log(w/α t + 1) andΨ t (x) = k ∫ x 0 min η≤1/ht [ F t (x) η + ηV t ] dxThen we have ψ(w) = Ψ t (∥w∥) and elementary calculation yields:Ψ ′ t (x) = { 2k √ V t F t (x) if h t √ F t (x) ≤ √ V t kh t F t (x) + kVt ht otherwise Ψ ′′ t (x) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ k √ Vt (x+αt) √ Ft(x) if h t √ F t (x) ≤ √ V t kht x+αt otherwise Ψ ′′′ t (x) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ -k √ Vt(1+2Ft(x)) 2(x+αt) 2 Ft(x) 3/2 if h t √ F t (x) ≤ √ V t -kht (x+αt) 2 otherwise Therefore, Ψ t (x) ≥ 0, Ψ ′ t (x) ≥ 0, Ψ ′′ t (x) ≥ 0 and Ψ ′′′ t (x) ≤ 0.Further, if we define x 0 = α t (e -1), then for any > x 0 we have√ F t (x) ≥ 1 √ Ft(x)and:-Ψ ′′′ t (x) Ψ ′′ t (x) 2 ≤ ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 1 2k √ Vt ( 1 √ Ft(x) + 2 √ F t (x)) if h t √ F t (x) ≤ √ V t 1 kht otherwise ≤ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 3 √ Ft(x) 2k √ Vt if h t √ F t (x) ≤ √ V t 1 kht otherwise using k ≥ 3: ≤ 1 2 min ⎛ ⎝ √ F t (x) V t , 1 h t ⎞ ⎠ Now, if we define Z t (x) = ∫ x 0 min ( √ Ft(x)Vt , 1 ht ) dx, then we have- Ψ ′′′ t (x) Ψ ′′ t (x) 2 ≤ 1 2 Z ′ t (x)Clearly Z t is convex, 1/h t Lipschitz, and achieves its minimum value of 0 at 0. Therefore, by [20] Lemma 2, we have:g t (w t -w t+1 ) -D ψt (w t+1 |w t ) -Z t (|w t+1 |)g 2 t ≤ 2g 2 t Ψ ′′ (x 0 ) , ≤ 2g 2 t (x 0 + α t ) k √ V t , = 2g 2 t α t e k √ V t , ≤ 2g 2 t α t √ V t .So, now if we could show that ∆ t (w) ≥ Z t (|w|)g 2 t , this would establish (17) . In turn, since ∆ t (w) = Ψ t+1 (|w|) -Ψ t (|w|), it suffices to establish:Ψ ′ t+1 (x) -Ψ ′ t (x) ≥ Z ′ (x)g 2 t = g 2 t min ⎛ ⎝ √ F t (x) V t , 1 h t ⎞ ⎠ .To this end, we compute:Ψ ′ t+1 (x) -Ψ ′ t (x) = k min η≤1/ht+1 [ F t+1 (x) η + ηV t+1 ] -k min η≤1/ht [ F t (x) η + ηV t ] , ≥ k min η≤1/ht [ F t+1 (x) η + ηV t+1 ] -k min η≤1/ht [ F t (x) η + ηV t ] .Next, let us defineδ m = h 2 t+1 -h 2 t so that V t+1 = V t + δ m + g 2 t . Then we have Ft+1(x) η + ηV t+1 ≥ min η ′ [ Ft+1(x) η ′ + η ′ V t ] + η(δ m + g 2 t ). Armed with this calculation, we proceed:Ψ ′ t+1 (x) -Ψ ′ t (x) ≥ k(δ m + g 2 t ) min ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ √ F t+1 (x) V t+1 , 1 h t ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + k min η≤1/ht [ F t+1 (x) η + ηV t ] -k min η≤1/ht [ F t (x) η + ηV t ] ,now, since α t ≥ α t+1 , we have F t+1 ≥ F t so that:≥ k(δ m + g 2 t ) min ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ √ F t+1 (x) V t+1 , 1 h t ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . Next, observe that d dδ m δ m + g 2 t √ V t + δ m + g 2 t = δ 2 m + 2V t + g 2 t 2(V t + δ m + g 2 t ) 3/2 ≥ 0. Therefore δ m + g 2 t √ V t+1 = δ m + g 2 t √ V t + δ m + g 2 t , ≥ g 2 t √ V t + g 2 t , ≥ g 2 t √ V t √ V t V t + g 2 t , ≥ g 2 t √ V t h 2 t h 2 t + g 2 t , ≥ g 2 t √ 2V t .This implies thatEQUATION√ F t (x) V t .So, altogether we have:Ψ ′ t+1 (x) -Ψ ′ t (x) ≥ kg 2 t √ 2 min ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ √ F t+1 (x) V t , 1 h t ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , ≥ g 2 t min ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ √ F t+1 (x) V t , 1 h t ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , = Z ′ t (x)g 2 t , as desired.In this section, we provide a formal description of how to achieve a fully unconstrained bound via application of some peculiar regularization terms, as sketched in Section 3.2.The goal is to ensure regret given by ( 4), restated below:EQUATION)In Section H, we will see how to obtain the bound (4) via a general technique for obtaining constrained "full-matrix" regret bounds (which is of independent interest). However, this approach comes with a mild computational overhead. To counteract this, in Section E, we provide an alternative approach that has the same computational complexity as gradient descent, but achieves the slightly weaker bound:EQUATION)Fortunately, (18) will also be sufficient for our purposes.Armed with an algorithm that achieves (18) , we are ready to describe our approach for fully unconstrained learning. Corollary 13. There exists an online learning algorithm that requires O(d) space and takes O(d) time per update, takes as input scalar values γ, h 1 , and ϵ and ensures that for any sequence g 1 , g 2 , ⋅ ⋅ ⋅ ⊂ R d , the outputs w 1 , w 1 , ⋅ ⋅ ⋅ ⊂ R d satisfy for all w ⋆ and T :T ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ O ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵ √ V + ∥w ⋆ ∥ V log (e + ∥w ⋆ ∥ ϵ ) + ∥w ⋆ ∥G log (e + ∥w ⋆ ∥ ϵ ) +ϵ 2 γ √ log (e + log (e + G h 1 )) + G 2 γ log (e + G h 1 ) + γw 2 ⋆ log (e + ∥w ⋆ ∥ 2 ϵ 2 log (e + G h 1 )) ⎤ ⎥ ⎥ ⎥ ⎦.whereG = h 1 + max t ∥g t ∥ and V = G 2 + ∑ T t=1 ∥g t ∥ 2 .Proof. Apply Algorithm 5 with q = 1, and REG set to Algorithm 2 using Algorithm 3 with p = 0 as BASE. The result in 1 dimension then follows from Theorem 16 and Corollary 6. Then by the reduction from d-dimensional online learning to 1-dimensional online learning ( [15] Theorem 2), the result in high dimensions also follows.Theorem 1. There exists an online learning algorithm that requires O(d) space and takes O(d) time per update, takes as input scalar values γ, h 1 , and ϵ and ensures that for any sequence g 1 , g 2 , ⋅ ⋅ ⋅ ⊂ R d , the outputs w 1 , w 1 , ⋅ ⋅ ⋅ ⊂ R d satisfy for all w ⋆ and T :EQUATION))] ,whereG = max(h 1 , max t∈[T ] ∥g t ∥) and V = G 2 + ∑ T t=1 ∥g t ∥ 2 .Proof. Apply Algorithm 5 with q = 1, and REG set to Algorithm 2 using Algorithm 3 with p = 1/2 as BASE. The result in 1 dimension then follows from Theorem 16 and Corollary 6. Then by the reduction from d-dimensional online learning to 1-dimensional online learning ( [15] Theorem 2), the result in high dimensions also follows.Input: Regularized learning algorithm REG with domain R. Parameter γ > 0, h 1 > 0.Initialize REG with parameters ϵ and γ. for t = 1 . . . T do Send h t to REG as the tth magnitude hint. Get w t from REG. Play w t , see feedback g t .Seth t+1 = max(h t , |g t |). Set gt = clip [-ht,ht] g t Set a t = γ (ht+1-ht)/ht+11+∑ t i=1 (hi+1-hi)/hi+1 . Send gt , a t , to REG as tth loss and regularization coefficient. end for Theorem 14. There exists an online learning algorithm that requires O(d) space and takes O(d) time per update, takes as input scalar values γ, h 1 , and ϵ and a symmetric convex function ψ and ensures that for any sequence g 1 , g 2 , ⋅ ⋅ ⋅ ⊂ R d , the outputs w 1 , w 1 , ⋅ ⋅ ⋅ ⊂ R d satisfy for all w ⋆ and T :T ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ O ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ϵG + ∥w ⋆ || V log (e + ∥w ⋆ ∥ √ V log 2 (T ) h 1 ϵ ) + ∥w ⋆ ∥G log (e + ∥w ⋆ ∥ √ V log 2 (T ) h 1 ϵ ) +ψ(ϵ)γ + γψ(∥w ⋆ ∥) log (e + ψ(∥w ⋆ ∥) ψ(ϵ) log (e + G h 1 )) + γ log (1 + log ( G h 1 )) ψ ⋆ ( G γ [1 + log ( G h 1 )])] ,whereψ ⋆ (θ) = sup w θw -ψ(w) is the Fenchel conjugate of ψ, G = max(h 1 , max t ∥g t ∥) and V = G 2 + ∑ T t=1 ∥g t ∥ 2 .Proof. Apply Algorithm 5 with REG set to Algorithm 2 using Algorithm 3 with p = 1/2 as BASE.The result in 1 dimension then follows from Theorem 16 and Corollary 6. Then by the reduction from d-dimensional online learning to 1-dimensional online learning ( [15] Theorem 2), the result in high dimensions also follows.Theorem 15. Suppose ψ is a symmetric convex function. Suppose that so long as h t ≥ |g t |, REG ensures for some A, B, C, D, p, ϵ:T ∑ t=1 gt (w t -w ⋆ ) + a t (ψ(w t ) -ψ(w ⋆ )) ≤ Cϵh 2p T V 1/2-p g + Cψ(ϵ)γ 2p S 1/2-p a + A|w ⋆ | V g log (e + D|x ⋆ |V p g h 2p 1 ϵ ) + Bh T |w ⋆ | log (e + D|w ⋆ |V p g h 2p 1 ϵ ) + Aψ(w ⋆ ) S a log [e + Dψ(w ⋆ ) γ 2p ψ(ϵ) S p a ] + γBψ(w ⋆ ) log [e + Dψ(w ⋆ ) γ 2p ψ(ϵ) S p a ] ,whereV g = h 2 T + ∑ T t=1g2 t and S a = γ 2 + γ ∑ T t=1 a t . Then Algorithm 4 ensures:S a ≤ γ 2 + γ 2 log (1 + min [log ( h T h 1 ) , T ]) , V g ≤ h 2 T + T ∑ t=1 g 2 t ,and:T ∑ t=1 g t (w t -w ⋆ ) ≤ Cϵh 2p T V 1/2-p g + Cψ(ϵ)γ 2p S 1/2-p a + A|w ⋆ | V g log (e + D|w ⋆ |V p g h 2p 1 ϵ ) + Bh T |w ⋆ | log (e + D|w ⋆ |V p g h 2p 1 ϵ ) + Aψ(w ⋆ ) S a log [e + Dψ(w ⋆ ) γ 2p ψ(ϵ) S p a ] + γBψ(w ⋆ ) log [e + Dψ(w ⋆ ) γ 2p ψ(ϵ) S p a ] + h T |u| + ψ(w ⋆ )S a + γ log (1 + min [log ( h T h 1 ) , T ]) ψ ⋆ ( h T γ [1 + log ( h T h 1 )])In the special case that ψ(x)= |x| 1+q1+q , we can replace the final termγ log (1 + min [log ( h T h1 ) , T ]) ψ ⋆ (h T [1 + log ( h T h1 )]) in the above expression by:h 1+1/q T [1 + log ( h T h1 )] 1/q (1 + 1/q)γ 1/q .Proof. We have:T ∑ t=1 g t (w t -u) = T ∑ t=1 gt (w t -u) + a t (ψ(w t ) -ψ(u)) + a t ψ(u) + (g t -gt )(w t -u) -a t ψ(w t ), ≤ ψ(u) T ∑ t=1 a t + |u| T ∑ t=1 |g t -gt | + T ∑ t=1 gt (w t -u) + a t (ψ(w t ) -ψ(u)), + T ∑ t=1 |g t -gt ||w t | -a t ψ(w t ) Observing that |g t -gt | = h t+1 -h t : = ψ(u) T ∑ t=1 a t + |u| T ∑ t=1 [h t+1 -h t ] + T ∑ t=1 (h t+1 -h t )|w t | -a t ψ(w t ) + T ∑ t=1 gt (w t -u) + a t (ψ(w t ) -ψ(u)).Next, we will bound the terms∑ T t=1 a t ψ(u) and |u| ∑ T t=1 [|g t |-h t ] + .. Moreover, h t = h t-1 +[|g t |-h t ] + , so that |u| ∑ T t=1 |g t -gt | ≤ |u|h T .Further, notice that for any s 0 , s 1 , . . . , s T , ∑ T t=1 log ( st∑ t i=0 si ) ≤ log(s T /s 0 ), so that: T ∑ t=1 a t ≤ γ log (1 + T ∑ t=1 h t+1 -h t h t+1 )Notice that [|g t |h t ] + /h t+1 ≤ 1, so we also have:T ∑ t=1 h t+1 -h t h t+1 ≤ min [log ( h T h 1 ) , T ]so that overall:S a = γ 2 + γ T ∑ t=1 a t ≤ γ 2 + γ 2 log (1 + min [log ( h T h 1 ) , T ])Next, we bound the terms (h t+1h t )|w t |a t ψ(w t ). Let ψ ⋆ (w) be the Fenchel conjugate of ψ.Recall that ψ is symmetric so that ψ(w t ) = ψ(|w t |). This also implies that ψ ⋆ is symmetric and is minimized at zero. Thus:(h t+1 -h t )|w t | -a t ψ(w t ) = (h t+1 -h t )|w t | -a t ψ(|w t |), = a t ψ ⋆ ( h t+1 -h t a t ) , = a t ψ ⋆ ( h t+1 γ [1 + t ∑ i=1 h i+1 -h i h i+1 ]) .So, in general we have:T ∑ t=1 (h t+1 -h t )|w t | -a t ψ(w t ) ≤ T ∑ t=1 a t ψ ⋆ ( h t+1 γ [1 + t ∑ i=1 h i+1 -h i h i+1 ]) , ≤ T ∑ t=1 a t ψ ⋆ ( h T γ [1 + log ( h T h 1 )]) , ≤ γ log (1 + min [log ( h T h 1 ) , T ]) ψ ⋆ ( h T γ [1 + log ( h T h 1 )]) .In the special case that ψ(w) = |w| 1+q 1+q , we have ψ ⋆ (h) = h 1+1/q 1+1/q so that we can improve the logarithmic factors and simplify the calculation:a t ψ ⋆ (h t+1 [1 + t ∑ i=1 h i+1 -h i h i+1 ]) = a t h 1+1/q t+1 [1 + ∑ t i=1 hi+1-hi hi+1 ] 1+1/q (1 + 1/q)γ 1+1/q , = (h t+1 -h t )h 1/q t+1 [1 + ∑ t i=1 hi+1-hi hi+1 ] 1/q (1 + 1/q)γ 1/q , = (h t+1 -h t )h 1/q t+1 [1 + ∑ t i=1 hi+1-hi hi+1 ] 1/q (1 + 1/q)γ 1/q , ≤ (h t+1 -h t )h 1/q T [1 + log ( h T h1 )] 1/q (1 + 1/q)γ 1/q T ∑ t=1 (h t+1 -h t )|w t | -a t ψ(w t ) ≤ h 1+1/q T [1 + log ( h T h1 )] 1/q (1 + 1/q)γ 1/q . Finally, it is clear that |g t | ≤ h t so the summation ∑ T t=1 gt (w t -u) + a t (ψ(w t ) -ψ(u)) is controlled by the regret bound of REG: T ∑ t=1 gt (w t -u) + a t (ψ(w t ) -ψ(u)) ≤ Cϵh 2p T V 1/2-p g + Cψ(ϵ)γ 2p S 1/2-p a + A|x ⋆ | V g log (e + D|x ⋆ |V p g h 2p 1 ϵ ) + Bh T |x ⋆ | log (e + D|x ⋆ |V p g h 2p 1 ϵ ) + Aψ(x ⋆ ) S a log [e + Dψ(x ⋆ ) γ 2p ψ(ϵ) S p a ] + γBψ(x ⋆ ) log [e + Dψ(x ⋆ ) γ 2p ψ(ϵ) S p a ] .Algorithm 5 Fully Unconstrained LearningInput: Symmetric convex function ψ ∶ R → R with 0 = ψ(0). Scalars ϵ > 0, h 1 , γ > 0, p ∈ [0, 1/2].Let REG be an instance of Algorithm 6 with input ψ, γ, p, ϵ x = ϵ and ϵ ψ = ψ(ϵ). Set vector ⃗ w direction 1 = 0 Send h 1 to REG as the first magnitude hint. for t = 1 . . . T do // Apply reduction to 1-dimensional learning from [15] = max(h t , |g 1d t |). Set gt = clip [-ht,ht] g 1d t Set a t = γ (ht+1-ht)/ht+1 1+∑ t i=1 (hi+1-hi)/hi+1 .Send gt , a t to REG as tth loss and regularization coefficient. Send h t+1 to REG as the t + 1st magnitude hint. end for Finally, we also have:V g = h 2 T + T ∑ t=1 g2 t , ≤ h 2 T + T ∑ t=1 g 2 t .Throughout this paper, we have considered the special case that W = R. This suffices due to the reductions of [15] as discussed in Section C. However, here we provide a more complete theorem and algorithm for the case W = R d . The pseudocode is provided in Algorithm 5, and the regret bound is stated in Theorem 16. Note that the regret bound follows essentially immediately from Theorem 15. Theorem 16. There exists universal constants A, B, C, such that Algorithm 5 guarantees for all T :T ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ Cϵh 2p T V 1/2-p g + Cψ(ϵ)γ 2p S 1/2-p a + A∥w ⋆ ∥ V g log (e + ∥w ⋆ ∥V p g h 2p 1 ϵ ) + Bh T ∥w ⋆ ∥ log (e + ∥w ⋆ ∥V p g h 2p 1 ϵ ) + Aψ(∥w ⋆ ∥) S a log [e + ψ(∥w ⋆ ∥) γ 2p ψ(ϵ) S p a ] + γBψ(∥w ⋆ ∥) log [e + ψ(∥w ⋆ ∥) γ 2p ψ(ϵ) S p a ] + h T |u| + ψ(∥w ⋆ ∥)S a + γ log (1 + min [log ( h T h 1 ) , T ]) ψ ⋆ ( h T γ [1 + log ( h T h 1 )])whereS a ≤ γ 2 + γ 2 log (1 + min [log ( h T h 1 ) , T ]) V g ≤ h 2 T + T ∑ t=1 g 2 tIn the special case that ψ(x)= |x| 1+q1+q , we can replace the final termγ log (1 + min [log ( h T h1 ) , T ]) ψ ⋆ (h T [1 + log ( h T h1 )]) in the above expression by:h 1+1/q T [1 + log ( h T h1 )] 1/q (1 + 1/q)γ 1/q .Proof. Algorithm 5 is applying the dimension-free-to-one-dimension reduction provided by Theorem 2 of [15] . So overall the reduction tells us that the regret is bounded byT ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ T ∑ t=1 ⟨g 1d t , w magnitude t -∥w ⋆ ∥⟩ + ∥w ⋆ ∥ T ∑ t=1 ⟨g t , w direction t -w ⋆ /∥w ⋆ ∥⟩In this case, the "direction" learner's iterates w direction t are generated by standard adaptive gradient descent [12] , which guarantees the regret bound:∑ T t=1 ⟨g t , w direction t -w ⋆ /∥w ⋆ ∥⟩ ≤ 2 √ 2 ∑ T t=1 ∥g t ∥ 2 .For the first sum ∑ T t=1 ⟨g 1d t , w magnitude t -∥w ⋆ ∥⟩, notice that w magnitude is simply an application of Algorithm 4 using an instance of Algorithm 6 The first sum is bounded by application of Theorem 15, noticing that |g 1d t | ≤ ∥g t ∥. So, putting the two bounds together we have the stated result.Lemma 17. Let A, B, C, D, E be positive numbers and let e be the base of the natural logarithm. Then:sup M A √ M log(e + DM C ) + B log(e + DM C ) -EM ≤ ( A 2 E + B) log ⎛ ⎝ e + D ( 2CA 2 E 2 + 2CB E ) C ⎞ ⎠ Proof.First, by Young inequality xy ≤ inf λ x 2 /2λ + λy 2 /2, we have for all M :EQUATIONNow, from first order optimality conditions we are looking for a solution to:EQUATION( A 2 E + B) DCM C-1 = E 2 e + E 2 DM CNotice that for any M ≥ 2CA 2 E 2 + 2CB E we have:( A 2 E + B) CD ≤ E 2 DM ( A 2 E + B) DCM C-1 ≤ E 2 DM C ( A 2 E + B) DCM C-1 < E 2 e + E 2 DM CTherefore, the optimal value for M can be at most2CA 2 E 2 + 2CB E . Now, notice that ( A 2 E + B) log(e + DM C) is strictly increasing in M . Thus, our quantity of interest is upper-bounded by substituting inM = 2CA 2 E 2 + 2CB E into this increasing term: sup M ( A 2 E + B) log(e + DM C ) -EM ≤ ( A 2 E + B) log ⎛ ⎝ e + D ( 2CA 2 E 2 + 2CB E ) C ⎞ ⎠ Lemma 18.Let A, B < 1, C be positive numbers. Then:sup M AM B -CM = ( BA C B ) 1/(1-B) ( 1 -B B )Proof. We differentiate with respect to M :ABM B-1 = C M = ( C AB ) 1/(B-1)So, plugging in this optimal M value we have:sup M AM B -CM = ( C B BA )1/(B-1)( 1 B -1)Lemma 19. Let A, B, C, D, E, F , G < 1 be positive numbers and let e be the base of the natural logarithm. Then:EQUATION≤ ( 4A 2 E + B) log ⎛ ⎝ e + D ( 32CA 2 E 2 + 8CB E ) C ⎞ ⎠ + ( 4 G GF E G ) 1/(1-G) ( 1 -G G )When G = 0, the last term( 4 G GF E G ) 1/(1-G)( 1 G -1) should be replaced with the limiting value F .Proof. Notice thatEQUATIONThe result now follows from Lemmas 17 and 18. Alternatively, if A, B, C, D, F , S, γ , and p ≤ 1/2 be positive numbers with S ≥ γ 2 , and let e be the base of the natural logarithm. Then:G = 0, clearly sup M F M G -EM 4 = F . Lemma 20. Let ψ,inf E sup V A(ψ + E) V log (e + D(ψ + E) γ 2p V p ) + Bγ(ψ + E) log (e + D(ψ + E) γ 2p V p ) + F γ 2p V 1/2-p - EV 2γ + ES 2γ ≤ (1/2 + 16A 2 )ψ √ S log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + γψ (16A 2 + 2B) log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + ⎛ ⎝ (16A 2 + 2B) log (e + 2DF (128pA 2 + 16pB) p ) + 1 2 + (2p + 1)(2 -4p) 1-2p 1+2p 2 ⎞ ⎠ γ 2p F S 1/2-pProof. By Lemma 19, we have:sup V A(ψ + E) V log (e + D(ψ + E) γ 2p M p ) + Bγ(ψ + E) log (e + D(ψ + E) γ 2p M p ) + F γ 2p V 1/2-p - EV 2γ ≤ ( 4A 2 (ψ + E) 2 γ E + Bγ(ψ + E)) log (e + D(ψ + E) γ 2p ( 32pγ 2 A 2 (ψ + E) 2 E 2 + 8pγ 2 B(ψ + E) E ) p ) + ( 4 1/2-p (1/2 -p)F γ 2p (E/γ) 1/2-p ) 2 1+2p 2p + 1 1 -2p = ( 4A 2 (ψ + E) 2 γ E + Bγ(ψ + E)) log (e + D(ψ + E) ( 32pA 2 (ψ + E) 2 E 2 + 8pB(ψ + E) E ) p ) ( * ) + γ (2p + 1)(2 -4p) 1-2p 1+2p 2 ( F E 1/2-p ) 2 1+2p ( * * )Now, set:E = max ⎡ ⎢ ⎢ ⎢ ⎣ min ⎡ ⎢ ⎢ ⎢ ⎣ ψ, γψ √ S √ log (e + 2DψS p γ 2p (128pA 2 + 16pB) p ) ⎤ ⎥ ⎥ ⎥ ⎦ , γ 1+2p F S 1+2p 2 ⎤ ⎥ ⎥ ⎥ ⎦We will bound the above expression by first considering ( * ) and then ( * * ). Now, if E = ψ, we have:( * ) = γψ (16A 2 + 2B) log (e + 2Dψ (128pA 2 + 16pB) p )recalling that S ≥ γ 2 :≤ γψ (16A 2 + 2B) log (e + 2DψS p γ 2p (128pA 2 + 16pB) p ) Alternatively, if E = γψ √ S √ log (e + 2DψS p γ 2p (128pA 2 + 16pB) p), then we have E + ψ ≤ 2ψ and so:EQUATIONBefore we bound this expression, let us consider just the value inside the logarithm:EQUATIONSo, putting this back in the previous expression:log (e + 2Dψ ( 128pA 2 ψ 2 E 2 + 16pBψ E ) p ) ≤ log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p )from which we conclude:( * ) ≤ 16A 2 ψ √ S log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + 2Bγψ log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p )Finally, let us consider the case E = γ 1+2p F S 1+2p 2. To handle this situation, we will work with two more subcases: either E ≤ ψ or not. If E ≤ ψ, then E + ψ ≤ 2ψ. Therefore:( * ) ≤ ( 16A 2 ψ 2 γ E + 2Bγψ) log (e + 2Dψ ( 128pA 2 ψ 2 E 2 + 16pBψ E ) p ) However, if E ≤ ψ, then it must be that E ≥ γψ √ S √ log (e + 2DψS p γ 2p (128pA 2 + 16pB) p ).Thus by the exact same analysis following equation ( 19), we again have( * ) ≤ 16A 2 ψ √ S log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + 2Bγψ log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p )So, for our final subcase we considerE = γ 1+2p F S 1+2p 2and also E ≥ ψ. Then E + ψ ≤ 2E, which yields:( * ) ≤ γE(16A 2 + 2B) log (e + 2DE (128pA 2 + 16pB) p )Since S ≥ γ 2 , E ≤ F and so:≤ γF (16A 2 + 2B) log (e + 2DF (128pA 2 + 16pB) p )So, in all cases we have:( * ) ≤ 16A 2 ψ √ S log (e + 2DψS p γ 2p (128pA ψ + 16pB) p ) + γψ (16A 2 + 2B) log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + γF (16A 2 + 2B) log (e + 2DF (128pA 2 + 16pB) p )Where the last term γF (16A 2 + 2B) log (e + 2DF (128pA2 + 16pB) p ) is only present if p ≠ 1/2.Notice that we must haveE ≥ γ 1+2p F S 1+2p 2. Therefore:γ F 2 1+2p E 1-2p 1+2p ≤ γ 2p F S 1/2-p ( * * ) ≤ (2p + 1)(2 -4p) 1-2p 1+2p 2 γ 2p F S 1/2-pSo, overall it holds that: . In this case:( * ) + ( * * ) ≤ 16A 2 ψ √ S log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + γψ (16A 2 + 2B) log (e + 2DψS p γ 2p (128pA 2 ψ + 16pB) p ) + γF (16A 2 + 2B) log (e + 2DF (128pA 2 + 16pB) p ) + (2p + 1)(2 -4p) 1-2p 1+2p 2 γ 2p F SEQUATIONSo, combining all these facts, we have when p < 1/2: inf E sup V A(ψ + E) V log (e + D(ψ + E) γ 2p M p ) + Bγ(ψ + E) log (e + D(ψ + E) γ 2p M p ) + F γ 2p V 1/+ (2p + 1)(2 -4p) 1-2p 1+2p 2 γ 2p F S 1/2-p + γ 2p F S 1/2-p 2 + ψ 2 √ S log (e + 2DψS p γ 2p (128pA 2 + 16pB) p )grouping terms, and using γ ≤ γ 2p S < h 1 ≤ h 2 ≤ ⋅ ⋅ ⋅ ≤ h T are such that |g t | ≤ h t for all t. Define V t = ch 2 t + g 2 1∶t-1 . Define α t = ϵ √ c+∑ t-1 i=1 g 2 i /h 2 i log 2 (c+∑ t-1 i=1 g 2 i /h 2 i )for some c ≥ 3. Then:T ∑ t=1 α t g 2 t √ V t ≤= 4ϵh T Proof. Let 1 = τ 1 , .. . , τ k ≤ T be the set of indices such that h τi+1 > 2h τi and h τi+1-1 ≤ 2h τi , with τ k+1 defined equal to T + 1 for convenience. Note that this implies h τ k-i < h τ k /2 i . Further, h τ k ≤ h T , so overall we have for all i h τ k-i ≤ h T /2 i . We will show thatEQUATIONOnce established, this implies:T ∑ t=1 α t g 2 t √ V t = k ∑ i=1 τi+1-1 ∑ t=τi α t g 2 t √ V t ≤ 2ϵ k ∑ i=1 h τi = 2ϵ k-1 ∑ i=0 h τ k-i ≤ 2ϵh T k-1 ∑ i=0 2 -i = 4ϵh TSo, to establish (20) , we observe that for any t ∈ [τ i , τ i+1 -1] we haveV t ≥ (c -1)h 2 t + t ∑ j=τi g 2 j ≥ c -1 2 h 2 τi+1-1 + t ∑ j=τi g 2 jand also:α t ≤ ϵ √ c -1 + ∑ t j=τi g 2 j /h 2 j log 2 (c -1 + ∑ t j=τi g 2 j /h 2 j ) ≤ ϵ √ c-1 2 + ∑ t j=τi g 2 j /h 2 τi+1-1 log 2 ( c-1 2 + ∑ t j=τi g 2 j /h 2 τi+1-1 ) ≤ ϵh τi+1-1 √ c-1 2 h 2 τi+1-1 + ∑ t j=τi g 2 j log 2 ( c-1 2 + ∑ t j=τi g 2 j /h τi+1-1 ) Combining these yields: α t g 2 t √ V t ≤ ϵh τi+1-1 g 2 t ( c-1 2 h 2 τi+1-1 + ∑ t j=τi g 2 j ) log 2 ( c-1 2 + ∑ t j=τi g 2 j /h τi+1-1 ) = ϵh τi+1-1 g 2 t /h 2 τi+1-1 ( c-1 2 + ∑ t j=τi g 2 j /h 2 τi+1-1 ) log 2 ( c-1 2 + ∑ t j=τi g 2 j /h τi+1-1 ) using c ≥ 3 ≤ ϵh τi+1-1 g 2 t /h 2 τi+1-1 (1 + ∑ t j=τi g 2 j /h 2 τi+1-1 ) log 2 (1 + ∑ t j=τi g 2 j /h τi+1-1 ) ≤ 2ϵh τi g 2 t /h 2 τi+1-1 (1 + ∑ t j=τi g 2 j /h 2 τi+1-1 ) log 2 (1 + ∑ t j=τi g 2 j /h τi+1-1 ) So, now if we define x s = g 2 s+τi-1 /h 2 τi+1-1, then we have:τi+1-1 ∑ t=τi ≤ 2ϵh τi τi+1-τi ∑ s=1 x s (1 + ∑ s s ′ =1 x s ′ ) log 2 (1 + ∑ s s ′ =1 x s ′ )And, by [1] Lemma 4.13:EQUATIONSo, in the end we have ∑ τi+1-1 t=τi ≤ 2ϵh τi as desired.Lemma 22. Suppose g 1 , . . . , g t and 0< h 1 ≤ h 2 ≤ ⋅ ⋅ ⋅ ≤ h T are such that |g t | ≤ h t for all t. Define V t = ch 2 t + g 2 1∶t-1 . Define α t = ϵ (c+∑ t-1 i=1 g 2 i /h 2 i )p for some c ≥ 1 and p ∈ [0, 1/2). Then:T ∑ t=1 α t g 2 t √ V t ≤ 2ϵh 2p T (∑ T t=1 g 2 t ) 1/2-p 1 -2pProof. Similar to the proof of Lemma 21, we have:V t ≥ (c -1)h 2 t + t ∑ j=1 g 2 j ≥ t ∑ j=τi g 2 jand also:α t ≤ ϵ (∑ t j=1 g 2 j /h 2 j ) p ≤ ϵh 2p t (∑ t j=1 g 2 j )p Combining these yields:α t g 2 t √ V t ≤ ϵh 2p T g 2 t (∑ t j=1 g 2 j ) 1/2+pFurther, by [1] Lemma 4.13 we have:T ∑ t=1 g 2 t (∑ t j=1 g 2 j ) 1/2+p ≤ ∫ ∑ T t=1 g 2 t 0 dx x 1/2+p ≤ (∑ T t=1 g 2 t )1/2-p 1/2p from which the conclusion immediately follows.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 4) that ensures the regret bound:EQUATION)This type of bound is sometimes called a "full-matrix" bound as the term inside the square root can be expressed as w T ⋆ Σw ⋆ where Σ is the matrix of gradient outer products Σ = ∑ T t=1 g t g ⊺ t . Bounds of this form have appeared before in the literature. For the case that W is an entire vector space, [15, 17] both provide full-matrix bounds. For the case in which W is not an entire vector space, [29] provides to our 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, let 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 ⋆ , ψ(w ⋆ )) and g t ↦ (g t , a t ). Then the bound ( 6) is immediate from (21) . So, without further ado, let us provide our bound and analysis.Assume that W ⊂ R d is a closed convex set that contains the origin within its interior. Further, let Φ bar be a self-concordant barrier for W with parameter µ > 0. In this section, we present an algorithm that achieves (21) . The algorithm is Follow-The-Regularized-Leader (FTRL) with a specific regularizer we define next.Regularizers. For Σ ∈ R d×d and Z, σ, ε > 0, define the regularizer:EQUATIONwhere X(θ) ∶= W (θ) ∀G ∈ R d , Φ ⋆ (G; Σ, Z, σ, ε) = inf λ≥0 ε ⋅ exp( 1 2 G ⊺ (Σ + λI) -1 G + λZ 2 ) √ det(σ -2 Σ).Proof. See [17] .FTRL. We will consider the FTRL algorithm with regularizer Φ(⋅; Σ, Z, σ, ε) + Φ bar (⋅), for some choices of Σ, Z, σ, and ε. To specify these choices, letEQUATIONfor γ > 1. With this, and given the history of gradients g 1 , . . . , g t-1 up to round t -1 and parameters γ, σ, ε > 0 and hint h t > 0, the algorithm outputs:EQUATIONwhere Ψ(w; V, h, σ, ε) ∶= Φ(w; σ 2 I + γV, ρ(γ) 2 /h 2 , σ, ε) + Φ bar (-w),EQUATIONRemark 1 (Connection to Matrix-FreeGrad). We note that without the barrier term Φ bar in (25) , the iterates in (24) can be computed in closed-form; in this case, the iterates exactly matches those of the Matrix-FreeGrad algorithm by [17] for unconstrained Online Convex Optimization (the connection to FTRL was not made explicit in [17] ). The advantage of adding a barrier Φ bar is that it ensure that the iterates ( ŵt ) are always in the feasible set without requiring any sophisticated constrained-to-unconstrained reductions that may lead to sub-optimal logarithmic terms in the regret [44] (see Remark 2 in the sequel).Lemma 24 (Monotocity of potential). Let σ, ε > 0 and γ > 1 be given. For all g t ∈ R d and h t > 0 such that ∥g t ∥ ≤ h t , we haveEQUATION)where G ↦ Ψ ⋆ (G; V, h, σ, ε) denotes the Fenchel dual of w ↦ Ψ(w; V, h, σ, ε).The proof of the lemma is in Appendix H.3. By summing (27) over t and using Fenchel duality, we obtain the following regret bound for the FTRL iterates in (24) . Theorem 25 (Regret with valid hints). Let σ, ε > 0 and γ > 1 be given. The FTRL iterates ( ŵt ) in (24) in response to any sequence (g t ) such that ∥g t ∥ ≤ h t , for all t ≥ 1, satisfy: for all T ∈ N and w ∈ int W:EQUATIONwhere ln + (⋅) ∶= 0 ∨ ln(⋅), Σ T = σ 2 I + γV T , andEQUATIONRemark 2 (Comparison to previous "full-matrix" bounds in the constrained setting). We note that by having the O(log T ) factor in (28) inside the square root, the bound in (28) improves on previous "full-matrix" bounds in the constraint setting [44] , which have the log factor outside.As stated in Remark 2, if we remove Φ bar from the regularizer, then iterates in (24) match those of Matrix-FreeGrad, 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 ŵt in (24) no longer admits a closed-form expression, and computing ŵt , for t ∈ [T ], now requires solving a convex optimization problem. This is not ideal from a computational perspective; most first-order OCO algorithms require only O(d) operation per round. It might be possible (at least in the case where W is bounded) to efficiently approximate ( ŵt ) without solving an optimization problem at each step and without sacrificing the regret by much using Newton steps such as in the recent works of [45, 46, 47] . We leave this investigation for future work.Proof. By Lemma 23, we have that for all V and h, Ψ ⋆ (⋅; V, h, σ, ε) satisfiesEQUATIONWe will use this to prove (27) .Let (λ ⋆ , u ⋆ ) ∈ R ≥0 × R d be the minimizer in the problem Ψ ⋆ (G t-1 ; V t-1 , h t , σ, ε). With this notation, we have ŵt = argminw∈R d ⟨G t-1 , w⟩ + Ψ(-w; V t-1 , h t ), = argmax w∈R d ⟨G t-1 , -w⟩ -Ψ(-w; V t-1 , h t ), = -argmax v∈R d {⟨G t-1 , v⟩ -Ψ(v; V t-1 , h t )} , = -∇Ψ ⋆ (G t-1 ; V t-1 , h t , σ, ε),and so by Lemma 26,= -(σ 2 I + γV t-1 + λ ⋆ I) -1 (G t-1 -u ⋆ ) ⋅ Φ ⋆ (G t-1 -u ⋆ ; σ 2 I + γV t-1 , ρ(γ) 2 /h 2 t , σ, ε). (31) Moving forward, we define G t-1,⋆ ∶= G t-1 -u ⋆ and G t,⋆ ∶= G t -u ⋆ .To prove the lemmsa, it suffices to prove the stronger statement obtained by picking the sub-optimal choice (λ, u) = (λ ⋆ , u ⋆ ) for the problem Ψ ⋆ (G t , V t , h t , σ, ε); that is, ⟨ ŵt , g t ⟩ ≤ ε ⋅ exp( 1 2 G ⊺ t-1,⋆ (σ 2 I + γV t-1 + λ ⋆ I) -1 G t-1,⋆ + λ⋆ρ(γ) 2 2h 2 t ) √ det(I + σ -2 γV t-1 ) + Φ ⋆ bar (-u ⋆ ) - ε ⋅ exp( 1 2 G ⊺ t,⋆ (σ 2 I + γV t + λ ⋆ I) -1 G t,⋆ + λ⋆ρ(γ) 2 2h 2 t ) √ det(I + σ -2 γV t ) -Φ ⋆ bar (-u ⋆ ), = Φ ⋆ (G t-1,⋆ ; σ 2 I + γV t-1 , ρ(γ) 2 /h 2 t , σ, ε) -Φ ⋆ (G t,⋆ ; σ 2 I + γV t , ρ(γ) 2 /h 2 t , σ, ε),and so dividing by Φ ⋆ (G t-1,⋆ ; σ 2 I + γV t-1 , ρ(γ) 2 /h 2 t , σ, ε) and using (31) , this becomes-g t ⋅ (σ 2 I + γV t-1 + λ ⋆ I) -1 G t-1,⋆ ≤ 1 - exp( 1 2 G ⊺ t,⋆ (σ 2 I + γV t + λ ⋆ I) -1 G t,⋆ + λ⋆ρ(γ) 2 2h 2 t -1 2 ln det(I + σ -2 γV t )) exp( 1 2 G ⊺ t-1,⋆ (σ 2 I + γV t-1 + λ ⋆ I) -1 G t-1,⋆ + λ⋆ρ(γ) 2 2h 2 t -1 2 ln det(I + σ -2 γV t-1 )).Let us abbreviate Σ = σ 2 I + γV t-1 + λ ⋆ I. The matrix determinant lemma and monotonicity of matrix inverse give ln det(I + σ -2 γV t )det(I + σ -2 γV t-1 ) = ln(1 + γg ⊺ t (σ 2 I + γV t-1 ) -1 g t ) ≥ ln(1 + γg ⊺ t Σ -1 g t ).Then Sherman-Morrison givesG ⊺ t,⋆ (σ 2 I + γV t + λ ⋆ I) -1 G t,⋆ = G ⊺ t,⋆ Σ -1 G t,⋆ -γ (g ⊺ t Σ -1 G t,⋆ ) 2 1 + γg ⊺ t Σ -1 g t and splitting off the last round G t,⋆ = G t-1,⋆ + g t gives G ⊺ t,⋆ (σ 2 I + γV t + λ ⋆ I) -1 G t,⋆ = G ⊺ t-1,⋆ Σ -1 G t-1,⋆ + 2G ⊺ t-1,⋆ Σ -1 g t + g ⊺ t Σ -1 g t -γ(g ⊺ t Σ -1 G t-1,⋆ ) 2 1 + γg ⊺ t Σ -1 g t .All in all, it suffices to show-g ⊺ t Σ -1 G t-1,⋆ ≤ 1 -exp ⎛ ⎝ 2G ⊺ t-1,⋆ Σ -1 g t + g ⊺ t Σ -1 g t -γ(g ⊺ t Σ -1 G t-1,⋆ ) 2 2(1 + γg ⊺ t Σ -1 g t ) - 1 2 ln(1 + γg ⊺ t Σ -1 g t ) ⎞ ⎠ . Introducing scalars r = g ⊺ t Σ -1 G t-1,⋆ and z = g ⊺ t Σ -1 g t , this simplifies to -r ≤ 1 -exp( 2r + z -γr 2 2(1 + γz) - 1 2 ln(1 + γz))Being a square, z ≥ 0 is positive. In addition, optimality of λ ⋆ ensures that ∥ΣEQUATIONThe above requirement may hence be further reorganized to2r -γr 2 ≤ -z + (1 + γz)(ln(1 + γz) + 2 ln(1 + r)).The convex right hand side is minimized subject to z ≥ 0 atEQUATIONNote that by (32), we have 2 log(1 + r) ≥ 1 γ -1, and so the condition in the previous display reduces to the second case; that is,EQUATIONwhich is satisfied for the hardest case, where r = e 1 2γ -1 2 -1.Proof. Fix w ∈ R d . Using that Ψ ⋆ (G; V, h, σ, ε) is decreasing in h, we can telescope (27) in Lemma 24 to obtainEQUATIONwhere Σ T ∶= σ 2 I + γV T and Z T ∶= ρ(γ) 2 /h 2 T . Zero derivative of the above objective for λ occurs atλ = ln ∥w∥ 2 Z T 2Z T - w ⊺ Σ T w 2 ∥w∥ 2 ,and hence the optimum for λ is either at that point or at zero, whichever is higher, with the crossover point at ∥w∥ 2 Z T ln ∥w∥ 2 Z T = w ⊺ Σ T w. Plugging that in, we find that for C ∶= ∥w∥ 2 Z T ln ∥w∥ 2 Z T , we haveEQUATIONwhereQ w T ∶= max{w ⊺ Σ T w, 1 2 ( ∥w∥ 2 Z T ln ∥w∥ 2 Z T + w ⊺ Σ T w)};in the last inequality, we used that X(θ) is increasing to drop the exponential in its argument. Combining (36) with (35) and using that X(θ) ≤ √ ln + (θ) (see Lemma 27) , we obtain the desired bound.Lemma 26. Let W ⊆ R d and Y ⊆ R. Further, let f ∶ X × Y → R be a differentiable function such that for all x ∈ X , the problem inf y∈Y f (x, y) has a unique minimizer y(x). Then,EQUATION) Lemma 27. For θ ≥ 0, define X(θ) ∶= sup α α-e α 2 2 -1 2 ln θ . Then X(θ) = (W (θ)) 1/2 -(W (θ)) -1/2 = √ ln θ + o(1).Proof. The fact that X(θ) = (W (θ)) (θ) = sup α α -e α 2 2 -1 2 ln θ = sup α inf η α -η( α 2 2 - 1 2 ln θ) + η ln η -η = inf η 1 2η + η 2 ln θ + η ln η -η ≤ min{ √ ln θ - 1 + 1 2 ln ln θ √ ln θ , √ θ 2 - 1 √ θ } ≤ √ ln + θwhere we plugged in the sub-optimal choices η = Note that e e -2 = 1.14492. This is less than 2, the value of θ where √ θ/2-1/ √ θ becomes positive.In Algorithm 6, we provide a self-contained implementation of an algorithm for regularized online learning (Protocol 2). The algorithm is obtained by combing Algorithm 3 with Algorithm 2.I.1 Efficient Projections for ψ(z) = z 2Our algorithms for regularized online learning via epigraphs (Protocol 3) require projections to the set {y ≥ ψ(x)}. While in general this projection may be expensive, for simple function ψ of interest, such as ψ(z) = z 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 ψ ∶ R → R be given by ψ(x) = x 2 . Define the norm ∥(x, y)∥ 2 = hx 2 + γ 2 y 2 , the function S(x, ŷ) = inf y≥ψ(x) ∥(x, y) -(x, ŷ)∥, and the projection P (x, ŷ) = argmin y≥ψ(x) ∥(x, y) -(x, ŷ)∥. Then for any ŷ < ψ(x), we have P (x, ŷ) = (x, y) with y = x 2 and:x = 2 1/3 (G 2 -2γ 2 ŷ) Z 1/3 - Z 1/3 6 ⋅ 2 1/3 γ 2 with Z = -108G 2 γ 4 x + 2 √ 2916G 2 γ 8 x2 + (6G 2 γ 2 -12γ 4 ŷ) 3 Moreover, ∇S(x, ŷ) = ( G 2 (x-x) √ G 2 (x-x) 2 +γ 2 (-y) 2 , γ 2 (ŷ-y) √ G 2 (x-x) 2 +γ 2 (ŷ-y) 2 )Proof. Since the (x, y) is on the boundary of the constraint, we clearly have y = x 2 . Note that (x, y) = argmin y≥ψ(x) ∥(x, y) -(x, ŷ)∥ 2 . Thus, by LaGrange multipliers, we have for some λ:EQUATIONMoreover, we also must have y = x 2 , so that:G 4 x2 (G 2 -λ) 2 = ŷ - G 2 2γ 2 + G 2 -λ 2γ 2 (G 2 -λ) 3 2γ 2 + (ŷ - G 2 2γ 2 ) (G 2 -λ) 2 -G 4 x2 = 0This is clearly a cubic equation in λ, and so we can apply the cubic formula (via Mathematica) to obtain the following result:λ = 2G 2 3 + 2γ 2 ŷ 3 - 2 5/3 G 2 γ 2 + 2 11/3 G 2 γ 4 ŷ + 2 11/3 γ 6 ŷ2 Z 2/3 - Z 2/3 9 ⋅ 2 5/3 γ 2 where Z = -108G 2 γ 4 x + 2 √ 2916G 2 γ 8 x2 + (6G 2 γ 2 -12γ 4 ŷ) 3which yields:x = 2 1/3 (G 2 -2γ 2 ŷ) Z 1/3 - Z 1/3 6 ⋅ 2 1/3 γ 2 and y = x 2 .The expression for ∇S(x, ŷ) follows directly from [15] Theorem 4. 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper has only mathematical congtent. There are no experiments in this paper.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 no 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the 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 a dataset.38th Conference on Neural Information Processing Systems (NeurIPS 2024).It is plausible that the approach of[25] in concert with the varying potentials of[19] would achieve all points on the frontier as well, although our analysis takes a different direction using the centered mirror descent method of[20].The difference between these conversions lies in where the stochastic gradients gt are computed.A few exceptions achieve the prior bound (3)[17, 20, 22,41]. 
: 
 Protocol 1. Online Learning/Online Convex Optimization. Input: Convex domain W ⊆ R d , number of rounds T . For t = 1, . . . , T :1. Learner outputs w t ∈ W.2. Nature reveals loss vector g t ∈ ∂ℓ t for some convex function ℓ t ∶ W → R to the learner. 3. Learner suffers loss ⟨g t , w t ⟩.The learner is evaluated with the regret ∑ T t=1 (ℓ t (w t )ℓ t (w ⋆ )) against comparators w ⋆ ∈ W. By convexity, the regret is bounded by the linearized regret ∑ T t=1 ⟨g t , w tw ⋆ ⟩. Our goal is to ensure that for all w ⋆ ∈ W simultaneously:EQUATIONQualitatively, we consider a learner to be performing well if 1 T ∑ T t=1 (ℓ t (w t )ℓ t (w ⋆ )) is very small, usually going to zero as 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 (1) is unimprovable in general [3, 4, 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 (1) for appropriately tuned learning rate [6] . More generally, stochastic convex optimization can be reduced to online learning via the online to batch conversion [7] . 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 E[Regret T (w⋆)] T , where w ⋆ is the minimizer of the objective. Online learning can also be used to solve non-convex optimization problems via the recently-developed online to non-convex conversion [8] . In fact, online learning can even be used to prove concentration inequalities [9, 10, 11] . In all of these cases, achieving the bound (1) produces methods that are optimal for their respective tasks. Thus, it is desirable to be able to achieve (1) in as robust a manner as possible.Our goal is to come as close as possible to achieving the bound (1) while requiring minimal prior user knowledge about the loss sequence g 1 , . . . , g t and w ⋆ . In the past, several prior works have achieved the bound (1) when given prior knowledge of either ∥w ⋆ ∥ or max t ∥g t ∥ [12, 13, 14, 15, 16, 17, 18, 19, 20] . 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 ∥w ⋆ ∥ or max t ∥g t ∥. In particular, when considering the application to stochastic convex optimization, the values for ∥w ⋆ ∥ and max t ∥g t ∥ can be interpreted as knowledge of the correct learning rate for stochastic gradient descent [6] . Thus, achieving the bound (1) 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". This paper focuses on this difficult but realistic setting.Our new upper bound. Unfortunately, the bound (1) is actually unobtainable in general without prior knowledge of either the magnitude ∥w ⋆ ∥ or the value of max t ∥g t ∥ [17, 21] . Nevertheless, we will obtain a new compromise bound. For any user-specified γ > 0, our method will achieve:EQUATIONTo dissect this compromise, let us consider the case ∥g t ∥ = G for all t and γ = 1. In this situation, our bound (2) is roughly G 2 + ∥w ⋆ ∥ 2 + ∥w ⋆ ∥G √ T , while the "ideal" bound (1) is merely ∥w ⋆ ∥G √ T . However, for our bound to be significantly worse than (1) , we must have either G ≥ ∥w ⋆ ∥ √ T or ∥w ⋆ ∥ ≥ G √ T . In either case, we might expect that ∥w ⋆ ∥G √ T is roughly Ω(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 is already rather large-the problem is in some sense "too hard".Comparison with previous bounds Our bound (2) is not the first attempted compromise in our fully unconstrained setting. Prior work [17, 22] instead provides the bound:EQUATIONIn fact, readers familiar with this literature may be surprised that our bound is even possible; [17] show that the bound (3) is optimal for the fully-unconstrained case. However, the lower-bound provided by [17] actually has a small loophole; it only applies to algorithms that insist on a linear dependence on max t ∥g t ∥. Our method avoids this lower bound by instead suffering a quadratic dependence on max t ∥g t ∥.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 (3) does not have the desirable property outlined above for our new bound; for ∥g t ∥ = G, it is possible for the bound (3) to be much greater than the ideal bound (1) even when (1) is small.2. The dependency on the user-specified value γ is arguably more sensitive; in (3) , decreasing γ comes at a 1 γ G √ T cost while increasing gamma comes at an γ 2 ∥w ⋆ ∥ 3 cost. In contrast, in our bound (3) , the γ-dependencies are milder; G 2 /γ for decreasing γ (which does not depend on T ) and γ∥w ⋆ ∥ 2 for increasing γ.3. The previous compromise bound (3) has a term that depends on max t ∥g t ∥ (∑ T t=1 ∥g t ∥) rather than ∑ T t=1 ∥g t ∥ 2 . The dependence on the second power of ∥g t ∥ is sometimes referred to as a "second-order" bound and is known to imply constant regret in certain settings [1, 23] (so-called "fast rates"). 4 . Consider the case that both bounds are tuned with their respective "optimal" values for γ. Our new bound would then reduce to Õ (∥w ⋆ ∥ √ ∑ T t=1 ∥g t ∥ 2 + ∥w ⋆ ∥G), while the previous bound would instead become Õ (∥w ⋆ ∥ √ ∑ T t=1 ∥g t ∥ 2 + ∥w ⋆ ∥G 2/3 (∑ T t=1 ∥g t ∥) 1/3 ). Thus, our new bound appears more desirable even with individually optimal tuning. 5. Our bound ensures that when w ⋆ = 0, the dependence on T is O(1). This has a number of useful consequences. For example, by running a separate instance of our algorithm for each dimension of a d-dimensional problem, we can achieve:T ∑ t=1 ⟨g t , w t -w ⋆ ⟩ ≤ Õ ⎛ ⎜ ⎝ 1 γ d ∑ i=1 max t∈[T ] g 2 t,i + γ∥w ⋆ ∥ 2 2 + d ∑ i=1 |w ⋆,i | T ∑ t=1 g 2 t,i ⎞ ⎟ ⎠.Attempting this with the bound (3) would incur a more significant dependence on the dimension d. More generally, this property means that our bound fits into the framework for "combining" regret bounds of [24] . 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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*.

Previous 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.
strength_weakness: strength_weakness: 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. 

2 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?

-------------------
after the response:
They discussed the regimes where their bound is much better than the previous bounds. They also explained the unavailability of prior knowledge in practice.
questions: 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: limitations: Yes
paper_summary: paper_summary: The authors consider the task of unbounded online convex optimization
without prior knowledge of the magnitude of the comparator nor the largest gradient. 
In this context, they propose a parameter-free method whose regret against any arbitrary comparator 
$w_*$ matches the optimal bound of $\mathcal{O}(G||w_{\*}||\sqrt{T})$ up to logarithmic factors when considering 
$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.
strength_weakness: strength_weakness: 1. The authors discuss a number of preliminary ideas and independently interesting techniques which might be useful 
	for some to understand their thought process, but distracting for others who are more interested in the main claims, method and result.
questions: questions: I have some clarification questions, and comments below.
1. Just for clarification, can the authors explain why it is necessary to replace the regularization terms in the loss with constraints?
2. From the analysis of [1], it seems plausible that, for quadratic
	losses at least, regularization can be applied to completely eliminate the 
	magnitude of the iterates in the regret bound at the cost of an additional 
	factor of the magnitude of the comparator, but not the largest gradient.
        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?
3. Can this method be directly extended to work with noisy gradients?

**Comments**
1. In Equation 1, the inequality should be an equality. Same holds for Equation 4, the expression in Theorem 1, e.t.c.
2. In line 66, do you mean "... in our bound (2)"?
3. Line 4 of Protocol 2 should read "loss vector $\tilde{g}\_{t}$" not 
	"loss $\tilde{g}\_{t}$".
4. Line 231 should be "... the outputs 
	$w_1,w_2,\cdots\in\mathbb{R}^d$..."
5. Line 104 should be "... but is not a major focus..."

[1] Neu, G., & Okolo, N. (2024). Dealing with unbounded gradients in stochastic saddle-point optimization. arXiv preprint arXiv:2402.13903.
limitations: limitations: Nil
paper_summary: paper_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. 
The 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.
strength_weakness: strength_weakness: A potential weakness of this paper is the density of the presentation.
It 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).

The 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?

Minor issues:
- Line 86: [15] Theorems 2 and 3 (similar typos are present in several places in the appendix)
questions: questions: It is expected that the authors will address the questions mentioned in the Weakness section.
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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).
- 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.

The 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: 
- 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).
- 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.
- 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.
- I am confused by lines 109-111: if $a_t = 0$ then $\tilde{g}_t + a_t \nabla \psi(w_t) = \tilde{g_t}$ ?
- 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 ?
- 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.
- It would also be useful to have pointers to where the proofs of some of the later Theorems could be found.
- 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.
- 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).

Typos:
- Line 66: “in our bound (3)” - which should be (2).
questions: questions: See some questions in the weaknesses section.
- 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 ?
- 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 3. As the authors mention, an ideal result would also include previous results that are incomparable with the new bound.
questions: 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?

5. 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?

Overall, 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.

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

[2] Attia, A. and Koren, T., 2024. How Free is Parameter-Free Stochastic Optimization?. arXiv preprint arXiv:2402.03126.

[3] Khaled, A. and Jin, C., 2024. Tuning-Free Stochastic Optimization. arXiv preprint arXiv:2402.07793.

[4] Kreisler, I., Ivgi, M., Hinder, O. and Carmon, Y., 2024. Accelerated Parameter-Free Stochastic Optimization. arXiv preprint arXiv:2404.00666.
limitations: limitations: Incomparable results with previous work, which are discussed in the paper.

Comments: title: presentation
Response to Authors Rebuttal
comment: Thanks the authors for their detailed response, which answers my questions. I will raise my score.
Thank you for very much for the author’s response to the review. The authors' reply clearly addresses my questions. I will maintain my current positive score.
Unfortunately, this year are not allowed to submit revisions during the review process. 
However, we overall agree with your suggestions regarding the presentation. In particular,  we will commit to expanding our brief overview of the sequence of reductions at the start of section 3 to introduce $h_t$ and $a_t$  earlier, as well a higher level motivation for the approach. In particular, we will explan how algorithms that typically require a bound on $G$ can usually be modified to work with a value of $G$ that is not static but actually increases over time, and how we approximate  such a scenario with $h_t$. Then we will discuss that the remaining regret from this approach can be "cancelled" by adding an  additional quadratic regularization given by $a_t$. We will motivate this technique with the following example: suppose that for all but the *very last iteration*, it holds that $\|g_t\|\le H$ for some known value $H$. Then on the first $T-1$ iterations we can run a known-$G$ algorithm with $G=H$  and obtain low regret. However, on the last round we may discover that $G\gg  H$.  The maximum extra regret we can experience in this last round $(G-H)\|w_T - u\|\le G\|w_T\|+G\|u\|\le \frac{(G-H)^2}{2a_t } + \frac{a_t\|w_T\|^2}{2} + (G-H)\|u\|$. So, our approach is to add quadratic regularization to offset the $\frac{a_t \|w_T\|^2}{2}$  at the cost of an additional $\frac{a_t\|u\|^2}{2}$ in the regret. 

Your suggestion to add  more discussion after Theorem 1 linking back to equation (2) is also a good one and we will implement it as well.
Thanks to the authors for their response. Apologies, I had missed the square on the $a_t$ in (4) - this clarifies my query. I will keep my score but acknowledge that it could be raised to a 7 with an improved presentation of the final version.
I thank the authors for their response and am happy to keep my score.

That said, I suggest the authors to conisder extending their method to work with quadratic losses, i.e getting rid of $G$ which can scale with $\|w_t\|$ while retaining the optimal $\mathcal{O}(\|w^*\|\sqrt{T})$ scaling in the bound, at least in cases where sub-linear regret is achievable. This would be an interesting future direction.
I thank the authors for their response.

I have read the reviews and responses and would like to keep my score.