Adaptive scale-invariant online algorithms for learning linear models

Introduction

The problem described above becomes apparent if we make an analogy from physics and imagine that all features have physical units. In particular, if we assigned a unit $\bm{[}x_{i}\bm{]}$ to feature $i$, and assumed for simplicity that the prediction and the label are unitless (as in, e.g., classification), the corresponding coordinate of the weight vector would need to have unit $1/\bm{[}x_{i}\bm{]}$. However, the units in the OGD update (1) are mismatched, because $\nabla_{t,i}$ has unit $\bm{[}x_{i}\bm{]}$ (as $\nabla_{t}$ is proportional to $\bm{x}_{t}$), while $w_{t,i}$ has unit $1/\bm{[}x_{i}\bm{]}$; even assigning a unit to $\eta$ does not help as a single number cannot compensate different units. A reasonable solution to this “unit clash” problem is to use one learning rate per dimension, i.e. to modify (1) to:

If we choose the oracle tuning of the learning rates to minimize the regret against comparator $\bm{u}$, it follows that $\eta_{i}^{*}=|u_{i}|/\sqrt{\sum_{t}\nabla_{t,i}^{2}}$ which results in the regret bound of order $\sum_{i}|u_{i}|\sqrt{\sum_{t}\nabla_{t,i}^{2}}$, better than the bound obtained with a single learning rate. Interestingly, the unit of $\eta_{i}^{*}$ becomes $1/[x_{i}]^{2}$, which fixes the “unit clash” in (2) and makes the scaling issues go away (as now scaling the $i$-the feature by any factor $c$ will be compensated by scaling down $u_{i}$ by $c^{-1}$). Unfortunately, it is infeasible in practice to separately tune a single learning rate per dimension (oracle tuning requires the knowledge the comparator and all future gradients).

The first algorithm achieves a regret bound which depends on instances only relative to the scale of the comparator, through products of the form $|u|_{i}\sqrt{\max_{t}|x_{t,i}|^{2}+\sum_{t}\nabla_{t,i}^{2}}$ for $i=1,\ldots,d$, similarly as in the bound of OGD with per-dimension learning rates (with additional maximum over feature values, which is usually much smaller than the sum over squared gradients). As the algorithm can be sometimes a bit conservative in its predictions, we also introduce a second algorithm which is more aggressive in decreasing its cumulative loss; the price to pay is a regret bound which mildly (logarithmically) depends on ratios between the largest and the first non-zero input value for each coordinate. While these quantities can be made arbitrarily large in the worst case, it is unlikely to happen in practice. We test both algorithms in a computational study on several real-life data sets and show that without any need to tune parameters, they are competitive to popular online learning methods, which are allowed to tune their learning rates to optimize the test set performance.

Related work.

Our work is rooted from a long line of research on regret minimizing online algorithms (Cesa-Bianchi et al., 1996; Kivinen & Warmuth, 1997; Cesa-Bianchi & Lugosi, 2006). Most of the proposed methods have “range factors” present both in the algorithm and in the bound: it is typically assumed that some prior knowledge on the range of the comparator and the gradients is given, which allows the algorithm to tune its parameters appropriately. For instance, assuming $\|\bm{u}\|\leq U$ and $\|\nabla_{t}\|\leq G$ for all $t$, OGD (1) with learning rate $\eta=U/(G\sqrt{T})$ achieves $O(UG\sqrt{T})$ regret bound.

More recent work on adaptive algorithms aims to get rid of these range factors. In particular, with a prior bound on the comparator norm, it is possible to adapt to the unknown range of the gradients (Duchi et al., 2011; Orabona & Pál, 2015), whereas having a prior bound on all future gradients, one can adapt to the unknown norm of the comparator (Streeter & McMahan, 2012; McMahan & Abernethy, 2013; Orabona, 2014; Orabona & Pál, 2016; Orabona & Tommasi, 2017; Cutkosky & Orabona, 2018). In particular, using reduction methods proposed by Cutkosky & Orabona (2018), one can get a bound matching OGD with separate learning rate per dimension, but this requires to know $\max_{t,i}|\nabla_{t,i}|$ in advance. Interestingly, Cutkosky & Boahen (2017) have shown that in online convex optimization it is not possible to adapt to both unknown gradient range and unknown comparator norm at the same time. Here, we circumvent this negative result by exploiting the fact that the input instance $\bm{x}_{t}$ is available ahead of prediction and therefore can be used to construct $\widehat{y}_{t}$ (this idea was first discovered in the context of linear regression (Vovk, 2001; Azoury & Warmuth, 2001)).

Scale-invariant algorithm has been been studied by Ross et al. (2013); Orabona et al. (2015) in a setup very similar to ours. Their algorithms, however, require a prior knowledge on the largest per-coordinate comparator’s prediction, $\max_{t,i}|u_{i}x_{t,i}|$, whereas their bounds scale with relative ratios between the largest and the first non-zero input value for each coordinate (the bound of our second algorithm also depends on these quantities but only in a logarithmic way). Luo et al. (2016); Koren & Livni (2017) considered even a more general setup of invariance under linear transformation of features (of which our invariance is a special case if the transformation is diagonal), but a prior knowledge of $\max_{t}|\bm{x}_{t}^{\top}\bm{u}|$ must be available, and the resulting algorithms are second-order methods. The closest to our work are the results by Kotłowski (2017), which concern the same setup, general invariance under linear transformations, and, similarly to us, make no prior range assumptions. Their bounds, however, do not scale with gradients $\nabla_{t,i}^{2}$ (as in the optimal OGD bound), but with the size of the features $x_{t,i}^{2}$ (multiplied by the Lipschitz constant of the loss), which upper-bounds $\nabla_{t,i}^{2}$ and can become much larger. For instance, in the “noise-free” case, when some comparator $\bm{u}$ has zero loss, the algorithm playing sufficiently close to $\bm{u}$ can inflict arbitrarily small gradients, while the sum of squared feature values will still grow linearly in $t$.

The goal of scale-invariance seems to go hand in hand with a requirement for the updates to avoid unit clashes and this connection was the motivating idea for our work. In the most basic case, assume you want to design online algorithms for linear regression

that are to be robust to scaling the input vectors $\bm{x}_{t}$ by a single positive constant factor. In this case $\bm{[}\eta\bm{]}$ should be $1/\bm{[}\|\bm{x}_{t}\|^{2}\bm{]}$. Interestingly enough, good tunings of the learning rates $\eta$ often “fix the units”: the properly tuned learning rates for the linear regression updates employed in (Cesa-Bianchi et al., 1996; Kivinen & Warmuth, 1997) have units $1/\bm{[}\|\bm{x}_{t}\|^{2}\bm{]}$. In this paper we focus on robustness to independently scaling the individual components $x_{t,i}$ of the input vectors by positive factors. This requires privatized learning rates $\eta_{i}$ with the property that $\bm{[}\eta_{i}\bm{]}=1/\bm{[}x_{t,i}\bm{]}^{2}$. Our paper focuses on this case because of efficiency concerns. However there is a third case (more expensive) where we want robustness to independent scaling and rotation of the input vectors $\bm{x}_{t}$. Now $\bm{\eta}$ must be a matrix parameter (playing a similar role to a Hessian) and if the instances are pre-multiplied by a fixed invertible $\bm{A}$, then the tuned learning rate matrix of the new instances must become $\bm{\eta}\bm{A}^{-1}$, thus correcting for the pre-multiplication with $\bm{A}$. The updates of Luo et al. (2016); Koren & Livni (2017); Kotłowski (2017), as well as the Newton algorithm, have this form, but they are all second order algorithms with runtime of at least $O(d^{2})$ per trial.

Problem Setting

Consider running Online Gradient Descent (OGD) algorithm on this problem, as defined in (2), i.e. we let the algorithm have a separate learning rate per dimension. When initialized at $\bm{w}_{1}=\bm{0}$, OGD achieves the regret bound:

where we introduced $S^{2}_{t,i}=\sum_{j\leq t}\nabla_{j,i}^{2}=\sum_{j\leq t}(g_{j}x_{j,i})^{2}$. This is a slight generalization of a standard textbook bound (see, e.g., Hazan, 2015), proven in Appendix A for completeness. Tuning the learning rates to minimize the bound results in $\eta_{i}=\frac{|u_{i}|}{S_{t,i}}$, and the bound simply becomes:

Such tuning is, however, not directly feasible as it would require knowing the comparator and the future gradients in hindsight. The goal of this work is to design adaptive online algorithms which for any comparator $\bm{u}$, and any data sequence $\{(\bm{x}_{t},y_{t})\}_{t=1}^{T}$, without any prior knowledge on their magnitudes, achieve (4) up to logarithmic factors.

The invariance of predictions of the optimal comparator leads to the definition of scale-invariant algorithms. We call a learning algorithm scale-invariant if its behavior (sequence of predictions) is invariant under arbitrary rescaling of individual features (Ross et al., 2013; Kotłowski, 2017). More precisely, if we apply a transformation $x_{t,i}\mapsto a_{i}x_{t,i}$ simultaneously to all instances, the predictions of the algorithm $\widehat{y}_{1},\ldots,\widehat{y}_{T}$ remain the same as on the original data sequence. Scale-invariant algorithm are thus independent on the “units” in which the instance vectors are expressed on each feature, and do not require any prior normalization of the data. Interestingly, OGD defined in (2) is not a scale invariant algorithm, but becomes one under the optimal tuning of its learning rates. The algorithms presented in the next section will turn out to be scale-invariant, essentially as a by-product of adaptiveness to arbitrary scale of the comparator and the instances, required to achieve (4).

Remark: As noted in the introduction, scale invariance can be generalized to arbitrary linear invertible transformations $\bm{x}_{t}\mapsto\bm{A}\bm{x}_{t}$. Unfortunately, this leads to second-order algorithms (Luo et al., 2016; Koren & Livni, 2017; Kotłowski, 2017), with the complexity at least $\Theta(d^{2})$ per trial.

Scale-invariant algorithms

We first briefly describe the motivating idea behind the construction of the algorithms. We start with rewriting the right hand side of (3) to get:

Now, the key idea is to note that the bound must hold for any comparator $u_{i}$, therefore it must hold if we take a supremum over $u_{i}$ on the left-hand side, $\sup_{u_{i}}\{G_{T,i}u_{i}-B(u_{i}S_{T,i})\}$. To evaluate this supremum, we note that under variable change $x=u_{i}S_{T,i}$ it becomes equivalent to $\sup_{x}\{G_{T,i}/S_{T,i}x-B(x)\}$. Recalling the definition of the Fenchel conjugate of a function $f(x)$, defined as $f^{*}(\theta)=\sup_{x}\{\theta x-f(x)\}$ (Boyd & Vandenberghe, 2004), we see that the supremum can be evaluated to $B^{*}(G_{T,i}/S_{T,i})$. Thus, the unknown comparator has been eliminated from the picture, and the algorithm can be designed to satisfy:

for every data sequence. In fact, we construct our algorithms by proceeding in the reverse direction: starting with an appropriate function $\psi$ playing the role of $B^{*}$ (which we call a potential) and getting bound expressed by means of its conjugate $\psi^{*}$. What we just described is known as regret-reward duality and has been successfully used in adaptive online learning (Streeter & McMahan, 2012; McMahan & Orabona, 2014; Orabona & Pál, 2016).

As already briefly mentioned, achieving (4), which corresponds to a bound with $B(x)=|x|$, is actually not possible: a negative result by Streeter & McMahan (2012) implies that the best one can hope for is $B(x)=O(|x|\sqrt{\ln(|x|)})$. We will show that our algorithm achieve a bound of a slightly weaker form $B(x)=O(|x|\ln(|x|))$, but still giving only a logarithmic overhead comparing to (4).

Algorithms.

ScInOL1.

where $\delta_{t,i}$ is a small additional overhead. The algorithm resembles FreeRex by (Cutkosky & Boahen, 2017), because it actually uses the same functional form of the potential. The choice of the weight looks almost like a derivative of a potential function $\psi_{t-1,i}(x)$ at $x=G_{t-1,i}$, but it differs slightly in using $M_{t,i}$ rather than $M_{t-1,i}$ in its definition. This prior update of $M_{t,i}$ let the algorithm account for potentially very large value of $x_{t,i}$ and avoid incurring too much loss. The coefficients $\beta_{t,i}$ multiplying the potential are chosen to be a nonincreasing sequence, which at the same time keeps the overhead $\delta_{t}$ upper-bounded by $\frac{\epsilon}{t}$, in order to to avoid terms in the regret bound depending on ratios between feature values and get $\sum_{t}\delta_{t,i}\leq\epsilon(1+\ln T)$. Summing (5) over trials and using using $\psi_{0,i}(G_{0})=0$ gives:

Using the convexity of $\psi_{T+1,i}$ we can rewrite it by means of its Fenchel conjugate, $\psi_{T+1,i}(G_{T,i})=\sup_{u}\{G_{T,i}u-\psi^{*}_{T+1,i}(u)\}$, which in turn can be bounded as:

Summing over features $i=1,\ldots,d$, bounding $\beta_{T,i}\geq(\epsilon T)^{-1}$, and using (3) gives:

The full proof of Theorem 3.1 is given in Appendix C. Note that the bound depends on the scales of the features only relative to the comparator weights $\bm{u}$ through quantities $|u_{i}|\hat{S}_{T,i}$, and is equivalent to the optimal OGD bound (4) up to logarithmic factors.

ScInOL2.

The algorithm described in the previous section is designed to achieve a regret bound which depends on instances only relative to the scale of the comparator, no matter how extreme are the ratios $|x_{t,i}|/M_{t-1,i}$ between the new inputs and previously observed maximum feature values. We have observed that this can make the behavior of the algorithm too conservative, due to guarding against the worst-case instances. Therefore we introduce a second algorithm, which is more aggressive in decreasing its cumulative loss; the price to pay is a regret bound which mildly depends on ratios between feature values. The algorithm has a multiplicative flavor and resembles a family of Coin Betting algorithms recently developed by Orabona & Pál (2016); Orabona & Tommasi (2017); Cutkosky & Orabona (2018).

The algorithm is based on a potential function $\psi_{t,i}(x)=e^{\frac{1}{2}h(x/\hat{S}_{t,i})}$, where:

Function $h(y)$ interpolates between between the quadratic (for $|y|\leq 1$) and absolute value (otherwise). It is easy to check that $h(y)\geq|y|-\frac{1}{2}$ for all $y$.

By the definition, $\eta_{t,i}=\epsilon-\sum_{j\leq t}g_{t}x_{t,i}w_{t,i}$ is (up to $\epsilon$) the cumulative negative loss of the algorithm (“reward”). The weights are chosen in order to guarantee the relative increase in the reward lower-bounded by the relative increase in the potential:

where $\delta_{t,i}$ is an overhead which can be controlled. Taking the product over trials $t=1,\ldots,T$ and using $\psi_{0,i}(G_{0,i})=1$ gives $\eta_{T}\geq\epsilon\psi_{T,i}(G_{T,i})e^{-\Delta_{T}}$, where $\Delta_{T,i}=\sum_{t}\delta_{t,i}$. Using the definition of $\eta_{T,i}$, this translates to:

where we used $h(y)\geq|y|-\frac{1}{2}$. Denote the function on the r.h.s. by $f(x)=\epsilon e^{-\Delta_{T,i}-\frac{1}{4}}e^{|x|/(2\hat{S}_{T,i})}$. Using convexity of $f(x)$, we can express it by means of its Fenchel conjugate, $f(G_{T,i})=\sup_{u}\{G_{T,i}u-f^{*}(u)\}$, for which we have the following bound (Orabona, 2013):

Unfortunately, it turns out that $\Delta_{T,i}$ can be $\Omega(T)$ in the worst case, which makes the bound linear in $T$. We can, however, bound $\Delta_{T,i}$ in a data-dependent way by:

where $\tau_{i}$ is the first trial in which $|x_{t,i}|\neq 0$. As $\hat{S}^{2}_{T,i}\leq(T+1)\max_{t}x_{t,i}^{2}$, the bound involves the ratio between the largest and the first non-zero input value. While being vacuous in the worst case, this quantity is likely not to be excessively large for non-adversarial data encountered in practice, and it is moreover hidden under the logarithm in the bound (a similar quantity is analyzed by Ross et al. (2013), where its magnitude is bounded with high probability for data received in a random order). Following along the steps from the previous section, we end up with the following bound:

where $\hat{S}_{T,i}=\sqrt{S_{T,i}^{2}+M_{T,i}^{2}}$ and $\tau_{i}=\min\{t\colon|x_{t,i}|\neq 0\}$.

The proof of Theorem 3.2 is given in Appendix D.

Experiments

The algorithms were trained by minimizing the logistic loss (cross entropy loss) in an online fashion. Following similar experiments in the past papers concerning online methods (Kingma & Ba, 2014; Ross et al., 2013; Orabona & Tommasi, 2017), we report the average loss on the test set (after every 50 iterations) rather than the regret. We tested the following algorithms: OGD with learning rate decaying as $\eta_{t}=\eta/\sqrt{t}$ (called SGD here from stochastic gradient descent), AdaGrad (Duchi et al., 2011), Adam (Kingma & Ba, 2014), two scale-invariant algorithms from past work: NAG (Normalized Adaptive Gradient) (Ross et al., 2013) and Scale-free Mirror Descent by Orabona et al. (2015) (SFMD), and algorithms from this work. All algorithms except ours have a learning rate parameter, which in each case was set to values from $\{0.001,0.005,0.01,0.05,0.1,0.5,1,5,10\}$ (results concerning all learning rates were reported). We implemented our algorithms in Tensorflow and used existing implementations whenever it was possible.

Figure 1 shows average cross entropy measured on test set as a function of the number of iterations. Lines of the same color show results for the same algorithm but with different learning rates. Figure 1(a) uses logarithmic scale for $y$ axis: note the extreme values of the loss for most of the non-invariant algorithms. In fact, the two black dashed lines mark the loss achieved by the best possible model $\bm{u}$ (lower line) and a model with zero weight vector (upper line), so that every method above the upper dashed line does something worse than such a trivial baseline. Figure 1(b) shows only the fragment between dashed lines using linear scale for $y$ axis.

The results clearly show that algorithms which are not invariant to feature scales (SGD, Adam, and AdaGrad) are unable to achieve any reasonable result for any choice of the learning rate (most of the time performing much worse than the zero vector). This is because a single learning rate is unable to compensate all feature scales at the same time. The scale invariant algorithms, NAG and SFMD, perform much better (achieving the best overall results), but their behavior still depends on the learning rate tuning. Among our algorithms, ScInOL1 slowly decreases its loss moving away from the initial zero solution, but it is clearly too slow in this problem. On the other hand, ScInOL2 was able to achieve descent results without any tuning at all.

2 Linear Classification

To further check empirical performance of our algorithms we tested them on some popular real-life benchmark datasets. We chose 5 datasets with varying levels of feature scale variance from UCI repository (Dheeru & Karra Taniskidou, 2017) (Covertype, Census, Shuttle, Bank, Madelon) and a popular benchmark dataset MNIST (LeCun & Cortes, 2010). For all datasets, categorical features were one-hot-encoded into multiple features and missing values were replaced by dedicated substitute features. Datasets that do not provide separate testing sets were split randomly into training/test sets ($2/1$ ratio). Short summary of datasets can be found in Appendix E.

Algorithms were trained by minimizing the cross entropy loss in an online fashion. Some of the data sets concern multiclass classification, which is beyond the framework considered here, as it would require multivariate prediction $\widehat{\bm{y}}=(\widehat{y}_{1},\ldots,\widehat{y}_{K})$ for each of $K$ classes, but it is straightforward to extend our setup to such multivariate case (details are given in Appendix G). To gain more insight into the long-term behavior of the algorithms, we trained all algorithms for multiple epochs. Each epoch consisted of running through the entire training set (shuffled) and testing average cross entropy and accuracy on the test set. Each algorithm was run 10 times for stability. We compared our algorithms with the following methods: SGD (with $\eta_{t}\sim 1/\sqrt{t}$), AdaGrad, Adam, NAG, CoCoB (Orabona & Tommasi, 2017) (an adaptive parameter-free algorithm; we used its Tensorflow implementation), and Algorithm 1 (coordinate-wise scale invariant method) by Kotłowski (2017) (which we call Alg1-K17). The algorithms using hand-picked learning rates (SGD, AdaGrad, Adam, NAG) were run with values from $\{0.00001,0.0001,0.001,0.01,0.1,1.0\}$ (all other parameters were kept default), and only the best test set results were reported (note that this biases the results in favour of these algorithms).

Figure 2 shows mean (test set) cross entropy loss (classification accuracy, given in Appendix F, leads to essentially the same conclusions); shaded areas around each curve depicts $\pm$ one standard deviation (over different runs). All graphs start with the error measured after the first epoch for better readability. The most noticeable fact in the plots is comparatively high variance (between different runs) of SGD, AdaGrad, Adam and NAG, i.e. the approaches with tunable learning rate. They also often performed worse than the remaining algorithms. Among our methods, ScInOL2 turned out to perform better than ScInOL1 in every case, due to its more aggressive updates. Note, however, that both algorithms are surprisingly stable, exhibiting very small variance in their performance across different runs. The best performance was most of the time achieved by either ScInOL2 or CoCoB. Alg1-K17 was often converging somewhat slower (which is most pronounced for MNIST data), which we believe is due to its very conservative update policy.

Conclusions and future work

We proposed two online algorithms which behavior is invariant under arbitrary rescaling of individual features. The algorithms do not require any prior knowledge on the scale of the instances or the comparator and achieve, without any parameter tuning, regret bounds which match (up to a logarithmic factor) the regret bound of Online Gradient Descent with optimally tuned separate learning rates per dimension. The algorithms run in $O(d)$ per trial, which is comparable to the runtime of vanilla OGD.

The framework considered in this paper concerns well-understood and relatively simple linear models with convex objectives. It would be interesting to evaluate the importance of scale-invariance for deep learning methods, comprised of multiple layers connected by non-linear activation functions. As scale-invariance leads to well-conditioned algorithms, we believe that it could not only avoid the need for prior normalization of the inputs to the network, but it would also make the algorithm be independent of the scale of the inputs fed forward to the next layers. A scale-invariant update for neural nets might be robust against the “internal covariance shift” phenomenon (Ioffe & Szegedy, 2015) and avoid the need for batch normalization.

Finally, the potential functions we use to analyze our updates seems closely related to the potential function of EGU± (Kivinen & Warmuth, 1997). It may be that our tuned online updates are simply approximation of (a version of) EGU± and this needs further investigation.

Acknowledgements

M. Kempka and W. Kotłowski were supported by the Polish National Science Centre under grant No. 2016/22/E/ST6/00299. Part of this work was done while M. K. Warmuth was at UC Santa Cruz, supported by NSF grant IIS-1619271.

References

Appendix A Bound for Online Gradient Descent with per-dimension learning rates

We remind the update of OGD with per-dimension learning rates:

Summing over trials $t=1,\ldots,T$ and rearranging:

Dividing by $2\eta_{i}$, upper bounding and summing over $i=1,\ldots,d$:

Finally, using (3) shows that the right-hand side of the above upper bounds the regret.

Appendix B Scale invariance of Algorithm 1 and Algorithm 2

so that $x_{t,i}w_{t,i}\mapsto x_{t,i}w_{t,i}$ and thus $\widehat{y}_{t}=\bm{x}_{t}^{\top}\bm{w}_{t}$ is invariant under the scale transformation.

Appendix C Proof of Theorem 3.1

Before proving the theorem, we need two auxiliary results:

Let $f(x)=\alpha\left(e^{|x|/\gamma}-|x|/\gamma-1\right)$ with $\alpha,\gamma>0$. Its Fenchel conjugate is given by:

Note that since $f(x)$ is symmetric in $x$,

Setting the derivative of $g(x)$ to zero gives its unconstrained maximizer $x^{*}=\gamma\ln(1+|u|\gamma/\alpha)$, and since $x^{*}\geq 0$, it is also the maximizer of $g(x)$ under constraint $x\geq 0$. Thus:

The inequality in the lemma follows from an elementary inequality $\ln(1+x)\leq x$ applied to $\alpha\ln(1+|u|\gamma/\alpha)$. ∎

It suffices to prove the lemma for $v\geq 0$. Indeed, the inequality holds for some $v\geq 0$ and $q\in$ if and only if it holds for $-v$ and $-q$. Denote:

In this notation and with the assumption $v\geq 0$, the inequality translates to:

We will split the proof into three sub-cases: (i) $q\geq v$, (ii) $q\leq v\leq 3$, and (iii) $v\geq 3$. Since $q\leq 1$, these cases cover all allowed values of $v$ and $q$.

We have $\widetilde{v}=\frac{q-v}{\sqrt{1+q^{2}}}\leq q-v$. Since the function $e^{x}-x$ is increasing in $x$ for $x\in(1,\infty)$, it holds:

From $q\leq 1$ and $v\geq 0$ it follows $\frac{q-2v}{2}\leq\frac{1-2v}{2}\leq\frac{1}{2}$. Since function $f(x)=\frac{e^{x}-x-1}{x^{2}}$ is nondecreasing in $x$ (see, e.g., (Cesa-Bianchi & Lugosi, 2006), Section A.1.2), we have:

Thus, we bound $e^{\frac{q-2v}{2}}$ by $1+\frac{q-2v}{2}+0.15(q-2v)^{2}$ and get:

where the last inequality follows from the fact that $v\leq 1$ (as $q\geq v$ and $q\leq 1$), which by (9) implies $e^{\frac{v}{2}}\leq 1+\frac{v}{2}+0.6\frac{v^{2}}{4}=1+0.5v+0.15v^{2}\leq 1+v$, and furthermore $0.15e^{\frac{v}{2}}\leq 0.15e^{\frac{1}{2}}\leq\frac{1}{4}$. But $v(q-v)+\frac{1}{4}(q-2v)^{2}=\frac{1}{4}q^{2}\leq q^{2}$, which proves (8) for $q\geq v$.

Case (ii): q≤v≤3𝑞𝑣3q\leq v\leq 3.

We have $\widetilde{v}=\frac{v-q}{\sqrt{1+q^{2}}}\leq v-q$, and by the monotonicity of function $e^{x}-x$ for $x\in(1,\infty)$:

Using (9) and $q\geq-1$, we bound $e^{-q/2}\leq 1-\frac{q}{2}+0.15q^{2}$ to get:

Using $0.15e^{\frac{v}{2}}\leq 0.15e^{\frac{3}{2}}\leq 0.68\leq 1$ proves (8) for $q\leq v\leq 3$.

Case (iii): v>3𝑣3v>3.

We lower-bound the right-hand side of (8):

where the first inequality is simply from $q^{2}\geq\frac{q^{2}}{4}$, while the second follows from $1-x\geq e^{-x-x^{2}}$ for $x\leq\frac{1}{2}$ (see, .e.g., (Cesa-Bianchi & Lugosi, 2006), Lemma 2.4). Now, using the monotonicity of function $e^{x}-x$,

thus it suffices to show the latter to finish the proof. We have:

Using elementary inequality $\sqrt{1+x}\leq 1+\frac{x}{2}$, we have: $\frac{1}{\sqrt{1+q^{2}}}=\frac{\sqrt{1+q^{2}}}{1+q^{2}}\leq\frac{1+q^{2}/2}{1+q^{2}}$, and thus:

This shows that $v-q-\frac{q^{2}}{2}\geq\widetilde{v}$ and thus proves (9) for $v>3$. ∎

Before we state the next result, we summarize the notation which will be used in what follows. For any $i=1,\ldots,d$ and any $t=1,\ldots,T$, let:

be, respectively, the maximum input value, the negative cumulative gradient, and the sum of squared gradients at $i$-th coordinate up to (and including) trial $t$, and we also denote $M_{0,i}=G_{0,i}=S^{2}_{0,i}=0$. Moreover, define:

with $\beta_{1,i}=\epsilon$. The weight vector at trial $t$ is given by:

as long as $M_{t,i}>0$; if $M_{t,i}=0$ (which means that $x_{j,i}=0$ for all $j\leq t$), we set $w_{t,i}=0$, but any other value of $w_{t,i}$ would lead to the same loss. Finally, define $\hat{S}^{2}_{t,i}=S^{2}_{t,i}+M^{2}_{t,i}$.

For any $i=1,\ldots,d$ and any $t=1,\ldots,T$ we have:

Fix $i\in\{1,\ldots,d\}$, and let $\tau_{i}$ be the first trial $t$ such that $x_{t,i}\neq 0$. This means that $\hat{S}_{t,i}=x_{t,i}=0$ for all $t<\tau_{i}$, and the inequality is trivially satisfied for any $t<\tau_{i}$, as the left-hand side is zero, while the right-hand side is $\epsilon/t$. Thus, assume $t\geq\tau_{i}$.

Fix $t$ and define $v=\frac{G_{t-1,i}}{\sqrt{S_{t-1,i}^{2}+M_{t,i}^{2}}}$ and $q=\frac{g_{t}x_{t,i}}{\sqrt{S_{t-1,i}^{2}+M_{t,i}^{2}}}$. As $|q|\leq\frac{|g_{t}x_{t,i}|}{M_{t,i}}\leq\frac{|x_{t,i}|}{\max_{j\leq t}|x_{j,i}|}\leq 1$, we can apply Lemma C.2 to such $v$ and $q$, which, after subtracting $1$ and multiplying by $\beta_{t,i}$ on both sides, gives:

Using the definition of the weight vector (10) we identify the first term on the left-hand side of (11):

the second term on the left-hand side of (11) is equal to $\psi_{t,i}(G_{t,i})$. Thus, (11) can be rewritten as:

and to finish the proof, it suffices to show that the two terms on the right-hand side are upper bounded, respectively, by $\psi_{t-1,i}(G_{t-1,i})$ and $\frac{\epsilon}{t}$.

To bound $\beta_{t,i}q^{2}$ note that if $x_{t,i}=0$ then $\beta_{t,i}q^{2}=0$, whereas if $x_{t,i}\neq 0$ then by the definition of $\beta_{t,i}$:

To bound $\beta_{t,i}(e^{|v|/2}-|v|/2-1)$ by $\psi_{\tau_{i}-1,i}(G_{t-1,i})$ note that both are zero if $t=\tau_{i}$ (because $G_{\tau_{i}-1,i}=0$ and $v=0$). On the other hand, for $t>\tau_{i}$ we have:

and by the monotonicity of $f(x)=e^{x}-x-1$:

where in the last inequality we used $\beta_{t,i}\leq\beta_{t-1,i}$ (which follows from the definition) and the fact that $e^{x}-x-1\geq 0$ for all $x$. ∎

We are now ready to prove Theorem 3.1, which we restate here for convenience:

Applying Lemma (C.3) for a fixed $i\in\{1,\ldots,d\}$ and all $t=1,\ldots,T$, and summing over trials gives:

where we used $\psi_{0,i}(G_{0,i})=0$. By (3),

where in the last inequality we used Lemma C.1 for each $i$ with $\alpha=\beta_{T,i}$ and $\gamma=2\hat{S}_{T,i}$. To finish the proof, it suffices to show that $\beta_{T,i}\geq\frac{\epsilon}{T}$, which we do by induction on $t$. For $t=1$, we have by the definition $\beta_{t,i}=\epsilon$. Now, assume $\beta_{t-1,i}\geq\frac{\epsilon}{t-1}$, and we will show $\beta_{t,i}\geq\frac{\epsilon}{t}$. If $x_{t,i}=0$, $\beta_{t,i}=\beta_{t-1,i}\geq\frac{\epsilon}{t-1}>\frac{\epsilon}{t}$; on the other hand, if $x_{t,i}\neq 0$, from the definition of $\beta_{t,i}$:

where we used $S_{t-1,i}^{2}+M_{t,i}^{2}\geq M_{t,i}^{2}=\max_{j\leq t}x_{j,i}^{2}\geq x_{t,i}^{2}$. ∎

Appendix D Proof of Theorem 3.2

Similarly as in the previous section, we proceed the proof of the theorem with several auxiliary results. Define:

The lower bound in (13) is clearly satisfied for $|x|<1$, while for $|x|\leq 1$ we have $h(x)-(|x|-\frac{1}{2})=\frac{1}{2}(|x|-1)^{2}\geq 0$. On the other hand, the upper bound in (13) is clearly satisfied for $|x|\leq 1$, while for $|x|>1$ we have $h(x)-\frac{1}{2}x^{2}=-\frac{1}{2}(|x|-1)^{2}\leq 0$.

Let $f(x)=\alpha e^{|x|/\gamma}$ with $\alpha,\gamma>0$. Its Fenchel conjugate $f^{*}(u)=\sup_{x}\{ux-f(x)\}$ satisfies $f^{*}(u)\leq|u|\gamma(\ln(|u|\gamma/\alpha)-1)$ for all $u$.

It suffices to prove the lemma for $v\geq 0$. Indeed, the inequality holds for some $v\geq 0$ and $q\in$ if and only if it holds for $-v$ and $-q$. Denote:

In this notation and with the assumption $v\geq 0$, the inequality translates to:

because (15) together with $q\leq 1$ and inequality $e^{-x-x^{2}}\leq 1-x$ for $x\leq\frac{1}{2}$ (see, e.g., (Cesa-Bianchi & Lugosi, 2006), Section A.1.2) implies (14).

We will split the proof of (15) into three sub-cases: (i) $v\leq 1$, (ii) $v\geq 1$ and $\widetilde{v}\geq 1$, (iii) $v\geq 1$ and $\widetilde{v}<1$.

From the definition, $h(v)=\frac{1}{2}v^{2}$ and by (13) we upper bound $h(\widetilde{v})\leq\frac{1}{2}\widetilde{v}^{2}$. Using $\widetilde{v}\leq|v-q|$ we have:

and since $\min\{v,1\}=v$, this implies (15).

Case (ii): v≥1𝑣1v\geq 1 and v~≥1~𝑣1\widetilde{v}\geq 1.

As $q\leq 1\leq v$, we have $|v-q|=v-q$, and by the definition, $h(v)=v-\frac{1}{2}$, $h(\widetilde{v})=\widetilde{v}-\frac{1}{2}$. Therefore:

where in the first inequality we used $\widetilde{v}\leq|v-q|=v-q$. As $\min\{v,1\}=1$, this implies (15).

Case (iii): v≥1𝑣1v\geq 1 and v~<1~𝑣1\widetilde{v}<1.

where the last equivalence follows from solving a quadratic inequality with respect to $v\geq 1$ for fixed $q$. We now note that function:

is convex in $v$ and hence it is maximized at the boundaries $\{1,q+\sqrt{1+q^{2}}\}$ of the allowed range of $v$. When $v=1$, we have:

so that $g(v)\leq-q-\frac{1}{2}q^{2}$ in the entire range of allowed values of $v$. As $\min\{v,1\}=1$, this implies (15). ∎

Before stating further results, we summarize the notation: for $i=1,\ldots,d$ and $t=1,\ldots,T$,

with the convention $M_{0,i}=G_{0,i}=S^{2}_{0,i}=0$ and $\eta_{0,i}=\epsilon$. As before, we also use $\hat{S}^{2}_{t,i}=S^{2}_{t,i}+M^{2}_{t,i}$. The weight vector at trial $t$ is given by:

as long as $M_{t,i}>0$; if $M_{t,i}=0$, we set $w_{t,i}=0$.

with $h(\cdot)$ defined in (12). For any $i=1,\ldots,d$, let $\tau_{i}$ be the first trial in which $x_{t,i}\neq 0$. We have for any $=1,\ldots,d$ and any $t=\tau_{i},\ldots,T$:

where $\delta_{t,i}=\frac{(g_{t}x_{t,i})^{2}}{2(S_{t-1,i}^{2}+M_{t,i}^{2})}$

Fix $i$ and $t\geq\tau_{i}$, and define $v=\frac{G_{t-1,i}}{\sqrt{S_{t-1,i}^{2}+M_{t,i}^{2}}}$ and $q=\frac{g_{t}x_{t,i}}{\sqrt{S_{t-1,i}^{2}+M_{t,i}^{2}}}$. As $|q|\leq\frac{|g_{t}x_{t,i}|}{M_{t,i}}\leq 1$, we can apply Lemma D.2 to such $v$ and $q$, which gives:

Using the definition of weight vector (16), we identify the right-hand side of (17) with $1-\frac{g_{t}x_{t,i}w_{t,i}}{\eta_{t-1,i}}=\frac{\eta_{t,i}}{\eta_{t-1,i}}$. Since $\frac{1}{2}q^{2}=\delta_{t,i}$ and $\frac{G_{t,i}}{\hat{S}_{t,i}}=\frac{v-q}{\sqrt{1+q^{2}}}$ (see the proof of Lemma C.3), we also identify the left-hand side of (17) with $\psi_{t,i}(G_{t,i})e^{-\frac{1}{2}h(v)}e^{-\delta_{t,i}}$. Hence, (17) can be rewritten as:

and thus to prove the lemma, it suffices to show:

When $t=\tau_{i}$, we have $v=0$ as well as $G_{t-1,i}=0$, and (18) holds as its both sides are equal to $1$. For $t>\tau_{i}$, (18) reduces to $h(v)\leq h(G_{t-1,i}/\hat{S}_{t-1,i})$, which holds because:

and $h(x)=h(|x|)$ is monotonic in $|x|$. ∎

We are now ready to prove Theorem 3.2, which we restate here for convenience:

where $\hat{S}_{T,i}=\sqrt{S_{T,i}^{2}+M_{T,i}^{2}}$ and $\tau_{i}=\min\{t\colon|x_{t,i}|\neq 0\}$.

Fixing $i\in\{1,\ldots,d\}$, applying Lemma (C.3) for $t=\tau_{i},\ldots,T$, and multiplying over trials gives:

where we denoted $\Delta_{T,i}=\sum_{t=\tau_{i}}^{T}\delta_{t,i}$. From the definition of $\tau_{i}$, we have $\eta_{\tau_{i}-1,i}=\epsilon$ and $\psi_{\tau_{i}-1,i}\equiv 1$. Using $\eta_{T,i}=\epsilon-\sum_{t\leq T}g_{t}x_{t,i}w_{t,i}$ we get:

where we used (12) to bound $h(x)\geq|x|-\frac{1}{2}$. By (3),

where in the last inequality we used Lemma D.1 for each $i$ with $\alpha=\epsilon e^{-\Delta_{T,i}-\frac{1}{4}}$ and $\gamma=2\hat{S}_{T,i}$. We will now show that

which, together with $2e^{1/4}\leq 3$ will finish the proof. To prove (19), we use $M_{t,i}^{2}\geq x_{t,i}^{2}\geq(g_{t}x_{t,i})^{2}=S_{t,i}^{2}-S_{t-1,i}^{2}$ to get:

Using $\frac{a-b}{a}\leq\ln\frac{a}{b}$ for any $a\geq b>0$ (which follows from the concavity of the logarithm):

where for $t=T$, we define $M_{T+1,i}=M_{T,i}$. Summing the above over trials $t=\tau_{i},\ldots,T$:

Appendix E Datasets

MNIST dataset is available at Yann Lecun’s page. All other datasets are availableat the UCI repository. Scale is computed as a ratio of highest to lowest positive $L_{2}$ norms of features.

Appendix F Experiment: classification accuracy plots

Appendix G Multivariate predictions

where $\sigma_{k}(\widehat{\bm{y}})=\frac{e^{\widehat{y}_{k}}}{\sum_{j=1}^{K}e^{\widehat{y}_{j}}}$ is the soft-max transform.

The regret decouples into a sum over individual coordinates and dimensions of the prediction vector, and the extension of our algorithms is now straightforward (see Algorithm (3) and (4) below). Also, the analysis can be carried out in full analogy to the univariate loss case resulting in the following bounds (for $L=1$):

where $\hat{S}_{T;i,k}=\sqrt{S_{T;i,k}^{2}+M_{T;i}^{2}}$.

where $\hat{S}_{T;i,k}=\sqrt{S_{T;i,k}^{2}+M_{T;i}^{2}}$ and $\tau_{i}=\min\{t\colon|x_{t,i}|\neq 0\}$.