Abstract: 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.
Introduction
In classical statistics and machine learning, the independent and identically distributed (i.i.d.) assumption is a cornerstone for providing performance guarantees. Tools like Hoeffding’s inequality allow us to bound the probability that a sample mean deviates significantly from its true expectation. However, real-world data—ranging from spatial correlations in image pixels to temporal dependencies in financial markets—rarely satisfies this assumption.
Existing methods for handling dependent data generally fall into two categories: mixing processes, which assume a strict temporal ordering, and dependency graphs, which treat dependencies as binary (either present or absent). This paper addresses the gap in unordered, weakly dependent data, where the magnitude of dependency matters as much as its existence. By quantifying the strength of these relationships, the authors provide tighter, more flexible concentration inequalities.
Methodology: $\alpha$-separation and the Approximation Theorem
The authors introduce two primary theoretical innovations to bridge this gap:
- $\alpha$-separation: A novel measure that quantifies the total dependence within a set of variables. Unlike traditional measures, it considers the optimal ordering of variables to minimize the cumulative dependence of each variable on its predecessors, making it suitable for spatial or unordered data.
- The Approximation Theorem: This theorem allows a set of dependent variables to be modeled as "nearly independent." The authors prove that for any set of dependent variables, there exists a "shadow" set of perfectly independent variables with the same marginal distributions. The distance between the original set and this shadow set is controlled by the $\alpha$-separation coefficient.
Soft Covers and Graph Simplification
To operationalize these concepts, the authors introduce "soft covers." While traditional methods partition variables into strictly independent groups, soft covers allow for groups with a controlled, non-zero amount of internal dependence below a specific threshold $\gamma$. This allows for a significant reduction in the complexity of the dependency model.
As shown in Figure 1, the original dependency graph $\mathcal{G}$ contains various levels of interaction ($\alpha_1$ through $\alpha_4$). By applying a threshold $\gamma$, we can derive a simplified graph $\mathcal{G}_\gamma$ that retains only the strongest dependencies. This simplification is the key to deriving tighter bounds; by ignoring negligible correlations, we avoid the "wasteful" guarantees of traditional binary dependency graphs.
Key Results and Applications
The theoretical framework yields new concentration inequalities (Theorems 2 and 3) that resemble Hoeffding’s inequality but include an additive term accounting for dependency "leakage." The utility of these bounds is demonstrated across several models:
- Stationary Mixing Processes: The framework recovers and clarifies existing results for time-series data, proving that the unordered approach is as robust as traditional ordered ones.
- Lattice Models (Ising Model): For spatial grids where correlations decay exponentially with distance, the $\alpha$-separation coefficient also decays exponentially. This leads to highly efficient concentration bounds for properties like average magnetization.
- Independent Cascade Models: The authors provide new insights into information spread within networks, suggesting their bounds can be extended to complex graph structures.
Conclusion and Future Work
This work shifts the focus from the existence of dependencies to their magnitude. By treating weak dependencies as negligible through the $\alpha$-separation framework, researchers can obtain much tighter statistical guarantees for complex, real-world datasets. Future research directions include extending these proofs to unbounded variables (such as Gaussian noise) and exploring the authors' conjecture regarding the application of these bounds to arbitrary graph structures in social network analysis.
Summary updated