Of course it's possible to define a problem where there is no relationship between input $x$ and output $y$. In general if the mutual information between $x$ and $y$ is zero (i.e. $x$ and $y$ are statistically independent) then the best prediction you can do is independent of $x$. The task of machine learning is to learn a distribution $q(y|x)$ that is as close as possible to the real data generating distribution $p(y|x)$.

For example, looking at the common cross-entropy loss, we have 
$$
\begin{align}
H(p,q) = -\mathbb{E}_{y,x \sim p}\left[\log q(y|x)\right] & = \mathbb{E}_{x\sim p}\left[\text{H}(p(y|x)) + \text{D}_{\text{KL}}(p(y|x)\|q(y|x))\right]  \\
& = \text{H}(p(y)) + \mathbb{E}_{x \sim p}\left[\text{D}_{\text{KL}}(p(y)\|q(y|x))\right],
\end{align}
$$
Where we have used the fact that $p(y|x)=p(y)$ since $y$ and $x$ are independent. From this we can see that the optimal predicted distribution $q(y|x)$ is equal to $p(y)$, and actually independent of $x$. Also, the best loss you can get is equal to the entropy of $y$.