Typical NP-complete/hard problems in machine learning I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with constraints, etc.

I was wondering, is there any problem in ML that is NP-hard for which there are only approximations or small attempts of trying to solve them? I would like to look at them to see if my work can be applied there.

I am only interested in discrete optimization (so over integers/Booleans). Something that one could typically solve with constraint programming. Examples of such problems are scheduling tasks, finding paths in a graph given some weird constraints, TSP, vehicle routing... 
My research is on constraint programming applied to graphs, so if the problem can be modelled as a graph problem, that is a plus.
My knowledge of ML is limited. I know the high-level concepts such as what regression, classification or supervised/unsupervised mean. Never actually implemented one of this ML things. I am watching a coursera class form Stanford on ML, but it is portrayed in a way that doesn't let me really see what are the NP-hard challenges.
Many theoretical problems in ML are NP-hard.


I think the famous AlphaGo is trying to solve a NP-hard problem. 
Contextual bandit problem and its combinatorial variants are np-hard. 
In social network analysis, the famous influence maximization problem is a NP-hard problem. 
There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.