Pith. sign in

REVIEW 4 major objections 4 minor 34 references

Uniform mean estimation for monotonic processes

T0 review · 4 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Pith's one-line read The paper constructs confidence bands that contain the entire mean function of a monotonic process at every time and every point, with probability at least $1-\delta$, using coin-betting and monotonicity.

desk verdict Genuinely new monotonicity-based derandomization turns PAC-Bayes average bounds into uniform pointwise confidence bands; the core proof holds, but the KT regret citation is imprecise and equation (7) has typos. read the letter →

arxiv 2502.01244 v1 pith:OV4SHSPI submitted 2025-02-03 math.ST stat.TH

classification math.STstat.TH MSC 62G0562L1262G30
keywords anytime-validinferencecoin-bettingconfidencebandsCDFestimationmonotonicstochasticprocessesPAC-Bayesuniformsequencesequential
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper develops confidence bands that, with high probability, contain the whole mean function of a monotonic stochastic process--such as a cumulative distribution function--simultaneously at every sample size and every point of the domain. The bands are anytime-valid, so a user may stop at any time without breaking coverage. They adapt to the local variance of the process, becoming tight near 0 and 1 where a CDF is nearly constant, unlike the classical uniform bound for empirical CDFs. The method works by turning a coin-betting gamble into a per-point interval and then using monotonicity to merge those pointwise intervals into a uniform band.

What carries the argument

The load-bearing objects are the functions $\psi_T(y,\mu)$ and their inverses $\psi^{-1}_{T,\pm}$, defined from the log-wealth of a coin-betting gambler on the centred observations $f(X_t,y)-\mu$. A regret bound for the KT mixture forecaster (imported from the prediction literature) gives an anytime-valid bound on $\psi_T(y,F(y))$; a PAC-Bayesian variational inequality averages $\psi_T$ over nearby points $y_-$ and $y_+$; and Lemma 1--monotonicity of the inverses in $y$--converts the averaged bound into a pointwise bound uniform in $y$. The paper also exploits the piecewise-constant nature of the empirical CDF to make the band computable by checking only $T$ candidate points.

What would settle it

Run the CDF band (7) on many synthetic datasets from a known distribution, say $F(y)=y$ on $[0,1]$, with $T=1000$ and $\delta=0.05$; if over 10,000 replications the true CDF is not fully inside the band in at least 95% of runs, the uniform coverage claim is false. As a second check, evaluate numerically whether the imported regret inequality $R^{\mathrm{KT}}_T\le 2\sqrt{T}$ holds for all coin sequences in $[-1,1]$; a counterexample would break the proof.

Watch

Extended reading notes

Core claim

The central claim is Proposition 1: for $Y=[0,1]$ and a non-decreasing mean function $F(y)=\mathbb{E}[f(X,y)]$ with values in $[0,1]$, the interval with lower endpoint $\sup_{y_-\in[0,y_0]}\psi^{-1}_{T,-}(y_-,\log(2\sqrt{T}/((y_0-y_-)\delta)))$ and upper endpoint $\inf_{y_+\in[y_0,1]}\psi^{-1}_{T,+}(y_+,\log(2\sqrt{T}/((y_+-y_0)\delta)))$ contains $F(y_0)$ for every $y_0\in[0,1]$ and every $T\ge 1$ simultaneously, with probability at least $1-\delta$. The proof first obtains a PAC-Bayesian bound averaged over an interval of $y$-values, then uses monotonicity of the inverses (Lemma 1) to pass from the average to every point.

Load-bearing premise

The coverage guarantee depends entirely on two imported inequalities: the KT forecaster's regret bound $R_T\le 2\sqrt{T}$ and the lower bound $\psi_T(y,\mu)\ge T\,\mathrm{kl}(\hat F_T(y),\mu)$; if either is false or misstated, Proposition 1 does not follow.

Editorial extensions

If this is right

  • For CDF estimation, the band (7) is as tight as Proposition 1 and can be evaluated by checking only the observed order statistics, so it is computable in near-linear time.
  • The bands are anytime-valid, so they allow optional stopping and optional continuation in sequential data collection.
  • The band width adapts to the empirical variance, shrinking near the tails of the CDF where the classical uniform bound is loose.
  • A Pinsker-based relaxation yields a simple closed-form band (8) that resembles the classical DKW inequality, at some cost in tightness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the same 'average then derandomize by monotonicity' step could be applied to other PAC-Bayesian bounds, not only coin-betting, to produce uniform confidence bands for monotone regression curves or hazard functions.
  • Editorial extension: the finite-candidate simplification for the empirical CDF suggests that exact evaluation of the uniform band is possible whenever the estimator is piecewise constant with finitely many jumps, and a similar algorithm might work for cadlag estimators.
  • Editorial extension: replacing the KT forecaster with a lower-regret betting strategy would likely push the band width from $\sqrt{T^{-1}\log T}$ toward the $\sqrt{T^{-1}\log\log T}$ law-of-the-iterated-logarithm rate, at the cost of a more complex bound.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a method for constructing uniform anytime-valid confidence bands for the mean function F(y) = E[f(X,y)] of a bounded stochastic process, assuming f(x,.) is non-decreasing in y for every x. The construction combines the coin-betting/KT mixture forecaster regret bound with a PAC-Bayesian (Donsker-Varadhan) averaged bound and uses monotonicity to pass from an average guarantee to pointwise uniform guarantees. The main result, Proposition 1, gives a band whose endpoints are suprema and infima of the lower and upper inverses of the coin-betting log-wealth function psi_T. Section 4 provides kl- and Pinsker-based relaxations, plus a variance-adaptive relaxation; Section 5 specializes to CDF estimation, where the empirical CDF is piecewise constant, and gives a finite computation algorithm. Simulations compare the resulting CDF bands against the anytime-valid bands of Howard and Ramdas (2022).

Significance. Assuming the imported KT regret bound in Eq. (1) is valid, the central idea is sound and attractive: it converts a PAC-Bayesian average bound into a uniform pointwise band by monotonicity, producing explicit, anytime-valid, variance-adaptive CDF bands with no fitted constants. The paper is honest about the sqrt(log T) rate limitation and about the possibility that other e-value approaches could be even better. The main weaknesses are verification gaps: the KT regret bound is attributed to a source that does not state the continuous coin-betting wealth-ratio version, the proof of Proposition 1 contains an algebraic typo, Eq. (7) is misstated, and the variance-adaptive bound is imported without a theorem statement or a correct formula for the empirical variance. These are local and fixable within the manuscript's scope, but they are load-bearing for the advertised guarantees.

major comments (4)
  1. [Section 3, Eq. (1)] The bound R_KT^T <= 2 sqrt(T) for all coin sequences in [-1,1] is the sole source of the anytime-valid threshold in Eq. (3) and Proposition 1. The citation to Cesa-Bianchi and Lugosi (2006), Theorem 9.4, does not support this statement as written: that theorem concerns logarithmic-loss regret of the KT estimator for binary sequences, not the wealth-ratio regret of the continuous coin-betting forecaster used here. Please replace the citation with a precise theorem, for example from Orabona and Jun (2023), or include a proof, and verify that the constant 2 sqrt(T) holds under the stated conventions for a = 0 or b = 0.
  2. [Proof of Proposition 1] The displayed inequality after 'from (4) and (5)' writes the confidence threshold as log(2 sqrt(T)/(y+ - y0)) + integral_0^1 M_T(y) dy. Eq. (5) actually gives log(2 sqrt(T)/(y+ - y0)) + log(integral_0^1 M_T(y) dy). The displayed expression is not a valid consequence of (5); the subsequent Ville step controls the integral, so the intended argument is recoverable, but the proof as written contains a false step in the central derivation.
  3. [Section 4, Eq. (7)] As displayed, Eq. (7) uses the sample mean at y as the first argument of both kl inverses and uses (y - y-) in the denominator of the upper endpoint. The correct relaxation from Proposition 1 and Eq. (6) is: for the lower endpoint, kl^-1_- evaluated at the sample mean at y- with threshold 1/T log(2 sqrt(T)/((y-y-) delta)); for the upper endpoint, kl^-1_+ evaluated at the sample mean at y+ with threshold 1/T log(2 sqrt(T)/((y+ - y) delta)). Section 5 uses the corrected version, but the displayed theorem is unusable as written.
  4. [Section 4, variance-dependence] The variance-adaptive bound D_T(y,C) is introduced as 'a simplification of what is discussed in the proof of Theorem 3' of Orabona and Jun (2023), without stating the theorem or its hypotheses, and the empirical variance is defined as V_T(y) = 1/T sum (f(X_t,y) - sample mean at y), which omits the square in the summand. Since variance adaptation is advertised in the abstract and used in the proposed bands, please state the exact variance bound with sufficient detail to be checked and correct the definition of V_T(y).
minor comments (4)
  1. [Section 4, variance-dependence] In the displayed variance-adaptive band, the notation 'F_T(y)' should be 'F(y)'; F_T is not defined and the band is for the true mean function.
  2. [Section 3, footnote 5] The KT forecaster as defined in the footnote depends on the unknown F(y) through the previous coin outcomes c_i(y). The paper should clarify that this strategy is a proof device used to control regret and that the confidence intervals are computed through psi_T and its inverses, not by actually running the forecaster.
  3. [Section 5] The statement that the upper kl inverse is increasing in both of its arguments is used without proof or reference; a short justification would improve readability, since the argument is not entirely obvious at the boundary cases p = 0 and p = 1.
  4. [Section 7] The limitation paragraph is commendable: it explicitly notes the sqrt(1/T log T) rate and the possibility of improving the rate with the algorithm from Section IV of Orabona and Jun (2023).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the confidence-band derivation chains external, independent inequalities (KT regret, Donsker–Varadhan, Ville) through a new monotonicity argument; self-citations are not load-bearing.

full rationale

The derivation chain is self-contained relative to standard external results. The central guarantee, Proposition 1, is obtained by combining the KT-forecaster regret bound R_KT^T <= 2*sqrt(T) (Eq. 1, cited to Cesa-Bianchi and Lugosi, 2006, Theorem 9.4), the PAC-Bayesian inequality (5) via Donsker and Varadhan's variational formula, and Ville's inequality applied to the integrated wealth process. The proof of Proposition 1 then uses only the paper's own Lemma 1 (monotonicity of the inverses, proved from Lemma 3) and the fact that the integrated wealth is a nonnegative martingale. The relaxations (7) and (8) additionally import Orabona and Jun (2023, Proposition 1) as the lower bound psi_T(y,mu) >= T kl(F_hat_T(y), mu), which is an external result, not derived from the paper's target claim. Nothing is fitted to data, and no 'prediction' is a re-expression of an input: the uniform band is deduced, not assumed. The self-references (Clerico et al. 2022 for code used in numerical evaluations, and Clerico 2024a,b for optimality context) appear only in remarks and experiments; they do not support the mathematical coverage guarantee. The unproved imports (Eq. 1 and Eq. 6) are relevant to correctness or verifiability, but citing external theorems is not circularity. Therefore, the paper does not reduce its own inputs to its outputs and receives a score of 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The method rests on standard martingale and regret bounds from prior literature; it introduces no free parameters and no invented entities. The central novelty is the monotonicity-based derandomization, which is a proof technique rather than a new modeling entity.

assumptions (5)
  • standard math KT mixture forecaster regret bound R_KT^T <= 2 sqrt(T)
    Imported from Cesa-Bianchi and Lugosi (2006), Theorem 9.4; used in Eq. (3) and Proposition 1 to bound the wealth of the coin-betting game.
  • standard math Orabona-Jun lower bound psi_T(y, mu) >= T * kl(F_hat_T(y), mu)
    Proposition 1 of Orabona and Jun (2023), cited as Eq. (6); this converts the abstract psi-based bound into the explicit kl-based band (7).
  • standard math Donsker-Varadhan variational formula for KL divergence
    Used in Eq. (5) for the PAC-Bayesian continuous union bound.
  • domain assumption Observations are i.i.d. and f(x, y) is non-decreasing in y
    The monotonicity of f is the defining assumption of the problem; without it, Lemma 1 and Proposition 1 fail, and the proposed bands are not valid.
  • standard math Ville's inequality for non-negative supermartingales
    Used to bound the non-negative martingale M_T(y) and its integral in Proposition 1 and Eq. (2).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Uniform mean estimation for monotonic processes." pith.science (2026). https://pith.science/paper/OV4SHSPI

@misc{pith2026250201244,
  author       = {Pith},
  title        = {Pith review of: Uniform mean estimation for monotonic processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OV4SHSPI}},
  note         = {Machine review of arXiv:2502.01244}
}
read the original abstract

We consider the problem of deriving uniform confidence bands for the mean of a monotonic stochastic process, such as the cumulative distribution function (CDF) of a random variable, based on a sequence of i.i.d.~observations. Our approach leverages the coin-betting framework, and inherits several favourable characteristics of coin-betting methods. In particular, for each point in the domain of the mean function, we obtain anytime-valid confidence intervals that are numerically tight and adapt to the variance of the observations. To derive uniform confidence bands, we employ a continuous union bound that crucially leverages monotonicity. In the case of CDF estimation, we also exploit the fact that the empirical CDF is piece-wise constant to obtain simple confidence bands that can be easily computed. In simulations, we find that our confidence bands for the CDF achieve state-of-the-art performance.

Figures

Figures reproduced from arXiv: 2502.01244 by the authors.

Figure 1
Figure 1. CDF confidence bands from T = 1000 i.i.d. observations sampled from three different distributions supported in [0, 1]. Our method to produce the highlighted bands ensures that they contain the whole black line (the true CDF F) with probability at least 0.95 on the random datasets used to generate them. From left to right (in black): F(y) = y, F(y) = sin(π √y/2)6 , and F(y) = (3 + I{y ≥ 0.6})/4 + sin(2πy0.9 ) 3/10. T… view at source ↗
Figure 2
Figure 2. Confidence bands (δ = 0.05) for F(y) = sin π 2 √y 6 . The difference between the confidence bands and the true CDF is reported on the vertical axis. The confidence bands via our approach are plotted with a solid line. The dashed lines denote the confidence bands from Theorem 2 in Howard and Ramdas (2022), ∥Fˆ T − F∥∞ ≤ 0.85q 1 T [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 18 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...

  3. [3]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...

  4. [4]

    , year 2024

    author Alquier, P. , year 2024 . title User-friendly introduction to PAC -bayes bounds . journal Foundations and Trends in Machine Learning volume 17 , pages 174--303

  5. [5]

    On a variance dependent Dvoretzky-Kiefer-Wolfowitz inequality

    author Bartl, D. , author Mendelson, S. , year 2023 . title On a variance dependent Dvoretzky-Kiefer-Wolfowitz inequality . http://arxiv.org/abs/2308.04757 arXiv:2308.04757

  6. [6]

    , author Angelopoulos, A

    author Bates, S. , author Angelopoulos, A. , author Lei, L. , author Malik, J. , author Jordan, M. , year 2021 . title Distribution-free, risk-controlling prediction sets . journal Journal of the ACM volume 68

  7. [7]

    , year 1933

    author Cantelli, F.P. , year 1933 . title Sulla determinazione empirica delle leggi di probabilita . journal Giornale dell'Istituto italiano degli attuari volume 4 , pages 421--424

  8. [8]

    , author Lugosi, G

    author Cesa-Bianchi, N. , author Lugosi, G. , year 2006 . title Prediction, Learning, and Games . publisher Cambridge University Press

Show all 34 references
  1. [9]

    , year 2024 a

    author Clerico, E. , year 2024 a. title On the optimality of coin-betting for mean estimation . http://arxiv.org/abs/2412.02640 arXiv:2412.02640

  2. [10]

    , year 2024 b

    author Clerico, E. , year 2024 b. title Optimal e-value testing for properly constrained hypotheses . http://arxiv.org/abs/2412.21125 arXiv:2412.21125

  3. [11]

    , author Deligiannidis, G

    author Clerico, E. , author Deligiannidis, G. , author Doucet, A. , year 2022 . title Conditionally Gaussian PAC-Bayes , in: booktitle Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , pp. pages 2311--2329

  4. [12]

    , author Varadhan, S.S

    author Donsker, M.D. , author Varadhan, S.S. , year 1976 . title Asymptotic evaluation of certain markov process expectations for large time—iii . journal Communications on pure and applied Mathematics volume 29 , pages 389--461

  5. [13]

    , author Kiefer, J

    author Dvoretzky, A. , author Kiefer, J. , author Wolfowitz, J. , year 1956 . title Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator . journal The Annals of Mathematical Statistics volume 27 , pages 642 -- 669

  6. [14]

    , year 1933

    author Glivenko, V. , year 1933 . title Sulla determinazione empirica delle leggi di probabilita . journal Giornale dell'Istituto italiano degli attuari volume 4 , pages 92--99

  7. [15]

    , author Kaplan, D

    author Goldman, M. , author Kaplan, D. , year 2018 . title Comparing distributions by multiple testing across quantiles or CDF values . journal Journal of Econometrics volume 206 , pages 143--166

  8. [16]

    , author de Heide, R

    author Grünwald, P. , author de Heide, R. , author Koolen, W. , year 2024 . title Safe testing . journal Journal of the Royal Statistical Society Series B: Statistical Methodology volume 86 , pages 1091--1128

  9. [17]

    , author Lei, L

    author Hartog, W. , author Lei, L. , year 2025 . title Family-wise error rate control with e-values . http://arxiv.org/abs/2501.09015 arXiv:2501.09015

  10. [18]

    , author Ramdas, A

    author Howard, S. , author Ramdas, A. , year 2022 . title Sequential estimation of quantiles with applications to A/B testing and best-arm identification . journal Bernoulli volume 28 , pages 1704 -- 1728

  11. [19]

    , author Jun, K.S

    author Jang, K. , author Jun, K.S. , author Kuzborskij, I. , author Orabona, F. , year 2023 . title Tighter PAC -bayes bounds through coin-betting , in: booktitle The Thirty Sixth Annual Conference on Learning Theory , organization PMLR . pp. pages 2240--2264

  12. [20]

    , author Ramdas, A

    author Larsson, M. , author Ramdas, A. , author Ruf, J. , year 2024 . title The numeraire e-variable and reverse information projection . http://arxiv.org/abs/2402.18810 arXiv:2402.18810

  13. [21]

    , year 1990

    author Massart, P. , year 1990 . title The tight constant in the dvoretzky-kiefer-wolfowitz inequality . journal The annals of Probability , pages 1269--1283

  14. [22]

    , author Pathak, R

    author Nguyen, D. , author Pathak, R. , author Angelopoulos, A. , author Bates, S. , author Jordan, M. , year 2024 . title Data-adaptive tradeoffs among multiple risks in distribution-free prediction . http://arxiv.org/abs/2403.19605 arXiv:2403.19605

  15. [23]

    , author Jun, K.S

    author Orabona, F. , author Jun, K.S. , year 2023 . title Tight concentrations and confidence sequences from the regret of universal portfolio . journal IEEE Transactions on Information Theory volume 70 , pages 436--455

  16. [24]

    , author Gr \"u nwald, P

    author Ramdas, A. , author Gr \"u nwald, P. , author Vovk, V. , author Shafer, G. , year 2023 . title Game-theoretic statistics and safe anytime-valid inference . journal Statistical Science volume 38 , pages 576 -- 601

  17. [25]

    , author Ruf, J

    author Ramdas, A. , author Ruf, J. , author Larsson, M. , author Koolen, W. , year 2022 . title Admissible anytime-valid sequential inference must rely on nonnegative martingales . http://arxiv.org/abs/2009.03167 arXiv:2009.03167

  18. [26]

    , author Wang, R

    author Ramdas, A. , author Wang, R. , year 2024 . title Hypothesis testing with e-values . http://arxiv.org/abs/2410.23614 arXiv:2410.23614

  19. [27]

    , year 2021

    author Shafer, G. , year 2021 . title Testing by betting: A strategy for statistical and scientific communication . journal Journal of the Royal Statistical Society Series A: Statistics in Society volume 184 , pages 407--431

  20. [28]

    , author Vovk, V

    author Shafer, G. , author Vovk, V. , year 2019 . title Game-theoretic foundations for probability and finance . Wiley Series in Probability and Statistics, publisher Wiley

  21. [29]

    , author Wang, R

    author Vovk, V. , author Wang, R. , year 2021 . title E-values: Calibration, combination and applications . journal The Annals of Statistics volume 49 , pages 1736--1754

  22. [30]

    , author Ramdas, A

    author Wang, R. , author Ramdas, A. , year 2022 . title False discovery rate control with e-values . journal Journal of the Royal Statistical Society Series B: Statistical Methodology volume 84 , pages 822--852

  23. [31]

    , author Ramdas, A

    author Wasserman, L. , author Ramdas, A. , author Balakrishnan, S. , year 2020 . title Universal inference . journal Proceedings of the National Academy of Sciences volume 117 , pages 16880--16890

  24. [32]

    , author Ramdas, A

    author Waudby-Smith, I. , author Ramdas, A. , year 2023 . title Estimating means of bounded random variables by betting . journal Journal of the Royal Statistical Society Series B: Statistical Methodology volume 86 , pages 1--27

  25. [33]

    , author Ramdas, A

    author Xu, Z. , author Ramdas, A. , year 2023 . title Online multiple testing with e-values . http://arxiv.org/abs/2311.06412 arXiv:2311.06412

  26. [34]

    , author Ramdas, A

    author Xu, Z. , author Ramdas, A. , year 2024 . title More powerful multiple testing under dependence via randomization . http://arxiv.org/abs/2305.11126 arXiv:2305.11126

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.