#  Risk-limiting Financial Audits
via Weighted Sampling without Replacement

Shubhanshu Shekhar  Department of Statistics and Data Science, Carnegie Mellon
University  Ziyu Xu  Department of Statistics and Data Science, Carnegie
Mellon University
Zachary C. Lipton  Machine Learning Department, Carnegie Mellon University
Tepper School of Business, Carnegie Mellon University  Pierre J. Liang  Tepper
School of Business, Carnegie Mellon University  Aaditya Ramdas  Department of
Statistics and Data Science, Carnegie Mellon University  Machine Learning
Department, Carnegie Mellon University

###### Abstract

We introduce the notion of a risk-limiting financial auditing (RLFA): given
$N$ transactions, the goal is to estimate the total misstated monetary
fraction ($m^{*}$) to a given accuracy $\epsilon$, with confidence $1-\delta$.
We do this by constructing new confidence sequences (CSs) for the weighted
average of $N$ unknown values, based on samples drawn without replacement
according to a (randomized) weighted sampling scheme. Using the idea of
importance weighting to construct test martingales, we first develop a
framework to construct CSs for arbitrary sampling strategies. Next, we develop
methods to improve the quality of CSs by incorporating side information about
the unknown values associated with each item. We show that when the side
information is sufficiently predictive, it can directly drive the sampling.
Addressing the case where the accuracy is unknown _a priori_ , we introduce a
method that incorporates side information via control variates. Crucially, our
construction is adaptive: if the side information is highly predictive of the
unknown misstated amounts, then the benefits of incorporating it are
significant; but if the side information is uncorrelated, our methods learn to
ignore it. Our methods recover state-of-the-art bounds for the special case
when the weights are equal, which has already found applications in election
auditing. The harder weighted case solves our more challenging problem of AI-
assisted financial auditing.

###### Contents

  1. 1 Introduction
    1. 1.1 Contributions
  2. 2 Betting-based CS construction
    1. 2.1 Powerful betting strategies
    2. 2.2 Logical CS
  3. 3 Sampling Strategies
  4. 4 Using possibly inaccurate side information
  5. 5 Experiments
    1. 6 Conclusion
      1. A Additional Background
        1. A.1 Related Work on Confidence Sequences (CS)
        2. A.2 Betting-based CS construction
        3. A.3 Working with minibatches
      2. B Proofs
        1. B.1 Proof of Proposition 2
        2. B.2 Proof of Proposition 3
      3. C Alternative Definitions of RLFA
      4. D Hoeffding and empirical-Bernstein Confidence sequences
        1. D.1 Hoeffding CS
        2. D.2 Empirical-Bernstein CS
      5. E Connections with Waudby-Smith and Ramdas [32, 33]
      6. F Experiments Comparing Different CS Constructions
      7. G Experiments with Housing Sales Data

##  1 Introduction

Consider the following scenario: in a given year, a company has $N$ recorded
financial transactions with reported monetary values $M(i)\in(0,\infty)$ for
each $i\in[N]\coloneqq\\{1,\dots,N\\}$. As required by law, an external
auditor is required to attest with “reasonable assurance” about whether the
financial records as a whole are free from “material misstatement.” For
example, the company has cash receipts for sales of products, and it wants to
ensure that the reported monetary value matches the true amount that was made
on the sales according to prescribed accounting rules as some receipts may
actually represent past sales or future deliveries. This can be done, for
instance, by manually examining the entire sales process to determine the true
sales amount against the the amount recorded by the company. Since the task of
_auditing_ each transaction can be complex requires substantial human labor it
can be prohibitively expensive to perform a comprehensive audit of a company’s
records.

Suppose that the auditor has built an AI system for “automated auditing”,
i.e., this AI system can output predictions about the accuracy of a
transaction value, based on receipts, OCR (optical character recognition),
databases, etc. Such systems are in a state of active development and
deployment, and the high level of industry demand is unsurprising given the
remarkable predictive capabilities of modern machine learning algorithms. But
there’s a catch: because the system is trained and deployed on differently
distributed data, its accuracy on a new set of records in a new time period is
unknown _a priori_. Even if anecdotally, the AI system seems to perform
reasonably well on data collected from a variety of companies, we cannot make
statistically certifiable conclusions based solely on the output of the AI
system on a new company and/or in a new time period. Thus we can think of AI
systems in deployment as black boxes for which we have (reasonable) hopes of
high accuracy but lack formal guarantees.

The auditor’s goal is to minimize the amount of manual auditing that must be
done by a person, while accurately estimating the true monetary amount of
those transactions that have not manually audited. When the AI system is
accurate, we want to reduce the amount of human auditing effort required. More
importantly, we want a statistically rigorous conclusion regardless of the AI
system accuracy. Hence, our method should interpolate between using
predictions to reduce its uncertainty rapidly when the system is accurate, and
the most efficient AI-free strategy when the system is inaccurate.

#### Problem setup and notation.

Denote the unknown misstated fraction of the $i$th transaction as
$f(i)\in[0,1]$, for each $i\in[N]$. In other words, if $M^{*}(i)$ denotes the
true value of the transaction $i$, and $M(i)$ is the reported value, then
111We are primarily concerned with estimating the downside that arises from
misstatement, e.g., $M(i)$ represents the money that should have been received
for a sale, and $M^{*}(i)$ represents the actual money received. In this
scenario, we may lose at most $M(i)$ amount of money if $M^{*}(i)=0$. Hence,
we assume $f(i)\in[0,1]$.  $f(i)=|M^{*}(i)-M(i)|/M(i)$. We can normalize the
reported transaction values by the sum over all transaction values to get a
weight $\pi(i)\coloneqq M(i)/(\sum_{i=1}^{N}M(i))$ for each $i\in[N]$, where
$\sum_{i=1}^{n}\pi(i)=1$. The auditor wishes to obtain an estimate of
$m^{*}=\sum_{i=1}^{N}\pi(i)f(i)$, the fraction of the total monetary value
that is misstated, up to an accuracy $\varepsilon\in[0,1]$. By $S(i)$, we
denote the _side information_ , a score for the $i$th transaction that
(ideally) predicts $f(i)$. In our setup, the side information can be generated
through any method, e.g., through an AI system that automatically analyzes the
documents a human auditor would use, may also be available to the auditor.
Each transaction can be evaluated by the auditor to reveal $M^{*}(i)$ (or
equivalently, $f(i)$). Thus, _given an $\varepsilon>0$, in what order should
the transactions be audited to estimate $m^{*}$ within $\varepsilon$ additive
accuracy, using the fewest number of calls to the auditor?_

If we allow for no uncertainty, i.e., we want to produce a confidence interval
(CI) for $m^{*}$ with 100% confidence, then the best strategy is to audit the
transactions in decreasing order of their reported value, and stop when the
remaining transactions constitute smaller than an $\varepsilon$ fraction of
the total. However, we can show that if we want to provide an estimate of
$m^{*}$ that is $\varepsilon$-accurate with probability at least $1-\delta$,
for a tolerance level $\delta$ (e.g., $0.01$), there exist strategies based on
randomized sampling WoR that allow us to stop much earlier. In other words,
for each $t\in[N]$, we adaptively construct a sampling distribution $q_{t}$
over the remaining $N-t+1$ unaudited transactions, and sample $I_{t}$, the
index of the $t$th transaction to audit, according to $q_{t}$. We then obtain
$f(I_{t})$ through manual auditing, and incorporate this new information to
update our estimate of $m^{*}$. If our residual uncertainty is sufficiently
small (i.e., smaller than $\varepsilon$), we stop sampling. Otherwise, we
continue the process by drawing the next index, $I_{t+1}$, according to an
appropriately chosen distribution $q_{t+1}$.

Before presenting the technical details, we note that we use
$(X_{t})_{t\in\mathbb{I}}$ to denote a sequence of objects indexed by a set
$\mathbb{I}$, and the $t$th object is $X_{t}$. We drop the indexing subscript
if it is clear from context. For any $t\in[N]$, we use
$\mathcal{F}_{t}\coloneqq\sigma(\\{I_{i}\\}_{i\in[t]})$ to denote the sigma-
algebra over our query selections for the first $t$ queries.

#### Risk-limiting financial audit (RLFA).

Formally, a $(\varepsilon,\delta)$-risk-limiting financial audit (RFLA) is a
procedure that outputs an interval $\mathcal{C}$ where
$|\mathcal{C}|\leq\varepsilon$ and $\mathcal{C}$ contains the true misstated
fraction, $m^{*}$, with probability at least $1-\delta$. This is a natural
generalization of risk-limiting audits that are used to ensure statistically
valid election auditing [26, 27, 20] to the financial setting, where each
transaction is weighted by its reported monetary value (as opposed to uniform
weighting for all votes in the election setting). We also consider other
possible definitions of an RLFA in Appendix C. Our goal is to produce
$\mathcal{C}$ that satisfies the conditions of an RLFA with as few audits,
i.e, queries of $f$, as possible. To produce such an interval, we propose a
framework for building RLFAs by constructing confidence sequences, which we
introduce next.

#### Confidence sequences for sequential estimation.

Let $T\in[N]$ be a random stopping time, that is, a random variable for which
the event $\\{T=t\\}$ belongs to $\mathcal{F}_{t}$ for each $t\in[N]$, and let
$\mathcal{T}$ denote the universe of all such stopping times. _Confidence
sequences_ [19, 13] (CSs), or time-uniform confidence intervals, are sequences
of intervals, $(\mathcal{C}_{t})_{t\in[N]}$, that satisfy

$\displaystyle\underset{T\in\mathcal{T}}{\sup}\
\mathbb{P}\left(m^{*}\not\in\mathcal{C}_{T}\right)\leq\delta\Leftrightarrow\mathbb{P}\left(\exists
t\in[N]:m^{*}\not\in\mathcal{C}_{t}\right)\leq\delta,$ (2)

where $\delta\in(0,1)$ is a fixed error level. Ramdas et al. [22] showed the
equivalence above, i.e., that any sequence of intervals $(\mathcal{C}_{t})$
that satisfies one side of the implication will immediately satisfy the other
as well.

Using this equivalence, we can define a simple
$(\varepsilon,\delta)\text{-}\mathrm{RLFA}$ procedure: construct a CS for
$m^{*}$, denoted by $(\mathcal{C}_{t})$, and produce $\mathcal{C}_{\tau}$
where $\tau$ is the following stopping time:

$\displaystyle\tau=\tau(\varepsilon,\delta)\coloneqq\min\\{t\geq
1:|\mathcal{C}_{t}|\leq\varepsilon\\}.\ignorespaces\ignorespaces$

The width of all nontrivial CSs converges to zero as $t\to N$, and thus the
above stopping time is well-defined, and is usually smaller than $N$.

Note that the only source of randomness in this problem is the randomized
sampling strategy $(q_{t})_{t\in[N]}$, used to select transactions for manual
evaluation. Hence, $(q_{t})_{t\in[N]}$ is another design choice for us to
make. To summarize, our goal in this paper is to (i) design sampling
strategies $(q_{t})$, and (ii) develop methods of aggregating the information
so collected with any available side information, in order to construct CSs
for $m^{*}$ whose width decays rapidly to $0$.

Among existing works in literature, the recent papers by Waudby-Smith and
Ramdas [33, 32] are the most closely related to our work. In these works, the
authors considered the problem of estimating the average value of $N$ items
via WoR sampling—however, they considered only uniform sampling, and
estimating only the unweighted mean of the population. Our methods work with
any sampling scheme, and can estimate any weighted mean; we recover their
existing results in Appendix E.

#### WoR confidence intervals for a fixed sample size.

Most existing results on concentration inequalities for observations drawn via
WoR sampling focus on the fixed sample size setting, starting with Hoeffding
[11], who bounded the probability of deviation of the unweighted empirical
mean with WoR sampling in terms of the range of the observations. In
particular, Hoeffding [11] showed that for observations
$X_{I_{1}},\ldots,X_{I_{n}}\in[a,b]$ drawn uniformly WoR from $N$ values
$(X_{i})_{i\in[N]}$, we have

$\displaystyle{\mathbb{P}\left(\tfrac{\sum_{t=1}^{n}X_{I_{t}}}{n}-\tfrac{\sum_{t=1}^{N}X_{i}}{N}>\varepsilon\right)\leq\exp\left(-\tfrac{2n\varepsilon^{2}}{(b-a)^{2}}\right).}$
(3)

In WoR sampling, as the sample size $n$ approaches $N$, the total number of
items, we expect the empirical estimate to approximate the true average very
accurately. This observation, not captured by the above bound, was made formal
by Serfling [24], who showed that the $n$ in (3) can be replaced by
$\frac{n}{1-(n-1)/N}$, thus highlighting the significant improvement possible
for larger $n$ values. Ben-Hamou et al. [3] prove a Hoeffding style
concentration inequality on the unweighted sample mean to its own expectation,
which is a different estimand than the weighted population mean considered in
this paper. Finally, in the unweighted case, Bardenet and Maillard [2]
obtained variance adaptive Bernstein and empirical-Bernstein variants of
Serfling’s results, that are tighter in cases where the variance of the
observations is small. These results appear to be incomparable to those of
Waudby-Smith and Ramdas [32, 33], that have found successful application to
auditing elections [34]. In this paper, we develop techniques that generalize
the CS constructions of Waudby-Smith et al. [34], Waudby-Smith and Ramdas [32]
in order to estimate the weighted average of $N$ quantities (instead of
simple, unweighted average) sampled via an adaptive scheme (instead of
uniform), motivated by financial auditing applications.

###  1.1 Contributions

We introduce the concept of $(\varepsilon,\delta)\text{-}\mathrm{RLFA}$ that
generalizes the notion of a risk-limiting audit introduced by Stark [26] for
election auditing. Unlike risk-limiting audits, where the main concern is
testing an announced result, the objective of an RLFA is to precisely estimate
the misstated monetary fraction of the reported financial transactions. To
accomplish this, we make the following key technical contributions:

  1. 1.

_New CSs for weighted means with non-uniform sampling._ To design an
$(\varepsilon,\delta)\text{-}\mathrm{RLFA}$ procedure, we construct novel CSs
for $m^{*}$ that are based on a betting method that was pioneered in [33] in
Section 4, as well as Hoeffding and empirical-Bernstein CSs in Appendix D
(which are looser but have a simple analytical form). Our results generalize
previous methods in two ways: (i) they can estimate the weighted mean of $N$
items, and (ii) they work with adaptive, data-dependent, sampling strategies.
In particular, our betting CSs, which we show empirically are the most
powerful in Appendix F) are based on simultaneously playing gambling games
with an aim to disprove the possibility that $m^{*}=m$, for each $m\in[0,1]$.
Values for $m$, where we accumulate much wealth are eliminated from the CS.
Consequently, we develop a simple, lucrative betting strategy for this setting
(ApproxKelly), which is equivalent to formulating narrower CSs.

  2. 2.

_Adaptive sampling strategies that minimize CS width._ In addition to
designing CSes that are intrinsically narrow, we are also able to change the
sampling distribution of the transactions at each time step, and develop a
sampling strategy that will minimize CS width in concert with any valid CS
construction. We propose two sampling strategies, prop-M and prop-MS, the
latter of which can incorporate approximately accurate scores
$(S(i))_{i\in[N]}$ to improve the sample efficiency of our CSs. This is
accomplished by choosing the sampling distribution, at each time step, that
maximizes the wealth accumulated by the betting strategies that underlie our
CSs. We find that this is approximately equivalent to choosing the sampling
distribution with the minimal variance, and we show that our sampling
strategies result in a noticeable improvement over uniform sampling through
simulations in Section 5.

  3. 3.

_Robust use of side information to tighten CSs._ Finally, in Section 4, we
develop a principled way of leveraging any available side information,
inspired by the idea of control variates used for variance reduction in Monte
Carlo sampling. Interestingly, our method adapts to the quality of the side
information—if $(S(i))_{i\in[N]}$ and $(f(i))_{i\in[N]}$ are highly
correlated, the resulting CSs are tighter, while in the case of uncorrelated
$(S(i))$, we simply learn to discard the side information.

##  2 Betting-based CS construction

We derive our CSs by designing sequential tests to simultaneously check the
hypotheses that $m^{*}=m$, for all $m\in[0,1]$. By the principle of _testing
by betting_ [25], this is equivalent to playing repeated gambling games aimed
at disproving the null $m^{*}=m$, for each $m\in[0,1]$. Formally, for all
$m\in[0,1]$, we construct a process $(W_{t}(m))_{t\in[N]}$ (the wealth
process), such that (i) if $m=m^{*}$, then $(W_{t}(m))$ is a _test martingale_
, i.e., a nonnegative martingale with initial value $1$, and (ii) if $m\neq
m^{*}$, then $W_{t}(m)$ grows at an exponential rate. Recall that a process
$(W_{t})_{t\in[N]}$ adapted to $(\mathcal{F}_{t})_{t\in[N]}$ is a
supermartingale iff $\mathbb{E}[W_{t}\mid\mathcal{F}_{t-1}]\leq W_{t-1}$ for
all $t\in[N]$, and a martingale if the inequality is replaced with an
equality. Assuming we can construct such a process, we define the confidence
set at any time $t$ as the set of those $m\in[0,1]$ for which $(W_{t}(m))$ is
‘small’, because a nonnegative martingale is unlikely to take large values.

As mentioned earlier, this approach requires us to design sampling
distributions $(q_{t})$, and a method for constructing a CS
$(\mathcal{C}_{t})$ from the queried indices. We begin by formally defining a
sampling strategy.

######  Definition 1 (Sampling Strategy).

A sampling strategy consists of a sequence $(q_{t})_{t\in[N]}$, where $q_{t}$
is a probability distribution on the set
$\mathcal{N}_{t}\coloneqq[N]\setminus\\{I_{1},\ldots,I_{t-1}\\}$. Here $I_{j}$
denotes the index drawn according to the predictable (i.e.,
$\mathcal{F}_{j-1}$-measurable) distribution $q_{j}$.

A natural baseline sampling strategy is to set $q_{t}$ to be uniform over
$\mathcal{N}_{t}$ for all $t\in[N]$. We will develop other, more powerful,
sampling strategies that are more suited to our problem in Section 3.

We now describe how to construct the wealth process for an arbitrary sampling
strategy. First, define the following:

$\displaystyle Z_{t}\coloneqq f(I_{t})\tfrac{\pi(I_{t})}{q_{t}(I_{t})},\text{
and }\mu_{t}(m)\coloneqq m-\sum_{j=1}^{t-1}\pi(I_{j})f(I_{j}).$ (4)

Note that $\mu_{t}(m)$ is the remaining misstated fraction after accounting
for the first $t-1$ queries to $f$ if $m$ is truly the total misstated
fraction. Now, we can define the _wealth process_ :

$\displaystyle
W_{t}(m)=W_{t-1}(m)\times\left(1+\lambda_{t}(m)\left(Z_{t}-\mu_{t}(m)\right)\right),$
(5)

with $W_{0}=1$. $(\lambda_{t}(m))_{t\in[N]}$ is a predictable sequence with
values in $[0,1/u_{t}(m)]$, and $u_{t}(m)$ is the largest value in the support
of $Z_{t}-\mu_{t}(m)$, for each $t\in[N]$. Note that this constraint on
$(\lambda_{t}(m))$ ensures that $W_{t}(m)$ is nonnegative for each $t\in[N]$.
We also let $W_{0}(m)=1$ for all $m\in[0,1]$. If we view the wealth process as
the wealth we earn from gambling on the outcome of $Z_{t}-\mu_{t}(m)$, then
$(\lambda_{t}(m))$ represents a betting strategy, i.e., how much money to
gamble each turn. Hence, we refer to $(\lambda_{t}(m))$ as a _betting
strategy_.

It is easy to verify that $(W_{t}(m^{*}))$ is a nonnegative martingale for any
sampling strategy $(q_{t})$ and betting strategy $(\lambda_{t}(m^{*}))$).
Hence, it is unlikely to take large values, as we describe next.

######  Proposition 1.

For any sampling and betting strategies $(q_{t})$ and $(\lambda_{t}(m^{*}))$,
the following holds:

$\displaystyle\mathbb{P}\left(\exists t\geq 1:W_{t}(m^{*})\geq
1/\delta\right)\leq\delta.$ (6)

This is a consequence of Ville’s inequality, first obtained by Ville [29],
which is a time-uniform version of Markov’s inequality for nonnegative
supermartingales. This result immediately implies that for any sampling
strategy, and any betting strategy, the term $m^{*}$ must lie in the set

$\displaystyle\mathcal{C}_{t}=\\{m:W_{t}(m)<1/\delta\\}$ (7)

with probability at least $1-\delta$, making $(\mathcal{C}_{t})$ a
$(1-\delta)$-CS.

######  Theorem 1.

$(\mathcal{C}_{t})$ is an $(1-\delta)$-CS, where $\mathcal{C}_{t}$ defined by
(7). Hence, a procedure that outputs $\mathcal{C}_{\tau}$ is an
$(\varepsilon,\delta)\text{-}\mathrm{RLFA}$, for any sampling strategy
$(q_{t})$ and betting strategies $(\lambda_{t}(m))$ for each $m\in[0,1]$.
Recall that the $\tau$ is defined in (LABEL:eq:TauDef) as the first time where
$|\mathcal{C}_{t}|\leq\varepsilon$.

This methodology gives us flexible framework for constructing different
$(\mathcal{C}_{t})$ that result in different RLFAs. Now, we can turn our
attention to finding betting strategies $(\lambda_{t}(m))$ that reduces the CS
width quickly and minimizes $\tau$.

######  Remark 1.

Note that the set $\mathcal{C}_{t}$ in (7), does not admit a closed form
expression, and is computed numerically in practice by choosing $m$ values
over a sufficiently fine grid on $[0,1]$. In Appendix D, we design CSs based
on nonnegative supermartingales (instead of martingales) that do admit closed
form representation. However, this analytical tractability comes as the price
of empirical performance, as we demonstrate in Appendix F.

######  Remark 2.

Ville’s inequality (Fact 1 in Section A.2), used for proving Proposition 1, is
known to be tight for continuous-time nonnegative martingales with infinite
quadratic variation, and incurs a slight looseness as we move to the case of
discrete time martingales. As a result, the martingale-based CSs constructed
in this section provide nearly tight coverage guarantees, that are strictly
better than the supermartingale based closed-form CSs discussed in Appendix D.
This near-tightness of the error probability of our betting-based CSs implies
that there exists no other CS that is uniformly tighter than ours, while also
controlling the error probability below $\alpha$. In other words, our CSs
satisfy a notion of admissibility or Pareto-optimality.

###  2.1 Powerful betting strategies

Besides validity, we also want the size of the CS to shrink rapidly. This
depends on how quickly the values of $W_{t}(m)$ for $m\neq m^{*}$ grow with
$t$. One such criterion is to consider the _growth rate_ , i.e., the expected
logarithm of the outcome of each bet. We can define the _one-step growth rate_
$D_{n}$, for each $n\in[N]$ as follows:

$\displaystyle D_{n}(m,\lambda)$
$\displaystyle\coloneqq\log(1+\lambda(Z_{t}-\mu_{t}(m))).$ (8)

We are interested in maximizing the expected logarithm of the wealth process
[10, 25], since it is equivalent to minimizing the expected time for a wealth
process to exceed a fixed threshold (asymptotically, as the threshold grows
larger) [6]. Thus, in the context of the auditing problem, maximizing
$\mathbb{E}[D_{t}(\lambda,m)\mid\mathcal{F}_{t-1}]$, approximately minimizes
$\mathbb{E}[\tau]$. The one-step growth rate is a broadly studied objective
known as the “Kelly criterion” [18]. In general, finding the best sequence of
bets $\lambda_{t}(m)$ for different values of $n$ is non-tractable. Instead we
consider the approximation $\log(1+x)\geq x-x^{2}$ for $|x|\leq 1/2$, and
define the best constant bet $\lambda^{*}_{n}$ in hindsight, as

$\displaystyle B_{t}(m,\lambda)$
$\displaystyle\coloneqq\lambda\left(Z_{t}-\mu_{t}(m)\right)-\lambda^{2}\left(Z_{t}-\mu_{t}(m)\right)^{2},$
(9) $\displaystyle\lambda^{*}_{n}$
$\displaystyle\coloneqq\underset{\lambda\in[\pm 1/2c]}{\text{argmax}}\
\frac{1}{n}\sum_{t=1}^{n}B_{t}(m,\lambda),$ (10)

where $c=\max\\{|Z_{t}-\mu_{t}(m)|:t\in[n]\\}$. We get the following result on
$\lambda^{*}_{n}$ for each $n\in[N]$:

$\displaystyle\lambda^{*}_{n}\propto\frac{\sum_{t=1}^{n}Z_{t}-\mu_{t}(m)}{\sum_{t=1}^{n}(Z_{t}-\mu_{t}(m))^{2}}\coloneqq\frac{A_{n}}{V_{n}}.$

Since $\lambda^{*}_{n}$ depends on the $n$th sample itself, $Z_{n}$, we cannot
use this strategy in our CS construction. Instead, at any $n\in[N]$, we can
use a predictable approximation of this strategy, that we shall refer to as
the ApproxKelly betting strategy. This strategy sets $\lambda_{t}(m)$ as
follows:

$\displaystyle\lambda_{t}(m)=c_{t}\frac{A_{t-1}}{V_{t-1}},$ (ApproxKelly)

where the (predictable) factor $c_{t}$ is selected to ensure that
$\lambda_{t}(m)\times\left(Z_{t}-\mu_{t}(m)\right)\in(-1,\infty)$, i.e., to
satisfy the nonnegativity constraint of $(W_{t}(m))$.

######  Remark 3.

We note there exist several other betting schemes in literature besides
ApproxKelly, such as those based on alternative approximations of $\log(1+x)$
[9, 33, 23], or the ONS strategy that relies on the exp-concavity of the
$\log$-loss [7]. In practice, however, we did not observe significant
difference in their performance, and we focus on the ApproxKelly strategy in
this paper due to its conceptual simplicity.

###  2.2 Logical CS

Irrespective of the choice of the sampling and betting strategies, we can
construct a CS that contains $m^{*}$ with probability 1, based on purely
logical considerations. After sampling $t$ transactions, we know that $m^{*}$
is lower bounded by quantities derived from the the misstatement fraction
accumulated in the items we have sampled already. Hence, we can derive the
following deterministic bounds:

$\displaystyle L_{l}(t)\coloneqq\sum_{j=1}^{t}\pi(I_{j})f(I_{j})\leq
m^{*},\quad\text{and}\quad U_{l}(t)\coloneqq
L_{l}(t)+\sum_{i\in\mathcal{U}_{t}}\pi(i)\geq m^{*}.$ (11)

Note that $L_{l}(t)$ (resp. $U_{l}(t)$) values are obtained by noting that all
the remaining unknown $f$ values must be larger than $0$ (resp. smaller than
$1$). Additionally, due to the time-uniform nature of confidence sequences,we
can intersect the logical CS with a ‘probabilistic’ CS constructed in (7), and
obtain the following CS:

$\displaystyle\widetilde{\mathcal{C}}_{t}\coloneqq\mathcal{C}_{t}\cap[L_{\ell}(t),U_{\ell}(t)]\cap\widetilde{\mathcal{C}}_{t-1},$
(12)

where $\widetilde{C}_{0}\coloneqq[0,1]$. Note that we may take the running
intersection of a CS since it remains a CS, simply by definition.
Consequently, the combined CS in (12) dominates the probabilistic CS.

##  3 Sampling Strategies

The choice of the sampling strategy, $(q_{t})$, is also critical to reducing
uncertainty about $m^{*}$ quickly. Recall that $q_{t}$ is a probability
distribution on the remaining indices $\mathcal{N}_{t}$ for each $t\in[N]$. To
motivate the choice of our sampling strategy, we first consider the following
question: _what is the randomized sampling strategy that leads to the fastest
reduction in uncertainty about $m^{*}$?_

In general, it is difficult to characterize this strategy in closed form
(other than the computational aspect of the strategy being the solution of a
multistage optimization problem). Thus, we consider a simplified question,
that of finding the sampling strategy that maximizes the expectation of the
one-step growth rate, $D_{n}(\lambda,m)$, for each $n\in[N]$. We seek to
maximize the lower bound, $B_{n}(\lambda,m)$, introduced in (9):

$\displaystyle
q_{n}^{*}\coloneqq\underset{q\in\Delta^{\mathcal{N}_{n}}}{\text{argmax}}\
\mathbb{E}_{I_{n}\sim q}\left[B_{n}(\lambda,m)\right],$ (13)

where $\Delta^{\mathcal{N}_{n}}$ is the universe of distributions supported on
$\mathcal{N}_{n}$. Our next result presents a closed-form characterization of
$q_{n}^{*}$.

######  Proposition 2.

Note that $q_{n}^{*}=\text{argmin}_{q\in\Delta^{\mathcal{N}_{n}}}\
\mathbb{V}_{I_{n}\sim q}[Z_{n}]$, which implies that
$q_{n}^{*}(i)\propto\pi(i)f(i)$. Hence, for any valid betting strategy
$(\lambda_{t})$ and sampling strategy $(q_{t})$, we have $\mathbb{E}_{I\sim
q_{t}}[B_{t}(\lambda_{t},m)]\leq\mathbb{E}_{I\sim
q^{*}_{t}}[B_{t}(\lambda_{t},m)]$.

We defer the proof to Section B.1, which proceeds by showing that maximizing
the lower bound on the one-step growth rate is equivalent to minimizing the
variance of $Z_{n}$. It turns out that $q_{n}^{*}(i)\propto\pi(i)f(i)$ is the
minimum (in fact, zero) variance sampling distribution, and thus,
$(q^{*}_{t})$ dominates any other sampling strategy w.r.t. maximizing the
expected bound on the one-step growth rate.

######  Remark 4.

The oracle strategy in Proposition 2 can be considered as a solution of an
alternative question: suppose there is an oracle who knows the true values of
$f(i)$, and needs to convince an observer that the value $m^{*}$ is within an
interval of width $\varepsilon$ with probability at least $1-\delta$. The
oracle wishes to do so by revealing as few $f(i)$ values to the observer as
possible. Clearly, any deterministic sampling strategy from the oracle will
lead to skepticism from the observer (i.e., the observer will only be
convinced once the $\pi(i)$ corresponding to the unrevealed $f(i)$ sum to
$\varepsilon$). Hence, the sampling strategy used by the oracle must be
random, and according to Proposition 2, it should draw transactions with
probability $\propto\pi(i)\times f(i)$.

#### Sampling without side information.

Since the $(f(i))$ values are unknown by definition of the problem, we cannot
use $(q_{t}^{*})$ in practice. Instead, we consider a sampling strategy that
selects a index $i\in\mathcal{N}_{t}$ in proportion to its $\pi(i)$ value — we
refer to this strategy as the prop-M strategy. This strategy is also known as
“sampling proportional to size” in auditing literature [5], and is similar to
the best deterministic strategy, which queries indices in descending order
w.r.t. $\pi(i)$.

$\displaystyle q_{t}(i)=\frac{\pi(i)}{\sum_{j\in\mathcal{N}_{t}}\pi(j)},$
(prop-M)

for each $i\in\mathcal{N}_{t}$. Sampling with prop-M minimizes the “worst
case” support range, and max value, of $Z_{t}$. This allows for the largest
possible choice of $\lambda_{t}$, i.e., our bet.

#### Using accurate side information for sampling.

Proposition 2 motivates a natural sampling strategy in situations where we
have access to side information $(S(i))$ that is known to be a high-fidelity
approximation of the true $(f(i))$ values—draw indices proportional to
$\pi(i)\times S(i)$. We will refer to this strategy as the prop-MS strategy:

$\displaystyle
q_{t}(i)=\frac{\pi(i)S(i)}{\sum_{j\in\mathcal{N}_{t}}\pi(j)S(j)}~{}.$ (prop-
MS)

Under certain relative accuracy guarantees on the side information, we can
characterize the performance achieved by the prop-MS strategy as compared to
the optimal strategy of Proposition 2, as we state next.

######  Corollary 1.

Assume that the side information, $(S(i))$, is an accurate prediction of
$(f(i))$, i.e., there exists a known parameter $a\in[0,1)$, such that

$\displaystyle S(i)/f(i)\in[1\pm a]$ (14)

for all $i\in[N]$. With the prop-MS strategy for $(q_{t})$, we can ensure
$\mathbb{E}_{I_{t}\sim q_{t}}[B_{t}(\lambda_{t},m)]\geq\mathbb{E}_{I_{t}\sim
q_{t}^{*}}[B_{t}(\lambda_{t},m)]\left(\frac{1}{1+a}\right)^{2}$, where
$(q^{*}_{t})$ is the optimal sampling strategy of Proposition 2.

In many cases, we do not have the accuracy guarantees on the side information
required by Corollary 1, and we develop an approach to properly incorporate
such side information in the next section.

##  4 Using possibly inaccurate side information

Often, we do not have a uniform guarantee on accuracy on $(S(i))$ as we
assumed in the previous section. In such cases, we cannot continue to use the
prop-MS strategy, as it requires knowledge of the range of $f(i)/S(i)$ in
order to select the betting fractions that ensure non-negativity of the
process $(W_{t}(m))$. Nevertheless, we develop new techniques in this section
that can exploit the side information without the uniform accuracy guarantees,
provided that the side information is correlated with the unknown $(f(i))$
values. In particular, the method developed in this section for incorporating
the side information is orthogonal to the choice of the sampling strategy; and
thus, it can be combined with any sampling strategy that ensures the non-
negativity of the process $(W_{t}(m))$.

Our approach is based on the idea of control variates [1, § V.2] that are used
to reduce the variance of Monte Carlo (MC) estimates of an unknown quantity,
using some correlated side information whose expected value is known. More
specifically, let $\widehat{m}$ denote an unbiased estimate of an unknown
parameter $m$, and let $\widehat{v}$ denote another (possibly correlated to
$\widehat{m}$) statistic with zero mean. Then, the new statistic,
$\widehat{m}_{\beta}=\widehat{m}+\beta\widehat{v}$ is also an unbiased
estimate of $m$, for all $\beta\in\mathbb{R}$. Furthermore, it is easy to
check that
$\mathbb{V}(\widehat{m}_{\beta})=\mathbb{V}(\widehat{m})+\beta^{2}\mathbb{V}(\widehat{v})+2\beta\mathrm{Cov}(\widehat{m},\widehat{v})$,
which implies that the variance of this new estimate is minimized at
$\beta=\beta^{*}\coloneqq-\left(\mathrm{Cov}(\widehat{m},\widehat{v})/\mathbb{V}(\widehat{v})\right)$.
Finally, note that the variance of $\widehat{m}_{\beta^{*}}$ cannot be larger
than the variance of the original estimate $\widehat{m}$, since
$\mathbb{V}(\widehat{m}_{\beta^{*}})\leq\mathbb{V}(\widehat{m}_{0})=\mathbb{V}(\widehat{m})$
by the definition of $\beta^{*}$.

Returning to our problem, given some possibly inaccurate side information
$(S(i))$, define the control variate (that is, an analog of the term
$\widehat{v}$) as

$\displaystyle U_{t}\coloneqq S(I_{t})-\mathbb{E}_{I^{\prime}\sim
q_{t}}[S(I^{\prime})],$ (15)

and let $(\beta_{t})$ denote a sequence of predictable terms taking values in
$[-1,1]$ used to weigh the effect of $(U_{t})$. Note that, similar to
$\widehat{v}$, the term $U_{t}$ has zero mean for each $t\in[N]$. We now
define the wealth process with control variates, denoted by
$(\widetilde{W}_{t}(m))$, and its corresponding CS as follows:

$\displaystyle\widetilde{W}_{t}(m)$
$\displaystyle\coloneqq\prod_{t=1}^{n}\left(1+\lambda_{t}(m)(Z_{t}+\beta_{t}U_{t}-\mu_{t}(m))\right),$
(16) $\displaystyle\mathcal{C}_{t}$
$\displaystyle=\\{m\in[0,1]:\widetilde{W}_{n}(m)<1/\alpha\\},$ (17)

where $(\lambda_{t}(m))$ is a betting strategy for each $m\in[0,1]$.

######  Theorem 2.

For any set of side information $(S(i))$, sequence $(\beta_{t})$, sampling
strategy $(q_{t})$, and betting strategies $(\lambda_{t}(m))$,
$(\mathcal{C}_{t})$ as defined in (17) is an $(1-\delta)$-CS for $m^{*}$.
Consequently, the procedure that produces $\mathcal{C}_{\tau}$ is an
$(\varepsilon,\delta)\text{-}\mathrm{RLFA}$.

The discussion above suggests that by a suitable choice of the parameters
$(\beta_{t})$, we can reduce the variance of the first term. To see why this
is desirable, recall that the optimal value of the approximate growth rate
after $n$ steps of the new wealth process satisfies the following:

$\displaystyle\begin{aligned}
\widetilde{B}_{n}(\lambda,m)\coloneqq&\lambda(Z_{t}+\beta_{t}U_{t}-\mu_{t}(m))\\\
&-\lambda^{2}(Z_{t}+\beta_{t}U_{t}-\mu_{t}(m))^{2},\end{aligned}$
$\displaystyle\max_{\lambda}\widetilde{B}_{n}(\lambda,m)\propto\frac{\sum_{t=1}^{n}Z_{t}+\beta_{t}U_{t}-\mu_{t}(m)}{\sum_{t=1}^{n}(Z_{t}+\beta_{t}U_{t}-\mu_{t}(m))^{2}}.\ignorespaces\ignorespaces$

Note that by setting $\beta_{t}=0$ for all $t\in[n]$, we recover
$\widetilde{B}_{n}(\lambda,m)=B_{n}(\lambda,m)$, i.e., the wealth lower bound
with no side information. Next, we observe that $\sum_{t=1}^{n}\beta_{t}U_{t}$
concentrates strongly around its mean ($0$).

######  Proposition 3.

For any $\delta\in(0,1)$ and sequence $(\beta_{t})$, the following statement
is simultaneously true for all $n\in[N]$ with probability at least $1-\delta$

$\displaystyle\left\lvert\frac{1}{n}\sum_{t=1}^{n}\beta_{t}U_{t}\right\rvert=\mathcal{O}\left(\sqrt{\frac{\log(\log
n/\delta)}{n}}\right).$ (18)

This result, proved in Section B.2, implies that in order to select the
parameters $(\beta_{t})$, we can focus on its effect on the second order term
in the denominator. In particular, the best value of $\beta$ for the first $n$
observations, is the one that minimizes the denominator, and can be defined as
follows:

$\displaystyle\beta^{*}_{n}$
$\displaystyle\coloneqq\underset{\beta\in[-1,1]}{\text{argmin}}\;\sum_{t=1}^{n}{(Z_{t}-\mu_{t}(m)+\beta
U_{t})^{2}}\propto-\frac{\sum_{t=1}^{n}(Z_{t}-\mu_{t}(m))U_{t}}{\sum_{t=1}^{n}U_{t}^{2}}.$
(19)

The numerator of $\beta_{n}^{*}$ varies with
$\sum_{t=1}^{n}f(I_{t})S(I_{t})$—hence, the magnitude of $\beta_{t}$ increases
with the amount of correlation between $f(i)$ and $S(i)$. Since
$\beta^{*}_{n}$ is not predictable (it is $\mathcal{F}_{n}$ instead of
$\mathcal{F}_{n-1}$ measurable), we will use the following strategy of
approximating $\beta_{n}^{*}$ at each $n\in[N]$:

$\displaystyle\beta_{n}\propto-\frac{\sum_{t=1}^{n-1}(Z_{t}-\mu_{t}(m))U_{t}}{\sum_{t=1}^{n-1}U_{t}^{2}}.$
(20)

for $n\geq 2$ and we let $\beta_{1}=0$. This provides a principled way of
incorporating side information even when the relationship between the side
information and the ground truth is unclear.

######  Remark 5.

Our work is motivated by applications where the side-information is generated
by an ML model trained on historical transaction data. In practice, ML models
are trained via empirical risk minimization, and we expect that models with
lower risk should result in side-information with higher correlation. For some
simple cases, such as least-squares linear regressors, we can obtain a precise
relation between correlation and risk: $\rho^{2}=1-MSE/S_{y}$, where $S_{y}$
is the empirical variance of the target variable $y$ used in training the
model. Characterizing this relation for more general models is left for future
work.

##  5 Experiments

We conduct simulations of our RLFA methods on a variety of scenarios for $\pi$
and $f$. For each simulation setup, we choose two positive integers
$N_{\text{lg}}$ and $N_{\text{sm}}$ such that $N_{\text{lg}}+N_{\text{sm}}=N$.
We generate the weight distribution $\pi$, consisting of $N_{\text{lg}}$
‘large’ values and $N_{\text{sm}}$ ‘small’ values. The exact range of values
taken by these terms are varied across experiments, but on an average the
ratio of ‘large’ over ‘small’ $\pi$ values lie between $10$ and $10^{3}$. We
then generate the $f$ values in one of two ways: (1) $f\propto\pi$, where
indices with where large $\pi$ values take $f$ values in $[0.4,0.5]$ and small
$\pi$ values take on $f$ values in $[0.001,0.01]$, or (2) $f\propto 1/\pi$,
where the $f$ value ranges are swapped for large and small values. The
simulations in this section focus on the different sampling strategies as well
as the efficacy of control variates — we provide additional experiments
comparing the betting CS with other types of CS in Appendix F.

& $N_{1}/N=0.8$, $\displaystyle f\propto\pi$ $N_{1}/N=0.2$, $\displaystyle
f\propto 1/\pi$

$N_{1}/N=0.8$, $\displaystyle f\propto
1/\pi$propMpropM+logicaluniformuniform+logical

Figure 1: A comparison of prop-M vs. uniform sampling distributions, and the
impact of intersecting with the logical CS (Section 2.2) on the width of the
CSs, when $\delta=0.05$. The prop-M strategy produces tighter CSs that
results, and intersecting with the logical CS further reduces the width,
particularly when few transactions are large ($N_{\text{lg}}=0.2$).

& $50$$100$$150$$200$$N_{1}/N=0.8$, $\displaystyle f\propto\pi$
$50$$100$$150$$200$$N_{1}/N=0.2$, $\displaystyle f\propto 1/\pi$
$40$$60$$80$$100$$N_{1}/N=0.8$, $\displaystyle f\propto
1/\pi$propMpropM+logicaluniformuniform+logical

Figure 2: Distribution of the number of transactions audited ($\tau$) for the
same experiments as Section 5, with $\varepsilon=0.05$. We omit the uniform
(without logical CS) CS histograms, as they are concentrated entirely at $N$

#### No side information: uniform vs. prop-M sampling.

In the first experiment, we compare the performance of the prop-M strategy
with the uniform baseline. In addition to this, we also illustrate the
significance of logical CS (introduced in Section 2.2) especially in cases
when there are a few large $\pi$ values. From the widths of the CSs plotted in
Section 5, we can see that prop-M outperforms the uniform baseline in all four
cases. The gap in performance increases when $N_{\text{lg}}$ is small since
$\pi$ deviates more significantly from the uniform weighting: it consists of a
few large weights with the rest close to $0$. On the other hand, when
$N_{\text{lg}}$ is large, the weights resemble the uniform distribution,
leading to the competitive performance of the uniform baseline. The logical
CSs are most useful in the case of small $N_{\text{lg}}$, especially with
$f\propto\pi$. This is because for small $N_{\text{lg}}$, every query to an
index with large $\pi$ value leads to a significant reduction in the
uncertainty about $m^{*}$.

Next, in Section 5, we plot the distribution of the stopping time $\tau$ for
an RLFA with $\varepsilon=\delta=0.05$, over $500$ independent trials. The
prop-M strategy leads to a significant reduction in the sample size
requirement to obtain an $\varepsilon$-accurate estimate of $m^{*}$ as
compared to the uniform baseline, both with and without the logical CS.
Furthermore, the distribution of $\tau$ with the prop-M strategy often has
less variability than the uniform strategy. Hence, prop-M has demonstrated
itself empirically to be a better sampling strategy than simply sampling
uniformly, as one would do when all the weights are equal.

#### Using prop-MS with accurate side information.

In the second experiment, we study the benefit of incorporating accurate side
information in the design of our CSs, by comparing the performance of prop-MS
strategy with that of the prop-M strategy. We generate $S$ randomly while
ensuring $S(i)/f(i)\in[1\pm a]$ (from (14)) for some $a\in(0,1)$. Thus smaller
values of $a$ imply that the scores $S(i)$ are more accurate approximations of
$f(i)$ for all $i\in[N]$.

$0$$0.5$$1$Samples Audited ($\displaystyle n$) Width of CS$N_{1}/N=0.2$,
$\displaystyle f\propto\pi$propMpropMS

$0$$0.5$$1$Samples Audited ($\displaystyle n$) $N_{1}/N=0.8$, $\displaystyle
f\propto\pi$

$0$$50$$100$$150$$200$$0$$0.5$$1$Samples Audited ($\displaystyle n$) Width of
CS$N_{1}/N=0.2$, $\displaystyle f\propto 1/\pi$

$0$$50$$100$$150$$200$$0$$0.5$$1$Samples Audited ($\displaystyle n$)
$N_{1}/N=0.8$, $\displaystyle f\propto 1/\pi$

(a) Width of CSs

$50$$100$$150$$0$$0.05$$0.1$$0.15$Stopping TimesDensity$N_{1}/N=0.2$,
$\displaystyle f\propto\pi$propMpropMS

$50$$100$$150$$0$$0.05$$0.1$$0.15$Stopping Times$N_{1}/N=0.8$, $\displaystyle
f\propto\pi$

$50$$100$$150$$0$$0.05$$0.1$$0.15$Stopping TimesDensity$N_{1}/N=0.2$,
$\displaystyle f\propto 1/\pi$

$60$$80$$100$$120$$0$$0.05$$0.1$$0.15$Stopping Times$N_{1}/N=0.8$,
$\displaystyle f\propto 1/\pi$

(b) Distribution of samples audited ($\tau$).

Figure 3: Comparison of the prop-MS vs. the prop-M strategy with accurate side
information $(S(i))$, i.e., $S(i)/f(i)\in[0.9,1.1]$ where
$\varepsilon=\delta=0.05$. We see that prop-MS outperforms prop-M in both CS
width and sample efficiency.

In Figure 3(a), we can see that the prop-MS strategy with accurate side
information dominates the prop-M strategy. This is further reflected in the
distribution of $\tau$ for an RLFA where $\varepsilon=\delta=0.05$ in Figure
3(b). Hence, in situations where we are confident in the accuracy of our side
information, we should incorporate it directly into our sampling strategy to
reduce the width of the CS.

#### Control variates from possibly inaccurate side information.

Finally, we consider the case in which we do not have prior information about
the accuracy of the side information. Thus, using the prop-MS strategy in this
scenario directly can lead to very conservative CSs (this is because in the
absence of tight guarantees on the range of the $S/f$ ratio, we will have to
use the worst case range). Instead, we compare the performance of the prop-M
strategy, with and without using control variates described in Section 4. In
this case, we set $S(i)=c\times f(i)+(1-c)\times R_{i}$ for $c\in(0,1)$, where
$(R_{i})_{i\in[N]}$ are i.i.d.random variables distributed uniformly over
$[0,1]$. The parameter $c$ controls the level of correlation between $f$ and
$S$ values, with small $c$ values indicating low correlation.

We generate the data with $N_{\text{lg}}=40$ and $N=200$. In Figure 4, we
compare the CSs and the distribution of $\tau$ for an RLFA (with
$\varepsilon=\delta=0.05$) for the prop-M strategy with and without control
variates, when the side information is generate with $c=0.9$. Due to the high
correlation, there is a significant decrease in the samples needed to reach an
accuracy of $\varepsilon$, when using control variates.

$0$$50$$100$$150$$200$$0$$0.5$$1$Width of CS$\displaystyle
f\propto\pi$propMpropM+CV

$100$$120$$140$$160$$180$$200$$0$$0.05$$0.1$Density$\displaystyle
f\propto\pi$propMpropM+CV

$0$$50$$100$$150$$200$$0$$0.5$$1$Samples Audited ($\displaystyle n$) Width of
CS$\displaystyle f\propto 1/\pi$

$80$$100$$120$$140$$160$$180$$200$$0$$0.02$$0.04$$0.06$Samples Audited
($\tau$)Density$\displaystyle f\propto 1/\pi$

Figure 4: The plots above show the width of the CSs and the distribution of
$\tau$ for the $f\propto\pi$ and the $f\propto 1/\pi$ cases, where
$N_{\text{lg}}/N=0.2$ and $c=0.9$.

Finally, in Figure 5, we study the variation in sample efficiency as the
correlation between $S$ and $f$ changes (i.e., by varying $c$). In particular,
for $9$ linearly spaced $c$ values in the range $[0.1,0.9]$, we compute the
$\tau$ for an RLFA without ($\tau_{\text{no-CV}}$) and with control variates
($\tau_{\text{CV}}$) over $250$ trials, and then plot the variation of the
mean of their ratio, $\tau_{\text{CV}}/\tau_{\text{no-CV}}$.

$0.2$$0.4$$0.6$$0.8$$0.6$$0.8$$1$Correlation between $\displaystyle S$ and
$\displaystyle f$ $\tau_{\text{CV}}/\tau_{\text{no-CV}}$$f\propto\pi$

$0.2$$0.4$$0.6$$0.8$$0.6$$0.8$$1$$1.2$Correlation between $\displaystyle S$
and $\displaystyle f$ $f\propto 1/\pi$

Figure 5: The figures plot the variation of the reduction in $\tau$ for an
RLFA with $\varepsilon=0.025,\delta=0.05$, when the CS is constructed with and
without using control variates . The x-axis denotes the parameter
$c\in[0.1.,0.9]$, and thus controls the amount of correlation between $S$ and
$f$. As the amount of correlation between $S$ and $f$ increases, the CS with
control variates decreases takes a decreasing fraction of the time it would
take the CS w/o control variates.

Figure 5 highlights the key advantage of our CS construction using control
variates — this method automatically adapts to the correlation between the
side information and the $f$ values. In cases where the side information is
highly correlated (i.e., larger $c$ values), the reduction in samples is
large; whereas when the correlation is small, our approach automatically
reduces the impact of the side information.

##  6 Conclusion

In this paper, we defined the concept of an
$(\varepsilon,\delta)\text{-}\mathrm{RLFA}$ and devised RLFA procedures from
confidence sequences (CSs) for the weighted average of $N$ terms (denoted by
$m^{*}$), using adaptive randomized sampling WoR. First, for arbitrary
randomized sampling strategies, we developed two methods of constructing CSs
for $m^{*}$ using test martingales. We then addressed the question of
effectively incorporating side information, with or without guarantees on
their accuracy, to improve the quality of the CSs constructed.

Our work opens up several interesting directions for future work. For
instance, in Proposition 2, we characterized the sampling strategy that
optimizes a lower bound on the one-step growth rate. Future work could
investigate whether we can obtain a more complete characterization of the
optimal policy, without relying on approximations like Proposition 2. Another
interesting issue, not addressed in our paper is that of considering more
general types of side information available to us. As described in Section 1,
we have assumed that we have access to $[0,1]$ valued side information that is
supposed to be a proxy for the true (and unknown) $f$ values. However, in
practical auditing problems, the side information is usually available in
terms of a collection of numeric, discrete and categorical features that are
correlated with the unknown $f$ values. Developing methods for incorporating
these more realistic forms of side information into our framework for
designing CSs is another important question for future work. Furthermore,
another type of side information is any knowledge from a prior audit. For
example, auditors may know before reviewing any data (transactions or AI-
generated side-info) that for this year, some accounts are likely to have
smaller or bigger $f$ values than other accounts because of the specific
performance incentives placed on the company managers by their supervisors or
by the market conditions.

Acknowledgements. We acknowledge Ian Waudby-Smith, Justin Whitehouse, Sang Wu,
Tom Yan, and our collaborators at PricewaterhouseCoopers for their insightful
discussions on this work. We also acknowledge PricewaterhouseCoopers for
providing financial support for this research.

## References

  * Asmussen and Glynn [2007] S. Asmussen and P. W. Glynn.  _Stochastic simulation: algorithms and analysis_ , volume 57.  Springer, 2007.
  * Bardenet and Maillard [2015] R. Bardenet and O.-A. Maillard.  Concentration inequalities for sampling without replacement.  _Bernoulli_ , 21(3):1361–1385, 2015.
  * Ben-Hamou et al. [2018] A. Ben-Hamou, Y. Peres, and J. Salez.  Weighted sampling without replacement.  _Brazilian Journal of Probability and Statistics_ , 32(3):657–669, 2018.
  * Bhatt et al. [2022] S. Bhatt, G. Fang, P. Li, and G. Samorodnitsky.  Catoni-style confidence sequences under infinite variance.  _arXiv preprint arXiv:2208.03185_ , 2022.
  * Bickel [1992] P. J. Bickel.  Inference and auditing: the stringer bound.  _International Statistical Review/Revue Internationale de Statistique_ , pages 197–209, 1992.
  * Breiman [1961] L. Breiman.  Optimal Gambling Systems for Favorable Games.  _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics_ , 4.1:65–79, 1961.
  * Cutkosky and Orabona [2018] A. Cutkosky and F. Orabona.  Black-box reductions for parameter-free online learning in Banach spaces.  In _Conference On Learning Theory_ , 2018.
  * Darling and Robbins [1967] D. A. Darling and H. Robbins.  Confidence sequences for mean, variance, and median.  _Proceedings of the National Academy of Sciences_ , 58(1):66–68, 1967.
  * Fan et al. [2015] X. Fan, I. Grama, and Q. Liu.  Exponential inequalities for martingales with applications.  _Electronic Journal of Probability_ , 20:1–22, 2015.
  * Grünwald et al. [2023 (forthcoming] P. Grünwald, R. de Heide, and W. Koolen.  Safe Testing.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 2023 (forthcoming).
  * Hoeffding [1963] W. Hoeffding.  Probability inequalities for sums of bounded random variables.  _Journal of the American Statistical Association_ , pages 13–30, 1963\.
  * Howard and Ramdas [2022] S. R. Howard and A. Ramdas.  Sequential estimation of quantiles with applications to A/B testing and best-arm identification.  _Bernoulli_ , 28(3):1704–1728, 2022.
  * Howard et al. [2021] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon.  Time-uniform, nonparametric, nonasymptotic confidence sequences.  _The Annals of Statistics_ , 49(2):1055–1080, 2021.
  * Jamieson and Nowak [2014] K. Jamieson and R. Nowak.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _2014 48th Annual Conference on Information Sciences and Systems (CISS)_ , pages 1–6. IEEE, 2014.
  * Jennison and Turnbull [1989] C. Jennison and B. W. Turnbull.  Interim analyses: the repeated confidence interval approach.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 51(3):305–334, 1989.
  * Johari et al. [2015] R. Johari, L. Pekelis, and D. J. Walsh.  Always valid inference: Bringing sequential analysis to A/B testing.  _arXiv preprint arXiv:1512.04922_ , 2015.
  * Johari et al. [2017] R. Johari, P. Koomen, L. Pekelis, and D. Walsh.  Peeking at A/B tests: Why it matters, and what to do about it.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 1517–1525, 2017.
  * Kelly [1956] J. L. Kelly.  A New Interpretation of Information Rate.  _The Bell System Technical Journal_ , page 10, 1956.
  * Lai [1976] T. L. Lai.  On confidence sequences.  _The Annals of Statistics_ , pages 265–280, 1976.
  * Lindeman and Stark [2012] M. Lindeman and P. B. Stark.  A gentle introduction to risk-limiting audits.  _IEEE Security & Privacy_, 10(5):42–49, 2012\.
  * Mineiro [2022] P. Mineiro.  A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean.  _arXiv preprint arXiv:2210.11133_ , 2022.
  * Ramdas et al. [2020] A. Ramdas, J. Ruf, M. Larsson, and W. Koolen.  Admissible anytime-valid sequential inference must rely on nonnegative martingales.  _arXiv:2009.03167_ , 2020.
  * Ryu and Bhatt [2022] J. J. Ryu and A. Bhatt.  On confidence sequences for bounded random processes via universal gambling strategies.  _arXiv:2207.12382_ , 2022.
  * Serfling [1974] R. J. Serfling.  Probability inequalities for the sum in sampling without replacement.  _The Annals of Statistics_ , pages 39–48, 1974.
  * Shafer [2021] G. Shafer.  Testing by betting: A strategy for statistical and scientific communication.  _Journal of the Royal Statistical Society: Series A (Statistics in Society)_ , 184(2):407–431, 2021.
  * Stark [2008] P. B. Stark.  Conservative statistical post-election audits.  _The Annals of Applied Statistics_ , 2(2):550–581, 2008.
  * Stark [2009] P. B. Stark.  CAST: Canvass audits by sampling and testing.  _IEEE Transactions on Information Forensics and Security_ , 4(4):708–717, 2009.
  * Thomas et al. [2015] P. Thomas, G. Theocharous, and M. Ghavamzadeh.  High-Confidence Off-Policy Evaluation.  _AAAI Conference on Artificial Intelligence_ , 2015.
  * Ville [1939] J. Ville.  Etude critique de la notion de collectif.  _Gauthier-Villars, Paris_ , 1939.
  * Wang and Ramdas [2022] H. Wang and A. Ramdas.  Catoni-style confidence sequences for heavy-tailed mean estimation.  _arXiv preprint arXiv:2202.01250_ , 2022.
  * Wang and Ramdas [2023] H. Wang and A. Ramdas.  Huber-robust confidence sequences.  In _International Conference on Artificial Intelligence and Statistics_ , pages 9662–9679. PMLR, 2023.
  * Waudby-Smith and Ramdas [2020] I. Waudby-Smith and A. Ramdas.  Confidence sequences for sampling without replacement.  _Neural Information Processing Systems_ , 2020.
  * Waudby-Smith and Ramdas [2023 (forthcoming] I. Waudby-Smith and A. Ramdas.  Estimating means of bounded random variables by betting.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 2023 (forthcoming).
  * Waudby-Smith et al. [2021] I. Waudby-Smith, P. B. Stark, and A. Ramdas.  Rilacs: Risk limiting audits via confidence sequences.  In _International Joint Conference on Electronic Voting_ , pages 124–139. Springer, 2021.
  * Waudby-Smith et al. [2022] I. Waudby-Smith, L. Wu, A. Ramdas, N. Karampatziakis, and P. Mineiro.  Anytime-valid off-policy inference for contextual bandits.  _arXiv:2210.10768_ , 2022.

## Organization

We discuss some additional background material in Appendix A, and then
formulate the proofs omitted from the body of the paper for Proposition 2 and
Proposition 3 in Appendix B. We discuss a practical auditing consideration,
where one may wish to estimate the remaining misstated fraction as opposed to
the total misstated fraction, $m^{*}$, in Appendix C. In Appendix D, we
provide Hoeffding and empirical-Bernstein style CSs that are an alternative to
the betting CSs we provide in the paper. We then use the Hoeffding CS
constructed in the aforementioned to section as an example of the fact that
previous CSs for unweighted mean estimation with uniform sampling from Waudby-
Smith and Ramdas [32, 33] can be recovered by our method for a specific choice
of $(\lambda_{t})$ in Appendix E. Empirical results from simulations are shown
for these CSs in Appendix F, in which we compare the Hoeffding and empirical-
Bernstein CSs to the betting CS discussed in the main body of the paper.
Finally, we end by presenting the results of applying our methods on a real-
world housing dataset in Appendix G.

##  Appendix A Additional Background

###  A.1 Related Work on Confidence Sequences (CS)

Confidence sequences (CSs) are a fundamental tool in sequential analysis, and
were introduced into this literature by Robbins and coauthors in a series of
papers starting with [8]. Some other important early works in this area
include [19] and [15]. More recently, there has been a resurgence of interest
in confidence sequences, particularly motivated by its applications in anytime
valid inference. In anytime valid inference, data samples are received
sequentially, and the goal is to derive statistical guarantees that are valid
even if one stops sampling and performs inference at a data-dependent time
[16, 17, 13, 12]. Thus, confidence sequences can also be employed in the
multi-armed bandit setting (where one can sample adaptively from multiple
streams of data) to enable best arm identification [14]. Most of the papers
mentioned above rely on making certain moment assumptions on the data-
generating distributions. An important line of recent work aims to relax these
assumptions, by constructing confidence sequences for heavy-tailed data or
contaminated data [30, 4, 21, 31].

###  A.2 Betting-based CS construction

The betting-based approach for constructing confidence sequences builds upon
the idea of _testing-by-betting_ , popularized recently by Shafer [25]. This
principle states that we can refute a claim (equivalently, a null hypothesis
$H_{0}$) about the probability distribution generating some data stream, if we
can increase our wealth by repeatedly betting on the observations with the
restriction that the betting payoffs are _fair_ under $H_{0}$. The restriction
of fair payoff implies that that bettor is not expected to make large gains
under $H_{0}$, irrespective of the betting strategy employed (formally, the
wealth process is a non-negative supermartingale). Consequently, if the bettor
ends up making a large profit by betting on the observations, this can be
considered as evidence against $H_{0}$; with the relative growth in wealth
provide a precise measure of the strength of evidence.

To use the above principle for constructing CSs, we simultaneously play a
continuum of betting games, indexed by $m\in[0,1]$, each with an initial
wealth of $\$1$. For every $m\in[0,1]$, we bet against the claim $H_{0,m}$
that the true misspecified fraction $m^{*}$ is equal to $m$. We design the
payoff functions of this betting game, such that the resulting wealth process,
$\\{W_{t}(m):t\geq 1\\}$, is a non-negative martingale if $H_{0,m}$ were true,
but grows at an exponential rate otherwise. Due to this property, the process
at $m^{*}$, denoted by $\\{W_{t}(m^{*}):t\geq 1\\}$, is actually a _test
martingale_ ; that is, a nonnegative martingale with an initial value $1$.
Hence, Ville’s inequality (recalled below in Fact 1) implies that with
probability at least $1-\alpha$, the process $(W_{t}(m^{*}))$ never exceeds
the value $1/\alpha$. This fact, suggests a natural definition of a CS for
$m^{*}$, consisting of sets $C_{t}=\\{m:W_{t}(m)<1/\alpha\\}$, since these
sets contain $m^{*}$ for all $t\geq 1$, with probability at least $1-\alpha$.
To conclude, the betting-based approach breaks the task of constructing
confidence sequences into two smaller tasks:

  1. 1.

Choosing a sequence of payoff functions that are fair under $H_{0,m}$: we
achieve this by using the idea of importance weighting.

  2. 2.

Developing a betting strategy that ensures fast growth of the wealth process
for all $m\neq m^{*}$: we use the ApproxKelly strategy for this in our
construction.

An additional design choice that is unique to the problem studied in this
paper, is that of the _sampling strategy_ to select the transaction indices.
We discuss several strategies in Section 3, whose performance is determined by
the availability and accuracy of side-information.

We end this discussion by recalling a statement of Ville’s inequality [29].

######  Fact 1 (Ville’s Inequality).

Suppose $\\{M_{t}:t\geq 0\\}$ denotes a nonnegative supermartingale adapted to
a filtration $\\{\mathcal{F}_{t}:t\geq 0\\}$. Then, for any $\alpha>0$, we
have

$\displaystyle\mathbb{P}\left(\exists t\geq 0:M_{t}\geq
1/\alpha\right)\leq\frac{\mathbb{E}[M_{0}]}{\alpha}.$ (21)

###  A.3 Working with minibatches

In this paper, we have developed our methodology under the assumption that the
transactions are sampled and sent to the human auditor, one at a time. In
practical scenarios, it may be preferable for the human auditor to evaluate a
minibatch of transactions a time, rather than querying the transactions one-
by-one. This generalization can be easily handled by updating the wealth
process with the averaged payoff (over the minibatch in each round). More
specifically, we can proceed as follows, for any $m\in[0,1]$, and for
$t=1,2,\ldots$:

  * •

Calculate the next sampling distribution, $q_{t}$.

  * •

Sample the next batch of transactions,
$\mathcal{B}_{t}\coloneqq\\{I_{t}^{(1)},\ldots,I_{t}^{(B)}\\}$, with
$I_{t}^{(j)}$ is drawn according to $q_{t}$ restricted on
$\mathcal{N}_{t}\setminus\\{I_{t}^{(1)},\ldots,I_{t}^{(j-1)}\\}$. Recall that,
we now have
$\mathcal{N}_{t}=[N]\setminus\left(\cup_{s=1}^{t-1}\mathcal{B}_{s}\right)$.

  * •

Obtain the true $f$ values, $\\{f(I_{t}^{(i)}:1\leq i\leq B\\}$ from the
oracle (i.e., the human auditor).

  * •

Update the wealth process:

$\displaystyle
W_{t}(m)=W_{t-1}(m)\times\left(1+\frac{1}{B}\sum_{i=1}^{B}\lambda_{t}^{(i)}\left(Z_{t}^{(i)}-\mu_{t}^{(i)}(m)\right)\right),\quad\text{for
}m\in[0,1].$ (22)

Here $\lambda_{t}^{(i)}$ denotes the bet based on
$\cup_{s=1}^{t-1}\mathcal{B}_{t}\cup\\{X_{t}^{(1)},\ldots,X_{t}^{(i-1)}\\}$,
and $Z_{t}^{(i)}-\mu_{t}^{(i)}$ denotes the analogous payoff function, as
defined in Section 2.

  * •

Update the CS, as $C_{t}=\\{m\in[0,1]:W_{t}(m)<1/\alpha\\}$.

##  Appendix B Proofs

###  B.1 Proof of Proposition 2

Recall that $\mathbb{E}_{I_{n}\sim q}[Z_{n}]=\mu_{n}(m^{*})$ for any sampling
distribution $q\in\Delta^{\mathcal{N}_{n}}$. Now, we note the following
equivalencies

$\displaystyle\mathbb{E}_{I_{n}\sim q}[B_{n}(\lambda,m)]$ (23)
$\displaystyle=\mathbb{E}_{I_{n}\sim
q}[\lambda(Z_{n}-\mu_{n}(m))-\lambda^{2}(Z_{n}-\mu_{n}(m))^{2}]$ (24)
$\displaystyle=\mathbb{E}_{I_{n}\sim
q}[\lambda(Z_{n}-\mu_{n}(m))]-\mathbb{E}_{I_{n}\sim
q}[\lambda^{2}(Z_{n}-\mu_{n}(m))^{2}]$ (25)
$\displaystyle=\lambda(m^{*}-m)-\lambda^{2}\mathbb{E}_{I_{n}\sim
q}[(Z_{n}-\mu^{*}_{n}(m)-\mu_{n}(m)+\mu^{*}_{n}(m))^{2}]$ (26)
$\displaystyle=\lambda(m^{*}-m)-\lambda^{2}(m^{*}-m)^{2}+2\lambda^{2}\mathbb{E}_{I_{n}\sim
q}[Z_{n}-\mu_{n}(m^{*})](m^{*}-m)-\lambda^{2}\mathbb{E}_{I_{n}\sim
q}[(Z_{n}-\mu^{*}_{n}(m))^{2}]$ (27)
$\displaystyle=\lambda(m^{*}-m)-\lambda^{2}(m^{*}-m)^{2}-\mathbb{V}_{I_{n}\sim
q}[Z_{n}].$ (28)

The above equivalencies show that
$q_{n}^{*}=\text{argmin}_{q\in\Delta^{\mathcal{N}_{n}}}\ \mathbb{V}_{I_{n}\sim
q}[Z_{n}]$ by definition of $q_{n}^{*}$ in (13), and since $\lambda,m^{*},m$
are fixed in the optimization problem. Consequently, the minimizer of
$\mathbb{V}_{I_{n}\sim q}[Z_{n}]$ is when the distribution of $Z_{n}$ has
support on only a single value and the variance is 0. This is achieved when
$q_{n}(i)\propto\pi(i)f(i)$ for each $i\in\mathcal{N}_{n}$. Hence, we have
shown our desired result.

###  B.2 Proof of Proposition 3

For any $t\geq 1$, introduce the random variable
$D_{t}=t\times\left(\widetilde{A}_{t}-A_{t}\right)=\sum_{i=1}^{t}\beta_{i}U_{i}$.
By construction of the term $U_{i}$, we know that for any $t\geq 1$, we have

$\displaystyle\mathbb{E}[D_{t}|\mathcal{F}_{t-1}]=\sum_{i=1}^{t-1}\beta_{i}U_{i}+\beta_{t}\mathbb{E}[D_{t}|\mathcal{F}_{t-1}]=D_{t-1}.$
(29)

Thus, $\\{D_{t}:t\geq 1\\}$ is a martingale process. Furthermore, since both
$\beta_{t}$ and $U_{t}$ lie in the set $[-1,1]$, the martingale process
$\\{D_{t}:t\geq 1\\}$ has bounded differences. Hence, by using the time-
uniform deviation inequality for martingales with bounded differences [13, Eq.
(11)], we have

$\displaystyle\mathbb{P}\left(\exists t\leq
n:|D_{t}|>1.7\sqrt{t\left(\log\log(2t)+0.72\log(10.4/\delta)\right)}\right)<\delta.$
(30)

Since $|\widetilde{A}_{t}-A_{t}|/t=|D_{t}|/t$, the result follows.

##  Appendix C Alternative Definitions of RLFA

#### Testing based $\boldsymbol{(\varepsilon,\delta)\text{-}\mathrm{RLFA}}$.

An alternative notion of RLFAs, that mirrors the corresponding definition of
risk-limiting audits [26] more closely, can be obtained by framing it as the
task of testing whether the overall misstated fraction, $m^{*}$, is “small”.
This can be interpreted as auditing the claim that all the reported monetary
values are accurate. Formally, we assume that the announced assertion is that
$m^{*}\leq\varepsilon$, and we want to design a procedure that (i) with
probability at least $(1-\delta)$, rejects this assertion if it is false, and
(ii) confirms this assertion with probability $1$ if it is true. Our general,
CS-based strategy that we developed in this paper can be easily adapted to
this problem — we simply define the stopping time
$\tau(\varepsilon,\delta)\coloneqq\min\\{t\in[N]:\mathcal{C}_{t}\subseteq(\varepsilon,1]\cup\\{N\\}$
and reject if $C_{\tau(\varepsilon,\delta)}\subseteq(\varepsilon,1]$.
Properties (i) and (ii) follow immediately from the definition of a CS, and
the consistency of a CS, i.e., $|\mathcal{C}_{t}|\rightarrow 0$ as
$t\rightarrow N$.

#### Auditing the remaining misstated fraction.

Another quantity of interest is the remaining misstated fraction, i.e., what
is the remaining misstated fraction assuming we correct the transaction values
for the transactions we have audited? In many practical auditing scenarios,
the company does correct their finances in accordance with their records for
the audited transactions, i.e., $f(I_{i})=0$ for each $i\in[t]$ after querying
the $t$th transaction. This is equivalent to estimating $\mu_{t}(m^{*})$, a
time varying quantity, instead of the static quantity of $m^{*}$. Since
$\mu_{t}(m^{*})$ is simply a shift of $m^{*}$ by a quantity that is known to
the auditor, all estimates of $m^{*}$ we produce in this work can easily be
transformed into estimates of the remaining misstated fraction as well (by
subtracting $\sum_{i\in[t]}\pi(I_{i})f(I_{i})$ from both boundaries of our
CSs). Thus, we can estimate the remaining misstated fraction as efficiently as
we estimate $m^{*}$.

##  Appendix D Hoeffding and empirical-Bernstein Confidence sequences

In this section, we present a different approach for constructing confidence
sequences, that are based on nonnegative supermartingales (NSMs), instead of
nonnegative martingales used by the betting based CS (Section 2). While these
CSs are typically looser than the betting CS defined in (7), they are
computationally inexpensive and can be derived analytically. We will introduce
two such CSs, the Hoeffding CS and empirical-Bernstein CS, and each will have
boundaries that take on an explicit form. Thus, only constant time is needed
to compute the boundaries for each new sample. In contrast, the betting CS
computes its boundaries through a root finding procedure which requires $O(t)$
computations to derive updated boundaries after receiving the $t$th sample. We
provide simulations comparing the Hoeffding and empirical-Bernstein CSs with
the betting CS in Appendix F. Before defining our CSs, we first introduce the
following quantities:

$\displaystyle\widehat{m}_{t}\coloneqq\frac{\pi(I_{t})}{q_{t}(I_{t})}f(I_{t})+\sum\limits_{i=1}^{t-1}\pi(I_{i})f(I_{i}),\quad\widehat{\mu}_{t}\coloneqq\frac{\sum\limits_{i=1}^{t}\widehat{m}_{i}}{t},\qquad\widehat{\mu}_{t}(\lambda_{1}^{t})\coloneqq\frac{\sum\limits_{i=1}^{t}\lambda_{i}\widehat{m}_{i}}{\sum\limits_{i=1}^{t}\lambda_{i}}.$
(31)

Note that $\widehat{\mu}_{t}(\lambda_{1}^{t})$ where
$\lambda_{1}=\ldots=\lambda_{t}=1$ is equivalent to $\widehat{\mu}_{t}$.

###  D.1 Hoeffding CS

To define the Hoeffding CS, we first define the nonnegative supermartingale
(NSM) associated with it. As noted in prior work [13, 33], let the following
be a CGF-like function for Hoeffding:

$\displaystyle\psi_{\mathrm{H}}^{c}(\lambda)\coloneqq\frac{\lambda^{2}c^{2}}{8},$
(32)

for any fixed $c>0$. Now we define the following Hoeffding NSM as follows:

$\displaystyle M_{t}^{\mathrm{H}}(m)$
$\displaystyle\coloneqq\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}(Z_{i}-\mu_{i}(m))-\psi_{\mathrm{H}}^{c_{i}}(\lambda_{i})\right)=\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}(\widehat{m}_{i}-m)-\psi_{\mathrm{H}}^{c_{i}}(\lambda_{i})\right),$
(33)

where $c_{t}\geq\max_{i\in\mathcal{U}_{t}}\pi(i)/q_{t}(i)$, and both
$(\lambda_{t})$ and $(c_{t})$ are predictable w.r.t. $(\mathcal{F}_{t})$.

######  Proposition 4.

$(M_{t}^{\mathrm{H}}(m^{*}))_{t\in[N]}$ is an NSM.

###### Proof.

First, note that $\mathbb{E}[Z_{t}\mid\mathcal{F}_{t-1}]=\mu_{t}(m)$ since we
are assuming the null $H_{0,m}$ is true. Second, note that
$Z_{t}\in[0,\max_{i\in\mathcal{U}_{t}}\pi(i)/q_{t}(i)]$ is bounded. Thus, the
desired statement follows directly from the MGF bound on bounded random
variables i.e. if $X\in[\ell,u]$ is a random variable, then
$\mathbb{E}[\exp(\lambda(X-\mathbb{E}[X]))]\leq\exp(\lambda^{2}(u-\ell)^{2}/8)$
for any $\lambda\in\mathbb{R}$. ∎

Consequently, we can derive the following Hoeffding CS:

$\displaystyle
C^{\mathrm{H}}_{t}\coloneqq\left(\widehat{\mu}_{t}(\lambda_{1}^{t})\pm\frac{\log(2/\alpha)+\sum\limits_{i=1}^{t}\psi_{\mathrm{H}}^{c_{i}}(\lambda_{i})}{\sum\limits_{i=1}^{t}\lambda_{i}}\right)\cap[0,1],$
(34)

where $c_{t}\geq\max_{i\in\mathcal{U}_{t}}\pi(i)/q_{t}(i)$, and both
$(\lambda_{t})$ and $(c_{t})$ are predictable w.r.t. $(\mathcal{F}_{t})$.

###  D.2 Empirical-Bernstein CS

Define the following CGF-like function for empirical-Bernstein:

$\displaystyle\psi_{\mathrm{E}}^{c}\coloneqq\frac{-\log(1-c\lambda)-c\lambda}{c^{2}},$
(35)

for any $c>0$. Now we define the following empirical-Bernstein NSM:

$\displaystyle M_{t}^{\mathrm{EB}}(m)$
$\displaystyle\coloneqq\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}(Z_{i}-\mu_{i}(m))-(Z_{i}-\widehat{\mu}_{i-1})^{2}\psi_{\mathrm{E}}^{c_{i}}(\lambda_{i})\right)$
(36)
$\displaystyle=\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}(\widehat{m}_{t}-m)-(Z_{i}-\widehat{\mu}_{i-1})^{2}\psi_{\mathrm{E}}^{c_{i}}(\lambda_{i})\right),$
(37)

where $\lambda_{t}\in[0,1/c_{t})$, $c_{t}\geq\widehat{\mu}_{t-1}$, and both
$(\lambda_{t})$ and $(c_{t})$ are predictable w.r.t. $(\mathcal{F}_{t})$.

#### Constructing the upper CS through mirroring.

$M_{t}^{\mathrm{EB}}$ can be used to construct a CS that lower bounds $m^{*}$,
but naively constructing an analog NSM (i.e., by negating $Z_{t}-\mu_{t}(m)$
into $\mu_{t}(m)-Z_{t}$) results in a loose construction for the upper CS,
since $c_{t}$ would need to lower bound $\widehat{\mu}_{t-1}-Z_{t}$. $Z_{t}$
(and hence $c_{t}$) be quite large depending on the sampling probabilities
$q_{t}$. Thus, we use the fact that $m^{*}\in[0,1]$ and hence
$1-m^{*}\in[0,1]$ to construct a “mirroring” lower CS for
$1-m^{*}=\sum_{i=1}^{N}\pi(i)(1-f(i))$. The lower CS for $1-m^{*}$ is based
upon the following NSM:

$\displaystyle{M^{\prime}}_{t}^{\mathrm{EB}}(m)$
$\displaystyle\coloneqq\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}\left(\widetilde{Z}_{i}-\left(1-m+\sum\limits_{j=1}^{i-1}\pi(I_{j})(1-f(I_{j}))\right)-(\widetilde{Z}_{i}-\widetilde{\mu}_{i-1})^{2}\psi_{\mathrm{E}}^{c_{i}}(\lambda_{i})\right)\right)$
(38)
$\displaystyle=\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}(\widetilde{m}_{t}-(1-m))-(\widetilde{Z}_{i}-\widetilde{\mu}_{i-1})^{2}\psi_{\mathrm{E}}^{c_{i}}(\lambda_{i})\right).$
(39)

Here, define
$\widetilde{Z}_{t}\coloneqq\frac{\pi(I_{t})}{q_{t}(I_{t})}(1-f(I_{t}))$, and
let $\widetilde{m}_{t}$, and $\widetilde{\mu}_{t}$ be counterparts of
$\widehat{m}_{t}$ and $\widehat{\mu}_{t}$ where $f(i)$ is replaced with
$1-f(i)$ in the respective definitions for each $i\in[N]$.

######  Proposition 5.

$(M_{t}^{\mathrm{EB}}(m^{*}))_{t\in[N]}$ and
$({M_{t}^{\prime}}^{\mathrm{EB}}(m^{*}))_{t\in[N]}$ are both NSMs.

To prove Proposition 5, we introduce the following key lemma from Fan et al.
[9].

######  Lemma 1 (Fan et al. 9, Lemma 4.1).

Let $\xi$ be a number bounded from below i.e. satisfies $\xi\geq-c$, where
$c\in\mathbb{R}^{+}$ is a fixed constant. Let the following be true:
$\lambda\in[0,1/c)$. Then,

$\displaystyle
1+\lambda\xi\geq\exp(\lambda\xi+\xi^{2}(\log(1-c\lambda)+c\lambda)).$ (40)

###### Proof.

The proof revolves around the following function $h$:

$\displaystyle h(x)\coloneqq\frac{\log(1+x)-x}{x^{2}/2},\qquad x>-1.$ (41)

Note that $f$ is increasing in its domain. Then, $\lambda\xi\geq-c\lambda>-1$
by definition of $\lambda$ and $\xi$. Thus,

$\displaystyle h(\lambda\xi)$ $\displaystyle\geq
h(-c\lambda)\Leftrightarrow\frac{\log(1+\lambda\xi)-\lambda\xi}{\xi^{2}}\geq\frac{\log(1-c\lambda)+c\lambda}{c^{2}}.$
(42)

The desired statement follows from expanding this inequality and rearranging
terms. ∎

###### Proof of Proposition 5.

We will only show the proof that $(M^{\mathrm{EB}}_{t}(m^{*}))$ is an NSM,
since the proof that $({M^{\prime}}_{t}^{\mathrm{EB}}(m^{*}))$ is an NSM will
follow a similar derivation. Let $Y_{t}=Z_{i}-\mu_{i}(m)$ and
$\delta_{t}=\widehat{\mu}_{t-1}-\mu_{i}(m)$. Note that
$Y_{t}-\delta_{t}=Z_{t}-\widehat{\mu}_{t-1}$. To prove our desired statement,
it suffices to show the following is true:

$\displaystyle\mathbb{E}\left[\exp(\lambda_{t}Y_{t}-(Y_{t}-\widehat{\mu}_{t-1})^{2}\psi_{\mathrm{E}}^{\widehat{\mu}_{t-1}})\mid\mathcal{F}_{t-1}\right]\leq
1.$ (43)

We will now show that (43) is indeed true:

$\displaystyle\mathbb{E}\left[\exp(\lambda_{t}Y_{t}-(Y_{t}-\delta_{t})^{2}\psi_{\mathrm{E}}^{\widehat{\mu}_{t-1}})\mid\mathcal{F}_{t-1}\right]$
$\displaystyle=\mathbb{E}\left[\exp(\lambda_{t}(Y_{t}-\delta_{t})-(Y_{t}-\delta_{t})^{2}\psi_{\mathrm{E}}^{\widehat{\mu}_{t-1}})\mid\mathcal{F}_{t-1}\right]\exp(\lambda_{t}\delta_{t})$
(44)
$\displaystyle\leq\mathbb{E}\left[1+\lambda_{t}(Y_{t}-\delta_{t})\mid\mathcal{F}_{t-1}\right]\exp(\lambda_{t}\delta_{t})$
(45)
$\displaystyle=\mathbb{E}\left[1-\lambda_{t}\delta_{t}\mid\mathcal{F}_{t-1}\right]\exp(\lambda_{t}\delta_{t})\leq
1.$ (46)

The 1st inequality is by application of Lemma 1 with
$\xi_{t}=Y_{t}-\delta_{t}$ and $c=\widehat{\mu}_{t-1}$ ($Z_{t}\geq 0$, so
$\xi_{t}\geq-\widehat{\mu}_{t-1}$). The 2nd equality is the result of
$\mathbb{E}[Y_{t}\mid\mathcal{F}_{t-1}]=(m^{*}-m^{*}_{t})-(m^{*}-m^{*}_{t})=0$.
The last inequality is by $1-x\leq\exp(-x)$ for all $x\in\mathbb{R}$. Thus, we
have proved (43) and our desired statement as a result. ∎

As a result, we can construct the following empirical-Bernstein CS:

$\displaystyle C_{t}^{\mathrm{EB}}\coloneqq$
$\displaystyle\left(\widehat{\mu}({\lambda^{\prime}}_{1}^{t})-\frac{\log(2/\alpha)+\sum\limits_{i=1}^{t}(Z_{i}-\widehat{\mu}_{i-1})^{2}\psi_{E}^{c}(\lambda_{i}^{\prime})}{\sum\limits_{i=1}^{t}\lambda_{i}^{\prime}},1-\widetilde{\mu}_{t}({\lambda}_{1}^{t})+\frac{\log(2/\alpha)+\sum\limits_{i=1}^{t}(\widetilde{Z}_{t}-\widetilde{\mu}_{t-1})^{2}\psi_{E}^{c}(\lambda_{i})}{\sum\limits_{i=1}^{t}\lambda_{i}}\right)\cap[0,1].$
(47)

The mirroring trick of constructing a lower CS for $1-m^{*}$ was originally
employed to construct confidence bounds for off policy evaluation in
contextual bandits [28, 35]. To the best of our knowledge, this is the first
use of the mirroring trick simply for mean estimation.

For both the Hoeffding and empirical-Bernstein CSs, we show in Appendix E that
we are able to recover the unweighted, uniform sampling versions introduced by
Waudby-Smith and Ramdas [32] as a special case, i.e., when $q_{t}$ is the
uniform distribution over the remaining items and $\pi$ is uniform over all
items. Thus, our formulations of the Hoeffding and empirical-Bernstein CSs
generalize the CSs for sampling without replacement in [32] to weighted
sampling and estimation.

##  Appendix E Connections with Waudby-Smith and Ramdas [32, 33]

CSs for estimation of the unweighted mean through uniform sampling without
replacement are shown in Waudby-Smith and Ramdas [32] for Hoeffding and
empirical-Bernstein style CSs, and Waudby-Smith and Ramdas [33] for betting
style CSs. In this section, we show these results are a special case of our
results that also account for non-uniform sampling strategies and weighted
means. For simplicity, we will show the Hoeffding case, and the results for
the other CSs follow a similar argument. Following the notation of Waudby-
Smith and Ramdas [32], let $(X(i))_{i\in[N]}$ be a finite population of values
in $[0,1]$ (without loss of generality to arbitrary bounds on the $X(i)$). Let
$X_{1},\dots,X_{N}$ be random variables that are the the result of from
sampling uniformly w/o replacement from this population. Waudby-Smith and
Ramdas [32] construct the following NSM for
$\mu\coloneqq\tfrac{1}{N}\sum\limits_{i=1}^{N}X(i)$:

$\displaystyle
M_{t}^{\mathrm{WS}\text{-}\mathrm{R}}(m)\coloneqq\exp\left(\sum\limits_{i=1}^{t}\lambda_{i}\left(X_{i}-m+\frac{1}{N-i+1}\sum\limits_{j=1}^{i-1}(X_{j}-m)\right)-\psi_{H}(\lambda_{i})\right),$
(48)

and derive the CS

$\displaystyle
C_{t}^{\mathrm{WS}\text{-}\mathrm{R}}\coloneqq\left(\widehat{\mu}_{t}^{\mathrm{WS}\text{-}\mathrm{R}}(\lambda_{1}^{t})\pm\frac{\log(2/\alpha)+\sum\limits_{i=1}^{t}\psi_{H}(\lambda_{i})}{\sum\limits_{i=1}^{t}\lambda_{i}\left(1+\frac{i-1}{N-i+1}\right)}\right).$
(49)

The center of this CS is defined as

$\displaystyle\widehat{\mu}_{t}^{\mathrm{WS}\text{-}\mathrm{R}}(\lambda_{1}^{t})\coloneqq\frac{\sum\limits_{i=1}^{t}\lambda_{i}\left(X_{i}+\frac{1}{N-i+1}\sum\limits_{j=1}^{i-1}X_{j}\right)}{\sum\limits_{i=1}^{t}\lambda_{i}(1+\frac{i-1}{N-i+1})}=\frac{\sum\limits_{i=1}^{t}\lambda_{i}\left(X_{i}+\frac{1}{N-i+1}\sum\limits_{j=1}^{i-1}X_{j}\right)}{\sum\limits_{i=1}^{t}\lambda_{i}\cdot\frac{N}{N-i+1}}.$
(50)

In the weighted setting, $\pi(i)=1/N$ and $f(i)=X(i)$ for each $i\in[N]$
implies that we are estimating the uniformly weighted average $m^{*}=\mu$. For
each $t\in[N]$ and $i\in\mathcal{N}_{t}$, set $q_{t}(i)=1/(N-t+1)$ to be the
uniform distribution over the remaining items. This gets us the following
estimate of the mean from our Hoeffding CS:

$\displaystyle\widehat{\mu}_{t}({\lambda_{1}^{\prime}}^{t})=\frac{\sum\limits_{i=1}^{t}\lambda_{i}^{\prime}\left(\frac{N-i+1}{N}X_{i}+\frac{1}{N}\sum\limits_{j=1}^{i-1}X_{j}\right)}{\sum\limits_{i=1}^{t}\lambda_{i}^{\prime}}.$
(51)

By setting $\lambda^{\prime}_{i}=\lambda_{i}N/(N-i+1)$, for each $i\in[t]$, we
get that
$\widehat{\mu}_{t}({\lambda^{\prime}}_{1}^{t})=\widehat{\mu}^{\mathrm{WS}\text{-}\mathrm{R}}_{t}(\lambda_{1}^{t})$.
To see that $C_{t}^{H}=C_{t}^{\mathrm{WS}\text{-}\mathrm{R}}$, we set
$c_{t}=(N-t+1)/N$ for each $t\in[N]$. Note that that is minimum possible value
that $c_{t}$ can be since $\pi(i)=1/N$ for each $i\in[N]$, and
$q_{t}(i)=1/(N-t+1)$ for each $i\in\mathcal{N}_{t}$. As a result, we are able
to recover the Hoeffding CS from [32] as a special case of our Hoeffding CS.

##  Appendix F Experiments Comparing Different CS Constructions

In Figure 6, we compare the width of the Hoeffding, empirical-Bernstein, and
betting CSs under the prop-M sampling strategy, i.e., under a weighted
sampling strategy. We follow the same setup as Experiment 1 in Section 5. We
see that the empirical-Bernstein CS is tighter in cases where $N_{\text{lg}}$
is larger. In these cases, the support size, $c_{t}$, is large for
$N_{\text{lg}}$ transactions, with makes the Hoeffding CS looser as a result.
On the other hand, empirical-Bernstein is able to take advantage of the low-
variance from a large number of transactions having similar misstated
fractions $f(I_{t})$. However, when $N_{\text{lg}}$ is small, most
transactions will have a small support size, $c_{t}$, and the Hoeffding CS
will be tighter than empirical-Bernstein as a result. The betting CS is
tighter than both Hoeffding and empirical-Bernstein CSs in all our simulated
setups. This trend is reflected in Figure 7 where we plot the histogram of the
first time the CS reaches $\varepsilon=0.2$ width, i.e., the empirical-
Bernstein CS reaches $\varepsilon$ width faster than the Hoeffding CS when
$N_{\text{lg}}$ is larger, and the betting CS is the faster than both
Hoeffding and empirical-Bernstein CSs.

$0$$20$$40$$60$$80$$0$$0.5$$1$Sample Size ($\displaystyle n$) Width of
CS$\displaystyle N_{1}/N=0.2,f\propto\pi$Hoef.Emp. Bern.Bet

$0$$50$$100$$150$$200$$0$$0.5$$1$Sample Size ($\displaystyle n$)
$\displaystyle N_{1}/N=0.8,f\propto\pi$

$0$$20$$40$$60$$80$$0$$0.5$$1$Sample Size ($\displaystyle n$) $\displaystyle
N_{1}/N=0.2,f\propto 1/\pi$

$0$$50$$100$$150$$200$$0$$0.5$$1$Sample Size ($\displaystyle n$)
$\displaystyle N_{1}/N=0.8,f\propto 1/\pi$

Figure 6: Plots showing the variation of the width of the betting, Hoeffding,
and empirical-Bernstein CSs using prop-M sampling strategies in different data
regimes with $N=200$; all CSs here also are intersected with the logical CS of
Section 2.2. We can see that empirical-Bernstein is tighter than Hoeffding in
cases where the proportion of transactions with large weights is high (i.e.,
$N_{\text{lg}}/N$ is large), and vice versa. Across the board, the betting CS
is tighter than both Hoeffding and empirical-Bernstein CSs.

$20$$25$$30$$0$$0.2$$0.4$$0.6$$0.8$$1$Stopping TimesDensity$\displaystyle
N_{1}/N=0.2,f\propto\pi$Hoef.Emp. Bern.Bet

$20$$40$$60$$80$$100$$0$$0.2$$0.4$$0.6$$0.8$$1$Stopping Times$\displaystyle
N_{1}/N=0.8,f\propto\pi$

$10$$20$$30$$0$$0.2$$0.4$$0.6$$0.8$$1$Stopping Times$\displaystyle
N_{1}/N=0.2,f\propto 1/\pi$

$20$$30$$40$$0$$0.2$$0.4$$0.6$$0.8$$1$Stopping Times$\displaystyle
N_{1}/N=0.8,f\propto 1/\pi$

Figure 7: Histograms of the first time for each CS to reach a width of
$\varepsilon=0.2$ with $N=200$. We choose a larger $\varepsilon$ than in
Experiment 1 for purposes of demonstrating the difference between the CSs, as
all CSs converge to the logical CS and have nearly identical stopping time
distribution for small values of $\varepsilon$. We can see that the empirical-
Bernstein CS is reaches $\varepsilon$ width earlier than Hoeffding CS when
$N_{\text{lg}}$ is large and the reverse is true when $N_{\text{lg}}$ is
small, and the betting CS reaches $\varepsilon$ uniformly the fastest.

##  Appendix G Experiments with Housing Sales Data

We now apply our auditing scheme to the transactions in the ‘House Sales in
King County’ dataset from Kaggle. The dataset consists of $21,616$ datapoints,
each consisting of $21$ features describing the house (such as the number of
bedrooms, the number of bathrooms, square footage, floors, condition, etc),
and one target variable price. We treat the price values as the ‘reported
monetary values’ for our framework.

#### Creating the ground truth.

To adapt the dataset to our problem, we first need to generate the ‘ground
truth’, that is, the true $f$-values. To do this, we proceed in the following
steps:

  * •

We first select $10\%$ of the dataset, and assign them some arbitrary $f$
values in the range $(0,0.7)$.

  * •

Using this ‘labelled’ dataset, we train a random forest regressor with $200$
trees, and mean-absolute error criterion.

  * •

Finally, this trained regressor is then used to generate the ground truth for
the remaining $90\%$ of the dataset.

The reason for using this approach for generating the ground truth, is that we
want it to be dependent on the additional features associated with each
transaction.

#### Generating the side-information.

Having obtained the $M$ and $f$-values, we obtain the side-information (i.e.,
$S$-values) by using $10\%$ of the remaining labelled data to train another
predictor for generating side-information on the rest of the data. In our
experiments, we either used a single decision-tree regressor, or a random
forest with a small number of trees (fewer than $50$). Informally, we expect
that increasing the capacity of the regressor should lead to increased
correlation between the ground truth and the side-information.

$100$$150$$200$$0$$0.02$$0.04$$0.06$Stopping TimesDensityStopping Times
distribution ($\rho\approx 0.71$)propMpropM+CVuniform

$100$$150$$200$$0$$0.02$$0.04$$0.06$$0.08$Stopping TimesDensityStopping Times
distribution ($\rho\approx 0.82$)propMpropM+CVuniform

Figure 8: Histograms of the first time for each CS to reach a width of
$\varepsilon=0.05$ with $N=250$. As expected, the prop-M strategy (both with
and without control variates) is significantly more sample-efficient than the
uniform baseline, and furthermore, the improvement by using control variates
increases with increasing informativeness (i.e., $\rho$) of the side-
information.

#### Experimental Results.

In Figure 8, we consider two instances of this problem: (i) side-information
generated by a decision-tree regressor, and (ii) side-information generated by
a random-forest regressor, consisting of $10$ trees. In the former case, the
correlation between the side information and the ground-truth is approximately
$0.71$, while in the latter it is around $0.82$. As shown in the plots, the
prop-M based strategies (both with and without control variates) significantly
outperform the uniform baseline strategy. Furthermore, the improvement by
incorporating control variates increases with increasing correlation.