1 Introduction↩︎

Online learning is a setting where the learner receives an arbitrary sequence of loss functions, selects points before knowing the loss functions, and is evaluated on the values of the loss functions on the points it selects [1]–[3]. More in detail, at round \(t\) the learner outputs a point \(\boldsymbol{x}_t\) in a feasible set \(V\subseteq \mathbb{R}^d\). Then, it receives a loss function \(\ell_t: V \to \mathbb{R}\) and it pays the value \(\ell_t(\boldsymbol{x}_t)\). Given the arbitrary nature of the losses, the learner cannot guarantee to have a small cumulative loss, \(\sum_{t=1}^T \ell_t(\boldsymbol{x}_t)\). On the other hand, it is possible to minimize the regret, that is the difference between the cumulative loss of the algorithm and the one of any arbitrary comparator \(\boldsymbol{u}\in V\): \[\mathop{\mathrm{Regret}}_T(\boldsymbol{u}) \triangleq \sum_{t=1}^T \ell_t(\boldsymbol{x}_t) -\sum_{t=1}^T \ell_t(\boldsymbol{u})~.\] In particular, a successful online learning algorithm must guarantee a regret that grows sublinearly in time for any \(\boldsymbol{u}\in V\). In this way, its average performance approaches the one of the best comparator in hindsight.

There are two families of online learning algorithms: Online Mirror Descent (OMD) [4], [5] and Follow-the-Regularized-Leader (FTRL) [6]–[8]. They stem from two similar but complementary approaches: the update of OMD aims at minimizing a linearization of the current loss without going too far from its previous prediction \(\boldsymbol{x}_t\), while FTRL minimizes the sum of all the losses (or their linear approximation) plus a regularization term. On the contrary to the first approaches in online learning that focused on specific algorithms (e.g., the Winnow algorithm [9]), the theory of these two frameworks is particularly interesting because it allows both the design and the analysis of generic online learning algorithms.

While FTRL and OMD provide similar bounds in most situations, they are not completely equivalent. For example, FTRL has an advantage over OMD in unbounded domains, where it allows to use time-varying regularizers. In fact, OMD allows the use of time-varying stepsizes only in domains where its associated Bregman divergence is bounded.

On the other hand, in the cases where we can use time-varying stepsizes, OMD can achieve a superior adaption to the gradients (see, e.g., Theorem 2 in [10] versus Theorem 2 in [11]). In this view, these two frameworks are complementary.¹ Moreover, there exists another orthogonal axis on the use of the actual loss functions or a linear surrogate for both frameworks. We summarize all the variants of OMD and FTRL in Table 1.

Our motivation stems from the fact that in practical cases, all the variants that use full losses offer a big advantage in terms of empirical performance at the cost of a higher computational complexity. On the theoretical side, the situation is not so clear given that in the worst case using the full losses can be equivalent to their linearized version, as it should be clear considering linear losses. In particular, the standard theoretical framework for FTRL does not allow a clear analysis of the implicit case. Moreover, while for implicit OMD it has been proven that one can achieve lower regret if the temporal variation of the losses is small, it is unclear if the same guarantee can be achieved for FTRL without the computational cost of using full losses.

In this paper, we aim at bridging this gap proposing a generalized version of implicit FTRL. We go beyond implicit and linearized updates: we directly construct the update rule in a way that minimizes an upper bound on the regret. Our framework effectively expands the scope of the FTRL framework, fully retaining its coupling between design and analysis. Also, our updates come with a worst-case guarantee to never be worse than the standard linearized ones.

We show the flexibility of our framework recovering known update schemes, like the Mirror-Prox update [14], or extending updates specifically designed for OMD to the FTRL case, like the aProx one [15]. Moreover, for the first time, we show an implicit version of FTRL that recovers the temporal variation bound of implicit OMD [16], but with the same computational complexity of implicit OMD.

1.0.0.1 Related Work

While there are many works on implicit mirror descent in both the online and offline setting [16]–[22], the number of works that deal with implicit updates for FTRL is quite limited. We are only aware of [13], which quantifies a gain only for specific regularizers. However, the framework in [13] is non-constructive in the sense that it is difficult to see how to generalize implicit updates. [23] extends this last result, but it does not provide a link with the maximization of the dual function that governs the regret upper bound.

The closest approach to our framework is the one of [24], [25], which develop a theory of FTRL updates as maximization of a dual function. However, their framework is limited to a specific shape of regularizers and it does not deal with implicit updates.

For implicit OMD, [16] showed that implicit updates give rise to regret guarantees that depend on the temporal variability of the losses, so that constant regret is achievable if the variability of the losses is zero. They suggest that FTRL with full losses can achieve the same guarantee, but they also point out that given its computational complexity it would be “not worth pursuing.” Here, we show how to achieve the same bound of implicit OMD with our generalized implicit FTRL, while retaining the same computational complexity of implicit OMD.

Proximal updates on truncated linear models were introduced in [15] for the OMD algorithm. [26] used gradient flow on the same truncated linear models with a coin-betting algorithm [27], but their approach does not seem to satisfy a regret guarantee. [28] have used truncated linear models in an FTRL-based parameter-free algorithm [29] with a novel decomposition of the regret. However, their approach is ad-hoc is it seems difficult to generalize it.

2 Definitions and Basic Tools↩︎

We define here some basic concepts and tools of convex analysis, we refer the reader to, e.g., [30], [31] for a complete introduction to this topic. We will consider extended value function that can assume infinity values too. A function \(f\) is proper if it is nowhere \(-\infty\) and finite somewhere. A function \(f:V \subseteq \mathbb{R}^d \rightarrow [-\infty, +\infty]\) is closed if \(\{\boldsymbol{x}: f(\boldsymbol{x}) \leq \alpha\}\) is closed for every \(\alpha \in \mathbb{R}\). For a proper function \(f:\mathbb{R}^d \rightarrow (-\infty, +\infty]\), we define a subgradient of \(f\) in \(\boldsymbol{x}\in \mathbb{R}^d\) as a vector \(\boldsymbol{g}\in \mathbb{R}^d\) that satisfies \(f(\boldsymbol{y})\geq f(\boldsymbol{x}) + \langle \boldsymbol{g}, \boldsymbol{y}-\boldsymbol{x}\rangle, \;\forall \boldsymbol{y}\in \mathbb{R}^d\). We denote the set of subgradients of \(f\) in \(\boldsymbol{x}\) by \(\partial f(\boldsymbol{x})\). The indicator function of the set \(V\), \(i_V:\mathbb{R}^d\rightarrow (-\infty, +\infty]\), has value \(0\) for \(\boldsymbol{x}\in V\) and \(+\infty\) otherwise. We denote the dual norm of a norm \(\|\cdot\|\) by \(\|\cdot\|_\star\). A proper function \(f : \mathbb{R}^d \rightarrow (-\infty, +\infty]\) is \(\mu\)-strongly convex over a convex set \(V \subseteq \mathop{\mathrm{int}}\mathop{\mathrm{dom}}f\) w.r.t. \(\|\cdot\|\) if \(\forall \boldsymbol{x}, \boldsymbol{y}\in V\) and \(\forall \boldsymbol{g}\in \partial f(\boldsymbol{x})\), we have \(f(\boldsymbol{y}) \geq f(\boldsymbol{x}) + \langle \boldsymbol{g}, \boldsymbol{y}- \boldsymbol{x}\rangle + \frac{\mu}{2} \| \boldsymbol{x}- \boldsymbol{y}\|^2\). A function \(f:V \rightarrow \mathbb{R}\), differentiable in an open set containing \(V\), is \(L\)-smooth w.r.t. \(\|\cdot\|\) if \(f(\boldsymbol{y}) \leq f(\boldsymbol{x}) + \langle \nabla f(\boldsymbol{x}) , \boldsymbol{y}- \boldsymbol{x}\rangle + \frac{M}{2} \| \boldsymbol{x}- \boldsymbol{y}\|^2\) for all \(\boldsymbol{x}, \boldsymbol{y}\in V\). For a function \(f: \mathbb{R}^d\rightarrow [-\infty,\infty]\), we define the Fenchel conjugate \(f^\star:\mathbb{R}^d \rightarrow [-\infty,\infty]\) as \(f^\star(\boldsymbol{\theta}) = \sup_{\boldsymbol{x}\in \mathbb{R}^d} \;\langle \boldsymbol{\theta}, \boldsymbol{x}\rangle - f(\boldsymbol{x})\). From this definition, we immediately have the Fenchel-Young inequality: \(f(\boldsymbol{x}) + f^\star(\boldsymbol{\theta}) \geq \langle \boldsymbol{\theta}, \boldsymbol{x}\rangle, \;\forall \boldsymbol{x}, \boldsymbol{\theta}\).

We will also make use of the following properties of Fenchel conjugates.

3 Generalized Implicit FTRL↩︎

In this section, we introduce our novel generalized formulation of the implicit FTRL algorithm. The main idea is to depart from the implicit or linearized updates, and directly design updates that improve the upper bound on the regret. More in detail, the basic analysis of most of the online learning algorithms is based on the definition of subgradients: \[\label{eq:subgradient95ineq} \ell_t(\boldsymbol{x}_t) - \ell_t(\boldsymbol{u}) \leq \langle \boldsymbol{g}_t, \boldsymbol{x}_t-\boldsymbol{u}\rangle, \;\forall \boldsymbol{g}_t \in \partial \ell_t(\boldsymbol{x}_t)~.\tag{1}\] This allows to study the regret on the linearized losses as a proxy for the regret on the losses \(\ell_t\). However, we can do better. We introduce a new fundamental and more general strategy: using the Fenchel-Young inequality, we have \[\ell_t(\boldsymbol{x}_t) - \ell_t(\boldsymbol{u}) \leq \ell_t(\boldsymbol{x}_t) - \langle \boldsymbol{z}_t,\boldsymbol{u}\rangle + \ell_t^\star(\boldsymbol{z}_t), \;\forall \boldsymbol{z}_t~.\] In particular, the algorithm will choose \(\boldsymbol{z}_t\) to make a certain upper bound involving this quantity to be tighter. This is a better inequality than 1 because when we select \(\boldsymbol{z}_t=\boldsymbol{g}_t \in \partial \ell_t(\boldsymbol{x}_t)\), using Theorem 1, we recover 1 . So, this inequality subsumes the standard one for subgradients, but, using \(\boldsymbol{z}_t \in \ell_t(\boldsymbol{x}_{t+1})\), it also subsumes the similar inequality used in the implicit case, as we show in Section 3.1. Moreover, we will see in Section 6 that it covers cases where \(\boldsymbol{z}_t\) is not a subgradient of \(\ell_t\).

The analysis shows that the optimal setting of \(\boldsymbol{z}_t\) is the one that minimizes the function \[\label{eq:h} H_t(\boldsymbol{z}) \triangleq\psi^\star_{t+1,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}) + \ell^\star_t(\boldsymbol{z})\tag{2}\] or \[\label{eq:hprime} H'_t(\boldsymbol{z}) \triangleq\psi^\star_{t,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}_t) + \ell^\star_t(\boldsymbol{z}),\tag{3}\] where \(\psi_{t,V}\) is the restriction of the regularizer used at time \(t\) on the feasible set \(V\), i.e., \(\psi_{t,V}\triangleq\psi_t+i_V\). However, we can show that any setting of \(\boldsymbol{z}_t\) that guarantees \(H(\boldsymbol{z}_t)< H(\boldsymbol{g}_t)\) (or \(H'(\boldsymbol{z}_t)< H'(\boldsymbol{g}_t)\)) guarantee a strict improvement in the worst-case regret w.r.t. using the linearized losses.

One might wonder why the need for two different updates using \(H_t\) or \(H'_t\). The reason is that when using time-varying regularizers that depend on the data, like in the FTRL version of AdaGrad [32], [33], if \(\lambda_{t+1}\) depends on \(\boldsymbol{z}_t\) it might make the calculation of the update particularly difficult. This can be avoided using the update involving \(H'_t\).

Once we have the \(\boldsymbol{z}_t\), we treat them as the subgradient of surrogate linear losses. So, putting it all together, Algorithm 1 shows the final algorithm. We now show a regret guarantee for this algorithm. First, we state a general Lemma and then instantiate it in a few interesting cases.

The Theorem is stated with very weak assumption to show its generality, but it is immediate to obtain concrete regret guarantees just assuming, for example, strongly convex regularizers and convex and Lipschitz losses and using well-known methods as [2]

However, we can already understand why this is an interesting guarantee. Let’s first consider the case that \(\boldsymbol{z}_t=\boldsymbol{g}_t\). In this case, we exactly recover the linearized FTRL algorithm. Even the guarantee in the Theorem exactly recovers the best known one [2], with \(\delta_t=0\) and \(\delta'_t=0\). Now, if we set \(\boldsymbol{z}_t\) such that \(H_t(\boldsymbol{z}_t)< H_t(\boldsymbol{g}_t)\) or \(H'_t(\boldsymbol{z}_t)< H'_t(\boldsymbol{g}_t)\) we will have that \(\delta_t>0\) or \(\delta'_t>0\). Hence, in each single term of the sum we have a negative factor that makes the regret bound smaller. While it might be difficult to give a lower bound to \(\delta_t\) and \(\delta'_t\) without additional assumptions, the main value of this analysis is in giving a unifying way to design generalized implicit updates for FTRL. In fact, in the next sections we will show a number of possibilities that this framework enables.

Next, we will gain more understanding on the updates in Algorithm 1, comparing them to implicit OMD.

3.1 Comparison with Implicit Online Mirror Descent↩︎

In this section, we show that when \(\boldsymbol{z}_t\) is set to minimize \(H_t(\boldsymbol{z})\) or \(H'_t(\boldsymbol{z})\), we recover different variants of implicit updates.

Assume that the \(\ell_t\) are closed and convex. Also, assume that \(\psi^\star_{t,V}\) is differentiable, that is true, for example, when \(\psi_t\) is strongly convex by Theorem 2. Then, observe that by the first-order optimality condition and Theorem 1, we have \[\begin{align} \boldsymbol{z}_t &= \mathop{\mathrm{argmin}}_{\boldsymbol{z}} \;H_t(\boldsymbol{z}) \nonumber \\ &\Leftrightarrow \nabla \psi^\star_{t+1,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}_t) \in \partial \ell^\star_t(\boldsymbol{z}_t) \nonumber \\ & \Leftrightarrow \boldsymbol{z}_t \in \partial \ell_t(\nabla \psi^\star_{t+1,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}_t)) = \partial \ell_t(\boldsymbol{x}_{t+1})~. \label{eq:cond95update95exact} \end{align}\tag{4}\] Hence, in this case, we have that the optimal \(\boldsymbol{z}_t\) is the gradient at the next point \(\boldsymbol{x}_{t+1}\). This is exactly what happens in the implicit updates.

Under the same assumptions, we also have \[\begin{align} \boldsymbol{z}_t = \mathop{\mathrm{argmin}}_{\boldsymbol{z}} \;H'_t(\boldsymbol{z}) &\Leftrightarrow \nabla \psi^\star_{t,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}_t) \in \partial \ell^\star_t(\boldsymbol{z}_t) \nonumber \\ & \Leftrightarrow \boldsymbol{z}_t \in \partial \ell_t(\nabla \psi^\star_{t,V}(\boldsymbol{\theta}_{t+1}))~. \label{eq:cond95update95inexact} \end{align}\tag{5}\] In this other case, the update also has an implicit flavor but the subgradient is queried on a point different from the next point, where the difference depends on how much \(\nabla \psi^\star_{t, V}\) differs from \(\nabla \psi^\star_{t+1, V}\).

Let’s see this connection even more precisely, considering proximal updates. Hence, for simplicity, let’s consider the case that \(V=\mathbb{R}^d\), similar considerations hold in the constrained case. Consider the case that \(\psi_t(\boldsymbol{x})=\frac{\lambda_t}{2}\|\boldsymbol{x}\|_2^2\). In this case, the update can be written with the proximal operator of the loss functions. In particular, the proximal operator of \(\eta f\), is defined as \[\mathop{\mathrm{Prox}}_{\eta f}(\boldsymbol{y}) \triangleq \mathop{\mathrm{argmin}}_{\boldsymbol{x}\in \mathbb{R}^d} \;\frac{1}{2}\|\boldsymbol{x}-\boldsymbol{y}\|_2^2 + \eta f(\boldsymbol{x})~.\] If the function \(f\) is differentiable we have that \(\mathop{\mathrm{Prox}}_{\eta f}(\boldsymbol{y}) = \boldsymbol{y}- \eta \nabla f(\mathop{\mathrm{Prox}}_{\eta f}(\boldsymbol{y}))\). In words, the proximal update moves by a quantity that depends on the gradient on the updated point. The implicit nature of these updates justifies the name “implicit updates” used in the online learning literature. More generally, we have that \(\mathop{\mathrm{Prox}}_{\eta f}(\boldsymbol{y}) \in \boldsymbol{y}- \eta \partial f(\mathop{\mathrm{Prox}}_{\eta f}(\boldsymbol{y}))\). We list some common proximal operators in Appendix 9.

Assuming \(\lambda_{t+1}\) does not depend on \(\boldsymbol{z}_t\), using the proximal operator we can rewrite the update in 4 as

\[\begin{align} \boldsymbol{x}_{t+1} &=\frac{\boldsymbol{\theta}_{t+1}}{\lambda_{t+1}} = \mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda_{t+1}}}\left(\frac{\boldsymbol{\theta}_t}{\lambda_{t+1}}\right) \nonumber \\ &= \mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda_{t+1}}}\left(\frac{\lambda_t \boldsymbol{x}_t}{\lambda_{t+1}}\right)~. \label{eq:prox95ftrl952} \end{align}\tag{6}\]

Similarly, we can rewrite the update in 5 as \[\begin{align} \frac{\boldsymbol{\theta}_{t+1}}{\lambda_t} &= \frac{\boldsymbol{\theta}_{t}}{\lambda_t} - \frac{\boldsymbol{z}_t}{\lambda_t} = \boldsymbol{x}_t - \frac{\boldsymbol{z}_t}{\lambda_t} \in \boldsymbol{x}_t - \frac{1}{\lambda_t}\partial \ell_t(\nabla \psi^\star_{t,V}(\boldsymbol{\theta}_{t+1})) \\ &= \boldsymbol{x}_t - \frac{1}{\lambda_t}\partial \ell_t\left(\frac{\boldsymbol{\theta}_{t+1}}{\lambda_t}\right)~. \end{align}\] Hence, we have that \(\frac{\boldsymbol{\theta}_{t+1}}{\lambda_t} = \mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda_t}} (\boldsymbol{x}_t)\) and we get \[\label{eq:prox95ftrl951} \boldsymbol{x}_{t+1} = \frac{\boldsymbol{\theta}_{t+1}}{\lambda_{t+1}} = \frac{\lambda_t}{\lambda_{t+1}}\mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda_t}} (\boldsymbol{x}_t)~.\tag{7}\]

It is instructive to compare both updates with the one of Implicit Online Mirror Descent using \(\psi(\boldsymbol{x})=\frac{1}{2}\|\boldsymbol{x}\|^2_2\) as distance generating function and stepsizes \(\frac{1}{\lambda_t}\). In this case, we would update with \[\begin{align} \boldsymbol{x}_{t+1} &= \mathop{\mathrm{argmin}}_{\boldsymbol{x}} \frac{1}{2} \|\boldsymbol{x}_t-\boldsymbol{x}\|_2^2 + \frac{1}{\lambda_t}\ell_t(\boldsymbol{x}) \nonumber \\ &= \mathop{\mathrm{Prox}}_\frac{\ell_t}{\lambda_t}(\boldsymbol{x}_t)~. \label{eq:prox95omd} \end{align}\tag{8}\] Comparing 4 and 5 to 8 , we see, when \(\lambda_t \leq \lambda_{t+1}\) as it is usual, the two updates above shrink a bit towards the zero vector, that is the initial point \(\boldsymbol{x}_1\), before or after the proximal operator. This shrinking is given by the FTRL update and it is the key difference with Implicit OMD update. The different update also corresponds to a different guarantee: the regret of the generalized implicit FTRL holds for unbounded domains too, while in Implicit OMD with time-varying stepsizes can have linear regret on unbounded domains [34]. Interestingly, a similar shrinking has been proposed in [35] to fix the unbounded issue in OMD. Clearly, the updates 4 and 5 become equivalent to 8 for \(\lambda_t\) constant in \(t\), that is exactly the only case when implicit/proximal online mirror descent works for unbounded domains.

4 Temporal Variability Bound↩︎

In this section, we quantify the advantage of the generalized implicit FTRL updates in the case of slow temporal variability of the loss functions.

It was observed in [16] that implicit OMD satisfies regret guarantees that depends on the temporal Variability \(V_T\): \[V_T \triangleq \sum_{t=2}^T \max_{x\in V} \;\ell_t(\boldsymbol{x}) - \ell_{t-1}(\boldsymbol{x})~.\] In [16] they also show that FTRL with full losses guarantees a similar guarantee, but at a much higher computational price. Indeed, FTRL with full losses requires solving a finite sum optimization problem at each step, whose size increases with the number of iterations. Such computational burden induced [16] to say that such approach is “not worth of pursuing.”

Here, we show that the Algorithm 1 can satisfy the same guarantee of implicit OMD with the same computational complexity too. First, we show the following Lemma.

This Lemma mirrors Theorem 5.2 in [16], with the important difference that here we do not need the Bregman divergence to be bounded on the feasible set \(V\), thanks to the use of FTRL instead of OMD. We can now state the immediate corollary on a regret bound that depends on the temporal variation.

From this result, following [16], it is relatively easy to obtain the following adaptive regret guarantee. The only difficulty is the fact that we need \(\psi_{t+1}\) to be independent of \(\boldsymbol{z}_t\) to have a simpler update rule. We solve this problem using an increasing regularizer that is “behind of two steps”. In this way, we have that \(\lambda_{t+1}\) depends on quantities that are all known at the beginning of round \(t\). The proof is in Appendix 10.

5 Two-step Updates↩︎

The choice of \(\boldsymbol{z}_t\) that minimizes the regret upper bound requires solving the optimization problem \(\min_{\boldsymbol{z}} \;H(\boldsymbol{z})\) or \(\min_{\boldsymbol{z}} \;H'(\boldsymbol{z})\). We have seen in Section 3.1 that this corresponds to (some variant) of a implicit/proximal update and, depending on \(\ell_t\), it can be of difficult calculation. However, as we said, any choice better than \(\boldsymbol{g}_t\) will cause a provable gain. Hence, a viable solution is to approximately solve for the optimal \(\boldsymbol{z}_t\).

Here, we propose a simple approximation: set \(\boldsymbol{z}_t\) as \[\label{eq:two95step95h} \boldsymbol{z}_t \in \partial \ell_t(\nabla \psi^\star_{t+1,V}(\boldsymbol{\theta}_t-\boldsymbol{g}_t))\tag{9}\] or as \[\label{eq:two95step95hprime} \boldsymbol{z}_t \in \partial \ell_t(\nabla \psi^\star_{t,V}(\boldsymbol{\theta}_t-\boldsymbol{g}_t))~.\tag{10}\] In words, we set \(\boldsymbol{z}_t\) to be a subgradient after one fake update. This is exactly the approach used in the Mirror-Prox algorithm [14], an offline optimization algorithm. In the next theorem, when the loss functions \(\ell_t\) are smooth and the regularizer is chosen appropriately, we show that this choice can be used in the generalized implicit FTRL too and it cannot be worse than using \(\boldsymbol{g}_t\).

6 Going Beyond Subgradients with aProx↩︎

Till now, in all the updates we have considered \(\boldsymbol{z}_t\) was set to be a subgradient of \(\ell_t\) in a specific point. In this section, we show that we can go beyond this idea.

[15] introduced aProx updates, that is proximal updates on surrogate loss functions. In particular, they used truncated linear lower bounds to the loss functions as surrogate functions. These simple surrogates are motivated by the fact that they are strictly better than linear approximation and at the same time they allow writing the proximal update in a closed form. Moreover, they showed empirically that in certain situations the performance of the algorithms becomes much more resistant to the tuning of the stepsizes.

One might just use the same truncated lower bounds in implicit FTRL, but it would not be clear why this should give any advantage in the theoretical bound. Indeed, even in [15] it is not completely clear what part of the theory tells us that we should expect a better performance from these updates.

Here, we show how the updates in the generalized implicit FTRL are actually a generalization of the aProx ones. In particular, we generalize the aProx updates to arbitrary regularizers and show that all of them satisfy \(H_t(\boldsymbol{z}_t)\leq H_t(\boldsymbol{g}_t)\) and \(H'_t(\boldsymbol{z}_t)\leq H'_t(\boldsymbol{g}_t)\). In words, the aProx updates are guaranteed to be at least as good as the subgradient \(\boldsymbol{g}_t\) in minimizing the worst-case regret.

In order to consider truncated linear lower bounds to the functions \(\ell_t\), in this section we will assume that the loss functions \(\ell_t\) are lower bounded. Given that the regret is invariant to additive constants in the losses, without loss of generality we can assume the lower bound to be 0 for all the loss functions. Hence, define the truncated linear model \(\hat{\ell}_t:V\to \mathbb{R}\) around \(\boldsymbol{x}_t\) to be \[\hat{\ell}_t(\boldsymbol{x}) \triangleq \max(\ell_t(\boldsymbol{x}_t)+ \langle \boldsymbol{g}_t, \boldsymbol{x}- \boldsymbol{x}_t\rangle,0),\] where \(\boldsymbol{g}_t \in \partial \ell_t(\boldsymbol{x}_t)\). For brevity of notation, our notation does not stress the fact that the truncated linear model depends on \(\boldsymbol{x}_t\) and the specific subgradient \(\boldsymbol{g}_t\).

To idea to extend aProx to the case of generalized implicit FTRL, we use the truncated linear lower bound in the update of \(\boldsymbol{z}_t\). So, we define \[\label{eq:aprox95h} \boldsymbol{z}_t = \mathop{\mathrm{argmin}}_{\boldsymbol{z}} \;\psi^\star_{t+1,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}_t) + \hat{\ell}^\star_t(\boldsymbol{z}_t)\tag{11}\] or \[\label{eq:aprox95hprime} \boldsymbol{z}_t=\mathop{\mathrm{argmin}}_{\boldsymbol{z}} \;\psi^\star_{t,V}(\boldsymbol{\theta}_{t}-\boldsymbol{z}_t) + \hat{\ell}^\star_t(\boldsymbol{z}_t)~.\tag{12}\]

We can also immediately write closed form updates for generalized implicit FTRL with regularizer \(\psi_t(\boldsymbol{x})=\frac{\lambda_t}{2}\|\boldsymbol{x}\|^2\), that mirror the ones of aProx. The proof is in Section 11.

7 Empirical Evaluation↩︎

As we said, in the worst case scenario any kind of implicit update cannot give any advantage over the usual updates. However, in practice it is well-known that things are vastly different. Hence, in this section, we compare the performance of different choices of \(\boldsymbol{z}_t\) in Algorithm 1 when \(\psi_t(\boldsymbol{x})=\frac{\lambda_t}{2}\|\boldsymbol{x}\|_2^2\). In particular, we consider:

• FTRL with linearized losses (Linear): \(\boldsymbol{z}_t=\boldsymbol{g}_t\);

• Implicit FTRL with aProx updates (Trunc): \(\boldsymbol{z}_t = \min\left\{ 1,\frac{\lambda_t \ell_t(\boldsymbol{x}_t)}{\| \boldsymbol{g}_t\|^2}\right\}\boldsymbol{g}_t\);

• Implicit FTRL with two-step updates (Twostep): \(\boldsymbol{z}_t = \partial \ell_t(\boldsymbol{x}_t - \boldsymbol{g}_t/\lambda_t)\);

• Implicit FTRL with 6 when the proximal operator has a closed form (Proximal).

We adopt the choice of \(\lambda_t\) from Corollary 5.

We conduct linear prediction experiments on datasets from LibSVM [36]. We show here experiments on classification tasks using the hinge loss and the logistic loss, and regression tasks with absolute loss. We normalize the datasets and added a constant bias term to the features. Given that in the online learning setting, we do not have the training data and validation data to tune the \(\beta\), we will plot the averaged loss, \(\frac{1}{t}\sum_{i=1}^t \ell_i(\boldsymbol{x}_i)\), versus different choice of \(\beta\), that at the same time show the algorithms’ sensitivity to the hyperparameter \(\beta\) and their best achievable performance. We consider \(\beta \in [10^{-3},10^3]\) for hinge loss and logistic loss, and \(\beta \in [10^{-3},10^8]\) for the absolute loss. Each algorithm is run 15 times, we plot the average of the averaged losses and the \(95\%\) confidence interval. Note that the confidence intervals so small to be invisible, but for the larger values of the \(\beta\) for the Linear updates.

Figure 2 and Figure 3 show the averaged loss versus different selections of hyperparameter \(\beta\) for classification tasks with hinge loss and logistic loss respectively. Note that with the hinge loss aProx updates and proximal updates are completely equivalent. In all experiments, FTRL with linearized updates is more sensitive to the setting of \(\beta\), and its performance is almost uniformly worse than all the other generalized implicit updates. This is in line with previous results in [15] in the offline setting. With the logistic loss, the proximal operator does not have a closed-form solution. In all the classification experiments, the performance of generalized implicit FTRL with two-step updates seems remarkable and a possible viable alternative to aProx. The confidence intervals for all implicit updates have a width smaller than 0.01, making them too narrow to be visible in the figures. In contrast, when using hinge loss, the performance of FTRL with linear models exhibits significant fluctuations across different repetitions when a large learning rate is used. This observation provides evidence supporting our assertion that the selection of hyperparameter \(\beta\) greatly affects the performance of FTRL with linear models, while implicit updates demonstrate robustness.

Figure 4 shows that FTRL with linearized updates is very sensitive to the choice of the hyperparameter \(\beta\), while the implicit FTRL updates are robust. Again, Implicit FTRL with two-step updates achieves essentially the best performance. The confidence intervals in the regression tasks lead to a similar conclusion as in the classification tasks.

8 Conclusion and Future Work↩︎

In this work, we propose a new framework: generalized implicit Follow-the-Regularized-Leader. We show that generalized implicit FTRL can not only recover known algorithms, e.g., implicit FTRL and FTRL with linearized losses, but it also provides a theoretical guideline to design new algorithms, such as the extensions of aProx and Mirror-Prox. Indeed, we believe that the main contribution of our work lies precisely in the fact that it provides a unifying framework that is general, flexible, and theoretically grounded.

In the future, we plan to explore further this framework designing new \(\boldsymbol{z}_t\) with low computational complexity. This is a promising direction because the two-steps update seems to be already a valid alternative to the aProx updates, even if it comes at the computational expense of querying an additional gradient in each round.

Acknowledgements↩︎

We thank Alex Shtoff for discussion and feedback on a preliminary version of this paper. Francesco Orabona is supported by the National Science Foundation under the grants no. 2022446 “Foundations of Data Science Institute” and no. 2046096 “CAREER: Parameter-free Optimization Algorithms for Machine Learning”.

9 Update Rule for Common Losses↩︎

In this section, we report the proximal operator of common losses for easy referencing. These formulas are well-known and they can be found, for example, in [37], [38].

\[\begin{align} \ell_t(\boldsymbol{x})=\max(1-y_t \langle \boldsymbol{s}_t, \boldsymbol{x}\rangle,0) &\Rightarrow \mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda}}(\boldsymbol{x})=\boldsymbol{x}+\min\left(\frac{1}{\lambda}, \frac{\max(1-y_t \langle \boldsymbol{s}_t, \boldsymbol{x}\rangle,0)}{\|\boldsymbol{s}_t\|^2}\right) y_t \boldsymbol{s}_t\\ \ell_t(\boldsymbol{x})=|\langle \boldsymbol{s}_t, \boldsymbol{x}\rangle-y_t| &\Rightarrow \mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda}}(\boldsymbol{x})=\boldsymbol{x}-\min\left(\frac{1}{\lambda}, \frac{|\langle \boldsymbol{s}_t, \boldsymbol{x}\rangle-y_t|}{\|\boldsymbol{s}_t\|^2}\right) \boldsymbol{s}_t\\ \ell_t(\boldsymbol{x})=\frac{1}{2}(\langle \boldsymbol{s}_t,\boldsymbol{x}\rangle - y_t)^2 &\Rightarrow \mathop{\mathrm{Prox}}_{\frac{\ell_t}{\lambda}}(\boldsymbol{x})=\boldsymbol{x}-\frac{(\langle \boldsymbol{s}_t, \boldsymbol{x}\rangle-y_t) \boldsymbol{s}_t}{\lambda+ \|\boldsymbol{s}_t\|_2^2}~. \end{align}\]

10 Proof of Corollary 5↩︎

11 Proof of Corollary 8↩︎

References↩︎