commit 01225b5275cdae0215412fc0704c88bfc2128dd6
parent 55bab648d1e9a7b46ef8d51ff2b506dbb08dcc0c
Author: Jared Tobin <jared@jtobin.io>
Date: Thu, 4 Jun 2026 14:56:18 -0230
rename Agrapa to Adaptive, Ons to Newton
retains the aGRAPA acronym expansion in the Adaptive haddock.
Diffstat:
6 files changed, 82 insertions(+), 81 deletions(-)
diff --git a/README.md b/README.md
@@ -16,8 +16,8 @@ A sample GHCi session:
> import qualified Numeric.Eproc.Bounded as Bounded
>
> -- hypothesis: E[X] = 0.5 for samples in [0, 1] at alpha = 1e-3, tested
- > -- with the ONS bettor
- > let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ > -- with the Newton bettor
+ > let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
> let s0 = Bounded.initial cfg
>
> -- ten observations (drifting from hypothesis), and state afterwards
@@ -52,7 +52,7 @@ Current benchmark figures on an M4 Silicon MacBook Air look like (use
`cabal bench` to run the benchmark suite):
```
- benchmarking Bounded.update (one step)/ons
+ benchmarking Bounded.update (one step)/newton
time 13.05 ns (12.95 ns .. 13.17 ns)
1.000 R² (0.999 R² .. 1.000 R²)
mean 13.03 ns (12.95 ns .. 13.15 ns)
@@ -64,13 +64,13 @@ Current benchmark figures on an M4 Silicon MacBook Air look like (use
mean 4.828 μs (4.817 μs .. 4.847 μs)
std dev 44.90 ns (30.94 ns .. 61.54 ns)
- benchmarking Bounded.update (1000-sample fold)/agrapa
+ benchmarking Bounded.update (1000-sample fold)/adaptive
time 15.67 μs (15.66 μs .. 15.69 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 15.67 μs (15.65 μs .. 15.69 μs)
std dev 63.74 ns (55.65 ns .. 75.07 ns)
- benchmarking Bounded.update (1000-sample fold)/ons
+ benchmarking Bounded.update (1000-sample fold)/newton
time 14.43 μs (14.42 μs .. 14.44 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 14.43 μs (14.42 μs .. 14.44 μs)
diff --git a/bench/Main.hs b/bench/Main.hs
@@ -26,21 +26,21 @@ main = defaultMain [
update :: Benchmark
update =
let !cfg_f = Bounded.config 0.5 0.0 1.0 1.0e-3 (Bounded.Fixed 0.5)
- !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Agrapa
- !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Adaptive
+ !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
!st_f = Bounded.initial cfg_f
!st_a = Bounded.initial cfg_a
!st_o = Bounded.initial cfg_o
!x = 0.7
in bgroup "Bounded.update (one step)" [
bench "fixed" $ nf (Bounded.update cfg_f st_f) x
- , bench "agrapa" $ nf (Bounded.update cfg_a st_a) x
- , bench "ons" $ nf (Bounded.update cfg_o st_o) x
+ , bench "adaptive" $ nf (Bounded.update cfg_a st_a) x
+ , bench "newton" $ nf (Bounded.update cfg_o st_o) x
]
decide :: Benchmark
decide =
- let !cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ let !cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
!st = Bounded.initial cfg
in bgroup "Bounded.decide" [
bench "initial state" $ nf (Bounded.decide cfg) st
@@ -50,24 +50,24 @@ stream :: Benchmark
stream =
let !xs = force (take 1000 (cycle [0.3, 0.7]))
!cfg_f = Bounded.config 0.5 0.0 1.0 1.0e-3 (Bounded.Fixed 0.5)
- !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Agrapa
- !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Adaptive
+ !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
run_m cfg = foldl' (Bounded.update cfg) (Bounded.initial cfg)
in bgroup "Bounded.update (1000-sample fold)" [
bench "fixed" $ nf (run_m cfg_f) xs
- , bench "agrapa" $ nf (run_m cfg_a) xs
- , bench "ons" $ nf (run_m cfg_o) xs
+ , bench "adaptive" $ nf (run_m cfg_a) xs
+ , bench "newton" $ nf (run_m cfg_o) xs
]
twosample :: Benchmark
twosample =
let !ps = force (take 1000 (cycle [(0.3, 0.7), (0.7, 0.3)]))
!cfg_f = P.config 0.0 1.0 1.0e-3 (Bounded.Fixed 0.5)
- !cfg_a = P.config 0.0 1.0 1.0e-3 Bounded.Agrapa
- !cfg_o = P.config 0.0 1.0 1.0e-3 Bounded.Ons
+ !cfg_a = P.config 0.0 1.0 1.0e-3 Bounded.Adaptive
+ !cfg_o = P.config 0.0 1.0 1.0e-3 Bounded.Newton
run_t cfg = foldl' (P.update cfg) (P.initial cfg)
in bgroup "Paired.update (1000-sample fold)" [
bench "fixed" $ nf (run_t cfg_f) ps
- , bench "agrapa" $ nf (run_t cfg_a) ps
- , bench "ons" $ nf (run_t cfg_o) ps
+ , bench "adaptive" $ nf (run_t cfg_a) ps
+ , bench "newton" $ nf (run_t cfg_o) ps
]
diff --git a/bench/Weight.hs b/bench/Weight.hs
@@ -23,19 +23,19 @@ main = mainWith $ do
update :: Weigh ()
update =
let !cfg_f = Bounded.config 0.5 0.0 1.0 1.0e-3 (Bounded.Fixed 0.5)
- !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Agrapa
- !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Adaptive
+ !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
!st_f = Bounded.initial cfg_f
!st_a = Bounded.initial cfg_a
!st_o = Bounded.initial cfg_o
in wgroup "Bounded.update (one step)" $ do
func "fixed" (Bounded.update cfg_f st_f) 0.7
- func "agrapa" (Bounded.update cfg_a st_a) 0.7
- func "ons" (Bounded.update cfg_o st_o) 0.7
+ func "adaptive" (Bounded.update cfg_a st_a) 0.7
+ func "newton" (Bounded.update cfg_o st_o) 0.7
decide :: Weigh ()
decide =
- let !cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ let !cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
!st = Bounded.initial cfg
in wgroup "Bounded.decide" $ do
func "initial state" (Bounded.decide cfg) st
@@ -44,22 +44,22 @@ stream :: Weigh ()
stream =
let !xs = force (take 1000 (cycle [0.3, 0.7]))
!cfg_f = Bounded.config 0.5 0.0 1.0 1.0e-3 (Bounded.Fixed 0.5)
- !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Agrapa
- !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ !cfg_a = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Adaptive
+ !cfg_o = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
run_m cfg = foldl' (Bounded.update cfg) (Bounded.initial cfg)
in wgroup "Bounded.update (1000-sample fold)" $ do
func "fixed" (run_m cfg_f) xs
- func "agrapa" (run_m cfg_a) xs
- func "ons" (run_m cfg_o) xs
+ func "adaptive" (run_m cfg_a) xs
+ func "newton" (run_m cfg_o) xs
twosample :: Weigh ()
twosample =
let !ps = force (take 1000 (cycle [(0.3, 0.7), (0.7, 0.3)]))
!cfg_f = P.config 0.0 1.0 1.0e-3 (Bounded.Fixed 0.5)
- !cfg_a = P.config 0.0 1.0 1.0e-3 Bounded.Agrapa
- !cfg_o = P.config 0.0 1.0 1.0e-3 Bounded.Ons
+ !cfg_a = P.config 0.0 1.0 1.0e-3 Bounded.Adaptive
+ !cfg_o = P.config 0.0 1.0 1.0e-3 Bounded.Newton
run_t cfg = foldl' (P.update cfg) (P.initial cfg)
in wgroup "Paired.update (1000-sample fold)" $ do
func "fixed" (run_t cfg_f) ps
- func "agrapa" (run_t cfg_a) ps
- func "ons" (run_t cfg_o) ps
+ func "adaptive" (run_t cfg_a) ps
+ func "newton" (run_t cfg_o) ps
diff --git a/lib/Numeric/Eproc/Bounded.hs b/lib/Numeric/Eproc/Bounded.hs
@@ -61,7 +61,7 @@ import GHC.Exts (Double(D#))
-- observed strictly before step @t@ -- is what makes the resulting
-- wealth process a nonnegative supermartingale under @H_0@.
--
--- For 'Agrapa' and 'Ons', a per-direction safe-bet ceiling
+-- For 'Adaptive' and 'Newton', a per-direction safe-bet ceiling
-- @lambda_max@ is derived from the sample bounds supplied to
-- 'config' -- bets get clipped to @[0, lambda_max]@ so that the
-- wealth factor @1 + lambda * z@ stays nonnegative for every
@@ -71,23 +71,24 @@ import GHC.Exts (Double(D#))
-- does not respond to observed data; this strategy is useful only
-- as a baseline.
--
--- * 'Agrapa' is the aGRAPA (approximate growth-rate adaptive
+-- * 'Adaptive' is the aGRAPA (approximate growth-rate adaptive
-- predictable plug-in) bettor of Waudby-Smith & Ramdas (2024).
-- It tracks the empirical mean @mu@ and variance @sigma^2@ of
-- centred observations and bets the Kelly-optimal plug-in
-- @lambda* = mu \/ (sigma^2 + mu^2)@ clipped to
-- @[0, lambda_max]@. Fast to compute and competitive in practice.
--
--- * 'Ons' is the online Newton step bettor. The per-step log-wealth
--- loss @-log(1 + lambda * z)@ is convex in @lambda@; ONS performs
--- one Newton step per observation, accumulating squared gradients
--- to scale the update. Achieves logarithmic regret against the
--- best constant bet in hindsight and is in practice the strongest
--- of the three bettors under most signal regimes.
+-- * 'Newton' is the online Newton step (ONS) bettor. The per-step
+-- log-wealth loss @-log(1 + lambda * z)@ is convex in @lambda@;
+-- ONS performs one Newton step per observation, accumulating
+-- squared gradients to scale the update. Achieves logarithmic
+-- regret against the best constant bet in hindsight and is in
+-- practice the strongest of the three bettors under most signal
+-- regimes.
data Bettor =
Fixed {-# UNPACK #-} !Double
- | Agrapa
- | Ons
+ | Adaptive
+ | Newton
deriving (Eq, Show)
-- | Test outcome at the current sample count.
@@ -107,11 +108,11 @@ data Verdict =
-- in the enclosing 'Config'.
data BetState =
SFixed
- | SAgrapa
+ | SAdaptive
{-# UNPACK #-} !Double -- sum of z (centred observation)
{-# UNPACK #-} !Double -- sum of z^2 (for online variance)
{-# UNPACK #-} !Int -- count
- | SOns
+ | SNewton
{-# UNPACK #-} !Double -- current bet lambda
{-# UNPACK #-} !Double -- running sum of per-step squared gradients
@@ -168,21 +169,21 @@ tiny = D# 1.0e-300##
-- per-bettor initial state.
init_bet :: Bettor -> BetState
init_bet b = case b of
- Fixed _ -> SFixed
- Agrapa -> SAgrapa 0 0 0
- Ons -> SOns 0 1.0e-6 -- small acc seed avoids div-by-zero on first step
+ Fixed _ -> SFixed
+ Adaptive -> SAdaptive 0 0 0
+ Newton -> SNewton 0 1.0e-6 -- small acc seed avoids div-by-zero
{-# INLINE init_bet #-}
-- compute the next bet 'lambda' from the bettor and its current
-- state; 'lam_max' is the direction-specific safety bound. for
--- Agrapa we form a Kelly-style plug-in from the running sample mean
--- and variance; for Ons the bet is just the last lambda chosen by the
--- Newton step (updated during 'step_bet').
+-- Adaptive we form a Kelly-style plug-in from the running sample
+-- mean and variance; for Newton the bet is just the last lambda
+-- chosen by the Newton step (updated during 'step_bet').
bet_lambda :: Bettor -> Double -> BetState -> Double
bet_lambda b !lam_max !s = case b of
Fixed lam -> lam
- Agrapa -> case s of
- SAgrapa !sm !sm2 !n
+ Adaptive -> case s of
+ SAdaptive !sm !sm2 !n
| n == 0 -> 0
| otherwise ->
let !nd = fromIntegral n
@@ -193,30 +194,30 @@ bet_lambda b !lam_max !s = case b of
!raw = if den == 0 then 0 else mu / den
in max 0 (min lam_max raw)
_ -> 0
- Ons -> case s of
- SOns !lam _ -> lam
- _ -> 0
+ Newton -> case s of
+ SNewton !lam _ -> lam
+ _ -> 0
{-# INLINE bet_lambda #-}
-- update bettor state with newly observed centred value 'z'. for
--- Agrapa this is just accumulating sums; for Ons we take one Newton
--- step on the per-step log-wealth loss '-log(1 + lambda * z)',
+-- Adaptive this is just accumulating sums; for Newton we take one
+-- Newton step on the per-step log-wealth loss '-log(1 + lambda * z)',
-- accumulating squared gradients for adaptive scaling.
step_bet :: Bettor -> Double -> BetState -> Double -> BetState
step_bet b !lam_max !s !z = case b of
Fixed _ -> SFixed
- Agrapa -> case s of
- SAgrapa !sm !sm2 !n -> SAgrapa (sm + z) (sm2 + z * z) (n + 1)
- _ -> SAgrapa z (z * z) 1
- Ons -> case s of
- SOns !lam !acc ->
+ Adaptive -> case s of
+ SAdaptive !sm !sm2 !n -> SAdaptive (sm + z) (sm2 + z * z) (n + 1)
+ _ -> SAdaptive z (z * z) 1
+ Newton -> case s of
+ SNewton !lam !acc ->
let !denom = 1 + lam * z
!g = if denom == 0 then 0 else negate z / denom
!acc' = acc + g * g
!lam' = lam - g / acc'
!clp = max 0 (min lam_max lam')
- in SOns clp acc'
- _ -> SOns 0 1.0e-6
+ in SNewton clp acc'
+ _ -> SNewton 0 1.0e-6
{-# INLINE step_bet #-}
-- construction ---------------------------------------------------------------
@@ -242,7 +243,7 @@ step_bet b !lam_max !s !z = case b of
-- @log(2 \/ alpha)@; the 2 is the Bonferroni union-bound
-- adjustment for the two one-sided e-processes.
--
--- >>> let cfg = config 0.5 0.0 1.0 1.0e-3 Ons
+-- >>> let cfg = config 0.5 0.0 1.0 1.0e-3 Newton
config
:: Double -- ^ null mean @m@
-> Double -- ^ sample lower bound @lo@
diff --git a/lib/Numeric/Eproc/Paired.hs b/lib/Numeric/Eproc/Paired.hs
@@ -69,7 +69,7 @@ newtype State = State Bounded.State
-- on the differences, which lie in @[lo - hi, hi - lo]@ with null
-- mean @0@.
--
--- >>> let cfg = config 0.0 1.0 1.0e-3 Ons
+-- >>> let cfg = config 0.0 1.0 1.0e-3 Newton
config
:: Double -- ^ sample lower bound @lo@
-> Double -- ^ sample upper bound @hi@
diff --git a/test/Main.hs b/test/Main.hs
@@ -126,12 +126,12 @@ paired_avg_rate cfg pa pb budget trials seed =
sanity_tests :: TestTree
sanity_tests = testGroup "sanity" [
testCase "degenerate input never rejects" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 1.0e-6 Bounded.Ons
+ let cfg = Bounded.config 0.5 0.0 1.0 1.0e-6 Bounded.Newton
xs = replicate 5000 0.5
st = foldl' (Bounded.update cfg) (Bounded.initial cfg) xs
Bounded.decide cfg st @?= Bounded.Continue
, testCase "two-sided thresholds applied symmetrically" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 1.0e-6 Bounded.Ons
+ let cfg = Bounded.config 0.5 0.0 1.0 1.0e-6 Bounded.Newton
Bounded.decide cfg (Bounded.initial cfg) @?= Bounded.Continue
]
@@ -142,15 +142,15 @@ sanity_tests = testGroup "sanity" [
-- so the slack is small.
calibration_tests :: TestTree
calibration_tests = testGroup "null calibration" [
- testCase "ONS, Bernoulli(0.5), m=0.5, alpha=0.05" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 0.05 Bounded.Ons
+ testCase "Newton, Bernoulli(0.5), m=0.5, alpha=0.05" $ do
+ let cfg = Bounded.config 0.5 0.0 1.0 0.05 Bounded.Newton
rate = rejection_rate cfg 0.5 2000 200 12345
-- expected rate <= 0.05; allow up to 0.10 slack for sampling
-- variability over 200 trials.
assertBool ("FPR " ++ show rate ++ " exceeded slack") $
rate <= 0.10
- , testCase "aGRAPA, Bernoulli(0.5), m=0.5, alpha=0.05" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 0.05 Bounded.Agrapa
+ , testCase "Adaptive, Bernoulli(0.5), m=0.5, alpha=0.05" $ do
+ let cfg = Bounded.config 0.5 0.0 1.0 0.05 Bounded.Adaptive
rate = rejection_rate cfg 0.5 2000 200 67890
assertBool ("FPR " ++ show rate ++ " exceeded slack") $
rate <= 0.10
@@ -161,13 +161,13 @@ calibration_tests = testGroup "null calibration" [
-- under a clear shift, all (or nearly all) trials reject within budget.
power_tests :: TestTree
power_tests = testGroup "power" [
- testCase "ONS detects Bernoulli(0.7) vs m=0.5" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ testCase "Newton detects Bernoulli(0.7) vs m=0.5" $ do
+ let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
rate = rejection_rate cfg 0.7 5000 100 11111
assertBool ("power " ++ show rate ++ " too low") $
rate >= 0.95
- , testCase "aGRAPA detects Bernoulli(0.7) vs m=0.5" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Agrapa
+ , testCase "Adaptive detects Bernoulli(0.7) vs m=0.5" $ do
+ let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Adaptive
rate = rejection_rate cfg 0.7 5000 100 22222
assertBool ("power " ++ show rate ++ " too low") $
rate >= 0.95
@@ -178,11 +178,11 @@ power_tests = testGroup "power" [
two_sample_tests :: TestTree
two_sample_tests = testGroup "two-sample" [
testCase "identical distributions don't reject" $ do
- let cfg = P.config 0.0 1.0 1.0e-3 Bounded.Ons
+ let cfg = P.config 0.0 1.0 1.0e-3 Bounded.Newton
rate = paired_avg_rate cfg 0.5 0.5 2000 100 33333
assertBool ("FPR " ++ show rate) $ rate <= 0.05
, testCase "different distributions reject" $ do
- let cfg = P.config 0.0 1.0 1.0e-3 Bounded.Ons
+ let cfg = P.config 0.0 1.0 1.0e-3 Bounded.Newton
rate = paired_avg_rate cfg 0.3 0.7 5000 100 44444
assertBool ("power " ++ show rate) $ rate >= 0.95
]
@@ -198,13 +198,13 @@ bettor_smoke_tests = testGroup "bettor smoke" [
xs = take 100 (cycle [0.0, 1.0])
st = foldl' (Bounded.update cfg) (Bounded.initial cfg) xs
assertBool "samples advanced" (Bounded.samples st == 100)
- , testCase "ONS bettor runs without error" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Ons
+ , testCase "Newton bettor runs without error" $ do
+ let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton
xs = take 100 (cycle [0.0, 1.0])
st = foldl' (Bounded.update cfg) (Bounded.initial cfg) xs
assertBool "samples advanced" (Bounded.samples st == 100)
- , testCase "aGRAPA bettor runs without error" $ do
- let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Agrapa
+ , testCase "Adaptive bettor runs without error" $ do
+ let cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Adaptive
xs = take 100 (cycle [0.0, 1.0])
st = foldl' (Bounded.update cfg) (Bounded.initial cfg) xs
assertBool "samples advanced" (Bounded.samples st == 100)
