Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the SAT problem. Randomly generated SAT problems are greatly different from industry collected SAT problems. The solvers behave quite different.
I am thinking about an approximation scheme that given an unknown distribution $D$ over the problem instances, there exists a polynomial time algorithm $A$ that solves the problems drawn from $D$ successfully with a probability $1-\eta$. $\eta$ somehow relates to the divergence between the $D$ and the random distribution.
Furthermore, if we have samples from $D$, we can estimate $A$, and address the sample complexity and the consistency issue.
I wonder whether such a scheme already exists or not. If so, what is the name and what are the milestones?