Iosif Pinelis

Iosif Pinelis

Sequences of algebraic upper and lower bounds on the Wallis ratio are given with the relative errors that converge to 0 geometrically and uniformly on any interval of the form [x_0,\infty) for x_0>-\frac12; moreover, the relative and absolute errors converge to 0 as x\to\infty. These conclusions are based on corresponding results for the digamma function ψ:=\Ga'/\Ga. Relations with other relevant results are discussed, as well as the corresponding computational aspects. This work was motivated by studies of exact bounds involving the Student probability distribution.

Lun Wang, Iosif Pinelis, Dawn Song

We prove that $\mathbb{F}_p$ sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when $p\in(0, 1]$. $\mathbb{F}_p$ sketch uses only polylogarithmic space, exponentially better than existing DP baselines and only worse than the optimal non-private baseline by a logarithmic factor. The evaluation shows that $\mathbb{F}_p$ sketch can achieve reasonable accuracy with strong privacy guarantees.

Iosif Pinelis

Exact lower and upper bounds on the best possible misclassification probability for a finite number of classes are obtained in terms of the total variation norms of the differences between the sub-distributions over the classes. These bounds are compared with the exact bounds in terms of the conditional entropy obtained by Feder and Merhav.

Iosif Pinelis

The Euler--Maclaurin (EM) summation formula is used in many theoretical studies and numerical calculations. It approximates the sum $\sum_{k=0}^{n-1} f(k)$ of values of a function $f$ by a linear combination of a corresponding integral of $f$ and values of its higher-order derivatives $f^{(j)}$. An alternative (Alt) summation formula is proposed, which approximates the sum by a linear combination of integrals only, without using high-order derivatives of $f$. Explicit and rather easy to use bounds on the remainder are given. Possible extensions to multi-index summation are suggested. Applications to summing possibly divergent series are presented. It is shown that the Alt formula will in most cases outperform, or greatly outperform, the EM formula in terms of the execution time and memory use. One of the advantages of the Alt calculations is that, in contrast with the EM ones, they can be almost completely parallelized. Illustrative examples are given. In one of the examples, where an array of values of the Hurwitz generalized zeta function is computed with high accuracy, it is shown that both our implementation of the EM formula and, especially, the Alt formula perform much faster than the built-in Mathematica command HurwitzZeta[].

Aryeh Kontorovich, Iosif Pinelis

We provide an exact non-asymptotic lower bound on the minimax expected excess risk (EER) in the agnostic probably-ap\-proximately-correct (PAC) machine learning classification model and identify minimax learning algorithms as certain maximally symmetric and minimally randomized "voting" procedures. Based on this result, an exact asymptotic lower bound on the minimax EER is provided. This bound is of the simple form $c_\infty/\sqrtν$ as $ν\to\infty$, where $c_\infty=0.16997\dots$ is a universal constant, $ν=m/d$, $m$ is the size of the training sample, and $d$ is the Vapnik--Chervonenkis dimension of the hypothesis class. It is shown that the differences between these asymptotic and non-asymptotic bounds, as well as the differences between these two bounds and the maximum EER of any learning algorithms that minimize the empirical risk, are asymptotically negligible, and all these differences are due to ties in the mentioned "voting" procedures. A few easy to compute non-asymptotic lower bounds on the minimax EER are also obtained, which are shown to be close to the exact asymptotic lower bound $c_\infty/\sqrtν$ even for rather small values of the ratio $ν=m/d$. As an application of these results, we substantially improve existing lower bounds on the tail probability of the excess risk. Among the tools used are Bayes estimation and apparently new identities and inequalities for binomial distributions.