Clustered Switchback Experiments: Near-Optimal Rates Under Spatiotemporal Interference

• URL: http://arxiv.org/abs/2312.15574v4
• Date: Sun, 23 Jun 2024 22:24:22 GMT
• Title: Clustered Switchback Experiments: Near-Optimal Rates Under Spatiotemporal Interference
• Authors: Su Jia, Nathan Kallus, Christina Lee Yu,
• Abstract summary: We estimate the global average treatment effect (GATE), the difference between average outcomes having exposed all units at all times to treatment or to control. We propose a clustered switchback design, where units are grouped into clusters and time steps are grouped into blocks. We show that for graphs that admit good clustering, a truncated exposure-mapping Horvitz-Thompson estimator achieves $tilde O(1/NT)$ mean-squared error (MSE), matching an $Omega (1/NT)$ lower bound up to logarithmic terms.
• Score: 44.644520116360106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider experimentation in the presence of non-stationarity, inter-unit (spatial) interference, and carry-over effects (temporal interference), where we wish to estimate the global average treatment effect (GATE), the difference between average outcomes having exposed all units at all times to treatment or to control. We suppose spatial interference is described by a graph, where a unit's outcome depends on its neighborhood's treatment assignments, and that temporal interference is described by a hidden Markov decision process, where the transition kernel under either treatment (action) satisfies a rapid mixing condition. We propose a clustered switchback design, where units are grouped into clusters and time steps are grouped into blocks and each whole cluster-block combination is assigned a single random treatment. Under this design, we show that for graphs that admit good clustering, a truncated exposure-mapping Horvitz-Thompson estimator achieves $\tilde O(1/NT)$ mean-squared error (MSE), matching an $\Omega(1/NT)$ lower bound up to logarithmic terms. Our results simultaneously generalize the $N=1$ setting of Hu, Wager 2022 (and improves on the MSE bound shown therein for difference-in-means estimators) as well as the $T=1$ settings of Ugander et al 2013 and Leung 2022. Simulation studies validate the favorable performance of our approach.

Related papers

• Estimation and Inference for Causal Functions with Multiway Clustered Data [6.988496457312806]
  This paper proposes methods of estimation and uniform inference for a general class of causal functions. The causal function is identified as a conditional expectation of an adjusted (Neyman-orthogonal) signal. We apply the proposed methods to analyze the causal relationship between levels in Africa and the historical slave trade.
  arXiv  Detail & Related papers  (2024-09-10T17:17:53Z)
• Cluster truncated Wigner approximation for bond-disordered Heisenberg spin models [0.0]
  Cluster Truncated Wigner Approximation (cTWA) applied to quench dynamics in bond-disordered Heisenberg spin chains with power-law interactions. We develop a discrete sampling scheme for the initial Wigner function, as an alternative to the originally introduced scheme based on Gaussian approximations.
  arXiv  Detail & Related papers  (2024-07-01T18:00:06Z)
• Revisiting Counterfactual Regression through the Lens of Gromov-Wasserstein Information Bottleneck [30.31832773408621]
  We propose a novel learning paradigm called Gromov-Wasserstein information bottleneck (GWIB) GWIB effectively learns the CFR model through alternating optimization, suppressing selection bias while avoiding trivial latent distributions. Experiments on ITE estimation tasks show that GWIB consistently outperforms state-of-the-art CFR methods.
  arXiv  Detail & Related papers  (2024-05-24T12:48:24Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
  Normalized-cut graph partitioning aims to divide the set of nodes in a graph into $k$ disjoint clusters to minimize the fraction of the total edges between any cluster and all other clusters. We consider a fair variant of the partitioning problem wherein nodes are characterized by a categorical sensitive attribute indicating membership to different demographic groups. Our goal is to ensure that each group is approximately proportionally represented in each cluster while minimizing the normalized cut value.
  arXiv  Detail & Related papers  (2023-07-22T12:20:46Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering [0.0]
  In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement, the clustering outcome might discriminate against people across different demographic groups. We propose a novel alternating balance mini-batch $k$-means (SAKM) algorithm, which consists of $k$-means updates and group swap updates.
  arXiv  Detail & Related papers  (2021-05-29T01:47:15Z)
• Federated Functional Gradient Boosting [75.06942944563572]
  We study functional minimization in Federated Learning. For both FFGB.C and FFGB.L, the radii of convergence shrink to zero as the feature distributions become more homogeneous.
  arXiv  Detail & Related papers  (2021-03-11T21:49:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.