5
$\begingroup$

P.S. I just posted this question on MathOverflow, as I didn't seem to get an answer here.

Let's consider a supervised learning problem where $\{(x_1,y_1) \dots (x_n,y_n)\} \subset \mathbb{R}^p \times \mathbb{R}$ where $x_i \sim x$ are iid observations/samples, and $y_i \sim y$ are iid response variables. $y$ can be either continuous(regression) or discrete random variable (classification). To simply things, you can treat the $x_i, y_i$'s below as individual input and output, as opposed to random vectors/variables.

We know that if the learning problem at hand is linear regression, then $p \ge n-1$ is sufficient to guarantee an interpolation - i.e. the hyperplane in $\mathbb{R}^{p+1} $ passing through (and not passing near) all the points $\{(x_1,y_1) \dots (x_n,y_n)\} \subset \mathbb{R}^p \times \mathbb{R}$, thereby giving us an exact zero training error (and not a small, positive training error).

My question is: are there such lower bound on the data dimension, a lower bound that's a function of the sample size $n,$ that ensures zero training errors when the supervised learning problem at hand is not a linear regression problem, but say a classification problem? To be more specific, assume that we're solving a logistic regression problem (or replace it by your favorite classification algorithm) with $n$ samples of dimension $p$. Now, irrespective of any distribution of the covariates/features, can we come up with a positive integer valued function $f$ so that $p \ge f(n)$ guarantees a perfect classification, i.e. zero training error (and not, small, positive training error)?

To be even more specific, let's consider the logistic regression, where given: $\{(x_1,y_1) \dots (x_n,y_n)\} \subset \mathbb{R}^p \times \{0,1\},$ one assumes: $$y_i|x_i \sim Ber(h_{\theta}(x_i)), h_{\theta}(x_i):= \sigma(\theta^{T}x_i), \sigma(z):= \frac{1}{1+e^{-z}},$$ and then finds the optimal parameter $\theta*$ of the model by: $$\theta^{*}:= arg \hspace{1mm}max_{\theta \in \mathbb{R}^p} \sum_{i=1}^{n}y_iln(h_{\theta}(x_i)) + (1-y_i)ln (1 - h_{\theta}(x_i))$$

Is there a guarantee, just like linear regression, that when $p \ge f(n)$ for a certain positive integer-valued function $f,$ the training error is always zero, i.e. ${\theta^{*}}^{T}x_i>0$ when $y_i =1$ and ${\theta^{*}}^{T}x_i<0$ when $y_i =0,$ irrespective of the distribution of $x_i?$ P.S. I understand that when $p$ is large enough, perhaps just $p=n+1,$ there exists $\theta_1\in \mathbb{R}^p$ so that ${\theta_1}^{T}x_i>0$ when $y_i =1$ and ${\theta_1}^{T}x_i<0$ when $y_i =0,$ but why does the same has to be true for $\theta^{*}?$

The same question for other types of regression problems? I know the my question is broad, so some links that goes over the mathematical details will be greatly appreciated!

$\endgroup$
3
  • 1
    $\begingroup$ The statement about linear regression isn't true in general. $p>n$ doesn't guarantee zero training error. If there are two points where $x_1 = x_2$ but $y_1 \ne y_2$ then a function that perfectly interpolates the training set doesn't exist. This also holds for nonlinear regression and classification. $\endgroup$ – user20160 Nov 18 '20 at 13:48
  • $\begingroup$ @user20160 Thanks for your comment. But I think it's one of the extreme/pathological example, perhaps even a non-example; here's why. In fact, even in linear regression, if you keep the $x$-co-ordnates the same, say $x_0,$ then yes, the line consisting of all the points of the form $(x_0,y), y \in \mathbb{R}$ will pass through all of them, but this won't be a linear regression anymore, as in linear regression and all supervised learning problems, we're supposed to come up with a predictive function of $x,$ namely $f_{\theta}(x),$. But the line above won't be the graph of any function (contd) $\endgroup$ – Mathmath Nov 18 '20 at 14:31
  • $\begingroup$ @user20160 (contd.) because it takes two different values $y_1, y_2$ for the same value of $x,$ contradicting the very definition of a function. It's similar to the high school math exercise we did: why the parabola $y^2=x$ doesn't represent the graph of a function? This is so because for every $x,$ there're two $y's$ with +ve and -ve signs, and that's not the case for a graph of a function $f$, as every point has just one image $f(x),$ not two or more. Also your input data essentially consists of only one sample, namely $x_0,$ which is an extreme example. $\endgroup$ – Mathmath Nov 18 '20 at 14:32
1
$\begingroup$

Let me start with the linear regression case. Consider:

$$ Xb = y $$ where $X$ is a $n\times p$ matrix, $y$ is a $n$-vector, and $b$ is a $p$-vector. If and only if there exists $b$ that satisfies this equation, we can achieve the zero training error for the linear regression. "If" part is trivial. "Only if" part can be proven by noting that there is a non-zero residual and thus squared sum is not zero.

Unfortunately $p \ge n$ is not sufficient due to the possibility that some equations are contradictory, as pointed out by @user21060 in the comment. $p \ge n$ is not necessary either. To see this, imagine the case where $y$ is constant to zero; we can achieve zero training error by $b=0$.

Perhaps a general condition for $Xb=y$ to be possible is that $$ \mathrm{rank}(X) = \mathrm{rank}([X, y]) $$ There can be better way to state this, but you can search for the linear algebra and the conditions regarding the solution existence for linear equations.

In the logistic regression context, consider:

$$ Xb = 2 y - 1 $$

Note that the right hand side converts $y$ from $\{0,1\}$ to $\{-1,1\}$. Similar to the case of linear regression, we can achieve the zero training error if this equation has a solution. But this is not necessary condition since all we need is that $Xb$ has the correct sign and we don't need them to be exactly equal to $1$ or $-1$.

It would be possible to refine the condition by considering the hyperplane separation. The hyperplane separation theorem states roughly that

If two sets are disjoint and convex, then there exists a hyperplane separating them.

The separating hyperplane is very close to what we need to achieve zero training error. This is because, separating hyperplane would imply that $$ x_i \cdot v \ge c \;\;\;\; \text{for all positive cases} $$ $$ x_i \cdot v \le c \;\;\;\; \text{for all negative cases} $$

If we have a separating hyperplane with the strict inequalities, then we can achieve zero training error. You can look into the conditions for achieving the strict hyperplane separation, but I cannot find one immediately.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, however, I'm really not sure it even remotely answers my question. First off, see my comments following @user20160's comment - in case $y$ takes two different values for the same $x,$ we simply can't have a function (linear or nonlinear) that fits perfectly the data: this is because for a function $f,$ linear or not, it's not possible to have $f(x_1)=y_1$ and also $f(x_1)=y_2,$ this contradicts the very definition of a function. $\endgroup$ – Mathmath Nov 20 '20 at 22:49
  • $\begingroup$ I'm also not sure why you brought up the question of general hyperplane separation problem, while I specifically mentioned that in my post that such a hyperplane obviously exists in high enough dimension. But this doesn't mean that that separating hyperplane corresponds to the optimal value of the parameter you obtain using MLE or minimizing some loss function. For example, in logistic regression, when you minimize the cross-entropy loss, that corresponds to a specific hyperplane. Why does this specific hyperplane separates the classes perfectly? This is however the case for linear regression. $\endgroup$ – Mathmath Nov 20 '20 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.