際際滷

際際滷Share a Scribd company logo

Jamieson_Jain2018

?
?
Masa Kato
Masa Kato

This document summarizes a paper titled "A Bandit Approach to Multiple Testing with False Discovery Control" by Jamieson and Jain from NIPS 2018. It introduces the problem of multiple hypothesis testing with the goals of controlling false discovery rate (FDR) and family-wise error rate (FWER) while maximizing true positive rate (TPR) and family-wise probability of detection (FWPD). It describes using an adaptive sampling strategy based on multi-armed bandits to achieve these goals with near-optimal sample complexity.

1 of 41
Download to read offline
A Bandit Approach to Multiple Testing with False Discovery Control Jamieson and Jain, NIPS 2018 Dec. 1th, 2018 @Ichimura Seminar
Jamieson_Jain2018
n nUnited States Food & Drug Administration (FDA) 1. 2. 3. 4. 5. 6. 7. 8
n n n Adaptive Design nFDA
nClinical Trial: Hao et al. Nature 2008, Rocklin et al. Science 2017. nEconomics: Hahn, Hirano and Karlan, Journal of Business & Economic Statistics 2011. n 9 Adaptive Design Methods in Clinical Trials Chow and Chang, 2012
n Multi-armed Bandit Problem; MAB n MAB ! = 1,2, ´ . ( n ＾K￣ n ) n exploration exploitation
n n n ! = 1,2, ´ , ' () *) !? = arg max)（ 2,3,´,4 *) n 5 = 1,2, ´ ! = !(5) () 8)(5) n 9 !? ?;?(9) (< = ?[ ?;? 9 』 !?] n 9 fixed budget
n ? ! （ (0,1) ! ? ? ( ? ?+? ( 』 .? ＋ ! 0[(]
nMachine Learning: and , 2016 nEconomics: Fudenberg and He, Econometrica 2018.
? Sofia S. Villar and William F. Rosenberger (2017), Covariate-adjusted response-adaptive randomization for multi-arm clinical trials using a modified forward looking Gittins index rule, Biometrics ? Adam Smith and Sofia S. Villar (2017), Bayesian adaptive bandit-based designs using the Gittins index for multi-armed trials with normally distributed endpoints, Journal of Applied Statistics ? Yusuke Narita and Shota Yasui and Kohei Yata (2019), Efficient Counterfactual Learning from Bandit Feedback, AAAI
2 1 2 t 3 1 1 2 2 1 1 2 1 2 multiple comparison n n http://www.med.osaka-u.ac.jp/pub/kid/clinicaljournalclub1.html
A Bandit Approach to Multiple Testing with False Discovery Control
n A Bandit Approach to Multiple Testing with False Discovery Control, Jamieson and Jain, Neural Information Processing Systems (NIPS) 2018. ? 3 n ? false alarm n
n ! " 1 ? " # （ ! ? 1, ´ , ! )*,+ ゛ -* ? )*,+ （ 0,1 / 0 )*,+ = 2* n 23 ?/ = # （ ! : 2* > 23 , ?3 = # （ ! : 2* = 23 = ! ? ?/ ? # （ [!] 2* ?/ . ? ?/ : 23 ? ?3 : 23 " :+ ? [!] (# （ :+ # （ ?/ )
False Alarm n !（? false alarm |$_%”?_0 | %（? %−! |$_%”?_1 | |?_1 | n false alarm |$_%”?_0 | %（? %−! |$_%”?_1 | |?_1 |
False Alarm n False alarm ! （ (0,1) ( () )*+ , , -.) / （ ? 1 23”?6 23 ‥+ ＋ ! FDR-! ! （ (0,1) ( () )*+ , , -.) ? “;*+ < =; ” ?. 』 ? ＋ ! FWER-! 1 False Discovery Rate, FDR-! 2 Family-wise Error Rate, FWER-!
True Discovery n True discovery ! （ (0,1) F( () )=1 + , ,0) - D . /0”?0 ?1 ＋ 1 ? !-0 − - 1 8 ! ! （ (0,1) F( () )=1 + , ,0) - D ? ?1 ? /0 ＋ 1 ? !-0 − - 1 8 ! 3 True Positive Rate, TPR-!, - 4 Family-wise Probability of Detection, FWPD-!, -
n FWER-! FDR-! n FWPD-!, " TPR-!, " n
n !" ?1 statistical power 2 n 0 n 5 False Discovery Rate, FDR-% % （ (0,1) FDR-% FWER-% + ( ,- -=1 / , 00) " （ ? + - （ ? 1 0 0 !" ? [/] + + TPR-%, 5 FWPD-%, FWPD-% 5 （ ?
n n {FDR-!, FWER-!} {TPR-!, ", FWPD-! , "} 2 ? 2 FDR-!+ TPR-!, " FDR-!+ FWPD-! , " FWER-!+ TPR-!, " FWER-!+ FWPD-! , " ? {FDR-!, FWER-!} 2 {TPR-!, ", FWPD-! , "} 1 21 ? n ?1 = & ? ?0 confidence parameter! Δ ? min .（?1 0. ? 00
n 2 2! "# 2$ （ (0,1] # （ ?0 ? "# ＋ $ ＋ $ n Bonferroni selection rule: p "1 ＋ "2 ＋ ? ＋ "02 2 #2 123 = #: "# ＋ 6/0 . n FWER FDR 9 123 ” ?0 ＋ ? “#（?0 "# ＋ 6/0 ＋ 6 ?0 0 ＋ 6. ★ FDR n BH procedure: 2 FDR 21
n 2 Upper confidence bound (UCB) 2 3 ? Upper confidence bound Hoeffding 2 ? UCB p
n anytime confidence interval ? !"#,%: & ' . ? For any (, ?(”%,- . !"#,% ? "# ＋ 1 &, ( − 1 ? (. n 1(&, () ( 67 1 &, ( ＋ 67 log log; 2& /( & . ★
Jamieson_Jain2018
n !": FDR n ?": FWER n $" %" n FDR !" upper confidence bound &" n FWER FDR
False Alarm Control n n !" FDR 7 ? 2 confidence bound #(", &) (),* ? sup / （ 0,1 : 45),* ? 57 ＋ # ", / ＋ log< 2" exp ?" 45),* ? 57 < /AB . ? 5) = 57 E （ ?7 (),* anytime sub- uniformly distributed p-value ? “*IJ K (),* ＋ L ＋ L. ? p always-valid p-values ? 5) > 57 E （ ?J (),* *IJ K 5) = 57 E # ?,? 2
?Benjamini-Hochberg (BH) procedure ? 2p 8 ! " ,$ % & ＋ ! ( ,$ ) & ＋ ? ＋ ! + ,$ , & . ? 2 ./ 0128 ./ = max /: ! 8 ,$ 9 ,: 9 ; ＋ < / = >=? 012 = @: !A,$B & ＋ < ./ = . ? 8 C / = @: !A,$B & ＋ < / = = @: DEA,$B & ? G HA I , < / = − KL . ./ = max /: C(/) − / >=? 012 = C(./) ?Algorithm12 0& anytime p-values2BH-procedure8 2 FDR 8 Lemma 1
n ?" FWER ? ?$ ? 29FWER+FWPD 2 ? Bonferroni correction ? “'（?) “"*$ + ?-'," ? 0 1, 2 3 ? ?$ − -5 ＋ 7 '（?) ? “"*$ + ?-'," ? 0 1, 2 ?$ − -5 ＋ ?5 2 ?5 . ?$ 9"
Sampling Strategies to Boost Statistical Power n ? !" ?" $% &% n TPR-' ( setting: ? ? = + （ ?1: 01+,3+ " + 5 3+ " , ' − 1+, ?" （ ? . ? 53anytime confidence bound : ? − 1 ? ' ?1 ? Δ = min +（?1 1+ ? 10 0 min +（? 1+ − 10 + Δ 0 1 ? A(') D "=1 ± F $" （ ?0, ? ? !" ＋ D "=1 ± F $" （ ?0, 01$",3$" " + 5 3$" " , ' − 10 + Δ ＋ I ?0 Δ?2 log log Δ?2/'
n FWPD-!, " setting: ? 31 ?1 ? &' ? max ,（?1”&' / 01,,3, ' + 5 3, ' , ! − min ,（?1”&' / 1, − 10 + Δ. ? ?1 1 3 <' − ?1 1 ? “,（?1 “'=1 ± 01,,' + 5 ', ! <' < 1, ＋ C D（?1 ? “'=1 ± 01,,' + 5 ', ! <' < 1, ＋ ?1 ! <' . ?E &F
n {FDR-!, FWER-!} {TPR-!, FWPD-!} n 2 ? near-optimal near-optimal ? 3
Jamieson_Jain2018
n Jarvis Haupt, Rui M Castro, and Robert Nowak. Distilled sensing: Adaptive sampling for sparse detection and estimation. IEEE Transactions on Information Theory , 57(9):6222C 6235, 2011. n ?" FWER+FWPD top-k identification problem 3 n # 4 Lijie Chen, Jian Li, and Mingda Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics , pages 101C110, 2017. n Ramesh Johari, Leo Pekelis, and David J Walsh. Always valid inference: Bringing sequential analysis to a/b testing. arXiv preprint arXiv:1512.04922 , 2015.
n ┨ confidence bound ┨ 5 3 ?" = $ ? ?& confidence parameter' Δ ? min -（?/ 0- ? 0&
1 (FDR, TPR) ?1 ?0 ?1 = % （ ' : )% > )0 ?0 = % （ ' : )% ＋ )0 3 Δ% = )% ? )0 ./0 % （ ?1 Δ = min %（?1 Δ% Δ% = min 4（?1 )4 ? )% = Δ + )0 ? )% ./0 % （ ?0 6 （ ? 8 96”?0 96 ‥1 ＋ < 1 ? 2< 3 > 6 T ? min 'Δ?2 log log Δ?2 < , E %（?0 Δ% ?2 log log Δ% ?2 /< + E %（?1 Δ% ?2 log log Δ% ?2 /< G'H 8 96 ” ?1 ?1 − 1 ? < ./0 GJJ 6 − >.
2 (FDR, FWPD) ! （ ? $ %!”?0 %! ‥1 ＋ , 7 1 ? 5, 3 / T ? 2 ? ?1 Δ?2 log max ?1 , log log 2/, log Δ?2 /, + ?1 Δ?2 log log Δ?2 /, >2? ?1 ? %! ABC >DD ! − /.
3 (FWER, FWPD) ! （ ? $ %!”?0 %! ‥1 ＋ , 3 1 ? 6, ! （ ? ?0 ” ?! = ? 8 2 T ? 5 ? ?6 Δ89 log max ?6 , log log 5/, log Δ89 /, + ?6 Δ89 log max 5 ? 1 ? 2, 1 + 4, ?6 , log log(5/, log Δ89 /, F5G ?1 ? %! IJK FLL ! − 2 3 ! − 2 ?6 = ?N
4 (FWER, TPR) ! （ ? $ %&”?) %& ‥+ ＋ - 3 9 1 ? 7- ! （ ? ?1 ” ?3 = ? 6 3 T ? 9 ? ?+ Δ;< log log Δ;< /- + ?+ Δ;< log max 9 ? 1 ? E ?+ , log log(9/- log Δ;< /- H9I$ ?3 ” ?+ ?+ − 1 ? -KLM HNN ! − 6 E = (1 ? 3- ? 2- log 1/- / ?+
Jamieson_Jain2018
Jamieson_Jain2018
n n

More Related Content

Jamieson_Jain2018

  • 1. A Bandit Approach to Multiple Testing with False Discovery Control Jamieson and Jain, NIPS 2018 Dec. 1th, 2018 @Ichimura Seminar
  • 3. n nUnited States Food & Drug Administration (FDA) 1. 2. 3. 4. 5. 6. 7. 8
  • 5. nClinical Trial: Hao et al. Nature 2008, Rocklin et al. Science 2017. nEconomics: Hahn, Hirano and Karlan, Journal of Business & Economic Statistics 2011. n 9 Adaptive Design Methods in Clinical Trials Chow and Chang, 2012
  • 6. n Multi-armed Bandit Problem; MAB n MAB ! = 1,2, ´ . ( n ＾K￣ n ) n exploration exploitation
  • 7. n n n ! = 1,2, ´ , ' () *) !? = arg max)（ 2,3,´,4 *) n 5 = 1,2, ´ ! = !(5) () 8)(5) n 9 !? ?;?(9) (< = ?[ ?;? 9 』 !?] n 9 fixed budget
  • 8. n ? ! （ (0,1) ! ? ? ( ? ?+? ( 』 .? ＋ ! 0[(]
  • 9. nMachine Learning: and , 2016 nEconomics: Fudenberg and He, Econometrica 2018.
  • 10. ? Sofia S. Villar and William F. Rosenberger (2017), Covariate-adjusted response-adaptive randomization for multi-arm clinical trials using a modified forward looking Gittins index rule, Biometrics ? Adam Smith and Sofia S. Villar (2017), Bayesian adaptive bandit-based designs using the Gittins index for multi-armed trials with normally distributed endpoints, Journal of Applied Statistics ? Yusuke Narita and Shota Yasui and Kohei Yata (2019), Efficient Counterfactual Learning from Bandit Feedback, AAAI
  • 11. 2 1 2 t 3 1 1 2 2 1 1 2 1 2 multiple comparison n n http://www.med.osaka-u.ac.jp/pub/kid/clinicaljournalclub1.html
  • 12. A Bandit Approach to Multiple Testing with False Discovery Control
  • 13. n A Bandit Approach to Multiple Testing with False Discovery Control, Jamieson and Jain, Neural Information Processing Systems (NIPS) 2018. ? 3 n ? false alarm n
  • 14. n ! " 1 ? " # （ ! ? 1, ´ , ! )*,+ ゛ -* ? )*,+ （ 0,1 / 0 )*,+ = 2* n 23 ?/ = # （ ! : 2* > 23 , ?3 = # （ ! : 2* = 23 = ! ? ?/ ? # （ [!] 2* ?/ . ? ?/ : 23 ? ?3 : 23 " :+ ? [!] (# （ :+ # （ ?/ )
  • 15. False Alarm n !（? false alarm |$_%”?_0 | %（? %−! |$_%”?_1 | |?_1 | n false alarm |$_%”?_0 | %（? %−! |$_%”?_1 | |?_1 |
  • 16. False Alarm n False alarm ! （ (0,1) ( () )*+ , , -.) / （ ? 1 23”?6 23 ‥+ ＋ ! FDR-! ! （ (0,1) ( () )*+ , , -.) ? “;*+ < =; ” ?. 』 ? ＋ ! FWER-! 1 False Discovery Rate, FDR-! 2 Family-wise Error Rate, FWER-!
  • 17. True Discovery n True discovery ! （ (0,1) F( () )=1 + , ,0) - D . /0”?0 ?1 ＋ 1 ? !-0 − - 1 8 ! ! （ (0,1) F( () )=1 + , ,0) - D ? ?1 ? /0 ＋ 1 ? !-0 − - 1 8 ! 3 True Positive Rate, TPR-!, - 4 Family-wise Probability of Detection, FWPD-!, -
  • 18. n FWER-! FDR-! n FWPD-!, " TPR-!, " n
  • 19. n !" ?1 statistical power 2 n 0 n 5 False Discovery Rate, FDR-% % （ (0,1) FDR-% FWER-% + ( ,- -=1 / , 00) " （ ? + - （ ? 1 0 0 !" ? [/] + + TPR-%, 5 FWPD-%, FWPD-% 5 （ ?
  • 20. n n {FDR-!, FWER-!} {TPR-!, ", FWPD-! , "} 2 ? 2 FDR-!+ TPR-!, " FDR-!+ FWPD-! , " FWER-!+ TPR-!, " FWER-!+ FWPD-! , " ? {FDR-!, FWER-!} 2 {TPR-!, ", FWPD-! , "} 1 21 ? n ?1 = & ? ?0 confidence parameter! Δ ? min .（?1 0. ? 00
  • 21. n 2 2! "# 2$ （ (0,1] # （ ?0 ? "# ＋ $ ＋ $ n Bonferroni selection rule: p "1 ＋ "2 ＋ ? ＋ "02 2 #2 123 = #: "# ＋ 6/0 . n FWER FDR 9 123 ” ?0 ＋ ? “#（?0 "# ＋ 6/0 ＋ 6 ?0 0 ＋ 6. ★ FDR n BH procedure: 2 FDR 21
  • 22. n 2 Upper confidence bound (UCB) 2 3 ? Upper confidence bound Hoeffding 2 ? UCB p
  • 23. n anytime confidence interval ? !"#,%: & ' . ? For any (, ?(”%,- . !"#,% ? "# ＋ 1 &, ( − 1 ? (. n 1(&, () ( 67 1 &, ( ＋ 67 log log; 2& /( & . ★
  • 25. n !": FDR n ?": FWER n $" %" n FDR !" upper confidence bound &" n FWER FDR
  • 26. False Alarm Control n n !" FDR 7 ? 2 confidence bound #(", &) (),* ? sup / （ 0,1 : 45),* ? 57 ＋ # ", / ＋ log< 2" exp ?" 45),* ? 57 < /AB . ? 5) = 57 E （ ?7 (),* anytime sub- uniformly distributed p-value ? “*IJ K (),* ＋ L ＋ L. ? p always-valid p-values ? 5) > 57 E （ ?J (),* *IJ K 5) = 57 E # ?,? 2
  • 27. ?Benjamini-Hochberg (BH) procedure ? 2p 8 ! " ,$ % & ＋ ! ( ,$ ) & ＋ ? ＋ ! + ,$ , & . ? 2 ./ 0128 ./ = max /: ! 8 ,$ 9 ,: 9 ; ＋ < / = >=? 012 = @: !A,$B & ＋ < ./ = . ? 8 C / = @: !A,$B & ＋ < / = = @: DEA,$B & ? G HA I , < / = − KL . ./ = max /: C(/) − / >=? 012 = C(./) ?Algorithm12 0& anytime p-values2BH-procedure8 2 FDR 8 Lemma 1
  • 28. n ?" FWER ? ?$ ? 29FWER+FWPD 2 ? Bonferroni correction ? “'（?) “"*$ + ?-'," ? 0 1, 2 3 ? ?$ − -5 ＋ 7 '（?) ? “"*$ + ?-'," ? 0 1, 2 ?$ − -5 ＋ ?5 2 ?5 . ?$ 9"
  • 29. Sampling Strategies to Boost Statistical Power n ? !" ?" $% &% n TPR-' ( setting: ? ? = + （ ?1: 01+,3+ " + 5 3+ " , ' − 1+, ?" （ ? . ? 53anytime confidence bound : ? − 1 ? ' ?1 ? Δ = min +（?1 1+ ? 10 0 min +（? 1+ − 10 + Δ 0 1 ? A(') D "=1 ± F $" （ ?0, ? ? !" ＋ D "=1 ± F $" （ ?0, 01$",3$" " + 5 3$" " , ' − 10 + Δ ＋ I ?0 Δ?2 log log Δ?2/'
  • 30. n FWPD-!, " setting: ? 31 ?1 ? &' ? max ,（?1”&' / 01,,3, ' + 5 3, ' , ! − min ,（?1”&' / 1, − 10 + Δ. ? ?1 1 3 <' − ?1 1 ? “,（?1 “'=1 ± 01,,' + 5 ', ! <' < 1, ＋ C D（?1 ? “'=1 ± 01,,' + 5 ', ! <' < 1, ＋ ?1 ! <' . ?E &F
  • 31. n {FDR-!, FWER-!} {TPR-!, FWPD-!} n 2 ? near-optimal near-optimal ? 3
  • 33. n Jarvis Haupt, Rui M Castro, and Robert Nowak. Distilled sensing: Adaptive sampling for sparse detection and estimation. IEEE Transactions on Information Theory , 57(9):6222C 6235, 2011. n ?" FWER+FWPD top-k identification problem 3 n # 4 Lijie Chen, Jian Li, and Mingda Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics , pages 101C110, 2017. n Ramesh Johari, Leo Pekelis, and David J Walsh. Always valid inference: Bringing sequential analysis to a/b testing. arXiv preprint arXiv:1512.04922 , 2015.
  • 34. n ┨ confidence bound ┨ 5 3 ?" = $ ? ?& confidence parameter' Δ ? min -（?/ 0- ? 0&
  • 35. 1 (FDR, TPR) ?1 ?0 ?1 = % （ ' : )% > )0 ?0 = % （ ' : )% ＋ )0 3 Δ% = )% ? )0 ./0 % （ ?1 Δ = min %（?1 Δ% Δ% = min 4（?1 )4 ? )% = Δ + )0 ? )% ./0 % （ ?0 6 （ ? 8 96”?0 96 ‥1 ＋ < 1 ? 2< 3 > 6 T ? min 'Δ?2 log log Δ?2 < , E %（?0 Δ% ?2 log log Δ% ?2 /< + E %（?1 Δ% ?2 log log Δ% ?2 /< G'H 8 96 ” ?1 ?1 − 1 ? < ./0 GJJ 6 − >.
  • 36. 2 (FDR, FWPD) ! （ ? $ %!”?0 %! ‥1 ＋ , 7 1 ? 5, 3 / T ? 2 ? ?1 Δ?2 log max ?1 , log log 2/, log Δ?2 /, + ?1 Δ?2 log log Δ?2 /, >2? ?1 ? %! ABC >DD ! − /.
  • 37. 3 (FWER, FWPD) ! （ ? $ %!”?0 %! ‥1 ＋ , 3 1 ? 6, ! （ ? ?0 ” ?! = ? 8 2 T ? 5 ? ?6 Δ89 log max ?6 , log log 5/, log Δ89 /, + ?6 Δ89 log max 5 ? 1 ? 2, 1 + 4, ?6 , log log(5/, log Δ89 /, F5G ?1 ? %! IJK FLL ! − 2 3 ! − 2 ?6 = ?N
  • 38. 4 (FWER, TPR) ! （ ? $ %&”?) %& ‥+ ＋ - 3 9 1 ? 7- ! （ ? ?1 ” ?3 = ? 6 3 T ? 9 ? ?+ Δ;< log log Δ;< /- + ?+ Δ;< log max 9 ? 1 ? E ?+ , log log(9/- log Δ;< /- H9I$ ?3 ” ?+ ?+ − 1 ? -KLM HNN ! − 6 E = (1 ? 3- ? 2- log 1/- / ?+
  • 41. n n