eproc

Anytime-valid sequential testing and confidence sequences.
git clone git://git.ppad.tech/eproc.git
Log | Files | Refs | README | LICENSE

README.md (4470B)

      1 # ppad-eproc
      2 
      3 [![](https://img.shields.io/hackage/v/ppad-eproc?color=blue)](https://hackage.haskell.org/package/ppad-eproc)
      4 ![](https://img.shields.io/badge/license-MIT-brightgreen)
      5 [![](https://img.shields.io/badge/haddock-eproc-lightblue)](https://docs.ppad.tech/eproc)
      6 
      7 A pure Haskell implementation of anytime-valid sequential hypothesis
      8 tests and confidence sequences for bounded random variables, via the
      9 e-process ("testing by betting") framework of [Waudby-Smith & Ramdas
     10 (2024)][wsr24].
     11 
     12 Observations are consumed one at a time. Unlike with classical tests,
     13 you can check the verdict (or the confidence interval) after every
     14 observation and stop whenever you like, without inflating the error
     15 rate.
     16 
     17 Includes tests for bounded means, paired differences, and Bernoulli
     18 rates, mixtures of such tests, and confidence sequences for bounded
     19 means.
     20 
     21 ## Usage
     22 
     23 A sample GHCi session:
     24 
     25 ```
     26   > -- import qualified
     27   > import qualified Numeric.Eproc.Bounded as B
     28   > import Data.List (find)
     29   >
     30   > -- test H_0: E[x] = 0.5 for x in [0, 1], at level 0.001
     31   > let Right cfg = B.config 0.5 0.0 1.0 1.0e-3 B.Newton
     32   >
     33   > -- a stream of observations with mean 0.8
     34   > let xs = cycle [1, 1, 0, 1, 1, 0, 1, 1, 1, 1]
     35   >
     36   > -- after ten observations, the evidence is weak
     37   > let s10 = foldl' (B.update cfg) (B.initial cfg) (take 10 xs)
     38   > B.decide cfg s10
     39   Continue
     40   > B.p_value s10
     41   0.8
     42   >
     43   > -- check after every observation, stopping at the first rejection
     44   > let ss = scanl (B.update cfg) (B.initial cfg) xs
     45   > let Just s = find ((== B.Reject) . B.decide cfg) ss
     46   > B.samples s
     47   59
     48   > B.p_value s
     49   8.474770976464489e-4
     50 ```
     51 
     52 Confidence sequences are the estimation analogue: intervals that are
     53 valid at every sample size simultaneously. Continuing from the above:
     54 
     55 ```
     56   > import qualified Numeric.Eproc.ConfSeq as C
     57   >
     58   > -- 95% confidence sequence for the mean of x in [0, 1], on a
     59   > -- 100-point grid
     60   > let Right cfg = C.config 0.0 1.0 0.05 100
     61   > let after n = foldl' (C.update cfg) (C.initial cfg) (take n xs)
     62   >
     63   > C.interval cfg (after 10)
     64   Just (0.3564356435643564,1.0)
     65   > C.interval cfg (after 100)
     66   Just (0.6633663366336634,0.9108910891089109)
     67   > C.interval cfg (after 1000)
     68   Just (0.7425742574257426,0.8514851485148515)
     69 ```
     70 
     71 See the haddocks for additional examples.
     72 
     73 ## Documentation
     74 
     75 Haddocks (API documentation, etc.) are hosted at
     76 [docs.ppad.tech/eproc](https://docs.ppad.tech/eproc).
     77 
     78 ## Performance
     79 
     80 Current benchmark figures on an M4 Silicon MacBook Air look like (use
     81 `cabal bench` to run the benchmark suite):
     82 
     83 ```
     84   benchmarking Bounded.update (one step)/newton
     85   time                 15.27 ns   (15.23 ns .. 15.30 ns)
     86 
     87   benchmarking Bounded.update (1000-sample fold)/fixed
     88   time                 8.271 μs   (8.266 μs .. 8.275 μs)
     89 
     90   benchmarking Bounded.update (1000-sample fold)/adaptive
     91   time                 15.38 μs   (15.35 μs .. 15.41 μs)
     92 
     93   benchmarking Bounded.update (1000-sample fold)/newton
     94   time                 17.00 μs   (16.98 μs .. 17.02 μs)
     95 
     96   benchmarking Bernoulli.update (1000-sample fold)/newton
     97   time                 14.85 μs   (14.84 μs .. 14.87 μs)
     98 
     99   benchmarking Bernoulli.TwoSided.update (1000-sample fold)/newton
    100   time                 16.70 μs   (16.68 μs .. 16.72 μs)
    101 
    102   benchmarking Mixture.update (one step)/K=4
    103   time                 22.24 ns   (22.21 ns .. 22.27 ns)
    104 
    105   benchmarking ConfSeq.update (one step, g = 200)/plug-in
    106   time                 2.100 μs   (2.097 μs .. 2.103 μs)
    107 
    108   benchmarking ConfSeq.update (1000-sample fold, g = 200)/plug-in
    109   time                 193.3 μs   (192.3 μs .. 194.5 μs)
    110 ```
    111 
    112 You should compile with the 'llvm' flag for maximum performance.
    113 
    114 ## Development
    115 
    116 You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a
    117 development shell with:
    118 
    119 ```
    120 $ nix develop
    121 ```
    122 
    123 Then do e.g.:
    124 
    125 ```
    126 $ cabal repl ppad-eproc
    127 ```
    128 
    129 to get a REPL for the main library.
    130 
    131 ## References
    132 
    133 - Waudby-Smith & Ramdas (2024), "[Estimating means of bounded random
    134   variables by betting][wsr24]." JRSS-B.
    135 - Ramdas, Grünwald, Vovk, Shafer (2023), "[Game-theoretic statistics
    136   and safe anytime-valid inference][rgvs23]." Statistical Science.
    137 - Shafer (2021), "[Testing by betting][shafer21]." JRSS-A.
    138 
    139 [nixos]: https://nixos.org/
    140 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html
    141 [wsr24]: https://arxiv.org/abs/2010.09686
    142 [rgvs23]: https://arxiv.org/abs/2210.01948
    143 [shafer21]: https://arxiv.org/abs/1909.03807