  Violating Bell's inequalities (BIs) allows one to certify the preparation of
entangled states from minimal assumptions -- in a device-independent manner.
Finding BIs tailored to many-body correlations as prepared in present-day
quantum computers and simulators is however a highly challenging endeavour. In
this work, we focus on BIs violated by very coarse-grain features of the
system: two-body correlations averaged over all permutations of the parties.
For two-outcomes measurements, specific BIs of this form have been
theoretically and experimentally studied in the past, but it is practically
impossible to explicitly test all such BIs. Data-driven methods --
reconstructing a violated BI from the data themselves -- have therefore been
considered. Here, inspired by statistical physics, we develop a novel
data-driven approach specifically tailored to such coarse-grain data. Our
approach offers two main improvements over the existing literature: 1) it is
directly designed for any number of outcomes and settings; 2) the obtained BIs
are quadratic in the data, offering a fundamental scaling advantage for the
precision required in experiments. This very flexible method, whose complexity
does not scale with the system size, allows us to systematically improve over
all previously-known Bell's inequalities robustly violated by ensembles of
quantum spin-$1/2$; and to discover novel families of Bell's inequalities,
tailored to spin-squeezed states and many-body spin singlets of arbitrary
spin-$j$ ensembles.
