Learning Linear and Kernel Predictors with the 0-1 Loss Function

1 Introduction

One of the main workhorses of machine learning are linear predictors, used in algorithms such as Support Vector Machines, Perceptron, Adaboost, Linear Regression and more. A linear predictor is parameterized by a vector w, and given an instance x, predicts according to 〈w, x〉. A powerful extension of linear predictors are kernel predictors, where the instances x are mapped to a high-dimensional feature space ψ(x), and a linear predictor is learned in that space. Rather than working with ψ(x) explicitly, one performs the learning implicitly using a kernel function k(x, x′ ) which efficiently computes inner products 〈ψ(x), ψ(x′ )〉 in the feature space.

For binary classification tasks, the common approach is to take the sign of 〈w, x〉 as the prediction. The natural way to quantify the performance of such a classifier is using the 0-1 loss function: for a given instance x and a true binary label y ∈ {0, 1}, we incur a loss of 1 if sgn(〈w, x〉) ̸= y, and 0 otherwise.

However, there is no efficient algorithm known for finding the linear predictor w which minimizes the number of classification errors on an arbitrary dataset. With general kernel predictors, this is aggravated by a statistical problem, namely that it is impossible to obtain generalization guarantees which relate good performance on the training data to a good performance on the distribution from which the training data was sampled.

In practice, a common solution to both problems has been to replace the non-convex 0-1 loss function by a convex surrogate, such as the hinge loss (defined as max{0, 1 - y〈w, x〉}). With respect to such loss functions, one can efficiently find the best predictor using convex optimization, as well as obtain statistical guarantees, even for general kernel predictors. However, this comes at the price of solving a somewhat different problem than what we are really after, namely minimizing classification mistakes. Worse, there is no simple way to relate these two problems for finite samples (although there do exist some recent results on the asymptotic relationship between the two [Zhang, 2004; Bartlett et al., 2006]).

In this paper, we present and analyze a simple algorithm for learning linear or kernel predictors for binary classification, with respect to the 0-1 loss function. To obtain nontrivial guarantees, the learned predictors allow themselves a small region of uncertainty (or randomness) close to the decision boundary, whose effective width is parameterized by L. We show that for any fixed L, the algorithm learns a classifier which is worse than the optimal such classifier by at most ϵ, and runs in time polynomial in ϵ. Moreover, the algorithm has the interesting property of being provably competitive not only with respect to such classifiers, but with respect to a much larger set of predictors. In addition, while our guarantees are worst-case, the runtime of the algorithm can be much smaller, depending on the data distribution. We also prove a hardness result, showing that under a certain cryptographic assumption, no algorithm can learn such classifiers in time polynomial in L.

2 Preliminaries

Following the standard statistical learning framework, we assume that there is an unknown distribution D over the set of labeled examples, X ×{0, 1}, and our primary goal is to find a classifier, h : X → {0, 1}, with low error in expectation

Karthik Sridharan

Toyota Technological Institute

karthik@tti-c.org over D:

The learning algorithm is allowed to sample a training set of labeled examples, (x1, y1), . . . , (xm, ym), where each example is sampled i.i.d. from D, and it returns a classifier. Following the agnostic PAC learning framework [Kearns et al., 1992], we say that an algorithm (ϵ, δ)-learns a concept class H of classifiers using m examples, if with probability at least 1 - δ over a random choice of m examples, the algorithm returns a classifier ˆh that satisfies

We note that ˆh does not necessarily belong to H. Namely, we are concerned with improper learning, which is as useful as proper learning for the purpose of deriving good classifiers. A common learning paradigm is the Empirical Risk Minimization (ERM) rule, which returns a classifier that minimizes the average error over the training set,

The class of classifiers discussed in the introduction, also known as halfspaces, is defined as follows. Let X be the set of all vectors in the unit ball. Let φ0-1 : R → R be the function φ0-1(a) = 1(a ≥ 0) = 12 (sgn(a) + 1). The class of halfspaces is the set of classifiers

If X lives in an n-dimensional Euclidean space, then standard learning-theoretic results allow us to obtain a guarantee of the form (2) using the ERM learning rule (Equation (3)). The size of the required training data scales linearly with n. However, with kernel predictors, which maps data to a high or even infinite-dimensional space, we must use a different class in order to obtain a guarantee of the form given in Equation (2).

One way to define a slightly different concept class is to approximate the non-continuous function, φ0-1, with a Lipschitz continuous function, φ : R → [0, 1], which is often called a transfer function. For example, we can use a sigmoidal transfer function

which is a L-Lipschitz function. An illustration of this transfer function is given in Figure 1. Analogously to the definition of Hφ0-1 , for a general transfer function φ we define Hφ to be the set of predictors x ↦→ φ(〈w, x〉). Since now the range of φ is not {0, 1} but rather the entire interval [0, 1], we interpret φ(〈w, x〉) as the probability to output the label 1. The definition of errD(h) remains 1 as in Equation (1).

The advantage of using a L-Lipschitz transfer function is that one can obtain learning guarantees which depend only on

1 Note that in this case errD(h) can be interpreted as P(x,y)∼D,b∼φ(〈w,x〉)[y ̸=b].

(ϵ, δ) and L, rather than the dimensionality of the data. For example, based on techniques form [Bartlett and Mendelson, 2002], one can show the following:

Theorem 1 Let ϵ, δ ∈ (0, 1) and let φ be an L-Lipschitz transfer function. Let m be an integer satisfying

Then, for any distribution D over X × {0, 1}, the ERM algorithm (ϵ, δ)-learns the concept class Hφ using m examples.

The above theorem tells us that the sample complexity of learning Hφ is ˜Ω(L2 /ϵ2 ), regardless of the dimensionality of X . This allows us to learn with kernels, when the dimensionality of X can even be infinite.

From the computational complexity point of view, the result given in Theorem 1 is problematic, since the ERM algorithm should solve the non-convex optimization problem

The main focus of this paper is the derivation and analysis of a simple learning algorithm that (ϵ, δ)-learns the class Hsig using time and sample complexity which is polynomial for any fixed L.

3 Main Results

In this section we present our main results. Recall that we would like to derive an algorithm which learns the class Hsig. However, the ERM optimization problem associated with Hsig is non-convex. The main idea behind our construction is to learn a larger hypothesis class, denoted HB, which approximately contains Hsig, and for which the ERM optimization problem becomes convex. The price we need to pay is that from the statistical point of view, it is more difficult to learn the class HB than the class Hsig, therefore the sample complexity increases.

The class HB we use is a class of kernel predictors. The kernel function we use is defined as

where ν ∈ (0, 1) is a parameter. If our original learning problem pertained to linear predictors, then 〈x, x′ 〉 is the standard inner product between vectors in Euclidean space. If our original learning problem pertained to kernel predictors, then 〈x, x′ 〉 is the kernel inner product. For example, if we wish to learn kernel predictors using the Gaussian kernel, defined as k(x, x′ ) = exp(-‖x-x′ ‖2 /σ2 ), then the kernel function we will use to learn with respect to the 0-1 loss is 1/(1 - ν exp(- ‖x - x′ ‖2 /σ2 )).

To simplify the presentation we will set ν = 1/2, although in practice other choices might be more effective. It is easy to verify that K is a valid kernel function (see for example [Cristianini and Shawe-Taylor, 2004]). Therefore, there exists some feature mapping ψ : X → V, where V is an inner product space with 〈ψ(x), ψ(x′ )〉 = K(x, x′ ). The class HB is defined to be:

The algorithm we present and analyze is straightforward: first, it uses the ERM learning rule and finds the kernel predictor v ∈ V which minimizes the average absolute value of its mis-predictions on the training data:

Since the objective function is defined only via inner products with ψ(xi), and the constraint on v is defined by the ℓ2-norm, it follows by standard results that there is an optimal solution v⋆ that can be written as v⋆ = ∑mi=1 αiψ(xi). Therefore, instead of optimizing over v, we can optimize over the set of weights α1, . . . , αm by solving the equivalent optimization problem

and defining the predictor x ↦→ 〈v, x〉 to be x ↦→ ∑mi=1 K(xi, x). We note that this optimization problem is convex and can be solved efficiently (i.e. in time poly(m)) by any of several possible methods.

After finding this v, the algorithm constructs and returns the following randomized binary classifier: Given an instance x, the classifier predicts 1 with probability [〈v, ψ(x)〉][0,1] (where [·][0,1] clips values to the range [0, 1]), and 0 otherwise.

The main result we prove in this section is the following:

Theorem 2 Let ϵ, δ ∈ (0, 1) and let L ≥ 3. Let B = 2L4 + exp (7L log ( 2L ϵ ) + 3) and let m be a sample size that satisfies m ≥ 8B ϵ2 (2+9√ln(8/δ))2 . Then with probability at least 1 - δ, the predictor ˆh returned by the algorithm satisfies

As discussed earlier, our algorithm runs in time polynomial in the sample size, and thus runs in time poly(1/ϵ) for any fixed L. We note that the bound on B is far from being the tightest possible in terms of constants and second-order terms. Also, the assumption of L ≥ 3 is rather arbitrary, and is meant to simplify the presentation of the bound.

The algorithm and accompanying analysis has two important properties: first, the classifier returned by the algorithm is near-optimal not only with respect to the class of linear (or kernel) predictors Hφ0-1 , but also with respect to the class HB, which contains a much larger set of transfer functions (see Lemma 1 below). In particular, it is near-optimal with respect to the "best" transfer function in HB, where by best we mean the one which attains the smallest error rate over the distribution D. A second important property is that the runtime of our algorithm depends on the parameter B, for which the bound in Theorem 2 is only a worst-case bound over any possible distribution. Since in practice B is chosen via crossvalidation, it is plausible that in many real-world scenarios the runtime of our algorithm will be much smaller.

To prove Theorem 2, we start with analyzing the time and sample complexity of learning HB. A standard analysis (using tools from [Bartlett and Mendelson, 2002]) tells us that the sample complexity of learning HB with the ERM rule is order of B/ϵ2 examples:

Theorem 3 Let ϵ, δ ∈ (0, 1), let B ≥ 1, and let m be a sample size that satisfies

Then, for any distribution D, the ERM algorithm (ϵ, δ)-learns HB .

Next, as discussed earlier, we note that the ERM problem with respect to HB (namely, optimizing Equation (8) or equivalently Equation (9)) can be solved in time poly(m).

It is left to understand why the class HB approximately contains the class Hsig. Recall that for any transfer function, φ, we define the class Hφ to be all the predictors of the form x ↦→ φ(〈w, x〉). The first step is to show that HB contains the union of Hφ over all polynomial transfer functions that satisfy a certain boundedness condition on their coefficients.

Lemma 1 Let PB be the following set of polynomials (possibly with infinite degree)

Proof To simplify the proof, we will assume that X is simply the unit ball in Rn (the case of kernel predictors can be proven similarly), for an arbitrarily large but finite n. Consider the mapping ψ : X → RN defined as follows: for any x ∈ X, we let ψ(x) be an infinite vector, indexed by k1 . . . , kj for all (k1, . . . , kj) ∈ {1, . . . , n}j and j = 0 . . .∞, where the entry at index k1 . . . , kj equals 2-j/2xk1 · xk2 · · · xkj . The innerproduct between ψ(x) and ψ(x′ ) for any x, x′ ∈ X can be calculated as follows,

This is exactly the kernel function defined in Equation (6) (recall that we set ν = 1/2) and therefore ψ maps to the feature space defined by K. Consider any polynomial p(a) = ∑∞j=0 βjaj in PB, and any w ∈ X. Let vw be an element in RN explicitly defined as being equal to βj2j/2wk1 · · · wkj at index k1, . . . , kj (for all k1, . . . , kj ∈ {1, . . . , n}j , j = 0 . . .∞). By definition of ψ and vw, we have that

Similarly, it can be verified that

Thus, the predictor x ↦→ 〈vw, ψ(x)〉 belongs to HB and is the same as the predictor x ↦→ p(〈w, x〉). This proves that Hp ⊂ HB for all p ∈ PB as required.

Finally, the following lemma states that with a sufficiently large B, there exists a polynomial in PB which approximately equals φsig. This implies that HB approximately contains Hsig .

Lemma 2 Let φsig be as defined in Equation (4), where for simplicity we assume L ≥ 3. For any ϵ > 0, let

Then there exists p ∈ PB such that

The proof of the lemma is based on a Chebyshev approximation technique and is given in the full version of our paper [Shalev-Shwartz et al., 2010].

Finally, Theorem 2 is obtained as follows: Combining Theorem 3 and Lemma 1 we get that with probability at least 1 - δ,

From Lemma 2 we obtain that for any w ∈ X, if h(x) = φsig(〈w, x〉) then there exists a polynomial p0 ∈ PB such that if h′ (x) = p0(〈w, x〉) then errD(h′ ) ≤ errD(h) + ϵ/2. Since it holds for all w, we get that

Combining this with Equation (11), and using the fact that clipping predictions to [0, 1] can only decrease the error, Theorem 2 follows.

4 Hardness

In this section, we derive a hardness result for distributionfree learning of Hsig with respect to the 0-1 loss. The hardness result relies on the hardness of learning intersections of halfspaces in the standard PAC model 2 , proven by [Klivans and Sherstov, 2006]. The hardness result is representationindependent -it makes no restrictions on the learning algorithm and in particular also holds for improper learning algorithms. The hardness result is based on the following cryptographic assumption:

Assumption 1 There is no polynomial time solution to the ˜O(n1.5 )-unique-Shortest-Vector-Problem.

In a nutshell, given a basis v1, . . . , vn ∈ Rn , the ˜O(n1.5 )- unique-Shortest-Vector-Problem consists of finding the shortest nonzero vector in {a1v1 + . . . +anvn : a1, . . . , an ∈ Z}, even given the information that it is shorter by a factor of at least ˜O(n1.5 ) than any other non-parallel vector. This problem is believed to be hard - there are no known subexponential algorithms, and it is known to be NP-hard if ˜O(n1.5 ) is replaced by a small constant (see [Klivans and Sherstov, 2006] for more details).

Our hardness result is the following:

Theorem 4 Let L be a Lipschitz constant and let Hsig be the class defined by the L-Lipschitz transfer function φsig. Then, based on Assumption 1, there is no algorithm that runs in time poly(L, 1/ϵ, 1/δ) and (ϵ, δ)-learns the class Hsig.

Proof

With assumption 1, [Klivans and Sherstov, 2006] proved the following:

Theorem 5 (Theorem 1.2 in [Klivans and Sherstov, 2006]) Let X = {±1}n , let H = {x ↦→ φ0,1(〈w, x〉 - θ - 1/2) : θ ∈ N,w ∈ Nn , |θ| + ‖w‖1 ≤ poly(n)}, and let Hk = {x ↦→ (h1(x) ∧ . . . ∧ hk(x)) : ∀i, hi ∈ H}. Then, based on Assumption 1, Hk is not efficiently learnable in the standard PAC model for any k = nρ where ρ > 0 is a constant.

2 In the standard PAC model, we assume that some hypothesis in the class has errD(h) = 0, while in our setting, errD(h) might be strictly greater than zero for all h ∈ H.

The above theorem implies the following.

Lemma 3 Based on Assumption 1, there is no algorithm that runs in time poly(n, 1/ϵ, 1/δ) and (ϵ, δ)-learns the class H defined in Theorem 5.

Proof To prove the lemma we show that if there is a polynomial time algorithm that learns H in the agnostic model, then there exists a weak learning algorithm (with a polynomial edge) that learns Hk in the standard (non-agnostic) PAC model. In the standard PAC model, weak learning implies strong learning [Schapire, 1990], hence the existence of a weak learning algorithm that learns Hk will contradict Theorem 5.

Indeed, let D be any distribution such that there exists h⋆ ∈ Hk with errD(h⋆ ) = 0. Let us rewrite h⋆ = h⋆1 ∧ . . . ∧ h⋆k where for all i, h⋆i ∈ H. To show that there exists a weak learner, we first show that there exists some h ∈ H with errD(h) ≤ 1/2 - 1/2k2 .

Since for each x if h⋆ (x) = 0 then there exists j s.t. h⋆j (x) = 0, we can use the union bound to get that

So, for j that maximizes P[h⋆j (x) = 0|h⋆ (x) = 0] we get that P[h⋆j (x) = 0|h⋆ (x) = 0] ≥ 1/k. Therefore,

Now, if P[h⋆ (x) = 0] ≤ 1/2 + 1/k2 then the above gives

where the inequality holds for any positive integer k. Otherwise, if P[h⋆ (x) = 0] > 1/2 + 1/k2 , then the constant predictor h(x) = 0 has errD(h) < 1/2 - 1/k2 . In both cases we have shown that there exists a predictor in H with error of at most 1/2 - 1/2k2 .

Finally, if we can agnostically learn H in time poly(n, 1/ϵ, 1/δ), then we can find h′ with errD(h′ ) ≤ minh∈H errD(h) + ϵ ≤ 1/2 - 1/2k2 + ϵ in time poly(n, 1/ϵ, 1/δ) (recall that k = nρ for some ρ > 0). This means that we can have a weak learner that runs in polynomial time, and this concludes our proof.

We now turn to prove Theorem 4 itself. Let h be a hypothesis in the class H defined in Theorem 5 and take any x ∈ {±1}n . Then, there exist an integer θ and a vector of integers w such that h(x) = φ0,1(〈w, x〉 - θ - 1/2). However, since 〈w, x〉 - θ is also an integer, we see that

This means that for any ϵ > 0, if we pick L = log(2/ϵ-1) 2 and define hsig(x) = φsig(〈w, x〉 - θ - 1/2), then |h(x) - hsig(x)| ≤ ϵ/2. Furthermore, letting x′ ∈ Rn+1 denote the

.

concatenation of x with the constant 1 and letting w′ ∈ Rn+1 denote the concatenation of w with the scalar (-θ - 1/2) we obtain that hsig(x) = φsig(〈w′ , x′ 〉). Last, let us normalize ˜w =w′ /‖w′ ‖, ˜x = x/‖x′ ‖, and redefine L to be

so that hsig(x) = φsig(〈 ˜w, ˜x〉). Thus we see that if there exists an algorithm that runs in time poly(L, 1/ϵ, 1/δ) and (ϵ/2, δ)-learns the class Hsig, then since for all h ∈ H exists hsig ∈ Hsig such that |hsig(x) - h(x)| ≤ ϵ/2, there also exists an algorithm that (ϵ, δ)-learns the concept class H defined in Theorem 5 in time polynomial in (L, 1/ϵ, 1/δ) (for L defined in Equation 12). But by definition of L in Equation 12 and the fact that ‖w′ ‖ and ‖x′ ‖ are of size poly(n), this means that there is an algorithm that runs in time polynomial in (n, 1/ϵ, 1/δ) and (ϵ, δ)-learns the class H, which contradicts Lemma 3.

5 Related work

The problem of learning linear and kernel predictors has been extensively studied before, mainly in the framework of Support Vector Machines [Vapnik, 1998; Cristianini and ShaweTaylor, 2004; Sch¨olkopf and Smola, 2002]. In the special case where the data is separable (namely, there exists a predictor w such that y〈w, x〉 ≥ 0 for any example (x, y)), it is possible to learn a predictor in polynomial time, say by using linear programming. The learning problem becomes much more difficult when the data is not separable.

A paper closely related to ours is [Ben-David and Simon, 2000], whose techniques can be adapted to develop an exhaustive-search algorithm for our problem, whose runtime is poly (exp ( L2 ϵ2 log( Lϵ ))). In comparison, the runtime of our algorithm is exponentially smaller. Moreover, the algorithm of [Ben-David and Simon, 2000] performs an exhaustive search over all (L/ϵ)2 subsets of the m examples in the training set, and therefore its runtime is always order of mL2 /ϵ2 . In contrast, our algorithm's runtime depends on a parameter B, which is bounded by exp(L) only under a worst-case assumption. Depending on the underlying distribution, B can be much smaller than the worst-case bound. In practice, we will cross-validate for B, and therefore the worst-case bound will often be pessimistic.

Another related line of work has been learning of linear predictors with respect to the 0-1 loss function, but making distributional assumptions on the data. For instance, [Kalai et al., 2005] show that when the distribution over X ⊆ is uniform, and assuming it is a subset of Rn , then it is possible to learn in time poly(n1/ϵ4 ). This was further generalized by [Blais et al., 2008], who showed that similar bounds hold for product distributions. However, such distributional assumptions are not very realistic. Moreover, these works are characterized by explicit dependence on the dimension of X , and therefore are not adequate for the kernel-based setting we consider in this paper, in which the dimensionality of X can even be infinite. Interestingly, in [Shalev-Shwartz et al.,

2009] we show that the very same algorithm we use in this paper recovers the same complexity bound of [Kalai et al., 2005].

In terms of hardness results, there exist strong results on hardness of proper learning, where the learning algorithm must return a linear predictor (e.g. [Guruswami and Raghavendra, 2006; Ben-David and Simon, 2000] and references therein). We emphasize that we allow improper learning, which is just as useful for the purpose of learning good classifiers, and thus these hardness results do not apply.

6 Discussion

In this paper we described and analyzed a new technique for agnostically learning linear and kernel predictors with the 0-1 loss function. The bound we derive is polynomial for any fixed L, the Lipschitz coefficient of the transfer function. While we prove that (under a certain cryptographic assumption) no algorithm can have a polynomial dependence on L, the immediate open question is whether the dependence on L can be further improved.

A perhaps surprising property of our analysis is that we propose a single algorithm, returning a single classifier, which is simultaneously competitive against all transfer functions p ∈ PB. In particular, it learns with respect to the "optimal" transfer function, where by optimal we mean the one which attains the smallest error rate, E[|p(〈w, x〉) - y|], over the distribution D.

Our algorithm boils down to a simple ERM algorithm using a particular kernel function. In fact, it is possible to show that the standard Support Vector Machine algorithm, using the hinge-loss and our particular kernel, can also give similar guarantees. It is therefore interesting to study if there is something special about the kernel we propose or maybe other kernel functions (e.g. the Gaussian kernel) can give similar guarantees.

Acknowledgments

We would like to thank Adam Klivans for helping with the Hardness results. Shai Shalev-Shwartz is supported by the Israeli Science Foundation grant number 598-10.