Not sure if I can answer the question as a whole, but a pure random input/output pair doesn't quite have "no relationship" at all. At the very least, for any fixed training set input/output pair, you can do an if...then mapping to construct a 1-to-1 function, such that you can classify the training set with 100% accuracy (assuming no duplicates of input).

In any case, I assume you mean uniform random, because if you have something like gaussian random, you can still learn some latent structure from how the random numbers are generated.

But even if you assume uniform random, and your algorithm is only guessing, your algorithm is technically still operating optimally per the data generating distribution, which basically means its as optimal as it gets.

The only such case that I can imagine which would satisfy your question, would be if you had a separate training/validation set, where the only element of the training input/output is [1,1], but the validation set only has elements of [1,-1], or something along those lines.