How does one design a data set from polynomial target function such that logistic regression separates the data perfectly?

I want to design a target function for a classification task of the form:

$$f_{target}(x) = \mathbb{1}_{>0}[\sum^{D^*}_{i=0} w^*_i x^i] = \mathbb{1}_{>0}[ \langle w^*, \Phi(x)\rangle]$$

and solve it using logistic regression $h_{w}(x) = sigmoid( \sum^{D}_{i=0} w_i x^i) = sigmoid \langle w, \Phi(x)\rangle)$. I was thinking of fixing some interval too, why not $I = [-1,1]$ (just because probably anything larger might lead to numerical error since this problem is usually solved with Gradient Descent (GD) with logistic regression).

What I am confused about is the conditions such that the problem is separable (or not) since it depends on:

• complexity of the target (classification) function ($D^*$ in this problem)
• complexity of the (linear) logistic model ($D$ in this problem)
• the number of train (or test) examples $N_{train}$

For normal linear regression as long as the rank of $\Phi(X)$ the design matrix is large equal to the number of data points, then the problem will have zero error due to the pseudo-inverse. So its not to hard to have this happen if you make the problem under-constrained for instance and solve $w^+ = \Phi(X)^+ y$.

However, for classification things don't seem as simple. For things to be separable we just need that there to exists a hyperplane in feature space that correctly classifies every point. I was thinking that intuitively:

as long as the degree of the polynomial inside the target function is less than the degree of the polynomial of the logistic regression model things should be separable.

furthermore, it didn't really seem to matter how many points I got so unlike in linear regression, getting to few or to many data points won't determine if the problem is separable or not because once the hyperplane has been chose, its just a matter of sampling many points and that doesn't determine the invertibility of the problem it seems to me.

Is this right?

The reason I was thinking this was because of the way kernel methods are usually taught. If we have a feature space of polynomials $\phi(x)$ say $\phi(x) = [1,x,x^2]$. So a data point is embedded in that 3 dimensional space. Thus, if we choose as a model a polynomial of at least degree 3 we should be able to find a hyperplane that separates the points. Of course, the parameters corresponding too higher degree can just be ignored via training and assigned any value since they don't contribute to deciding the value of the label.

• Your intuition looks well motivated, but I doubt it's correct. The problem is that separation is a property of the number $c\ge 1$ of peaks and valleys (local extrema) of the polynomial within the interval $[0,1]$ and the only relation $c$ has to the degree $d$ of the polynomial is $c \le d+1$. It easily can happen that $c$ is much less than that, even as low as $2$. This occurs for the polynomials $1-((x+1)/2)^d$, for instance. – whuber Jan 26 '18 at 14:21
• @whuber I was thinking more about it and the issue truly lies I believe in the number of roots (not the degree) of the target and the model polynomial. This is because a root indicates when the function changes sign. Thus if the target polynomial has the same number of roots as the model polynomial then depending on how the points are sampling it and were the roots are located (approximately in the same regions of each other) then they would more or less change sign together. If this happens then model can match the target even if the target is much higher degree. – Pinocchio Jan 26 '18 at 20:13
• @whuber so yes, ur right. I think my intuition is incorrect because we need to think of the "rank" of this problem which seems to be somehow similar/analogous to the # of roots. However, if the target has many more roots and the model does not have that many roots (or even achieve them since it is of a lower degree for example), then the model could potentially be unlucky and never be able to separate the data set (assuming enough data points are sampled and the interval contains all the regions of changing sings, i.e. contains the roots of course). I think thats roughly the solution. – Pinocchio Jan 26 '18 at 20:15