Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta < 1$? If not, can something like this hold for a "generic" $A$ (say, with high probability if $A$ is chosen at random)? What about $2A-A$ or similar sets? (as you can guess, interest in $2A-A$ comes from arithmetic progressions)

Of course only the case $|A| = \Omega(\sqrt{n})$ is nontrivial, and perhaps we have to assume also an upper bound on $|A|$ (e.g. $|A| \leq n^{\gamma}$ for some $\gamma <1$), since of course we could have $A = \{1, \dots, n\}$.