Consider $n$ i.i.d spherically distributed random vectors $z_1 ,\cdots , z_n \sim \text{Unif}(\mathbb{S}^{d-1})$. What is the best lower bound on $n$ for which whp there exists a constant $c>0$ such that the following bound holds for all $v\in \mathbb{R}^d\setminus \{0\}$:
\begin{equation} cn\leq \left\vert\left\{i:\langle z_i,v \rangle>0 \right\} \right\vert \end{equation}
$\newcommand\PP{\mathbb P}$ Surely $n_\min \lesssim d$, because it works for $c = 1/4$ and $n=160d$.
We use that the number of "distinct" $v$ with respect to the classifiers $\textrm{sgn}\langle \cdot, z_i \rangle$ is $$ \sum_{i=0}^{d-1} \binom{n-1}{i} \le \left( \frac{ne}{d} \right)^d $$
The proof can be found in [Bürgisser and Cucker (2013), Lemma 13.7]. (Anyone has a better reference?)
Let $X = \lvert \left\{ i ~:~ \langle z_i, e_1 \rangle \right\} \rvert$ for a basis vector $e_1$. Then, by the union bound $$ \PP \left[ ~\exists v ~~ \lvert \left\{ i ~:~ \langle z_i, v \rangle > 0 \right\}\rvert < cn \right] \\ \le \left( \frac{ne}{d} \right)^d \PP \left[ X < cn \right] \\ \le \exp(d\log(n) - \frac{n}{16} + d - d \log{d}) \\ = \exp(\log(160)d - 9d) \xrightarrow{d \to \infty} 0$$
where we used the Chernoff bound on $\PP[X < cn]$, in the form $$ \PP\left[X \le (1 - \delta) \mathbb E[X] \right] \le \exp(-\frac12 \delta^2 \mathbb E[X]). $$
As noted in the comment by Sandeep Silwal, $n_{\text{min}} \ge d$ due to the strict inequality sign in the question. So the answer to the original question is $n_{\text{min}} = \Theta(d)$.
