Using More Data to Speed-up Training Time

Introduction

Machine learning are now prevalent in a large range of scientific, engineering and every-day tasks, ranging from analysis of genomic data, through vehicle and aircraft control to locating information on the web and providing users with personalized recommendations. Meanwhile, our world has become increasingly “digitized” and the amount of data available for training is dramatically increasing. By now, we have a rather clear understanding of how more data can be used to improve the accuracy of learning algorithms. In this paper we study how more data can be beneficiary for constructing more efficient learning algorithms.

Roughly speaking, one way to show how more data can reduce the training runtime is as follows. Consider learning by finding a hypothesis in the hypothesis class that minimizes the training

error. In many situations, this search problem is computationally hard. One can circumvent the hardness by replacing the original hypothesis class with a different (larger) hypothesis class, such that the search problem in the larger class is computationally easier (e.g., the search problem in the new hypothesis class reduces to a convex optimization problem). On the flip side, from the statistical point of view, the estimation error in the new hypothesis class might be larger than the estimation error in the original class, and thus, with a small number of examples, learning the larger class might lead to overfitting even though the same amount of examples suffices for the original hypothesis class. However, having more training examples keeps the overfitting in check. In particular, if the number of extra examples we need for learning the new class is only polynomially larger than the original number of examples, we end up with an efficient algorithm for the original problem. If, however, we don’t have those extra examples, our only option is to learn the original hypothesis class, which may be computationally harder.

The goal of this paper is to present a formal model for studying the runtime of learning algorithms as a function of the available number of examples. After defining the formal model, we present a binary classification learning problem for which we can provably (based on standard cryptographic assumption) demonstrate an inverse dependence of the runtime on the number of examples. While there have been previous constructions which demonstrated a similar phenomenon, assuming the existence of a “perfect” hypothesis, we show this in the much more natural agnostic model of learning. A possible criticism is that our learning problem is still rather synthetic. We continue with presenting several learning problems, which arise in natural settings, that have more efficient algorithms by relying on the availability of more training data. Some of these examples are based on the intuition of Figure 1, but some are also based on other ideas and techniques. However, for all these problems, the analysis is based on upper bounds without having matching lower bounds. This raises several interesting open problems.

were the first to jointly study the computational and sample complexity, and to show that a tradeoff between runtime and sample size exists. In particular, they distinguish between the information theoretic sample complexity of a class and its computational sample complexity, the latter being the number of examples needed for learning the class in polynomial time. They presented a learning problem which is not efficiently learnable from a small training set, and is efficient learnable from a polynomially larger training set. showed that for a concept class composed of $1$-decision-lists over $\{0,1\}^{n}$, which can be learned inefficiently using $O(1)$ examples, no algorithm can learn it efficiently using $o(n)$ examples, and there is an efficient algorithm using $\Omega(n)$ examples. The construction was also extended to $k$ decision-lists, $k\geq 1$. with larger gaps.

In contrast to , which focused on learning under the realizable case (namely, that the labels are generated by some hypothesis in the class), we mostly focus on the more natural agnostic setting, where any distribution over the example domain is possible, and there may be no hypothesis $h$ in our class that never errs. This is not just a formality - in both , the construction crucially relies on the fact that the labels are provided by some hypothesis in the class. In terms of techniques, we rely on the cryptographic assumption that one-way permutations exist, which is the same assumption as in and similar to the assumption in . We note that cryptographic assumptions are common in proving lower bounds for efficient learnability, and in some sense they are even necessary . However, our construction is very different. For example, in both , revealing information on the identity of the “correct” hypothesis is split among many different examples. Therefore, efficient learning is possible after sufficiently many examples are collected, which then allows us to return the “correct” hypothesis. In our agnostic setting, there is no “correct” hypothesis, so this kind of approach cannot work. Instead, our efficient learning procedure computes and returns an improper predictor, which is not in the hypothesis class at all.

A potential weaknesses of our example, as well as the example given in , is that our hypothesis class does not consist of “natural” hypotheses. The class employed in is more natural, but it is also a very carefully constructed subset of decision lists. The goal of the second part of the paper is to demonstrate gaps (though based on upper bounds) for natural learning problems.

Another contribution of our model is that it captures the exact tradeoff between sample and computational complexity rather then only distinguishing between polynomial and non-polynomial time, which may not be refined enough. Bottou and Bousquet initiated a study on learning in the data laden domain – a scenario in which data is plentiful and computation time is the main bottleneck. This is the case in many real life applications nowadays. Shalev-Shwartz and Srebro continued this line of research and showed how for the problem of training Support Vector Machines, a joint statistical-computational analysis reveals how the runtime of stochastic-gradient-descent can potentially decrease with the number of training examples. However, this is only demonstrated via upper bounds. More importantly, the advantage of having more examples only improves running time by constant factors. In this paper, we will be interested in larger factors of improvement, which scale with the problem size.

Formal Model Description

A learning algorithm, $A$, receives a training set of $m$ examples, $S_{m}=(({\mathbf{x}}_{1},y_{1}),\ldots,({\mathbf{x}}_{m},y_{m}))$, which are assumed to be sampled i.i.d. from an unknown distribution $\mathcal{D}$ over the problem domain $\mathcal{Z}\subseteq\mathcal{X}\times\mathcal{Y}$. Using the training data, together with any prior knowledge or assumptions about the distribution $\mathcal{D}$, the learner forms a prediction rule. The predictor is a random variable and we denote it by $A(S_{m})$. The goal of the learner is to find a prediction rule with low generalization error (a.k.a. risk), defined as the expected loss:

where when no $t$ satisfies the above constraint we set $T_{\mathcal{H},\epsilon}(m)=\infty$. Thus, $T_{\mathcal{H},\epsilon}(m)$ measures the required runtime to learn the class $\mathcal{H}$ with an excess error of $\epsilon$ given a budget of $m$ training examples. Studying this function can show us how more data can be used to decrease the required runtime of the learning algorithm. The minimum value of $m$ for which $T_{\mathcal{H},\epsilon}(m)<\infty$ is the information-theoretic sample complexity. This corresponds to the case in which we ignore computation time. The other extreme case is the value of $T_{\mathcal{H},\epsilon}(\infty)$. This corresponds to the data laden domain, namely data is plentiful and computation time is the only bottleneck.

To illustrate how more data can reduce runtime, consider the problem of learning the class of $3$-term disjunctive normal form (DNF) formulas in the realizable case. A $3$-DNF is a Boolean mapping, $h:\{0,1\}^{d}\to\{0,1\}$, that can be written as $h({\mathbf{x}})=T_{1}({\mathbf{x}})\lor T_{2}({\mathbf{x}})\lor T_{3}({\mathbf{x}})$, where for each $i$, $T_{i}({\mathbf{x}})$ is a conjunction of an arbitrary number of literals, e.g. $T_{i}({\mathbf{x}})=x_{1}\land\lnot x_{3}\land x_{5}\land\lnot x_{7}$.

It is important to emphasize that the analysis above is not satisfactory for two reasons. First, we do not know if it is not possible to improperly learn $3$-DNFs in polynomial time using $O(d/\epsilon)$ examples. All we know is that the ERM approach is not efficient. Second, we do not know if the information theoretic sample complexity of learning conjunctions over $\psi({\mathbf{x}})$ is $\Omega(d^{3}/\epsilon)$. Maybe the specific structure of the range of $\psi$ yields a lower sample complexity.

But, if we do believe that the above analysis indeed reflects reality, we obtain two points on the curve $T_{\mathcal{H},\epsilon}(m)$. Still, we do not know how the rest of the curve looks like. This is illustrated below.

Formal derivation of gaps

In this section, we formally show a learning problem which exhibits an inverse dependence of the runtime on the number of examples. As discussed in the Subsection 1.1, it is distinguished from previous work in being applicable to the natural agnostic setting, where we do not assume that a perfect hypothesis exist. Since this assumption was crucial in all previous works, the construction we use is rather different.

To present the result, we will need the concept of a one-way permutation. Intuitively, a one-way permutation over $\{0,1\}^{n}$ is a permutation which is computationally hard to invert. More formally, let $\mathcal{U}_{n}$ denote the uniform distribution over $\{0,1\}^{n}$, and let $\{0,1\}^{*}$ denote the set of all finite bit strings. Then we have the following definition:

A one-way permutation $P:\{0,1\}^{*}\mapsto\{0,1\}^{*}$ is a function which for any $n$, maps $\{0,1\}^{n}$ to itself; there exists an algorithm for computing $P({\mathbf{x}})$, whose runtime is polynomial in the length of ${\mathbf{x}}$; and for any (possibly randomized) polynomial-time algorithm $A$ and any polynomial $p(n)$ over $n$, $\Pr_{{\mathbf{x}}\sim\mathcal{U}_{n}}(A(P({\mathbf{x}}))={\mathbf{x}})<\frac{1}{p(n)}$ for sufficiently large $n$.

It is widely conjectured that such one-way permutations exist. One concrete candidate is the RSA permutation function, which treats ${\mathbf{x}}\in\{0,1\}^{n}$ as a number in $\{0,\ldots,2^{n}-1\}$, and returns $P({\mathbf{x}})={\mathbf{x}}^{3}~\text{mod}~N$, where $N$ is a product of two “random” primes of length $n$ such that $(p-1)(q-1)$ does not divide $3$. However, since the existence of such a one-way permutation would imply $P\neq NP$, there is no formal proof that such functions exist (see for this and related results).

There exists an agnostic binary classification learning problem over $\mathcal{X}=\{0,1\}^{2n}$ and $\mathcal{Y}=\{0,1\}$ with the following properties:

It is inefficiently learnable with sample size $m=O(1/\epsilon)$, and running time $O(2^{n}+m)$.

Assuming one-way permutations exist, there exist no polynomial-time algorithm based on a sample of size $O(\log(n))$.

It is efficiently learnable with a sample of size $m=O(n/\epsilon^{2})$. Specifically, the training time is $O(m)$, resulting in an improper predictor whose runtime is $O(m^{3})$.

The theorem implies that in the reasonable regime where $1/\epsilon\leq\log(n)\leq n/\epsilon^{2}$, we really get an inverse dependence of the runtime on the training size. The theorem is illustrated below:

The hypothesis class $\mathcal{H}$ consists of randomized functions, parameterized by $\{0,1\}^{n}$, and defined as follows, where $\mathcal{U}_{1}$ is the uniform distribution on $\{0,1\}$:

Inefficient Distribution-Free Learning Possible with O⁡(1/ϵ)O(1/\epsilon) Samples

Ignoring computational constraints, we can use the following simple learning algorithm: given a training sample $\{({\mathbf{r}}_{i},{\mathbf{s}}_{i}),b_{i}\}_{i=1}^{m}$, find the most common value ${\mathbf{s}}^{\prime}$ among ${\mathbf{s}}_{1},\ldots,{\mathbf{s}}_{m}$, compute ${\mathbf{x}}^{\prime}=P^{-1}({\mathbf{s}}^{\prime})$ (inefficiently, say by exhaustive search), and return the hypothesis $h_{{\mathbf{x}}^{\prime}}$.

To see why this works, we will need the following lemma, which shows that if $h_{{\mathbf{x}}}$ has a low error rate, then ${\mathbf{s}}=P({\mathbf{x}})$ is likely to appear frequently in the examples (the proof appears in Appendix A).

Efficient Distribution-Free Learning Possible with O⁡(n/ϵ2)O(n/\epsilon^{2}) Samples

We will need the following lemma, whose proof appears in Appendix A:

Let $\mathcal{D}^{\prime}$ be some distribution over $\{0,1\}^{n}$, and suppose we sample $m^{\prime}$ vectors ${\mathbf{r}}_{1},\ldots,{\mathbf{r}}_{m^{\prime}}$ from that distribution. Then the probability that a freshly drawn vector ${\mathbf{r}}$ is not spanned by ${\mathbf{r}}_{1},\ldots,{\mathbf{r}}_{m^{\prime}}$ is at most $n/m^{\prime}$.

We use a similar algorithm to the one discussed earlier for inefficient learning. However, instead of finding the most common ${\mathbf{s}}^{\prime}$, computing ${\mathbf{x}}^{\prime}=P^{-1}({\mathbf{s}}^{\prime})$ and returning $h_{{\mathbf{x}}^{\prime}}$, which cannot be done efficiently, we build a predictor which is at most $\epsilon$ worse than $h_{{\mathbf{x}}^{\prime}}$, and doesn’t require us to find ${\mathbf{x}}^{\prime}$ explicitly.

To do so, let $\{(({\mathbf{r}}_{i_{j}},{\mathbf{s}}_{i_{j}}),b_{i_{j}})\}_{j=1}^{m^{\prime}}$ be the subset of examples for which ${\mathbf{s}}_{i_{j}}={\mathbf{s}}^{\prime}$. By definition of $\mathcal{Z}$, we know that for any such example, $\langle{\mathbf{x}}^{\prime},{\mathbf{r}}_{i_{j}}\rangle=\langle P^{-1}({\mathbf{s}}^{\prime}),{\mathbf{r}}_{i_{j}}\rangle=b_{i_{j}}$. In other words, this gives us a set of values ${\mathbf{r}}_{i_{1}},\ldots,{\mathbf{r}}_{i_{m^{\prime}}}$, for which we know $\langle{\mathbf{x}}^{\prime},{\mathbf{r}}_{i_{1}}\rangle,\ldots,\langle{\mathbf{x}}^{\prime},{\mathbf{r}}_{i_{m^{\prime}}}\rangle$. As a consequence, for any ${\mathbf{r}}$ in the linear subspace spanned by ${\mathbf{r}}_{i_{1}},\ldots,{\mathbf{r}}_{i_{m^{\prime}}}$, we can efficiently compute $\langle{\mathbf{x}}^{\prime},{\mathbf{r}}\rangle$. Let $B$ denote this subspace. Then our improper predictor works as follows, given some instance $({\mathbf{r}},{\mathbf{s}})$:

If ${\mathbf{s}}={\mathbf{s}}^{\prime}$ and ${\mathbf{r}}\in B$, output $\langle{\mathbf{x}}^{\prime},{\mathbf{r}}\rangle$ (note that this is the same output as $h_{{\mathbf{x}}^{\prime}}$, by definition).

If ${\mathbf{s}}\neq{\mathbf{s}}^{\prime}$, output a random bit (note that this is the same output as $h_{{\mathbf{x}}^{\prime}}$, by definition of $h_{{\mathbf{x}}^{\prime}}$).

If ${\mathbf{s}}={\mathbf{s}}^{\prime}$ and ${\mathbf{r}}\notin B$, output a bit uniformly at random.

Note that checking whether ${\mathbf{r}}\in B$ can always be done in at most $O(m^{\prime 3})\leq O(m^{3})$ time, via Gaussian elimination.

Now, we claim that the probability of the third case happening is at most $\epsilon/2$. If this is indeed true, then our improper predictor is only $\epsilon/2$ worse (in terms of generalization error) from $h_{{\mathbf{x}}^{\prime}}$, which based on the argument in the previous section, is already $\epsilon$-close to optimal.

So let us consider the possibility that ${\mathbf{s}}={\mathbf{s}}^{\prime}$ and $r\notin B$. If $\Pr_{{\mathbf{s}}}({\mathbf{s}}={\mathbf{s}}^{\prime})\leq\epsilon$, we are done, so let us suppose that $\Pr_{{\mathbf{s}}}({\mathbf{s}}={\mathbf{s}}^{\prime})>\epsilon$. This means that $m^{\prime}$ is unlikely to be much smaller than $\epsilon m$. More precisely, by the multiplicative Chernoff bound, $\Pr(m^{\prime}<\epsilon m/2)\leq\exp(-\epsilon m/8)$. Also, conditioned on some fixed $m^{\prime}\geq\epsilon m/2$, Lemma 2 assures us that $\Pr({\mathbf{r}}\notin B|{\mathbf{s}}={\mathbf{s}}^{\prime})\leq n/m^{\prime}\leq 2n/\epsilon m$. Overall, we get the following (the probabilities are over the draw of the training set and an additional example $(({\mathbf{r}},{\mathbf{s}}),b)$):

By taking $m=O(n/\epsilon^{2})$ examples, we can ensure this to be at most order $\epsilon$.

Gaps for natural learning problems

In this section we collect examples of natural learning problems in which we conjecture there is an inverse dependence of the training time on the sample size. Some of these examples already appeared explicitly in previous literature, but most are new, unpublished, or did not appear in such an explicit form. We base our inverse dependence conjecture on the current best known upper bounds. Of course, an immediate open question is to show matching lower bounds. However, our main goal here is to demonstrate general techniques of how to reduce the training runtime by requiring more examples.

Consider the set $[d]=\{1,\ldots,d\}$, and let $\mathcal{X}=[d]\times[d]$ and $\mathcal{Y}=\{0,1\}$. That is, each example is a pair $(i,j)$ and the label indicates whether $i$ is more preferable to $j$.

On the other hand, in the following we show that with $m=\Theta(d^{2}/\epsilon^{2})$ it is possible to learn preferences in time $O(m)$. The idea is to define the hypothesis class of all Boolean functions over $\mathcal{X}$, namely, $H_{1}=\{H(i,j)=M_{i,j}:M\in\{0,1\}^{d^{2}}\}$. Clearly, $H\subset H_{1}$. In addition, $|H_{1}|=2^{d^{2}}$ and therefore the sample complexity of learning $H_{1}$ using the ERM rule is $O(d^{2}/\epsilon^{2})$. Last, it is easy to verify that solving the ERM problem can be easily done in time $O(m)$. So, overall, we obtain the following:

2 Agnostic Learning of Kernel-based Halfspaces

We now consider the popular class of kernel-based linear predictors. In kernel predictors, the instances ${\mathbf{x}}$ are mapped to a high-dimensional feature space $\psi({\mathbf{x}})$, and a linear predictor is learned in that space. Rather than working with $\psi({\mathbf{x}})$ explicitly, one performs the learning implicitly using a kernel function $k({\mathbf{x}},{\mathbf{x}}^{\prime})$ which efficiently computes inner products $\langle\psi({\mathbf{x}}),\psi({\mathbf{x}}^{\prime})\rangle$ .

Using standard Rademacher complexity analysis (e.g. ), it is easy to see that the information theoretic sample complexity of learning $\mathcal{H}$ is $O(L^{2}/\epsilon^{2})$. However, from the computational complexity point of view, the ERM problem amounts to solving a non-convex optimization problem (with respect to ${\mathbf{w}}$). Adapting a technique due to it is possible to show that an $\epsilon$-accurate solution to the ERM problem cam be calculated in time $\exp\left(O\left(\tfrac{L^{2}}{\epsilon^{2}}\log(\tfrac{L}{\epsilon})\right)\right)$. The idea is to observe that the solution can be identified if someone reveals us a subset of $(L/\epsilon)^{2}$ non-noisy examples. Therefore we can perform an exhaustive search over all $(L/\epsilon)^{2}$ subsets of the $m$ examples in the training set and identify the best solution.

3 Additional Examples

In Appendix B we list additional examples of inverse dependence of runtime on sample size. These examples deal with other learning settings like online learning and unsupervised learning. These examples are interesting since they show other techniques to obtain faster algorithms using a larger sample. For example, we demonstrate how to use exploration for injecting structure into the problem, which leads better runtime. The price of the exploration is the need of a larger sample. For the unsupervised setting, we recall an existing example which shows polynomial gap for learning the support of a certain sparse vector.

Discussion

In this paper, we formalized and discussed the phenomena of an inverse dependence between the running time and the sample size. While this phenomena has also been discussed in some earlier works, it was under a restrictive realizability assumption, that a perfect hypothesis exists, and the techniques mostly involved finding this hypothesis. In contrast, we frame our discussion in the more modern approach of agnostic and improper learning.

In the first half of our paper, we provided a novel construction which shows such a tradeoff, based on a cryptographic assumption. While the construction indeed has an inverse dependence phenomenon, it is not based on a natural learning problem. In the second half of the paper, we provided more natural learning problems, which seem to have this phenomenon. Some of these problems were based on the intuition described in the introduction, but some were based on other techniques. However, the apparent inverse dependence in these problems is based on the assumption that the currently available upper bounds have matching lower bounds, which is not known to be true. Thus, we cannot formally prove that they indeed become computationally easier with the sample size.

Thus, a major open question is finding natural learning problems, whose required running time has provable inverse dependence with the sample size. We believe the examples we outlined hint at the existence of such problems, and provide clues as to the necessary techniques. Other problems are finding additional examples where this inverse dependence seems to hold, as well as finding additional techniques for making this inverse dependence happen. The ability to leverage large amounts of data to obtain more efficient algorithms would surely be a great asset to any machine learning application.

References

Appendix A Technical Results

Using the definition of $\mathcal{Z}$ and $h_{{\mathbf{x}}}$, we have

A.2 Proof of Lemma 2

Let $p_{k}$ denote the probability that after drawing ${\mathbf{r}}_{1},\ldots,{\mathbf{r}}_{k}$, i.i.d., an independently drawn ${\mathbf{r}}_{k+1}$ is not spanned by ${\mathbf{r}}_{1},\ldots,{\mathbf{r}}_{k}$. Also, let $B_{k}$ be a Bernoulli random variable with parameter $p_{k}$. Whenever $B_{k}=1$, the dimensionality of the subspace spanned by the vectors we drew so far increases by $1$. Since we are in an $n$-dimensional space, we must have $B_{1}+\ldots+B_{m^{\prime}}\leq n$ with probability $1$. In particular, we have

Also, for any $k\leq m^{\prime}$, by the assumption that the vectors are drawn i.i.d., we have

Combining the two inequalities, it follows that $m^{\prime}p_{m^{\prime}}\leq n$, so $p_{m^{\prime}}\leq n/m^{\prime}$ as required.

Appendix B Additional Examples

This example is based on . It deals with another variant of the multi-armed bandit problem. It shows how to use exploration for injecting structure into the problem, which leads to a decrease in the required runtime. The price of the exploration is a larger regret, which corresponds to the need of a larger number of online rounds for achieving the same target error.

The second algorithm is the Banditron of . The Banditron uses exploration for reducing the learning problem into the problem of learning multiclass classifier in the full information case, which can be performed efficiently using the Perceptron algorithm. In particular, in some of the rounds the Banditron guesses a random label, attempting to “fish” the relevant information. This exploration yields a higher regret bound of $O(\sqrt{kdT})$.

We can therefore draw the following table, which shows a tradeoff between running time and number of rounds required to obtain regret $\leq\epsilon$. Note that we will usually want $\epsilon$ to be much smaller than $1/k$.

B.2 Sparse Principal Component Recovery

This example is taken from . This time, it is in the context of unsupervised statistical learning.

provide two algorithms to deal with this problem. The first method is a simple diagonal thresholding scheme, which takes the empirical covariance matrix $\hat{\Sigma}$, and returns the $k$ indices for which the diagonal entries of $\hat{\Sigma}$ are largest. It is proven that if $m\geq ck^{2}\log(d-k)$ (for some constant $c$), then the probability of not perfectly identifying the support of ${\mathbf{z}}$ is at most $\exp(-O(k^{2}\log(d-k)))$, which goes to $0$ with $k$ and $d$. Thus, we can view the sample complexity of this algorithm as $O(k^{2}\log(d-k))$. In terms of running time, given a sample of size $m=O(k^{2}\log(d-k))$, the method requires computing the diagonal of $\hat{\Sigma}$ and sorting it, for a total runtime of $O(k^{2}d\log(d-k)+d\log(d))=O(k^{2}d\log(d))$.

The second algorithm is a more sophisticated semidefinite programming (SDP) scheme, which can be solved exactly in time $O(d^{4}\log(d))$. Moreover, the sample complexity for perfect recovery is shown to be asymptotically $O(k\log(d-k))$. Summarizing, we have the following clear sample-time complexity tradeoff. Note that here, the gaps are only polynomial.