I tried posting this question on Cross Validated (the stack exchange for statistics) but didn't get an answer, so posting 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 simplify 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!


1 Answer 1


$\newcommand\th\theta\newcommand\R{\mathbb R}$In your logistic regression model, there is no function $f$ such that the condition $p\ge f(n)$ guarantees the zero training error.

Indeed, let us say that a point $x_i$ in your data is red if $y_i=1$ and blue of $y_i=0$. Let us say that $\th\in\R^p$ separates the red and blue points -- that is, has zero training error --- if $\th^Tx_i>0$ if $x_i$ is red and $\th^Tx_i<0$ if $x_i$ is blue.

Then, for any natural $p$, the zero training error cannot be attained by any $\th$ if e.g. (i) one of the $x_i$'s is $0$ or (ii) there are two red points of the form $u$ and $au$ for some real $a\ge0$ and some $u\in\R^p$ or (iii) there are two red points $u$ and $v$ and a blue point of the form $au+bv$ for some real $a,b\ge0$.

On the other hand, if the training data $\{(x_1,y_1),\dots,(x_n,y_n)\}$ admits some $\th_*\in\R^p$ that separates the red and blue points (that is, has zero training error), then your formula $$\th^*:= \text{arg max}_{\th\in\R^p}\sum_{i=1}^n(y_i\ln h_{\th}(x_i)+(1-y_i)\ln(1-h_{\th}(x_i))$$ makes no sense, because then the supremum of $$H(\th):=\sum_{i=1}^n(y_i\ln h_{\th}(x_i)+(1-y_i)\ln(1-h_{\th}(x_i))$$ over all $\th\in\R^p$ is not attained. Rather, this supremum (equal $0$) is "attained" only in the limit, when $\th=t\th_*$, $t\to\infty$, and, as above, $\th_*\in\R^p$ separates the red and blue points (that is, has zero training error).

  • $\begingroup$ Thank you for your answer and observing that if $\theta^{*}\in \mathbb{R}^p$ does a perfect classification, then any positive multiple of $\theta^{*}$ does so as well and hence $H(\theta)$ doesn't have a maximum. I also well noted the three points you mentioned before when no $\theta$ can separate them. But for point (ii) did you mean that there's a red and a blue point of the form $u$ and $au, a\ge 0$ respectively (so that one of them will always get misclassified)? But I wonder about this: if we change the signs of $y_i$ from $\{0,1\}$ to something else, say $\{a,b\},$ (contd) $\endgroup$ Nov 20, 2020 at 22:18
  • $\begingroup$ (contd) then the classification problem won't change, but I wonder if we can still apply some modified version of the counterexamples (i)-(iii) you gave that heavily depends upon the fact that $y_i=0$ or $1.$ Of course this is my mistake, as I should've given general $y_i$'s. In fact as long as $y_i's$ take two different values, that still doesn't change the problem. But thanks to your counterexample, I do see the trouble with setting $y_i=0$ or $1.$ $\endgroup$ Nov 20, 2020 at 22:23
  • $\begingroup$ @Learningmath : I don't see any problem with how you label the $x_i$'s. Actually, and in my counterexamples I relabeled $1$ as red and $0$ as blue. However, in the expression for $H(\theta)$ we should keep the (standard) values $1$ and $0$ for the $y_i$'s, if we want to get meaningful results. $\endgroup$ Nov 22, 2020 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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