Descriptive Complexity and Algorithmic Complexity theory both use an analysis in the worst-case. However, hard problems such as \(\mathsf {SAT}\) become much easier when we relax the worst-case condition. We introduce the notion of statistical queries which take finite structures as inputs and return distributions on finite domains. A statistical constraint is a relation between statistical queries. We use the notion of a stochastic approximation (Mathieu and Rougemont, Network Sci. 9(4):403–424, 2021) for structures which satisfy a statistical constraint and can be generated with a distribution \(\mu \) . A hard problem is approximable with an algorithm A if A is correct on YES instances with high probability, and on NO instances generated by \(\mu \) with high probability. We explain how a generalization of \(\mathsf {Maxclique}\) is easy on graphs which follow a power law degree distribution, even if the graph is given as a stream of edges.