Fully Unconstrained Online Learning

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.

Strengths

1. The paper unrolls a detailed discussion and comparison with previous work, providing an in-depth understanding of the problem, including both results and techniques. 2. The guarantee is new and possesses several properties that are more appealing than previous ''fully parameter-free'' results, including a nicer symmetry between $G$ and $\lVert w_\star \rVert$ without a dependence in $T$ on the excess terms.

Weaknesses

3. As the authors mention, an ideal result would also include previous results that are incomparable with the new bound.

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.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Incomparable results with previous work, which are discussed in the 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.

Strengths

- The regret bounds significantly improve upon prior work in certain settings, e.g. when $||g_t||=G$ for all $t$ or can have milder dependence on the $\gamma$-parameter. - A lower-bound is provided to establish the tightness of their bounds. - They exploit reductions from prior works that make some aspects of the analysis easier to present and follow. Their proposed regularisation of the losses is an interesting technical contribution.

Weaknesses

- The improvement upon prior work is only relevant under specific conditions. In particular, if $||g_t||$ is not constant and many are small (or even 0) and only a few are large, it is unclear which bound is better. It would also be interesting to have a comparison of the bounds for the “optimal” value of $\gamma$ (which of course is not of practical use but may help provide some intuition). - 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

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 ?

Rating

6

Confidence

2

Soundness

3

Presentation

1

Contribution

3

Limitations

Yes

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.

Strengths

The authors make a solid contribution to parameter-free online learning under the assumption that both the magnitude of the comparator $\|| w_* \||$ and the Lipschitz continuity $G$ of the loss are unknown. In particular, the second-order bound, which is one of the main differences from existing bounds, is an important contribution. The quality of the paper is high. Although the presentation is very dense, it is clear, and the flow of the sequence of reductions and their motivations are explained in a comprehensive manner. The proof sketch of Theorem 1 in Section 3.2 is clearly given while explaining the existing techniques in online convex optimization. I have only partially reviewed the proofs in the appendix, but they appear to be correct.

Weaknesses

A potential weakness of this paper is the density of the presentation. 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

It is expected that the authors will address the questions mentioned in the Weakness section.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

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.

Strengths

1. This paper contributes to the budding line of work on near-optimal parameter-free online convex optimization. The authors build on the seminal work of Ashok Cutkosky on Artificial Constraints and Hints for Unbounded Online Learning, and address, in a unique way, a significant constraint in that work. 2. The paper is technically sound. The authors are honest about their methodology and adequately cite related works. Also, the submission was clearly written. 3. Overall, the authors address an important yet complex task by combining existing techniques in an unconventional way.

Weaknesses

1. The authors discuss a number of preliminary ideas and independently interesting techniques which might be useful for some to understand their thought process, but distracting for others who are more interested in the main claims, method and result.

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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

4

Limitations

Nil

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.

Strengths

1 This paper provides an algorithm that improved the regret bound for the fully unconstrained online convex optimization. It achieves the optimal bound for all sublinear regret regimes. The previous work for fully unconstrained online learning has a larger additive term G|w*|^3, which can not get the optimal bound for all sublinear regimes.

Weaknesses

1 The paper introduces a lot of notations before defining them properly. It is not easy to read and have a general idea about the techniques. 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

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?

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes