Fully Unconstrained Online Learning

Thanks for your review!

Q1: Yes, in a certain sense. The way to to obtain the improved PoA using [1] is simply to only do the clipping suggested by [1] and not the artificial constraints - instead just rely upon the coarse bound on $\|w_\star\|$. We could do the same thing by just replacing our regularization with a constraint to the coarse bound, which makes the two algorithms the same. That said, it would better to have a "cleaner" way to do this.

Q2: Yes, our bound implies this sort of result immediately. In general, "variance of gradients"-style bounds for smooth losses are implied by any online algorithm whose regret bound depends on $\sum_{t=1}^T \|g_t\|^2$.

To see this, let $L$ be the expected loss. Then we have $\sum_{t=1}^T \|g_t\|^2 \sim \sum_{t=1}^T \|\nabla L(w_t)\|^2 + T\sigma^2 \le \sum_{t=1}^T L(w_t) -L(w_\star) + T\sigma^2$. So, our regret bound looks like $\sum_{t=1}^T L(w_t) - L(w_\star) \le O(\sqrt{T\sigma^2 + \sum_{t=1}^T L(w_t) - L(w_\star)})$, which implies $\sum_{t=1}^T L(w_t) - L(w_\star) \le O(1+\sqrt{T\sigma^2})$. This is one motivation for why we wanted to achieve the $\sum_{t=1}^T \|g_t\|^2$ in the regret bound rather than $G\sum_{t=1}^T \|g_t\|$ as obtained by the previous work.

Thank you so much for your very detailed review and you careful comments on the presentation. We will work hard to incorporate your comments into the final version. In the interest of brevity, below we respond to just a few of your comments:

• For the "optimal" value of $\gamma$ our bound is always better. This is because for the optimal $\gamma$ value the previous bound is $O\left[\|w_\star\|\sqrt{\sum_{t=1}^T \|g_t\|^2} + \|w_\star\| G^{2/3}\left(\sum_{t=1}^T \|g_t\|\right)^{1/3}\right]$ while ours is $\tilde O\left[\|w_\star\|\sqrt{\sum_{t=1}^T \|g_t\|^2} + G\|w_\star\|\right]$ where $G=\max_t\|g_t\|$. Thanks for suggesting this comparision!
• We can actually deal with arbitrary Banach spaces (so any reasonable norm). This is because the reduction in Section 3 of https://arxiv.org/pdf/1802.06293 shows that to solve an online learning problem in a Banach space, you need only be able to solve it in 1-dimension. We focused on the familiar L2 case here to tame the complexity a little bit.
• There are by now many algorithms that deal with either unknown $G$ or unknown $\|w_\star\|$ ahead of time - it is dealing with both at once that is somewhat more rare. That said, the unknown $\|w_\star\|$ case is arguably more challenging. Our particular approach works by improving algorithms that deal with known $\|w_\star\|$, which is why our exposition focuses on these problems.
• Regarding Lines 109-110: That's right. In these lines we are suggesting a straw-man algorithm: replace $\tilde g_t$ with $\hat g_t= \tilde g_t + a_t \nabla \psi(w_t)$. Then we could try to solve the problem by considering the pure linear losses $\langle \hat g_t, w\rangle$, which would be equivalent to the case $a_t=0$.
• The weaker bound (7) vs the bound (4). We believe (4) is actually smaller than (7), not the other way around. This is because (7) depends on $\gamma \sum_{t=1}^T a_t$ while (4) depends on $\sum_{t=1}^T a_t^2$, and $a_t\le \gamma$ for all $t$. We chose to present (4) first because it is the true "ideal" bound, and we can in fact achieve it with a more computationally expensive algorithm.

Questions:

1. Yes, the bounds hold for all $w_\star$ simultaneously, including 0. In the case $w_\star=0$, our bound achieve constant regret, while the previous approach achieves $O(\sqrt{T})$ regret. For the case $G\to 0$, you're right our bound appears to not go to zero. However, we believe this is an artifact of analysis: notice that all algorithms achieve zero regret when $G\to 0$. In our particular case, the algorithm will set $w_t=0$ for all $t$, as one might intuitively expect.
2. The unconstrained strongly convex setting is perhaps understudied in online learning: even the standard $G^2\log(T)$ bound doesn't really make sense since $G$ is unbounded in the unconstrained setting. We would suffer from this same issue. It's an interesting open problem to deal with this!

Thanks for your work reviewing our paper!

W1 (Regarding the density of the presentation): We chose a presentation intended to communicate all of the ideas, but it might become difficult to follow and we will work to make things clearer in the revision. For the epigraph-based learning, the idea is the following: Suppose you are interested in an online learning problem with losses of the form $\ell_t(w) = \langle g_t, w\rangle + a_t \psi(w)$ for some known function $\psi$. We are guaranteed $\|g_t\|\le 1$ and $a_t \in[0,1]$, but $\psi$ may not be Lipschitz. This means that we cannot apply the standard linearization trick $\ell_t(w)-\ell_t(w_\star) \le \langle \hat g_t, w-w_\star\rangle$ with $\hat g_t= g_t +a_t \nabla \psi(w)$ and then run an OLO algorihtm using $\hat g_t$ because $\hat g_t$ is not bounded. To fix this, we instead consider the 2-dimensional problem with parameter $(w_t, y_t)$ subject to the constraint $y_t \ge \psi(w_t)$ and linear losses $\hat \ell_t(w_t, y_t) = \langle g_t, w_t\rangle + a_t y_t$. This has the property that $\hat \ell(w_t, y_t) - \hat \ell_t(w_\star, \psi(w_\star)) \ge \ell_t(w_t) - \ell_t(w_\star)$, so it suffices to control the regret on the constrained linear problem.

For protocol 2, the idea is that when one checks the analysis of essentially any algorithm that assumes a fixed Lipschitz constant, it is usually fairly easy to change the algorithm to allow for the Lipschitz constant to grow over time. Protocol 2 captures this by letting $h_t$ describe the growth in the Lipschitz constant. Of course, in general we do not know how it might grow over time, which is what the clipping technique in our final analysis addresses.

W2 (definition of $w^{1d}_t$ in Algorithm 1): We apologize for the typo here: $w^{1d}$ is the same as $w^{\text{magnitude}}$. In the revision we will only mention $w^{\text{magnitude}}$ and convert all the $1D$ superscripts to $\text{magnitude}$. Intuitively, the idea is that the 1-dimensional learner $\mathcal{A}^{1D}$ is responsible for learning the magnitude of the comparison point $u$, while the direction $u/\|u\|$ is learned by a standard mirror descent algorithm in $w^{\text{direction}}$. See also the development in Sections 3 and 4 of https://arxiv.org/pdf/1912.13213, which is where we got these reductions.

Thanks for your detailed review! Below we answer your questions.

Q1: It is may not be strictly "necessary" to replace the regularization with a constraint - we suspect that in fact a suitable variation on e.g. FTRL based algorithms would also achieve the same goals. However, the constraint approach led to an algorithm that does not require solving a complex subproblem, and we also feel it is inherently interesting as it is a technique less commonly deployed in online optimization.

Q2: We agree, the technique of [1] is essentially to apply an extra quadratic regularizer to an FTRL update. We believe an approach along these lines could achieve the same results we have for the quadratic case without using constraints. However, it would probably not remove the $G^2$ dependence on its own because the $G^2$ dependence arises from the calculuation that makes eliminating $\|w_t\|^2$ a useful thing to do.

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.

Thanks for your work reviewing our paper! Regarding the unvailability of prior knowledge of $\|w_\star\|$ and $G$ in practice, let's think about the stochastic optimization setting. In this case, the unavailability of $G$ in practice is exactly the problem that popular methods like AdaGrad (the precurser to Adam) actually solve. However, these algorithms still require tuning a learning rate scalar, which roughly corresponds to selecting the value for $\|w_\star\|$. In fact, we actually have trouble coming up with many compelling examples in which $\|w_\star\|$ is available ahead of time.

Regarding your question, the new bound is better in two important regimes:

1. When the $\|w_\star\|$ is large or $\gamma$ is small, so that the difference between the $\|w_\star\|^3/\gamma^2$ penalty incurred by the previous bounds is large compared to the $\|w_\star\|^2/\gamma$ penalty we incur. See also the response to review 1CHH, in which we observe that if both our bound and the previous bound are provided the optimal tuning for $\gamma$, our bound is always better.
2. For a more intuitive setting, consider a stochastic optimization problem in which the losses are smooth and $\ell_t(w_\star)=0$ for all $t$. In this case, by applying standard self-bounding arguments (e.g. see section 4.2 of A modern Introduction to Online Leraning), we will actually obtain constant regret due to our dependence on $\sum_{t=1}^T \|g_t\|^2$, while the previous bound that depends on $\sum_{t=1}^T G \|g_t\|$ will at best obtain $O(T^{1/3})$ regret.