Limit theorems beyond sums of I.I.D observations

We consider second and third order limit theorems--namely central-limit theorems, Berry-Esseen bounds and concentration inequalities-- and extend them for "symmetric" random objects, and general estimators of exchangeable structures. At first, we consider random processes whose distribution satisfies a symmetry property. Examples include exchangeability, stationarity, and various others. We show that, under a suitable mixing condition, estimates computed as ergodic averages of such processes satisfy a central limit theorem, a Berry-Esseen bound, and a concentration inequality. These are generalized further to triangular arrays, to a class of generalized U-statistics, and to a form of random censoring. As applications, we obtain new results on exchangeability, and on estimation in random fields and certain network model; extend results on graphon models; give a simpler proof of a recent central limit theorem for marked point processes; and establish asymptotic normality of the empirical entropy of a large class of processes. In certain special cases, we recover well-known properties, which can hence be interpreted as a direct consequence of symmetry. The proofs adapt Stein's method. Subsequently, we consider a sequence of-potentially random-functions evaluated along a sequence of exchangeable structures. We show that, under general stability conditions, those values are asymptotically normal. Those conditions are vaguely reminiscent of those familiar from concentration results, however not identical. We require that the output of the functions does not vary significantly when an entry is disturbed; and the size of this variation should not depend markedly on the other entries. Our result generalizes a number of known results, and as corollaries, we obtain new results for several applications: For randomly sub-sampled subgraphs; for risk estimates obtained by K-fold cross validation; and for the empirical risk of double bagging algorithms. The proof adapts the martingale central-limit theorem.