Monotone Learning

Introduction

In this work we study the following fundamental question. Pick some standard learning algorithm $A$, and consider training it for some natural task using a data-set of $n$ examples.

Does feeding $A$ with more training data provably reduces its population loss?

E.g., would increasing the number of examples from $n$ to $n+1$ improve its loss? How about $2n$? Can one guarantee improvement in this case? What about $2^{n}$, or even $2^{2^{n}}$? Would that be sufficient? Can one at least assure that the loss will not deteriorate?

Intuitively, the answer should be yes: indeed, the more often we face a certain task, the better we typically get at solving it. This basic intuition is reflected in many works in theoretical and applied machine learning. For example, Shalev-Shwartz and Ben-David (2014) assert in their book that the learning curve starts decreasing when the number of examples surpasses the VC dimension (page 153); Duda, Hart, and Stork (2001) state in their book that for real-world problems the learning curve is monotone (Subsection 9.6.7). Similar statements are made by a variety of other works, a partial list includes Gu, Hu, and Liu (2001); Tax and Duin (2008); Weiss and Battistin (2014). We refer the reader to the thorough survey by Viering and Loog (2021) for an extensive discussion about monotone and non-monotone learning curves (Section 6).

On the other hand, one might argue that in order to successfully learn complex functions, the algorithm must dedicate time and resources to exploring larger and larger sets of hypotheses, and consequently exhibit a non-monotone behaviour. For example, any Bayes consistent learning algorithm must consider arbitrarily complex hypotheses (since it is able to approximate arbitrary functions). Indeed, one can show that consistent algorithms such as Nearest-Neighbors can demonstrate such non-monotone behaviour (Devroye, Györfi, and Lugosi, 1996). This intuition is reflected in Chapter 6 in the book by Devroye, Györfi, and Lugosi (1996) in which it is conjectured that no Bayes-consistent rules can be monotone (Problem 6.16).

These intuitive considerations inspire a host of theoretical questions. Is it really the case that “more data $=$ better generalization”? Is it at least the case for natural algorithms and natural learning tasks? Perhaps it is too much to expect that the addition of a single example will lead to better performance, but maybe if one doubles the training-set then better performance is guaranteed? Can we at least guarantee that the performance does not deteriorate?

Monotone Learners

A learning rule $M$ is said to be monotone w.r.t a distribution $D$ if,

That is, the expected population loss of $M$ is monotone non-decreasing in the size of its training set.

The following theorem is the main result in this work; it asserts that every learning algorithm can be efficiently transformed to a monotone one with competitive generalization guarantees.

$M$ is monotone with respect to every distribution $D$.

$M$’s performance is competitive with that of $A$: for every source distribution $D$,

Theorem 1.2 affirmatively answers questions posed by Devroye, Györfi, and Lugosi (1996), Viering, Mey, and Loog (2019), Viering and Loog (2021), and Mhammedi (2021). In addition, Theorem 1.2 readily implies monotone learners in a variety of contexts:

Indeed, this follows by applying the transformation on any Bayes-consistent learner (for example, $k$-nearest neighbor). This extends Pestov’s result who focused on the case of binary classification and designed a clever histogram-based Bayes consistent algorithm. Moreover, while Pestov’s algorithm and analysis are tailored to the binary case, our argument is more general, and at the same time conceptually (and arguably technically) simpler. The existence of Bayes-optimal consistent learner remained open for 25 years since it was asked by by Devroye, Györfi, and Lugosi (1996).

Theorem 1.2 is also applicable in other contexts. In fact, the distribution-free regret-bound on the learning rate of the monotone learner allows one to apply it in the PAC setting, where monotone learners were not known to exist Viering, Mey, and Loog (2019); Viering and Loog (2021):

Indeed, this follows by applying the transformation on any PAC learning algorithm for $\mathcal{H}$ (say any empirical risk minimizer). Note that the learning rate of the resulting monotone PAC learner is suboptimal by an additive $\log m$ factorThe optimal PAC learning rate is proportional to $\sqrt{1/m}$.. We leave the exploration for the optimal monotone PAC learning rate to future work.

1 Informal Explanation

A learning rule, even if it is Bayes consistent, does not have any reason, a priori, to be monotone. Indeed, the fact that the expected error converges to the Bayes error does not mean the convergence happens monotonically and it could very well be that the error strictly increases between $m$ and $m+1$ infinitely often. Let us examine what are the difficulties one would encounter when trying to convert a Bayes consistent learner into one that is monotone.

Given any learning algorithm $A$ that has the following convergence property:

However, the above subsequence of indices is distribution-dependent, which means that we cannot guarantee that if we increase the sample size from some value $m$ to some other value $m^{\prime}$, the error will be smaller for all distributions.

We first observe that we could relax the monotonicity requirement to hold only for infinitely many steps (or arbitrary size). Indeed, while the monotonicity requirement of Definition 1.1 is written for $m$ and $m+1$, we observe that if we had a learner that satisfies a sparse version of this inequality, such as

it would be easy to convert it into a learner that satisfies Definition 1.1 without affecting the limit of its population loss as $m\to\infty$. Indeed, the above condition guarantees that there is an infinite sequence $m_{1},\ldots,m_{k},\ldots$ of indices over which the algorithm is guaranteed not to increase its expected loss. This sequence can be defined as $m_{1}=1$ and $m_{k+1}=m^{\prime}(m_{k})$. And from this, one could create a learner that, given $m$ examples with $m\in[m_{k},m_{k+1})$, simply ignores $m-m_{k}$ examples from the training set. The monotonicity condition would then be satisfied with equality between $m_{k}$ and $m_{k+1}$ since the output of our algorithm would be unchanged (in expectation).

So in order to convert an arbitrary learning rule into one that is monotone, while still retaining its convergence properties, the main idea is to run the algorithm on prefixes of the training sample and measure the loss of the produced hypotheses in order to pick the best one. As the sample size increases, the pool of hypotheses to choose from will increase and the best one from a larger pool will thus have a smaller loss than from a smaller pool. This idea has been previously explored by Viering, Mey, and Loog (2020); Mhammedi (2021).

However, implementing this idea turns out to be a subtle task. Indeed, we can only estimate the loss of the hypotheses (by setting aside some examples and computing their empirical loss), so there is always some possibility that we choose a worse hypothesis (which empirically looks better).

To illustrate the issue, let’s consider the simplest possible situation where the base algorithm has produced a hypothesis $h_{0}$ on a prefix of the sample, and another hypothesis $h_{1}$ on a longer prefix. If $\operatorname{L_{D}}(h_{1})\leq\operatorname{L_{D}}(h_{0})$, the base algorithm is already monotone, but in the case $\operatorname{L_{D}}(h_{1})>\operatorname{L_{D}}(h_{0})$, any wrapper algorithm would have to choose between outputting $h_{0}$ or $h_{1}$. Unfortunately, this choice will necessarily worsen the error (unless the wrapper always outputs $h_{0}$ deterministically, in which case it would not manage to track the performance of the base algorithm). Indeed, the expected loss of any wrapper would be a convex combination of $\operatorname{L_{D}}(h_{1})$ and $\operatorname{L_{D}}(h_{0})$ and would be strictly larger than $\operatorname{L_{D}}(h_{0})$.

So we cannot simply take the output of the base algorithm, and the idea is to regularize it, i.e., make it possibly a little worse but in such a way that this regularization can be reduced as the sample size increases and thus we can guarantee monotonicity.

The question thus becomes: given a hypothesis $h$, is there a way to produce a hypothesis $h^{\prime}$ that is guaranteed to be worse than $h$ (i.e., $\operatorname{L_{D}}(h^{\prime})>\operatorname{L_{D}}(h)$) and to possibly control how much worse it is? The first idea that comes to mind is to sometimes output a label which we know is incorrect. This would be possible if we add some extra label at our disposal, e.g., in binary classification we would allow the learner to output something different from or $1$, say $\bot$ and count $\bot$ as a mistake. But this is somewhat artificial and would require to change the nature of the algorithm’s predictions. So the second idea that comes to mind is to just add noise to the output of the algorithm, i.e., to randomly pick a different label than the one predicted. Unfortunately, in the context of classification, adding noise does not guarantee that the loss is made worse! Indeed, in binary classification, if $\operatorname{L_{D}}(h)>1/2$, adding some uniform noise to the output would make the error closer to $1/2$, hence better and not worse.

So we see that if we could, given a hypothesis $h$, which could have error larger than $1/2$, return one that is guaranteed to have error less than $1/2$, we could then make the latter worse by adding uniform noise. This brings us to our last key idea: we symmetrize the output by replacing the hypothesis produced by the base algorithm by the best (in terms of empirical error) between $h$ and $1-h$. We can then guarantee (we will prove it below) that the expected loss of this symmetrized output is less than $1/2$ and adding noise will thus strictly increase its loss, making room for reducing the loss when we choose between $h_{0}$ and $h_{1}$.

Symmetrization is more subtle in the context of multiclass classification with $k>2$ labels; the idea there is to replace $h$ with the best out of $k$ hypotheses which are obtained by composing $h$ with a cyclic permutation of the labels. For simplicity, we focus on the binary-case in this outline.

Let us now try and write down some of the ideas above more formally. The overall approach is to run the base algorithm on a prefix of size $n$ of the sample $S$ to obtain some hypothesis $h_{0}$, apply some transformation (which we call regularization) to $h_{0}$ which consists of symmetrizing and adding noise, in order to obtain $R(h_{0},S)$. Then perform the same operation on a longer prefix of size $N>n$ of $S$ to obtain $R(h_{1},S)$ and then decide whether to use $h_{0}$ or $h_{1}$ by estimating their respective errors (on an additional subset of $N$ examples from $S$). If we denote by $p_{N}$ the probability of choosing $h_{1}$ over $h_{0}$, we see that the expected error of the resulting procedure will have the formWe will later provide more details about how to split the training sample so as to guarantee independence and decouple the expecations appropriately.

and if we want to satisfy Inequality (1), this quantity would have to be smaller than the expected error of our procedure ran on $n$ examples, i.e., we would want

As discussed above, without regularization, i.e., if $R$ is the identity, there is no way to guarantee this inequality for every pair $h_{0},h_{1}$, and the problematic case is when $h_{1}$ is worse than $h_{0}$, or when $R(h_{1},S)$ is worse than $R(h_{0},S)$. If we rewrite the above condition as follows:

we see that in order for it to be satisfied even when $R(h_{1},S)$ is worse than $R(h_{0},S)$, we need

$p_{N}$ has to be small enough (to make the left hand side small enough).

The regularization over $N$ examples has to be strictly better than the regularization over $n$ examples (to make the right hand side positive and large enough).

2 Technical Contributions

The technical contribution in this work can roughly be partitioned to two parts:

We develop a general axiomatic framework for constructing transformations which compile arbitrary learners to monotone learners with similar guarantees (Section 2). We attempt to state this framework in an abstract manner with the hope that it might be useful for other loss functions.

In a nutshell, this framework reduces the task to constructing for every hypothesis $h$ a small and symmetric class $B_{h}$ such that $h\in B_{h}$, and $B_{h}$ can be learned by a monotone learner; for example, in the context of binary classification ($Y=\{0,1\}$) we use $B_{h}=\{h,1-h\}$. More generally, in the context of multiclass classification ($Y=[k]=\{0,\ldots,k-1\}$), we use $B_{h}=\{s_{i}\circ h:i\in[k]\}$, where $s_{i}$ is the cyclic permutations mapping a label $y$ to $y+i\mod k$.

In Sections 3 and 4 we use our general framework to prove Theorem 1.2. In Section 3 we focus on the case of binary classification; this section serves as a warmup to the general multiclass setting which is considered in Section 4.

The most technical proof in this work is that of Proposition 4.1, specifically Lemma 4.2 which asserts that the randomized ERM over $B_{h}$ is monotone: Recall that for a hypothesis $h:X\to\{0,\ldots,k-1\}$, the class $B_{h}$ consists of the $k$ cyclic permutations of $h$: $B_{h}=\{s_{i}\circ h:i\in[k]\}$, where $s_{i}$ is a cyclic permutation mapping $y\mapsto y+i\mod k$. The randomized ERM is the algorithm which given an input sample $S$, outputs an empirical risk minimizer from $B_{h}$ which is drawn uniformly at random.

To prove Proposition 4.1 we exploit the following symmetry exhibited by $B_{h}$: for any example $(x,y)$ there exists a unique $h^{\prime}\in B_{h}$ such that $h^{\prime}(x)=y$. This implies, via a symmetrization argument and via Chebychev’s sum inequalityChebyshev’s sum inequality asserts that if $a_{1}\leq a_{2}\leq\ldots\leq a_{n}$ and $b_{1}\geq b_{2}\geq\ldots b_{n}$ then $\frac{1}{n}\sum a_{i}\cdot\frac{1}{n}\sum b_{i}\geq\frac{1}{n}a_{i}b_{i}$. the desired monotonicity (Hardy, Littlewood, and Pólya, 1988).

We also note that the upper bound on the rate in Theorem 1.2 is independent of the number of labels $k$. To achieve this we once again appeal to the symmetric structure of $B_{h}$, and show that $B_{h}$ satisfies uniform convergence with rate which is independent of $k$.

3 Related Work

The idea of monotone learning curves for universally consistent learners was first discussed by Devroye, Györfi, and Lugosi (1996).This problem attracted little attention until recently when Viering, Mey, and Loog (2019) considered monotone learning in a variety of contexts (e.g., when the goal is to learn a fix hypothesis class) and under more general loss functions. Viering, Mey, and Loog (2020), Viering and Loog (2021), and Mhammedi (2021) considered the problem of transforming a given learner to a monotone one using a wrapper algorithm. Viering, Mey, and Loog (2020) and Mhammedi (2021) derive weaker forms of monotonicity and leave open the question of whether such a transformation exists. In this work we resolve this problem in the context of multiclass classification.

The conjecture by Devroye et al. (1996) was finally answered in the positive by Pestov (2021). Pestov’s result applies to binary classification, and here we prove an extension to general multiclass classification.

Viering, Mey, and Loog (2020) proposes to relax the requirement of monotonicity in expectation into high-probability and eventual monotonicity. Viering, Mey, and Loog (2020) and Mhammedi (2021) also discuss the relationship with the multiple descent phenomenon established for many learners in recent years.

It is important to note that the open problem proposed by Viering et al. (2019) is concerning consistency with respect to a fixed class of function. So this is less general than the universal consistency of (Devroye, Györfi, and Lugosi, 1996).

While Pestov (2021) just builds a specific algorithm and not a generic wrapper, and considers only the binary classification case, there are some similarities between his approach and ours that are worth illustrating. Indeed, his algorithm consists in the following three ingredients

Consider prefixes of the input sample of (exponentially) increasing size

Perform a majority vote over a partition of the input domain

Decide (empirically) whether or not to split each element of the partition into smaller pieces

The first ingredient is similar to our (and other’s) approach of guaranteeing monotonicity on an infinite sequence of indices (what we call sparse monotonicity above), the second one bears some similarity with our symmetrization approach since the majority vote consists in comparing $h$ and $1-h$, and the last one is comparable with our update procedure which decides whether to continue using $h_{0}$ or to switch to $h_{1}$.

However there is one important difference which is key to obtaining a uniform bound on the excess loss of our monotone algorithm. Indeed, Pestov does not regularize by adding noise which requires him to refine the partition element under some very restrictive conditions (the conditional loss on the partition should not be close to $1/2$ nor to or $1$) which has the effect of requiring to make a very large increases of the sample size between two stages, resulting in a slower, non-uniform, convergence rate (more specifically, he does not provide an explicit formula for computing $N$ from $n$).

General Framework

Given an algorithm $A$ which maps an input sample $S$ to an output hypothesis $A(S)$, we construct a monotone algorithm $M$ using two intermediate algorithms:

A regularization algorithm $R$ is an algorithm that takes as input a sample $S$ and a hypothesis $h$ and returns a (possibly randomized) hypothesis $R(h,S)$. It might be useful/intuitive to think about $R(h,S)$ as a smooth/regularized version of $h$.

An update algorithm $U$ is an algorithm that takes as an input a sample $S$ and two hypotheses: (i) $h_{0}$ which is called the current hypothesis, and (ii) $h_{1}$ which is called the candidate hypothesis. The algorithm then outputs a hypothesis denoted by $U(h_{0},h_{1},S)\in\{h_{0},h_{1}\}$. Intuitively, $U$ chooses whether to replace the current hypothesis $h_{0}$ with the candidate hypothesis $h_{1}$, when the latter has smaller error.

The monotone algorithm will then be constructed in an iterative manner from $A$ by applying $A$ to prefixes of the training sample of increasing size and using the update algorithm at each step to decide whether to keep the current hypothesis or to update it to the new one (built on a longer prefix). At the end, we output a normalized version of the currently chosen hypothesis.

The update algorithm ensures that with high probability we update the hypothesis only when the new hypothesis has better (smaller) loss than the previous one. But since there is still a small chance we have updated to a worse hypothesis, the regularization step will be used to correct for corresponding additional expected loss.

See Figure 1 for a more precise description of the algorithm $M$.

We introduce several conditions on the update and regularization algorithms which guarantee the success of Algorithm $M$ when applied to any learning algorithm $A$. We then analyze our algorithms by showing that they satisfy these conditions. Let us begin by introducing some notation: given a hypothesis $h$, denote by $\mathtt{LR}_{n}(h)$ the quantity

where the expectation is with respect to the sample $S$ of size $n$.

Let $R$ be a regularization algorithm, let $U$ be an update algorithm. We say that $(R,U)$ are successful if for every source distribution $D$ the following conditions are satisfied:

After regularization, the expected loss of the update algorithm is non-increasing:

The update algorithm competes with the new hypothesis at a small cost:

for some function $c$ such that $\lim_{n\to\infty}c(n)=0$.

where $T$ and $S_{T-2}$ are as in the pseudo-code of $M$ in Figure 1.

The case of $m<2b(1)+b(0)$ is trivial, so we assume that $m\geq 2b(1)+b(0)$. We start by proving monotonicity. We only need to consider the case where a new block is added (otherwise, the additional examples are simply discarded and thus the expected error is unchanged). In this case, it is sufficient to consider the effect of adding a new block $B_{T}$ and prove that

Conditioned on $S_{T-2}$, the hypotheses $f_{T-2}$ and $h_{T-1}$ are fixed and

is a function of $B_{T-1}$ (which is not under conditioning). Therefore,

where the last inequality follows by of Condition (C1)Notice that we apply (C1) here while conditioning on $S_{T-2}$. This is valid because $B_{T-1}$ is independent of $S_{T-2}$ and therefore Condition (C1) applies for every fixing of $S_{T-2}$.. Equation (3) now follows by taking expectation over $S_{T-2}$.

For the second part, observe that Condition (C2) implies that

1 The Base-Class Approach

We design two algorithms using our framework above, one in binary classification which serves as a “warmup” and a more general one in multiclass classification. In this subsection we describe a common abstraction of these two algorithms. We hope this abstraction will be useful in other contexts as well. (E.g., other loss functions.)

The common abstraction boils down to assuming that every hypothesis $h$ has an associated simple hypothesis class $B_{h}$ such that $h\in B_{h}$. For example in the context of binary classification ($Y=\{0,1\}$) our $B_{h}$ will consist of two hypotheses: $h$ and its negation $1-h$; i.e., $B_{h}=\{h,1-h\}$. More generally in multiclass classification with $k$ labels our $B_{h}$ will consist of $k$ hypotheses.

We require that $B_{h}$ is “well-behaved” in a precise sense which we next describe. Consider the following randomized empirical risk minimizer over $B_{h}$.

Algorithm $G$: Randomized Empirical Risk Minimization • Input: a hypothesis $h\in Y^{X}$ and a sample $S\in(X\times Y)^{n}$ • Set $B_{h}^{\star}=\{f\in B_{h}:\operatorname{\hat{L}_{S}}(f)=\min_{g\in B_{h}}\operatorname{\hat{L}_{S}}(g)\}$ • Output: a uniformly random hypothesis from $B_{h}^{\star}$, which is denoted by $G(h,S)$. In words, $G(h,S)$ is a random empirical risk minimizer in $B_{h}$. Note that on the empty sample, $G(h,\emptyset)$ is a random hypothesis drawn uniformly from $B_{h}$.

Let $\mathtt{LG}_{n}(h)$ denote the expected loss of $G(h,S)$ where $S$ is of size $n$:

Let $h\mapsto B_{h}$ be a mapping which associates with every hypothesis $h$ a finite hypothesis class $B_{h}$ such that $h\in B_{h}$. This mapping is called successful if the following properties are satisfied:

The loss of the randomized ERM over $B_{h}$ is monotone

There exists a function $e(n)$ with $\lim_{n\to\infty}e(n)=0$ such that every $B_{h}$ satisfies uniform convergence with rate $e(n)$:

The loss of the random ERM on the empty sample is independent of $h$ and of the source distribution $D$:

In other words, the expected loss of a uniform random hypothesis from $B_{h}$ is equal to a universal constant $\alpha$ which does not depend on $h$. ($\alpha$ can depend on the source distribution $D$.)

The first condition above could be relaxed into $\mathtt{LG}_{N}(h)\leq\mathtt{LG}_{n}(h)$ for some $N\geq n$ large enough. Indeed this would be sufficient to derive condition (C1). But we will show that the randomized ERM that we consider actually satisfies the stronger property of monotonicity for $N=n+1$.

The second item above implies (via a triangle inequality) that the randomized ERM $G(h,\cdot)$ is competitive with $h$:

(Note that $\min_{f\in B_{h}}\operatorname{L_{D}}(f)\leq\operatorname{L_{D}}(h)$, since $h\in B_{h}$.)

We next describe how a successful map $h\mapsto B_{h}$ yields a successful pair of regularization and update algorithms.

The Regularization Algorithm $R$ • Input: a hypothesis $h\in Y^{X}$, a sample $S\in(X\times Y)^{n}$. • Output: with probability $1-\eta_{n}$ output $G(h,S)$ and with probability $\eta_{n}$ output $G(h,\emptyset)$. Here $\eta_{n}\in(0,1)$ is a decreasing function of $n$ satisfying $\lim_{n\to\infty}\eta_{n}=0$. The Update Algorithm $U$ • Input: two hypotheses $h_{0},h_{1}\in Y^{X}$, a sample $S\in(X\times Y)^{n}$. • Compute $\min_{f\in B_{h_{0}}}\operatorname{\hat{L}_{S}}(f)$ and $\min_{f\in B_{h_{1}}}\operatorname{\hat{L}_{S}}(f)+\epsilon_{n}$, and output $h_{0}$ if the first quantity is smaller and $h_{1}$ otherwise. Here $\epsilon_{n}\in(0,1)$ is a decreasing function of $n$ satisfying $\lim_{n\to\infty}\epsilon_{n}=0$. Proposition 2 (Base-class). Assume $h\mapsto B_{h}$ is successful with uniform convergence rate $e(n)$. Then, the update algorithm $U$ and the regularization algorithm $R$ with parameters

satisfy Condition (C1) with $N(n)=4n$ and condition (C2) with $c(n)=2\eta_{n}+3\epsilon_{n}$.

The rest of this section is dedicated to proving Proposition 2. We begin with collecting some simple properties of the regularization and update algorithms, and then continue to establish Conditions (C1) and (C2).

2 Basic Properties of R𝑅R and U𝑈U

Fix a source distribution $D$. Recall the definition of $\mathtt{LR}_{n}$ (Equation 2):

We next present some basic properties of $\mathtt{LR}_{n}$ which will be useful in proving Proposition 2.

A simple calculation yields the following relationship between $\mathtt{LG}_{n}$ and $\mathtt{LR}_{n}$: for every hypothesis $h$ and every $n$:

The following claim asserts that $\mathtt{LR}_{n}$ is monotone:

For all $n,m$, if $m\geq n$ and $\eta_{m}\leq\eta_{n}\leq 1$ then

Lastly, observe that $R$ does not deteriorate the performance of $h$:

3 Update Probability

We first provide upper and lower bounds on the probability of making an update.

Let {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}u_{n}=\epsilon_{n}-6e(n)}=\sqrt{\ln(64n)/n}. (Recall the definition of $\epsilon_{n}$ in Proposition 2.) If $\mathtt{LR}_{n}(h_{1})>\mathtt{LR}_{n}(h_{0})$ then

and if $\mathtt{LR}_{n}(h_{1})<\mathtt{LR}_{n}(h_{0})-2\epsilon_{n}$ then

To simplify the calculations below, for a hypothesis $h$ let

We first connect the performance of the regularized versions of the hypotheses $h_{0}$ and $h_{1}$ to their error probability $\operatorname{L_{D}^{*}}(h_{0})$ and $\operatorname{L_{D}^{*}}(h_{1})$. From Equation (5) we obtain

Recall from the pseudo-code of the update algorithm $U$ that the probability of update, which we denote $p_{n}$ is given by

Hence we have the following implications:

4 Condition (C1)

Under the assumptions of Proposition 2, Condition (C1) is satisfied with $N(n)=4n$.

Thus, assume that $\mathtt{LR}_{N}(h_{1})>\mathtt{LR}_{n}(h_{0})$. By Equation (10),

Therefore, it suffices to show that in this case

Denoting $\eta^{\prime}=\eta_{n}-\eta_{N}\geq 0$, we have, by Claim 1:

Further, because $\mathtt{LG}_{N}(\cdot)\leq\alpha$,

Hence, condition (C1) is satisfied provided that $p_{N}\leq\eta^{\prime}$. By Lemma 2.5, we have

5 Condition (C2)

Under the assumptions of Propositon 2, Condition (C2) is satisfied with

Let $q_{n}:=\Pr_{S\sim D^{n}}[U(h_{0},h_{1},S)=h_{0}]$ be the probability of not switching to $h_{1}$. Thus,

Therefore, if $\mathtt{LR}_{n}(h_{0})\leq\mathtt{LR}_{n}(h_{1})+2\epsilon_{n}$ then :

Thus, the conclusion holds in this case. Therefore, assume that $\mathtt{LR}_{n}(h_{0})>\mathtt{LR}_{n}(h_{1})+2\epsilon_{n}$. In this case,

Binary Classification

In this section we prove that in the setting of binary classification, one can associate with every hypothesis $h$ a base class $B_{h}$ such that Definition 2.2 is satisfied.

Let the label-space $Y$ be $Y=\{0,1\}$. For each $h:X\to Y$ let $B_{h}=\{h,1-h\}$. Then, the mapping $h\to B_{h}$ is successful with uniform convergence rate $e(n)=1/\sqrt{n}$ and with $\alpha=1/2$.

That $e(n)=1/\sqrt{n}$ follows by elementary probabilistic argument (essentially bounding the variance of a Binomial random variable):

Also, showing that $\alpha=1/2$ is simple: indeed for every distribution $D$:

Thus, it remains to prove the first Item in Definition 2.2:

For all $n,m$ such that $m\geq n$ we have

We note that Pestov (2021) proved this statement when $m,n$ are odd. (See Lemma 3.1 in (Pestov, 2021)). We defer the proof to the next section where we derive a more general result that applies to multiclass with an arbitrary number of labels $k$. (See Lemma 4.2.) ∎

Multiclass Classification

We consider the multiclass case with $k<\infty$ labels. A hypothesis is a map from $X$ to $[k]$. To define $B_{h}$ we introduce cyclic permutations $s_{0},\ldots,s_{k-1}$ of $[k]$ ($s_{i}(j)=(j+i)\mod k$) and let $B_{h}=\{s_{i}\circ h:i\leq k\}$.

Let the label-space $Y$ be $Y=[k]$. For each $h:X\to Y$ let $B_{h}=\{s_{i}\circ h:i\leq k\}$. Then, the mapping $h\to B_{h}$ is successful with uniform convergence rate $e(n)=36/\sqrt{n}$ and with $\alpha=\frac{k-1}{k}$.

Let $h\in H$. We begin with the simplest part: namely that $\alpha=\frac{k-1}{k}$. Notice that the events

are pairwise disjoint; in fact they form a partition of $X\times Y$ because for each $(x,y)$ there is a unique $i$ such that $s_{i}\circ h(x)=y$). Therefore, for every distribution $D$ over $X\times Y$:

Above, $D_{S}$ denotes the empirical distribution induced by the sample $S=\{(x_{i},y_{i})\}_{i=1}^{m}$ (i.e., $D_{S}(E)=\frac{1}{m}\sum_{i=1}^{m}1[(x_{i},y_{i})\in E]$.). Thus, it remains to prove the first Item in Definition 2.2:

For all $n,m$ such that $m\geq n$ we have

By induction, it suffices to consider the case of $m=n+1$.

We first reformulate this problem in simpler terms. Recall that any example $z=(x,y)$ is classified correctly by exactly one of the $h_{j}$’s in $B_{h}$. Thus, partition the domain into sets $E_{1},\ldots,E_{k}$ (with $k=\lvert B_{h}\rvert$) such that $z\in E_{j}\Leftrightarrow h_{j}(x)=y$. Thus, we have $\Pr(E_{j})=1-\operatorname{L_{D}}(h_{j})$. To simplify the expressions below we denote

Let $S=\{z_{i}\}_{i=1}^{n}\sim D^{n}$ be an i.i.d sample and let $i\leq n$. Define $X_{i}$ to be the random variable which is equal to the unique index $j$ such that $z_{i}\in E_{j}$. (I.e., $h_{j}$ correctly classifies $z_{i}$.) Notice that the variables $(X_{1},\ldots,X_{n})$ are i.i.d. with values in $[k]$ and distribution given by $\Pr(X_{i}=j)=p_{j}$ for all $i\leq n,j\leq k$. We can then express $\mathtt{LG}_{n}(h)$ as the expectation over the sample ${L_{n}}=(X_{1},\ldots,X_{n})$ of the quantity

where $I=I({L_{n}})$ is the set of indices $j$ such that $\sum_{i=1}^{n}1[X_{i}=j]$ is largest. (Equivalently, such that $h_{j}$ is an empirical risk minimizer in $B_{h}$ with respect to the input sample $S$.)

Let ${L=L_{n+1}}$ be a sample of $n+1$ such variables $(X_{1},\ldots,X_{n+1})$ (corresponding to an input sample $S\sim D^{n+1}$), and let $L^{-i}$ denote the sample $L$ without its $i$-th element, by symmetry and by linearity of expectation, we have

We first study the above quantity when conditioned on $\lvert I\rvert>1$ (i.e., there are at least $2$ empirical risk minimizers in $B_{h}$). Notice that when $\lvert I\rvert>1$ every $i\leq n+1$ satisfies $I_{i}\subseteq I$, where $I_{i}=I(L^{-i})$. Also notice that if $\lvert I\rvert>1$ then $I_{i}=I$ if and only if $X_{i}\notin I$. Thus,

Since all elements of $I$ have the same number of successes, the sum $\sum_{i=1}^{n+1}1[X_{i}=k]$ is the same for all $k\in I$ and since

Now let us consider the case $|I|=1$. Let $J\supseteq I$ denote the set of almost minimizers (i.e., which are either optimal or one away from being optimal). We further condition on $J$ being some arbitrary fixed set $J_{0}$:

Therefore, since $\Pr[I=\{X_{n+1}\}|\lvert I\rvert=1,J=J_{0}\}]>0$, it is enough to consider

Equation (13) above follows because the event that the set of almost minimizers $J$ is $J_{0}$ and the unique minimizer is $X_{n+1}$ is equivalent to the event that the set of minimizers with respect to the first $n$ samples $X_{1},\ldots,X_{n}$ is $J_{0}$ and $X_{n+1}\in J_{0}$.

Finally, to see that the above is non-positive we use Chebyshev’s sum inequality, which asserts that if $a_{1}\leq\ldots\leq a_{n}$ and $b_{1}\geq\ldots\geq b_{n}$ then $\frac{1}{n}\sum a_{i}\cdot\frac{1}{n}\sum b_{i}\geq\frac{1}{n}\sum a_{i}b_{i}$ (Hardy, Littlewood, and Pólya, 1988). Thus, since $p_{i}=1-q_{i}$, this inequality implies that the left term inside the brackets is upper bounded by the right term, and so we get that the difference is non-positive. Hence, for every choice of $J_{0}$:

which together with Equation (12) allows to conclude the proof of the lemma. ∎

This concludes the proof of Proposition 4.1. ∎

Wrapping Up

Let $A$ be any learning algorithm Proposition 4.1, Proposition 2, and Proposition 1 imply the existence of a monotone algorithm $M$ such that for all $m\geq 2\cdot b(1)+b(0)$,

$T=T(m)$ is the maximal integer such that $b(T-1)+\sum_{t=0}^{T-1}b(t)\leq m$, and

$S_{T-2}$ is an i.i.d sample from the source distribution $D$ of size $\sum_{t=0}^{T-2}b(t)$.

c(x)=2\cdot\frac{1}{2\sqrt{x}}+3\Bigl{(}\sqrt{{\ln(64x)}/{x}}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}6\cdot\frac{36}{\sqrt{x}}}\Bigr{)}=O\Bigl{(}\sqrt{\frac{\log x}{x}}\Bigr{)},

Since $M$ is monotone, it remains to prove that $M$’s performance is competitive with that of $A$. The case of input sample-size $m<2b(1)+b(0)=9$ is trivial. So, assume $m\geq 9$ and hence Equation 14 holds. By Items 1–4 above it suffices to show that $\lvert S_{T-2}\rvert\geq(m/30)-1$ and that $b(T-1)\geq m/10$. We proceed by showing that $T=T(m)=\Theta(\log m)$. Recall that $T$ is the maximal positive integer such that

and $b(T-1)$, $\lvert S_{T-2}\rvert$ satisfy:

Open Questions and Future Research

We conclude this manuscript with some suggestions of open problems for future research.

While the abstract framework developed in Section 2 extends to other (bounded) loss functions, the construction of the base classes $B_{h}$ is tailored to the zero/one loss. It will be interesting to explore to which loss functions can one extend Theorem 1.2.

It will be interesting to explore whether the bound on the rate in Theorem 1.2 can be strengthened to retain optimal learning rates.

For example, for PAC learnable classes $\mathcal{H}\subseteq\{0,1\}^{X}$, the optimal learning rate in the agnostic setting scales like $\sqrt{d/m}$, and in the realizable setting like $d/m$, where $d$ is the VC dimension and $m$ is the input-sample size. Can these optimal rates be achieved by a monotone learning rule? Note that Theorem 1.2 is off by a $\log m$ factor.

Another interesting setting to explore this question is the model of universal learning, in which one focuses on distribution-dependent rates (Bousquet, Hanneke, Moran, van Handel, and Yehudayoff, 2021). In contrast with the distribution-free nature of PAC learning, some classes can be learned exponentially fast, at a rate which scales like $\exp(-n)$ (Schuurmans, 1997; Bousquet, Hanneke, Moran, van Handel, and Yehudayoff, 2021). Can such classes be learned monotonically in this fast rate?

Which classes admit a monotone empirical risk minimizer (ERM)? One of the key technical steps in our proof was to show that the class $B_{h}$ admits a monotone ERM. Our proof exploited the symmetry of $B_{h}$ (specifically, that each example is classified correctly by exactly one hypothesis in $B_{h}$). It will be interesting to determine which other classes admit monotone ERMs. In fact, as far as we know it is even open whether every (learnable) class admits a monotone ERM.

Acknowledgements

We thank Gábor Lugosi for an insightful correspondence that helped to materialize the ideas leading to this work. We also thank Grigoris Velegkas and Amin Karbasi, and Gyeongwon Jeong and Jaehui Hwang for helping us correcting derivations in the proofs of Lemma 4.2 and Lemma 2.5.

References