Near-Optimal Experimental Design for Networks: Independent Block Randomization

Near-Optimal Experimental Design for Networks: Independent Block Randomization

Subscribers:
348,000
Published on ● Video Link: https://www.youtube.com/watch?v=TAjB1uj32fs



Duration: 57:58
1,629 views
23


A Google TechTalk, presented by Rad Niazadeh, 2021/09/30
ABSTRACT: Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing randomized experiments to assess the effectiveness of a new market intervention for a network of users. An experiment assigns each user to either the treatment or the control group. The outcome of each user depends on her assignment as well as the assignments of her neighbors. Given the experiment, the unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. The decision maker chooses randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is almost without loss to assign all users in the same community to the same variant (treatment or control). The problem of designing the optimal randomized assignments of communities can be formulated as a linear program with exponential number of decision variables and constraints in the number of communities -- and hence is in general computationally intractable.
We develop a family of practical experiments that we refer to as independent block randomization (IBR) experiments. Such an experiment partitions communities into blocks so that each block contains communities of similar sizes. It then treats half of the communities in each block (chosen uniformly at random) and does so independently across blocks. The optimal community partition can be obtained in a tractable way using dynamic programming. We show that these policies are asymptotically optimal when the number of communities grows large and no community size dominates the rest. In the special case where community sizes take values in a finite set and the number of communities of each size is a fixed proportion of the total number of communities, the loss is only a constant that is independent of the number of communities. Beyond the asymptotic regime, we show that the IBR experiment is a 7/3-approximation for any problem instance. We also examine the performance of the IBR experiments on data-driven numerical examples, including an example based on a Facebook subnetwork.

Based on a joint work with Ozan Candogan and Chen Chen
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3852100

Bio: Rad Niazadeh is an Assistant Professor at the University of Chicago Booth School of Business in the operations management area. Prior to joining Booth, he was a postdoc researcher in the market algorithms group at Google Research NYC and a Motwani postdoctoral fellow at Stanford University, Department of Computer Science. He received his PhD in Computer Science (minored in Applied Mathematics) from Cornell University. Rad studies the interplay between algorithms, incentives, and learning, with the goal of advancing the theoretical methodologies and foundations of market design and operations in dynamic and complex environments. He has received the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention) in 2018, the Google PhD Fellowship in Market Algorithms in 2016, the Stanford Motwani fellowship in 2017, and the Cornell Jacobs fellowship in 2012 for his research.




Other Videos By Google TechTalks


2022-02-08Academic Keynote: Federated Learning with Strange Gradients, Martin Jaggi (EPFL)
2022-02-08Google Keynote: Federated Aggregation and Privacy
2022-02-08Welcome and Opening Remarks
2022-01-25Warehouse-Scale Video Acceleration: Co-Design and Deployment in the Wild
2022-01-06What Could Be the Data-Structures of the Mind?
2021-12-21Differential Privacy and the 2020 Census in the United States
2021-12-21Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
2021-12-21Private Histograms in the Shuffle Model
2021-12-14The Platform Design Problem
2021-11-19Reducing Polarization and Increasing Diverse Navigability in Graphs
2021-10-12Near-Optimal Experimental Design for Networks: Independent Block Randomization
2021-10-06Greybeard Qualification (Linux Internals) part 1: Process Structure and IPC
2021-10-06Greybeard Qualification (Linux Internals) part 3: Memory Management
2021-10-06Greybeard Qualification (Linux Internals) part 2 Execution, Scheduling, Processes & Threads
2021-10-06Greybeard Qualification (Linux Internals) part 6: Networking & Building a Kernel
2021-10-06Greybeard Qualification (Linux Internals) part 5: Block Devices & File Systems
2021-10-06Greybeard Qualification (Linux Internals) part 4: Startup and Init
2021-09-30A Regret Analysis of Bilateral Trade
2021-09-29CoinPress: Practical Private Mean and Covariance Estimation
2021-09-29"I need a better description": An Investigation Into User Expectations For Differential Privacy
2021-09-29On the Convergence of Deep Learning with Differential Privacy