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!