1Department of Control System and Instrumentation Engineering,
King Mongkut’s University of Technology Thonburi (KMUTT), Bangkok, Thailand
(E-mail:l<EMAIL_ADDRESS><EMAIL_ADDRESS>
2Department of Information Technology and Media Design,
Nippon Institute of Technology (NIT), Saitama, Japan
(E-mail<EMAIL_ADDRESS>

# Modeling the Material-Inventory Transportation Problem Using Multi-Objective
Optimization

Issarapong Khuankrue1† Sudchai Boonto1 and Yasuhiro Tsujimura2

###### Abstract

In the era of industry 4.0, the procurement in supply chain management is the
key to develop information management systems. It directly affects production
planning failure. In this case, it is the process to prepare and confirm the
material-inventory be ordinal stages and be able to produce the products in
any production line. In terms of industrial informatics, it can provide
information management approaches for leveraging data sharing between
factories. The multi-objective optimization will be enabled by the integration
of material-inventory, production planning and monitoring, and transportation
planning collaboration. The material-inventory transportation problem is the
virtual factory situation when production plan failure occurs. It becomes the
cost to transport material between each factory and the distribution to
clients. In this study, the question of the material-inventory transportation
problem is : How can we transport other materials from one factory into
another factory? This study proposed a model to found out about the adjustment
of material-inventory by means of transportation. The objective of this model
is to minimize the whole production cost and total transportation cost.

###### keywords:

Information Management Systems, Material-Inventory Transportation Problem,
Supply Chain Management, Multi-Objective Model

##  1 Supply Chain Management in Industry 4.0

With the development of Industry 4.0, the supply chain management is the core
area of information management systems application. The procurement of
inventory can directly affect production planning failure. In this case, it is
the process to prepare and confirm the material-inventory be ordinal stages
and be able to produce the products in any production line.

The material-inventory transportation problem is the virtual factory situation
when production plan failure occurs. It becomes the cost to transport material
between each factory and the distribution to clients. In this study, the
problems of inventory and transportation in factories did not have the
material-inventory enough for production. The research question is : How can
we transport other materials from one factory into another factory? This study
proposed a way to found out about the adjustment of material-inventory by
means of transportation.

###  1.1 Four functions of Supply Chain Management (SCM)

Supply Chain Management (SCM) is the way to manage the flow of products and
services, including the movement and storage of raw material, inventory, and
the finished goods from many points to consumption. The network of SCM is the
connection and relation of channels and nodes of businesses combine in the
provision of products and services required by end customers in a supply
chain. The objective of SCM is to make the net value on supply with demand and
measuring the performance of the production. In the industry 4.0, B. Tjahjono
and others [1] conducted their research to explore the impact of information
technology or industry 4.0 on supply chain management (SCM) by focusing on
four functions including 1) Procurement, 2) Transport Logistics, 3) Warehouse,
and 4) Order Fulfillment. They reviewed several sources of information and
analyzed the advantages or disadvantages which impact the SCM throughout Key
Performance Indicators (KPI) of each scope. The KPIs relied on the majority
activities in each function.

The procurement was categorized in purchasing activity, so the KPIs would be
related to the quality of suppliers’ services and goods. In terms of the
warehouse, the storage was set as KPIs to evaluate the quality of stock
management. The inventories moving activity from one place to another place
was considered as transport logistics’ KPIs. Finally, the fulfillment process
was measured by sale activity because the quality of fulfillment in
distribution channels would directly impact to sales . They found that the
order fulfillment would be impacted by positive from industry 4.0 trend.
Similarly, technology would be an opportunity for transport logistics. On the
other side, warehouse and procurement functions were considered as
opportunities or threats. They mentioned that some technology could be both
opportunities and threats because all supply chain functions were related.
Therefore, it depended on how to implement technology and management.
Moreover, They believed that the core advantages of technology application
were about increased flexibility, quality standards, efficiency, and
productivity.

###  1.2 Servitization : Outcome as a Service

Servitization concept is about customer-centric to add value through products,
service, or other processes. [2] It brings to the question: How the production
industry adapt to the big data era and suggested some essential technology for
long-lasting innovative service? J. Lee and others [3] reviewed that one of
the significant trend which drives the manufacturing industry to be innovative
as servitization. Another factor that drove industry was a big data
environment. Cyber-Physical System (CPS) framework was applied in the big data
era for supporting the machines to do self-evaluation and make intelligent
decisions. Moreover, they concluded that there were four areas that generated
the 4.0 industry revolution. They were prognostics and health management, SCM
and business management, minimize cost, and improve the working environment.

In the same way, J. C. De Man and J. O. Strandhagen [4] studied the effect of
4.0 industry evolution to a sustainable business model. The descriptive
meaning of a sustainable business model that it was the model transform inputs
to outputs that were efficient, sufficient, and consistency delivery these
values products or services to customers. However, the sustainable strategy
was not applied for the long-lasting product but it used for sustainable
economic advantage. They also mentioned that even the challenge of industry
4.0 in a sustainable business model that how well value proposition of
business was delivered to the customer, the information technology was still
able to create a competitive advantage for the business. The paper also
identified that the company trended to concern about collecting data for the
supply chain management.

##  2 Material-Inventory Transportation Model

###  2.1 Problem Statement

The Material-Inventory Transportation (MIT) problem is the virtual factory
situation when production plan failure occurs. It becomes the cost to
transport material ($TC$) between each factory and the distribution to
clients. As shown in Fig.1, some of the factories ($SI_{i}$) have manufactured
the same products ($y_{i}$) with different productivity.

The process begins when the total order ($Y$) comes to places a purchasing
order. Then in the production planning phase, an order will consider making
the production plan. The information management system will support to check
the necessary material ($l_{k}$) to make an ordered product. The information
management system has to check another’s factories’ whether or not the
factories have surplus inventories. In case that the factories cannot produce
the assigned amount of products due to a lack of materials, the system will
make the transportation plan at the transportation planning phase. Material
transportation will occur in this state. Otherwise, If a factory has a surplus
of the materials, the factory would provide the surplus to other factories,
which is short of the material, with enough amount of material by
transportation using a track. Ordinal production planning will be approved in
this state.

Figure 1:  Overview of Material-Inventory Transportation Model.

Note that, the lacks and surpluses of materials are observed by sensors
embedded in the factories. The sensors, or CPS, send inventory information to
the central control center through a cloud computing environment. The central
control center draws up production plans for every factory and transportation
plan in the virtual factory.

In terms of SCM, inventory transportation has many logistic problems in their
business and still cannot find the best way to solve the logistic problem.
Transportation topics still have problems, which need to figure out and
improve. This study desired to be a part of the decreasing cost of
transportation. When inventory transportation occurs whenever the condition is
satisfied. When the total amount of materials are over the capacity of a
track, the materials are transported by enough number of tracks.

###  2.2 Multi-Objective MIT Model

In general, t10he multi-objective optimization[5] is related to evolutionary
algorithms, which is solving problems that rely on their population. It
generates several elements of the optimal set, or the Vilfredo Pareto’s
optimal set, in a single run. Normally, the population is randomly generated
to be a potential solution set. The individual, which is each solution in
population, will encode and contains all the decision variables of the problem
to be solved. So, the fitness function will define as the performance
measurement for each of the solutions, and find the best solution when
compared to the others. On the fitness function, the objective function aims
to optimize. It means a variation of the objective function needs to solve the
problem. Then, the stochastic selection process, or mating of individual, is
the process for contributing each individual to be a higher probability of
being selected. The offspring, or mutate, are generated and be the new
population to be evaluated at the next iteration, or generation.

The evolutionary algorithms are very effective in solving single-objective
optimization problems. The ideal of the multi-objective optimization procedure
simplified into two steps. The first step is to find multiple trade-off
optimal solutions with a wide range of values for objectives. Then, choose one
of the obtained solutions using higher-level information. [6]

The multi-objective optimization procedure will be enabled by the integration
of material-inventory, production planning and monitoring, and collaboration
of transportation planning.

In this study, the main notation used in the following equations are
including, $TC$ is the total transportation cost, $PC$ is the total production
cost, $SI$ is a set of factories, $l_{k}$ is a necessary amount of material
$k$ to make a product (k =1,2, 3, …., m), $m$ is the number of kinds of
materials, $L_{i}{}_{k}$ is an inventory of material $k$ at a factory $i$,
$y_{k}$ is a set of divided amount to produce the order $Y$ by use material
$k$, $q_{j}{}_{i}{}_{k}$ is the amount of material $k$ transported from
factory $j$ to factory $i$, $r$ is the maximum number available trucks, $tc$
is a unit transportation cost, $V$ is the maximum loading capacity of a truck,
and $SL$ is a set of material-inventory that need to transport which is
$\Delta_{i}{}_{j}$ = 1 if some materials are transported from factory $i$ to
factory $j$ or otherwise $\Delta_{i}{}_{j}$ = 0.

In the initialization stage, the defined assumption is as follows: The order
and inventory in each factory are constant. Then, All trucks have the same
specifications, and lastly, a transportation cost does not change according to
the weight of materials. The objective of the proposed model is to minimize
the production cost and transpiration cost, which can be expresses as:

$\displaystyle\begin{array}[]{rcl}\textbf{Objective}:Minimize(PC+TC)\end{array}$
(2)

In term of constraining, The feasibility condition for the total material-
inventory is

$\displaystyle\begin{array}[]{rcl}\sum_{i\in I}L_{ik}\geq Y*l_{k}\mid\forall
k\\\ \end{array}$ (4)

To check the occurrence condition of material-inventory transportation, The
Ordinal Production Planning stage will be happened If $(l_{ik}*y_{k}\leq
L_{ik}\mid\forall i,k)$ Then $\Delta=0$. Otherwise, the Material
Transportation occur stage will be replace the ordinal stage Else If
$(l_{ik}*y_{k}>L_{ik}\mid\exists i,k)$ Then $\Delta=1$

At this step, the material-inventory transportation adjustment can be
expressed in Algorithm1: CheckInventory.

Algorithm 1 CheckInventory

1:Input: $l_{k}$ : a necessary amount of material k to make a product (k =1,2,
3, …., m)

2:$m$ : the number of kinds of materials

3:$L_{i}{}_{k}$ : an inventory of material k at a factory i

4:$y_{k}$ : a set of divided amount to produce the order Y by use material k

5:Output: a set of of material k in $\cup^{m}_{k=1}SI_{k}$

6:

7:while The amount of the material k in the $factory_{i}$ is not enough to
make $y_{i}$ products. do

8: $j\leftarrow 0$

9: if $l_{k}*y_{k}<=L_{i}{}_{k}$ then

10: $\Delta\leftarrow 0$ (Ordinal Production Planning)

11: else if then

12: $\Delta\leftarrow 1$ (Material Transportations occur)

13: for $k\leftarrow 1$ to $m$ do

14: for $i\leftarrow 1$ to $len(SI)$ do

15: if $l_{k}*y_{k}>L_{i}{}_{k}$ and $l_{k}*y_{k}<L_{j}{}_{k}$ then

16: $SI_{k}\leftarrow l_{k}$

17:return  $\cup^{m}_{k=1}SI_{k}$

To make the transportation plan, a constraint for the maximum number of trucks
is

$\displaystyle\begin{array}[]{rcl}\sum_{i\in
SI_{ALL}}\\{\frac{\lceil\sum_{k\in SM_{i}}q_{ijk}\mid j\in SL_{k},i\neq
j\rceil}{V}\\}\leq r\end{array}$ (6)

Then, The total transportation cost is
$TC=\sum_{i\in I}\\{\sum_{j\in SL_{k}}\sum_{i\in
SI_{ALL}}\\{\frac{\lceil\sum_{k\in SM_{i}}q_{i}{}_{j}{}_{k}\mid j\in
SL_{k},i\neq j\rceil}{V}\\}*tc\\}$

Lastly, The total production cost is $PC=\sum_{i\in I}pc_{i}*y_{i}$ .

The above model will be considered to make the decision on optimal solutions
based on the objective, as the first step for multi-objective optimization. It
can be do the iteration and change the wide range of values for objectives
rely on the obtained solutions using higher-level information. The other
factors have to concern include the type of order, production and
transportation cost, and so on.

##  3 Conclusion

To answer the question: How can we transport other materials from one factory
into another factory? This paper proposed Material-Inventory Transportation
(MIT) model to check and judge the number of material from one point to
another point in their production environment. It is a part of the procurement
function in supply chain management. The objective of this model has been set
for minimizing all production costs and total transportation costs. In this
model, the information management system provides the process to prepare and
confirm the material-inventory be ordinal stages and be able to produce the
products in any production line, which is the data sharing between factories.
This model design based on multi-objective optimization, which integrates the
material-inventory, production planning, and monitoring, and collaboration of
transportation planning.

This preliminary model still on the process to develop agent-based modeling
and simulation. It is able to contribute to the landscape of data, which is
the possible data on the situation. It requires setting the initial behavior
of the agent, depending on the business goal, and focusing on predicting the
possible failure. The most feasible approach is to understand in deep of
system complexity. So the new area or other functions on supply chain
management could be considered on the opportunity of an information management
system. The future model could also move to collect the data based on the
business and supply chain experience, especially industry 4.0.

## References

  * [1] B. Tjahjono, C. Esplugues, E. Ares, and G. Pelaez, “What does Industry 4.0 mean to Supply Chain?,”Procedia Manuf., Vol. 13, pp. 1175–1182, 2017.
  * [2] S. Vandermerwe and J. Rada, “Servitization of business: Adding value by adding services,” Eur. Manag. J., 1988.
  * [3] J. Lee, H. A. Kao, and S. Yang, “Service innovation and smart analytics for Industry 4.0 and big data environment,” Procedia CIRP,Vol. 16, pp. 3–8, 2014.
  * [4] J. C. De Man and J. O. Strandhagen, “An Industry 4.0 Research Agenda for Sustainable Business Models,” Procedia CIRP, Vol. 63, pp. 721–726, 2017.
  * [5] C. A. Coello Coello, “Multi-objective optimization,” in Handbook of Heuristics, 2018.
  * [6] K. Deb, Multi Objective Optimization using Evlutionary Algorithms. John Wiley and Sons, Ltd, 2001.


[name=Theorem,sibling=theorem]thm2 [name=Lemma,sibling=theorem]lem2
[name=Proposition,sibling=theorem]prop2

# Majority-of-Three: The Simplest Optimal Learner?

Ishaq Aden-Ali Department of EECS, UC Berkeley. Email<EMAIL_ADDRESS>Mikael Møller Høgsgaard Computer Science Department, Aarhus University. Email:
{hogsgaard<EMAIL_ADDRESS>Kasper Green Larsen22footnotemark: 2 Nikita
Zhivotovskiy Department of Statistics, UC Berkeley. Email:
<EMAIL_ADDRESS>
###### Abstract

Developing an optimal PAC learning algorithm in the realizable setting, where
empirical risk minimization (ERM) is suboptimal, was a major open problem in
learning theory for decades. The problem was finally resolved by Hanneke a few
years ago. Unfortunately, Hanneke’s algorithm is quite complex as it returns
the majority vote of many ERM classifiers that are trained on carefully
selected subsets of the data. It is thus a natural goal to determine the
simplest algorithm that is optimal. In this work we study the arguably
simplest algorithm that could be optimal: returning the majority vote of three
ERM classifiers. We show that this algorithm achieves the optimal in-
expectation bound on its error which is provably unattainable by a single ERM
classifier. Furthermore, we prove a near-optimal high-probability bound on
this algorithm’s error. We conjecture that a better analysis will prove that
this algorithm is in fact optimal in the high-probability regime.

##  1 Introduction

In the setting of realizable Probably Approximately Correct (PAC) learning
[17, 18, 21], the goal is to learn or approximate an unknown target function
$f^{\star}\in\\{0,1\\}^{\mathcal{X}}$ from a labelled training sample
$(S,f^{\star}(S))=((X_{1},f^{\star}(X_{1})),\ldots,(X_{n},f^{\star}(X_{n})))$,
where the $X_{i}$’s are i.i.d. samples from an unknown distribution $P$ over
an instance space $\mathcal{X}$. In the realizable setting, we are furthermore
promised that $f^{\star}$ belongs to a known function class
$\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ of Vapnik-Chervonenkis (VC)
dimension $d$.

Given a labelled training sample $(S,f^{\star}(S))$, a learning algorithm
produces a function $\widehat{f}_{S}\in\\{0,1\\}^{\mathcal{X}}$ with the goal
of minimizing the probability of mispredicting the label of a new sample from
$P$, where we denote this error by
$\operatorname{err}_{P}\left(\widehat{f}_{S}\right):=\operatorname*{\mathbf{Pr}}_{X\sim
P}[\widehat{f}_{S}(X)\neq f^{\star}(X)]$. The simplest reasonable learning
algorithm, known as _empirical risk minimization_ (ERM), simply reports an
arbitrary function $\widehat{f}_{S}\in\mathcal{F}$ that is consistent with
$f^{\star}$ on the training data, i.e.
$\widehat{f}_{S}(X_{i})=f^{\star}(X_{i})$ for all $i=1,\dots,n$. Classic work
by Blumer et al. [4] (the same bound also essentially follows from the earlier
works [19, 20]) shows that for any $\delta>0$, it holds with probability
$1-\delta$ over $S$ that any $\widehat{f}_{S}\in\mathcal{F}$ consistent with
$f^{\star}$ on $S$ has

$\operatorname{err}_{P}\left(\widehat{f}_{S}\right)=O\left(\frac{d}{n}\log\left(\frac{n}{d}\right)+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$
(1)

On the lower bound side, there exists an instance space $\mathcal{X}$ and
function class $\mathcal{F}$ such that for a certain ERM algorithm, there is a
target function $f^{\star}\in\mathcal{F}$ and hard distribution $P$ for which
Eq. 1 is tight [11, 3, 16, 10]. Learning algorithms that always output a
function in $\mathcal{F}$ are referred to as _proper_ learning algorithms.
Generally, it is known that not only ERM, but all proper learners fail to
achieve the optimal error bound in the PAC learning framework. See the
corresponding lower bounds in [5].

For _improper_ learning algorithms — algorithms that are allowed to output an
arbitrary function $\widehat{f}_{S}\in\\{0,1\\}^{\mathcal{X}}$ — known lower
bounds on the error only imply that we must have

$\operatorname{err}_{P}\left(\widehat{f}_{S}\right)=\Omega\left(\frac{d}{n}+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$
(2)

Developing an algorithm with a matching error upper bound, or strengthening
the lower bound, was a major open problem for decades. This was finally
resolved in 2015 when Hanneke [9], building on the work of Simon [16],
proposed the first optimal algorithm with an error upper bound matching Eq. 2,
leading to the optimal error bound

$\Theta\left(\frac{d}{n}+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$
(3)

Hanneke’s algorithm is based on constructing a large number ($\approx
n^{0.79}$) of sub-samples $S_{1},S_{2},\dots\subseteq S$ of the training data.
This algorithm then runs ERM on each $(S_{i},f^{\star}(S_{i}))$ to obtain
functions $\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\dots$ and finally combines
them via a majority vote. The sub-samples $S_{i}$ are constructed to have a
carefully designed overlapping structure, and an intricate inductive argument
exploiting this structure is then used to argue optimality. Recent work by
Larsen [13] shows that the carefully designed overlap structure may instead be
replaced by the significantly simpler strategy of sampling each $S_{i}$ as
$\Theta(n)$ samples with replacement from $S$. This algorithm is precisely the
classic heuristic known as Bagging, or bootstrap aggregation, due to Breiman
[6]. Furthermore, the proof shows that a mere $O(\log(n/\delta))$ sub-samples
suffice for an optimal sample complexity. The proof is however even more
involved than Hanneke’s and uses his analysis at its core.

Another line of work studied an alternative learning algorithm, the one-
inclusion graph algorithm of Haussler, Littlestone, and Warmuth [11] that
returns a function $\widehat{f}_{\mathrm{OIG}}$. This work also introduces the
_prediction model_ of learning, which focuses on achieving bounds on the
_expected error_ rather than _high probability_ bounds on the error. The one-
inclusion graph algorithm was initially shown to have an expected error of

$\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P}\left(\widehat{f}_{\mathrm{OIG}}\right)\right]\leq\frac{d}{n+1},$
(4)

which was later proven to be optimal within this prediction model [14].
Because of the tightness of the in-expectation bound Eq. 4, Warmuth
conjectured [22] that the one-inclusion graph algorithm achieves an error
upper bound matching the general lower bound Eq. 2 in the high probability
regime.

Recent work by Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [1]
unfortunately refutes this conjecture. Concretely, they show that for any
$d\in\mathbb{N}$, sample size $n\geq d$ and confidence parameter $\delta\geq
cd/n$, there exists a function class
$\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC dimension $d$ and a hard
distribution $P$ such that a certain implementation of the one-inclusion graph
algorithm has, with probability at least $\delta$,

$\operatorname{err}_{P}\left(\widehat{f}_{\mathrm{OIG}}\right)=\Omega\left(\frac{d}{\delta
n}\right).$

This result essentially says that, in general, the one-inclusion graph
algorithm’s high-probability guarantee cannot be better than applying Markov’s
inequality to the in-expectation guarantee in Eq. 4. In recent work also by
Aden-Ali et al. [2], it was shown that if one combines the output of
$\Omega(n)$ predictions made by one-inclusion algorithms on prefixes of the
training data $((X_{1},f^{\star}(X_{1})),\ldots,(X_{m},f^{\star}(X_{m})))$ for
$m=n/2,\dots,n$ via a majority vote, then the resulting function is optimal in
the high probability regime and, therefore, matches the error bound Eq. 3.
Unfortunately, the one-inclusion graph algorithm (and this extension) is much
less intuitive than the aforementioned algorithms based on taking majority
votes of ERMs.

###  1.1 The simplest possible optimal algorithm?

In light of prior work, we have several provably optimal algorithms for PAC
learning in the realizable setting. The algorithms and their analyses vary in
complexity and a natural question remains: What is the simplest possible
optimal algorithm? We know from lower bounds that the algorithm has to be
improper and as such must be more complicated than ERM. Bagging is arguably
the simplest algorithm among previous proposed algorithms, but has the most
difficult analysis. The voting among one-inclusion algorithms has a somewhat
simple proof, but the algorithm is not the simplest. In this work, we consider
what is perhaps the simplest imaginable improper algorithm, _Majority-of-
Three_ (_ERMs_): Partition $S$ into three equal-sized disjoint pieces
$S_{1},S_{2},S_{3}$, run the same ERM algorithm on each
$(S_{i},f^{\star}(S_{i}))$ to obtain
$\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}}$, and combine
them via a majority vote to produce the function
$\mathrm{Maj}{(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})}$.
Since a majority vote of two functions is undefined when the functions
disagree, this is arguably the simplest possible improper algorithm. Our first
main result shows that this concrete majority vote of three ERMs, which we
will refer to as Majority-of-Three throughout, is optimal in expectation. []
Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$ and target function
$f^{\star}\in\mathcal{F}$. For any ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$ it follows that

$\operatorname*{\mathbb{E}}_{S_{1},S_{2},S_{3}\sim
P^{n}}\left[\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)\right]=O\left(\frac{d}{n}\right).$

This result shows that Majority-of-Three matches the optimal expectation bound
Eq. 4 achieved by the one-inclusion graph algorithm, up to a universal
constant. Furthermore, our proof of Theorem 1.1 is in fact quite simple,
especially compared to the previous proof that Bagging is optimal.

We note here that a single ERM alone is sub-optimal by a multiplicative
$\ln(n/d)$ factor in-expectation (see the well-known lower bound in [11,
Theorem 4.2]). We emphasize that in Subsection 1.1, the ERMs corresponding to
$S_{1}$, $S_{2}$ and $S_{3}$ can be chosen by _any_ algorithm $\widehat{f}$
that outputs functions consistent with the sample. The only restriction is
that it is the same algorithm $\widehat{f}$ that is run on each $S_{i}$ (and
that the subsets $S_{i}$ are disjoint and thus i.i.d.).

We now turn our attention to the high-probability regime, where we prove the
following result. [] Fix a function class
$\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC dimension $d$. Fix a
distribution $P$ over $\mathcal{X}$ and target function
$f^{\star}\in\mathcal{F}$. Fix any ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. For any parameter
$\delta\in(0,1/2]$ it holds with probability at least $1-\delta$ over the
randomness of $S_{1},S_{2},S_{3}\sim P^{n}$ that

$\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)=O\left(\frac{d}{n}\log\left(\log\left(\min\left\\{\frac{n}{d},\frac{1}{\delta}\right\\}\right)\right)+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$

This bound is sub-optimal due to the $\log(\log(\min\\{n/d,1/\delta\\}))$
term, however the additive $\log(1/\delta)$ term dominates for $\delta\leq
d^{-d}$. Thus, Majority-of-Three is optimal both in the constant (Subsection
1.1) and high-probability regimes (Subsection 1.1). Because of this, we
conjecture that Majority-of-Three is in fact optimal for all $\delta$ and
leave this as an open question for future research.

######  Conjecture 1.1.

Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$ and target function
$f^{\star}\in\mathcal{F}$. Fix any ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. For any parameter
$\delta\in(0,1)$ it holds with probability at least $1-\delta$ over the
randomness of $S_{1},S_{2},S_{3}\sim P^{n}$ that

$\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)=O\left(\frac{d}{n}+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$

###  1.2 An alternative by Simon

In his breakthrough work, Simon [16] proposed taking majority votes of three
ERMs trained on certain sub-samples of the training sample.111Simon studied
majority votes over any odd number $L$ of ERMs trained on specific sub-samples
of the data. He also proved bounds on the error of these majority votes that
shrunk as $L$ increased. However, his algorithm is slightly different than
ours. Concretely, he proposed the following algorithm: given an ERM algorithm
and labelled training sample, partition $S$ into three equal-sized disjoint
pieces $S_{1},S_{2},S_{3}$ and for $i=1,2,3$, run any ERM algorithm on
$((S_{1},\ldots,S_{i}),f^{\star}((S_{1},\ldots,S_{i})))$ to obtain
$\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}$,
and combine them via a majority vote to produce the function
$\mathrm{Maj}{(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})})}$.
Intuitively, more training data for the ERM should be better and Simon also
proved the following high-probability upper bound on his algorithm’s error:

$\operatorname{err}_{P}\left(\mathrm{Maj}\left(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}\right)\right)=O\left(\frac{d}{n}\log\left(\log\left(\frac{n}{d}\right)\right)+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$
(5)

This bound is asymptotically smaller than the tight bound Eq. 1 that holds for
a single ERM.

We note that Simon also discusses the applicability of his analysis to more
general majorities of ERMs including the Majority-of-Three function
$\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})$
analyzed in this work.222Simon’s analysis applies to any majority where each
of the participating ERMs is trained on an independent constant fraction of
the training sample. However, adopting the approach in [16], the error of
Majority-of-Three is controlled by the same upper bound as expressed in (5),
which is suboptimal as demonstrated by Subsection 1.1. Furthermore, we
additionally remark that a similar in spirit construction based on the
majority of three functions has been extensively studied in Schapire’s PhD
thesis [15]. However, his approach (inspired by what we now know as boosting)
works with essentially any learning algorithm and is not necessarily limited
to ERM.

In the same work [16], Simon further showed that for a specific function class
$\mathcal{F}$ for which there is a choice of target function
$f^{\star}\in\mathcal{F}$ and hard distribution $P$ that certify the tightness
of Eq. 1 for a certain choice ERM, his algorithm can actually achieve an
optimal upper bound matching Eq. 2 for $\mathcal{F}$ regardless of the choice
of $f^{\star}\in\mathcal{F}$ and $P$. Unfortunately, we prove the following
lower bound that shows that the upper bound Eq. 5 cannot be improved in
general, answering a question posed by Simon.

[] For any sample size $n$ that is divisible by $6$ and positive integer
$d\leq n$, there is a function class $\mathcal{F}\subseteq\\{0,1\\}^{[0,1]}$
with VC dimension $4d$, distribution $P$ over $[0,1]$, target function
$f^{\star}\in\mathcal{F}$, and an ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$ such that the
following holds: given i.i.d. training samples $S_{1},S_{2},S_{3}\sim P^{n}$,

$\operatorname{err}_{P}\left(\mathrm{Maj}\left(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}\right)\right)=\Omega\left(\frac{d}{n}\log\left(\log\left(\frac{n}{d}\right)\right)\right),$

with probability at least $2/3$ over the randomness of
$S=(S_{1},S_{2},S_{3})$. This result shows that Simon’s algorithm
unfortunately cannot achieve the optimal bound Eq. 3 in general. This
indicates that it is important that the ERM algorithm used in Majority-of-
Three is instantiated on disjoint subsets of the training sample.

###  1.3 Notation

We use $\mathcal{X}$ to denote the _instance space_ ,
$\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ to denote a function class, and
let $\mathcal{Z}=\mathcal{X}\times\\{0,1\\}$. Throughout, $P$ is a
distribution over $\mathcal{X}$ and $f^{\star}\in\mathcal{F}$ is the unknown
_target function_ in the class. For $n\in\mathbb{N}$ and a distribution $P$,
we denote by $P^{n}$ the product distribution of $P$. We say that a sequence
$S=(X_{1}\ldots,X_{n})$ is a _training sample_ of size $n$ where $X_{i}$ are
i.i.d. samples from a distribution $P$. For a training sample
$S=(X_{1},\dots,X_{n})$, we find it useful to write
$(S,f^{\star}(S))=((X_{1},f^{\star}(X_{1})),\ldots,(X_{n},f^{\star}(X_{n})))$,
and we call this the _labelled training sample_. For training samples
$S_{1}=(X_{1},\ldots,X_{n})$ and $S_{2}=(X_{n+1},\ldots,X_{n+m})$ we let
$(S_{1},S_{2})=(X_{1},\ldots,X_{n},X_{n+1},\ldots,X_{n+m})$, and for $S_{1},$
$S_{2}$ and $S_{3}$ we take $(S_{1},S_{2},S_{3})=((S_{1},S_{2}),S_{3})$. We
define the error of a binary function $f$ under distribution $P$ and target
function $f^{\star}$ to be
$\operatorname{err}_{P}\left(f\right)=\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[f(X)\not=f^{\star}(X)\right]$. For any measurable set
$R\subseteq\mathcal{X}$, we define $P_{R}$ to be the conditional distribution
of $P$ restricted to $R$, i.e. for $X\sim P_{R}$ we have that for any
measurable function $g$ that $\operatorname*{\mathbb{E}}_{X\sim
P_{R}}\left[g(X)\right]=\operatorname*{\mathbb{E}}_{X\sim
P}\left[g(X)\mathbf{1}\\{{X\in R}\\}\right]/\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[X\in R\right].$

For a function class $\mathcal{F}$ and subset
$U=\\{x_{1},\ldots,x_{d}\\}\subseteq\mathcal{X}$ of $d$ points we let
$\mathcal{F}\mid_{U}$ denote the set $\\{y\in\\{0,1\\}^{d}\mid\exists
f\in\mathcal{F}:\forall i\in[d],\;f(x_{i})=y_{i}\\}$. The _Vapnik-Chervonenkis
(VC) dimension_ is then defined as the largest number $d$ such that there
exists a point set $U\subseteq\mathcal{X}$ of size $d$ such that the
cardinality of $\mathcal{F}\mid_{U}$ is $2^{d}$. We use $\log(x)$ and $\ln(x)$
to denote $\log_{2}(x)$ and $\log_{e}(x)$ respectively and we also use
$\operatorname{Log}(x):=\max\\{2,\log_{2}(x)\\}$ to denote a truncated
logarithm.

Let $\mathcal{Z}^{*}=\cup_{i=1}^{\infty}\mathcal{Z}^{i}$ be the set of all
possible labelled training samples. We define a _learning algorithm_
$\widehat{f}$ to be a mapping
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. That is, given a
labelled training sample $(S,f^{\star}(S))$ as input,
$\widehat{f}(\cdot;(S,f^{\star}(S))):\mathcal{X}\to\\{0,1\\}$ is the function
that is learned from $(S,f^{\star}(S))$. For ease of reading, we often denote
the learned function by
$\widehat{f}_{S}\coloneqq\widehat{f}(\cdot;(S,f^{\star}(S)))$. A learning
algorithm $\widehat{f}$ is an _Empirical Risk Minimizer (ERM)_ for the class
$\mathcal{F}$ if, given a labelled training sample $(S,f^{\star}(S))$ as
input, it output a function $\widehat{f}_{S}$ in $\mathcal{F}$ that satisfies
$\widehat{f}_{S}(X_{i})=f^{\star}(X_{i})$ for every $X_{i}$ that appears in
$S$. We define the majority vote of $k$ binary functions
$f_{1},\dots,f_{k}:\mathcal{X}\to\\{0,1\\}$ to be the function

$\mathrm{Maj}(f_{1},\dots,f_{k})(x)\coloneqq\mathbf{1}\\{f_{1}(x)+\dots+f_{k}(x)>k/2\\}.$

##  2 Majority-of-Three is optimal in-expectation

In this section, we prove the main in-expectation result for the Majority-of-
Three algorithm. Before we prove our result, we will find it helpful to
introduce some auxiliary notation. Throughout this section, we set
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$ to be a fixed (but
arbitrary) ERM algorithm. Fix a distribution $P$ over $\mathcal{X}$ and let
$f^{\star}\in\mathcal{F}$ be the target function. For any $x\in\mathcal{X}$ we
let

$p_{x}(n,f^{\star},P)=\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}[\widehat{f}_{S}(x)\not=f^{\star}(x)].$

In words, $p_{x}(n,f^{\star},P)$ is the chance that $\widehat{f}_{S}$ errs on
the point $x$ for an _average_ sample $S\sim P^{n}$. We now define a partition
of $\mathcal{X}$ based on $p_{x}(n,f^{\star},P)$. Consider the following sets
for any $i\in\mathbb{N}$:

$R_{i}(n,f^{\star},P)=\\{x\in\mathcal{X}:p_{x}(n,f^{\star},P)\in(2^{-i},2^{-i+1}]\\}.$

We often write $R_{i}=R_{i}(n,f^{\star},P)$ and $p_{x}=p_{x}(n,f^{\star},P)$
since $n$, $P$, and $f^{\star}$ will always be clear from the context. With
this notation in place, we are now ready to prove that Majority-of-Three has
an optimal in-expectation upper bound on its error. See 1.1

To prove Subsection 1.1, we require the following lemma which says that two
ERMs trained on 2 i.i.d. training samples of the same size rarely makes a
mistake on the same point.

######  Lemma 2.1.

Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$ and target function
$f^{\star}\in\mathcal{F}$. For any ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$ it follows that

$\operatorname*{\mathbb{E}}_{S_{1},S_{2}\sim
P^{n}}\left[\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[\widehat{f}_{S_{1}}(X)\not=f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\not=f^{\star}(X)\right]\right]\leq
c\frac{d}{n},$

where $c$ is a universal constant.

We postpone the proof of Lemma 2.1 for now and show how it implies Subsection
1.1.

###### Proof of Subsection 1.1.

For any fixed $x\in\mathcal{X}$ and fixed samples $S_{1},S_{2},S_{3}$, if
$\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})(x)\not=f^{\star}(x)$,
then there must be at least two distinct indices $i,j\in[3]$ such that
$\widehat{f}_{S_{i}}(x)\not=f^{\star}(x)$ _and_
$\widehat{f}_{S_{j}}(x)\not=f^{\star}(x)$. So,

$\displaystyle\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)$
$\displaystyle=\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})(X)\not=f^{\star}(X)\right]$
$\displaystyle\leq\sum_{\begin{subarray}{c}i,j\in[3]\\\
i<j\end{subarray}}\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[\widehat{f}_{S_{i}}(X)\not=f^{\star}(X)\wedge\widehat{f}_{S_{j}}(X)\not=f^{\star}(X)\right].$

Combining the above and Lemma 2.1 gives us

$\operatorname*{\mathbb{E}}_{S_{1},S_{2},S_{3}\sim
P^{n}}\left[\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)\right]\leq
3c\frac{d}{n}.$

This concludes the proof. ∎

We now move on to proving Lemma 2.1, where we will use the following lemma. []
Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$, target function
$f^{\star}\in\mathcal{F}$, and $R\subseteq\mathcal{X}$ such that
$\operatorname*{\mathbf{Pr}}_{X\sim P}\left[X\in R\right]\not=0$. For any ERM
algorithm $\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$ it
follows that

$\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\right]\leq
20\frac{d\operatorname{Log}(e\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in
R]n/d)}{\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n}.$

Lemma 2.1 is an immediate consequence of the celebrated uniform convergence
principle and a simple proof can be found in Subsection A.1. We now prove
Lemma 2.1.

###### Proof Lemma 2.1.

Let $S_{1}$ and $S_{2}$ be independent samples from $P^{n}$. By the
independence of $S_{1}$ and $S_{2}$ and the definition of $p_{x}$ we have, for
any $x\in\mathcal{X}$, that

$\displaystyle\operatorname*{\mathbf{Pr}}_{S_{1},S_{2}\sim
P^{n}}\left[\widehat{f}_{S_{1}}(x)\not=f^{\star}(x)\wedge\widehat{f}_{S_{2}}(x)\not=f^{\star}(x)\right]=\prod_{i=1}^{2}\operatorname*{\mathbf{Pr}}_{S_{i}\sim
P^{n}}\left[\widehat{f}_{S_{i}}(x)\not=f^{\star}(x)\right]$
$\displaystyle=\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{n}}\left[\widehat{f}_{S_{1}}(x)\not=f^{\star}(x)\right]^{2}=p_{x}^{2}.$

Using the above, the law of total expectation with partitioning
$(R_{i})_{i\in\mathbb{N}}$, and swapping the order of expectations ($X$ and
$(S_{1},S_{2})$ being independent), we get that

$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},S_{2}\sim
P^{n}}\left[\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[\widehat{f}_{S_{1}}(X)\not=f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\not=f^{\star}(X)\right]\right]$
$\displaystyle=\sum_{i=1}^{\infty}\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[X\in R_{i}\right]\operatorname*{\mathbb{E}}_{X\sim
P}\left[p_{X}^{2}|X\in
R_{i}\right]\leq\sum_{i=1}^{\infty}\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[X\in R_{i}\right]2^{-2i+2},$

where the inequality follows from the fact that $p_{x}\leq 2^{-i+1}$ for every
$x\in R_{i}$. We will now show that $\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[X\in R_{i}\right]\leq cdi2^{i}/n$ for every $i\in\mathbb{N}$ (for a
universal constant $c\geq 1$ chosen below), which combined with the above
gives us

$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},S_{2}\sim
P^{n}}\left[\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[\widehat{f}_{S_{1}}(X)\not=f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\not=f^{\star}(X)\right]\right]\leq\frac{4cd}{n}\sum_{i=1}^{\infty}i2^{-i}\leq
8c\frac{d}{n}.$

This yields the claim with the constant $8c$. Towards a contradiction, assume
there is an $i\in\mathbb{N}$ such that $\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[X\in R_{i}\right]>cdi2^{i}/n$, which is equivalent to
$\operatorname*{\mathbf{Pr}}_{X\sim P}\left[X\in R_{i}\right]n/d>ci2^{i}\geq
1$. Using this assumption, the fact that
$x\rightarrow\operatorname{Log}(ex)/x$ is decreasing for $x>0$, and Lemma 2.1,
we have

$\operatorname*{\mathbb{E}}_{S_{1}\sim
P^{n}}\left[\operatorname{err}_{P_{R_{i}}}\left(\widehat{f}_{S_{1}}\right)\right]\leq
20\frac{\operatorname{Log}(e\operatorname*{\mathbf{Pr}}_{X\sim P}\left[X\in
R_{i}\right]n/d)}{(\operatorname*{\mathbf{Pr}}_{X\sim P}\left[X\in
R_{i}\right]n/d)}\leq
20\frac{\operatorname{Log}\left(eci2^{i}\right)}{ci2^{i}}.$ (6)

By changing the order of expectations of the left hand side of the above and
using the fact that $p_{x}>2^{-i}$ for every $x\in R_{i}$, we also have

$\operatorname*{\mathbb{E}}_{S_{1}\sim
P^{n}}\left[\operatorname{err}_{P_{R_{i}}}\left(\widehat{f}_{S_{1}}\right)\right]=\operatorname*{\mathbb{E}}_{X\sim
P_{R_{i}}}\left[p_{X}\right]>2^{-i}.$ (7)

Combining the upper bound (6), the lower bound (7), and the fact that the
function $x\rightarrow\operatorname{Log}(ex)/x$ is decreasing for $x>0$, we
get

$\displaystyle 1<20\frac{\operatorname{Log}\left(eci2^{i}\right)}{ci}\leq
20\left(\frac{\operatorname{Log}\left(eci\right)}{ci}+\frac{2}{c}\right)\leq
20\frac{\operatorname{Log}(ec)+2}{c}.$

However, for $c$ large enough, the right hand side of the above is strictly
less than $1$. This gives us the desired contradiction and concludes the
proof. ∎

##  3 A lower bound for certain majorities

In this section, we prove that not all majorities of 3 ERMs trained on subsets
of the data are optimal. In particular, we show that Simon’s [16] original
partitioning scheme of the training sample into 3 sub-samples can produce a
majority of 3 ERMs with sub-optimal error. Recall Simon’s algorithm: partition
the training sample $S=(S_{1},S_{2},S_{3})$ into 3 equal pieces
$S_{1},S_{2},S_{3}$, train 3 ERMs
$\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}$,
and return the majority vote
$\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})})$.
Simon proved that this algorithm enjoys the PAC upper bound

$\operatorname{err}_{P}\left(\mathrm{Maj}\left(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}\right)\right)=O\left(\frac{d}{n}\log\left(\log\left(\frac{n}{d}\right)\right)+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).$

The next theorem shows that this algorithm unfortunately has a matching lower
bound on its error. See 1.2 Comparing the above bound with the upper bound in
Subsection 1.1, we see that if the ERMs did not overlap in their sub-samples
the log factor would not be present. The construction we use in our lower
bound is a modification of the usual construction used to prove a lower bound
on the error of a single ERM (see [3, 16]). In these constructions, one takes
the domain $\mathcal{X}$ to be a finite set of size roughly $n/\log(n/d)$
where $n\geq d$ is the sample size333These results are often stated as lower
bounds on the _sample complexity_ for some target error $\epsilon$. and the
function class $\mathcal{F}$ is taken to be all functions that assign the
value $1$ to at most $d$ points on $\mathcal{X}$. Furthermore, the target
function is set to be the $0$ function, and the sampling distribution is the
uniform distribution over $\mathcal{X}$. Finally, the “bad” ERM algorithm
returns any function that assigns as many 1’s to the domain as possible, while
being consistent on the observed samples. The error of this ERM is tightly
connected to the number of unique elements we sample from the domain. One can
then use a coupon collector argument to show that the error is
$\Omega(d\log(n/d)/n)$ with constant probability.

Simon noticed that we cannot directly use this “hard instance” to prove a
lower bound on his algorithm due to the structure of the class $\mathcal{F}$
[16, Theorem 7]. We get around this by considering a version of this
construction that uses a continuous domain (instead of finite) and a function
class consisting of functions that are unions of intervals (instead of
points).

Before we prove Subsection 1.2, it will be convenient to introduce the
following notation. For a positive integer $d$ and non-empty set $A$, we
define $A_{\lfloor d\rfloor}$ to be the set consisting of the smallest $d$
elements of $A$ with respect to an ordering of the elements of $A$. The
ordering we use will be clarified when needed. We now prove Subsection 1.2.

$I_{1}$$I_{(2,2)}$

Figure 1:  An illustration of the partitioning of the interval $(0,1]$ for a
training sample consisting of $m=18$ points with $d=2$. The interval $(0,1]$
is partitioned into $4$ intervals $I_{1},\dots,I_{4}$. Each interval $I_{i}$
is further partitioned into the $4$ subintervals $I_{(i,1)},\dots,I_{(i,4)}$.
The red points correspond to the first half of the sample
$(X_{1},\dots,X_{9})$ and the blue points correspond to the second half of the
sample $(X_{10},\dots,X_{18})$. The yellow highlighted regions are the first
$d$ intervals $I_{2}$ and $I_{4}$ that contain no points from
$(X_{1},\dots,X_{9})$. The green highlighted regions are the first $d$
subintervals of $I_{2}$ and $I_{4}$ that contain no points from
$(X_{10},\dots,X_{18})$. The green intervals are added to the union of
intervals used by $\widehat{f}_{S}$ as their indices correspond to the set
$L_{1}(S)$.

###### Proof of Subsection 1.2.

Fix a sample size $n$ divisible by $6$ and positive integer $d\leq n$.
Throughout, we will assume any interval considered is left-open and right-
closed. A collection of intervals $I_{1},\dots,I_{t}\subseteq[0,1]$ can be
viewed as the binary function $f_{I_{1}\cup\dots\cup I_{t}}$ that satisfies
$f_{I_{1}\cup\dots\cup I_{t}}(x)=1$ if and only if there is an index $j$ such
that $x\in I_{j}$. We will consider the function class $\mathcal{F}$ that is
the collection of all functions corresponding to the union of at most $2d$
interval. It is not hard to show that this class has VC dimension $4d$. We
take $P$ to be the uniform distribution on the domain $[0,1]$ and choose the
target function $f^{\star}$ to be the $0$ function on the domain $[0,1]$.

We now describe the “bad” ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. For the remainder
of the proof, $C>0$ is a large universal constant that we will determine
below. For a training sample size $m$, we define three collections of sets:

  1. 1.

$\\{I_{i}(m):i\in[m_{1}]\\}$ is the unique partition of $(0,1]$ into
$m_{1}\coloneqq\lceil Cm/\ln\left(Cm/d\right)\rceil$ intervals of the same
length.

  2. 2.

$\\{I_{i,j}(m):i\in[m_{1}],j\in[m_{2}]\\}$ where, for a fixed $i$,
$\\{I_{i,j}(m):j\in[m_{2}]\\}$ is the unique partition of $I_{i}(m)$ into
$m_{2}\coloneqq\lceil
4Cm/\left(m_{1}\ln\left(\ln\left(Cm/d\right)\right)\right)\rceil$ intervals of
the same length.

  3. 3.

$\\{J_{i}(m):i\in m_{3}\\}$ is the unique partition of $(0,1]$ into
$m_{3}\coloneqq\lceil 2Cm/\ln\left(2Cm/d\right)\rceil$ intervals of the same
length.

Given a labelled training sample
$(S,f^{\star}(S))=((X_{1},0),\dots,(X_{m},0))$ as input, the ERM algorithm
$\widehat{f}$ constructs the function
$\widehat{f}_{S}=\widehat{f}(\cdot;(S,f^{\star}(S)))$ in the following
way:444This defines $\widehat{f}_{S}$ when $(S,f^{\star}(S))$ contains only
$0$ labels. On any $(S,f^{\star}(S))$ that contains a $1$ label we return an
arbitrary consistent function.

  1. 1.

For $i\in[m_{1}]$, $j\in[m_{2}]$, and $k\in[m_{3}]$ define the sets

$\displaystyle\tilde{I}_{i}(S)=\\{x_{1},\dots,x_{\lfloor m/2\rfloor}\\}\cap
I_{i}(m),$ $\displaystyle\tilde{I}_{(i,j)}(S)=\\{x_{\lfloor
m/2\rfloor+1},\dots,x_{m}\\}\cap I_{(i,j)}(m),$
$\displaystyle\tilde{J}_{k}(S)=\\{x_{1},\dots,x_{m}\\}\cap J_{k}(m).$

  2. 2.

Define the index sets

$\displaystyle
L_{1}(S)=\\{(i,j):i\in\\{i^{\prime}:\tilde{I}_{i^{\prime}}(S)=\emptyset\\}_{\lfloor
d\rfloor},\tilde{I}_{(i,j)}(S)=\emptyset\\}_{\lfloor d\rfloor},$
$\displaystyle L_{2}(S)=\\{k:\tilde{J}_{k}(S)=\emptyset\\}_{\lfloor
d\rfloor}.$

  3. 3.

Define the union of intervals

$I_{S}=\left(\bigcup_{(i,j)\in
L_{1}(S)}I_{i,j}(m)\right)\bigcup\left(\bigcup_{i\in
L_{2}(S)}J_{i}(m)\right).$

  4. 4.

Finally, define the function $\widehat{f}_{S}=f_{I_{S}}$.

Observe that $I_{S}$ is the union of at most $2d$ disjoint intervals, so
$\widehat{f}_{S}$ will always be in the class $\mathcal{F}$. Furthermore,
$\widehat{f}_{S}$ is always consistent with the sample $S$ by construction.
See Fig. 1 for an example of the resulting intervals considered by the set
$L_{1}(S)$. Let $m=n/3$. From now on we use $m_{1}$ and $m_{2}$ to denote the
number of intervals of the form $I_{i}(2m)$ and $I_{(i,j)}(2m)$ considered by
$\widehat{f}_{(S_{1},S_{2})}$ respectively. Consider the unions of intervals
$I_{S_{1}}$ and $I_{(S_{1},S_{2})}$ corresponding to the ERM functions
$\widehat{f}_{S_{1}}$ and $\widehat{f}_{(S_{1},S_{2})}$. The number $m$ is
divisible by $2$ from our choice of $n$, so it follows that
$J_{i}(m)=I_{i}(2m)$ and $\tilde{J}_{i}(S_{1})=\tilde{I}_{i}(S_{1},S_{2})$,
which implies
$L_{2}(S_{1})=\\{k:\tilde{I}_{k}((S_{1},S_{2}))=\emptyset\\}_{\lfloor
d\rfloor}$. Thus, $\widehat{f}_{S_{1}}$ and $\widehat{f}_{(S_{1},S_{2})}$
agree, and simultaneously err, on every subinterval $I_{(i,j)}(2m)$ with
$(i,j)\in L_{1}(S_{1},S_{2})$. Because $P$ is the uniform distribution and
every interval $I_{(i,j)}(2m)$ has length
$1/(m_{1}m_{2})=\Theta(\ln\left(\ln\left(n/d\right)\right)/n)$, it follows
that the error of the majority vote satisfies

$\operatorname{err}_{P}\left(\mathrm{Maj}\left(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}\right)\right)\geq\frac{|L_{1}(S_{1},S_{2})|}{m_{1}m_{2}}=\Omega\left(\frac{|L_{1}(S_{1},S_{2})|}{n}\ln\left(\ln\left(\frac{n}{d}\right)\right)\right).$

Thus, if $|L_{1}(S_{1},S_{2})|=d$, we have

$\operatorname{err}_{P}\left(\mathrm{Maj}\left(\widehat{f}_{S_{1}},\widehat{f}_{(S_{1},S_{2})},\widehat{f}_{(S_{1},S_{2},S_{3})}\right)\right)=\Omega\left(\frac{d}{n}\log\left(\log\left(\frac{n}{d}\right)\right)\right),$

so the claim of the theorem follows once we prove that

$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2m}}\left[|L_{1}(S_{1},S_{2})|=d\right]\geq 2/3.$

To this end, let $E_{1}=E_{1}(S_{1})$ be the event that $S_{1}$ satisfies
$|L_{2}(S_{1})|=d$ and let $E_{2}=E_{2}((S_{1},S_{2}))$ be the event that
$(S_{1},S_{2})$ satisfies $|L_{1}(S_{1},S_{2})|=d$. Using the law of total
probability we get,

$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n/3}}\left[|L_{1}(S_{1},S_{2})|=d\right]=\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2m}}\left[E_{2}\right]\geq\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2m}}\left[E_{2}\mid E_{1}\right]\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{m}}\left[E_{1}\right],$

so it suffices to prove that $\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2m}}\left[E_{2}\mid E_{1}\right]\geq\sqrt{2/3}$ and
$\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{m}}\left[E_{1}\right]\geq\sqrt{2/3}$. We omit the proof of the later
inequality since it is very similar to the proof of the former inequality.

When $E_{1}$ occurs, we have
$|L_{2}(S_{1})|=|\\{k:\tilde{J}_{k}(S_{1})=\emptyset\\}_{\lfloor
d\rfloor}|=|\\{k:\tilde{I}_{k}((S_{1},S_{2}))=\emptyset\\}_{\lfloor
d\rfloor}|=d$. So, showing that the event $E_{2}$ occurs conditioned on
$E_{1}$ is equivalent to showing that _at least_ $d$ subintervals in the
collection $\\{I_{(i,j)}:i\in L_{2}(S_{1}),j\in[m_{2}]\\}$ do not contain any
points from the sample $S_{2}$. Let $Y\sim Q$ be the random variable that
counts the number of points required to sample from $P$ until $m_{2}d-d$
subintervals in $\\{I_{(i,j)}:i\in L_{2}(S_{1}),j\in[m_{2}]\\}$ contain one of
the sampled points. Furthermore, let $Y_{t}\sim Q_{t}$ denote the random
variable that counts the number of trials required to cover $(t+1)$
subintervals given that we have covered $t$. Notice that $Y_{t}$ is a
geometric random variable with parameter
$p_{t}=\frac{m_{2}d-t}{m_{1}m_{2}}=\frac{d}{m_{1}}-\frac{t}{m_{1}m_{2}}$ and
$Y=\sum_{t=0}^{m_{2}d-d-1}Y_{t}$. It follows that

$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim P^{2m}}\left[E_{2}\mid
E_{1}\right]\geq\operatorname*{\mathbf{Pr}}_{Y\sim Q}\left[Y\geq
m\right]=\operatorname*{\mathbf{Pr}}_{Y_{t}\sim
Q_{t}}\left[\sum_{t=0}^{m_{2}d-d-1}Y_{t}\geq m\right].$

We can use a concentration inequality for sums of geometric random variables
together with some simple calculations to show that

$\operatorname*{\mathbf{Pr}}_{Y_{t}\sim
Q_{t}}\left[\sum_{t=0}^{m_{2}d-d-1}Y_{t}\geq m\right]\geq\sqrt{2/3},$ (8)

when $C$ is large enough. We defer these calculations to Appendix B. This
concludes the proof. ∎

##  4 High probability upper bound

In this section we prove our high-probability upper bound for the Majority-of-
Three algorithm which we now restate for convenience. See 1.1 In this section
it will be convenient to use the following notation: for a probability
distribution $P$ over $\mathcal{X}$ and set $R\subseteq\mathcal{X}$, we define
$P(R)=\operatorname*{\mathbf{Pr}}_{X\sim P}\left[X\in R\right]$. Subsection
1.1 is a consequence of the following technical lemma.

######  Lemma 4.1.

Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$ and target function
$f^{\star}\in\mathcal{F}$. Fix an ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. For any parameter
$\delta\in(0,1/2]$ it holds with probability at least $1-\delta$ over the
randomness of $S_{1},S_{2}\sim P^{n}$ that

$\underset{X\sim P}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]\leq
c\left(\frac{d}{n}\operatorname{Log}\left(\operatorname{Log}\left(\min\left\\{\frac{n}{d},\frac{1}{\delta}\right\\}\right)\right)+\frac{1}{n}\operatorname{Log}\left(\frac{1}{\delta}\right)\right),$

where $c$ is a universal constant.

We now prove Subsection 1.1 using Lemma 4.1 and postpone the proof of Lemma
4.1.

###### Proof of Subsection 1.1.

Since
$\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})(x)\not=f^{\star}(x)$
happens if and only if there exists two distinct indices $i,j\in[3]$ such that
$\widehat{f}_{S_{i}}(X)\neq f^{\star}(X)$ _and_ $\widehat{f}_{S_{j}}(X)\neq
f^{\star}(X)$, we get that

$\displaystyle\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)\leq\sum_{\begin{subarray}{c}i,j\in[3]\\\
i<j\end{subarray}}\underset{X\sim
P}{\operatorname{Pr}}\left[\widehat{f}_{S_{i}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{j}}(X)\neq f^{\star}(X)\right].$

Using Lemma 4.1 with confidence parameter $\delta/3$ for every distinct pair
$i,j\in[3]$ together with a union bound gives us, with probability at least
$1-\delta$ over the randomness of $(S_{1},S_{2},S_{3})$, that

$\displaystyle\operatorname{err}_{P}\left(\mathrm{Maj}(\widehat{f}_{S_{1}},\widehat{f}_{S_{2}},\widehat{f}_{S_{3}})\right)=O\left(\frac{d}{n}\operatorname{Log}\left(\operatorname{Log}\left(\min\left\\{\frac{n}{d},\frac{1}{\delta}\right\\}\right)\right)+\frac{1}{n}\operatorname{Log}\left(\frac{1}{\delta}\right)\right).$

This concludes the proof. ∎

Before we prove Lemma 4.1, we provide a short overview of the proof. Our first
step is to reuse the idea from Section 2 to partition the instance space
$\mathcal{X}$ into sets $\\{R_{i}\\}_{i\in\mathbb{N}}$ based on the chance
that an average ERM errs on a point in $x\in\mathcal{X}$. However, we use a
different way to quantify the errors defining $R_{i}$ by incorperating the
failure parameter $\delta$. For $i\geq 2$, we can actually reuse our in-
expectation analysis from Section 2 together with a simple application of
Markov’s inequality and a sequence of union bounds. This gives us an upper
bound on the joint error of two ERMs on the conditional distributions for all
$\\{R_{i}\\}_{i\geq 2}$, with high probability. The major technical work of
the proof lies in controlling the joint error of two ERMs on the conditional
distribution of $R_{1}$. To do this, we borrow an idea from Simon [16] that
views the probability of $\widehat{f}_{S_{1}}$ and $\widehat{f}_{S_{2}}$
jointly erring as the probability that $\widehat{f}_{S_{1}}$ errs times the
probability that $\widehat{f}_{S_{2}}$ errs conditioned on
$\widehat{f}_{S_{1}}$ erring.666This idea used by Simon in fact builds upon
even earlier work of Hanneke [8] in the context of active learning. It was
also applied in the context of PAC learning by Darnstädt [7]. A crucial
technicality that differentiates our setting from Simon’s is that the
probability that $\widehat{f}_{S_{1}}$ and $\widehat{f}_{S_{2}}$ jointly err
is taken over a _conditional distribution_ $P_{R}$ rather than the
distribution $P$ from which the samples $S_{1}$ and $S_{2}$ are drawn.

The following lemma formalizes how we can control the joint error of two ERMs
under $P_{R}$.

######  Lemma 4.2.

Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$, target function
$f^{\star}\in\mathcal{F}$ and $R\subseteq\mathcal{X}$ such that $P(R)\not=0$.
Fix an ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. For any parameter
$\delta\in(0,1/2]$ it holds with probability at least $1-\delta$ over the
randomness of $S_{1},S_{2}\sim P^{n}$ that

$\displaystyle\underset{X\sim
P_{R}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]\leq
8\max\left\\{\frac{d\operatorname{Log}(8e\operatorname{Log}(eP\left(R\right)n/d))}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}.$

We now prove Lemma 4.1 using Lemma 4.2 and postpone the proof of Lemma 4.2.

###### Proof of Lemma 4.1.

We use the same definition for $p_{x}$ (see Section 2) but redefine the sets
$\\{R_{i}\\}_{i\in\mathbb{N}}$ to be

$R_{1}=\left\\{x\in\mathcal{X}:p_{x}\in(2^{-1}\delta/\operatorname{Log}(1/\delta),1]\right\\},$

and for any integer $i\geq 2$,

$R_{i}=\left\\{x\in\mathcal{X}:p_{x}\in\left(2^{-i}\delta/\operatorname{Log}(1/\delta),2^{-i+1}\delta/\operatorname{Log}(1/\delta)\right]\right\\}.$

Using the law of total probability we have

$\displaystyle\operatorname*{\mathbf{Pr}}_{X\sim
P}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]$
$\displaystyle=P\left(R_{1}\right)\underset{X\sim
P_{R_{1}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]$
$\displaystyle\quad+\sum_{i=2}^{\infty}P\left(R_{i}\right)\underset{X\sim
P_{R_{i}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right].$

We will prove that there is a universal constant $c>0$ such that the events

$\displaystyle
E_{1}=E_{1}((S_{1},S_{2}))\coloneqq\Bigg{\\{}P\left(R_{1}\right)\underset{X\sim
P_{R_{1}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]\leq$
$\displaystyle
c\max\left\\{\frac{d\operatorname{Log}(\operatorname{Log}(\min\\{n/d,1/\delta\\}))}{n},\frac{\operatorname{Log}(1/\delta)}{n}\right\\}\Bigg{\\}},$

and

$\displaystyle
E_{2}=E_{2}((S_{1},S_{2}))\coloneqq\left\\{\sum_{i=2}^{\infty}P\left(R_{i}\right)\underset{X\sim
P_{R_{i}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]\leq
c\frac{d}{n}\right\\}$

each happen with probability at least $1-\delta/2$ over the randomness of
$(S_{1},S_{2})$. The claim of Lemma 4.1 then follows from a union bound.
Define the set $I=\\{i\geq 2:P(R_{i})\not=0\\}$. To prove that $E_{1}$ and
$E_{2}$ each occur with high probability, we will use the following
proposition. [] In the setting of Lemma 4.1 we have the following:

  1. 1.

There is a universal constant $c^{\prime}$ such that for any $i\in\mathbb{N}$

$\displaystyle
P\left(R_{i}\right)\leq\frac{c^{\prime}2^{i}d\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}{\delta
n}.$

  2. 2.

With probability at least $1-\delta/2$ over the randomness of $(S_{1},S_{2})$
we have, simultaneously for all $i\in I=\\{i\geq 2:P(R_{i})\not=0\\}$, that

$\underset{X\sim P_{R_{i}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq
f^{\star}(X)\right]\leq\frac{5\cdot
2^{-1.1i}\delta}{\operatorname{Log}^{2}(1/\delta)}.$

We defer the proof of Section 4 to Subsection A.2 as its proof is similar to
that of Lemma 2.1.

We first prove that the event $E_{1}$ occurs with high probability. If
$P(R_{1})=0$, then we immediately have that
$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})}[E_{1}]=1$. We now consider the
case that $P(R_{1})\not=0$. From Item 1 of Section 4 we can conclude there is
a universal constant $\tilde{c}$ such that
$P\left(R_{1}\right)\leq\min\\{1,\tilde{c}\frac{d\operatorname{Log}^{2}(1/\delta)}{\delta
n}\\}$. Using this combined with Lemma 4.2 we have, with probability at least
$1-\delta/2$ over the randomness of $(S_{1},S_{2})$, that

$\displaystyle P\left(R_{1}\right)\underset{X\sim
P_{R_{1}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]$
$\displaystyle\leq
8\max\left\\{\frac{d\operatorname{Log}(8e\operatorname{Log}(\min\\{en/d,e\tilde{c}\operatorname{Log}^{2}(1/\delta)/\delta\\}))}{n},\frac{\operatorname{Log}(16/\delta)}{n}\right\\}$
$\displaystyle\leq
c\max\left\\{\frac{d\operatorname{Log}(\operatorname{Log}(\min\\{n/d,1/\delta\\}))}{n},\frac{\operatorname{Log}(1/\delta)}{n}\right\\},$

where the last inequality holds for $c$ large enough.

We now prove that the event $E_{2}$ occurs with high probability. Combining
Items 1 and 2 of Section 4 we have, with probability at least $1-\delta/2$
over the randomness of $(S_{1},S_{2})$, that

$\displaystyle\sum_{i=2}^{\infty}$ $\displaystyle
P\left(R_{i}\right)\underset{X\sim
P_{R_{i}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]$
$\displaystyle\leq\sum_{i\not\in I}0+\sum_{i\in
I}\frac{2^{i}c^{\prime}d\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}{\delta
n}\cdot\frac{5\cdot 2^{-1.1i}\delta}{\operatorname{Log}^{2}(1/\delta)}$
$\displaystyle\leq\frac{5c^{\prime}d}{n}\sum_{i=2}^{\infty}\frac{2^{-0.1i}\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)}{\operatorname{Log}(1/\delta)}$
$\displaystyle\leq\frac{5c^{\prime}d}{n}\sum_{i=2}^{\infty}\frac{2^{-0.1i}\cdot\left(i\operatorname{Log}(2)+\operatorname{Log}(\operatorname{Log}(1/\delta))+\operatorname{Log}(1/\delta)\right)}{\operatorname{Log}(1/\delta)}$
$\displaystyle\leq c\frac{d}{n},$

where the last inequality holds for $c$ large enough. This concludes the
proof. ∎

We now move on to prove Lemma 4.2. To do so, we will need the following lemma
which is a simple consequence of uniform convergence. We defer the proof of
this lemma to Subsection A.3. [] Fix a function class
$\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC dimension $d$. Fix a
distribution $P$ over $\mathcal{X}$, target function
$f^{\star}\in\mathcal{F}$, and $R\subseteq\mathcal{X}$ such that $P(R)\not=0$.
Fix an ERM algorithm
$\widehat{f}:\mathcal{X}\times\mathcal{Z}^{*}\to\\{0,1\\}$. For any parameter
$\delta\in(0,1/2]$ it holds with probability at least $1-\delta$ over the
randomness of $S\sim P^{n}$ that

$\displaystyle\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\leq
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)n/d)}{P\left(R\right)n},\frac{\operatorname{Log}(4/\delta)}{P\left(R\right)n}\right\\}.$

We are now ready to prove Lemma 4.2.

###### Proof of Lemma 4.2.

We will prove that the event

$\displaystyle E$ $\displaystyle=E((S_{1},S_{2}))$
$\displaystyle\coloneqq\left\\{\underset{X\sim
P_{R}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]\leq
8\max\left\\{\frac{d\operatorname{Log}(8e\operatorname{Log}(eP\left(R\right)n/d))}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}\right\\}$

occurs with high probability. Let $B_{1}$ denote the (random) set
$\\{x\in\mathcal{X}:\widehat{f}_{S_{1}}(x)\not=f^{\star}(x)\\}$ and define the
event $E_{1}=E_{1}(S_{1})\coloneqq\\{P(R\cap B_{1})\not=0\\}$. By the law of
total probability, we have

$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[E\right]=\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[E_{1}\cap E\right]+\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[\bar{E}_{1}\cap E\right].$ (9)

Furthermore, we can write the second term on the right hand side of Eq. 9 as

$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim P^{2n}}\left[\bar{E}_{1}\cap
E\right]=\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[E\mid\bar{E}_{1}\right]\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[\bar{E}_{1}\right]=\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[\bar{E}_{1}\right].$

Combining the identities above, it suffices to show that

$\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[E\cap{E}_{1}\right]\geq\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[{E}_{1}\right]-\delta.$

Notice that when $E_{1}$ occurs, then for any measurable set
$C\subseteq\mathcal{X}$, the distribution $(P_{R})_{B_{1}}$ (which is the
conditional distribution of $P_{R}$ restricted to $B_{1}$) satisfies

$(P_{R})_{B_{1}}(C)=\frac{P_{R}\left(C\cap
B_{1}\right)}{P_{R}\left(B_{1}\right)}=\frac{P\left(C\cap B_{1}\cap
R\right)}{P\left(B_{1}\cap R\right)}=P_{R\cap B_{1}}\left(C\right),$

i.e., $(P_{R})_{B_{1}}=P_{R\cap B_{1}}$. Thus on $E_{1}$, the probability that
both $\widehat{f}_{S_{1}}$ and $\widehat{f}_{S_{2}}$ simultaneously err on a
new data point drawn from $P_{R}$ can be written as

$\displaystyle\underset{X\sim
P_{R}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq
f^{\star}(X)\right]=\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)\operatorname{err}_{P_{R\cap
B_{1}}}\left(\widehat{f}_{S_{2}}\right).$ (10)

We now bound the right side of Eq. 10. To do this, we define the following
events over $(S_{1},S_{2})$:

$\displaystyle
E_{2}=E_{2}(S_{1})\coloneqq\left\\{\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)\leq
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)n/d)}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}\right\\}$

and for outcomes of $S_{1}$ in $E_{1}$

$\displaystyle E_{3}$ $\displaystyle=E_{3}((S_{1},S_{2}))$
$\displaystyle\coloneqq\left\\{\operatorname{err}_{P_{R\cap
B_{1}}}\left(\widehat{f}_{S_{2}}\right)\leq
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)n\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)/d)}{P\left(R\right)n\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)}\right\\}\right\\}.$

We now show that the event $E_{1}\cap E_{2}\cap E_{3}$ happens with
probability at least $P[E_{1}]-\delta$ and that it implies the event
$E_{1}\cap E$. Assume that $E_{1}\cap E_{2}\cap E_{3}$ occurs. If

$\displaystyle
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)n/d)}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}=8\frac{d\operatorname{Log}(eP\left(R\right)n/d)}{P\left(R\right)n},$

we have

$\displaystyle\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)\operatorname{err}_{P_{R\cap
B_{1}}}\left(\widehat{f}_{S_{2}}\right)$ $\displaystyle\leq
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)n\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)/d)}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}$
$\displaystyle\leq
8\max\left\\{\frac{d\operatorname{Log}(8e\operatorname{Log}(eP\left(R\right)n/d))}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}.$

Otherwise, if

$\displaystyle
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)n/d)}{P\left(R\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\right\\}=8\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n},$

we have

$\displaystyle\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)\operatorname{err}_{P_{R\cap
B_{1}}}\left(\widehat{f}_{S_{2}}\right)$ $\displaystyle\leq
8\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)n}\cdot 1.$

We can thus conclude that $E_{1}\cap E_{2}\cap E_{3}$ implies $E_{1}\cap E$.
Towards showing the bound $\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[E_{1}\cap E_{2}\cap E_{3}\right]\geq P[E_{1}]-\delta$, notice
that the bound $\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[\bar{E}_{2}\right]\leq\delta/2$ can be established from Lemma 4.2
directly. Furthermore, for _any fixed realization_ of $S_{1}$ such that
$P(R\cap B_{1})\not=0$, Lemma 4.2 implies that

$\operatorname{err}_{P_{R\cap B_{1}}}\left(\widehat{f}_{S_{2}}\right)\leq
8\max\left\\{\frac{d\operatorname{Log}(eP\left(R\right)\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)n/d)}{P\left(R\right)\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)n},\frac{\operatorname{Log}(8/\delta)}{P\left(R\right)\operatorname{err}_{P_{R}}\left(\widehat{f}_{S_{1}}\right)n}\right\\},$

with probability at least $1-\delta/2$ over the randomness of $S_{2}$. Using
the independence of $S_{1}$ and $S_{2}$ we have

$\displaystyle\operatorname*{\mathbf{Pr}}_{(S_{1},S_{2})\sim
P^{2n}}\left[E_{1}\cap E_{2}\cap E_{3}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S_{1}\sim
P^{n}}\left[\mathbf{1}_{E_{1}}\mathbf{1}_{E_{2}}\operatorname*{\mathbf{Pr}}_{S_{2}\sim
P^{n}}\left[E_{3}\right]\right]$
$\displaystyle\geq\operatorname*{\mathbb{E}}_{S_{1}\sim
P^{n}}\left[\mathbf{1}_{E_{1}}\mathbf{1}_{E_{2}}\right](1-\delta/2)$
$\displaystyle\geq(1-\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{n}}\left[\bar{E}_{1}\right]-\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{n}}\left[\bar{E}_{2}\right])(1-\delta/2)$
$\displaystyle\geq(\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{n}}\left[E_{1}\right]-\delta/2)(1-\delta/2)$
$\displaystyle\geq\operatorname*{\mathbf{Pr}}_{S_{1}\sim
P^{n}}\left[E_{1}\right]-\delta.$

This completes the proof. ∎

## References

  * [1] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy.  The one-inclusion graph algorithm is not always optimal.  In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume 195 of Proceedings of Machine Learning Research, pages 72–88. PMLR, 2023.
  * [2] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy.  Optimal PAC bounds without uniform convergence.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203–1223. IEEE Computer Society, 2023.
  * AO [07] Peter Auer and Ronald Ortner.  A new PAC bound for intersection-closed concept classes.  Machine Learning, 66(2):151–163, 2007.
  * BEHW [89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the Vapnik-Chervonenkis dimension.  Journal of the ACM, 36(4):929–965, 1989.
  * BHMZ [20] Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy.  Proper learning, Helly number, and an optimal SVM bound.  In Conference on Learning Theory, pages 582–609. PMLR, 2020.
  * Bre [96] Leo Breiman.  Bagging predictors.  Mach. Learn., 24(2):123–140, aug 1996.
  * Dar [15] Malte Darnstädt.  The optimal PAC bound for intersection-closed concept classes.  Information Processing Letters, 115(4):458–461, 2015.
  * Han [09] Steve Hanneke.  Theoretical Foundations of Active Learning.  Doctoral thesis, Carnegie-Mellon University, Machine Learning Department, 2009.
  * [9] Steve Hanneke.  The optimal sample complexity of PAC learning.  The Journal of Machine Learning Research, 17(1):1319–1333, 2016\.
  * [10] Steve Hanneke.  Refined error bounds for several learning algorithms.  The Journal of Machine Learning Research, 17(1):4667–4721, 2016\.
  * HLW [94] David Haussler, Nick Littlestone, and Manfred K Warmuth.  Predicting $\\{$0, 1$\\}$-functions on randomly drawn points.  Information and Computation, 115(2):248–292, 1994.
  * Jan [18] Svante Janson.  Tail bounds for sums of geometric and exponential variables.  Statistics and Probability Letters, 135:1–6, 2018.
  * Lar [23] Kasper Green Larsen.  Bagging is an optimal PAC learner.  In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume 195 of Proceedings of Machine Learning Research, pages 450–468. PMLR, 2023.
  * LLS [01] Yi Li, Philip M Long, and Aravind Srinivasan.  The one-inclusion graph algorithm is near-optimal for the prediction model of learning.  IEEE Transactions on Information Theory, 47(3):1257–1261, 2001\.
  * Sch [92] Robert E. Schapire.  The Design and Analysis of Efficient Learning Algorithms.  ACM Doctoral Dissertation Awards. The MIT Press, 1992.
  * Sim [15] Hans U Simon.  An almost optimal PAC algorithm.  In Conference on Learning Theory, pages 1552–1563. PMLR, 2015.
  * Val [84] Leslie G Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * VC [64] Vladimir Vapnik and Alexey Chervonenkis.  A class of algorithms for pattern recognition learning.  Avtomatika i Telemekhanika, 25(6):937–945, 1964.
  * VC [68] Vladimir Vapnik and Alexey Chervonenkis.  Algorithms with complete memory and recurrent algorithms in the problem of learning pattern recognition.  Avtomatika i Telemekhanika, pages 95–106, 1968.
  * VC [71] Vladimir Vapnik and Alexey Chervonenkis.  On uniform convergence of the frequencies of events to their probabilities.  Teoriya Veroyatnostei i ee Primeneniya, 16(2):264–279, 1971.
  * VC [74] Vladimir Vapnik and Alexey Chervonenkis.  Theory of Pattern Recognition.  Nauka, Moscow, 1974.
  * War [04] Manfred K Warmuth.  The optimal PAC algorithm.  In International Conference on Computational Learning Theory, pages 641–642. Springer, 2004.

##  Appendix A Ommited proofs from Sections 2 and 4

In this appendix we prove Lemma 2.1, Section 4, and Lemma 4.2. These results
are by-products of the classic _uniform convergence_ result which uniformly
bounds the error of any function in $\mathcal{F}$ that is consistent with the
training sample. To state the result, we first introduce some notation. For a
training sample $S=((X_{1},f^{\star}(X_{1})),\dots,(X_{n},f^{\star}(X_{n})))$,
let $\mathcal{F}_{S}$ denote the functions in $\mathcal{F}$ that are
consistent with $S$, i.e., $f\in\mathcal{F}_{S}$ if and only if
$f(X_{i})=f^{\star}(X_{i})$ for every $i\in[n]$.

######  Lemma A.1 (Uniform convergence [4]).

Fix a function class $\mathcal{F}\subseteq\\{0,1\\}^{\mathcal{X}}$ with VC
dimension $d$. Fix a distribution $P$ over $\mathcal{X}$ and target function
$f^{\star}\in\mathcal{F}$. For any parameter $\delta\in(0,1/2]$ it holds with
probability at least $1-\delta$ over $S\sim P^{n}$ that

$\sup_{f\in\mathcal{F}_{S}}\operatorname{err}_{P}\left(f\right)\leq
2\left(\frac{d\log(2en/d)+\log(2/\delta)}{n}\right).$

In what follows, we will use the slightly weaker bound

$\displaystyle\sup_{f\in\mathcal{F}_{S}}\operatorname{err}_{P}\left(f\right)\leq
4\max\left\\{\frac{d\operatorname{Log}(2en/d)}{n},\frac{\operatorname{Log}(2/\delta)}{n}\right\\}.$
(11)

###  A.1 Proof of Lemma 2.1

We now prove Lemma 2.1 which we restate here for convenience. See 2.1

###### Proof.

Consider the case that $\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n\leq
4d$. In this case the claim follows easily since
$\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\leq 1$ and
$x\rightarrow\operatorname{Log}(ex)/x$ is decreasing in $x$ for $x>0$, so
$20\frac{d\operatorname{Log}(e\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in
R]n/d)}{\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n}>1$. We now consider
the case that $\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n>4d$. For any
$m\in\mathbb{N}$ we define the event $E_{m}=E_{m}(S)=\\{|\\{i\in[n]:X_{i}\in
R\\}|=m\\}$. Similarly, we define the event

$E=E(S)=\bigcup\limits_{m\geq\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in
R]n/2}E_{m}.$

It follows from a Chernoff bound and our assumption that
$\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n>4d$ that

$\operatorname*{\mathbf{Pr}}_{S\sim P^{n}}[E]\geq
1-\exp\left(-\frac{\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in
R]n}{8}\right)\geq 1-\frac{8}{\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in
R]n}.$

Using the law of total probability we have

$\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\right]\leq\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\;\middle|\;E\right]+\frac{8}{\operatorname*{\mathbf{Pr}}_{X\sim
P}[X\in R]n}.$ (12)

So, if we show that for any $m\geq\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in
R]n/2$ that

$\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\;\middle|\;E_{m}\right]\leq\frac{12d\operatorname{Log}\left(e\operatorname*{\mathbf{Pr}}_{X\sim
P}[X\in R]n/d\right)}{\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n},$ (13)

the claim follows from one more application of the law of total probability
applied to the first term on the right hand side of Eq. 12.

We now prove Eq. 13. Using the non-negativity of
$\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)$ we have

$\displaystyle\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\;\middle|\;E_{m}\right]$
$\displaystyle=\int_{0}^{\infty}\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)>x\;\middle|\;E_{m}\right]dx$
$\displaystyle\leq\frac{4d\operatorname{Log}\left(2em/d\right)}{m}+\int_{\frac{4d\operatorname{Log}\left(2em/d\right)}{m}}^{1}\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)>x\;\middle|\;E_{m}\right]dx.$
(14)

Notice that conditioned on $E_{m}$, the $m$ samples that land in $R$ form an
i.i.d. sample from the conditional distribution $P_{R}$. Thus, any ERM trained
on $S$ is also consistent with $m$ i.i.d. samples from $P_{R}$, so we can
apply uniform convergence (Lemma A.1) to control the error of any ERM when
measured with respect to the conditional distribution $P_{R}$. Setting
$\delta=2^{1-\frac{mx}{4}}$ we have

$\displaystyle\int_{\frac{4d\operatorname{Log}\left(2em/d\right)}{m}}^{1}\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)>x\;\middle|\;E_{m}\right]dx$
$\displaystyle=\int_{\frac{4d\operatorname{Log}\left(2em/d\right)}{m}}^{1}\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)>\frac{4\operatorname{Log}(2/\delta)}{m}\;\middle|\;E_{m}\right]dx$
$\displaystyle\leq
2\int_{\frac{4d\operatorname{Log}\left(2em/d\right)}{m}}^{1}2^{-\frac{mx}{4}}dx$
$\displaystyle\leq 2\left(\frac{4\cdot
2^{-d\operatorname{Log}\left(2em/d\right)}}{m\ln(2)}\right)\leq\frac{2d\operatorname{Log}\left(2em/d\right)}{m}.$

Here, the first equality follows from the fact that
$m\geq\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n/2\geq 2d$ and our choice
of $\delta$. The second inequality follows from Eq. 11 and the final
inequality follows from the fact that $d\operatorname{Log}(2em/d)\geq 2$. Now,
using the fact that $x\rightarrow\operatorname{Log}(2ex)/x$ is decreasing for
$x>0$ together with the fact that $m\geq\operatorname*{\mathbf{Pr}}_{X\sim
P}[X\in R]n/2\geq 2d$, we conclude

$\operatorname*{\mathbb{E}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)\;\middle|\;E_{m}\right]\leq\frac{6d\operatorname{Log}\left(2em/d\right)}{m}<\frac{12d\operatorname{Log}\left(e\operatorname*{\mathbf{Pr}}_{X\sim
P}[X\in R]n/d\right)}{\operatorname*{\mathbf{Pr}}_{X\sim P}[X\in R]n},$

as claimed. ∎

###  A.2 Proof of Section 4

We now prove Section 4 which we restate here for convenience. See 4

###### Proof.

We first prove Item 1. Towards a contradiction, assume that there is an
$i\in\mathbb{N}$ such that

$\frac{P\left(R_{i}\right)n}{d}\geq\frac{c^{\prime}2^{i}\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}{\delta}$

for a constant $c^{\prime}$ that we will choose below. By changing the order
of expectations we have

$\underset{S_{1}\sim
P^{n}}{\mathbb{E}}\left[\operatorname{err}_{P_{R_{i}}}\left(\widehat{f}_{S_{1}}\right)\right]=\underset{X\sim
P_{R_{i}}}{\mathbb{E}}\left[\underset{S_{1}\sim
P^{n}}{\mathbf{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\right]\right]=\underset{X\sim
P_{R_{i}}}{\mathbb{E}}\left[p_{X}\right].$

Using the above together with the fact that $p_{X}\geq
2^{-i}\delta/\operatorname{Log}(1/\delta)$ for any $X\in R_{i}$, we can
conclude that

$\displaystyle\underset{S_{1}\sim
P^{n}}{\mathbb{E}}\left[\operatorname{err}_{P_{R_{i}}}\left(\widehat{f}_{S_{1}}\right)\right]>\frac{\delta}{2^{i}\operatorname{Log}(1/\delta)}.$
(15)

On the other hand, using Lemma 2.1 we conclude that there is a universal
constant $\hat{c}$ such that

$\displaystyle\underset{S_{1}\sim
P^{n}}{\mathbb{E}}\left[\operatorname{err}_{P_{R_{i}}}\left(\widehat{f}_{S_{1}}\right)\right]\leq\hat{c}\frac{d\operatorname{Log}\left(P\left(R_{i}\right)n/d\right)}{P\left(R_{i}\right)n}.$

Combining this inequality with the fact that $\operatorname{Log}(x)/x$ is a
decreasing function for $x>0$, we have

$\displaystyle\underset{S_{1}\sim
P^{n}}{\mathbb{E}}\left[\operatorname{err}_{P_{R_{i}}}\left(\widehat{f}_{S_{1}}\right)\right]\leq\hat{c}\frac{\delta\operatorname{Log}\left(\frac{c^{\prime}2^{i}\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}{\delta}\right)}{c^{\prime}2^{i}\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}$
$\displaystyle=\hat{c}\frac{2^{-i}\delta}{\operatorname{Log}(1/\delta)}\cdot\frac{\operatorname{Log}\left(\frac{c^{\prime}2^{i}\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}{\delta}\right)}{c^{\prime}\operatorname{Log}\left(\frac{2^{i}\operatorname{Log}(1/\delta)}{\delta}\right)}$
$\displaystyle\leq\hat{c}\frac{2^{-i}\delta}{\operatorname{Log}(1/\delta)}\cdot\frac{\operatorname{Log}\left(c^{\prime}\right)+\operatorname{Log}\left(\operatorname{Log}\left(\frac{2^{i}\operatorname{Log}(1/\delta)}{\delta}\right)\right)+\operatorname{Log}\left(2^{i}\frac{\operatorname{Log}(1/\delta)}{\delta}\right)}{c^{\prime}\operatorname{Log}\left(\frac{2^{i}\operatorname{Log}(1/\delta)}{\delta}\right)}.$

However, for $c^{\prime}$ large enough, the above is less than
$2^{-i}\delta/\operatorname{Log}(1/\delta)$ which contradicts the lower bound
Eq. 15. Thus, we have shown that there is a constant $c^{\prime}$ such that

$\displaystyle\frac{P\left(R_{i}\right)n}{d}\leq\frac{c^{\prime}2^{i}\operatorname{Log}(2^{i}\operatorname{Log}(1/\delta)/\delta)\operatorname{Log}(1/\delta)}{\delta},$

which proves Item 1.

We now prove Item 2. We will show that for each $i\in I$ with probability at
least $1-2^{-0.9i+2}\delta/5$ we have

$\underset{X\sim P_{R_{i}}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq
f^{\star}(X)\right]\leq\frac{5\cdot
2^{-1.1i}\delta}{\operatorname{Log}^{2}(1/\delta)}.$ (16)

Applying a union bound implies that the above holds simultaneously for every
$i\in I$ with probability at least $1-\sum_{i\geq 2}2^{-0.9i+2}\delta/5\geq
1-\delta/2$. To see that Eq. 16 holds for each $i\in I$, notice that we can
use the fact that $S_{1}$ and $S_{2}$ are i.i.d. samples together with the
fact that $p_{X}\leq 2^{-i+1}\delta/\operatorname{Log}(1/\delta)$ for $X\in
R_{i}$ to conclude that

$\underset{X\sim P_{R_{i}}}{\mathbb{E}}\left[\underset{S_{1},S_{2}\sim
P^{n}}{\operatorname{Pr}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq
f^{\star}(X)\right]\right]=\underset{X\sim
P_{R_{i}}}{\mathbb{E}}p_{X}^{2}\leq\frac{2^{-2i+2}\delta^{2}}{\operatorname{Log}^{2}(1/\delta)}.$

Combining this with Markov’s inequality we have

$\displaystyle\underset{S_{1},S_{2}\sim
P^{n}}{\operatorname{Pr}}\left[\operatorname{Pr}_{X\sim
P_{R_{i}}}\left[\widehat{f}_{S_{1}}(X)\neq
f^{\star}(X)\wedge\widehat{f}_{S_{2}}(X)\neq f^{\star}(X)\right]>\frac{5\cdot
2^{-1.1i}\delta}{\operatorname{Log}^{2}(1/\delta)}\right]$
$\displaystyle\leq\frac{2^{-2i+2}\delta^{2}}{\operatorname{Log}^{2}(1/\delta)}\frac{\operatorname{Log}^{2}(1/\delta)}{5\cdot
2^{-1.1i}\delta}=2^{-0.9i+2}\delta/5,$

which proves the claim. ∎

###  A.3 Proof of Lemma 4.2

We now prove Lemma 4.2 which we restate here for convenience. See 4.2

###### Proof.

If $8\operatorname{Log}(4/\delta)/(P(R)n)\geq 1$ we are done as
$\operatorname{err}_{P_{R}}\left(f\right)\leq 1$. Thus, for the remainder of
the proof we will assume that $8\operatorname{Log}(4/\delta)/(P(R)n)<1$, which
is equivalent to $P(R)n\geq 8\operatorname{Log}(4/\delta)$. Define the event

$E=E(S)=\\{|\\{i\in[n]:X_{i}\in R\\}|\geq P(R)n/2\\}.$

Using the Chernoff bound and our assumption that $P(R)n\geq
8\operatorname{Log}(4/\delta)$, we have

$\operatorname*{\mathbf{Pr}}_{S\sim P^{n}}\left[E\right]\geq
1-\exp\left(-\frac{P(R)n}{8}\right)\geq 1-\delta/2.$

Notice that conditioned on $E$, the $M\geq P(R)n/2\geq 1$ samples777The number
of samples $M$ is random. that land in $R$ form an i.i.d. sample from the
conditional distribution $P_{R}$. Thus when $E$ occurs, any ERM trained on $S$
is also consistent with $M\geq P(R)n/2\geq 1$ i.i.d. samples from $P_{R}$, so
Lemma A.1 yields, with probability at least $1-\delta/2$ over the randomness
of $S$, that

$\displaystyle\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)$
$\displaystyle\leq
4\max\left\\{\frac{d\operatorname{Log}(2eM/d)}{M},\frac{\operatorname{Log}(4/\delta)}{M}\right\\}$
$\displaystyle\leq
8\max\left\\{\frac{d\operatorname{Log}(eP(R)n/d)}{P(R)n},\frac{\operatorname{Log}(4/\delta)}{P(R)n}\right\\}.$

Here, the second inequality follows from the fact that
$x\rightarrow\operatorname{Log}(2ex)/x$ is decreasing for $x>0$. Using the law
of total probability we get that

$\displaystyle\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)>8\max\left\\{\frac{d\operatorname{Log}(eP(R)n/d)}{P(R)n},\frac{\operatorname{Log}(4/\delta)}{P(R)n}\right\\}\right]$
$\displaystyle\leq\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\bar{E}\right]+\operatorname*{\mathbf{Pr}}_{S\sim
P^{n}}\left[\operatorname{err}_{P_{R}}\left(\widehat{f}_{S}\right)>8\max\left\\{\frac{d\operatorname{Log}(eP(R)n/d)}{P(R)n},\frac{\operatorname{Log}(4/\delta)}{P(R)n}\right\\}\;\middle|\;E\right]$
$\displaystyle\leq\delta/2+\delta/2=\delta.$

This concludes the proof. ∎

##  Appendix B Ommited proofs from Section 3

In this appendix we prove Eq. 8. We will show that

$\operatorname*{\mathbf{Pr}}_{Y\sim Q}\left[Y\geq
m\right]=\operatorname*{\mathbf{Pr}}_{Y_{t}\sim
Q_{t}}\left[\sum_{t=0}^{m_{2}d-d-1}Y_{t}\geq m\right]\geq\sqrt{\frac{2}{3}}.$

Let $p^{\star}=p_{m_{2}d-d-1}=\frac{d+1}{m_{1}m_{2}}$ be the smallest
parameter $p_{t}$ of the geometric random variables
$\\{Y_{t}\\}_{t=0}^{m_{2}d-d-1}$ that we consider. We make use of the
following well known concentration inequality for sums of geometric random
variables:

$\operatorname*{\mathbf{Pr}}_{Y\sim
Q}\left[Y\leq\lambda\operatorname*{\mathbb{E}}_{Y\sim
Q}\left[Y\right]\right]\leq\exp\left(-p^{\star}\operatorname*{\mathbb{E}}_{Y\sim
Q}[Y](\lambda-1-\ln(\lambda))\right),$ (17)

which holds for any $0<\lambda\leq 1$ (see [12, Theorem 3.1]). Let
$\lambda=1/4$. We will show $\operatorname*{\mathbb{E}}_{Y\sim
Q}\left[Y\right]\geq 4m$ and $p^{\star}\operatorname*{\mathbb{E}}_{Y\sim
Q}\left[Y\right]\geq 4$ which combined with $1/4-1-\ln\left(1/4\right)\geq
1/2$ and Eq. 17 gives us

$\displaystyle\operatorname*{\mathbf{Pr}}_{Y\sim Q}\left[Y\leq
m\right]\leq\operatorname*{\mathbf{Pr}}_{Y\sim
Q}\left[Y\leq\operatorname*{\mathbb{E}}_{Y\sim
Q}[Y]/4\right]\leq\exp\left(-p^{\star}\operatorname*{\mathbb{E}}_{Y\sim
Q}\left[Y\right]/2\right)\leq\exp(-2)\leq 1-\sqrt{2/3}.$

This implies $\operatorname*{\mathbf{Pr}}_{Y\sim Q}\left[Y\geq
m\right]\geq\sqrt{2/3}$ as required. We first show that
$\operatorname*{\mathbb{E}}_{Y\sim Q}[Y]\geq 4m$. We have

$\displaystyle\operatorname*{\mathbb{E}}_{Y\sim
Q}[Y]=\sum_{t=0}^{m_{2}d-d-1}\frac{m_{1}m_{2}}{m_{2}d-t}=\sum_{i=d+1}^{m_{2}d}\frac{m_{1}m_{2}}{i}\geq
m_{1}m_{2}\ln\left(\frac{m_{2}}{2}\right).$ (18)

Plugging in the definition of $m_{1}$ and $m_{2}$ into Eq. 18 and using the
fact that $\lceil x\rceil\leq 2x$ for $x\geq 0.5$ gives us

$\operatorname*{\mathbb{E}}_{Y\sim
Q}[Y]\geq\frac{8Cm}{\ln\left(\ln\left(2Cm/d\right)\right)}\ln\left(\frac{\ln(2Cm/d)}{\ln\left(\ln\left(2Cm/d\right)\right)}\right).$

For $C$ large enough we have $\ln(\ln(2Cm/d))>0$,
$\frac{\ln(2Cm/d)}{\ln(\ln(2Cm/d))}\geq\sqrt{\ln(2Cm/d)}$ and $C>1$, so

$\operatorname*{\mathbb{E}}_{Y\sim
Q}[Y]\geq\frac{8Cm}{\ln\left(\ln\left(2Cm/d\right)\right)}\ln\left(\sqrt{\ln(2Cm/d)}\right)\geq
4m.$

We now show that $p^{\star}\operatorname*{\mathbb{E}}_{Y\sim Q}[Y]\geq 4$.
Using the fact that $p^{\star}\geq 2/(m_{1}m_{2})$ together with Eq. 18 gives
us

$p^{\star}\operatorname*{\mathbb{E}}_{Y\sim Q}[Y]\geq
2\ln\left(\frac{m_{2}}{2}\right)\geq
2\ln\left(\frac{\ln(2Cm/d)}{\ln\left(\ln\left(2Cm/d\right)\right)}\right)\geq
4,$

where the last inequality holds for $C$ large enough.