What is a good reference for NP hardness in the machine learning/optimization/operations research context?
In modern papers, and unless stated otherwise, NP-hardness is one of the following:

A decision problem is NP-hard if it is NP-hard with respect to many-one reductions.
An optimization problem is NP-hard if its decision version is NP-hard.

Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem states that maximization problem X is NP-hard to approximate within a factor of $\alpha &lt; 1$, it usually means that there is a many-one reduction from SAT (or some other NP-complete problem) an instance of X and a parameter $k$ such that

If the original SAT instance is satisfiable, then the value of the X-instance is at least $k$.
If the original SAT instance is unsatisfiable, then the value of the X-instance is at most $\alpha k$.

However, to be sure, you need to look at the exact statement being proved.
Your case is similar. The complete version of your paper proves the main theorem in Section 5. Theorem 5.2 on page 21 states exactly what holds in the Yes case and what holds in the No case (Theorem 5.1 shows that it is NP-hard to distinguish the two cases). You should be able to relate this to the informal statement appearing in Theorem 1.1.