  We consider the problem of bounding large deviations for non-i.i.d. random
variables that are allowed to have arbitrary dependencies. Previous works
typically assumed a specific dependence structure, namely the existence of
independent components. Bounds that depend on the degree of dependence between
the observations have only been studied in the theory of mixing processes,
where variables are time-ordered. Here, we introduce a new way of measuring
dependences within an unordered set of variables. We prove concentration
inequalities, that apply to any set of random variables, but benefit from the
presence of weak dependencies. We also discuss applications and extensions of
our results to related problems of machine learning and large deviations.
