A PTAS for Agnostically Learning Halfspaces

Introduction

For every $\mu>0$, there is an efficient algorithm for agnostically learning halfspaces under the uniform distribution with an approximation ratio of $(1+\mu)$.

As noted above, showed that under a certain complexity assumption (hardness of learning sparse parity), there are no exact efficient algorithms (i.e., with approximation ratio $\alpha=1$). In that case, our result is optimal.

Open questions: Obvious open questions are to extend our results to more distributions (uniform on $\{\pm 1\}^{d}$, permutation-invariant, product, log-concave, …) and more problems (learning intersection of halfspaces, functions of halfspaces, …). In addition, as opposed to previous approximation algorithms , our algorithm does not always return a halfspace classifier. A natural open question is therefore to find a proper PTAS.

Our algorithm and its analysis build on and combine various algorithmic and proof techniques that were previously used for learning halfspaces. This includes regression based algorithms (e.g. ), polynomial approximations of the sign function (e.g. ) and localization techniques . In this section we outline these techniques and the way we use them. Then, we present our PTAS, state its properties (theorem 1.5), and describe the course of the proof. The full proof is in sections 2 and 3.

1.3 Learning halfspaces using sign approximations

To use theorem 1.2 for learning halfspaces, we need to prove the existence of low degree polynomials $P$ such that $\|h-P\|_{1,{\cal D}}$ is small, where $h$ is a halfspace classifier. As explained below, this is naturally done by approximating the sign function, $\operatorname*{sign}(x)=\begin{cases}1&x>0\\ -1&x\leq 0\end{cases}$, with respect to an appropriate proximity measure.

1.4 Localization

An additional algorithmic component we will use, except polynomial regression, is localization in the instance and the hypotheses space (e.g. ). The basic idea is the following. Suppose that $w^{*}\in S^{d-1}$ defines the optimal halfspace. Suppose furthermore that we have found (say, using some simple algorithm) a vector $w\in S^{d-1}$ that defines a halfspace with a relatively small error. The facts that the marginal distribution is uniform and $\operatorname{Err}(h_{w})$ is small have two relevant consequences:

We know that the optimal vector, $w^{*}$, is close to $w$.

Hence, if $|\langle w,x\rangle|$ is large, then $h_{w^{*}}(x)=h_{w}(x)$ and therefore we know $h_{w^{*}}(x)$.

There is an efficient learning algorithm with label complexity $\operatorname{poly}\left(d,\log\left(\frac{1}{\eta}\right)\right)$ that tolerates noise rate of $\frac{\eta}{\alpha_{0}}$ for some universal constant $\alpha_{0}>1$. Moreover, the algorithm is proper, that is, its output is a halfspace.

1.5 The PTAS and its analysis

In a nutshell, our algorithm first find (step 1) a “rough estimation”, $w$, of $w^{*}$. Then, it “localizes the learning” and apply more computation power (step 3), to a small strip $T$ that is closed to $h_{w}$’s decision boundary, and therefore, intuitively, we are less certain about $h_{w}$’s prediction.

With appropriate choice of the parameters $r,\beta,\gamma$ (depending on $0<\mu,\eta\leq 1$), algorithm 1 satisfies:

It tolerates noise rate of $(1-\mu)\eta$.

It runs in time $\operatorname{poly}\left(d^{\frac{\log^{3}\left(\frac{1}{\mu}\right)}{\mu^{2}}},\frac{1}{\eta}\right)$.

Its label complexity is $\operatorname{poly}\left(d^{\frac{\log^{3}\left(\frac{1}{\mu}\right)}{\mu^{2}}},\log\left(\frac{1}{\eta}\right)\right)$.

Proof outline. To prove theorem 1.5, we must show that we can choose the parameters so that the time and label complexity are as stated, and under the assumption that $\operatorname{Err}_{{\cal D}}(h_{w^{*}})\leq(1-\mu)\eta$, the error of the returned classifier satisfies $\operatorname{Err}_{{\cal D}}(h)\leq\eta$. Below, we explain how we do that. We would naturally like to decompose the error into two parts:

We first handle the former summand using a localization lemma (lemma 2.1 below). We show that for $\gamma=\Theta\left(\frac{\eta\sqrt{\log\left(\frac{1}{\mu}\right)}}{\sqrt{d}}\right)$, the probability that $h_{w}(x)\neq h_{w^{*}}(x)$ outside the strip $T$, is $\leq\frac{\mu\eta}{2}$. Hence, on the complement of $T$, the returned classifier, that coincides with $h_{w}$, is as good as $h_{*}$, up to an additive error of $\frac{\mu\eta}{2}$. Concretely,

It remains to handle the latter summand in equation (4). It is enough to show that

Indeed, in that case it follows from equations (3), (4) and (5) that

We first (section 3.1) show how to find polynomials that approximate the sign function on all the points of a given segment $[-a,a]$, except the area that is very close to the origin, say $[-\epsilon,\epsilon]$. To this end, we invoke Jackson’s theorem (theorem 1.3) to find a polynomial that roughly (up to an error of, say, $0.1$) approximates the sign function on the mentioned regime. Namely, we find a polynomial $p$ of degree $O\left(\frac{a}{\epsilon}\right)$ that maps $[-a,-\epsilon]$ (resp. $[\epsilon,a]$) to $[-1.1,-0.9]$ (resp. $[0,9,1.1]$). To move from accuracy of $0.1$ to accuracy of some small $\tau>0$, we compose $p$ with another polynomial $r$ that maps $[-1.1,-0.9]$ (resp. $[0.9,1.1]$) to $[-1-\tau,-1+\tau]$ (resp. $[1-\tau,1+\tau]$). Using the Taylor expansion of the the error function $\operatorname*{erf}(x):=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^{2}}{2}}dt$, we show that there exists such $r$ of degree $O\left(\log\left(\frac{1}{\tau}\right)\right)$.

In the last step (section 3.3), using basic facts about high dimensional spherical geometry, we show that the distribution $({\cal D}|_{T\times\{\pm 1\}})_{w^{*}}$ have strong enough tail bounds.

2 Related work

Proof of theorem 1.5

For localization arguments, we will use the following lemma.

Let $w,w^{*}\in S^{n-1}$ and let ${\cal D}$ be a distribution of $S^{d-1}\times\{\pm 1\}$ such that ${\cal D}|_{S^{d-1}}$ is uniform.

We have $\frac{\theta(w,w^{*})}{\pi}\leq\operatorname{Err}_{{\cal D}}(w)+\operatorname{Err}_{{\cal D}}(w^{*})$.

If $x\in S^{d-1}$ is a uniform vector, then for every $r>0$,

Proof For the first part we note that $\Pr_{x\sim{\cal D}}\left(h_{w}(x)\neq h_{w^{*}}(x)\right)=\frac{\theta(w,w^{*})}{\pi}$, while on the other hand,

Therefore, if $P_{V}(x)\in B$ and $|\langle x,w\rangle|>r\cdot\theta(w,w^{*})$ then $h_{w}(x)=h_{w^{*}}(x)$. It follows that

Finally, let $e_{1},e_{2}\in V$ be an orthonormal basis. Note that if $|\langle x,e_{1}\rangle|\leq\frac{r}{\sqrt{2}}$ and $|\langle x,e_{2}\rangle|\leq\frac{r}{\sqrt{2}}$ then $P_{V}(x)\in B$. Hence, we have

Here, the last inequality follows from the well known measure concentration bound according which for every $e\in S^{d-1}$ and $\sigma>0$ we have $\Pr\left(|\langle x,e\rangle|\geq\sigma\right)\leq 2\exp\left(-\frac{1}{4}\sigma^{2}d\right)$.

Lastly, we will also rely on the following complexity analysis of algorithm 1.

The runtime of algorithm 1 is $\operatorname{poly}\left(d^{r},\frac{1}{\beta},\frac{1}{\gamma},\frac{1}{\eta}\right)$ and the label complexity is $\operatorname{poly}\left(d^{r},\frac{1}{\eta},\log\left(\frac{1}{\eta}\right)\right)$.

Proof The runtime of step 1 is $\operatorname{poly}\left(d,\frac{1}{\eta}\right)$, while the label complexity is $\operatorname{poly}\left(d,\log\left(\frac{1}{\eta}\right)\right)$. For step 3, we can apply the algorithm on $\operatorname{poly}\left(d^{r},\frac{1}{\eta}\right)$ examples and labels from the distribution ${\cal D}|_{T}$. We can get these many examples by sampling $\operatorname{poly}\left(d^{r},\frac{1}{\beta},\frac{1}{\Pr_{{\cal D}}(T\times\{\pm 1\})}\right)$ examples from ${\cal D}$ and keep and expose the labels of only the first $\operatorname{poly}\left(d^{r},\frac{1}{\beta}\right)$ examples that fell in $T$. It is not hard to see that $\Pr_{{\cal D}}(T\times\{\pm 1\})\geq\Omega\left(\min\left(\gamma\sqrt{d},1\right)\right)$. Hence, the runtime of step 3 is $\operatorname{poly}\left(d^{r},\frac{1}{\beta},\frac{1}{\gamma}\right)$. To summarize, the total runtime is $\operatorname{poly}\left(d^{r},\frac{1}{\beta},\frac{1}{\gamma},\frac{1}{\eta}\right)$ and the label complexity is $\operatorname{poly}\left(d^{r},\frac{1}{\beta},\log\left(\frac{1}{\eta}\right)\right)$.

By assumption, $\operatorname{Err}_{{\cal D}}(h_{w^{*}})\leq(1-\mu)\eta$. Hence, $\operatorname{Err}_{{\cal D}}(P)\leq\eta$, as required. It also follows from lemma 2.4 that the runtime and label complexity are $\operatorname{poly}\left(d^{\frac{\log^{2}\left(1/\mu\right)}{\mu^{2}}}\right)$ (note that $\eta$ is bounded from below by a constant) as stated .

Next, we deal with the case that $\eta\leq\frac{1}{2(1+\alpha_{0})}$. We will show that it is possible to choose $r=\Theta\left(\frac{\log^{3}\left(\frac{1}{\mu}\right)}{\mu^{2}}\right)$, $\beta=\theta\left(\frac{\mu}{\sqrt{\log\left(\frac{1}{\mu}\right)}}\right)$ and $\gamma=\Theta\left(\frac{\eta\sqrt{\log\left(\frac{1}{\mu}\right)}}{\sqrt{d}}\right)$ for which the algorithm will have the desired properties. Also, by lemma 2.4, for such a choice of parameters, the runtime and label complexity are as stated.

Let $w^{*}$ be the vector defining the optimal halfspace. By assumption, $\operatorname{Err}_{{\cal D}}(h_{w^{*}})\leq(1-\mu)\eta$. Let $w$ be the vector found in step 1, and let $P$ be the polynomial found in step 3. We first claim that we can assume w.l.o.g. that

and in that case the algorithm will return, in the last step, w.p. $\frac{1}{2}$, a hypothesis with error at most $\eta$, as required.

Let $h(x)=\begin{cases}h_{w}(x)&|\langle w,x\rangle|>\gamma\\ \operatorname*{sign}(P(x))&|\langle w,x\rangle|\leq\gamma\end{cases}$. It is enough to show that $\operatorname{Err}_{{\cal D}}(h)\leq\eta$. Let $T=T_{d,\gamma}(w):=\{u\in S^{d-1}:|\langle w,u\rangle|\leq\gamma\}$. The error of $h$ is

Now, by an appropriate choice of $\gamma=\Theta\left(\frac{\eta\sqrt{\log\left(\frac{1}{\mu}\right)}}{\sqrt{d}}\right)$, we get

We next deal with the term $\Pr_{(x,y)\sim{\cal D}}\left(x\in T\right)\cdot\operatorname{Err}_{{\cal D}|_{T}}(P)$. Since $\gamma=\Theta\left(\frac{\eta\sqrt{\log\left(\frac{1}{\mu}\right)}}{\sqrt{d}}\right)$ we have that

Also, by equation (8) and the assumption that $\eta\leq\frac{1}{2(\alpha_{0}+1)}$, we have that $0\leq\theta\leq\frac{\pi}{2}$. For this regime, $\sin(\theta)\geq\frac{2\theta}{\pi}$. Hence, by equation (6) we have

By equations (10) and (11) we can choose $\beta=\frac{\mu}{4C\sqrt{\log\left(\frac{1}{\mu}\right)}}$, where $C>0$ is a universal constant that is large enough so that

By equation 12 and lemma 2.3 we can choose $r=\Theta\left(\frac{\log^{2}\left(\frac{1}{\beta}\right)}{\beta^{2}}\right)=\Theta\left(\frac{\log^{3}\left(\frac{1}{\mu}\right)}{\mu^{2}}\right)$ such that

By equations (7), (9) and (13) we conclude that

Polynomial approximation of the sign function

Let $a,\gamma,\tau>0$. There exist a polynomial $p$ of degree $O\left(\frac{1}{\gamma}\cdot\log\left(\frac{1}{\tau}\right)\right)$ such that

For $x\in[-a,a]\setminus[-\gamma\cdot a,\gamma\cdot a]$, $|p(x)-\operatorname*{sign}(x)|<\tau$.

Let $\tau>0$. There exist a polynomial $p$ of degree $O\left(\log\left(\frac{1}{\tau}\right)\right)$ such that

For $x\in[-1.5,1.5]\setminus[-0.5,0.5]$, $|p(x)-\operatorname*{sign}(x)|<\tau$.

Proof The proof is established by approximating the error function, $\operatorname*{erf}(x):=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^{2}}{2}}dt$ by a low degree polynomial. Let $\sigma=2\sqrt{2\log(\frac{4}{\sqrt{2\pi}\tau})}$. We claim that for every $x>\frac{\sigma}{2}$ we have

Because $0\leq\operatorname*{erf}(x)\leq 1$ for all $x$, and since $\operatorname*{erf}(x)=1-\operatorname*{erf}(-x)$, it is enough to prove that $\operatorname*{erf}(x)\geq 1-\frac{\tau}{4}$. Indeed, we have

Now, by the Taylor expansion of $e^{x}$ we have

Integrating element-wise and using the fact that $\operatorname*{erf}(0)=\frac{1}{2}$, we have

Let $r$ be the $2k$’th Taylor polynomial of $\operatorname*{erf}$ for $k=\max\{\lceil 2(1.5\sigma)^{2}e\rceil,\log_{2}\left(\frac{4}{\tau}\right)\}=O\left(\log\left(\frac{1}{\tau}\right)\right)$. We have, for $|x|\leq 1.5\sigma\leq\sqrt{\frac{k}{2e}}$

Here, the 4’th inequality follows from the well known fact that $n!\geq\sqrt{2\pi}\left(\frac{n}{e}\right)^{n}$. Finally, using the last inequality and equation (14), it is not hard to check that the polynomial $p(x)=2r(\sigma x)-1$ satisfies the required properties.

2 Approximations for short tailed distributions

Then, for every $0<\tau\leq\frac{\sigma}{2\gamma}$ there is a polynomial of degreeThe constant in the big-O notation is universal. $O\left(\frac{\log^{2}\left(1/\tau\right)}{\tau^{2}}\right)$ such that

Proof (of lemma 3.3) By lemma 3.1, there is a polynomial $p$ of degree $O\left(r\log\left(1/\tau\right)\right)$ such that

For $x\in\left[-r\tau\sigma,r\tau\sigma\right]$, $|p(x)|<2$.

For $x\in\left[-r\tau\sigma,-\frac{\tau\sigma}{100}\right]$, $|p(x)|<\frac{\tau}{100}$.

For $x\in\left[\frac{\tau\sigma}{100},r\tau\sigma\right]$, $|p(x)-1|<\frac{\tau}{100}$.

It remains to bound $\int_{|x|\geq r\tau\sigma}|p(x)-\operatorname*{sign}(x)|\rho(x)dx$. We will choose $r\geq\frac{1}{\tau^{2}}$, and therefore we will have $r\tau\sigma\geq\frac{\sigma}{\tau}\geq 2\gamma$. Hence, by lemma 3.4 we have

Now, it is possible to choose $r=\Theta\left(\frac{\log\left(1/\tau\right)}{\tau^{2}}\right)$ such that for all $y>r\tau$ we have $\left(\frac{2y}{r\tau}\right)^{r}\cdot e^{-\frac{y^{2}}{64}}\leq 1$. For such $r$, the last expression is bounded by $12\int_{\omega\left(\frac{1}{\tau}\right)}^{\infty}e^{-\frac{y^{2}}{64}}dy=o(\tau)$.

3 Approximation on a biased strip: proof of lemma 2.3

There is a univariate polynomial $p$ of degree $r=O\left(\frac{\log^{2}\left(1/\tau\right)}{\tau}\right)$ such that

Lemma 3.5 follows immediately from lemma 3.3 with $\sigma=\frac{\sin(\theta)}{\sqrt{d}}$, the assumptions that $\gamma<\frac{1}{2}$ and $\tau<\frac{\sin(\theta)}{2\gamma\sqrt{d}}$, and the following bound:

We will use the following well known inequality

Let $A$ be the probability of $T_{d,\gamma}(w)$ according to the uniform distribution. We have

Proof Let $x$ be a uniform vector in the strip $T_{d,\gamma}(w)$, and let $y=\langle w^{*},x\rangle$. We note that $\rho_{d,\gamma,\theta}$ is the density of $y$. We write

where $\langle w,z\rangle=0$. For $(w^{*})^{\perp}=w^{*}-\langle w^{*},w\rangle w$ we have,

We note that the density function of the distribution of $\alpha\cdot\cos(\theta)$ is given by

Now, given $\alpha$, $z$ is a uniform vector of norm $\sqrt{1-\alpha^{2}}$ in the orthogonal complement of $w$, and $(w^{*})^{\perp}$ is a vector of norm $\sin(\theta)$ in that space. It follows that the density function of $\langle(w^{*})^{\perp},z\rangle$ given that $\alpha\cdot\cos(\theta)=u$ is $\rho_{d-1,\sin(\theta)\cdot\sqrt{1-\frac{u^{2}}{\cos^{2}(\theta)}}}=\rho_{d-1,\sqrt{\sin^{2}(\theta)-\tan^{2}(\theta)u^{2}}}$. It therefore follows that

Proof (of lemma 3.6) Let $A$ be the probability of the strip $T_{d,\gamma}(w)$ according to the uniform distribution on the sphere. We have, using equations (15) and (16),

Proof (of lemma 2.2) By equation (1.1.3), in is enough to show that the there is a univariate polynomial $p$ of degree $r=O\left(\frac{\log^{2}\left(1/\tau\right)}{\tau^{2}}\right)$ such that

This, however, follows immediately from lemma 3.3 and equation (16).

Amit Daniely is a recipient of the Google Europe Fellowship in Learning Theory, and this research is supported in part by this Google Fellowship. The author thanks Pranjal Awasthi, Adam Klivans, Nati Linial, and Shai Shalev-Shwartz for valuable discussions and comments.

References