On the Optimality of Randomization in Experimental Design: How to Randomize for Minimax Variance and Design-Based Inference

• URL: http://arxiv.org/abs/2005.03151v1
• Date: Wed, 6 May 2020 21:43:50 GMT
• Title: On the Optimality of Randomization in Experimental Design: How to Randomize for Minimax Variance and Design-Based Inference
• Authors: Nathan Kallus
• Abstract summary: I study the minimax-optimal design for a two-arm controlled experiment where conditional mean outcomes may vary in a given set. The optimal design is shown to be the mixed-strategy optimal design (MSOD) of Kallus. I therefore propose the inference-constrained MSOD, which is minimax-optimal among all designs subject to such constraints.
• Score: 58.442274475425144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: I study the minimax-optimal design for a two-arm controlled experiment where conditional mean outcomes may vary in a given set. When this set is permutation symmetric, the optimal design is complete randomization, and using a single partition (i.e., the design that only randomizes the treatment labels for each side of the partition) has minimax risk larger by a factor of $n-1$. More generally, the optimal design is shown to be the mixed-strategy optimal design (MSOD) of Kallus (2018). Notably, even when the set of conditional mean outcomes has structure (i.e., is not permutation symmetric), being minimax-optimal for variance still requires randomization beyond a single partition. Nonetheless, since this targets precision, it may still not ensure sufficient uniformity in randomization to enable randomization (i.e., design-based) inference by Fisher's exact test to appropriately detect violations of null. I therefore propose the inference-constrained MSOD, which is minimax-optimal among all designs subject to such uniformity constraints. On the way, I discuss Johansson et al. (2020) who recently compared rerandomization of Morgan and Rubin (2012) and the pure-strategy optimal design (PSOD) of Kallus (2018). I point out some errors therein and set straight that randomization is minimax-optimal and that the "no free lunch" theorem and example in Kallus (2018) are correct.

Related papers

• Optimized experiment design and analysis for fully randomized benchmarking [34.82692226532414]
  We investigate the advantages of fully randomized benchmarking, where a new random sequence is drawn for each experimental trial. The advantages of full randomization include smaller confidence intervals on the inferred step error. We experimentally observe such improvements in Clifford randomized benchmarking experiments on a single trapped ion qubit.
  arXiv  Detail & Related papers  (2023-12-26T00:41:47Z)
• Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation [19.58011821409878]
  We study the mean estimation problem under communication and local differential privacy constraints. We take a step towards characterizing the emphexact-optimal approach in the presence of shared randomness.
  arXiv  Detail & Related papers  (2023-06-08T04:00:00Z)
• On the Variance, Admissibility, and Stability of Empirical Risk Minimization [80.26309576810844]
  Empirical Risk Minimization (ERM) with squared loss may attain minimax suboptimal error rates. We show that under mild assumptions, the suboptimality of ERM must be due to large bias rather than variance. We also show that our estimates imply stability of ERM, complementing the main result of Caponnetto and Rakhlin (2006) for non-Donsker classes.
  arXiv  Detail & Related papers  (2023-05-29T15:25:48Z)
• Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
  We show that efficiency of Metropolis-Hastings (M-H) algorithms in discrete spaces can be characterized by an acceptance rate that is independent of the target distribution. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.
  arXiv  Detail & Related papers  (2022-09-16T22:09:53Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Refined bounds for randomized experimental design [7.899055512130904]
  Experimental design is an approach for selecting samples among a given set so as to obtain the best estimator for a given criterion. We propose theoretical guarantees for randomized strategies on E and G-optimal design.
  arXiv  Detail & Related papers  (2020-12-22T20:37:57Z)
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs [12.089409241521185]
  We investigate the effectiveness of convex relaxation and nonoptimal optimization in solving bi$a-vis random noise. Results significantly improve upon the state-of-the-art theoretical guarantees.
  arXiv  Detail & Related papers  (2020-08-04T17:57:02Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Randomized Smoothing of All Shapes and Sizes [29.40896576138737]
  We show that for an appropriate notion of "optimal", the optimal smoothing for any "nice" norms have level sets given by the norm's *Wulff Crystal* We show fundamental limits to current randomized smoothing techniques via the theory of *Banach space cotypes*.
  arXiv  Detail & Related papers  (2020-02-19T11:41:09Z)

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.