In linear regression, we have 0 training error if data dimension is high, but are there similar results for other supervised learning problems?

Question

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!

Answer 1

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.