Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning

Introduction

Stochastic Gradient Descent (SGD) algorithms are gaining more and more importance in the Machine Learning community as efficient and scalable machine learning tools. There are two possible ways to use a SGD algorithm: to optimize a batch objective function, e.g. , or to directly optimize the generalization performance of a learning algorithm, in a stochastic approximation way . The second use is the one we will consider in this paper. It allows learning over streams of data, coming Independent and Identically Distributed (IID) from a stochastic source. Moreover, it has been advocated that SGD theoretically yields the best generalization performance in a given amount of time compared to other more sophisticated optimization algorithms .

Yet, both in theory and in practice, the convergence rate of SGD for any finite training set critically depends on the step sizes used during training. In fact, often theoretical analysis assumes the use of optimal step sizes, rarely known in reality, and in practical applications wrong step sizes can result in arbitrary bad performance. While in finite hypothesis spaces simple optimal strategies are known , in infinite dimensional spaces the only attempts to solve this problem achieve convergence only in the realizable case, e.g. , or assume prior knowledge of intrinsic (and unknown) characteristic of the problem . The only known practical and theoretical way to achieve optimal rates in infinite Reproducing Kernel Hilbert Space (RKHS) is to use some form of cross-validation to select the step size that corresponds to a form of model selection [26, Chapter 7.4]. However, cross-validation techniques would result in a slower training procedure partially neglecting the advantage of the stochastic training. A notable exception is the algorithm in , that keeps the step size constant and uses the number of epochs on the training set as a regularization procedure. Yet, the number of epochs is decided through the use of a validation set .

Note that the situation is exactly the same in the batch setting where the regularization takes the role of the step size. Even in this case, optimal rates can be achieved only when the regularization is chosen in a problem dependent way .

On a parallel route, the Online Convex Optimization (OCO) literature studies the possibility to learn in a scenario where the data are not IID . It turns out that this setting is strictly more difficult than the IID one and OCO algorithms can also be used to solve the corresponding stochastic problems . The literature on OCO focuses on the adversarial nature of the problem and on various ways to achieve adaptivity to its unknown characteristics .

This paper is in between these two different worlds: We extend tools from OCO to design a novel stochastic parameter-free algorithm able to obtain optimal finite sample convergence bounds in infinite dimensional RKHS. This new algorithm, called Parameter-free STOchastic Learning (PiSTOL), has the same complexity as the plain stochastic gradient descent procedure and implicitly achieves the model selection while training, with no parameters to tune nor the need for cross-validation. The core idea is to change the step sizes over time in a data-dependent way. As far as we know, this is the first algorithm of this kind to have provable optimal convergence rates.

The rest of the paper is organized as follows. After introducing some basic notations (Sec. 2), we will explain the basic intuition of the proposed method (Sec. 3). Next, in Sec. 4 we will describe the PiSTOL algorithm and its regret bounds in the adversarial setting and in Sec. 5 we will show its convergence results in the stochastic setting. The detailed discussion of related work is deferred to Sec. 6. Finally, we show some empirical results and draw the conclusions in Sec. 7.

Problem Setting and Definitions

Let $L_{K}:\mathcal{L}^{2}_{\rho_{\mathcal{X}}}\rightarrow\mathcal{H}_{K}$ the integral operator defined by $(L_{K}f)(x)=\int_{\mathcal{X}}K(x,x^{\prime})f(x^{\prime})d\rho_{\mathcal{X}}(x^{\prime})$. There exists an orthonormal basis $\{\Phi_{1},\Phi_{2},\cdots\}$ of $\mathcal{L}^{2}_{\rho_{\mathcal{X}}}$ consisting of eigenfunctions of $L_{K}$ with corresponding non-negative eigenvalues $\{\lambda_{1},\lambda_{2},\cdots\}$ and the set $\{\lambda_{i}\}$ is finite or $\lambda_{k}\rightarrow 0$ when $k\rightarrow\infty$ [12, Theorem 4.7]. Since $K$ is a Mercer kernel, $L_{K}$ is compact and positive. Therefore, the fractional power operator $L^{\beta}_{K}$ is well defined for any $\beta\geq 0$. We indicate its range space by

A Gentle Start: ASGD, Optimal Step Sizes, and the Perceptron

On the other hand, using the tools to design self-tuning algorithms, e.g. , it may be possible to design an ASGD-like algorithm, able to self-tune its step size in a data-dependent way. Indeed, we would like an algorithm able to select the optimal step size in (3), that is

In the OCO setting, this would correspond to a regret bound of the form $\mathcal{O}(\left\|{h}\right\|_{K}T^{\frac{1}{2}})$. An algorithm that has this kind of guarantee is the Perceptron algorithm , see Algorithm 2. In fact, for the Perceptron it is possible to prove the following mistake bound :

The r.h.s of (6) has exactly the same form of the expression in (3), but with a minimum over $\eta$. Hence, we can expect it to always have the optimal rate of convergence. In the next section, we will present such algorithm.

PiSTOL: Parameter-free STOchastic Learning

In this section we describe the PiSTOL algorithm. The pseudo-code is in Algorithm 3. The algorithm builds on recent advancement in unconstrained online learning . It is very similar to a SGD algorithm , the main difference being the computation of the solution based on the past gradients, in line 4. Note that the calculation of $\left\|{g_{t}}\right\|_{K}^{2}$ can be done incrementally, hence, the computational complexity is the same as ASGD in a RKHS, Algorithm 1. For the PiSTOL algorithm we have the following regret bound.All the proofs are in Appendix.

where $\phi(x):=\frac{x}{2}\,\frac{\exp\left(\frac{x}{2}\right)\left(x+1\right)+2}{1-x\exp\left(\frac{x}{2}\right)-x}\,\left(\exp\left(\frac{x}{2}\right)\left(x+1\right)+2\right)$.

This theorem shows that PiSTOL has the right dependency on $\left\|{h}\right\|_{K}$ and $T$ that was outlined in Sec. 3 and its regret bound is also optimal up to $\sqrt{\log\log T}$ terms . Moreover, Theorem 1 improves on the results in , obtaining an almost optimal regret that depends on the sum of the absolute values of the gradients, rather than on the time $T$. This is critical to obtain a tighter bound when the losses are $H$-smooth, as shown in the next Corollary.

In the Appendix, we also show a variant of PiSTOL for linear kernels with almost optimal learning rate for each coordinate. Contrary to other similar algorithms, e.g. , it is a truly parameter-free one.

Convergence Results for PiSTOL

Setting $\alpha=\frac{q}{q+1}\in$, and $c_{\alpha}=c_{q}+1$, condition (7) is equivalent [32, Lemma 6.1] to:

It would be possible to obtain similar results with other algorithms, as the one in , using a doubling-trick approach . However, this would result most likely in an algorithm not useful in any practical application. Moreover, the doubling-trick itself would not be trivial, for example the one used in achieves a suboptimal regret and requires to start from scratch the learning over two different variables, further reducing its applicability in any real-world application.

Also, note that the guarantees of Corollary 2 and Theorem 2 hold simultaneously. Hence, the theoretical performance of PiSTOL is always better than both the ones of SGD with the step sizes tuned with the knowledge of $\beta$ or with the agnostic choice $\eta=\mathcal{O}(T^{-\frac{1}{2}})$. In the Appendix, we also show another convergence result assuming a different smoothness condition.

Regarding the optimality of our results, lower bounds for the square loss are known under assumption (2) and further assuming that the eigenvalues of $L_{K}$ have a polynomial decay, that is

Related Work

For finite dimensional spaces and self-concordant losses, an optimal parameter-free stochastic algorithm has been proposed in . However, the convergence result seems specific to finite dimension.

In the batch setting, the same optimal rates were obtained by for the square loss, in high probability, for $\beta>\frac{1}{2}$. In , using an additional assumption on the infinity norm of the functions in $\mathcal{H}_{K}$, they give high probability bounds also in the range $0<\beta\leq\frac{1}{2}$. The optimal tuning of the regularization parameter is achieved by cross-validation. Hence, we match the optimal rates of a batch algorithm, without the need to use validation methods.

In Sec. 3 we saw that the core idea to have the optimal rate was to have a classifier whose performance is close to the best regularized solution, where the regularizer is $\left\|{h}\right\|_{K}$. Changing the regularization term from the standard $\left\|{h}\right\|_{K}^{2}$ to $\left\|{h}\right\|_{K}^{q}$ with $q\geq 1$ is not new in the batch learning literature. It has been first proposed for classification by , and for regression by . Note that, in both cases no computational methods to solve the optimization problem were proposed. Moreover, in it was proved that all the regularizers of the form $\left\|{h}\right\|_{K}^{q}$ with $q\geq 1$ gives optimal convergence rates bound for the square loss, given an appropriate setting of the regularization weight. In particular, [27, Corollary 6] proves that, using the square loss and under assumptions (2) and (9), the optimal weight for the regularizer $\left\|{h}\right\|_{K}^{q}$ is $T^{-\frac{2\beta+q(1-\beta)}{2\beta+2/b}}.$ This implies a very important consequence, not mentioned in that paper: In the the capacity independent setting, that is $b=1$, if we use the regularizer $\left\|{h}\right\|_{K}$, the optimal regularization weight is $T^{-\frac{1}{2}}$, independent of the exponent of the range space (1) where $f_{\rho}$ belongs. Moreover, in the same paper it was argued that “From an algorithmic point of view however, q = 2 is currently the only feasible case, which in turn makes SVMs the method of choice”. Indeed, in this paper we give a parameter-free efficient procedure to train predictors with smooth losses, that implicitly uses the $\left\|{h}\right\|_{K}$ regularizer. Thanks to this, the regularization parameter does not need to be set using prior knowledge of the problem.

Discussion

Borrowing from OCO and statistical learning theory tools, we have presented the first parameter-free stochastic learning algorithm that achieves optimal rates of convergence w.r.t. the smoothness of the optimal predictor. In particular, the algorithm does not require any validation method for the model selection, rather it automatically self-tunes in an online and data-dependent way.

Even if this is mainly a theoretical work, we believe that it might also have a big potential in the applied world. Hence, as a proof of concept on the potentiality of this method we have also run few preliminary experiments, to compare the performance of PiSTOL to an SVM using 5-folds cross-validation to select the regularization weight parameter. The experiments were repeated with 5 random shuffles, showing the average and standard deviations over three datasets.Datasets available at http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. The precise details to replicate the experiments are in the Appendix. The latest version of LIBSVM was used to train the SVM . We have that PiSTOL closely tracks the performance of the tuned SVM when a Gaussian kernel is used. Also, contrary to the common intuition, the stochastic approach of PiSTOL seems to have an advantage over the tuned SVM when the number of samples is small. Probably, cross-validation is a poor approximation of the generalization performance in that regime, while the small sample regime does not affect at all the analysis of PiSTOL. Note that in the case of News20, a linear kernel is used over the vectors of size $1355192$. The finite dimensional case is not covered by our theorems, still we see that PiSTOL seems to converge at the same rate of SVM, just with a worse constant. It is important to note that the total time the 5-folds cross-validation plus the training with the selected parameter for the SVM on 58000 samples of SensIT Vehicle takes $\sim 6.5$ hours, while our unoptimized Matlab implementation of PiSTOL less than 1 hour, $\sim 7$ times faster. The gains in speed are similar on the other two datasets.

References

Appendix A Per-coordinate Variant of PiSTOL

Recently a number of algorithms with a different step size for each coordinate have been proposed, e.g. . The motivation is to take advantage of the sparsity of the features and, at the same time, to have a slower decaying step size for rare features. However, till now this adaptation has considered only the gradients and not to the norm of the competitor. Here we close this gap.

As shown in , these kind of algorithms can be very easily designed and analyzed just running an independent copy of the algorithm on each coordinate. Hence, we have the following corollary.

where $\phi(x):=\frac{x}{2}\,\frac{\exp\left(\frac{x}{2}\right)\left(x+1\right)+2}{1-x\exp\left(\frac{x}{2}\right)-x}\,\left(\exp\left(\frac{x}{2}\right)\left(x+1\right)+2\right)$.

Up to logarithmic terms, this regret bound is very similar to the one of AdaGrad , with two importance differences. Using our notation, AdaGrad depends $\sum_{t=1}^{T-1}s^{2}_{i,t}$ rather than $\sum_{t=1}^{T-1}|s_{i,t}|$. In the case of Lipschitz losses and binary features, these two dependencies are essentially equivalent. The second and more important difference is that AdaGrad depends on $\left\|{\boldsymbol{u}}\right\|^{2}_{\infty}$ instead of $\left\|{\boldsymbol{u}}\right\|_{\infty}$, or in alternative it assumes the knowledge of the (unknown) $\left\|{\boldsymbol{u}}\right\|_{\infty}$ to tune its step size.

Define $\left\|{f}\right\|_{\mathcal{L}^{1}_{\rho_{\mathcal{X}}}}:=\int_{\mathcal{X}}|f(x)|d\rho_{\mathcal{X}}$. We now use the the standard assumption on the behavior of the approximation error in $\mathcal{L}^{1}_{\rho_{\mathcal{X}}}$, see, e.g., .

then, under the assumptions of Theorem 1, the averaged solution of PiSTOL satisfies

This Theorem improves over the result in , where the worse bound $\mathcal{O}\left(T^{\epsilon-\frac{\beta}{2(\beta+1)}}\right),\forall\epsilon>0$, was proved using the prior knowledge of $\beta$. See for a discussion on the condition (10).

Appendix C Details about the Empirical Results

For the sake of the reproducibility of the experiments, we report here the exact details. The loss used by PiSTOL in all the experiments is a smoothed version of the hinge loss:

For the SVM we used the hinge loss. The parameters of PiSTOL were the same in all the experiments: $a=0.25$, $L=2$, $\beta=\sqrt{2aLT}$. The a9a dataset is composed by $32561$ training samples and $16281$ for testing, the dimension of the features is 123. The Gaussian kernel is

where $\gamma$ was fixed to $0.04$, as done in . The “C” parameter of the SVM was tuned with cross-validation over the range $\{2^{-1},2^{0},2^{1},2^{2},2^{3}\}$. The SensIT Vehicle dataset is a 3-class dataset composed by $78823$ training samples and $19705$ for testing. A binary classification task was built using the third class versus the other two, to have a very balanced problem. For the amount of time taken by LIBSVM to train a model, we only used a maximum of $58000$ training samples. The parameter $\gamma$ in the Gaussian kernel is $0.125$, again as in in . The range of the “C” parameter of the SVM was $\{2^{0},2^{1},2^{2},2^{3},2^{4},2^{5},2^{6}\}$. The news20.binary dataset is composed by $19996$ samples with dimension $1355191$, and normalized to have $L_{2}$ norm equal to 1. The test set was composed by $10000$ samples drawn randomly from the training samples. The range of the “C” parameter of the SVM was $\{2^{1},2^{2},2^{3},2^{4}\}$.

Appendix D Proofs

Given a closed and convex function $h:\mathcal{H}_{K}\to[-\infty,+\infty]$, its Fenchel conjugate $h^{*}:\mathcal{H}_{K}\to[-\infty,+\infty]$ is defined as h^{*}(g)=\sup_{f\in\mathcal{H}_{K}}\bigl{(}\left\langle{f}\,,\,{g}\right\rangle_{K}-h(f)\bigr{)}.

D.2 Proof of (3)

From , it is possible to extract the following inequality

Using the elementary inequalities $(1-2\eta)^{-1}-1\leq 4\eta,\ \forall 0<\eta\leq\frac{1}{4}$, we have

D.3 Proof of Theorem 1

In this section we prove the regret bound in the adversarial setting. The key idea is of the proof is to design a time-varying potential function. Some of the ideas in the proof are derived from .

In the proof of Theorem 1 we also use the following technical lemmas.

Consider the function $g(b)=\exp\left(\frac{(a+b)^{2}}{2c}\right)$. Using a second order Taylor expansion around we have

for some $\xi$ between and $b$. Note that r.h.s of (11) is a convex function w.r.t. $\xi$, so it is maximized when $\xi=0$ or $\xi=b$. Hence, the first inequality is obtained using upper bounding $\xi$ with $b$, and $(a+\xi)^{2}$ with $a^{2}+b^{2}$ in the second case. ∎

[15, Lemma 14] Define $\Psi(g)=b\exp{\frac{\left\|{g}\right\|_{K}^{2}}{2\alpha}}$, for $\alpha,b>0$. Then

Define $v_{t}=\delta+\sum_{i=1}^{t}x_{i}$. The concavity of the logarithm implies $\ln b\leq\ln a+\frac{b-a}{a}$ for all $a,b>0$. Hence we have

We are now ready to prove Theorem 1. Differently from the proof methods in , here the potential functions will depend explicitly on the sum of the past gradients, rather than simple on the time.

The Fenchel-Young inequality states that $\Psi(f)+\Psi^{*}(g)\geq\left\langle{f}\,,\,{g}\right\rangle_{K}$ for all $f,g\in\mathcal{H}_{K}$. Hence, it implies that, for any sequence of $k_{t}\in\mathcal{H}_{K}$ and any $h\in\mathcal{H}_{K}$, we have

Hence, using the definition of $g_{T}$, we have

Observe that, with the choice of $\alpha_{t}$, we have the following inequalities that will be used often in the proof:

$\frac{\left\|{g_{t}}\right\|_{K}}{\alpha_{t}}\leq\frac{\left\|{\sum_{i=1}^{t}k_{i}}\right\|_{K}}{\alpha_{t}}\leq\frac{1}{a}.$

$\frac{\left\|{g_{t-1}}\right\|_{K}\left\|{k_{t}}\right\|_{K}}{\alpha_{t}}\leq\left\|{k_{t}}\right\|_{K}\frac{\left\|{\sum_{i=1}^{t-1}k_{i}}\right\|_{K}}{\alpha_{t}}\leq\frac{\left\|{k_{t}}\right\|_{K}}{a}\leq\frac{L}{a}.$

$\frac{2\left\|{g_{t-1}}\right\|_{K}\left\|{k_{t}}\right\|_{K}+\left\|{k_{t}}\right\|_{K}^{2}}{2\alpha_{t}}\leq\left\|{k_{t}}\right\|_{K}\frac{\left\|{\sum_{i=1}^{t-1}k_{i}}\right\|_{K}+\left\|{k_{t}}\right\|_{K}}{\alpha_{t}}\leq\left\|{k_{t}}\right\|_{K}\frac{\left\|{\sum_{i=1}^{t}k_{i}}\right\|_{K}}{\alpha_{t}}\leq\frac{\left\|{k_{t}}\right\|_{K}}{a}\leq\frac{L}{a}.$

Consider the max of the r.h.s. of the last equality w.r.t. $\left\langle{g_{t-1}}\,,\,{k_{t}}\right\rangle_{K}$. Being a convex function of $\left\langle{g_{t-1}}\,,\,{k_{t}}\right\rangle_{K}$, the maximum is achieved at the border of the domain. Hence, $\langle g_{t-1},k_{t}\rangle=c_{t}\left\|{g_{t-1}}\right\|_{K}\left\|{k_{t}}\right\|_{K}$ where $c_{t}=1$ or $-1$. We will analyze the two case separately.

Case positive: Consider the case that $c_{t}=1$. Considering only the expression in parenthesis in (12), we have

where in the first inequality we used the first statement of Lemma 2. We now use the fact that $A:=\frac{L}{a}\exp\left(\frac{L}{a}\right)<1$ and the elementary inequality $\exp(x)\geq x+1$, to have

This quantity is non-positive iff $\frac{\left\|{g_{t-1}}\right\|_{K}^{2}}{\alpha_{t-1}}\geq\frac{A}{1-A}\left(\frac{2L}{a}+1\right)$.

We now consider the case of $\frac{A}{1-A}\left(\frac{2L}{a}+1\right)>\frac{\|g_{t-1}\|^{2}}{\alpha_{t-1}}\geq\frac{\|g_{t-1}\|^{2}}{\alpha_{t}}$. In this case, from (14), we have

Case negative: Now consider the case that $c_{t}=-1$. So we have

where in the inequality we used the second statement of Lemma 2. Considering again only the expression in the parenthesis we have

We have that this quantity is non-positive if $\frac{\left\|{g_{t-1}}\right\|_{K}^{2}}{\alpha_{t-1}}\geq\frac{\left\|{k_{t}}\right\|_{K}}{a}\frac{\exp\left(\frac{L}{2a}\right)\left(\frac{L}{a}+1\right)+2}{1-\frac{L}{a}\exp\left(\frac{L}{2a}\right)-\frac{L}{a}}$. Hence we now consider the case that $\frac{\left\|{g_{t-1}}\right\|_{K}^{2}}{\alpha_{t-1}}<\frac{\left\|{k_{t}}\right\|_{K}}{a}\frac{\exp\left(\frac{L}{2a}\right)\left(\frac{L}{a}+1\right)+2}{1-\frac{L}{a}\exp\left(\frac{L}{2a}\right)-\frac{L}{a}}$.

Using the definition of $\phi(\frac{L}{a})$ and summing over time we have

where in the third inequality we used Lemma 4.

Using (D.3), (20), and the definition of subgradient, we have

D.4 Proof of Corollary 1

We first state the technical results, used in the proofs.

[12, Lemma 7.2] Let $c_{1},c_{2},\cdots,c_{l}>0$ and $s>q_{1}>q_{2}>\cdots>q_{l-1}>0$. Then the equation

has a unique positive solution $x^{*}$. In addition,

Let $a,b,c>0$ and $0<\alpha<1$. Then the inequality

Denote by $y=x+b$, so consider the function $f(y)=y-ay^{\alpha}-b-c$. Applying Lemma 6 we get that the $h(y)=0$ has a unique positive solution $y^{*}$ and

Moreover, the inequality $h(y)\leq 0$ is verified for $y=0$, and $\lim_{y\rightarrow+\infty}h(y)=+\infty$, so we have $h(y)\leq 0$ implies $y\leq y^{*}$. We also have

Substituting back $x$ we get the stated bound. ∎

Using Cauchy-Schwarz inequality and Lemma 5, we have

Denote by $C=\sqrt{2a\sqrt{4H}\log\left(\frac{\left\|{f}\right\|_{K}\sqrt{aLT}}{b}+1\right)}$. Using Lemma 7 we get

D.5 Proof of Lemma 1

For any $f\in\mathcal{L}^{2}_{\rho_{\mathcal{X}}}$, define $X_{f}=\{\boldsymbol{x}\in\mathcal{X}:{\rm sign}(f)\neq f_{c}\}$. It is easy to verify that

Using Lemma 10.10 in and proceeding as in the proof of Theorem 10.5 in , we have

An application of Jensen’s inequality concludes the proof. ∎

D.6 Proof of Theorem 2

[12, Lemma 10.7] Let $p,q>1$ be such that $\frac{1}{p}+\frac{1}{q}=1$. Then

and the argmin is $\left(\frac{pa}{qb}\right)^{-\frac{1}{q+p}}$.

Equating the first derivative to zero we have

Substituting this expression into the min we have

The next Lemma is needed for the proof of Lemma 12 that is a stronger version of [12, Corollary 10.14] because it needs only smoothness rather than a bound on the second derivative.

We will first get rid of the norm inside the logarithmic term. This will allow us to have a bound that depends only on norm of $g$.

Let $\mathcal{L}(f)=\left\|{f}\right\|_{K}\sqrt{2\alpha\log\left(\frac{\sqrt{\alpha}\left\|{f}\right\|_{K}}{b}+1\right)}+q(f)$. Denote by $h^{*}=\operatorname*{arg\,min}_{f\in\mathcal{H}_{K}}\ \mathcal{L}(f)$. Hence, we have

Solving the quadratic inequality and using the elementary inequality $\sqrt{a+b}\leq\sqrt{a}+\frac{b}{2\sqrt{a}}$, we have

We now use this result in the regret bound of Theorem 1, to have

Dividing everything by $T$, taking the expectation of the two sides and using Jensen’s inequality we have

We now need to upper bound the terms in the $\max$. Using Lemma 8, we have that, for any $\eta,\gamma>0$

Consider first (33). Observe that from Lemma 12 and Lemma 10, we have

Consider now (32). Reasoning in a similar way we have

We now use the elementary inequality $1+x\leq\max(2,2x),\forall x\geq 0$, to study separately

On the other hand, for (36), for $\beta<\frac{1}{3}$, we have that the minimum over $\gamma$ is 0. For $\beta>\frac{1}{3}$, from Lemma 9, we have

Putting together (34), (37), and (38), we have the stated bound. ∎

D.7 Proof of Theorem 3

From the proof of Theorem 2, we have that

Dividing everything by $T$, taking the expectation of the two sides and using Jensen’s inequality we have

where in the last inequality we used Lemma 9. ∎