Dynamic Algorithms for Online Multiple Testing

• URL: http://arxiv.org/abs/2010.13953v3
• Date: Wed, 2 Jun 2021 15:43:59 GMT
• Title: Dynamic Algorithms for Online Multiple Testing
• Authors: Ziyu Xu, Aaditya Ramdas
• Abstract summary: We derive new algorithms for online multiple testing that provably control false discovery exceedance (FDX) We demonstrate that our algorithms achieve higher power in a variety of synthetic experiments. SupLORD is the first non-trivial algorithm, to our knowledge, that can control FDR at stopping times in the online setting.
• Score: 38.45810475976042
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We derive new algorithms for online multiple testing that provably control false discovery exceedance (FDX) while achieving orders of magnitude more power than previous methods. This statistical advance is enabled by the development of new algorithmic ideas: earlier algorithms are more "static" while our new ones allow for the dynamical adjustment of testing levels based on the amount of wealth the algorithm has accumulated. We demonstrate that our algorithms achieve higher power in a variety of synthetic experiments. We also prove that SupLORD can provide error control for both FDR and FDX, and controls FDR at stopping times. Stopping times are particularly important as they permit the experimenter to end the experiment arbitrarily early while maintaining desired control of the FDR. SupLORD is the first non-trivial algorithm, to our knowledge, that can control FDR at stopping times in the online setting.

Related papers

• Online multiple testing with e-values [37.0397290998274]
  A scientist wishes to make as many discoveries as possible while ensuring the number of false discoveries is controlled. Prior methods for FDR control in the online setting have focused on formulating algorithms when specific dependency structures are assumed to exist between the test statistics of each hypothesis. Our algorithm, e-LOND, provides FDR control under arbitrary, possibly unknown, dependence.
  arXiv  Detail & Related papers  (2023-11-10T22:14:47Z)
• Iteratively Refined Behavior Regularization for Offline Reinforcement Learning [57.10922880400715]
  In this paper, we propose a new algorithm that substantially enhances behavior-regularization based on conservative policy iteration. By iteratively refining the reference policy used for behavior regularization, conservative policy update guarantees gradually improvement. Experimental results on the D4RL benchmark indicate that our method outperforms previous state-of-the-art baselines in most tasks.
  arXiv  Detail & Related papers  (2023-06-09T07:46:24Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Toward Asymptotic Optimality: Sequential Unsupervised Regression of Density Ratio for Early Classification [11.470070927586017]
  Theoretically-inspired sequential density ratio estimation (SDRE) algorithms are proposed for the early classification of time series. Two novel SPRT-based algorithms, B2Bsqrt-TANDEM and TANDEMformer, are designed to avoid the overnormalization problem for precise unsupervised regression of SDRs.
  arXiv  Detail & Related papers  (2023-02-20T07:20:53Z)
• Emphatic Algorithms for Deep Reinforcement Learning [43.17171330951343]
  Temporal difference learning algorithms can become unstable when combined with function approximation and off-policy sampling. Emphatic temporal difference (ETD($lambda$) algorithm ensures convergence in the linear case by appropriately weighting the TD($lambda$) updates. We show that naively adapting ETD($lambda$) to popular deep reinforcement learning algorithms, which use forward view multi-step returns, results in poor performance.
  arXiv  Detail & Related papers  (2021-06-21T12:11:39Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  We propose a new reinforcement learning based ZO algorithm (ZO-RL) with learning the sampling policy for generating the perturbations in ZO optimization instead of using random sampling. Our results show that our ZO-RL algorithm can effectively reduce the variances of ZO gradient by learning a sampling policy, and converge faster than existing ZO algorithms in different scenarios.
  arXiv  Detail & Related papers  (2021-04-09T14:50:59Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Learning and Planning in Average-Reward Markov Decision Processes [15.586087060535398]
  We introduce learning and planning algorithms for average-reward MDPs. All of our algorithms are based on using the temporal-difference error rather than the conventional error when updating the estimate of the average reward.
  arXiv  Detail & Related papers  (2020-06-29T19:03:24Z)
• Structure-Adaptive Sequential Testing for Online False Discovery Rate Control [1.456699007803424]
  This work develops a new class of structure--adaptive sequential testing (SAST) rules for online false discover rate (FDR) control. A key element in our proposal is a new alpha--investment algorithm that precisely characterizes the gains and losses in sequential decision making.
  arXiv  Detail & Related papers  (2020-02-28T23:16:44Z)

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.