pith. sign in

arxiv: 1906.10465 · v1 · pith:MQLDN4PPnew · submitted 2019-06-25 · 🧮 math.NA · cs.NA

Probabilistic Error Analysis for Inner Products

Ilse C.F. Ipsen , Hua Zhou This is my paper

Pith reviewed 2026-05-25 16:42 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords inner productroundoff errorprobabilistic boundsAzuma inequalityforward error analysisnumerical stabilitymartingale
0
0 comments X

The pith

Probabilistic bounds on the forward error of computed inner products scale with the square root of the vector length rather than the length itself.

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

The paper develops explicit non-asymptotic probabilistic bounds on the forward error of numerically computed inner products between two real n-vectors. It models both input perturbations and roundoff errors as bounded zero-mean random variables, derives one perturbation bound via Azuma's inequality under independence, and produces two roundoff bounds: one assuming independent roundoffs and one using a martingale to respect the sequential order of accumulation without that assumption. Experiments demonstrate that these bounds are tighter than classical deterministic bounds by orders of magnitude, even at small n and high success probabilities, and replace the usual linear growth in n with growth in sqrt(n). A reader would care because this supplies a quantitatively sharper picture of when and why inner-product computations remain reliable.

Core claim

Probabilistic perturbation bounds based on Azuma's inequality and probabilistic roundoff error bounds, one assuming independence of roundoffs and one using a martingale that mirrors the sequential accumulation order, yield explicit non-asymptotic forward-error estimates that depend on sqrt(n) and are more informative than deterministic bounds for small n and stringent success probabilities.

What carries the argument

Azuma's inequality applied to independent bounded zero-mean perturbations, together with a martingale constructed to track sequential roundoff accumulation without assuming independence.

If this is right

  • Error growth in inner products is governed by a random-walk-like accumulation rather than coherent worst-case addition.
  • Vectors of length n can be handled with error guarantees that degrade only like sqrt(n), postponing the onset of instability.
  • High success probabilities remain compatible with practical bounds that are still far smaller than deterministic ones.
  • The same modeling approach separates the effect of input perturbation from the effect of rounding during accumulation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The martingale technique could be reused to analyze sequential error propagation in other algorithms such as recursive summation or Gram-Schmidt.
  • The sqrt(n) scaling supplies a concrete quantitative basis for choosing block sizes or precision in large-scale inner-product-heavy kernels.
  • The distinction between the independent-roundoff bound and the martingale bound offers a way to quantify how much dependence among rounding errors actually costs in practice.

Load-bearing premise

Perturbations and roundoffs can be represented as bounded zero-mean random variables that are either independent or sequentially dependent in a martingale sense.

What would settle it

Numerical trials in which the realized forward error of an inner product exceeds the probabilistic bound more often than the failure probability permitted by the stated success level.

Figures

Figures reproduced from arXiv: 1906.10465 by Hua Zhou, Ilse C.F. Ipsen.

Figure 5
Figure 5. Figure 5: illustrates that, among the three amplifiers in (5.1), the tr [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: zooms in on the left panel in Figure 5.3 and illustrates that (5 [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: illustrates that the probabilistic result (5.7) tends to be at [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
read the original abstract

Probabilistic models are proposed for bounding the forward error in the numerically computed inner product (dot product, scalar product) between of two real $n$-vectors. We derive probabilistic perturbation bounds, as well as probabilistic roundoff error bounds for the sequential accumulation of the inner product. These bounds are non-asymptotic, explicit, and make minimal assumptions on perturbations and roundoffs. The perturbations are represented as independent, bounded, zero-mean random variables, and the probabilistic perturbation bound is based on Azuma's inequality. The roundoffs are also represented as bounded, zero-mean random variables. The first probabilistic bound assumes that the roundoffs are independent, while the second one does not. For the latter, we construct a Martingale that mirrors the sequential order of computations. Numerical experiments confirm that our bounds are more informative, often by several orders of magnitude, than traditional deterministic bounds -- even for small vector dimensions~$n$ and very stringent success probabilities. In particular the probabilistic roundoff error bounds are functions of $\sqrt{n}$ rather than~$n$, thus giving a quantitative confirmation of Wilkinson's intuition. The paper concludes with a critical assessment of the probabilistic approach.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes probabilistic models for the forward error in computed inner products of n-vectors. Perturbations are modeled as independent bounded zero-mean random variables with bounds derived via Azuma's inequality. Roundoff errors in sequential accumulation are modeled as bounded zero-mean random variables, with one bound assuming independence and a second using a martingale construction that respects the computation order. The paper presents explicit non-asymptotic bounds and reports numerical experiments claiming that the probabilistic bounds are tighter than deterministic ones by orders of magnitude, scaling as O(sqrt(n)) rather than O(n) and thereby confirming Wilkinson's intuition; the manuscript ends with a critical assessment of the probabilistic approach.

Significance. If the zero-mean modeling assumptions hold for actual floating-point roundoff, the explicit non-asymptotic bounds would supply a quantitative, dimensionally favorable alternative to classical deterministic analysis, with direct relevance to error estimation in high-dimensional linear algebra. The provision of both independent and martingale versions, together with the reported numerical comparisons, constitutes a concrete contribution to probabilistic numerical analysis.

major comments (2)
  1. [Abstract] Abstract (modeling paragraphs): The central claim that the probabilistic roundoff bounds scale as sqrt(n) rather than n rests on representing roundoffs as bounded zero-mean random variables (either independent or as a martingale). The manuscript states this modeling choice explicitly but supplies neither a derivation from floating-point semantics nor any empirical check demonstrating that actual roundoff errors in inner-product accumulation have zero conditional expectation; a small nonzero bias would produce linear accumulation and render the probabilistic bounds no tighter than deterministic ones in practice.
  2. [Numerical experiments] Numerical experiments section: The experiments are asserted to confirm that the new bounds are 'more informative, often by several orders of magnitude' even for small n and stringent success probabilities. Without details on how the synthetic roundoff errors were generated (i.e., whether they were forced to obey the zero-mean property or drawn from actual floating-point execution), it is impossible to determine whether the reported improvement validates the model or merely reproduces the modeling assumption.
minor comments (1)
  1. [Abstract] The abstract refers to 'the first probabilistic bound' and 'the second one' without numbering; adding explicit labels or section references would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (modeling paragraphs): The central claim that the probabilistic roundoff bounds scale as sqrt(n) rather than n rests on representing roundoffs as bounded zero-mean random variables (either independent or as a martingale). The manuscript states this modeling choice explicitly but supplies neither a derivation from floating-point semantics nor any empirical check demonstrating that actual roundoff errors in inner-product accumulation have zero conditional expectation; a small nonzero bias would produce linear accumulation and render the probabilistic bounds no tighter than deterministic ones in practice.

    Authors: We agree that the zero-mean property is introduced as a modeling assumption rather than derived from floating-point semantics. The paper proposes non-asymptotic bounds that hold under this assumption (and the boundedness condition), with the critical assessment section already noting limitations of the probabilistic approach. A nonzero bias would indeed cause linear accumulation and eliminate the sqrt(n) improvement. We will revise the abstract and introduction to state more explicitly that the bounds are conditional on the zero-mean modeling choice and that empirical verification of this assumption for actual roundoff is outside the paper's scope. This constitutes a partial revision. revision: partial

  2. Referee: [Numerical experiments] Numerical experiments section: The experiments are asserted to confirm that the new bounds are 'more informative, often by several orders of magnitude' even for small n and stringent success probabilities. Without details on how the synthetic roundoff errors were generated (i.e., whether they were forced to obey the zero-mean property or drawn from actual floating-point execution), it is impossible to determine whether the reported improvement validates the model or merely reproduces the modeling assumption.

    Authors: The experiments generate synthetic errors as independent bounded zero-mean random variables (drawn uniformly from the intervals consistent with the model) precisely to test the derived bounds under the modeling assumptions; they are not taken from actual floating-point runs. We will expand the numerical experiments section with an explicit description of the generation procedure, the distributions employed, and confirmation that the zero-mean property is enforced. This will clarify that the reported improvements validate the bounds under the stated model. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds follow from standard inequalities applied to explicitly stated external models

full rationale

The paper states its modeling assumptions explicitly (perturbations and roundoffs as independent bounded zero-mean RVs) and applies Azuma's inequality, a standard external result, to obtain the concentration bounds. The sqrt(n) scaling is a direct consequence of the zero-mean assumption under the martingale or independence construction; it is not obtained by fitting parameters to data or by redefining quantities in terms of themselves. No self-citations are invoked to justify the core premises or uniqueness of the approach. The derivation chain is therefore self-contained against the stated models and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Central claims rest on modeling assumptions about error random variables; no free parameters or invented entities are mentioned in the abstract.

axioms (2)
  • domain assumption Perturbations are independent, bounded, zero-mean random variables
    Invoked to apply Azuma's inequality for the perturbation bound.
  • domain assumption Roundoffs are bounded, zero-mean random variables
    Used for both the independent case and the martingale construction.

pith-pipeline@v0.9.0 · 5728 in / 1356 out tokens · 37021 ms · 2026-05-25T16:42:47.912904+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Babu ˇska and G

    I. Babu ˇska and G. S ¨oderlind, On roundoff error growth in elliptic problems , ACM Trans. Math. Software, 44 (2018), pp. Art. 33, 22. 21

    work page 2018

  2. [2]

    E. H. Bareiss and J. L. Barlow , Roundoff error distribution in fixed point multiplication , BIT, 20 (1980), pp. 247–250

    work page 1980

  3. [3]

    J. L. Barlow and E. H. Bareiss , On roundoff error distributions in floating point and loga- rithmic arithmetic , Computing, 34 (1985), pp. 325–347

    work page 1985

  4. [4]

    , Probabilistic error analysis of Gaussian elimination in flo ating point and logarithmic arithmetic, Computing, 34 (1985), pp. 349–364

    work page 1985

  5. [5]

    Bennani, M.-C

    M. Bennani, M.-C. Brunet, and F. Chatelin , De l’utilisation en calcul matriciel de mod` eles probabilistes pour la simulation des erreurs de calcul , C. R. Acad. Sci. Paris S´ er. I Math., 307 (1988), pp. 847–850

    work page 1988

  6. [6]

    Brunet and F

    M.-C. Brunet and F. Chatelin , CESTAC, a tool for a stochastic round-off error analysis in scientific computing , in Numerical mathematics and applications (Oslo, 1985), I MACS Trans. Sci. Comput. 85, I, North-Holland, Amsterdam, 1986, pp. 11–20

    work page 1985

  7. [7]

    Calvetti , Roundoff error for floating point representation of real data , Comm

    D. Calvetti , Roundoff error for floating point representation of real data , Comm. Statist. Theory Methods, 20 (1991), pp. 2687–2695

    work page 1991

  8. [8]

    Comp., 56 (1991), pp

    , A stochastic roundoff error analysis for the fast Fourier tra nsform, Math. Comp., 56 (1991), pp. 755–774

    work page 1991

  9. [9]

    Comp., 59 (1992), pp

    , A stochastic roundoff error analysis for the convolution , Math. Comp., 59 (1992), pp. 569–582

    work page 1992

  10. [10]

    Chatelin and M.-C

    F. Chatelin and M.-C. Brunet , A probabilistic round-off error propagation model. Appli- cation to the eigenvalue problem , in Reliable numerical computation, Oxford Sci. Publ., Oxford Univ. Press, New York, 1990, pp. 139–160

    work page 1990

  11. [11]

    Chung and L

    F. Chung and L. Lu , Concentration inequalities and Martingale inequalities: A survey , Inter- net Math., 3 (2006), pp. 79–127

    work page 2006

  12. [12]

    Henrici, Problems of stability and error propagation in the numerica l integration of ordinary differential equations , in Proc

    P. Henrici, Problems of stability and error propagation in the numerica l integration of ordinary differential equations , in Proc. Internat. Congr. Mathematicians (Stockholm 1962 ), Inst. Mittag-Leffler, Djursholm, 1963, pp. 102–113

    work page 1962

  13. [13]

    N. J. Higham , Accuracy and Stability of Numerical Algorithms , SIAM, Philadelphia, sec- ond ed., 2002

    work page 2002

  14. [14]

    N. J. Higham and T. Mary , A new approach to probabilistic rounding error analysis , MIMS EPrint 2018.33, University of Manchester, 2018

    work page 2018

  15. [15]

    T. E. Hull and J. R. Swenson , Tests of probabilistic models for the propagation of roundo ff errors, Comm. ACM, 9 (1966), pp. 108–113

    work page 1966

  16. [16]

    Kahan , The improbability of probabilistic error analyses for nume rical computations , March 1996

    W. Kahan , The improbability of probabilistic error analyses for nume rical computations , March 1996

    work page 1996

  17. [17]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal , Probability and Computing , Cambridge University Press, Cambridge, 2005. Randomized Algorithms and Probabilistic Analysis

    work page 2005

  18. [18]

    Tienari , A statistical model of roundoff error for varying length float ing-point arithmetic , Nordisk Tidskr

    M. Tienari , A statistical model of roundoff error for varying length float ing-point arithmetic , Nordisk Tidskr. Informationsbehandling (BIT), 10 (1970), pp. 355–365

    work page 1970

  19. [19]

    von Neumann and H

    J. von Neumann and H. H. Goldstine , Numerical inverting of matrices of high order , Bull. Amer. Math. Soc., 53 (1947), pp. 1021–1099

    work page 1947

  20. [20]

    J. H. Wilkinson , Rounding errors in algebraic processes , Dover Publications, Inc., New York,

    work page

  21. [21]

    Reprint of the 1963 original [Prentice-Hall, Englewo od Cliffs, NJ]. 22

    work page 1963