domain: info math

text:
Niklas Thiemann
email: niklasthiemann@gmail.com

Christian Igel
email: igel@di.ku.dk

Olivier Wintenberger
email: olivier.wintenberger@upmc.fr

Yevgeny Seldin
email: seldin@di.ku.dk

Steve Hanneke

Lev Reyzin

Algorithmic Learning Theory 2017

We propose a new PAC-Bayesian bound and a way of constructing a hypothesis space, so that the bound is convex in the posterior distribution and also convex in a trade-off parameter between empirical performance of the posterior distribution and its complexity. The complexity is measured by the Kullback-Leibler divergence to a prior. We derive an alternating procedure for minimizing the bound. We show that the bound can be rewritten as a one-dimensional function of the trade-off parameter and provide sufficient conditions under which the function has a single global minimum. When the conditions are satisfied the alternating minimization is guaranteed to converge to the global minimum of the bound. We provide experimental results demonstrating that rigorous minimization of the bound is competitive with cross-validation in tuning the trade-off between complexity and empirical performance. In all our experiments the trade-off turned to be quasiconvex even when the sufficient conditions were violated.

Introduction

PAC-Bayesian analysis, where PAC stands for the Probably Approximately Correct frequentist learning model [START_REF] Valiant | A theory of the learnable[END_REF], analyzes prediction accuracy of randomized classifiers. A randomized classifier is a classifier defined by a distribution ρ over a hypothesis class H. A randomized classifier predicts by drawing a hypothesis from H according to ρ and applying it to make the prediction [START_REF] Mcallester | Some PAC-Bayesian theorems[END_REF]. In many applications randomized prediction is replaced by a ρ-weighted majority vote [START_REF] Germain | PAC-Bayesian learning of linear classifiers[END_REF].

PAC-Bayesian analysis provides some of the tightest generalization bounds in statistical learning theory [START_REF] Germain | PAC-Bayesian learning of linear classifiers[END_REF]. PAC-Bayesian bounds have a form of a tradeoff between empirical performance of ρ and its complexity, measured by the Kullback-Leibler (KL) divergence (a.k.a. relative entropy) between ρ and a prior distribution π. Most of PAC-Bayesian literature relies on cross-validation to tune the trade-off. Crossvalidation is an extremely powerful and practical heuristic for selecting model parameters, but it can potentially be misleading [START_REF] Kearns | An experimental and theoretical comparison of model selection methods[END_REF][START_REF] Michael | Algorithmic stability and sanity-check bounds for leaveone-out cross-validation[END_REF]. It is also computationally expensive, especially for computationally demanding models, such as kernel SVMs, since it requires training a large number of classifiers on almost the whole dataset. Derivation of theoretical results that would not require parameter cross-validation is a long-standing challenge for theoretical machine learning [START_REF] Langford | Tutorial on practical prediction theory for classification[END_REF].

The need to rely on cross-validation stems from several reasons:

• Not all of the existing PAC-Bayesian bounds are convex in the posterior distribution ρ. For example, the most widely used PAC-Bayes-kl bound due to [START_REF] Seeger | PAC-Bayesian generalization error bounds for Gaussian process classification[END_REF] is non-convex. This makes it hard to minimize the bound with respect to the posterior distribution. In most papers the bound is replaced by a linear trade-off between empirical error and the KL divergence and the trade-off parameter is tuned by crossvalidation.

While it is possible to achieve convexity in the posterior distribution ρ by introducing an additional trade-off parameter [START_REF] Catoni | PAC-Bayesian supervised classification: The thermodynamics of statistical learning[END_REF][START_REF] Keshet | Pac-bayesian approach for minimization of phoneme error rate[END_REF], we are unaware of successful attempts to tune the additional trade-off parameter through rigorous bound minimization. In practice, the alternative bounds are replaced by the same linear trade-off mentioned above and tuned by cross-validation.

• The second obstacle is that, in order to keep the KL divergence between the posterior and the prior tractable, the set of posterior and prior distributions is often restricted.

A popular example are Gaussian posteriors and Gaussian priors [START_REF] Langford | PAC-Bayes & margins[END_REF][START_REF] Mcallester | PAC-Bayesian stochastic model selection[END_REF][START_REF] Langford | Tutorial on practical prediction theory for classification[END_REF]. Even if the initial bound is convex in the posterior distribution, the convexity may be broken by such a restriction or reparametrization, as it happens in the Gaussian case [START_REF] Germain | PAC-Bayesian learning of linear classifiers[END_REF].

• Even though PAC-Bayesian bounds are some of the tightest, we are unaware of examples, where their tightness is sufficient to compete with cross-validation in tuning the trade-off between complexity and empirical performance.

We propose a relaxation of Seeger's PAC-Bayes-kl inequality, which we name PAC-Bayes-λ inequality or PAC-Bayes-λ bound when referring to the right hand side of the inequality. The bound is convex in the posterior distribution ρ and has a convex trade-off between the empirical loss and KL divergence. The inequality is similar in spirit to the one proposed by [START_REF] Keshet | Pac-bayesian approach for minimization of phoneme error rate[END_REF], but it does not restrict the form of ρ and π. We provide an alternating procedure for minimizing the bound. We show that the bound can be rewritten as a continuous one-dimensional function of the trade-off parameter λ and that under certain sufficient conditions this function is strongly quasiconvex (it has a single global minimum and no other stationary points). This guarantees convergence of alternating minimization to the global optimum.

For infinite hypothesis spaces alternating minimization can be computationally intractable or require parametrization, which can break the convexity of the bound in the posterior distribution. We get around this difficulty by constructing a finite data-dependent hypothesis space. The hypothesis space is constructed by taking m subsamples of size r from the training data. Each subsample is used to train a weak classifier, which is then validated on the remaining n -r points, where n is the sample size. We adapt our PAC-Bayesian bound and minimization procedure to this setting. Our analysis and minimization procedure work for any m, r, and any split of the data, including overlaps between training sets and overlaps between validation sets. In particular, it can also be applied to aggregate models originating from a cross-validation split of the data. However, in cross-validation the training sets are typically large (of order n) and validation sets and the number of models are small. While the prediction accuracy is still competitive in this setting, the highest computational advantage from our approach is achieved when the relation is reversed and the training size r is taken to be small, roughly of order d, where d is the number of features, and the number of models m is taken to be large, roughly of order n. The construction of hypothesis space can be seen as sample compression [START_REF] Laviolette | PAC-Bayes risk bounds for stochastic averages and majority votes of sample-compressed classifiers[END_REF]. However, unlike the common approach to sample compression, which considers all possible subsamples of a given size and thus computationally and statistically inefficient, we consider only a small subset of possible subsamples.

We provide experimental results on several UCI datasets showing that the prediction accuracy of our learning procedure (training m weak classifiers and weighting their predictions through minimization of the PAC-Bayes-λ bound) is comparable to prediction accuracy of kernel SVMs tuned by cross-validation. In addition, we show that when r is considerably smaller than n and m is of order n, the comparable prediction accuracy is achieved at a much lower computation cost. The computational speed-up is achieved because of the super-quadratic training time of kernel SVMs, which makes it much faster to train many weak SVMs on small training sets than one powerful SVM on a big training set.

In the following, we provide a brief review of PAC-Bayesian analysis, then present the PAC-Bayesian bound and its minimization procedure in Section 3, derive conditions for convergence of minimization procedure to the global minimum in Section 4, describe our construction of a hypothesis space and specialize our results to this construction in Section 5, and provide experimental validation in Section 6.

A Brief Review of PAC-Bayesian Analysis

To set the scene we start with a brief review of PAC-Bayesian analysis.

Notations

We consider a supervised learning setting with an input space X and an output space Y. We let S = {(X 1 , Y 1 ), . . . , (X n , Y n )} denote an independent identically distributed (i.i.d.) sample of size n drawn according to an unknown distribution D(X, Y ). A hypothesis h is a function from the input to the output space h : X → Y. We use H to denote a hypothesis class. We let : Y 2 → [0, 1] denote a bounded loss function. The loss of h on a sample (X, Y ) is (h(X), Y ) and the expected loss of h is denoted by

L(h) = E [ (h(X), Y )]. We use L(h, S) = 1 n n i=1 (h(X i ), Y i ) to denote the empirical loss of h on S.
A randomized prediction rule parametrized by a distribution ρ over H is defined in the following way. For each prediction on a sample point X the rule draws a new hypothesis h ∈ H according to ρ and applies it to X. The expected loss of such prediction rule is E h∼ρ [L(h)] and the empirical loss is E h∼ρ L(h, S) . We use KL(ρ π) = E h∼ρ ln ρ(h) π(h) to denote the KL divergence between ρ and π. For Bernoulli distributions with biases p and q we use kl(p q) as a shorthand for KL([p, 1 -p] [q, 1 -q]), the KL divergence between the two distributions. Finally, we use

E ρ [•] as a shorthand for E h∼ρ [•] and E S [•] as a shorthand for E S∼D n [•].

Change of Measure Inequality

The majority of PAC-Bayesian bounds are based on the following lemma.

Lemma 1 (Change of Measure Inequality) For any function f : H × (X × Y) n → R and for any distribution π over H , such that π is independent of S, with probability greater than 1 -δ over a random draw of S, for all distributions ρ over H simultaneously: ,S ) .

E h∼ρ [f (h, S)] ≤ KL(ρ π) + ln 1 δ + ln E h∼π E S e f (h
(

) 1
The lemma is based on Donsker-Varadhan's variational definition of the KL divergence [START_REF] Donsker | Asymptotic evaluation of certain Markov process expectations for large time[END_REF], by which KL(ρ π) h) , where the supremum is over all measurable functions f : H → R. In the lemma, f is extended to be a function of h and S and then Markov's inequality is used to bound the expectation with respect to π by E π e f (h,S) ≤ 1 δ E S E π e f (h,S ) with probability at least 1 -δ. Independence of π and S allows to exchange the order of expectations, leading to the statement of the lemma. For a formal proof we refer to [START_REF] Tolstikhin | PAC-Bayes-Empirical-Bernstein inequality[END_REF].

= sup f E ρ [f (h)] + ln E π e f (

PAC-Bayes-kl Inequality

Various choices of the function f in Lemma 1 lead to various forms of PAC-Bayesian bounds [START_REF] Seldin | PAC-Bayesian inequalities for martingales[END_REF]. The classical choice is f (h, S) = n kl( L(h, S) L(h)). The moment generating function of f can be bounded in this case by E S e f (h,S) ≤ 2 √ n [START_REF] Maurer | A note on the PAC-Bayesian theorem[END_REF][START_REF] Germain | Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm[END_REF]. This bound is used to control the last term in equation (1), leading to the PAC-Bayes-kl inequality [START_REF] Seeger | PAC-Bayesian generalization error bounds for Gaussian process classification[END_REF].

Theorem 2 (PAC-Bayes-kl Inequality) For any probability distribution π over H that is independent of S and any δ ∈ (0, 1), with probability greater than 1 -δ over a random draw of a sample S, for all distributions ρ over H simultaneously:

kl E ρ L(h, S) E ρ [L(h)] ≤ KL(ρ π) + ln 2 √ n δ n .
(2)

PAC-Bayes-λ inequality and its Alternating Minimization

By inversion of the kl with respect to its second argument, inequality (2) provides a bound on E ρ [L(h)]. However, this bound is not convex in ρ and, therefore, inconvenient for minimization. We introduce a relaxed form of the inequality, which has an additional trade-off parameter λ. The inequality leads to a bound, which is convex in ρ for a fixed λ and convex in λ for a fixed ρ, making it amenable to alternating minimization. Theorem 3 is analogous to Keshet et al. (2011, Theorem 1) and a similar result can also be derived by using the techniques from [START_REF] Tolstikhin | PAC-Bayes-Empirical-Bernstein inequality[END_REF], as shown by [START_REF] Thiemann | PAC-Bayesian ensemble learning[END_REF].

Theorem 3 (PAC-Bayes-λ Inequality) For any probability distribution π over H that is independent of S and any δ ∈ (0, 1), with probability greater than 1 -δ over a random draw of a sample S, for all distributions ρ over H and λ ∈ (0, 2) simultaneously:

E ρ [L(h)] ≤ E ρ L(h, S) 1 -λ 2 + KL(ρ π) + ln 2 √ n δ λ 1 -λ 2 n . ( 3
)
We emphasize that the theorem holds for all values of λ ∈ (0, 2) simultaneously. This is in contrast to some other parametrized PAC-Bayesian bounds, for example, the one proposed by [START_REF] Catoni | PAC-Bayesian supervised classification: The thermodynamics of statistical learning[END_REF], which hold for a fixed value of a trade-off parameter.

Proof We use the following analog of Pinsker's inequality [START_REF] Marton | A measure concentration inequality for contracting Markov chains[END_REF][START_REF] Marton | A measure concentration inequality for contracting Markov chains Erratum[END_REF][START_REF] Samson | Concentration of measure inequalities for markov chains and φ-mixing processes[END_REF]Boucheron et al., 2013, Lemma 8.4): for p < q

kl(p q) ≥ (q -p) 2 /(2q). (4)
By application of inequality (4), inequality (2) can be relaxed to , 2003). By using the inequality √ xy ≤ 1 2 λx + y λ for all λ > 0, we have that with probability at least 1 -δ for all ρ and λ > 0 [START_REF] Keshet | Pac-bayesian approach for minimization of phoneme error rate[END_REF]. By changing sides

E ρ [L(h)] -E ρ L(h, S) ≤ 2E ρ [L(h)] KL(ρ π) + ln 2 √ n δ n (5) (McAllester
E ρ [L(h)] -E ρ L(h, S) ≤ λ 2 E ρ [L(h)] + KL(ρ π) + ln 2 √ n δ λn (6)
1 - λ 2 E ρ [L(h)] ≤ E ρ L(h, S) + KL(ρ π) + ln 2 √ n δ λn .
For λ < 2 we can divide both sides by 1 -λ 2 and obtain the theorem statement.

Since [START_REF] Cover | Elements of Information Theory[END_REF], for a fixed λ the right hand side of inequality (3) is convex in ρ and the minimum is achieved by

E ρ L(h, S) is linear in ρ and KL(ρ π) is convex in ρ (
ρ λ (h) = π(h)e -λn L(h,S) E π e -λn L(h ,S) , (7)
where E π e -λn L(h ,S) , a shorthand for E h ∼π e -λn L(h ,S) , is a convenient way of writing the normalization factor, which covers continuous and discrete hypothesis spaces in a unified notation. Furthermore, for t ∈ (0, 1) and [START_REF] Tolstikhin | PAC-Bayes-Empirical-Bernstein inequality[END_REF]. Therefore, for a fixed ρ the right hand side of inequality ( 3) is convex in λ for λ ∈ (0, 2). The minimum is achieved by [START_REF] Tolstikhin | PAC-Bayes-Empirical-Bernstein inequality[END_REF]. Note that the optimal value of λ is smaller than 1 and that for n ≥ 4 it can be lower bounded as λ ≥

c 1 , c 2 ≥ 0 the function c 1 1-t + c 2 t(1-t) is convex in t (Tolstikhin
λ = 2 2nEρ[ L(h,S)] KL(ρ π)+ln 2 √ n δ + 1 + 1 (8)
2 √ 2n+1+1 ≥ 1 √ n .
Alternating application of the update rules ( 7) and ( 8) monotonously decreases the bound, and thus converges to a local minimum.

Unfortunately, the bound is not jointly convex in ρ and λ (this can be verified by computing the Hessian of the first term and taking large n, so that the second term can be ignored). Joint convexity would have been a sufficient condition for convergence to the global minimum, but it is not a necessary condition. In the following section we show that under certain conditions alternating minimization is still guaranteed to converge to the global minimum of the bound despite absence of joint convexity.

Strong Quasiconvexity of the PAC-Bayes-λ Bound

We denote the right hand side of the bound in Theorem 3 by

F(ρ, λ) = E ρ L(h, S) 1 -λ/2 + KL(ρ π) + ln 2 √ n δ nλ(1 -λ/2)
.

By substituting the optimal value of ρ from equation (7) into F(ρ, λ) and applying the identity

KL(ρ λ π) = E ρ λ ln ρ λ (h) π(h) = E ρ λ   ln e -nλ L(h,S) E π e -nλ L(h ,S)   = -nλE ρ λ L(h, S) -ln E π e -nλ L(h,S) (9)
we can write F as a function of a single scalar parameter λ:

F(λ) = E ρ λ L(h, S) 1 -λ/2 + KL(ρ λ π) + ln 2 √ n δ nλ(1 -λ/2) = E ρ λ L(h, S) 1 -λ/2 - E ρ λ L(h, S) 1 -λ/2 + -ln E π e -nλ L(h,S) + ln 2 √ n δ nλ(1 -λ/2) = -ln E π e -nλ L(h,S) + ln 2 √ n δ nλ(1 -λ/2) .
We note that F(λ) is not necessarily convex in λ. For example, taking

H = {h 1 , h 2 }, L(h 1 , S) = 0, L(h 2 , S) = 0.5, π(h 1 ) = π(h 2 ) = 1
2 , n = 100, and δ = 0.01 produces a nonconvex F. However, we show that F(λ) is strongly quasiconvex under a certain condition on the variance defined by

Var ρ λ L(h, S) = E ρ λ L(h, S) 2 -E ρ λ L(h, S) 2 .
We recall that a univariate function f : I → R defined on an interval I ⊆ R is strongly quasiconvex if for any x, y ∈ I and t ∈ (0, 1) we have f (tx + (1 -t)y) < max {f (x), f (y)}.

Theorem 4 F(λ) is continuous and if at least one of the two conditions

2 KL(ρ λ π) + ln 4n δ 2 > λ 2 n 2 Var ρ λ L(h, S) (10
)

or E ρ λ L(h, S) > (1 -λ)nVar ρ λ L(h, S) (11)
is satisfied for all λ ∈ ln 2 √ n δ n , 1 , then F(λ) is strongly quasiconvex for λ ∈ (0, 1] and alternating application of the update rules (7) and (8) converges to the global minimum of F.

Proof The proof is based on inspection of the first and second derivative of F(λ). Calculation of the derivatives is provided in Appendix A. The existence of the first derivative ensures continuity of F(λ). By inspecting the first derivative we obtain that stationary points of F(λ) corresponding to F (λ) = 0 are characterized by the identity

2(1 -λ) KL(ρ λ π) + ln 2 √ n δ = λ 2 nE ρ λ L(h, S) .
The identity provides a lower bound on the value of λ at potential stationary points. Using the facts that E ρ λ L(h, S) ≤ 1 and for λ ≤ 1 2 the complement (1 -λ) ≥ 1 2 , for n ≥ 7 we have

λ = 2(1 -λ) KL(ρ λ π) + ln 2 √ n δ nE ρ λ L(h, S) ≥ min   KL(ρ λ π) + ln 2 √ n δ n , 1 2   ≥ ln 2 √ n δ n .
By expressing KL(ρ λ π) via E ρ λ L(h, S) (or the other way around) and substituting it into the second derivative of F(λ) we obtain that if either of the two conditions of the theorem is satisfied at a stationary point then the second derivative of F(λ) is positive there. Thus, if (10) or ( 11) is satisfied for all λ ∈ ln 2 √ n δ n , 1 then all stationary points of F(λ) (if any exist) are local minima. Since F(λ) is a continuous one-dimensional function it means that F(λ) is strongly quasiconvex (it has a single global minimum and no other stationary points). Since alternating minimization monotonously decreases the value of F(λ) it is guaranteed to converge to the global minimum.

Next we show a sufficient condition for (10) to be satisfied for a finite H for all λ.

Theorem 5 Let m be the number of hypotheses in H and assume that the prior π

(h) is uniform. Let a = ln 4n δ 2 n √ 3 , b = ln(3mn 2 ) n ln 2 √ n δ
, and K = e 2 12 ln 4n δ 2 . Let x h = L(h, S) -min h L(h, S).

If the number of hypotheses for which

x h ∈ (a, b) is at most K then Var ρ λ L(h, S) ≤ ln 4n δ 2 λ 2 n 2 for all λ ∈ ln 2 √ n δ
n , 1 and F(λ) is strongly quasiconvex and its global minimum is guaranteed to be found by alternating application of the update rules (7) and (8).

The theorem splits hypotheses in H into "good", "mediocre", and "bad". "Good" hypotheses are those for which x h ≤ a, meaning that the empirical loss L(h, S) is close to the best. "Mediocre" are those for which x h ∈ (a, b). "Bad" are those for which x h ≥ b. The theorem states that as long as the number of "mediocre" hypotheses is not too large, F(λ) is guaranteed to be quasiconvex. Proof We have Var ρ λ L(h, S) = Var ρ λ L(h, S) -min h L(h, S) . Under the assumption of a uniform prior ρ λ (h) = e -nλx h / h e -nλx h . Since for h * = arg min h L(h, S) we have x h * = 0, the denominator satisfies h e -nλx h ≥ 1. Let I 0a = [0, a], I ab = (a, b), and I b1 = [b, 1] be the intervals corresponding to "good", "mediocre", and "bad" hypotheses. We have:

Var ρ λ L(h, S) ≤ E ρ λ x 2 h = h x 2 h e -nλx h h e -nλx h = x h ∈I 0a x 2 h e -nλx h h e -nλx h + x h ∈I ab x 2 h e -nλx h h e -nλx h + x h ∈I b1 x 2 h e -nλx h h e -nλx h ≤ a 2 + x h ∈I ab x 2 h e -nλx h + x h ∈I b1 x 2 h e -nλx h .
We show a number of properties of the above expression. First, we recall that λ ≤ 1. Therefore,

a 2 = ln 4n δ 2 3n 2 ≤ ln 4n δ 2 3λ 2 n 2 .
For the second term, simple calculus gives x 2 e -nλx ≤ 4 e 2 n 2 λ 2 . Since by the theorem assumption there are at most K hypotheses falling in I ab ,

h∈I ab x 2 h e -nλx h ≤ 4K e 2 n 2 λ 2 ≤ ln 4n δ 2 3λ 2 n 2 .
For the last term we have b > 2

n ln 2 √ n δ = 2 n n ln 2 √ n δ ≥ 2 λn
and we note that for x ≥ 2/λn the function x 2 e -nλx is monotonically decreasing in x. Since

λ ≥ ln 2 √ n δ n we obtain x h ∈I b1 x 2 h e -nλx h ≤ mb 2 e -nλb ≤ mb 2 e -n ln 2 √ n δ b ≤ me -n ln 2 √ n δ b = m 1 3mn 2 = 1 3n 2 ≤ ln 4n δ 2 3λ 2 n 2 .
(12) By taking all three terms together we arrive at

Var ρ λ L(h, S) ≤ ln 4n δ 2
λ 2 n 2 , which implies condition (10) of Theorem 4 since KL(ρ λ π) ≥ 0.

In Appendix B we provide a couple of relaxations of the conditions in Theorem 5. The first allows to trade the boundaries a and b of the intervals with the value of K and the second improves the value of b.

In our experiments presented in Section 6, F(λ) turned to be convex even when the sufficient conditions of Theorem 5 (including the relaxations detailed in Appendix B) were violated. This suggests that it may be possible to relax the conditions even further. At the same time, it is possible to construct artificial examples, where F(λ) is not quasiconvex. For example, taking n = 200, δ = 0.25, and m = round e 0.74n∆ + 1 ≈ 2.7 • 10 6 hypotheses (where round is rounding to the nearest integer) with L(h 1 , S) = 0 and L(h i , S) = ∆ = 0.1 for all i ∈ {2, . . . , m} and a uniform prior leads to F(λ) with two local minima. The artificial example requires m to be of the order of e nλ ∆ , where λ is the value of λ at a stationary point of F(λ) and ∆ is the loss of suboptimal hypotheses (in the example ∆ = 0.1). Thus, quasiconvexity is not always guaranteed, but it holds in a wide range of practical scenarios.

Construction of a Hypothesis Space

Computation of the partition function (the denominator in (7)) is not always tractable, however, it can be easily computed when H is finite. The crucial step is to construct a sufficiently powerful finite hypothesis space H. Our proposal is to construct H by training m hypotheses, where each hypothesis is trained on r random points from S and validated on the remaining n -r points. This construction resembles a cross-validation split of the data. However, in cross-validation r is typically large (close to n) and validation sets are nonoverlapping. Our approach works for any r and has additional computational advantages when r is small. We do not require validation sets to be non-overlapping and overlaps between training sets are allowed. Below we describe the construction more formally.

Let h ∈ {1, . . . , m} index the hypotheses in H. Let S h denote the training set of h and S \ S h the validation set. S h is a subset of r points from S, which are selected independently of their values (for example, subsampled randomly or picked according to a predefined partition of the data). We define the validation error of h by Lval (h, S) = 1 n-r (X,Y )∈S\S h (h(X), Y ). Note that the validation errors are (n -r) i.i.d. random variables with bias L(h) and, therefore, for f (h, S) = (n -r) kl( Lval (h, S) L(h)) we have Theorem 6 Let S be a sample of size n. Let H be a set of m hypotheses, where each h ∈ H is trained on r points from S selected independently of the composition of S. For any probability distribution π over H that is independent of S and any δ ∈ (0, 1), with probability greater than 1 -δ over a random draw of a sample S, for all distributions ρ over H and λ ∈ (0, 2) simultaneously:

E S e f (h,S) ≤ 2 √ n -r.
E ρ [L(h)] ≤ E ρ Lval (h, S) 1 -λ 2 + KL(ρ π) + ln 2 √ n-r δ λ 1 -λ 2 (n -r) . (13)
It is natural, but not mandatory to select a uniform prior π(h) = 1/m. The bound in equation ( 13) can be minimized by alternating application of the update rules in equations ( 7) and ( 8) with n being replaced by n -r and L by Lval .

Experimental Results

In this section we study how PAC-Bayesian weighting of weak classifiers proposed in Section 5 compares with "strong" kernel SVMs tuned by cross-validation and trained on all training data. The experiments were performed on eight UCI datasets [START_REF] Asuncion | UCI machine learning repository[END_REF] summarized in Table 1. In our experiments we employed the SVM solver from LIBSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF]. We compared the prediction accuracy and run time of our prediction strategy with a baseline of RBF kernel SVMs tuned by cross-validation. For the baseline we used 5-fold cross-validation for selecting the soft-margin parameter, C, and the bandwidth parameter γ of the kernel k(X i , X j ) = exp(-γ X i -X j 2 ). The value of C was selected from a grid, such that log 10 C ∈ {-3, -2, . . . , 3}. The values for the grid of γ-s were selected using the heuristic proposed in [START_REF] Jaakkola | Using the fisher kernel method to detect remote protein homologies[END_REF]. Specifically, for i ∈ {1, . . . , n} we defined G(X i ) = min (X j ,Y j )∈S∧Y i =Y j X i -X j . We then defined a seed γ J by γ J = 1 2•median(G) 2 . Finally, we took a geometrically spaced grid around γ J , so that γ ∈ {γ J 10 -4 , γ J 10 -2 , . . . , γ J 10 4 }.

For our approach we selected m subsets of r points uniformly at random from the training set S. We then trained an RBF kernel SVM for each subset. The kernel bandwidth parameter γ was randomly selected for each subset from the same grid as used in the baseline. In all our experiments very small values of r, typically up to d + 1 with d being the input dimension, were sufficient for successfully competing with the prediction accuracy of the baseline and provided the most significant computational improvement. For such small values of r it was easy to achieve perfect separation of the training points and, therefore, selection of C was unnecessary. The performance of each weak classifier was validated on n -r points not used in its training. The weighting of classifiers ρ was then computed through alternating minimization of the bound in Theorem 6.

In most of PAC-Bayesian literature it is common to replace randomized prediction with ρ-weighted majority vote. From a theoretical point of view the error of ρ-weighted majority vote is bounded by at most twice the error of the corresponding randomized classifier, however, in practice it usually performs better than randomized prediction [START_REF] Germain | PAC-Bayesian learning of linear classifiers[END_REF]. In our main experiments we have followed the standard choice of using the ρweighted majority vote. In Appendix D.4 we provide additional experiments showing that in our case the improvement achieved by taking the majority vote was very minor compared to randomized prediction. We use the term PAC-Bayesian aggregation to refer to prediction with ρ-weighted majority vote.

In the first two experiments we studied the influence of r and m on classification accuracy and run time. The complexity term in Theorem 6 (the second term on the right hand side of ( 13)) decreases with the decrease of the training set sizes r (because the size of the validation sets n -r increases) and with the decrease of the number of hypotheses m (because π(h) = 1/m increases). From the computational point of view it is also desirable to have small r and m, especially when working with expensive-to-train models, such as In the first experiment we studied the influence of r and m on the prediction accuracy of PAC-Bayesian aggregation. We considered 20 values of m in [1, n] and 20 values of r in [2, d + 1]. For each pair of m and r the prediction accuracy of PAC-Bayesian aggregation was evaluated, resulting in a matrix of losses. To simplify the comparison we subtracted the prediction accuracy of the baseline, thus zero values correspond to matching the accuracy of the baseline. In Figure 1 we show a heatmap of this matrix for two UCI datasets and the results for the remaining datasets are provided in Appendix D.1. Overall, reasonably small values of m and r were sufficient for matching the accuracy of SVM tuned by crossvalidation.

In the second experiment we provide a closer look at the effect of increasing the number m of weak SVMs when their training set sizes r are kept fixed. We picked r = d + 1 and ran our training procedure with 20 values of m in [1, n]. In Figure 2 we present the prediction accuracy of the resulting weighted majority vote vs. prediction accuracy of the baseline for four datasets. The graphs for the remaining datasets are provided in Appendix D.1. We also show the running time of our procedure vs. the baseline. The running time of the baseline includes cross-validation and training of the final SVM on the whole training set, while the running time of PAC-Bayesian aggregation includes training of m weak SVMs, their validation, and the computation of ρ. In addition, we report the value of PAC-Bayes-kl bound from Theorem 2 on the expected loss of the randomized classifier defined by ρ. The kl divergence was inverted numerically to obtain a bound on the expected loss E ρ [L(h)].

The bound was adapted to our construction by replacing n with n -r and E ρ L(h, S)

with E ρ

Lval (h, S) . We note that since the bound holds for any posterior distribution, it also holds for the distribution found by minimization of the bound in Theorem 6. However, since Theorem 6 is a relaxation of PAC-Bayes-kl bound, using PAC-Bayes-kl for the final error estimate is slightly tighter. The bound on the loss of ρ-weighted majority vote is at most a factor of 2 larger than than the bound for the randomized classifier. In calculation of the bound we used δ = 0.05. We conclude from the figure that relatively small values of m are sufficient for matching or almost matching the prediction accuracy of the baseline, while the run time is reduced dramatically. We also note that the bound is exceptionally tight.

In our last experiment we tested quasiconvexity of F(λ). Theorem 5 provided theoretical guarantee of quasiconvexity for small m and numerical evaluation has further shown that F(λ) was convex for all values of m used in our experiments. For testing the theoretical guarantees we increased m in steps of 10 until the sufficient condition for strong In Table 2 we report the average over the 10 repetitions of the maximal values of m with guaranteed quasiconvexity. Since F(λ) is always quasiconvex for m ≤ K(0, 0) + 1, where K(0, 0) = e 2 4 ln 4n δ 2 (see equation ( 15) in Appendix B.1), we report the value of K(0, 0) + 1 whenever it was not possible to ensure quasiconvexity with larger m. When it was not possible to guarantee quasicovexity theoretically we tested the shape of F(λ) empirically. Figure 3 shows a few typical examples. The plots in Figure 3 were constructed in the following way: given a sample S, we trained m weak SVMs. We then computed the corresponding vector of validation losses, Lval (h, S). For each value in a grid of λ-s, we computed the corresponding ρ according to equation ( 7). Finally, we substituted the value of ρ λ and λ into equation (3) to get the value of the bound. In all our calculations we used a uniform prior and δ = 0.05. The figure shows that F(λ) was convex in λ in all the cases.

Conclusion

We have presented a new PAC-Bayesian inequality, an alternating procedure for its minimization, and a way to construct a finite hypothesis space for which the bound and minimization procedure work particularly well. We have derived sufficient conditions for the minimization procedure to converge to the global optimum of the bound. We have shown that the procedure is competitive with cross-validation in tuning the trade-off between complexity and empirical performance of ρ. In addition, it provides tight high-probability generalization guarantees and achieves prediction accuracies on par with kernel SVMs tuned by cross-validation, but at a considerably lower computation cost.

In our experiments the bound turned to be convex even when the sufficient conditions of Theorem 5 were violated. It suggests that further relaxation of these conditions may be possible to achieve in future work.

Appendix A. Calculation of the Derivatives of F(λ)

We decompose F(λ) in the following way:

F(λ) = -ln E π e -nλ L(h,S) + ln 2 √ n δ nλ(1 -λ/2) = f (λ)g(λ),
where

f (λ) = - 1 n ln E π e -nλ L(h,S) + ln 2 √ n δ n , g(λ) = 1 λ(1 -λ/2) .
For the derivatives of f and g we have:

f (λ) = - d dλ E π e -nλ L(h,S) nE π e -nλ L(h,S) = E π L(h, S)e -nλ L(h,S) E π e -nλ L(h,S) = E ρ λ L(h, S) ≥ 0. f (λ) = d dλ E π L(h, S)e -nλ L(h,S) E π e -nλ L(h,S) -d dλ E π e -nλ L(h,S) E π L(h, S)e -nλ L(h,S) E π e -nλ L(h,S) 2 = -nE π L(h, S) 2 e -nλ L(h,S) E π e -nλ L(h,S) + n   E π L(h, S)e -nλ L(h,S) E π e -nλ L(h,S)   2 = -n E ρ λ L(h, S) 2 -E ρ λ L(h, S) 2 = -nVar ρ λ L(h, S) ≤ 0. g (λ) = - (1 -λ/2 -λ/2) λ 2 (1 -λ/2) 2 = λ -1 λ 2 (1 -λ/2) 2 ≤ 0. g (λ) = λ 2 (1 -λ/2) 2 -(λ -1) 2λ(1 -λ/2) 2 -λ 2 (1 -λ/2) λ 4 (1 -λ/2) 4 = λ(1 -λ/2) -(λ -1) (2(1 -λ/2) -λ) λ 3 (1 -λ/2) 3 = λ(1 -λ/2) -2(λ -1)(1 -λ) λ 3 (1 -λ/2) 3 = λ(1 -λ/2) + 2(λ -1) 2 λ 3 (1 -λ/2) 3 = λ -λ 2 /2 + 2λ 2 -4λ + 2 λ 3 (1 -λ/2) 3 = (3/2)λ 2 -3λ + 2 λ 3 (1 -λ/2) 3 = 3λ 2 -6λ + 4 2λ 3 (1 -λ/2) 3 = 3 (λ -1) 2 + 1 2λ 3 (1 -λ/2) 3 > 0.
At a stationary point we have F (λ) = f (λ)g(λ) + g (λ)f (λ) = 0. By using the identity

f (λ) = λE ρ λ L(h, S) + KL(ρ λ π) + ln 2 √ n δ n , (14)
which follows from (9), this gives

F (λ) = E ρ λ L(h, S) λ(1 -λ/2) + (λ -1) λE ρ λ L(h, S) λ 2 (1 -λ/2) 2 + (λ -1) KL(ρ λ π) + ln 2 √ n δ nλ 2 (1 -λ/2) 2 = 0.
This can be rewritten as

E ρ λ L(h, S) + (λ -1)E ρ λ L(h, S) 1 -λ/2 + (λ -1) KL(ρ λ π) + ln 2 √ n δ nλ(1 -λ/2) = 0, 1 2 λE ρ λ L(h, S) = (1 -λ) KL(ρ λ π) + ln 2 √ n δ nλ , KL(ρ λ π) + ln 2 √ n δ n = λ 2 E ρ λ L(h, S) 2(1 -λ) ,
which characterizes the stationary points. By combining this with the identity ( 14) we obtain that at a stationary point

f (λ) = λ + λ 2 2(1 -λ) E ρ λ L(h, S) = λ(1 -λ/2) 1 -λ E ρ λ L(h, S) .
For the second derivative we have

F (λ) = f (λ)g(λ) + 2f (λ)g (λ) + g (λ)f (λ). At a stationary point g (λ)f (λ) + 2f (λ)g (λ) = 3λ 2 -6λ + 4 2λ 3 (1 -λ/2) 3 λ(1 -λ/2) 1 -λ - 2(1 -λ) λ 2 (1 -λ/2) 2 E ρ λ L(h, S) = E ρ λ L(h, S) λ(1 -λ/2)(1 -λ) .
By plugging this into F (λ) we obtain that at a stationary point (if such exists)

F (λ) = -nVar ρ λ L(h, S) λ(1 -λ/2) + E ρ λ L(h, S) λ(1 -λ/2)(1 -λ) = 1 λ(1 -λ/2)   E ρ λ L(h, S) 1 -λ -nVar ρ λ L(h, S)   .
This expression is positive if

E ρ λ L(h, S) > (1 -λ)nVar ρ λ L(h, S)
or, equivalently (by characterization of a stationary point), 2 KL(ρ λ π) + ln 4n δ 2 > λ 2 n 2 Var ρ λ L(h, S) .

B.2. Refinement of the Boundary b

In the derivation in ( 12 ≥ 2 and n ≥ 5 we have

x h ∈I b1 x 2 h e -nλx h ≤ mb 2 e -nλb = m ln(3mn) + ln 4(ln(3mn)) 2 ln 2 √ n δ ln 4n δ 2 2 n ln 2 √ n δ ln 2 √ n δ ln 4n δ 2 3mn × 4 (ln(3mn)) 2 = ln 4n 2 3n 2 ln(3mn) + ln 4(ln(3mn)) 2 ln 2 √ n δ ln 4n δ 2 2 4 (ln(3mn)) 2 (16) ≤ ln 4n δ 2 3n 2 (17) ≤ ln 4n δ 2 3λ 2 n 2 .
In step (17) we used the following auxiliary calculations. For n ≥ 5 we have ln 2

√ n δ ln 4n δ 2 ≥ 4. From here, for n ≥ 5 we have 4(ln(3mn)) 2 ln 2 √ n δ ln 4n δ 2 ≤ (ln(3mn)) 2 . Furthermore, for x ≥ 0.5 we have

x ≥ (ln x) 2 , leading to ln(3mn) + ln (ln(3mn)) 2 ≤ 2 ln(3mn), since 3mn ≥ 0.5. Thus, the second fraction in line ( 16) is bounded by 1. In this section we compare the performance of ρ-weighted majority vote with the performance of randomized classifier defined by ρ and the performance of the best out of m weak classifiers (measured by the validation loss). The comparison is provided in Figure 9. Furthermore, in Table 4 we provide the number of hypotheses that took up 50% of the posterior mass ρ. While the performance of the randomized classifier is close to the performance of the best weak classifier, the distribution of posterior mass ρ over several classifiers improves the generalization bound and reduces the risk of overfitting when m is large. In other words, randomized classifier makes learning with large m safer. In our experiments the majority vote provided slight, but not significant improvement over the randomized classifier.

B.3. Combining the two improvements

Figure 1 :

 1 Figure 1: Prediction accuracy of PAC-Bayesian aggregation vs. cross-validated SVM across different values of m and r. The colors of the heatmap represent the difference between the zero-one loss of the ρ-weighted majority vote and the zero-one loss of the cross-validated SVM. The loss of the cross-validated SVM is given by L CV in the caption.

  (a) Ionosphere dataset. n = 200, r = d + 1 = 35. (b) Waveform dataset. n = 2000, r = d + 1 = 41. (c) Breast cancer dataset. n = 340, r = d + 1 = 11. (d ) AvsB dataset. n = 1000, r = d + 1 = 17.

Figure 2 :

 2 Figure 2: Comparison of PAC-Bayesian aggregation with RBF kernel SVM tuned by cross-validation. The solid red, black, and blue lines correspond, respectively, to the zero-one test loss of the cross-validated SVM, the loss of ρweighted majority vote, where ρ is a result of minimization of the PAC-Bayes-λ bound, and PAC-Bayes-kl bound on the loss of randomized classifier defined by ρ. The dashed black line represents the training time of PAC-Bayesian aggregation, while the red dashed line represents the training time of cross-validated SVM. The prediction accuracy and run time of PAC-Bayesian aggregation and PAC-Bayes-kl bound are given as functions of the hypothesis set size m.

Figure 3 :

 3 Figure 3: Empirical evaluation of the shape of F(λ). The blue curve represents the value of F(λ) and the red cross marks λ returned by alternating minimization.

  ) we have dropped the factor b 2 . If we would have kept it we could reduce the value of b.

  α) and K(α, β) as before. We only have to check that the conditions ln β ≥ 0.5 are satisfied and, otherwise, tune further. Note that since L(h, S) is trivially upper bounded by 1, b(β) > 1 is vacuous.

Figure 4 :

 4 Figure 4: Prediction accuracy of PAC-Bayesian aggregation vs. cross-validated SVM across different values of m and r. The colors of the heatmap represent the difference between the zero-one loss of the ρ-weighted majority vote and the zero-one loss of the cross-validated SVM. The loss of the cross-validated SVM is given by L CV in the caption.

Figure 5 :

 5 Figure 5: Comparison of PAC-Bayesian aggregation with RBF kernel SVM tuned by cross-validation. The solid red, black, and blue lines correspond, respectively, to the zero-one test loss of the cross-validated SVM, the loss of ρweighted majority vote, where ρ is a result of minimization of the PAC-Bayes-λ bound, and PAC-Bayes-kl bound on the loss of randomized classifier defined by ρ. The dashed black line represents the training time of PAC-Bayesian aggregation, while the red dashed line represents the training time of cross-validated SVM. The prediction accuracy and run time of PAC-Bayesian aggregation are given as functions of the hypothesis set size m.

Figure 8 :

 8 Figure 8: Comparison of the Alternating Minimization with Grid Search for Selection of λ. We show the loss on the test set obtained by direct minimization of λ ("Direct") and grid search ("Validate"). Error bars correspond to one standard deviation over 5 splits of the data into training, validation, and test set.

Table 1 :

 1 The following result is a straightforward adaptation of Theorem 3 to our setting. A proof sketch is provided in Appendix C. Datasets summary. |S| = n refers to the size of the training set and |T | refers to the size of the test set, d refers to the number of features. "Breast" abbreviates "Breast cancer" dataset.

		Mushrooms Skin Waveform Adult Ionosphere AvsB Haberman Breast
	|S|	2000	2000	2000	2000	200	1000	150	340
	|T|	500	500	500	500	150	500	150	340
	d	112	3	40	122	34	16	3	10

Table 2 :

 2 Average maximal values of m for which quasiconvexity was guaranteed by Theorem 5. kernel SVMs, which have super-quadratic training time. What pushes r and m up is the validation error, E ρ Lval (h, S) .

		Mushrooms Skin Waveform Adult Ionosphere AvsB Haberman Breast
	m	130	27	140	28	24	160	23	50

Acknowledgments

We thank anonymous reviewers of this and earlier versions of the manuscript for valuable feedback. We also thank Oswin Krause for suggesting the use of the term "quasiconvexity" to describe the shape of F(λ). CI and YS acknowledge support by the Innovation Fund Denmark through the Danish Center for Big Data Analytics Driven Innovation (DABAI). OW would like to thank the mathematical department of the university of Copenhagen for his guest professorship in 2015-2016.

Appendix B. Relaxation of the Sufficient Conditions in Theorem 5

In this section we propose a couple of relaxations of the conditions in Theorem 5. The first provides a possibility of tuning the intervals I 0a , I ab , and I b1 , and the second provides a slight improvement in the definition of b.

B.1. Tuning the intervals I 0a , I ab , and I b1

We recall the definition x h = L(h, S) -min h L(h, S). In Theorem 5 we have tuned a and b so that the contribution to E ρ λ [x h ] from hypotheses falling into intervals I 0a , I ab , and I b1 is equal. Obviously, this does not have to be the case. Take α ≥ 0 and β ≥ 0, such that α + β ≤ 1 and define

If we can find any pair (α, β), such that the number of hypotheses for which

n , 1 and F(λ) is strongly quasiconvex. The proof is identical to the proof of Theorem 5 with α, (1 -α -β), and β being the relative contributions to E ρ λ [x h ] from the intervals I 0a , I ab , and I b1 , respectively.

Appendix C. A Proof Sketch of Theorem 6

In this section we provide a sketch of a proof of Theorem 6. The proof is a straightforward adaptation of the proof of Theorem 3. Proof As we have already mentioned in the text, since the validation errors are (n -r) i.i.d. random variables with bias L(h), for f (h, S) = (n -r) kl( Lval (h, S) L(h)) we have E S e f (h,S) ≤ 2 √ n -r [START_REF] Maurer | A note on the PAC-Bayesian theorem[END_REF]. With this result replacing f (h, S) = n kl( L(h, S) L(h)) and E S e f (h,S) ≤ 2 √ n in the proof of Theorem 2 it is straightforward to obtain an analogue of Theorem 2. Namely, that for any probability distribution π over H that is independent of S and any δ ∈ (0, 1), with probability greater than 1 -δ over a random draw of a sample S, for all distributions ρ over H simultaneously

And from here, directly following the steps in the proof of Theorem 3, we obtain Theorem 6.

Appendix D. Additional Experiments

In this section we present figures with experimental results for UCI datasets that could not be included in the body of the paper. We also present three additional experiments.

D.1. Additional Figures for the Main Experiments

We present the outcomes of experiments in Section 6 for additional UCI datasets. Since the skin and Haberman datasets have low dimensionality (d = 3) we use r = √ n rather than r = d + 1, to get a reasonable subsample size. Figure 4 continues the plots in Figure 1, and Figure 5 continues the plots in Figure 2.

D.2. Comparison with Uniform Weighting and Best Performing Classifier

In Figures 6 and7 we compare the prediction accuracy of ρ-weighted majority vote with uniformly weighted majority vote, which is popular in ensemble learning [START_REF] Collobert | A parallel mixture of SVMs for very large scale problems[END_REF][START_REF] Valentini | Low bias bagged support vector machines[END_REF][START_REF] Claesen | EnsembleSVM: A library for ensemble learning using support vector machines[END_REF]. As a baseline the prediction accuracy of a cross-validated SVM is also shown. For the two datasets in Figure 7 we also include the prediction accuracy of SVM corresponding to the maximum value of ρ (which is the best performing SVM in the set). Due to significant overlap with the weighted majority vote, the latter graph is omitted for the datasets in Figure 6. Overall, in our setting the accuracy of ρ-weighted majority vote is comparable to the accuracy of the best classifier in the set and significantly better than uniform weighting.

D.3. Comparison of the Alternating Minimization with Grid Search for Selection of λ

In this section we present a comparison between direct minimization of the PAC-Bayes-λ bound and selection of λ from a grid using a validation set. Table 3 shows how each dataset For each λ we evaluated on the validation set the performance of the majority vote weighted by the distribution ρ(λ) defined in equation (7), and picked the one with the lowest validation error. Note that the grid search had access to additional validation data that was unavailable to the alternating minimization procedure. Figure 8 presents the results. We conclude that the bound minimization performed comparably to validation in our experiments. Table 4: The number of hypotheses that make up 50% of the posterior mass ρ.