How to know that your machine learning problem is hopeless? Imagine a standard machine-learning scenario:

You are confronted with a large multivariate dataset and you have a
  pretty blurry understanding of it. What you need to do is to make
  predictions about some variable based on what you have. As usual, you
  clean the data, look at descriptive statistics, run some models,
  cross-validate them etc., but after several attempts, going back and
  forth and trying multiple models nothing seems to work and your
  results are miserable. You can spend hours, days, or weeks on such a
  problem...

The question is: when to stop? How do you know that your data actually is hopeless and all the fancy models wouldn't do you any more good than predicting the average outcome for all cases or some other trivial solution?
Of course, this is a forecastability issue, but as far as I know, it is hard to assess forecastability for multivariate data before trying something on it. Or am I wrong?

Disclaimer: this question was inspired by this one
When have I to stop looking for a model? that did not attract much attention. It would be nice to have detailed answer to such question for reference.

 A: The answer from Stephan Kolassa is excellent, but I would like to add that there is also often an economic stop condition:


*

*When you are doing ML for a customer and not for fun, you should take a look at the amount of money the customer is willing to spend. If he pays your firm 5000€ and you spent a month on finding a model, you will loose money. Sounds trivial, but I have seen "there must be a solution!!!!"-thinking which led to huge cost overruns. So stop when the money is out and communicate the problem to your customer.

*If you have done some work, you often have a feeling what is possible with the current dataset. Try to apply that to the amount of money you can earn with the model, if the amount is trivial or a net negative (e.g. due to the time to collect data, develop a solution etc.) you should stop. 


As an example: we had a customer who wanted to predict when his machines break, We analyzed existing data and found essentially noise. We dug into the process and found that the most critical data was not recorded and was very difficult to collect. But without that data, our model was so poor that nobody would have used it and it was canned.
While I focused on the economics when working on a commercial product, this rule also applies to academia or for fun projects - while money is less of a concern in such circumstances, time is still a rare commodity.
E. g. in academia you should stop working when you produce no tangible results, and you have others, more promising projects you could do. But do not drop that project - please also publish null or "need more / other data" results, they are important, too!
A: Forecastability
You are right that this is a question of forecastability. There have been a few articles on forecastability in the IIF's practitioner-oriented journal Foresight. (Full disclosure: I'm an Associate Editor.)
The problem is that forecastability is already hard to assess in "simple" cases.
A few examples
Suppose you have a time series like this but don't speak German:

How would you model the large peak in April, and how would you include this information in any forecasts?
Unless you knew that this time series is the sales of eggs in a Swiss supermarket chain, which peaks right before western calendar Easter, you would not have a chance. Plus, with Easter moving around the calendar by as much as six weeks, any forecasts that don't include the specific date of Easter (by assuming, say, that this was just some seasonal peak that would recur in a specific week next year) would probably be very off.
Similarly, assume you have the blue line below and want to model whatever happened on 2010-02-28 so differently from "normal" patterns on 2010-02-27:

Again, without knowing what happens when a whole city full of Canadians watches an Olympic ice hockey finals game on TV, you have no chance whatsoever to understand what happened here, and you won't be able to predict when something like this will recur.
Finally, look at this:

This is a time series of daily sales at a cash and carry store. (On the right, you have a simple table: 282 days had zero sales, 42 days saw sales of 1... and one day saw sales of 500.) I don't know what item it is.
To this day, I don't know what happened on that one day with sales of 500. My best guess is that some customer pre-ordered a large amount of whatever product this was and collected it. Now, without knowing this, any forecast for this particular day will be far off. Conversely, assume that this happened right before Easter, and we have a dumb-smart algorithm that believes this could be an Easter effect (maybe these are eggs?) and happily forecasts 500 units for the next Easter. Oh my, could that go wrong.
Summary
In all cases, we see how forecastability can only be well understood once we have a sufficiently deep understanding of likely factors that influence our data. The problem is that unless we know these factors, we don't know that we may not know them. As per Donald Rumsfeld:

[T]here are known knowns; there are things we know we know. We also know there are known unknowns; that is to say we know there are some things we do not know. But there are also unknown unknowns – the ones we don't know we don't know.

If Easter or Canadians' predilection for Hockey are unknown unknowns to us, we are stuck - and we don't even have a way forward, because we don't know what questions we need to ask.
The only way of getting a handle on these is to gather domain knowledge.
Conclusions
I draw three conclusions from this:


*

*You always need to include domain knowledge in your modeling and prediction.

*Even with domain knowledge, you are not guaranteed to get enough information for your forecasts and predictions to be acceptable to the user. See that outlier above.

*If "your results are miserable", you may be hoping for more than you can achieve. If you are forecasting a fair coin toss, then there is no way to get above 50% accuracy. Don't trust external forecast accuracy benchmarks, either.
The Bottom Line
Here is how I would recommend building models - and noticing when to stop:


*

*Talk to someone with domain knowledge if you don't already have it yourself.

*Identify the main drivers of the data you want to forecast, including likely interactions, based on step 1.

*Build models iteratively, including drivers in decreasing order of strength as per step 2. Assess models using cross-validation or a holdout sample.

*If your prediction accuracy does not increase any further, either go back to step 1 (e.g., by identifying blatant mis-predictions you can't explain, and discussing these with the domain expert), or accept that you have reached the end of your models' capabilities. Time-boxing your analysis in advance helps.


Note that I am not advocating trying different classes of models if your original model plateaus. Typically, if you started out with a reasonable model, using something more sophisticated will not yield a strong benefit and may simply be "overfitting on the test set". I have seen this often, and other people agree.
A: There is another way.   Ask yourself - 


*

*Who or what makes the best possible forecasts of this particular variable?"

*Does my machine learning algorithm produce better or worse results than the best forecasts?  


So, for example, if you had a large number of variables associated with different soccer teams and you were trying to forecast who would win, you might look at bookmaker odds or some form of crowd sourced prediction to compare with the results of your machine learning algorithm.  If you are better you might be at the limit, if worse then clearly there is room for improvement.
Your ability to improve depends (broadly) on two things:


*

*Are you using the same data as the best expert at this particular task?

*Are you using the data as effectively as the best expert at this particular task?


It depends on exactly what I'm trying to do, but I tend to use the answers to these questions to drive the direction I go in when building a model, particularly whether to try and extract more data  that I can use or to concentrate on trying to refine the model.
I agree with Stephan that usually the best way of doing this is to ask a domain expert.
