Complexity theoretic limitations on learning DNF's

Introduction

In the PAC learning model , a learner is given an oracle access to randomly generated samples $(X,Y)\in{\cal X}\times\{0,1\}$ where $X$ is sampled from some unknown distribution ${\cal D}$ on ${\cal X}$ and $Y=h^{*}(X)$ for some unknown $h^{*}:{\cal X}\to\{0,1\}$. It is assumed that $h^{*}$ comes from a predefined hypothesis class ${\cal H}$, consisting of $0,1$ valued functions on ${\cal X}$. The learning problem defined by ${\cal H}$ is to find $h:{\cal X}\to\{0,1\}$ that minimizes $\operatorname{Err}_{{\cal D}}(h):=\Pr_{X\sim{\cal D}}(h(X)\not=h^{*}(X))$. For concreteness, we take ${\cal X}=\{\pm 1\}^{n}$, and say that the learning problem is tractable if there is an algorithm that on input $\epsilon$, runs in time $\operatorname{poly}(n,1/\epsilon)$ and outputs, w.h.p., a hypothesis $h$ with $\operatorname{Err}(h)\leq\epsilon$.

Assuming $\mathbf{P}\neq\mathbf{NP}$, the status of most basic computational problems is fairly well understood. In a sharp contrast, $30$ years after Valiant’s paper, the status of most basic learning problems is still wide open – there is a huge gap between the performance of best known algorithms and hardness results (see ). The main obstacle is the ability of a learning algorithm to return a hypothesis which does not belong to ${\cal H}$ (such an algorithm is called improper). This flexibility makes it very hard to apply reductions from $\mathbf{NP}$-hard problems (again, see ). Until recently, there was only a single framework, due to Kearns and Valiant , to prove lower bounds on learning problems. The framework of makes it possible to show that certain cryptographic assumptions imply hardness of certain learning problems. As indicated above, the lower bounds established by this method are very far from the performance of best known algorithms.

Learning intersections of $\omega(\log(n))$ halfspaces is hard, even over the boolean cube.

AgnosticallySee section 2.1 for a definition of agnostic learning. learning conjunctions is hard.

Agnostically learning halfspaces is hard, even over the boolean cube.

Agnostically learning parities is hard, even when ${\cal D}$ is uniform.

We note that 4, 6 can be established under cryptographic assumptions, using the cryptographic technique . Also, 5 follows from the hardness of learning parities with noiseNote that agnostically learning parities when ${\cal D}$ is uniform is not equivalent to the problem that is usually referred as “learning parities with noise”, since in agnostic learning, the noise might depend on the instance. , which is often taken as a hardness assumption. As for 2, the previously best lower bounds only rule out learning intersections of polynomially many halfspaces, again under cryptographic assumptions. To the best of our knowledge, 1-6 implies the hardness of virtually all (distribution free) learning problems that were previously shown hard (under various complexity assumptions).

Unless we face a dramatic breakthrough in complexity theory, it seems unlikely that hardness of learning can be established on standard complexity assumptions such as $\mathbf{P}\neq\mathbf{NP}$ (see ). Indeed, all currently known lower bounds are based on cryptographic assumptions. Similarly to Feige’s paper , we rely here on the hardness of refuting random $K$-SAT formulas. As cryptographic assumptions, our assumption asserts the hardness on average of a certain problem that have been resisted extensive attempts of attack during the last 50 years (e.g. ).

Let $J=\{C_{1},\ldots,C_{m}\}$ be a random $K$-SAT formula on $n$ variables. Precisely, each $K$-SAT constraint $C_{i}$ is chosen independently and uniformly from the collection of $n$-variate $K$-SAT constraints. A simple probabilistic argument shows that for some constant $C$ (depending only on $K$), if $m\geq Cn$, then $J$ is not satisfiable w.h.p. The problem of refuting random $K$-SAT formulas (a.k.a. the problem of distinguishing satisfiable from random $K$-SAT formulas) seeks efficient algorithms that provide, for most formulas, a refutation. That is, a proof that the formula is not satisfiable.

Concretely, we say that an algorithm is able to refute random $K$-SAT instances with $m=m(n)\geq Cn$ clauses if on $1-o_{n}(1)$ fraction of the $K$-SAT formulas with $m$ constraints, it outputs “unsatisfiable”, while for every satisfiable $K$-SAT formula with $m$ constraints, it outputs “satisfiable”See a precise definition in section 2.2. Since such an algorithm never errs on satisfiable formulas, an output of “unsatisfiable” provides a proof that the formula is not satisfiable.

The problem of refuting random $K$-SAT formulas has been extensively studied during the last 50 years. It is not hard to see that the problem gets easier as $m$ gets larger. The currently best known algorithms can only refute random instances with $\Omega\left(n^{\lceil\frac{K}{2}\rceil}\right)$ constraints for $K\geq 4$ and $\Omega\left(n^{1.5}\right)$ constraints for $K=3$. In light of that, Feige made the assumption that for $K=3$, refuting random instances with $Cn$ constraints, for every constant $C$, is hard (and used that to prove hardness of approximation results). Here, we put forward the following assumption.

Computational problem is RSAT-hard if its tractability refutes assumption 1.1.

We outline below some evidence to the assumption, in addition to known algorithms’ performance.

Resolution lower bounds. The length of resolution refutations of random $K$-SAT formulas have been extensively studied (e.g. ). It is known (theorem 2.24 in ) that random formulas with $n^{\frac{K}{2}-\epsilon}$ constraints only have exponentially long resolution refutations. This shows that a large family of algorithms (the so-called Davis-Putnam algorithms ) cannot efficiently refute random formulas with $n^{\frac{K}{2}-\epsilon}$ constraints. These bounds can also be taken as an indication that random instances do not have short refutations in general, and therefore hard to refute.

Hierarchies lower bounds. Another family of algorithms whose performance has been analyzed are convex relaxations . In it is shown that relaxations in the Lasserre hierarchy with sub-exponential many constraints cannot refute random formulas with $n^{\frac{K}{2}-\epsilon}$ constraints.

2 Results

By boosting results , hardness of improper learning is automatically very strong quantitatively. Namely, for every $c>0$, it is hard to find a classifier with error $\leq\frac{1}{2}-\frac{1}{n^{c}}$. Put differently, making a random guess on each example, is essentially optimal.

Additional results. Theorem 1.3 implies the hardness of several problems, in addition to DNFs.

Learning intersections of $\omega(\log(n))$ halfsapces over $\{\pm 1\}^{n}$ is RSAT-hard.

Agnostically learning conjunctions is RSAT-hard.

Agnostically learning halfspaces over $\{\pm 1\}^{n}$ is RSAT-hard.

Agnostically learning paritiesA parity is any hypothesis of the form $h(x)=\Pi_{i\in S}x_{i}$ for some $S\subset[n]$. is RSAT-hard, even when the marginal distribution is uniform on $\{\pm 1\}^{n}$.

For every $\epsilon>0$, learning automata of size $n^{\epsilon}$ is RSAT-hard.

Theorem 1.6 is a direct consequence of theorem 1.3, as a DNF formula with $q(n)$ clauses is an intersection of $q(n)$ halfspaces. Theorem 1.7 follows from theorem 1.3, as learning DNFs can be reduced to agnostically learning conjunctions . Theorem 1.8 follows from theorem 1.7, as conjunctions are a subclass of halfspaces. Theorem 1.9 follows from theorem 1.3 and , who showed that learning DNFs can be reduced to agnostically learning parities over the uniform distribution. Theorem 1.10 follows from theorem 1.3 by a simple reduction (see section 4).

3 Related work

As indicated above, hardness of learning is traditionally established based on cryptographic assumptions. The first such result follows from , and show that if one-way functions exist, than it is hard to learn polynomial sized circuits. To prove lower bounds on simpler hypothesis classes, researchers had to rely on more concrete hardness assumptions. Kearns and Valiant were the first to prove such results. They showed that assuming the hardness of various cryptographic problems (breaking RSA, factoring Blum integers and detecting quadratic residues), it is hard to learn automata, constant depth threshold circuits, $\log$-depth circuits and boolean formulae. Kharitanov showed, under a relatively strong assumption on the complexity of factoring random Blum integers, that learning constant depth circuits (for unspecified constant) is hard. Klivans and Sherstov showed that, under the hardness of the shortest vector problem, learning intersections of polynomially many halfspaces is hard. By , it also follows that agnostically learning halfspaces is hard. Hardness of agnostically learning halfspaces also follows from the hardness of learning parities with noise .

There is a large body of work on various variants of the standard (improper and distribution free) PAC model. Hardness of proper learning, when the leaner must return a hypothesis from the learnt class, in much more understood (e.g. ). Hardness of learning with restrictions on the distribution were studied in, e.g., . Hardness of learning when the learner can ask the label of unseen examples were studied in, e.g., .

Preliminaries

A hypothesis class, ${\cal H}$, is a series of collections of functions ${\cal H}_{n}\subset\{0,1\}^{{\cal X}_{n}},\;n=1,2,\ldots$. We often abuse notation and identify ${\cal H}$ with ${\cal H}_{n}$. The instance spaces ${\cal X}_{n}$ we consider are $\{\pm 1\}^{n}$, $\{0,1\}^{n}$ or ${\cal X}_{n,K}$ (see section 2.2). Distributions on ${\cal Z}_{n}:={\cal X}_{n}\times\{0,1\}$ are denoted ${\cal D}_{n}$. The error of $h:{\cal X}_{n}\to\{0,1\}$ is $\operatorname{Err}_{{\cal D}_{n}}(h)=\Pr_{(x,y)\sim{\cal D}_{n}}\left(h(x)\neq y\right)$. For a class ${\cal H}_{n}$, we let $\operatorname{Err}_{{\cal D}_{n}}({\cal H}_{n})=\min_{h\in{\cal H}_{n}}\operatorname{Err}_{{\cal D}_{n}}(h)$. We say that ${\cal D}_{n}$ is realizable by $h$ (resp. ${\cal H}_{n}$) if $\operatorname{Err}_{{\cal D}_{n}}(h)=0$ (resp. $\operatorname{Err}_{{\cal D}_{n}}({\cal H}_{n})=0$). A sample is a sequence $S=\{(x_{1},y_{1}),\ldots(x_{m},y_{m})\}\in{\cal Z}^{m}_{n}$. The empirical error of $h:{\cal X}_{n}\to\{0,1\}$ on $S$ is $\operatorname{Err}_{S}(h)=\frac{1}{m}\sum_{i=1}^{m}1(h(x_{i})\neq y_{i})$, while the empirical error of ${\cal H}_{n}$ on $S$ is $\operatorname{Err}_{S}({\cal H}_{n})=\min_{h\in{\cal H}_{n}}\operatorname{Err}_{S}(h)$. We say that $S$ is realizable by $h$ (resp. ${\cal H}_{n}$) if $\operatorname{Err}_{S}(h)=0$ (resp. $\operatorname{Err}_{S}({\cal H}_{n})=0$).

A learning algorithm, ${\cal L}$, obtains an error, confidence and complexity parameters $0<\epsilon<1$, $0<\delta<1$, and $n$, as well as oracle access to examples from unknown distribution ${\cal D}_{n}$ on ${\cal Z}_{n}$. It should output a (description of) hypothesis $h:{\cal X}_{n}\to\{0,1\}$. We say that ${\cal L}$ (PAC) learns ${\cal H}$ if, for every realizable ${\cal D}_{n}$, w.p. $\geq 1-\delta$, ${\cal L}$ outputs a hypothesis with error $\leq\epsilon$. We say that ${\cal L}$ agnostically learns ${\cal H}$ if, for every ${\cal D}_{n}$, w.p. $\geq 1-\delta$, ${\cal L}$ outputs a hypothesis with error $\leq\operatorname{Err}_{{\cal D}_{n}}({\cal H})+\epsilon$. We say that ${\cal L}$ is efficient if it runs in time $\operatorname{poly}(n,1/\epsilon,1/\delta)$, and outputs a hypothesis that can be evaluated in time $\operatorname{poly}(n,1/\epsilon,1/\delta)$. Finally, ${\cal L}$ is proper if it always outputs a hypothesis in ${\cal H}$. Otherwise, we say that ${\cal L}$ is improper.

2 Random Constraints Satisfaction Problems

Let ${\cal X}_{n,K}$ be the collection of (signed) $K$-tuples, that is, vectors $x=[(\alpha_{1},i_{1}),\ldots,(\alpha_{K},i_{K})]$ for $\alpha_{1},\ldots,\alpha_{K}\in\{\pm 1\}$ and distinct $i_{1},\ldots,i_{K}\in[n]$. For $j\in[K]$ we denote $x(j)=(x^{1}(j),x^{2}(j))=(\alpha_{j},i_{j})$. Each $x\in{\cal X}_{n,K}$ defines a function $U_{x}:\{\pm 1\}^{n}\to\{\pm 1\}^{K}$ by $U_{x}(\psi)=(\alpha_{1}\psi_{i_{1}},\ldots,\alpha_{K}\psi_{i_{K}})$.

3 The methodology of [14]

In this section we briefly survey the technique of to prove hardness of improper learning. Let ${\cal D}=\{{\cal D}^{m(n)}_{n}\}_{n}$ be a polynomial ensemble of distributions, that is, ${\cal D}^{m(n)}_{n}$ is a distribution on ${\cal Z}_{n}^{m(n)}$ and $m(n)\leq\operatorname{poly}(n)$. Think of ${\cal D}^{m(n)}_{n}$ as a distribution that generates samples that are far from being realizable. We say that it is hard to distinguish realizable from ${\cal D}$-random samples if there is no efficient randomized algorithm ${\cal A}$ with the following properties:

For every realizable sample $S\in{\cal Z}^{m(n)}_{n}$,

If $S\sim{\cal D}_{n}^{m(n)}$, then with probability $1-o_{n}(1)$ over the choice of $S$, it holds that

Let ${\cal D}_{n}$ be a distribution over ${\cal Z}_{n}$ such that if $(x,y)\sim{\cal D}_{n}$, then $y$ is a Bernoulli r.v. with parameter $\frac{1}{2}$, independent from $x$. Let ${\cal D}^{m(n)}_{n}$ be the distribution over ${\cal Z}_{n}^{m(n)}$ obtained by taking $m(n)$ independent examples from ${\cal D}_{n}$. For $f:{\cal X}_{n}\to\{0,1\}$, $\Pr_{S\sim{\cal D}^{m(n)}_{n}}\left(\operatorname{Err}_{S}(f)\leq\frac{1}{4}\right)$ is the probability of getting at most $\frac{m(n)}{4}$ heads in $m(n)$ independent tosses of a fair coin. By Hoeffding’s bound, this probability is $\leq 2^{-\frac{1}{8}m(n)}$. Therefore, ${\cal D}=\{{\cal D}^{m(n)}_{n}\}_{n}$ is $\left(\frac{1}{8}m(n),1/4\right)$-scattered.

Hardness of distinguishing realizable from scattered samples turns out to imply hardness of learning.

Every hypothesis class that satisfies the following condition is not efficiently learnable. There exists $\beta>0$ such that for every $d>0$ there is an $(n^{d},\beta)$-scattered ensemble ${\cal D}$ for which it is hard to distinguish between a ${\cal D}$-random sample and a realizable sample.

The basic observation of is that an efficient algorithm, running on a very scattered sample, will return a bad hypothesis w.h.p. The reason is that the output classifier has a short description, given by the polynomially many examples the algorithm uses. Hence, the number of hypotheses the algorithm might return is limited. Now, since the sample is scattered, all these hypotheses are likely to perform purely. Based on that observation, efficient learning algorithm can efficiently distinguish realizable from scattered samples: We can simply run the algorithm on the given sample to obtain a classifier $h$. Now, if the sample is realizable, $h$ will perform well. Otherwise, if the sample is scattered, $h$ will perform purely. Relying on that, we will be able to distinguish between the two cases. For completeness, we include the proof of theorem 2.2 in section 5.

Proof of theorem 1.3

The main conceptual idea is to interpret CSP problems as learning problems. Let $P:\{\pm 1\}^{K}\to\{0,1\}$ be some predicate. Every $\psi\in\{\pm 1\}^{n}$ naturally defines $h_{\psi}:{\cal X}_{n,K}\to\{0,1\}$, by mapping each $K$-tuple $x$ to the truth value of the corresponding constraint, given the assignment $\psi$. Namely, $h_{\psi}(x)=P\circ U_{x}(\psi)$. Finally, let ${\cal H}_{P}\subset\{0,1\}^{{\cal X}_{n,K}}$ be the hypothesis class ${\cal H}_{P}=\{h_{\psi}\mid\psi\in\{\pm 1\}^{n}\}$.

In the case that sample $(x_{1},1),\ldots,(x_{m},1)$ is random, it is, in a sense, “very random”. Yet, it is not scattered at all! Since all the labels are $1$, the constant function $1$ realizes the sample.

Next, we explain how we address these two points.

Making the sample scattered

We will consider the predicate $T_{K,M}:\{0,1\}^{KM}\to\{0,1\}$ defined by

We will group the coordinates of vectors in $\{\pm 1\}^{2Kn}$ into $2K$ groups, corresponding to $P$’s literals, and index them by $[K]\times\{\pm 1\}\times[n]$. For $x=[(\alpha_{1},i_{1}),\ldots,(\alpha_{K},i_{K})]\in{\cal X}_{n,K}$, $g(x)$ will be the vector whose all coordinates are $1$, except that for $j\in[K]$, the $(j,-\alpha_{j},i_{j})$ coordinate is $-1$.

Now, given $\psi\in\{\pm 1\}^{n}$, we show that $h_{\psi}:{\cal X}_{n,K}\to\{0,1\}$ equals to $h\circ g$ for a DNF formula $h$ with $T$ clauses. Indeed, suppose that $P(x)=C_{1}(x)\vee\ldots\vee C_{T}(x)$ is a DNF representation of $P$. It is enough to show that for every $C_{r}(z)=(-1)^{\beta_{1}}z_{j_{1}}\wedge\ldots\wedge(-1)^{\beta_{l}}z_{j_{l}}$ there is a conjunction of literals $h_{r}:\{\pm 1\}^{2Kn}\to\{0,1\}$ such that for all $x=[(\alpha_{1},i_{1}),\ldots,(\alpha_{K},i_{K})]\in{\cal X}_{n,K}$, $h_{r}(g(x))=C_{r}(U_{x}(\psi))$. To see that such $h_{r}$ exists, note that $C_{r}(U_{x}(\psi))=1$ if and only if, for every $1\leq\tau\leq l$, all the values in $g(x)$ in the coordinates of the form $(j_{\tau},\psi_{i}(-1)^{\beta_{\tau}},i)$ are $1$.

It will be convenient to use the following strengthening of Chernoff’s bound, recently proved (with a very simple proof) by Linial and Luria

Let $X_{1}\ldots,X_{n}$ be indicator random variables such that for every $S\subset[n]$, $\Pr\left(\forall i\in S,\;X_{i}=1\right)\leq\alpha^{|S|}$. Then, for every $\beta>\alpha$,

Partition the constraints in $J$ into $n^{d-1}$ blocks, $\{C_{t+1},\ldots,C_{t+n}\},\;\;t=1,2,\ldots,n^{d-1}$.

If $|J^{\prime}_{t}|<\frac{n}{\log(n)}$ and, for all $C\in J^{\prime}_{t}$, the set variables appearing in $C_{t+r}$ is disjoint from the set of variables appearing in $C$, add $C_{t+r}$ to $J^{\prime}_{t}$.

If $|J^{\prime}_{t}|<\frac{n}{\log(n)}$, return “satisfiable”.

Let $C^{\prime}_{t}$ be the $T_{K,\lceil\frac{n}{\log(n)}\rceil}$-constraint which is the conjunction of all the constraints in $J^{\prime}_{t}$.

Run ${\cal A}$ on the instance $J^{\prime}=\{C^{\prime}_{1},\ldots,C^{\prime}_{n^{d-1}}\}$ and return the same answer as ${\cal A}$.

Suppose now that $J$ is random. First, we claim that ${\cal A}^{\prime}$ will reach 3 w.p. $\geq 1-o_{n}(1)$. Indeed, we will show that for large enough $n$ and any fixed $t$, the probability of exiting at step 2c is $\leq\exp\left(-\left(\frac{1}{2^{2K+5}K}\right)^{2}n\right)$, from which it follows that the probability of exiting at step 2c for some $t$ is $o_{n}(1)$. To show that, let $X_{r},\;r=1,\ldots,n$ be the indicator r.v. that is $1$ if and only if one of the variables appearing in $C_{t+r}$ also appears in one of $C_{t+1},\ldots,C_{t+r-1}$. Denote also $\bar{X}_{r}=1-X_{r}$

Let $n^{\prime}=\lfloor\frac{n}{2K}\rfloor$. It is enough to show that $\sum_{r=1}^{n^{\prime}}\bar{X}_{r}\geq\frac{n}{\log(n)}$ w.p. $\geq 1-\exp\left(-\left(\frac{1}{2^{2K+5}K}\right)^{2}n\right)$. Indeed, for every fixed $r\in[n^{\prime}]$, since the number of variables appearing in $C_{t+1},\ldots,C_{t+r-1}$ is $\leq\frac{n}{2}$, the probability that $X_{r}=1$ is $\leq 1-2^{-K}$, even if we condition on $X_{1},\ldots,X_{r-1}$. Hence, the probability that any fixed $u$ variables out of $X_{1},\ldots,X_{n^{\prime}}$ are all $1$ is $\leq\left(1-2^{-K}\right)^{u}$. By theorem 3.2,

It follows that w.p. $\geq 1-\exp\left(-\left(\frac{1}{2^{2K+5}K}\right)^{2}n\right)$, $\sum_{r=1}^{n^{\prime}}\bar{X}_{r}\geq\frac{n^{\prime}}{2^{K+1}}$, and the claim follows as for sufficiently large $n$, $\frac{n^{\prime}}{2^{K+1}}\geq\frac{n}{\log(n)}$. Finally, it is not hard to see that, conditioning on the event that the algorithm reaches step 3, $J^{\prime}$ is random as well, and therefore w.p. $\geq 1-o_{n}(1)$ over the choice of $J$, ${\cal A}$ (and therefore ${\cal A}^{\prime}$) will return “random” w.p. $\geq\frac{3}{4}$ over its internal randomness.

Proof The realization is defined by the function $g:{\cal X}_{n,K}\to\{\pm 1\}^{2Kn}$, defined as follows. We will index the coordinates of vectors in $\{\pm 1\}^{2Kn}$ by $[K]\times\{\pm 1\}\times[n]$ and let

Indeed, write $P(z_{1},\ldots,z_{K})=\vee_{t=1}^{T}\wedge_{r=1}^{R_{t}}b_{t,r}z_{j_{t,r}}$ for $b_{t,r}\in\{\pm 1\}$ and $i_{t,r}\in[K]$. Now consider the formula $h:\{\pm 1\}^{2Kn}\to\{0,1\}$ defined by

5 Wrapping up – concluding theorem 1.3

Proof theorem 1.10

Proof of theorem 2.2 [14]

Let ${\cal H}$ be the hypothesis class in question and suppose toward a contradiction that algorithm ${\cal L}$ learns ${\cal H}$ efficiently. Let $M\left(n,1/\epsilon,1/\delta\right)$ be the maximal number of random bits used by ${\cal L}$ when it run on the input $n,\epsilon,\delta$. This includes both the bits describing the examples produced by the oracle and “standard” random bits. Since ${\cal L}$ is efficient, $M\left(n,1/\epsilon,1/\delta\right)<\operatorname{poly}(n,1/\epsilon,1/\delta)$. Define

By assumption, there is a $(q(n),\beta)$-scattered ensemble ${\cal D}$ for which it is hard to distinguish a ${\cal D}$-random sample from a realizable sample. Consider the algorithm ${\cal A}$ defined below. On input $S\in{\cal Z}_{n}^{m(n)}$,

Run ${\cal L}$ with parameters $n,\beta$ and $\frac{1}{4}$, such that the examples’ oracle generates examples by choosing a random example from $S$.

Let $h$ be the hypothesis that ${\cal L}$ returns. If $\operatorname{Err}_{S}(h)\leq\beta$, output “realizable”. Otherwise, output “unrealizable”.

Next, we derive a contradiction by showing that ${\cal A}$ distinguishes a realizable sample from a ${\cal D}$-random sample. Indeed, if the input $S$ is realizable, then ${\cal L}$ is guaranteed to return, with probability $\geq 1-\frac{1}{4}$, a hypothesis $h:{\cal X}_{n}\to\{0,1\}$ with $\operatorname{Err}_{S}(h)\leq\beta$. Therefore, w.p. $\geq\frac{3}{4}$ ${\cal A}$ will output “realizable”.

What if the input sample $S$ is drawn from ${\cal D}^{m(n)}_{n}$? Let ${\cal G}\subset\{0,1\}^{{\cal X}_{n}}$ be the collection of functions that ${\cal L}$ might return when run with parameters $n,\epsilon(n)$ and $\frac{1}{4}$. We note that $|{\cal G}|\leq 2^{q(n)-n}$, since each hypothesis in ${\cal G}$ can be described by $q(n)-n$ bits. Namely, the random bits that ${\cal L}$ uses and the description of the examples sampled by the oracle. Now, since ${\cal D}$ is $(q(n),\beta)$-scattered, the probability that $\operatorname{Err}_{S}(h)\leq\beta$ for some $h\in{\cal G}$ is at most $|{\cal G}|2^{-q(n)}\leq 2^{-n}$. It follows that the probability that ${\cal A}$ responds “realizable” is $\leq 2^{-n}$. This leads to the desired contradiction and concludes our proof.

Open questions

An obvious direction for future work is to establish more lower bounds. We list below some basic learning problems that we are unable to resolve even under the random $K$-SAT assumption.

Learning intersections of a constantly many halfspaces. It is worth noting that no known algorithm can learn even intersections of $2$ halfspaces.

Agnostically Learning halfspaces with a constant approximation ratio. We note that the last problem was shown hard under the much stronger assumption of .

In addition, as discussed in , our work and have connections to several TCS areas, including hardness of approximation, cryptography, refutation algorithms and average case complexity.

Amit Daniely is a recipient of the Google Europe Fellowship in Learning Theory, and this research is supported in part by this Google Fellowship. Shai Shalev-Shwartz is supported by the Israeli Science Foundation grant number 590-10. We thank Uri Feige, Guy Kindler and Nati Linial for valuable discussions.

References