Of Dice and Games:
A Theory of Generalized Boosting

Marco Bressan¹, Nataly Brukhim², Nicolò Cesa-Bianchi^1,3,
Emmanuel Esposito¹, Yishay Mansour^4,5, Shay Moran^6,5, Maximilian Thiessen⁷
¹Universita degli Studi di Milano, Italy ²Institute for Advanced Study, USA
³Politecnico di Milano, Italy ⁴Tel Aviv University, Israel ⁵Google Research
⁶Technion, Israel ⁷TU Wien, Austria

Abstract

Cost-sensitive loss functions are crucial in many real-world prediction problems, where different types of errors are penalized differently; for example, in medical diagnosis, a false negative prediction can lead to worse consequences than a false positive prediction. However, traditional PAC learning theory has mostly focused on the symmetric 0-1 loss, leaving cost-sensitive losses largely unaddressed. In this work, we extend the celebrated theory of boosting to incorporate both cost-sensitive and multi-objective losses. Cost-sensitive losses assign costs to the entries of a confusion matrix, and are used to control the sum of prediction errors accounting for the cost of each error type. Multi-objective losses, on the other hand, simultaneously track multiple cost-sensitive losses, and are useful when the goal is to satisfy several criteria at once (e.g., minimizing false positives while keeping false negatives below a critical threshold).

We develop a comprehensive theory of cost-sensitive and multi-objective boosting, providing a taxonomy of weak learning guarantees that distinguishes which guarantees are trivial (i.e., can always be achieved), which ones are boostable (i.e., imply strong learning), and which ones are intermediate, implying non-trivial yet not arbitrarily accurate learning. For binary classification, we establish a dichotomy: a weak learning guarantee is either trivial or boostable. In the multiclass setting, we describe a more intricate landscape of intermediate weak learning guarantees. Our characterization relies on a geometric interpretation of boosting, revealing a surprising equivalence between cost-sensitive and multi-objective losses.

Keywords: Boosting, Minimax theorem, cost-sensitive learning, multi-objective learning, Blackwell’s approachability.

1 Introduction

In many machine learning applications, different types of mistakes may have very different consequences, making it crucial to consider the costs associated with them. For example, in medical diagnostics, failing to detect a serious illness (a false negative) can have life-threatening implications, whereas incorrectly diagnosing a healthy person as ill (a false positive) mostly leads to unnecessary stress and medical expenses. This disparity in error costs is not limited to binary decisions. For example, when recommending movies to a viewer with preferences “romance over action over horror”, misclassifying a romance film as “horror” is probably worse than misclassifying it as “action”. Besides weighting different kinds of mispredictions, one may even want to treat different kinds of mispredictions separately. That is, instead of a cost-sensitive criterion, one may use a multi-objective criterion, specifying acceptable rates for different types of mispredictions. For example, one may find acceptable a false positive rate of (say) $10\%$ only if simultaneously the false negative rate is at most (say) $1\%$ .

Despite the importance of misclassification costs in applications, the theoretical understanding of this setting is lacking. A glaring example, which motivates this work, is boosting. Broadly speaking, a boosting algorithm is a procedure that aggregates several weak learners (whose accuracy is only marginally better than a random guess) into a single strong learner (whose accuracy can be made as high as desired). Although this is a fundamental and well-studied machine learning technique, a theory of boosting accounting for cost-sensitive or multi-objective losses is missing, even in the simplest setting of binary classification.¹¹1There are many works on adapting AdaBoost to cost-sensitive learning, but they do not address the fundamental question of identifying the minimal assumption on the cost-sensitive function which guarantees boosting. See more in Appendix A. In fact, if one can assign different costs to different kinds of mistakes, then even the meaning of “marginaly better than a random guess” is not immediately clear; let alone the question of whether one can boost a weak learner to a strong learner, or what precisely “boosting” means. The present work addresses those challenges, providing a generalized theory of boosting which unifies different types of weak learning guarantees, including cost-sensitive and multi-objective ones, and extends the standard algorithmic boosting framework beyond the current state of the art. The fundamental question that we pose is:

Which cost-sensitive and/or multi-objective learners can be boosted? And how?

In classical boosting theory for binary classification, a sharp transition occurs at a weak learner’s error threshold of $1/2$ : if the weak learner is guaranteed to output hypotheses with an error rate below $1/2$ , then it can be boosted to a strong learner with arbitrarily small error, for instance by AdaBoost (Freund and Schapire, 1997). Thus, a weak learning guarantee below $1/2$ implies strong learning. On the other hand, a guarantee of $1/2$ is trivial, as it can be achieved by tossing a fair coin—see Schapire and Freund (2012). Therefore, guarantees above $1/2$ are not boostable.

We investigate whether similar transitions exist for arbitrary cost-sensitive losses. A cost-sensitive loss $w$ specifies the penalty $w(i,j)$ for predicting $i$ when the true label is $j$ , and can penalize prediction errors unequally (e.g., in binary classification, it may penalize false negatives more than false positives). Suppose we have access to a weak learner that outputs hypotheses with a cost-sensitive loss of at most $z>0$ under $w$ . For which values of $z$ does this imply strong learning, so that the weak learner can be boosted to achieve arbitrarily small cost-sensitive loss according to $w$ ? Which values of $z$ are trivial, meaning they can always be achieved? Are there intermediate values of $z$ that do not imply strong learning but are still non-trivial?

A similar question arises for multi-objective losses. A multi-objective loss is given by a vector $\boldsymbol{w}=(w_{1},w_{2},\ldots,w_{r})$ where each $w_{i}$ is a cost-sensitive loss as described above. For instance, in binary classification, a natural choice would be $\boldsymbol{w}=(w_{n},w_{p})$ , where $w_{n}$ measures false negatives and $w_{p}$ false positives. Suppose again we have access to a weak learner that outputs hypotheses with loss at most $z_{i}\geq 0$ under $w_{i}$ simultaneously for every $i$ , forming a vector of guarantees $\mathbf{z}=(z_{1},\ldots,z_{r})$ . Which $\mathbf{z}$ are trivial, in that they can always be achieved? Which $\mathbf{z}$ are boostable, allowing for a strong learner that achieves arbitrarily small error simultaneously for all of the losses $w_{i}$ ? And are there intermediate vectors $\mathbf{z}$ that fall between trivial and boostable?

We address these questions by introducing a new perspective on random guessing, framed as either a zero-sum game or a vector-payoff game (known as a Blackwell approachability game). This game-theoretic approach applies to both cost-sensitive and multi-objective learning, leading to a complete characterization of boostability in these cases. We then extend these techniques to the multiclass setting, where the boostability landscape becomes significantly more complex. While this perspective complements existing views of boosting as a zero-sum game, prior methods are not suited to the settings we examine here. The new tools introduced in this work effectively handle a broad learning framework, establishing a unified and comprehensive theory of generalized boosting.

In particular, we provide extensive answers to the above questions, as follows:

•

Cost-sensitive losses. For binary classification, we establish a crisp dichotomy: each guarantee $z\geq 0$ is either trivial or boostable (A). We show that this transition occurs at a critical threshold given by the value of a zero-sum game defined by $w$ itself. In the multiclass setting, the dichotomy expands into a hierarchy of guarantees, ranging from fully boostable to trivial. Here, we show that there exist multiple thresholds $0<v_{1}(w)<v_{2}(w)<\ldots<v_{\tau}(w)$ , where $\tau$ depends on the cost function $w$ , and each guarantee $z\in(v_{i},v_{i+1})$ can be boosted down to $v_{i}$ (C). This generalizes the binary case, in which $\tau=1$ .
•

Multi-objective losses. For binary classification, we again show a clean dichotomy; however, the threshold now takes a higher-dimensional form, becoming a surface that separates trivial guarantees from boostable ones (B). Figure 1 illustrates this surface for a loss vector $\boldsymbol{w}$ representing false positive and false negative errors. In the multiclass setting, things become more complex: here, we show how to boost non-trivial guarantees to list-learners (D), but a complete taxonomy of boostable guarantees remains elusive and is left as an open question.
•

An equivalence between cost-sensitive and multi-objective losses. We establish and exploit an equivalence between multi-objective and cost-sensitive losses that may be of independent interest (Theorem 6). Given a loss vector $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ , consider a weak learner that outputs hypotheses with loss at most $z_{i}$ for each $w_{i}$ . By linearity of expectation, it follows that for any convex combination $w_{\boldsymbol{\alpha}}=\sum\alpha_{i}w_{i}$ , the weak learner’s loss with respect to $w_{\boldsymbol{\alpha}}$ does not exceed $\sum\alpha_{i}z_{i}$ . We prove that the converse also holds: if for each such $w_{\boldsymbol{\alpha}}$ there exists a weak learner with loss at most $\sum\alpha_{i}z_{i}$ , then we can efficiently aggregate these learners into one that achieves loss at most $z_{i}$ simultaneously for every $w_{i}$ . Interestingly, a geometric perspective of this result reveals a connection to Blackwell’s Approachability Theorem (Blackwell, 1956) and to scalarization methods in multi-objective optimization.

Organization of the manuscript.

Section 2 gives a detailed walkthrough of all our main results, their significance, and the underlying intuition. Section 3 addresses the binary classification case, in both the cost-sensitive and multi-objective flavors. Section 4 presents our equivalence connecting cost-sensitive learners with multi-objective learners. Finally, Section 5 considers the multiclass case.

2 Main Results

This section outlines the problem setting and the key questions we investigate, and provides an overview of our main results. We begin from the basic technical setup. We consider the standard PAC (Probably Approximately Correct) setting (Valiant, 1984), which models learning a concept class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ for a domain ${\mathcal{X}}$ and a label space ${\mathcal{Y}}=[k]$ with $k\geq 2$ . We define a cost function, or simply cost, to be any function $w:{\mathcal{Y}}^{2}\to[0,1]$ that satisfies $w(i,i)=0$ for all $i\in{\mathcal{Y}}$ ;²²2Although the range of the cost is $[0,1]$ our results can be easily extended to arbitrary costs $w:{\mathcal{Y}}^{2}\to\mathbb{R}_{\geq 0}$ . the value $w(i,j)$ should be thought of as the penalty incurred by predicting $i$ when the true label is $j$ . Note that $w$ can be seen as a $k\times k$ matrix indexed by ${\mathcal{Y}}$ . For instance, for ${\mathcal{Y}}=\{-1,+1\}$ , a valid cost is $w=\bigl{(}\begin{smallmatrix}0&1\\ 4&0\end{smallmatrix}\bigr{)}$ ; this means that the cost of a false positive is $w(+1,-1)=4$ , and that of a false negative is $w(-1,+1)=1$ . For conciseness, in the binary setting we let $w_{-}=w(-1,+1)$ and $w_{+}=w(+1,-1)$ ; and by some overloading of notation we denote by $w$ both the matrix $\bigl{(}\begin{smallmatrix}0&w_{-}\\ w_{+}&0\end{smallmatrix}\bigr{)}$ and the vector $(w_{+},w_{-})$ . For a generic cost $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ , a target function $f\in\mathcal{F}$ , and a distribution $\mathcal{D}$ over ${\mathcal{X}}$ , the cost-sensitive loss of a predictor $h:{\mathcal{X}}\to{\mathcal{Y}}$ is:

L_{\mathcal{D}}^{w}(h)\triangleq{\mathbb E}_{x\sim\mathcal{D}}\Bigl{[}w(h(x),f(x))\Bigr{]}

(1)

For example, when $w(i,j)=\mathbb{I}\!\left\{i\neq j\right\}$ , then $L_{\mathcal{D}}^{w}(h)$ simply corresponds to $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}(h(x)\neq f(x))$ , the standard 0-1 loss used in binary classification. For convenience we assume throughout the paper that $\|w\|_{\infty}\leq 1$ , though all our results apply more broadly.

We begin by presenting our contributions for the binary setting (Section 2.1), followed by their extension to the general multiclass case (Section 2.2).

2.1 Binary setting

We begin from the binary setting, that is, the case ${\mathcal{Y}}=\{-1,+1\}$ . The starting point is the definition of a suitable notion of “weak learner” for an arbitrary cost function $w$ .

Definition 1 ( $(w,z)$ -learner).

Let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function and let $z\geq 0$ . An algorithm ${\mathcal{A}}$ is a $(w,z)$ -learner for $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ if there is a function $m_{0}:(0,1)^{2}\rightarrow\mathbb{N}$ such that for every $f\in\mathcal{F}$ , every distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and every $\epsilon,\delta\in(0,1)$ the following claim holds. If $S$ is a sample of $m_{0}(\epsilon,\delta)$ examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ , then ${\mathcal{A}}(S)$ returns a predictor $h:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ such that $L_{\mathcal{D}}^{w}(h)\leq z+\epsilon$ with probability at least $1-\delta$ .

Refer to caption — Figure 1: Boostability thresholds. Binary. For classic 0-1 loss binary boosting, it is well-known that the boostability threshold is $1/2$ : any value below it can be boosted, while any value above it is trivially attainable by non-boostable learners. For any cost $w$ , the boostability threshold is $\operatorname{V}(w)$ (see Equation 3, A). For the multi-objective loss, the threshold is determined by the boundary of the coin-attainable region, denoted $C(\boldsymbol{w})$ (see Definition 4, B), as illustrated in the plot on the right; each point in the plane corresponds to false-positive and false-negative errors $(z_{+},z_{-})$ . The two colored regions in the plot correspond to (a) coin-attainable point $C(\boldsymbol{w})$ (in red) and (b) boostable points $[0,1]^{2}\setminus C(\boldsymbol{w})$ (in blue). See below B for further discussion. Multiclass. A similar pattern holds for multiclass boosting. For 0-1 loss, boostability is known to be determined by $k-1$ thresholds (Brukhim et al., 2023a). For any cost $w$ , the boostability thresholds are $v_{{n}}(w)$ (see Equation 6). For the multi-objective loss, thresholds are determined by the boundaries of dice-attainable regions $D_{J}(\boldsymbol{w})$ (see Section 2.2 for further details).

We study the question of whether a $(w,z)$ -learner can be boosted. Broadly speaking, a learner ${\mathcal{A}}$ is boostable if there exists a learning algorithm ${\mathcal{B}}$ that can achieve arbitrarily small loss by aggregating a small set of predictors obtained from ${\mathcal{A}}$ . More precisely, given black-box access to ${\mathcal{A}}$ and a labeled sample $S$ , algorithm ${\mathcal{B}}$ invokes ${\mathcal{A}}$ on subsamples $S_{1},\ldots,S_{T}$ of $S$ to produce weak predictors $h_{1},\dots,h_{T}$ . It then outputs a predictor $\bar{h}(x)=g(h_{1}(x),\dots,h_{T}(x))$ using some aggregation function $g:{\mathcal{Y}}^{T}\rightarrow{\mathcal{Y}}$ . For instance, in classic binary boosting the function $g$ is usually a weighted majority vote. In this work, we consider arbitrary such aggregations. The goal is to ensure that the loss of the aggregate predictor, $L_{\mathcal{D}}^{w}(\bar{h})$ , goes to zero with $T$ , resulting in a $(w,0)$ -learner. Our guiding question can then be stated as:

Can we boost a $(w,z)$ -learner to a $(w,0)$ -learner?

In order to develop some intuition, let us consider again the case when $w$ yields the standard 0-1 loss. In that case, Definition 1 boils down to the standard notion of a weak PAC learner.³³3Notice that this definition is slightly more general than the classic weak PAC learning definition, in which $z=\nicefrac{{1}}{{2}}-\gamma$ and $\epsilon=0$ , yet we consider learners which are allowed to be arbitrarily close to $z$ . Then, classic boosting theory states that every $(w,z)$ -learner with $z<\nicefrac{{1}}{{2}}$ can be boosted to a $(w,0)$ -learner; and it is easy to see that a loss of $\nicefrac{{1}}{{2}}$ is always achievable, simply by predicting according to a fair coin toss. Thus, the value $\nicefrac{{1}}{{2}}$ yields a sharp dichotomy: every $z<\nicefrac{{1}}{{2}}$ can be boosted and drawn to $0$ , while every $z\geq\nicefrac{{1}}{{2}}$ is trivially achievable and cannot be brought below $\nicefrac{{1}}{{2}}$ .

Can this classic dichotomy between “boostable” and “trivial” be extended to accommodate arbitrary cost functions? It turns out that this can be done if one uses as trivial predictors biased coins. Indeed, we show that, by taking such random guessing strategies into account, one can identify a general boostability threshold for all cost functions $w$ . However, in contrast to the 0-1 loss case, this critical threshold between the boostable and non-boostable guarantees is no longer $\nicefrac{{1}}{{2}}$ ; instead, it is a function of the cost $w$ . More precisely, the threshold is determined by the outcome of a simple two-player zero-sum game, as we describe next.

The game involves a minimizing player (the predictor) and a maximizing player (the environment). The minimizing player selects a distribution $\mathbf{p}$ over ${\mathcal{Y}}=\{-1,+1\}$ ; similarly, the maximizing player selects a distribution $\mathbf{q}$ over ${\mathcal{Y}}=\{-1,+1\}$ . The payoff matrix of the game is $w$ . The overall cost paid by the predictor is then:

w(\mathbf{p},\mathbf{q})\triangleq{\mathbb E}_{i\sim\mathbf{p}}{\mathbb E}_{j\sim\mathbf{q}}\ w(i,j)\,.

(2)

Following standard game theory, the value of the game is the quantity

\displaystyle\operatorname{V}(w)\triangleq\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\max_{\mathbf{q}\in\Delta_{\mathcal{Y}}}w(\mathbf{p},\mathbf{q})\,,

(3)

where $\Delta_{\mathcal{Y}}$ is the set of all distributions over ${\mathcal{Y}}$ . In words, $\operatorname{V}(w)$ is the smallest loss that the predictor can ensure by tossing a biased coin (i.e., $\mathbf{p}$ ) without knowing anything about the true distribution of the labels (i.e., $\mathbf{q}$ ). Now consider a value $z\geq 0$ . It is easy to see that, if $z\geq\operatorname{V}(w)$ , then there exists a universal $(w,z)$ -learner—one that works for all $\mathcal{F}$ and all distributions $\mathcal{D}$ over ${\mathcal{X}}$ : this is the learner that, ignoring the input sample, returns the randomized predictor $h_{\mathbf{p}}$ whose outcome $h(x)$ is distributed according to $\mathbf{p}$ independently for every $x\in{\mathcal{X}}$ . Indeed, by Equation 3 the loss of $h_{\mathbf{p}}$ is at most $\operatorname{V}(w)$ regardless of $f\in\mathcal{F}$ and of the distribution $\mathcal{D}$ . Formally, we define:

Definition 2 (Random guess).

A randomized hypothesis is called a random guess if its prediction $y\in{\mathcal{Y}}$ is independent of the input point $x\in{\mathcal{X}}$ . That is, there exists a probability distribution $\mathbf{p}\in\Delta_{\mathcal{Y}}$ such that $h(x)\sim\mathbf{p}$ for every $x\in{\mathcal{X}}$ .

We prove that the non-boostability condition $z\geq\operatorname{V}(w)$ is tight. That is, we prove that every $(w,z)$ -learner with $z<\operatorname{V}(w)$ is boostable to a $(w,0)$ -learner. Thus, the value of the game $\operatorname{V}(w)$ given by Equation 3 is precisely the threshold for boostability. Formally:

Theorem A (Cost-sensitive boosting, binary case).

Let ${\mathcal{Y}}=\{-1,+1\}$ . Let $w=(w_{+},w_{-})\in(0,1]^{2}$ be a cost. Then, for all $z\geq 0$ , exactly one of the following holds.

•

$(w,z)$ is boostable: for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , every $(w,z)$ -learner is boostable to a $(w,0)$ -learner.
•

$(w,z)$ is trivial: there exists a random guess $h$ such that the learner that always outputs $h$ is a $(w,z)$ -learner for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ .

Moreover, $(w,z)$ is boostable if and only if $z<V(w)$ , where $\operatorname{V}(w)=\frac{w_{+}w_{-}}{w_{+}+w_{-}}$ .

The proof of A is given in Section 3. In a nutshell, A says that anything that beats the weakest possible learner (a coin) is as powerful as a the strongest possible learner; between these two extremes there is no middle ground. Remarkably, the proof of A is simple and yet it relies on three distinct applications of von Neumann’s Minimax Theorem! (von Neumann, 1928). The first application, which also appears in classical binary boosting, is used to aggregate a distribution over the weak learners. The other two applications are unique to the cost-sensitive setting: one arises in the analysis of the boosting algorithm (first item of A), and the other one in defining the trivial learner (second item of A). These last two applications are both based on the zero-sum game defined above. We also note that the first item of A is obtained constructively by an efficient boosting algorithm, as we detail in Section 3.

2.1.1 Multi-objective losses

We turn our attention to multi-objective losses. A multi-objective loss is specified by a multi-objective cost, that is, a vector $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where $w_{i}:{\mathcal{Y}}^{2}\to[0,1]^{2}$ is a cost for every $i=1,\ldots,r$ . This allows one to express several criteria by which a learner is evaluated; for example, it allows us to measure separately the false positive rate and the false negative rate, giving a more fine-grained control over the error bounds. The guarantees of a learner can then be expressed by bounding $L_{\mathcal{D}}^{w_{i}}(h)$ by some $z_{i}\geq 0$ simultaneously for each $i=1,\ldots,r$ . This leads to the following generalization of Definition 1.

Definition 3 ( $(\boldsymbol{w},\boldsymbol{z})$ -learner).

Let $r\in\mathbb{N}$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\to[0,1]^{2}$ is a cost function, and let $\boldsymbol{z}\in[0,1]^{r}$ . An algorithm ${\mathcal{A}}$ is a $(\boldsymbol{w},\boldsymbol{z})$ -learner for $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ if there is a function $m_{0}:(0,1)^{2}\rightarrow\mathbb{N}$ such that for every $f\in\mathcal{F}$ , every distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and every $\epsilon,\delta\in(0,1)$ what follows holds. If $S$ is a sample of $m_{0}(\epsilon,\delta)$ examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ , then ${\mathcal{A}}(S)$ returns a predictor $h:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ such that with probability at least $1-\delta$ :

\forall\ i=1,\ldots,r,\qquad L^{w_{i}}_{\mathcal{D}}(h)\leq z_{i}+\epsilon\;.

Consider for example $\boldsymbol{w}=(w_{p},w_{n})$ with $w_{p}=\bigl{(}\begin{smallmatrix}0&0\\ 1&0\end{smallmatrix}\bigr{)}$ and $w_{n}=\bigl{(}\begin{smallmatrix}0&1\\ 0&0\end{smallmatrix}\bigr{)}$ . Then $w_{p}$ counts the false positives, $w_{n}$ the false negatives. Thus a $(\boldsymbol{w},\mathbf{z})$ -learner for, say, $\mathbf{z}=(0.1,0.4)$ ensures simultaneously a false-positive rate arbitrarily close to $0.1$ and false-negative arbitrarily close to $0.4$ . See Figure 2 for illustrative geometric examples.

Like for the cost-sensitive case, we address the question of which $(\boldsymbol{w},\boldsymbol{z})$ -learners are boostable. In other words we ask: given $\boldsymbol{w}$ , what is the right “threshold” for $\mathbf{z}$ ? Equivalently, for which $\mathbf{z}$ can we always boost a $(\boldsymbol{w},\boldsymbol{z})$ -learner to a $(\boldsymbol{w},\mathbf{0})$ -learner, and for which $\mathbf{z}$ do there exist $(\boldsymbol{w},\boldsymbol{z})$ -learners that are not boostable? It turns out that the answer is more nuanced than in the cost-sensitive case of Section 2.1, and yet we can prove the same “all or nothing” phenomenon of A, as depicted in Figure 1.⁴⁴4Note that the light-red area (upper triangle) is attainable by coins (distributions) that are oblivious to the true distribution marginals. For example, it is trivial to attain the point $(\frac{1}{2},\frac{1}{2})$ by a fair coin, and the points $(0,1)$ or $(1,0)$ by a “degenerate coin” that is simply a constant function which always predicts the same label. In particular, every $\mathbf{z}\in[0,1]^{r}$ is either entirely boostable, in the sense that every $(\boldsymbol{w},\boldsymbol{z})$ -learner can be boosted to a $(\boldsymbol{w},\mathbf{0})$ -learner, or trivial, in the sense that there exists a $(\boldsymbol{w},\boldsymbol{z})$ -learner whose output is always a hypothesis that can be simulated by a (biased) random coin. To this end we introduce the notion of coin attainability. This is the multi-objective equivalent of the condition $z\geq\operatorname{V}(w)$ for $w$ being a scalar cost as in Section 2.1.

Definition 4 (Coin attainability).

Let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost function for every $i=1,\ldots,r$ , and let $\mathbf{z}\in[0,1]^{r}$ . We say that $(\boldsymbol{w},\boldsymbol{z})$ is coin-attainable if

\forall\mathbf{q}\in\Delta_{\mathcal{Y}},\ \exists\mathbf{p}\in\Delta_{\mathcal{Y}},\ \forall i=1,\ldots,r,\qquad w_{i}(\mathbf{p},\mathbf{q})\leq z_{i}\;.

(4)

The coin-attainable region of $\boldsymbol{w}$ is the set $C(\boldsymbol{w})$ of all $\boldsymbol{z}$ such that $(\boldsymbol{w},\boldsymbol{z})$ is coin-attainable.

It is not hard to see that, if $\mathbf{z}$ is coin-attainable, there exists a universal trivial $(\boldsymbol{w},\mathbf{z})$ -learner for all $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . Fix indeed any distribution $\mathcal{D}$ over ${\mathcal{X}}$ and any $f\in\mathcal{F}$ . First, one can learn the marginal $\mathbf{q}$ of $\mathcal{D}$ over ${\mathcal{Y}}$ within, say, total variation distance $\epsilon$ ; then, by the coin-attainability of $\mathbf{z}$ , one can return a hypothesis $h$ such that $h(x)\sim\mathbf{p}$ , where $\mathbf{p}$ ensures $w_{i}(\mathbf{p},\mathbf{q})\leq z_{i}+\epsilon$ for all $i=1,\ldots,r$ . Formally, recalling the definition of random guess (Definition 2), we have:

Definition 5 (Trivial learner).

A learning algorithm ${\mathcal{A}}$ is trivial if it only outputs random guesses.

Thus, a trivial learner can (at best) learn the best random guess and return it. Clearly, such a learner is in general not boostable to a $(\boldsymbol{w},\mathbf{0})$ -learner. The main result of this subsection is:

Theorem B (Multi-objective boosting, binary case).

Let ${\mathcal{Y}}=\{-1,1\}$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost, and let $\boldsymbol{z}\in[0,1]^{r}$ . Then, exactly one of the following holds.

•

$(\boldsymbol{w},\boldsymbol{z})$ is boostable: for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , every $(\boldsymbol{w},\boldsymbol{z})$ -learner is boostable to a $(\boldsymbol{w},\mathbf{0})$ -learner.
•

$(\boldsymbol{w},\boldsymbol{z})$ is trivial: there exists a trivial learner that is a $(\boldsymbol{w},\boldsymbol{z})$ -learner for all $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ .

Moreover, $(\boldsymbol{w},\mathbf{z})$ is boostable if and only if $\mathbf{z}\notin C(\boldsymbol{w})$ .

The proof of B is given in Section 3, and is based on a certain scalarization of the loss amenable to a reduction to A. Let us spend a few words on B. First, note how Definition 4 is reminiscent of the zero-sum game of Section 2.1. The crucial difference, however, is that now the maximizing player (the environment) plays first, and the minimizing player (the predictor) can then choose $\mathbf{p}$ as a function of $\mathbf{q}$ . As shown in more detail in Section 3.2, this is essential for proving the second item—that is, for coin-attainability to capture exactly the guarantees attainable by trivial learners. For the scalar-valued game of Section 2.1, instead, by von Neumann’s Minimax Theorem the order of the players is immaterial to the value of the game $\operatorname{V}(w)$ .

Second, note that the multi-objective setting is more general than that of a (scalar-valued) zero-sum game, as here the payoff is vector-valued. This can be thought of as a Blackwell approachability game (Blackwell, 1956), a generalization of zero-sum games to vectorial payoffs. Indeed, it turns out that there is a connection between these two notions, in the sense of Blackwell’s theorem: we prove that a certain vectorial bound $\mathbf{z}$ can be attained (with respect to a vector-valued loss $\boldsymbol{w}$ ) if an only if all the “scalarizations” of $\mathbf{z}$ can be attained with respect to the corresponding scalarizations of $\boldsymbol{w}$ . In fact, we can show that this is captured formally by an equivalence between cost-sensitive learners and multi-objective learners, as explained in Section 2.1.2.

Geometric interpretation of B.

A multi-objective guarantee $\mathbf{z}$ with respect to a multi-objective cost $\boldsymbol{w}$ can be viewed as a set of linear constraints, $w_{i}\leq z_{i}$ . This identifies a region that is convex and downward closed, see Figure 2. This holds true even in the multiclass setting, when there are more than $2$ labels. Similarly, the set of all coin-attainable points $C(\boldsymbol{w})$ for the false-negative/false-positive objective $\boldsymbol{w}=(w_{p},w_{n})$ can be shown to be convex and upward-closed⁵⁵5A set $C$ is upward-closed if for all $\boldsymbol{z}\in C$ and $\boldsymbol{z}^{\prime}\in[0,1]^{r}$ such that $\boldsymbol{z}^{\prime}\geq\boldsymbol{z}$ coordinate-wise, then $\boldsymbol{z}^{\prime}\in C$ . See Section 3 for further details.. This is illustrated in Figure 1, as well as the set of all boostable points, given in the red and blue areas, respectively.

As shown in Figure 2, the coin-attainable boundary curve in this case, is given by $\sqrt{e_{+}}+\sqrt{e_{-}}=1$ (as shown in Section 3), and it is exactly the same curve obtained by the envelope of the lines of the form $\langle e,w\rangle=V(w)$ , for any cost $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ . This ties between the value $\operatorname{V}(w)$ to the coin-attainable area $C(\boldsymbol{w})$ .

For a general pair $(\boldsymbol{w},\boldsymbol{z})$ , one can characterize if it is coin-attainable by examining whether its associated convex feasible region is intersected with the set coin-attainable points as depicted in Figure 1. This intuition is also captured in Theorem 7 below.

2.1.2 Cost-sensitive vs. multi-objective losses: a general equivalence

We establish a general, formal connection between cost-sensitive and multi-objective learning. The starting point is the straightforward observation that, by definition, a $(\boldsymbol{w},\boldsymbol{z})$ -learner is a $(w_{i},z_{i})$ -learner for every $i=1,\ldots,r$ . Does the converse hold, too? That is, if for each $i=1,\ldots,r$ there exist a $(w_{i},z_{i})$ -learner ${\mathcal{A}}_{i}$ , can we conclude that there exists a $(\boldsymbol{w},\boldsymbol{z})$ -learner ${\mathcal{A}}$ ? Perhaps surprisingly, we can show that this holds if we consider all convex combinations of the scalar guarantees $(w_{i},z_{i})$ . Formally, given a distribution $\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{r})\in\Delta_{r}$ , let $w_{\boldsymbol{\alpha}}=\sum_{i=1}^{r}\alpha_{i}w_{i}$ and $z_{\boldsymbol{\alpha}}=\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle$ . It is easy to see that the observation above continues to hold: a $(\boldsymbol{w},\boldsymbol{z})$ -learner is a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})$ -learner for every such $\boldsymbol{\alpha}$ . The next result shows that the converse holds, too: the existence of a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})$ -learner for every $\boldsymbol{\alpha}\in\Delta_{r}$ implies the existence of a $(\boldsymbol{w},\boldsymbol{z})$ -learner.

Theorem 6 (Equivalence of learners).

Let $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\to[0,1]$ is a cost function, and let $\boldsymbol{z}\in[0,1]^{r}$ . Then, the following are equivalent.

1.

There exists a $(\boldsymbol{w},\boldsymbol{z})$ -learner for $\mathcal{F}$ .
2.

For every $\boldsymbol{\alpha}\in\Delta_{r}$ there exists a $\big{(}w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}}\big{)}$ -learner for $\mathcal{F}$ .

Moreover, the equivalence is obtained constructively by an efficient algorithm.

We remark that Theorem 6 holds in the multiclass case, too (i.e., for arbitrary sets ${\mathcal{Y}}$ ). Thus, the interplay between multi-objective and cost-sensitive learning is a general phenomenon, not limited to binary classifiers. The reduction from multi-objective to cost-sensitive in Theorem 6 resembles the weighted sum scalarization method for multi-objective optimization (Ehrgott, 2005, Chapter 3). However, it is unclear whether this similarity can be used to provide further insights in our problem.

In the same vein as Theorem 6, we prove an equivalence between trivial guarantees of cost-sensitive learners (see A) and trivial guarantees of multi-objective learners (see B).

Theorem 7 (Equivalence of trivial guarantees).

Let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\to[0,1]$ is a cost function, and let $\boldsymbol{z}\in[0,1]^{r}$ . Then the following are equivalent.

1.

$(\boldsymbol{w},\boldsymbol{z})$ is coin-attainable.
2.

For every $\boldsymbol{\alpha}\in\Delta_{r}$ it holds that $z_{\boldsymbol{\alpha}}\geq\operatorname{V}(w_{\boldsymbol{\alpha}})$ .

As Theorem 6, we note that Theorem 7 also holds in the general multiclass case. The proof of Theorem 7 again uses von Neumann’s Minimax Theorem, based on a two-player game that differs from those described earlier. In this game, the pure strategies of the maximizing player are the different elements of $[r]$ , representing the various objectives of the cost function. The proofs of all equivalence theorems are given in Section 4.

2.2 Multiclass setting

For binary classification tasks, we get an especially clean and refined mathematical picture, in which boostability is fully determined by a single threshold, i.e., $\operatorname{V}(w)$ . That is, any learner with loss value below it can be boosted, while any value above it is attainable by a trivial non-boostable learner. In the unweighted case, recent work by Brukhim et al. (2023a) demonstrated that a multichotomy emerges, governed by $k-1$ thresholds: $\frac{1}{2},\frac{2}{3},\dots,\frac{k-1}{k}$ , where $k$ is the number of labels. For each such threshold, any learner achieving a loss below it can be “partially” boosted to the next threshold below it, but not further than that. Here, we extend their results to arbitrary cost functions and prove that a similar phenomenon holds more generally.

In contrast to the unweighted case, the landscape of boostability in the general setting is more complex, consisting of many thresholds corresponding to distinct possible subsets of labels. Interestingly, the thresholds of boostability can be computed precisely, and are all determined by the outcome of zero-sum games, as defined next. We generalize the zero-sum game defined in Equation (2) to the case of $k\geq 2$ labels. It turns out that in the multiclass setting, a more refined zero-sum game is needed, introducing a certain asymmetry between the sets of allowable strategies for each player. In particular, we restrict the set of distributions $\mathbf{q}$ which the maximizing player is allowed to choose. For a subset $J\subseteq{\mathcal{Y}}$ of labels define the value of the game restricted to the subset $J$ as:

\displaystyle\operatorname{V}_{J}(w)\triangleq\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p},\mathbf{q})\;.

(5)

Importantly, only the maximizing player is restricted to $\Delta_{J}$ while the minimizing player is not. Thus, $\operatorname{V}_{J}(w)$ is the smallest loss one can ensure by predicting with a die given that the correct label is in $J$ . Clearly, for every $J^{\prime}\subseteq J$ it holds that $\operatorname{V}_{J^{\prime}}(w)\leq\operatorname{V}_{J}(w)$ . Consider the subsets $J\subseteq{\mathcal{Y}}$ in nondecreasing order of $\operatorname{V}_{J}(w)$ .⁶⁶6For notational easiness we define $\operatorname{V}_{\emptyset}(w)=0$ . We then denote each such cost by $v_{s}(w)$ for some $s\in\{1,\dots,2^{k}\}$ , so that overall we have,

0=v_{1}(w)<v_{2}(w)<\ldots<v_{\tau}(w)=\operatorname{V}_{{\mathcal{Y}}}(w),

(6)

where $\tau\leq 2^{k}$ depends on the cost function $w$ . The first equality holds since $\operatorname{V}_{\{y\}}(w)=0$ for $y\in{\mathcal{Y}}$ . Moreover, by a straightforward calculation it can be shown that, for the unweighted case in which $w$ is simply the 0-1 loss (i.e., $w(i,j)=\mathbb{I}\!\left\{i\neq j\right\}$ ), the thresholds $\operatorname{V}_{J}(w)$ specialize to those given by Brukhim et al. (2023a). Concretely, it is described in the following fact.

Fact 8.

Let $w$ be the 0-1 loss. Then, for every $n\geq 1$ and $J\in{{\mathcal{Y}}\choose n}$ , it holds that $\operatorname{V}_{J}(w)=1-\frac{1}{n}$ .

Thus, for the 0-1 loss we have $\tau=k$ . Note that although for the general case given here there is no closed-form expression for the value of each threshold, it can each be determined by solving for the corresponding linear program representation of the zero-sum game described above.

We can now state our main results on multiclass cost-sensitive boosting, given next.

Theorem C (Cost-sensitive boosting, multiclass case).

Let ${\mathcal{Y}}=[k]$ , let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be any cost function, and let $z\geq 0$ . Let $v_{1}<v_{2}<\cdots<v_{\tau}$ as defined in Equation 6,⁷⁷7When clear from context we omit $w$ and denote a threshold by $v_{n}$ . and let $n$ be the largest integer such that $v_{n}\leq z$ . Then, the following claims both hold.

•

$(w,z)$ is $n$ -boostable: for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , every $(w,z)$ -learner is boostable to $(w,v_{{n}})$ -learner.
•

$(w,z)$ is not $(n-1)$ -boostable: there exists a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ and a $(w,z)$ -learner for $\mathcal{F}$ that cannot be boosted to $(w,z^{\prime})$ -learner for $\mathcal{F}$ , for any $z^{\prime}<v_{n}$ .

The proof of C is given in Section 5. In words, C implies that there is a partition of the interval $[0,1]$ , on which the loss values lie, into at most $\tau$ sub-intervals or “buckets”, based on $v_{{n}}$ . Then, any loss value $z$ in a certain bucket $\bigl{[}v_{{n}},v_{{n+1}}\bigr{)}$ can be boosted to the lowest value within the bucket, but not below that. We remark that, in fact, the above boostability result is obtained constructively via an efficient algorithm, as described in Section 5.

2.2.1 Multiclass classification, multi-objective loss

We shift our focus to multi-objective losses in the multiclass setting. Recall the notion of $(\boldsymbol{w},\boldsymbol{z})$ -learner of Definition 3. Our goal is to prove a multi-objective counterpart of C; that is, to understand for which $\boldsymbol{z}^{\prime}$ a $(\boldsymbol{w},\boldsymbol{z})$ -learner can be boosted to a $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -learner. Unlike the scalar cost setting of C, however, the set of those $\boldsymbol{z}^{\prime}$ that are reachable by boosting a $(\boldsymbol{w},\boldsymbol{z})$ -learner is not a one-dimensional interval in $[0,1]$ , but a subset of $[0,1]^{r}$ .

As a first step, we generalize the notion of coin attainability given by Definition 4. The key ingredient that we shall add is to restrict the distribution of the labels over a given set $J\subseteq{\mathcal{Y}}$ . From the point of view of a random guesser, this amounts to knowing that the correct label must be in $J$ . We then say that a guarantee is $J$ -dice-attainable if a trivial learner can satisfy that guarantee over any distribution supported only over $J$ . Formally, it is defined as follows.

Definition 9 ( $J$ -dice attainability).

Let ${\mathcal{Y}}=[k]$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost function, let $\mathbf{z}\in[0,1]^{r}$ , and let $J\subseteq{\mathcal{Y}}$ . Then $(\boldsymbol{w},\boldsymbol{z})$ is $J$ -dice-attainable if:

\forall\mathbf{q}\in\Delta_{J},\ \exists\mathbf{p}\in\Delta_{\mathcal{Y}},\ \forall i=1,\ldots,r,\qquad w_{i}(\mathbf{p},\mathbf{q})\leq z_{i}\;.

(7)

The $J$ -dice-attainable region of $\boldsymbol{w}$ is the set $D_{J}(\boldsymbol{w})\triangleq\left\{\boldsymbol{z}:(\boldsymbol{w},\boldsymbol{z})\text{ is }J\text{-dice-attainable}\right\}$ .

Intuitively, if $(\boldsymbol{w},\boldsymbol{z})$ is $J$ -dice-attainable, then a $(\boldsymbol{w},\boldsymbol{z})$ -learner is not better than a random die over $J$ , and therefore should not be able to separate any label in $J$ . Using the notion of $J$ -dice-attainability, we define a partial ordering over $[0,1]^{r}$ . For every $\boldsymbol{z},\boldsymbol{z}^{\prime}\in[0,1]^{r}$ write $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ if

\forall J\subseteq{\mathcal{Y}},\ \ \boldsymbol{z}\in D_{J}(\boldsymbol{w})\implies\boldsymbol{z}^{\prime}\in D_{J}(\boldsymbol{w})\,,

(8)

and $\boldsymbol{z}\not\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ otherwise. Intuitively, $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ means that, whenever $\boldsymbol{z}$ is not better than a die, then $\boldsymbol{z}^{\prime}$ is not better than a die either. We prove that this partial ordering precisely characterizes the boostability of $\boldsymbol{z}$ to $\boldsymbol{z}^{\prime}$ . We can now state our main result for multi-objective multiclass boosting.

Theorem D (Multi-objective boosting, multiclass case).

•

$(\boldsymbol{w},\boldsymbol{z})$ is boostable to $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ for every $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ : for every class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , every $(\boldsymbol{w},\boldsymbol{z})$ -learner for $\mathcal{F}$ is boostable to a $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -learner for $\mathcal{F}$ .
•

$(\boldsymbol{w},\boldsymbol{z})$ is not boostable to $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ for every $\boldsymbol{z}\not\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ : there exists a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ and a $(\boldsymbol{w},\boldsymbol{z})$ -learner for $\mathcal{F}$ that is a trivial learner and, therefore, cannot be boosted to a $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -learner for $\mathcal{F}$ , for any $\boldsymbol{z}\not\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ .

Let us elaborate briefly on D. In the multiclass cost-sensitive setting, where the overall cost is a scalar, the landscape of boostability is determined by a sequence of (totally ordered) scalar thresholds $v_{{n}}\in[0,1]$ ; and those thresholds determine whether a $(w,z)$ -learner can be boosted to a $(w,z^{\prime})$ -learner, for $z^{\prime}<z$ , as detailed in C. In the multiclass multi-objective setting, those scalar thresholds are replaced by a set of surfaces in $[0,1]^{r}$ . Each such surface corresponds to the boundary of the dice-attainable sets $D_{J}(\boldsymbol{w})$ . Those surface can be seen as thresholds of a higher-dimensional form, separating between different boostability guarantees.

3 Binary Classification

This section considers the classic binary classification setting, where ${\mathcal{Y}}=\{-1,+1\}$ . Section 3.1 tackles the simplest case, where the cost $w$ is scalar, and explores the conditions that make a $(w,z)$ -learner boostable, proving A. Section 3.2 considers multi-objective costs, where the cost $\boldsymbol{w}$ is vector-valued, for a specific but illustrative choice of $\boldsymbol{w}$ , proving a special case of B and of Theorem 7. The reason for restricting $\boldsymbol{w}$ to a special form is that this allows us to introduce the key ideas while avoiding heavy notation. Finally, in Section 3.4 we give the full proof of B.

For convenience, as ${\mathcal{Y}}=\{-1,+1\}$ , we will sometimes encode a cost function $w:{\mathcal{Y}}^{2}\to[0,1]$ as a 2-by-2 matrix $\bigl{(}\begin{smallmatrix}0&w_{-}\\ w_{+}&0\end{smallmatrix}\bigr{)}$ , where $w_{+}=w(+1,-1)$ is the cost of a false positive and $w_{-}=w(-1,+1)$ the cost of a false negative. We will also use the fact, provable through easy calculations, that the value of the game $\operatorname{V}(w)$ equals $0$ if $\min(w_{-},w_{+})=0$ and $\frac{w_{-}w_{+}}{w_{-}+w_{+}}$ otherwise. Before moving forward, we also need a measure of the advantage that a $(w,z)$ -learner has compared to a coin.

Definition 10 (Margin, binary case).

The margin of a $(w,z)$ -learner is $\gamma\triangleq\max\{0,\operatorname{V}(w)-z\}$ .

When $w_{+}=w_{-}=1$ , and thus $w$ is the standard 0-1 cost, $\gamma$ is the usual notion of margin that defines a weak learner in binary classification tasks. In that case, it is well known that to boost a weak learner with margin $\gamma$ it is necessary and sufficient to invoke the learner a number of times that scales with $\nicefrac{{1}}{{\gamma^{2}}}$ . This remains true for general $w$ and $z$ , in that our boosting algorithm below invokes the $(w,z)$ -learner a number of times proportional to $\nicefrac{{1}}{{\gamma^{2}}}$ .

3.1 Boosting a $(w,z)$ -learner

The main contribution of this subsection is a boosting algorithm, shown in Algorithm 1, that turns any $(w,z)$ -learner ${\mathcal{A}}$ with $z<\operatorname{V}(w)$ into a $(w,0)$ -learner ${\mathcal{A}}^{\prime}$ . We prove:

Theorem 11.

Let ${\mathcal{Y}}=\{-1,+1\}$ and $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . If ${\mathcal{A}}$ is a $(w,z)$ -learner for $\mathcal{F}$ with margin $\gamma>0$ , then Algorithm 1 with the choice of parameters of Lemma 12 is a $(w,0)$ -learner for $\mathcal{F}$ . Under the same assumptions, Algorithm 1 makes $T=O\bigl{(}\frac{\ln(m)}{\gamma^{2}}\bigr{)}$ oracle calls to ${\mathcal{A}}$ , where $m$ is the size of the input sample, and has sample complexity $m(\epsilon,\delta)=\widetilde{O}\Bigl{(}m_{0}\bigl{(}\frac{\gamma}{3},\frac{\delta}{2T}\bigr{)}\cdot\frac{\ln(1/\delta)}{\epsilon\cdot\gamma^{2}}\Bigr{)}$ , where $m_{0}$ is the sample complexity of ${\mathcal{A}}$ .

It is immediate to see that Theorem 11 implies the first item of A; for the second item see Lemma 14 below. In the rest of this subsection we prove Theorem 11. We do so in two steps: first we prove that Algorithm 1 returns a hypothesis consistent with the input sample (Lemma 12), and then we show generalization by a compression argument (Lemma 13).

Algorithm 1 Boosting a binary

(w,z)

-learner

0: sample

S=(x_{i},y_{i})_{i=1}^{m}

;

(w,z)

-learner

{\mathcal{A}}

; parameters

T,\eta,\widehat{m}

1: Initialize:

D_{1}(i)=1

for all

i=1,...,m

2: for

t=1,\ldots,T

3: Compute the distribution

\mathcal{D}_{t}\triangleq\frac{D_{t}}{\sum_{i}D_{t}(i)}

over

[m]

4: Draw a set

S_{t}

\widehat{m}

labeled examples i.i.d. from

\mathcal{D}_{t}

and obtain

h_{t}={\mathcal{A}}(S_{t})

5: For every

i=1,\ldots,m

let:

D_{t+1}(i)\triangleq D_{t}(i)\cdot e^{\eta\cdot w(h_{t}(x_{i}),y_{i})}\;.

6: end for

7: Let

F:{\mathcal{X}}\times{\mathcal{Y}}\to[0,1]

such that

F(x,y)\triangleq\frac{1}{T}\sum_{t=1}^{T}\mathbb{I}\!\left\{h_{t}(x)=y\right\}

for all

x\in{\mathcal{X}},y\in{\mathcal{Y}}

8: return

\widehat{h}_{S}:{\mathcal{X}}\to{\mathcal{Y}}

such that, for all

x\in{\mathcal{X}}

\widehat{h}_{S}(x)\triangleq\begin{cases}+1&\text{if }w_{-}\cdot F(x,-1)<w_{+}\cdot F(x,+1)\;,\\ -1&\text{otherwise.}\end{cases}

At a high level, Algorithm 1 follows standard boosting procedures. Given a $(w,z)$ -learner ${\mathcal{A}}$ and a labeled sample $S$ , Algorithm 1 uses ${\mathcal{A}}$ to obtain a sequence of hypotheses $h_{1},\ldots,h_{T}$ whose average has loss close to $z$ on each single example in $S$ . This can be achieved through any regret-minimizing algorithm, but for the sake of concreteness our algorithm uses a modified version of Hedge (Freund and Schapire, 1997) where the update step re-weights examples as a function of $w$ . Unlike standard approaches, the final prediction on a point $x$ is not just the majority vote of the $h_{t}$ ’s. Instead, the prediction is constructed by comparing the fraction of $h_{t}$ ’s returning $-1$ , weighted by $w_{-}$ , and the fraction of $h_{t}$ ’s returning $+1$ , weighted by $w_{+}$ . The smallest weighted fraction wins, and the corresponding label is returned. We show that this ensures correct labeling of the entire sample with the desired probability. Formally, we have:

Lemma 12.

Let ${\mathcal{Y}}=\{-1,+1\}$ and let $w:{\mathcal{Y}}^{2}\to[0,1]$ be a cost function. Let $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , and let ${\mathcal{A}}$ be a $(w,z)$ -learner for $\mathcal{F}$ with margin $\gamma>0$ and sample complexity $m_{0}$ . Fix any $f\in\mathcal{F}$ , let $\mathcal{D}$ be any distribution over ${\mathcal{X}}$ , and let $S=\{(x_{1},y_{1}),\ldots,(x_{m},y_{m})\}$ be a multiset of $m$ examples given by i.i.d. points $x_{1},\dots,x_{m}\sim\mathcal{D}$ labeled by $f$ . Finally, fix any $\delta\in(0,1)$ . If Algorithm 1 is given $S$ , oracle access to ${\mathcal{A}}$ , and parameters $T=\left\lceil\frac{18\ln(m)}{\gamma^{2}}\right\rceil$ , $\eta=\sqrt{\frac{2\ln(m)}{T}}$ , and $\widehat{m}=m_{0}\bigl{(}\frac{\gamma}{3},\frac{\delta}{T}\bigr{)}$ , then Algorithm 1 makes $T$ calls to ${\mathcal{A}}$ and returns $\widehat{h}_{S}:{\mathcal{X}}\to{\mathcal{Y}}$ such that with probability at least $1-\delta$ :

\widehat{h}_{S}(x_{i})=y_{i}\qquad\forall i=1,\ldots,m\;.

Proof.

Fix any $i\in[m]$ . Given that $\max_{t,i}w(h_{t}(x_{i}),y_{i})\leq 1$ and that $\eta\leq 1$ , the standard analysis of Hedge (Freund and Schapire, 1997) shows that:

\displaystyle\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})

\displaystyle\leq\frac{\ln(m)}{\eta}+\frac{\eta}{2}T+\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\;.

(9)

Dividing both sides by $T$ , and using the definitions of $\eta$ and $T$ at the right-hand side, yields:

\displaystyle\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})

\displaystyle\leq\frac{\gamma}{3}+\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\;.

(10)

For every $t=1,\ldots,T$ , since $h_{t}={\mathcal{A}}(S_{t})$ , since ${\mathcal{A}}$ is a $(w,z)$ -learner for $\mathcal{F}$ , and by the choice of $\widehat{m}$ :

\displaystyle\operatorname{\mathbb{P}}\left({\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}>z+\frac{\gamma}{3}\right)\leq\frac{\delta}{T}\;.

(11)

By averaging over $T$ and taking a union bound over $t=1,\ldots,T$ , we have that, with probability at least $1-\delta$ ,

\displaystyle\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\leq z+\frac{\gamma}{3}\;.

(12)

Now suppose Equation 12 holds. We shall prove that $\widehat{h}_{S}(x_{i})=y_{i}$ for every $i\in[m]$ . First, Equation 10 together with the definition of $\gamma$ implies that for every $i\in[m]$ :

\displaystyle\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})

\displaystyle\leq\frac{2}{3}\gamma+z\leq\operatorname{V}(w)-\frac{\gamma}{3}<\operatorname{V}(w)\;.

(13)

Now recall the definition of $F:{\mathcal{X}}\times{\mathcal{Y}}\to[0,1]$ from Algorithm 1:

\displaystyle F(x,y)=\frac{1}{T}\sum_{t=1}^{T}\mathbb{I}\!\left\{h_{t}(x)=y\right\}\qquad\forall x\in{\mathcal{X}},y\in{\mathcal{Y}}\;.

(14)

Clearly, for any $x\in{\mathcal{X}}$ , we have that $F(x,-1)+F(x,+1)=1$ . Now consider any $i\in[m]$ . If $y_{i}=+1$ then by definition of $w$ and $F$ :

\displaystyle\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})=w_{-}\cdot\frac{1}{T}\sum_{t=1}^{T}\mathbb{I}\!\left\{h_{t}(x_{i})=-1\right\}=w_{-}\cdot F(x_{i},-1)\;.

(15)

By Equation 13, then, $w_{-}\cdot F(x_{i},-1)<\operatorname{V}(w)$ . By a symmetric argument $w_{+}\cdot F(x_{i},+1)<\operatorname{V}(w)$ if $y_{i}=-1$ . It remains to show that for every $x\in{\mathcal{X}}$ exactly one among $w_{-}\cdot F(x,-1)<\operatorname{V}(w)$ and $w_{+}\cdot F(x,+1)<\operatorname{V}(w)$ holds. As we have just shown, at least one of the inequalities holds, depending on the value of $y_{i}$ . Now assume towards contradiction that both hold. Recall that $\operatorname{V}(w)=\frac{w_{-}w_{+}}{w_{-}+w_{+}}$ . Note that $\gamma>0$ implies $\operatorname{V}(w)>0$ and thus $w_{-},w_{+}>0$ . Then we have:

\displaystyle 1=F(x,-1)+F(x,+1)<\frac{\operatorname{V}(w)}{w_{-}}+\frac{\operatorname{V}(w)}{w_{+}}=\frac{w_{+}}{w_{-}+w_{+}}+\frac{w_{-}}{w_{-}+w_{+}}=1\;.

(16)

By definition of $\widehat{h}_{S}$ then $\widehat{h}_{S}(x_{i})=y_{i}$ for all $i\in[m]$ , concluding the proof. ∎

The next lemma shows that, if the size $m$ of the sample in Lemma 12 is large enough, then the hypothesis returned by Algorithm 1 has small generalization error. It is immediate to see that, together with Lemma 12, this implies Theorem 11.

Lemma 13.

Assume the hypotheses of Lemma 12. For any $\epsilon,\delta\in(0,1)$ , if the size $m$ of the sample given to Algorithm 1 satisfies

m\geq\frac{\ln(2/\delta)}{\epsilon}+m_{0}\left(\frac{\gamma}{3},\frac{\delta}{2T}\right)\cdot T\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)\;,

then with probability at least $1-\delta$ the output $\widehat{h}_{S}$ of Algorithm 1 satisfies $L_{\mathcal{D}}^{w}(\widehat{h}_{S})\leq\epsilon$ . Therefore, Algorithm 1 is a $(w,0)$ -learner for $\mathcal{F}$ with sample complexity $m(\epsilon,\delta)=\widetilde{O}\Bigl{(}m_{0}\bigl{(}\frac{\gamma}{3},\frac{\delta}{2T}\bigr{)}\cdot\frac{\ln(1/\delta)}{\epsilon\cdot\gamma^{2}}\Bigr{)}$ .

Proof.

First, we apply Lemma 12 with $\delta/2$ in place of $\delta$ ; we obtain that, with probability at least $1-\delta/2$ , the hypothesis $\widehat{h}_{S}$ is consistent with the labeled sample $S$ . Next, we apply a standard compression-based generalization argument (see e.g., Theorem 2.8 from Schapire and Freund (2012)). To this end, note that one can construct a compression scheme for $\widehat{h}_{S}$ of size $\kappa$ equal to the total size of the samples on which ${\mathcal{A}}$ is invoked, that is, $\kappa=\widehat{m}\cdot T$ . By Theorem 2.8 from Schapire and Freund (2012) with $\delta/2$ in place of $\delta$ we get that, with probability at least $1-\delta/2$ ,

\displaystyle L_{\mathcal{D}}^{w}(\widehat{h}_{S})\leq\frac{\kappa\ln(m)+\ln(2/\delta)}{m-\kappa}\;.

(17)

Straightforward calculations show that the right-hand side is at most $\epsilon$ whenever:

	$\displaystyle m$	$\displaystyle\geq\frac{\ln(2/\delta)}{\epsilon}+\kappa\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)$		(18)
		$\displaystyle=\frac{\ln(2/\delta)}{\epsilon}+m_{0}\left(\frac{\gamma}{3},\frac{\delta}{2T}\right)\cdot T\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)\;.$		(19)

A union bound completes the first part of the claim, and shows that Algorithm 1 is a $(w,0)$ -learner for $\mathcal{F}$ . The condition on the sample complexity of Algorithm 1 then follows immediately by definition of $T=O\bigl{(}\frac{\ln(m)}{\gamma^{2}}\bigr{)}$ . ∎

Remark on adaptive boosting.

Traditional boosting algorithms, such as the well-known AdaBoost (Schapire and Freund, 2012), do not assume prior knowledge of the margin parameter $\gamma$ and adapt to it dynamically during execution. In contrast, the boosting algorithm in Algorithm 1, along with our broader approach, requires an initial estimate of $\gamma$ as input. If this estimate is too large, the algorithm may fail. However, this issue can be addressed through a straightforward binary search procedure: we iteratively adjust our guess, halving it when necessary based on observed outcomes. This adds only a logarithmic overhead of $O(\ln(1/\gamma))$ to the runtime, without affecting sample complexity bounds.

We conclude this subsection with a proof of the second part of A.

Lemma 14.

Let ${\mathcal{X}}$ be any domain, let ${\mathcal{Y}}=\{-1,+1\}$ , and let $w=(w_{+},w_{-})\in(0,1]^{2}$ be a cost over ${\mathcal{Y}}$ . If $z\geq\operatorname{V}(w)$ , then there is an algorithm that is a $(w,z)$ -learner for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . Moreover, for some domain ${\mathcal{X}}$ and some $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ the said learner cannot be boosted to a $(w,z^{\prime})$ -learner for any $z^{\prime}<\operatorname{V}(w)$ .

Proof.

By definition of $\operatorname{V}(w)$ there exists a distribution $\mathbf{p}\in\Delta_{\mathcal{Y}}$ such that $w(\mathbf{p},\mathbf{q})\leq\operatorname{V}(w)$ for every $\mathbf{q}\in\Delta_{\mathcal{Y}}$ over ${\mathcal{Y}}$ . Consider then the algorithm that ignores the input and returns a randomized predictor $h_{\mathbf{p}}$ such that $h_{\mathbf{p}}(x)\sim\mathbf{p}$ independently for every given $\mathbf{x}\in{\mathcal{X}}$ . Clearly, for every distribution $\mathcal{D}$ over ${\mathcal{X}}$ ,

\displaystyle L_{\mathcal{D}}^{w}(h_{\mathbf{p}})\leq w(\mathbf{p},\mathbf{q})\leq\operatorname{V}(w)\;,

(20)

where $\mathbf{q}$ is the marginal of $\mathcal{D}$ over ${\mathcal{Y}}$ . This proves that the algorithm is a $(w,z)$ -learner for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . Let us now show that for some $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ cannot be boosted to a $(w,z^{\prime})$ -learner for any $z^{\prime}<\operatorname{V}(w)$ . If $\operatorname{V}(w)=0$ then this is trivial, as $w\geq 0$ ; thus we can assume $\operatorname{V}(w)>0$ . Suppose then that a $(w,z^{\prime})$ -learner for $\mathcal{F}$ exists, where $z^{\prime}<\operatorname{V}(w)$ . By item (1), it follows that a $(w,0)$ -learner for $\mathcal{F}$ exists. Recall that $\operatorname{V}(w)=\frac{w_{-}w_{+}}{w_{-}+w_{+}}$ . Since we assumed $\operatorname{V}(w)>0$ , it follows that $w_{-},w_{+}>0$ . Then, a $(w,0)$ -learner is a strong learner in the PAC sense. Now choose $\mathcal{F}$ to be any non-learnable class; for instance, let $\mathcal{F}={\mathcal{Y}}{N}$ (see Shalev-Shwartz and Ben-David (2014, Theorem 5.1)). Then, no strong PAC learner and therefore no $(w,0)$ -learner exists for $\mathcal{F}$ . Hence a $(w,z^{\prime})$ -learner for $\mathcal{F}$ with $z^{\prime}<\operatorname{V}(w)$ does not exist, too. ∎

3.2 Multi-objective losses: boosting a $(\boldsymbol{w},\mathbf{z})$ -learner

This section considers the boosting problem for learners that satisfy multi-objective costs, as captured by the notion of $(\boldsymbol{w},\mathbf{z})$ -learners (Definition 3). Our main question is then:

When can a $(\boldsymbol{w},\mathbf{z})$ -learner be boosted to a $(\boldsymbol{w},\mathbf{0})$ -learner?

For the scalar case, we showed in Section 3.1 that the threshold to boost $(w,z)$ -learners is the value of the game $\operatorname{V}(w)$ , which is the best bound on $w$ one can achieve by just tossing a coin—independently of the example $x$ at hand, and even of the specific distribution $\mathcal{D}$ over ${\mathcal{X}}$ . One may thus guess that the same characterization holds for boosting $(\boldsymbol{w},\mathbf{z})$ -learners. It turns out that this guess fails, as we show below. We thus adopt a different and stronger notion of “trivial learner”, obtained by exchanging the order of the players. It turns out that this is the right notion, in the sense that it is equivalent to being non-boostable.

For the sake of simplicity we assume a specific $\boldsymbol{w}$ that we call population-driven cost. This will help conveying the key ideas, without having to deal with the technical details of the more general version of our results (Section 5). The population-driven cost is the one that counts, separately, false negatives and false positives. More precisely, $\boldsymbol{w}=(w_{-},w_{+})$ where $w_{-}$ and $w_{+}$ are now two cost functions that for all $i,j\in{\mathcal{Y}}$ satisfy:

	$\displaystyle w_{-}(i,j)$	$\displaystyle=\mathbb{I}\!\left\{i=-1\land j=+1\right\}\;,$		(21)
	$\displaystyle w_{+}(i,j)$	$\displaystyle=\mathbb{I}\!\left\{i=+1\land j=-1\right\}\;.$		(22)

For $\mathbf{z}=(z_{-},z_{+})\in\mathbb{R}_{\geq 0}^{2}$ , a $(\boldsymbol{w},\mathbf{z})$ -learner then ensures simultaneously a false-negative rate arbitrarily close to $z_{-}$ and a false-positive rate arbitrarily close to $z_{+}$ .

3.2.1 Coin attainability

Let $\boldsymbol{w}$ as above, and let $\mathbf{z}\in\mathbb{R}_{\geq 0}^{2}$ . As a first attempt at answering our question above, we guess that $\mathbf{z}$ is non-boostable when it is attainable by a random coin toss in the same way as for scalar costs (Section 3.1). That is, we may say that $\mathbf{z}$ is trivially attainable w.r.t. $\boldsymbol{w}$ if there exists $\mathbf{p}\in\Delta_{\mathcal{Y}}$ such that for every $\mathbf{q}\in\Delta_{\mathcal{Y}}$ we have $\boldsymbol{w}(\mathbf{p},\mathbf{q})\leq\mathbf{z}$ . Clearly, for any such $\mathbf{z}$ there would exist a $(\boldsymbol{w},\mathbf{z})$ -learner that is not boostable for some class $\mathcal{F}$ . If we could also prove the converse, that any $\mathbf{z}$ not trivially attainable is boostable, then we would have determined that trivial attainability is equivalent non-boostability.

Unfortunately, this turns out to be false. To see why, fix any distribution $\mathbf{p}=(p_{-},p_{+})$ . Define then $\mathbf{q}=(q_{-},q_{+})$ as follows: if $p_{-}\geq\nicefrac{{1}}{{2}}$ then $q_{-}=0$ , otherwise $q_{+}=0$ . It follows immediately that either $p_{-}(1-q_{-})\geq\nicefrac{{1}}{{2}}$ or $p_{+}(1-q_{+})\geq\nicefrac{{1}}{{2}}$ . That is, $\boldsymbol{w}(\mathbf{p},\mathbf{q})$ is at least $\nicefrac{{1}}{{2}}$ in at least one coordinate. As a consequence, no $\mathbf{z}<(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$ is trivially attainable. Thus, if our guess is correct, it should be the case that any $(\boldsymbol{w},\mathbf{z})$ -learner with $\mathbf{z}<(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$ is boostable.

We can easily show that that is not the case. Let $\mathbf{z}=(\nicefrac{{1}}{{4}},\nicefrac{{1}}{{4}})$ and consider the following $(\boldsymbol{w},\mathbf{z})$ -learner. Upon receiving a sufficiently large labeled sample from some distribution $\mathcal{D}$ over ${\mathcal{X}}$ , the learner computes an estimate $\hat{\mathbf{q}}=(\hat{q}_{-},\hat{q}_{+})$ of the marginal of $\mathcal{D}$ over ${\mathcal{Y}}$ . The learner then computes $\mathbf{p}=(p_{-},p_{+})$ that satisfies:

\displaystyle p_{-}\cdot(1-\hat{q}_{-})\leq\frac{1}{4}\quad\text{and}\quad p_{+}\cdot(1-\hat{q}_{+})\leq\frac{1}{4}\;.

(23)

It is not hard to show that such a $\mathbf{p}$ always exists. The learner thus outputs $h$ such that $h(x)\sim\mathbf{p}$ for all $x\in{\mathcal{X}}$ independently. As the number of samples received by the learner increases, the estimate $\hat{\mathbf{q}}$ approaches $\mathbf{q}$ , and thus the loss of the learner approaches $\mathbf{z}$ . Clearly, however, such a learner cannot be boosted, as its predictions are independent of the example $x$ at hand. We conclude that there exist $\mathbf{z}$ that are not trivially attainable and yet are not boostable.

The example above suggest a fix to our notion of “non-boostable learner”. The fix consists in considering again prediction by a coin $\mathbf{p}$ , where, however, we allow $\mathbf{p}$ to be a function of $\mathbf{q}$ . This leads to the following definition:

Definition 15.

Let $\boldsymbol{w}=(w_{-},w_{+})$ be the population-driven cost and let $\mathbf{z}=(z_{-},z_{+})\in\mathbb{R}_{\geq 0}^{2}$ . Then, $\mathbf{z}$ is coin-attainable w.r.t. $\boldsymbol{w}$ if for every distribution $\mathbf{q}=(q_{-},q_{+})$ there exists a distribution $\mathbf{p}=(p_{-},p_{+})$ such that:

w_{-}(\mathbf{p},\mathbf{q})=p_{-}\cdot(1-q_{-})\leq z_{-}\quad\text{and}\quad w_{+}(\mathbf{p},\mathbf{q})=p_{+}\cdot(1-q_{+})\leq z_{+}\;.

Note how Definition 15 mirrors the game of Section 3.1, but with a reverted order of the players: here, the predictor plays second. It should be clear that, if $\mathbf{z}$ is coin-attainable, then there exists a $(\boldsymbol{w},\mathbf{z})$ -learner that is not boostable. That is the learner described above, which gets an estimate $\hat{\mathbf{q}}$ of $\mathbf{q}$ from the sample, and then returns $h$ such that $h(x)\sim\mathbf{p}$ , where $\mathbf{p}$ satisfies the condition in Definition 15 with respect to $\hat{\mathbf{q}}$ . What is not clear is whether the converse holds, too: is a $(\boldsymbol{w},\mathbf{z})$ -learner boostable whenever $\mathbf{z}$ is not coin-attainable? It turns out that this is the case, as the next subsection shows.

3.2.2 Coin-attainability equals non-boostability

Let us try to boost a $(\boldsymbol{w},\mathbf{z})$ -learner ${\mathcal{A}}$ . We can do so by reduction to the scalar case of Section 3.1. To this end choose any $\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2})\in\Delta_{\mathcal{Y}}$ . Define $\boldsymbol{\alpha}\cdot\boldsymbol{w}:{\mathcal{Y}}^{2}\to\mathbb{R}_{\geq 0}$ by:

\displaystyle(\boldsymbol{\alpha}\cdot\boldsymbol{w})(i,j)=\alpha_{1}\cdot w_{-}(i,j)+\alpha_{2}\cdot w_{+}(i,j)\qquad\forall i,j\in{\mathcal{Y}}\;.

(24)

For conciseness we shall write $w=\boldsymbol{\alpha}\cdot\boldsymbol{w}$ . In words, $w$ is the convex combination of $w_{-},w_{+}$ according to $\boldsymbol{\alpha}$ , and therefore $w=\bigl{(}\begin{smallmatrix}0&\alpha_{1}\\ \alpha_{2}&0\end{smallmatrix}\bigr{)}$ . Therefore $w:{\mathcal{Y}}^{2}\to[0,1]$ and $w(i,i)=0$ for each $i\in{\mathcal{Y}}$ . Now let $z=\boldsymbol{\alpha}\cdot\mathbf{z}$ . Now we make the following crucial observation: since ${\mathcal{A}}$ is a $(\boldsymbol{w},\mathbf{z})$ -learner, then it is also a $(w,z)$ -learner. This is immediate to see from the definition of $(\boldsymbol{w},\mathbf{z})$ and the definition of $w$ . It follows that, by the results of Section 3.1, ${\mathcal{A}}$ can be boosted if $z<\operatorname{V}(w)$ . Summarizing, we can boost ${\mathcal{A}}$ whenever:

\displaystyle\boldsymbol{\alpha}\cdot\mathbf{z}<\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})\;.

(25)

That is, if there is any $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ satisfying Equation 25, then ${\mathcal{A}}$ can be boosted to a strong learner. Moreover, if that is the case, then one can prove that one can ensure $\boldsymbol{\alpha}>\mathbf{0}$ . Then, one can easily see that ${\mathcal{A}}^{*}$ is a $(\boldsymbol{w},\mathbf{0})$ -learner. Our main question thus becomes:

Is it true that, if $\mathbf{z}$ is not coin-attainable, then there is $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ such that $\boldsymbol{\alpha}\cdot\mathbf{z}<\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ ?

We show that this is indeed the case, and therefore $\mathbf{z}$ is coin-attainable if and only if $\boldsymbol{\alpha}\cdot\mathbf{z}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ for all $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ . Equivalently, all $(\boldsymbol{w},\mathbf{z})$ -learners are boostable if and only if $\boldsymbol{\alpha}\cdot\mathbf{z}<\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ for some $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ . As a consequence, every $\mathbf{z}$ is either coin-attainable or boostable. Formally, we have:

Theorem 16.

Let ${\mathcal{Y}}=\{-1,+1\}$ , let $\boldsymbol{w}$ be the population-driven cost, and let $\mathbf{z}=(z_{-},z_{+})\in\mathbb{R}_{\geq 0}^{2}\setminus\mathbf{0}$ . Then $\mathbf{z}$ is coin-attainable w.r.t. $\boldsymbol{w}$ if and only if $\boldsymbol{\alpha}\cdot\mathbf{z}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ , where:

\displaystyle\boldsymbol{\alpha}=\left(\frac{\sqrt{z_{+}}}{\sqrt{z_{-}}+\sqrt{z_{+}}},\frac{\sqrt{z_{-}}}{\sqrt{z_{-}}+\sqrt{z_{+}}}\right)\in\Delta_{\mathcal{Y}}\,.

(26)

Equivalently, $\mathbf{z}$ is coin-attainable w.r.t. $\boldsymbol{w}$ if and only if $\sqrt{z_{-}}+\sqrt{z_{+}}\geq 1$ .

Proof.

First of all, by straightforward calculations we determine:

	$\displaystyle\boldsymbol{\alpha}\cdot\mathbf{z}$	$\displaystyle=\sqrt{z_{-}}\sqrt{z_{+}}\;,$		(27)
	$\displaystyle\operatorname{V}\left(\boldsymbol{\alpha}\cdot\boldsymbol{w}\right)$	$\displaystyle=\operatorname{V}\left(\begin{smallmatrix}0&\alpha_{1}\\ \alpha_{2}&0\end{smallmatrix}\right)=\frac{\sqrt{z_{-}}\sqrt{z_{+}}}{\sqrt{z_{-}}+\sqrt{z_{+}}}\;.$		(28)

This proves that $\boldsymbol{\alpha}\cdot\mathbf{z}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ if and only if $\sqrt{z_{-}}+\sqrt{z_{+}}\geq 1$ .

Now, for the “only if” direction, by von Neumann’s minimax theorem and by definition of $\boldsymbol{\alpha}$ ,

	$\displaystyle V(\boldsymbol{\alpha}\cdot\boldsymbol{w})$	$\displaystyle=\max_{\mathbf{q}\in\Delta_{\mathcal{Y}}}\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\frac{\sqrt{z_{+}}}{\sqrt{z_{-}}+\sqrt{z_{+}}}\cdot p_{-}\cdot(1-q_{-})+\frac{\sqrt{z_{-}}}{\sqrt{z_{-}}+\sqrt{z_{+}}}\cdot p_{+}\cdot(1-q_{+})$		(29)
		$\displaystyle\leq\frac{\sqrt{z_{+}}\cdot z_{-}}{\sqrt{z_{-}}+\sqrt{z_{+}}}+\frac{\sqrt{z_{-}}\cdot z_{+}}{\sqrt{z_{-}}+\sqrt{z_{+}}}=\sqrt{z_{-}}\sqrt{z_{+}}=\boldsymbol{\alpha}\cdot\mathbf{z}\;,$		(30)

where the inequality holds as $\mathbf{z}$ is coin-attainable.

For the “if” direction, suppose $\boldsymbol{\alpha}\cdot\mathbf{z}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ , hence $\sqrt{z_{-}}+\sqrt{z_{+}}\geq 1$ . We claim that this implies $\mathbf{z}$ is coin-attainable. Fix indeed any $\mathbf{q}=(q_{-},q_{+})\in\Delta_{\mathcal{Y}}$ . We consider three cases: (1) $q_{+}\leq z_{-}$ , (2) $q_{-}\leq z_{+}$ , and (3) $q_{+}>z_{-}$ and $q_{-}>z_{+}$ . If $q_{+}\leq z_{-}$ then choose $\mathbf{p}=(1,0)$ , otherwise if $q_{-}\leq z_{+}$ choose $\mathbf{p}=(0,1)$ . It is immediate to see that this implies $p_{-}\cdot(1-q_{-})\leq z_{-}$ and $p_{+}\cdot(1-q_{+})\leq z_{+}$ . Suppose then $q_{+}>z_{-}$ and $q_{-}>z_{+}$ , which implies $\mathbf{q}>\mathbf{0}$ . We claim that:

\displaystyle\frac{z_{-}}{q_{+}}+\frac{z_{+}}{q_{-}}\geq 1\;.

(31)

Indeed, letting $a=z_{-}$ , $b=z_{+}$ , $x=q_{+}$ , multiplying both sides by $x(1-x)$ , and rearranging yields:

\displaystyle a\cdot(1-x)+b\cdot x-x(1-x)\geq 0\;,

(32)

which can be easily checked to hold for all $x$ whenever $\sqrt{a}+\sqrt{b}\geq 1$ . Equation 31 then implies the existence of $p_{-},p_{+}$ such that $p_{-}+p_{+}=1$ and that:

	$\displaystyle p_{-}\cdot(1-q_{-})$	$\displaystyle\leq\frac{z_{-}}{q_{+}}\cdot(1-q_{-})=z_{-}\;,$		(33)
	$\displaystyle p_{+}\cdot(1-q_{+})$	$\displaystyle\leq\frac{z_{+}}{q_{-}}\cdot(1-q_{+})=z_{+}\;.$		(34)

We conclude that $\mathbf{z}$ is coin-attainable. ∎

3.3 A duality, and a geometric interpretation

Theorem 16 has an interesting geometric interpretation. In fact, one can easily check that for every $\mathbf{z}\in\mathbb{R}_{\geq 0}^{2}$ it holds that $\sqrt{z_{-}}+\sqrt{z_{+}}\geq 1$ if and only if $\boldsymbol{\alpha}\cdot\mathbf{z}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ for every $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ , and not just for the single $\boldsymbol{\alpha}$ specified in Theorem 16. That is, we have:

Theorem 17.

Let ${\mathcal{Y}}=\{-1,+1\}$ , let $\boldsymbol{w}$ be the population-driven cost, and let $\mathbf{z}\in\mathbb{R}_{\geq 0}^{2}$ . Then $\mathbf{z}$ is coin-attainable w.r.t. $\boldsymbol{w}$ if and only if $\boldsymbol{\alpha}\cdot\mathbf{z}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})$ for every $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ .

Theorem 17 says that $\mathbf{z}$ is coin-attainable if and only if there is no way to “scalarize” $\boldsymbol{w}$ so as to obtain a boostable learner w.r.t. the corresponding scalarized cost $z$ . From a geometric perspective, the result can be read as follows. For any $\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}$ consider the following halfspace:

\displaystyle H(\boldsymbol{\alpha})=\{{\boldsymbol{x}}\in\mathbb{R}^{2}\,:\,\boldsymbol{\alpha}\cdot{\boldsymbol{x}}\geq\operatorname{V}(\boldsymbol{\alpha}\cdot\boldsymbol{w})\}\;.

(35)

Let moreover $C(\boldsymbol{w})$ be the set of all $\mathbf{z}$ that are coin-attainable w.r.t. $\boldsymbol{w}$ . Then Theorem 17 says:

\displaystyle C(\boldsymbol{w})=\bigcap_{\boldsymbol{\alpha}\in\Delta_{\mathcal{Y}}}H(\boldsymbol{\alpha})\;.

(36)

In other words, the set of coin-attainable vectors is precisely the intersection of all halfspaces $H(\boldsymbol{\alpha})$ . It follows that $C(\boldsymbol{w})$ is convex: and, indeed, if two vectors $\mathbf{z}$ and $\mathbf{z}^{\prime}$ are both coin-attainable then it is easy to see that $a\cdot\mathbf{z}+(1-a)\cdot\mathbf{z}^{\prime}$ is coin-attainable, too, for every $a\in[0,1]$ . Figure 3 gives a pictorial description of this geometric interpretation. The proof of Theorem 17 is not given here, as it is a special case, for $\boldsymbol{w}$ being the population-driven cost, of Theorem 7.

3.4 Proof of B

First item. The proof makes use of the duality results of Section 4. Assume $(\boldsymbol{w},\boldsymbol{z})\notin C(\boldsymbol{w})$ ; that is, $\mathbf{z}$ is not coin-attainable with respect to $\boldsymbol{w}$ . By Theorem 17 there exists $\boldsymbol{\alpha}\in\Delta_{r}$ such that $z_{\boldsymbol{\alpha}}<\operatorname{V}(w_{\boldsymbol{\alpha}})$ , where $w_{\boldsymbol{\alpha}}=\sum_{i=1}^{r}\alpha_{i}w_{i}$ . Thus, ${\mathcal{A}}$ is a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})$ -learner for $\mathcal{F}$ . By Lemma 14, then, there exists a $(w_{\boldsymbol{\alpha}},0)$ -learner for $\mathcal{F}$ . It is immediate to see that, if $\boldsymbol{\alpha}>\mathbf{0}$ (that is, $\alpha_{\ell}>0$ for every $\ell\in[r]$ ) then it is a $(w,0)$ -learner for $\mathcal{F}$ . Thus, we need only to show that we can always assume $\boldsymbol{\alpha}>\mathbf{0}$ . Let

\displaystyle\boldsymbol{\alpha}(\epsilon)=(1-\epsilon)\boldsymbol{\alpha}+\frac{\epsilon}{r}\cdot\mathbf{1}\quad\forall\epsilon\in[0,1]\,.

(37)

Note that both $z_{\boldsymbol{\alpha}(\epsilon)}$ and $\operatorname{V}(w_{\boldsymbol{\alpha}(\epsilon)})$ are continuous functions of $\epsilon$ . Since $z_{\boldsymbol{\alpha}(0)}=z_{\boldsymbol{\alpha}}<\operatorname{V}(w_{\boldsymbol{\alpha}})=\operatorname{V}(w_{\boldsymbol{\alpha}(0)})$ , it follows that there exists $\epsilon>0$ such that $z_{\boldsymbol{\alpha}(\epsilon)}<\operatorname{V}(w_{\boldsymbol{\alpha}(\epsilon)})$ , too.

Second item. We show that, if $\mathbf{z}\in C(\boldsymbol{w})$ , then there is a trivial learner ${\mathcal{A}}$ that is a $(\boldsymbol{w},\mathbf{z})$ -learner for every $\mathcal{F}={\mathcal{Y}}^{\mathcal{X}}$ . By choosing $\mathcal{F}$ to be any non-learnable class this implies that ${\mathcal{A}}$ is not boostable to a $(\boldsymbol{w},\mathbf{z}^{\prime})$ -learner for $\mathcal{F}$ for any $\mathbf{z}^{\prime}\notin C(\boldsymbol{w})$ , for otherwise the first item above would imply the existence of a $(\boldsymbol{w},\mathbf{0})$ -learner for $\mathcal{F}$ . The learner ${\mathcal{A}}$ works as follows. Given a sample $S$ of $m$ examples drawn i.i.d. from $\mathcal{D}$ and labeled by any $f:{\mathcal{X}}\to{\mathcal{Y}}$ , it estimates the marginal $\mathbf{q}$ of $\mathcal{D}$ on ${\mathcal{Y}}$ . Denote that estimate by $\hat{\mathbf{q}}$ . It is well known that ${\mathcal{A}}$ can ensure $\hat{\mathbf{q}}$ is within total variation distance $\epsilon$ of $\mathbf{q}$ with probability at least $1-\delta$ by taking $m=\Theta\bigl{(}\frac{k+\ln(1/\delta)}{\epsilon^{2}}\bigr{)}$ , see for instance (Canonne, 2020, Theorem 1). Assume then this is the case. Let $\mathbf{p}\in\Delta$ be a distribution such that $\boldsymbol{w}(\mathbf{p},\hat{\mathbf{q}})\leq\mathbf{z}$ ; note that $\mathbf{p}$ exists by definition of coin attainability. Then, ${\mathcal{A}}$ returns a randomized predictor $h_{S}:{\mathcal{X}}\to{\mathcal{Y}}$ such that $h_{S}(x)\sim\mathbf{p}$ independently of the input $x$ . Since $\boldsymbol{w}\in[0,1]^{r}$ , then,

\displaystyle L_{\mathcal{D}}^{\boldsymbol{w}}(h_{S})\leq\boldsymbol{w}(\mathbf{q},\hat{\mathbf{q}})+\epsilon\cdot\mathbf{1}=\mathbf{z}+\epsilon\cdot\mathbf{1}\,.

(38)

This proves that ${\mathcal{A}}$ is a $(\boldsymbol{w},\mathbf{z})$ -learner.

4 Equivalence: Cost-Sensitive and Multi-Objective

In this section we examine the connection between cost-sensitive and multi-objective learning. In particular, we prove the two equivalence theorems: Theorem 6 which demonstrates a certain equivalence between learning algorithms for a class $\mathcal{F}$ , with respect to these different guarantees, and Theorem 7, which characterizes trivial guarantees in both settings.

The following lemma is the key component used to prove Theorem 7.

Lemma 18.

Let $r\in\mathbb{N}$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\to[0,1]$ is a cost function, and let $\boldsymbol{z}\in[0,1]^{r}$ . Fix any $J\subseteq{\mathcal{Y}}$ , and $\mathbf{q}\in\Delta_{J}$ . Let ${\mathcal{H}}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ be some fixed hypotheses class. Assume that for every $\boldsymbol{\alpha}\in\Delta_{r}$ , there exists $\mathbf{p}\in\Delta_{\mathcal{H}}$ such that $\sum_{i=1}^{r}\alpha_{i}\cdot w_{i}(\mathbf{p},\mathbf{q})\leq\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle$ . Then, there exists $\mathbf{p}^{*}\in\Delta_{\mathcal{H}}$ such that for all $i=1,...,r$ , it holds that $w_{i}(\mathbf{p}^{*},\mathbf{q})\leq z_{i}$ .

Proof.

Define the following zero-sum game. The pure strategies of the maximizing player are $[r]$ , and the pure strategies minimizing player are ${\mathcal{Y}}$ . The payoff matrix is given as follows, with rows corresponding to labels $\ell\in{\mathcal{Y}}$ and columns to loss-entry $i\in[r]$ ,

M(\ell,i)={\mathbb E}_{j\sim\mathbf{q}}\ w_{i}(\ell,j)-z_{i}.

(39)

Thus, we have,

M(\mathbf{p},\boldsymbol{\alpha})\triangleq{\mathbb E}_{\ell\sim\mathbf{p}}\ {\mathbb E}_{i\sim\boldsymbol{\alpha}}\ M(\ell,i)=\sum_{i=1}^{r}\alpha_{i}w_{i}(\mathbf{p},\mathbf{q})-\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle.

(40)

Denote,

\displaystyle\operatorname{V}(\mathbf{q})\triangleq\max_{\boldsymbol{\alpha}\in\Delta_{r}}\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}M(\mathbf{p},\boldsymbol{\alpha}).

(41)

It remains to show that there exists $\mathbf{p}$ such for all $i=1,...,r$ , we have $w_{i}(\mathbf{p},\mathbf{q})\leq z_{i}$ . By assumption, we know that $\operatorname{V}(\mathbf{q})\leq 0$ , and so by von Neumann’s minimax theorem (von Neumann, 1928) we have:

\displaystyle\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\max_{\boldsymbol{\alpha}\in\Delta_{r}}M(\mathbf{p},\boldsymbol{\alpha})\leq 0.

(42)

In particular, there exists $\mathbf{p}^{*}\in\Delta_{\mathcal{Y}}$ such that for all $\boldsymbol{\alpha}\in\Delta_{r}$ it holds that:

\sum_{i=1}^{r}\alpha_{i}w_{i}(\mathbf{p}^{*},\mathbf{q})\leq\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle.

Observe that the above holds for all $\boldsymbol{\alpha}$ of the form $\mathbf{e}_{i}$ for $i=1,...,r$ (i.e., the standard basis of $\mathbb{R}^{r}$ ), and so we get the desired result. ∎

Proposition 19.

Let $r\in\mathbb{N}$ , and let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\to[0,1]$ is a cost function, $\boldsymbol{z}\in[0,1]^{r}$ , and $J\subseteq{\mathcal{Y}}$ . Then, the following are equivalent.

1.

$(\boldsymbol{w},\boldsymbol{z})$ is $J$ -dice-attainable.
2.

$\forall\boldsymbol{\alpha}\in\Delta_{r}$ , it holds that $\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle\geq\operatorname{V}_{J}(w_{\boldsymbol{\alpha}})$ , where $w_{\boldsymbol{\alpha}}=\sum_{i=1}^{r}\alpha_{i}w_{i}$ .

Next, we prove Proposition 19, which also proves Theorem 7 as a special case.

Proof of Proposition 19.

It is easy to see that $1\implies 2$ holds, by definitions. We prove $2\implies 1$ . By assumption, for every $\boldsymbol{\alpha}\in\Delta_{r}$ it holds that,

\operatorname{V}_{J}(w_{\boldsymbol{\alpha}})=\max_{\mathbf{q}\in{\Delta_{J}}}\min_{\mathbf{p}\in\Delta_{{\mathcal{Y}}}}\sum_{i=1}^{r}\alpha_{i}\cdot w_{i}(\mathbf{p},\mathbf{q})\leq\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle.

(43)

In particular, this implies that for any $\mathbf{q}\in\Delta_{J}$ and any $\boldsymbol{\alpha}\in\Delta_{r}$ , there exists $\mathbf{p}\in\Delta_{\mathcal{Y}}$ such that

\sum_{i=1}^{r}\alpha_{i}\cdot w_{i}(\mathbf{p},\mathbf{q})\leq\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle.

Thus, by Lemma 18 we get that for any $\mathbf{q}\in\Delta_{J}$ , there exists $\mathbf{p}^{*}\in\Delta_{\mathcal{Y}}$ such that for every $i\in[r]$ ,

w_{i}(\mathbf{p}^{*},\mathbf{q})\leq z_{i}.

Thus, we get that $(\boldsymbol{w},\boldsymbol{z})$ is $J$ -dice-attainable. ∎

We shift our focus to general learning algorithms for a class $\mathcal{F}$ . First, recall that a multi-objective learner is, by definition, also a cost-sensitive learner. The existence of a $(\boldsymbol{w},\boldsymbol{z})$ -learner implies the existence of a $(w_{i},z_{i})$ -learner for each $i=1,\ldots,r$ . Equivalently, the existence of a $(\boldsymbol{w},\boldsymbol{z})$ -learner implies the existence of a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})$ -learner for $\boldsymbol{\alpha}\in\{\boldsymbol{e}_{1},\ldots,\boldsymbol{e}_{r}\}$ (the canonical basis of $\mathbb{R}^{r})$ where $w_{\boldsymbol{\alpha}}=\sum_{i=1}^{r}\alpha_{i}w_{i}$ and $z_{\boldsymbol{\alpha}}=\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle$ .

Theorem 6 shows the other direction holds, i.e., that the existence of a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})$ -learner for all possible $\boldsymbol{\alpha}$ implies the existence of a $(\boldsymbol{w},\boldsymbol{z})$ -learner.

Algorithm 2 Boosting

(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})

-learners

0: Sample

S=(x_{j},y_{j})_{j=1}^{m}

;

(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})

-learners

{\mathcal{A}}_{\boldsymbol{\alpha}}

for every

\boldsymbol{\alpha}\in\Delta_{r}

; parameters

T,\eta,\widehat{m}

1: Initialize:

a_{1}(i)=1

for all

i=1,...,r

, set

U

to be the uniform distribution over

[m]

2: Define

M(h,i)=\mathbb{I}\!\left\{\frac{1}{m}\sum_{j=1}^{m}\ w_{i}(h(x_{j}),y_{j})>z_{i}\right\}

for all

i=1,...,r

and

h:{\mathcal{X}}\rightarrow{\mathcal{Y}}

3: for

t=1,\ldots,T

4: Compute the distribution

\boldsymbol{\alpha}_{t}\triangleq\frac{\mathbf{a}_{t}}{\sum_{i}a_{t}(i)}

over

[r]

5: Draw a set

S_{t}

\widehat{m}

labeled examples i.i.d. from

U

and obtain

h_{t}={\mathcal{A}}_{\boldsymbol{\alpha}_{t}}(S_{t})

6: For every

i=1,\ldots,r

let:

a_{t+1}(i)\triangleq a_{t}(i)\cdot e^{\eta\cdot M(h_{t},i)}\;.

7: end for

8: return The set of weak predictors

h_{1},...,h_{T}

Proof of Theorem 6.

It is easy to see that $1\implies 2$ holds, by definitions. We prove $2\implies 1$ . For any $f\in\mathcal{F}$ , and distribution $\mathcal{D}$ over ${\mathcal{X}}$ , let $S$ be a set of $m$ examples sampled i.i.d. from $\mathcal{D}$ and labeled by $f$ , where $m$ to be determined later. Let $\epsilon,\delta>0$ . Then, applying Algorithm 2 over $S$ with access to ${\mathcal{A}}_{\boldsymbol{\alpha}}$ learners, and with $T={100r^{2}\ln(r)}$ , $\eta=\sqrt{\frac{2\ln(r)}{T}}$ , $\widehat{m}=m_{0}(\frac{1}{10r},\frac{1}{20rT})$ (where $m_{0}$ is the sample complexity of ${\mathcal{A}}_{\boldsymbol{\alpha}}$ ) yields the following. Fix any $i\in[r]$ . Given that $\max_{t,i}M(h_{t},i)\leq 1$ and that $\eta\leq 1$ , the standard analysis of Hedge (Freund and Schapire, 1997) shows that:

\sum_{t=1}^{T}M(h_{t},i)\leq\frac{\ln(r)}{\eta}+\frac{\eta}{2}T+\sum_{t=1}^{T}{\mathbb E}_{i\sim\boldsymbol{\alpha}_{t}}\Bigl{[}M(h_{t},i)\Bigr{]}\;.

(44)

By the guarantee of ${\mathcal{A}}_{\boldsymbol{\alpha}}$ and the choice of $\widehat{m}$ , and by union bound over all $t\in[T]$ we get that with probability at least $1-\frac{1}{20r}$ ,

\frac{1}{T}\sum_{t=1}^{T}\frac{1}{m}\sum_{j=1}^{m}\ w_{\boldsymbol{\alpha}_{t}}(h_{t}(x_{j}),y_{j})\leq\frac{1}{T}\sum_{t=1}^{T}z_{\boldsymbol{\alpha}_{t}}+\frac{1}{10r}\;,

(45)

which implies,

\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{i\sim\boldsymbol{\alpha}_{t}}\Bigl{[}M(h_{t},i)\Bigr{]}\leq\frac{1}{10r}.

(46)

Thus, we get that with probability $1-\frac{1}{20r}$ ,

\frac{1}{T}\sum_{t=1}^{T}M(h_{t},i)\leq\frac{\ln(r)}{T\eta}+\frac{\eta}{2}+\frac{1}{10r}\leq\frac{1}{5r}\;.

(47)

By then also taking a union bound over $i=1,...,r$ , we have with probability at least $\frac{19}{20}$ for all $i=1,...,r$ it holds that,

\frac{1}{T}\sum_{t=1}^{T}M(h_{t},i)\leq\frac{1}{5r}.

(48)

Recall that for each $t$ and $i$ we have that $M(h_{t},i)\in\{0,1\}$ , and so for all $t\in[T]$ but $\frac{T}{5r}$ it holds that $M(h_{t},i)=0$ . We can now define the randomized hypothesis $\tilde{h}$ for any $x\in{\mathcal{X}}$ as follows. To compute the value of $\tilde{h}(x)$ , first we sample a hypothesis $h_{t}$ by sampling $t\sim U(T)$ uniformly at random, and then predict according to $h_{t}(x)$ . We then have,

\operatorname{\mathbb{P}}_{t\sim U(T)}\Big{[}\sum_{i=1}^{r}M(h_{t},i)\geq 1\Big{]}\leq\sum_{i=1}^{r}\operatorname{\mathbb{P}}_{t\sim U(T)}\Big{[}M(h_{t},i)=1\Big{]}\leq\frac{1}{5}.

(49)

Then, by the definition of $M(h,i)$ , we have that with probability at least $\frac{19}{20}$ ,

\operatorname{\mathbb{P}}_{\tilde{h}}\Big{[}\forall i=1,...,r,\ \ \frac{1}{m}\sum_{j=1}^{m}\ w_{i}(\tilde{h}(x_{j}),y_{j})\leq z_{i}\Big{]}\geq\frac{4}{5}.

(50)

Finally, we apply standard compression-based generalization arguments (Shalev-Shwartz and Ben-David (2014), Theorem 30.2) where the sample size is $m=\tilde{O}(\frac{\kappa}{\epsilon^{2}})$ and where the compression size is $\kappa=\widehat{m}\cdot T$ , we get that with probability at least $1-\delta$ over the sample of $S\sim\mathcal{D}^{m}$ it holds that:

\operatorname{\mathbb{P}}_{\tilde{h}}\Big{[}\forall i=1,...,r,\ \ L_{\mathcal{D}}^{w_{i}}(\tilde{h})\leq z_{i}+\epsilon\Big{]}>1/2.

(51)

Thus, the randomized hypothesis $\tilde{h}$ satisfies the desired guarantees with a constant probability. Overall we get that the procedure described above is a $(\boldsymbol{w},\boldsymbol{z})$ -learner for $\mathcal{F}$ in expectation.

Lastly, we remark that instead of a randomized learner whose guarantees hold in expectation, one can de-randomize choosing a single $h_{t}$ uniformly at random as above. Moreover, the confidence parameter of $1/2$ can easily be made arbitrarily large using standard confidence-boosting techniques. That is, by first splitting the input sample into approximately $q=O(\log(r/\delta))$ non-intersecting equal parts to learn roughly $q$ independent classifiers, each satisfying Equation (51). By the choice of $q$ , with $1-\delta/2$ probability, at least one of these classifiers will the satisfy the $1/2$ -probability condition given in Equation (51). Then, by Chernoff’s inequality, for each of these classifiers the performance as tested over another independent test-set is close to that over the population distribution. Then, by choosing the one with best empirical errors over the test-set, we get the desired result. ∎

5 Multiclass Classification

In contrast to binary classification, boosting in the multiclass setting does not exhibit a clean dichotomy between “trivial” guarantees and “fully boostable” guarantees. A line of works (Mukherjee and Schapire, 2011; Brukhim et al., 2021, 2023b, 2023a) has studied multiclass boosting when $w$ is the standard 0-1 loss, and has shown a certain multichotomy determined by $k-1$ thresholds, $\frac{1}{2},\frac{2}{3},\dots,\frac{k-1}{k}$ , that replace the single boostability threshold $\nicefrac{{1}}{{2}}$ of the binary case. For each such threshold, any learner achieving a loss below it can be “boosted” to a predictor that rules out some incorrect labels, albeit not all. Thus, for every example $x$ the predictor returns a subset of candidate labels, also called a list. A learner that beats a threshold $\frac{\ell-1}{\ell}$ above in fact yields a list predictor with lists of size $\ell-1$ , and it can be shown that the converse is also true. In this section we generalize these kind of results to the case of arbitrary costs functions, proving that these list boostability and list-versus-loss equivalences hold more broadly.

We start in Section 5.1 by describing an algorithm that turns a $(w,z)$ -learner into a list learner, proving the first part of C. Next, Section 5.3 proves some “list boostability” results that focus on the list length, based on the framework of List PAC learning (Brukhim et al., 2022; Charikar and Pabbaraju, 2023). We turn to multi-objective losses in Section 5.2, proving the first item of D. Finally, Section 5.4 concludes by giving the lower bounds of both C and D.

5.1 Cost-sensitive boosting

As said, in multiclass classification one cannot in general boost a learner into one that predicts the correct label. However, as prior work has shown, one can boost a learner into a list learner. This is a learner whose output hypothesis maps each $x\in{\mathcal{X}}$ to a set of labels, rather than to one single label. Formally, a list function is any map $\mu:{\mathcal{X}}\to 2^{\mathcal{Y}}$ . A list learner is then a learner that outputs a list function $\mu$ . The performance of such a list function $\mu$ is typically measured in two ways. First, one wants $\mu(x)$ to contain the true label $f(x)$ with good probability. Second, one wants $\mu(x)$ to somehow be “close” to $f(x)$ ; for instance, in the case of standard 0-1 cost, this is measured by the length $|\mu(x)|$ of $\mu(x)$ . All these guarantees are meant, as usual, over the target distribution $\mathcal{D}$ . One can then ask the following question: given a $(w,z)$ -learner, how good a list function $\mu$ can one construct? In order to answer this question in the cost-sensitive setting, we need to generalize list length to a more nuanced measure—one that is based once again on the values of games.

Definition 20 ( $(w,z)$ -boundedness).

Let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function and let $z\geq 0$ . A list function $\mu:{\mathcal{X}}\to 2^{\mathcal{Y}}$ is $(w,z)$ -bounded if, for every $x\in{\mathcal{X}}$ , the list $\mu(x)$ satisfies $\operatorname{V}_{\!\mu(x)}(w)\leq z$ .

Definition 21 ( $(w,z)$ -list learner).

Let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function and let $z\geq 0$ . An algorithm $\mathcal{L}$ is a $(w,z)$ -list learner for a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ if there is a function $m_{\mathcal{L}}:(0,1)^{2}\rightarrow\mathbb{N}$ such that for every $f\in\mathcal{F}$ , every distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and every $\epsilon,\delta\in(0,1)$ the following claim holds. If $S$ is a sample of $m_{\mathcal{L}}(\epsilon,\delta)$ examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ , then $\mathcal{L}(S)$ returns a $(w,z)$ -bounded list function $\mu$ such that $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\left[f(x)\notin\mu(x)\right]~{}\leq~{}\epsilon$ with probability at least $1-\delta$ .

The definitions above mirror closely the standard ones used in list learning, where the quality of a list $\mu(x)$ is measured by its length $|\mu(x)|$ . The crucial difference is that, now, we are instead using the value of the restricted game $\operatorname{V}_{\!\mu(x)}(w)$ . To get some intuition why this is the right choice, consider again the case where $w$ is the standard 0-1 cost. In that case it is well known that $V_{J}(w)=1-\nicefrac{{1}}{{|J|}}$ for every (nonempty) $J\subseteq{\mathcal{Y}}$ . Then, by Definition 20 and Definition 21 a $(w,z)$ -list learner is one that outputs lists of length at most $\ell=\min(k,\lfloor\frac{1}{1-z}\rfloor)$ . That is, for the 0-1 cost Definition 21 yields the standard notion of $\ell$ -list learner used in prior work on multiclass boosting. Now, for the special case of the 0-1 cost, Brukhim et al. (2023a) showed that any $(w,z)$ -learner is equivalent to an $\ell$ -list learner, with $\ell$ as defined above, in the sense that each one of them can be converted into the other. We show that this remains true for every cost function $w$ , if one replaces $|\mu(x)|$ with $\operatorname{V}_{\!\mu(x)}(w)$ , and therefore the notion of $\ell$ -list learner with the notion of $(w,z)$ -list learner. That is, we prove that $(w,z)$ -learners and $(w,z)$ -list learners are equivalent. Formally, we prove:

Theorem 22.

Let ${\mathcal{Y}}=[k]$ , let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function, let $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , and let $z\geq 0$ . Then:

•

Every $(w,z)$ -learner for $\mathcal{F}$ can be converted into a $(w,z)$ -list learner for $\mathcal{F}$ .
•

Every $(w,z)$ -list learner for $\mathcal{F}$ can be converted into a $(w,z)$ -learner for $\mathcal{F}$ .

Theorem 22 is the main technical result of the present sub-section, and implies easily the first item of C. And again, the above-mentioned result of Brukhim et al. (2023a) is a special case of Theorem 22, obtained for $w$ being the standard 0-1 cost. Moreover, one can easily show that all these results do not hold if one uses $|\mu(x)|$ in place of $\operatorname{V}_{\!\mu(x)}(w)$ . Our game-theoretical perspective therefore seems the right point of view for characterizing multiclass boostability. Let us see how the first item of C follows from Theorem 22. Recall the thresholds defined in Equation 6:

0=v_{1}(w)<\ldots<v_{\tau}(w)=V(w),

(52)

where the first equalities hold because $v_{J}(w)=0$ for any singleton $J$ and, by convention, for the empty set. Given $z\geq 0$ , let $n=n(z)$ be the largest integer such that $v_{n}(w)\leq z$ . Now, suppose we have a $(w,z)$ -learner ${\mathcal{A}}$ for some $\mathcal{F}$ . By the first item of Theorem 22, there exists a $(w,z)$ -list learner $\mathcal{L}$ for $\mathcal{F}$ , too. However, by definition of $n$ every $J\subseteq{\mathcal{Y}}$ with $\operatorname{V}_{J}(w)\leq z$ satisfies $\operatorname{V}_{J}(w)\leq v_{n}$ . Therefore, $\mathcal{L}$ actually returns list functions that are $(w,v_{n}+\sigma)$ -bounded, for $\sigma>0$ arbitrarily small. That is, $\mathcal{L}$ is actually a $(w,v_{n})$ -list learner for $\mathcal{F}$ . By the second item of Theorem 22, then, there exists a $(w,v_{n})$ -learner for $\mathcal{F}$ .

The rest of the subsection is therefore devoted to prove Theorem 22: the first item in Section 5.1.1, and the second one in Section 5.1.2.

5.1.1 Turning a $(w,z)$ -learner into a $(w,z)$ -list learner

We prove the first item of Theorem 22 by giving an algorithm, Algorithm 3. The algorithm is very similar to the one for the binary case. And, like for that case, we define a certain margin that the learner has, in order to bound the number of “boosting” rounds of the algorithm. For the multiclass case, however, the definition is in general slightly different.

Definition 23 (Margin).

Let $w:{\mathcal{Y}}^{2}\to[0,1]$ be a cost function and let $z\geq 0$ . The margin of a $(w,z)$ -learner is $\gamma=\min\{\operatorname{V}_{J}(w)-z:J\subseteq{\mathcal{Y}},\operatorname{V}_{J}(w)>z\}$ , or $\gamma=0$ whenever the set is empty.

Note that $\gamma=0$ only when $z\geq\operatorname{V}(w)$ . In that case, the first item of Theorem 22 holds trivially by just considering the trivial list learner that outputs the constant list function $\mu(x)={\mathcal{Y}}$ . Hence, in what follows we consider always the case $\gamma>0$ . We shall prove:

Theorem 24 (Weak $\Rightarrow$ List Learning).

Let $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ and let $w:{\mathcal{Y}}^{2}\to[0,1]$ be a cost function. If ${\mathcal{A}}$ is a $(w,z)$ -learner for $\mathcal{F}$ with margin $\gamma>0$ , then Algorithm 3, with the choice of parameters of Lemma 25 and $\sigma=\frac{2}{3}\gamma$ , is a $(w,z)$ -list learner for $\mathcal{F}$ . Under the same assumptions, Algorithm 3 makes $T=O\bigl{(}\frac{\ln(m)}{\gamma^{2}}\bigr{)}$ oracle calls to ${\mathcal{A}}$ , where $m$ is the size of the input sample, and has sample complexity $m(\epsilon,\delta)=\widetilde{O}\Bigl{(}m_{0}\bigl{(}\frac{\gamma}{3},\frac{\delta}{2T}\bigr{)}\cdot\frac{\ln(1/\delta)}{\epsilon\cdot\gamma^{2}}\Bigr{)}$ .

Theorem 24 follows immediately from two technical results stated below. The first result, Lemma 25, proves that Algorithm 3 can turn a $(w,z)$ -learner ${\mathcal{A}}$ into a list function $\mu_{S}$ that is $(w,z+\sigma)$ -bounded and that with probability $1-\delta$ is consistent with $S$ (i.e., $y_{i}\in\mu(x_{i})$ for every $(x_{i},y_{i})\in S$ ), for $\sigma,\delta>0$ as small as desired. The second result, Lemma 26, shows that the list function $\mu$ has small generalization error: if the input sample $S$ of Algorithm 3 is sufficiently large, then $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[f(x)\in\mu(x)]\geq 1-\epsilon$ , where $\epsilon>0$ can be chosen as small as desired.

Lemma 25.

Let ${\mathcal{Y}}=[k]$ , let $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , and let ${\mathcal{A}}$ be a $(w,z)$ -learner for $\mathcal{F}$ with sample complexity $m_{0}$ . Fix any $f\in\mathcal{F}$ , any distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and any $\sigma,\delta\in(0,1)$ . Then, given a multiset $S=\{(x_{1},y_{1}),\ldots,(x_{m},y_{m})\}$ of $m$ examples formed by i.i.d. points $x_{1},\dots,x_{m}\sim\mathcal{D}$ labeled by $f$ , oracle access to ${\mathcal{A}}$ , and parameters $T=\left\lceil\frac{8\ln(m)}{\sigma^{2}}\right\rceil$ , $\eta=\sqrt{\frac{2\ln(m)}{T}}$ , and $\widehat{m}=m_{0}\bigl{(}\frac{\sigma}{2},\frac{\delta}{T}\bigr{)}$ , Algorithm 3 returns a list function $\mu_{S}$ that is $(w,z+\sigma)$ -bounded and that, with probability at least $1-\delta$ , satisfies:

y_{i}\in\mu_{S}(x_{i})\qquad\forall i=1,\dots,m\;.

Proof.

First, we prove that $\mu_{S}$ is $(w,z+\sigma)$ -bounded. Fix any $x\in{\mathcal{X}}$ . Observe that $F(x,\cdot)$ is a distribution over ${\mathcal{Y}}$ ; denote it by $\mathbf{p}^{x}\in\Delta_{\mathcal{Y}}$ , so that $p^{x}_{\ell}=F(x,\ell)$ for every label $\ell\in{\mathcal{Y}}$ . Thus, by the definition of $\mu_{S}$ , the sum involved in the condition for including a certain label $y\in{\mathcal{Y}}$ in the list $\mu_{S}(x)$ is

\sum_{\ell\in{\mathcal{Y}}}F(x,\ell)\cdot w(\ell,y)=w(\mathbf{p}^{x},y)\;.

(53)

Then, observe that

\displaystyle\operatorname{V}_{\!\mu_{S}(x)}(w)=\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\max_{\mathbf{q}\in\Delta_{\mu_{S}(x)}}w(\mathbf{p},\mathbf{q})\leq\max_{\mathbf{q}\in\Delta_{\mu_{S}(x)}}w(\mathbf{p}^{x},\mathbf{q})=\max_{y\in\mu_{S}(x)}w(\mathbf{p}^{x},y)\leq z+\sigma\;,

(54)

where the last inequality holds by definition of $\mu_{S}(x)$ .

We now turn to proving that with probability at least $1-\delta$ we have $y_{i}\in\mu_{S}(x_{i})$ for all $i\in[m]$ . The proof is similar to that of Lemma 12. For any given $i\in[m]$ , the analysis of Hedge and the definitions of $\eta$ and $T$ yield:

\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})\leq\frac{\sigma}{2}+\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\;.

(55)

Furthermore, since ${\mathcal{A}}$ is a $(w,z)$ -learner for $\mathcal{F}$ , and given the choices of $\widehat{m}$ and $h_{t}={\mathcal{A}}(S_{t})$ , by a union bound over $t\in[T]$ we have that with probability at least $1-\delta$ :

\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\leq z+\frac{\sigma}{2}\;.

(56)

Conditioning on Equation 56, we prove that $y_{i}\in\mu_{S}(x_{i})$ for every $i\in[m]$ . Consider the function $F:{\mathcal{X}}\times{\mathcal{Y}}\to[0,1]$ defined in Algorithm 3. By Equations 55 and 56, we obtain for every $i\in[m]$ that

\sum_{\ell\in{\mathcal{Y}}}F(x_{i},\ell)\cdot w(\ell,y_{i})=\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})\leq z+\sigma\;.

(57)

which in turn implies that $y_{i}\in\mu_{S}(x_{i})$ by construction of $\mu_{S}$ . This concludes the proof. ∎

Algorithm 3 Boosting a

(w,z)

-learner to an

(w,z+\sigma)

-list learner

0: Sample

S=(x_{i},y_{i})_{i=1}^{m}

;

(w,z)

-learner

{\mathcal{A}}

; parameters

T,\eta,\widehat{m},\sigma

1: Initialize:

D_{1}(i)=1

for all

i=1,...,m

2: for

t=1,\ldots,T

3: Compute the distribution

\mathcal{D}_{t}\triangleq\frac{D_{t}}{\sum_{i}D_{t}(i)}

over

S

4: Draw a set

S_{t}

\widehat{m}

labeled examples i.i.d. from

\mathcal{D}_{t}

and obtain

h_{t}={\mathcal{A}}(S_{t})

5: For every

i=1,\ldots,m

let:

D_{t+1}(i)\triangleq D_{t}(i)\cdot e^{\eta\cdot w(h_{t}(x_{i}),y_{i})}\;.

6: end for

7: Let

F:{\mathcal{X}}\times{\mathcal{Y}}\to[0,1]

be such that

F(x,y)\triangleq\frac{1}{T}\sum_{t=1}^{T}\mathbb{I}\!\left\{h_{t}(x)=y\right\}

for all

x\in{\mathcal{X}}

y\in{\mathcal{Y}}

8: return

\mu_{S}:{\mathcal{X}}\to 2^{\mathcal{Y}}

such that, for all

x\in{\mathcal{X}}

\mu_{S}(x)\triangleq\Biggl{\{}y\in{\mathcal{Y}}:\sum_{\ell\in{\mathcal{Y}}}F(x,\ell)\cdot w(\ell,y)\leq z+\sigma\Biggr{\}}\;.

In a similar way as Lemma 13 does for the binary case, we show that the list function $\mu_{S}$ returned by Algorithm 3 has small generalization error provided that the sample $S$ is sufficiently large. The main idea to prove generalization is again via a sample compression scheme, but relying instead on a novel result by Brukhim et al. (2023a) for multiclass classification; note that, while their result from Brukhim et al. (2023a) is stated in terms of list functions whose outputs are $s$ -uples in ${\mathcal{Y}}^{s}$ for some $s<k$ , their same proof applies to the $(w,z)$ -bounded list functions output by our Algorithm 3.

Lemma 26.

Assume the setting of Lemma 25. For any $\epsilon,\delta\in(0,1)$ , if the size $m$ of the sample given to Algorithm 3 satisfies

m\geq\frac{\ln(2/\delta)}{\epsilon}+m_{0}\left(\frac{\sigma}{2},\frac{\delta}{2T}\right)\cdot T\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)\;,

then the output $\mu_{S}$ of Algorithm 3 satisfies $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[f(x)\notin\mu_{S}(x)]\leq\epsilon$ with probability at least $1-\delta$ . Therefore, Algorithm 3 is a $(w,z+\sigma)$ -list learner for $\mathcal{F}$ with sample complexity $m(\epsilon,\delta)=\widetilde{O}\Bigl{(}m_{0}\bigl{(}\frac{\sigma}{2},\frac{\delta}{2T}\bigr{)}\cdot\frac{\ln(1/\delta)}{\epsilon\cdot\sigma^{2}}\Bigr{)}$ .

Proof.

By analogy with the proof of Lemma 13, we first apply Lemma 25 with $\delta/2$ in place of $\delta$ in order to obtain an $(w,z+\sigma)$ -bounded list function $\mu_{S}$ consistent with $S$ with probability at least $1-\delta/2$ . We then apply a compression-based generalization argument. To do so, we remark once again that one can construct a compression scheme for $\mu_{S}$ of size equal to the total size of the samples on which ${\mathcal{A}}$ operates, which is equal to $\kappa=\widehat{m}\cdot T$ . The main difference with the binary case is that we rely on the generalization bound for a sample compression scheme for lists as per Theorem 6 of Brukhim et al. (2023a), with $\delta/2$ in place of $\delta$ ; we can employ this generalization bound thanks to the consistency of $\mu_{S}$ with $S$ (with sufficiently large probability). Then, this implies that

\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\bigl{[}f(x)\notin\mu_{S}(x)\bigr{]}\leq\frac{\kappa\ln(m)+\ln(2/\delta)}{m-\kappa}

(58)

holds with probability at least $1-\delta/2$ . By similar calculations as in Equations 18 and 19, and replacing the values of $\kappa$ and $\widehat{m}$ , the right-hand side of the above inequality can be easily show to be at most $\epsilon$ whenever

m\geq\frac{\ln(2/\delta)}{\epsilon}+m_{0}\left(\frac{\sigma}{2},\frac{\delta}{2T}\right)\cdot T\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)\;.

(59)

A union bound concludes the proof for the first part of the claim, since it shows that Algorithm 3 is an $(w,z+\sigma)$ -list learner for $\mathcal{F}$ . The claim on the sample complexity of Algorithm 3 then follows by straightforward calculations and the definition of $T=O\bigl{(}\frac{\ln(m)}{\sigma^{2}}\bigr{)}$ . ∎

At this point, we have all the ingredients and tools to prove that we can construct a $(w,z)$ -list learner from a $(w,z)$ -learner.

Proof of Theorem 24.

Consider Algorithm 3 under the same assumptions of Lemma 25, and set $\sigma=\frac{2}{3}\gamma$ as per assumption. By Lemma 25 and Lemma 26, we know that Algorithm 3 is a $(w,z+\frac{2}{3}\gamma)$ -list learner with sample complexity $m(\epsilon,\delta)=\widetilde{O}\bigl{(}m_{0}\bigl{(}\frac{\gamma}{3},\frac{\delta}{2T}\bigr{)}\cdot\frac{\ln(1/\delta)}{\epsilon\cdot\gamma^{2}}\bigr{)}$ that performs $O\bigl{(}\frac{\ln(m)}{\gamma^{2}}\bigr{)}$ oracle calls to the $(w,z)$ -learner ${\mathcal{A}}$ . Moreover, we can immediately conclude that Algorithm 3 is also a $(w,z)$ -list learner because $z\geq v_{n}$ and $z+\frac{2}{3}\gamma<z+\gamma=v_{n+1}$ , by definitions of $n=n(z)$ and $\gamma$ . ∎

5.1.2 Turning a $(w,z)$ -list learner into a $(w,z)$ -learner

We prove that every $(w,z)$ -list learner can be converted into a $(w,z)$ -learner.

Lemma 27 (List $\Rightarrow$ Weak Learning).

There exists an algorithm ${\mathcal{B}}$ that for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ satisfies what follows. Let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function and let $z\geq 0$ . Given oracle access to a $(w,z)$ -list learner $\mathcal{L}$ for $\mathcal{F}$ with sample complexity $m_{\mathcal{L}}$ , algorithm ${\mathcal{B}}$ is a $(w,z)$ -learner for $\mathcal{F}$ with sample complexity $m_{\mathcal{L}}$ that makes one oracle call to $\mathcal{L}$ .

Proof.

Fix any $f\in\mathcal{F}$ and any distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and suppose ${\mathcal{B}}$ is given a sample $S$ of size $m\geq m_{\mathcal{L}}(\epsilon,\delta)$ consisting of examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ . First, ${\mathcal{B}}$ calls $\mathcal{L}$ on $S$ . By hypothesis, then, $\mathcal{L}$ returns a $(w,z)$ -bounded $\mu_{S}:{\mathcal{X}}\to{\mathcal{Y}}^{\mathcal{X}}$ that with probability at least $1-\delta$ satisfies:

\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\bigl{[}f(x)\notin\mu_{S}(x)\bigr{]}\leq\epsilon\;.

(60)

Conditioning on the event above from this point onwards, we give a randomized predictor $h_{S}$ such that $L_{\mathcal{D}}^{w}(h_{S})\leq z+\epsilon$ . First, for any nonempty $J\subseteq{\mathcal{Y}}$ , let $\mathbf{p}_{J}\in\Delta_{\mathcal{Y}}$ be the minimax distribution achieving the value of the game restricted to $J$ , i.e.,

\displaystyle\mathbf{p}_{J}=\arg\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\left(\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p},\mathbf{q})\right)\;.

(61)

Note that $\mathbf{p}_{J}$ can be efficiently computed via a linear program. Then, simply define $h_{S}(x)\sim\mathbf{p}_{\mu_{S}(x)}$ .

Let us analyse the loss of $h_{S}$ under $\mathcal{D}$ . First, by the law of total expectation, and since $\|w\|_{\infty}\leq 1$ ,

\displaystyle L_{\mathcal{D}}^{w}(h_{S})

\displaystyle\leq\operatorname{\mathbb{P}}_{x\sim D}[f(x)\notin\mu_{S}(x)]+\sum_{J}\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[\mu_{S}(x)=J\wedge f(x)\in J]\cdot L_{\mathcal{D}_{J}}^{w}(h_{S})\;,

(62)

where the summation is over all $J\subseteq{\mathcal{Y}}$ with $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[\mu_{S}(x)=J]>0$ , and $\mathcal{D}_{J}$ is the distribution obtained from $\mathcal{D}$ by conditioning on the event $\mu_{S}(x)=J\wedge f(x)\in J$ . Consider the right-hand side of Equation 62. By Equation 60, the first term is at most $\epsilon$ . For the second term, denote by $\mathbf{q}_{J}$ the marginal of $\mathcal{D}_{J}$ over ${\mathcal{Y}}$ ; note that, crucially, $\mathbf{q}_{J}\in\Delta_{J}$ . Therefore, by definition of $h_{S}$ :

\displaystyle L_{\mathcal{D}_{J}}^{w}(h_{S})=w(\mathbf{p}_{J},\mathbf{q}_{J})\leq\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p}_{J},\mathbf{q})=\operatorname{V}_{J}(w)\leq z\;,

(63)

where the last inequality holds as $J=\mu(x)$ and $\mu$ is $(w,z)$ -bounded. Using Equations 60 and 63 in Equation 62 shows that $L_{\mathcal{D}}^{w}(h_{S})\leq z+\epsilon$ . ∎

5.2 Multi-objective losses

In this sub-section we prove the first item of D. Coupled with Lemma 39 below, this proves D. Both results require the following definition. Let $\operatorname{av}(\boldsymbol{w},\mathbf{z})$ denote the family of all subsets of ${\mathcal{Y}}$ which are avoided by $(\boldsymbol{w},\mathbf{z})$ , i.e.,

\operatorname{av}(\boldsymbol{w},\mathbf{z})\triangleq\{J\subseteq{\mathcal{Y}}:\mathbf{z}\notin D_{J}(\boldsymbol{w})\}.

The algorithm proposed below then scales with $N=|\operatorname{av}(\boldsymbol{w},\mathbf{z})|$ , which may be exponential in $|{\mathcal{Y}}|$ . We remark that for our purposes, it also suffices to consider only the minimally-sized avoided lists in $\operatorname{av}(\boldsymbol{w},\mathbf{z})$ , i.e., if $J\subseteq J^{\prime}$ and $\mathbf{z}\notin D_{J}(\boldsymbol{w})$ then $J^{\prime}\notin\operatorname{av}(\boldsymbol{w},\mathbf{z})$ . However, in the worst case $N$ remains of the same order and so we keep the definition as given above for simplicity. Lemma 39 will then give a lower bound showing that this condition is, in some sense, necessary.

Theorem 28.

Let ${\mathcal{Y}}=[k]$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost function, and let $\boldsymbol{z}\in[0,1]^{r}$ . Let $\boldsymbol{z}^{\prime}\in[0,1]^{r}$ such that $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ . Assume there exists a $(\boldsymbol{w},\boldsymbol{z})$ -learner for a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . Then, there exists a $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -learner for $\mathcal{F}$ .

Proof.

By assumption, for every $J\subseteq{\mathcal{Y}}$ such that $J\in\operatorname{av}(\boldsymbol{w},\mathbf{z}^{\prime})$ it holds that $J\in\operatorname{av}(\boldsymbol{w},\mathbf{z})$ . Let $\boldsymbol{\alpha}\in\Delta_{r}$ , and denote $w_{\boldsymbol{\alpha}}=\boldsymbol{\alpha}\cdot\boldsymbol{w}$ and $z^{\prime}_{\boldsymbol{\alpha}}=\boldsymbol{\alpha}\cdot\mathbf{z}^{\prime}$ . Then, by Lemma 29 we get that the $(\boldsymbol{w},\boldsymbol{z})$ -learner can be used to obtain a $(w_{\boldsymbol{\alpha}},z^{\prime}_{\boldsymbol{\alpha}})$ -learner for $\mathcal{F}$ . Since this holds for every $\boldsymbol{\alpha}\in\Delta_{r}$ , then by Theorem 6 this implies the existence of a $(\boldsymbol{w},\mathbf{z}^{\prime})$ -learner as well, which completes the proof. ∎

Lemma 29.

Let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost function, and let $\boldsymbol{z},\boldsymbol{z}^{\prime}\in[0,1]^{r}$ such that $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ . Assume there exists a $(\boldsymbol{w},\boldsymbol{z})$ -learner ${\mathcal{A}}$ for a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . Then, there exists a $(w_{\boldsymbol{\alpha}},z^{\prime}_{\boldsymbol{\alpha}})$ -learner for $\mathcal{F}$ , for every $\boldsymbol{\alpha}\in\Delta_{r}$ .

Proof.

First, by Lemma 31 we get that ${\mathcal{A}}$ can be used to obtain an algorithm $\mathcal{L}$ that is a $\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -list learner for $\mathcal{F}$ . Next, we show that $\mathcal{L}$ can be boosted to a $(w_{\boldsymbol{\alpha}},z^{\prime}_{\boldsymbol{\alpha}})$ -learner. Fix any $\boldsymbol{\alpha}\in\Delta_{r}$ . First, we argue that $\mathcal{L}$ is in fact a $(w_{\boldsymbol{\alpha}},z^{\prime}_{\boldsymbol{\alpha}})$ -list learner (see Definition 21). This holds since for every $J\subseteq{\mathcal{Y}}$ such that $z^{\prime}_{\boldsymbol{\alpha}}<V_{J}(w_{\boldsymbol{\alpha}})$ , it must be that $J\in\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ , by definition and by Proposition 19. In particular, for any $\mu$ list function outputted by $\mathcal{L}$ , and for every $x\in{\mathcal{X}}$ it holds that $J\not\subseteq\mu(x)$ and so $V_{\mu(x)}(w_{\boldsymbol{\alpha}})\leq z^{\prime}_{\boldsymbol{\alpha}}$ .

Thus, we have established that $\mathcal{L}$ is in fact a $(w_{\boldsymbol{\alpha}},z^{\prime}_{\boldsymbol{\alpha}})$ -list learner. Lastly, by Lemma 27 we get that it can also be converted into a $(w_{\boldsymbol{\alpha}},z^{\prime}_{\boldsymbol{\alpha}})$ -learner, as needed. ∎

Definition 30 ( $\operatorname{av}(\boldsymbol{w},\boldsymbol{z})$ -list learner).

An algorithm $\mathcal{L}$ is a $\operatorname{av}(\boldsymbol{w},\boldsymbol{z})$ -list learner for a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ if there is a function $m_{\mathcal{L}}:(0,1)^{2}\rightarrow\mathbb{N}$ such that for every $f\in\mathcal{F}$ , every distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and every $\epsilon,\delta\in(0,1)$ the following claim holds. If $S$ is a sample of $m_{\mathcal{L}}(\epsilon,\delta)$ examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ , then $\mathcal{L}(S)$ returns a list function $\mu:{\mathcal{X}}\rightarrow 2^{\mathcal{Y}}$ such that $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\left[f(x)\notin\mu(x)\right]~{}\leq~{}\epsilon$ with probability $1-\delta$ , and such that for every $x\in{\mathcal{X}}$ and every $J\in\operatorname{av}(\boldsymbol{w},\boldsymbol{z})$ it holds that $J\not\subseteq\mu(x)$ .

Lemma 31.

Let ${\mathcal{Y}}=[k]$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost function, and let $\boldsymbol{z},\boldsymbol{z}^{\prime}\in[0,1]^{r}$ such that $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ . Assume there exists a $(\boldsymbol{w},\boldsymbol{z})$ -learner ${\mathcal{A}}$ for a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . Then, there exists a $\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -list learner for $\mathcal{F}$ .

Proof.

First, fix any $J\in\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ . By assumption that $\boldsymbol{z}\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ , we also have that $J\in\operatorname{av}(\boldsymbol{w},\boldsymbol{z})$ . In particular, we have that $(\boldsymbol{w},\boldsymbol{z})$ is not $J$ -dice-attainable. Then, by Proposition 19 we have that there exist $\boldsymbol{\alpha}\in\Delta_{r}$ such that,

z_{\boldsymbol{\alpha}}=\langle\boldsymbol{\alpha},\boldsymbol{z}\rangle<\operatorname{V}_{J}(w_{\boldsymbol{\alpha}}),

(64)

where $w_{\boldsymbol{\alpha}}=\sum_{i=1}^{r}\alpha_{i}w_{i}$ . Thus, we have that ${\mathcal{A}}$ is also a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}})$ -learner for $\mathcal{F}$ , and that $z_{\boldsymbol{\alpha}}<\operatorname{V}_{J}(w_{\boldsymbol{\alpha}})$ . We denote this learning algorithm by ${\mathcal{A}}_{J}$ . Notice that we can repeat the above process for any such $J$ . Thus, we obtain different learning algorithms ${\mathcal{A}}_{J}$ for each $J\in\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ .

Next, we will describe the construction of the $\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -list learning algorithm. Fix any $\delta^{\prime},\epsilon^{\prime}>0$ . For every learner ${\mathcal{A}}_{J}$ , apply Algorithm 3 with parameters $\sigma_{J}=\frac{2}{3}\gamma_{J}$ , where $\gamma_{J}$ is the margin of ${\mathcal{A}}_{J}$ , our $(w_{\boldsymbol{\alpha}_{J}},z_{\boldsymbol{\alpha}_{J}})$ -learner (see Definition 23). We also set the parameters of ${\mathcal{A}}_{J}$ to be $\epsilon=\epsilon^{\prime}$ , and $\delta=\delta^{\prime}/2N$ , for $N=|\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})|$ . The remaining parameters for Algorithm 3 are set as in Lemma 25.

For each such run of the algorithm, we obtain a list function. Let $\mu_{J_{1}},...,\mu_{J_{N}}$ denote all list functions obtained by this procedure. Finally, return the list function $\mu$ defined by

\mu(x)=\bigcap_{n=1}^{N}\mu_{J_{n}}(x),

for every $x\in{\mathcal{X}}$ . We will now show that this algorithm satisfies the desired guarantees, and is indeed a $\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -list learner.

First, by Lemma 25 and union bound we get that with probability at least $1-\delta/2$ , for each $n\leq N$ it holds that:

y_{i}\in\mu_{J_{n}}(x_{i})\qquad\forall i=1,\dots,m\;.

Thus, in particular, with probability at least $1-\delta/2$ we also have that $y_{i}\in\mu(x_{i})$ for all $i\in[m]$ . Moreover, by Lemma 25 we have that all $\mu_{J_{n}}$ are $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}}+\sigma_{J_{n}})$ -bounded. That is, for each $n\leq N$ and every $x\in{\mathcal{X}}$ it holds that $\operatorname{V}_{\!\mu_{J_{n}}(x)}(w_{\boldsymbol{\alpha}})\leq z_{\boldsymbol{\alpha}}+\sigma_{J_{n}}=z_{\boldsymbol{\alpha}}+\frac{2}{3}\gamma_{J_{n}}$ . Now recall that by the definition of the margin, and by Equation 64 we in fact have that:

\operatorname{V}_{\!\mu_{J_{n}}(x)}(w_{\boldsymbol{\alpha}})<\operatorname{V}_{\!J_{n}}(w_{\boldsymbol{\alpha}}).

This then implies that for every $x\in{\mathcal{X}}$ it holds that $J_{n}\not\subseteq\mu_{J_{n}}(x)$ . Thus, in particular, we also get that the final list function $\mu$ satisfies that for every $x\in{\mathcal{X}}$ it holds that $J_{n}\not\subseteq\mu(x)$ . Lastly, by following the same compression-based generalization analysis as in Lemma 26, we obtain that the above procedure is in fact a $\operatorname{av}(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -list learning algorithm, with sample complexity $m(\epsilon,\delta)=\widetilde{O}\Bigl{(}m_{0}\bigl{(}{\gamma^{*}},\frac{\delta}{NT}\bigr{)}\cdot\frac{\ln(N/\delta)}{\epsilon\cdot{\gamma^{*}}^{2}}\Bigr{)}$ , where $\gamma^{*}=\min_{n\in[N]}\gamma_{J_{n}}$ .

∎

5.3 Multiclass boosting via $s$ -list PAC learning

In this section we aim to convert weak learners to list learners, with a fixed list size. This is, in some sense, a coarsening of the previous subsection, which also subsumes previous work by Brukhim et al. (2023a), where the authors demonstrate $k-1$ thresholds which determine the achievable list sizes. To that end, for every $s=2,\ldots,k$ define the following coarsening of $s$ -the critical thresholds of $w$ :

\displaystyle v_{\underline{s}}(w)\triangleq\min\left\{\operatorname{V}_{J}(w):J\in{[k]\choose s}\right\},\qquad v_{\overline{s}}(w)\triangleq\max\left\{\operatorname{V}_{J}(w):J\in{[k]\choose s}\right\}\;.

(65)

Clearly, for all $s\in\{2,...,k\}$ we have that $v_{\underline{s}}(w)\leq v_{\overline{s}}(w)$ . It is also easy to see that $0\leq v_{\underline{2}}(w)\leq\ldots\leq v_{\underline{k}}(w)$ , and $0\leq v_{\overline{2}}(w)\leq\ldots\leq v_{\overline{k}}(w)$ . When clear from context, we omit $w$ and denote the thresholds by $v_{\underline{s}}$ and $v_{\overline{s}}$ . We remark that the two types of thresholds $v_{\underline{s}}$ and $v_{\overline{s}}$ are useful for different ways of boosting as specified in the remainder of this section.

Before stating the theorem, we need to first describe what it means to “partially” boost. The results given in this section are based on the framework of List PAC learning (Brukhim et al., 2022; Charikar and Pabbaraju, 2023). The connection between list learning and multiclass boosting was demonstrated by prior works (Brukhim et al., 2023a, b). Here we strengthen this link and generalize previous results to hold for arbitrary costs. We start with introducing list learning in Definition 32, followed by the statement of Theorem 33.

Definition 32 ( $s$ -List PAC Learning (Brukhim et al., 2022; Charikar and Pabbaraju, 2023)).

An algorithm $\mathcal{L}$ is a $s$ -list PAC learner for a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ if the following holds. For every distribution $\mathcal{D}$ over ${\mathcal{X}}$ and target function $f\in\mathcal{F}$ , and every $\epsilon,\delta>0$ , if $S$ is a set of $m\geq m(\epsilon,\delta)$ examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ , then $\mathcal{L}(S)$ returns $\mu:{\mathcal{X}}\rightarrow{\mathcal{Y}}^{s}$ such that, with probability at least $1-\delta$ ,

L_{\mathcal{D}}(\mu)\triangleq\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\bigl{[}f(x)\notin\mu(x)\bigr{]}~{}\leq~{}\epsilon\;.

Theorem 33.

Let ${\mathcal{Y}}=[k]$ , let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be any cost function, and let $z\geq 0$ . Let $v_{\underline{2}}\leq\ldots\leq v_{\underline{k}}$ as defined in Equation 65, and let $s<k$ be the smallest integer for which $z<v_{\underline{s+1}}$ or, if none exists, let $s=k$ . Then, the following claims both hold.

•

$(w,z)$ is $s$ -boostable: for every class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ , every $(w,z)$ -learner is boostable to an $s$ -list PAC learner.
•

$(w,z)$ is not $(s-1)$ -boostable: for some $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ there exists a $(w,z)$ -learner that cannot be boosted to an $s^{\prime}$ -list PAC learner with $s^{\prime}<s$ .

In words, Theorem 33 implies that there is a partition of the loss values interval $[0,1]$ into $k$ sub-intervals or “buckets”, based on $v_{\underline{s}}$ . Then, any loss value $z$ in a certain bucket $v_{\underline{s}}$ can be boosted to a list of size $s$ , but not below that. In Theorem 36 we show the converse: that any $s$ -list learner can be boosted to $(w,z)$ -learner where $z$ may be the lowest value within the $s$ -th interval $v_{\overline{s}}$ , but not below it.

The first item of Theorem 33 holds trivially for $z\geq v_{\underline{k}}$ , since in that case $s=k$ and a $k$ -list learner always exists. The case $z<v_{\underline{k}}$ is addressed by Lemma 34 below.

Lemma 34.

Let ${\mathcal{Y}}=[k]$ , let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function, and define $v_{\underline{2}}\leq\ldots\leq v_{\underline{k}}$ as in Equation 65. Let $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ and let ${\mathcal{A}}$ be a $(w,z)$ -learner for $\mathcal{F}$ with sample complexity $m_{0}$ such that $z<v_{\underline{k}}$ . Let $s$ be the smallest integer in $\{1,\ldots,k-1\}$ such that $z<v_{\underline{s+1}}$ and let $\gamma=v_{\underline{s+1}}-z>0$ be the margin. Fix any $f\in\mathcal{F}$ , let $\mathcal{D}$ be any distribution over ${\mathcal{X}}$ , and let $S=\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\}$ be a multiset of $m$ examples given by i.i.d. points $x_{1},\dots,x_{m}\sim\mathcal{D}$ labeled by $f$ . Finally, fix any $\delta\in(0,1)$ . If Algorithm 3 is given $S$ , oracle access to ${\mathcal{A}}$ , and parameters $T=\left\lceil\frac{18\ln(m)}{\gamma^{2}}\right\rceil$ , $\eta=\sqrt{\frac{2\ln(m)}{T}}$ , $\widehat{m}=m_{0}\bigl{(}\frac{\gamma}{3},\frac{\delta}{T}\bigr{)}$ , and $\sigma=\frac{2}{3}\gamma$ , then Algorithm 3 makes $T$ calls to ${\mathcal{A}}$ and returns $\mu_{S}:{\mathcal{X}}\to{\mathcal{Y}}^{s}$ such that with probability at least $1-\delta$ :

y_{i}\in\mu_{S}(x_{i})\qquad\forall i=1,\dots,m\;.

Proof.

Fix any $f\in\mathcal{F}$ and any $\epsilon,\delta\in(0,1)$ . Let $\mathcal{D}$ be any distribution over ${\mathcal{X}}$ and let $S=\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\}$ be a multiset of $m$ examples given by i.i.d. points $x_{1},\dots,x_{m}\sim\mathcal{D}$ labeled by $f$ . The first part of this proof follows similar steps as the one of Lemma 12. In particular, fix any $i\in[m]$ and observe that, again by the regret analysis of Hedge and by the definitions of $\eta$ and $T$ , Algorithm 3 guarantees

\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})\leq\frac{\gamma}{3}+\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\;.

(66)

Furthermore, since ${\mathcal{A}}$ is a $(w,z)$ -learner for $\mathcal{F}$ , and given the choices of $\widehat{m}$ and $h_{t}={\mathcal{A}}(S_{t})$ , by a union bound over $t\in[T]$ we obtain that

\frac{1}{T}\sum_{t=1}^{T}{\mathbb E}_{j\sim\mathcal{D}_{t}}\Bigl{[}w(h_{t}(x_{j}),y_{j})\Bigr{]}\leq z+\frac{\gamma}{3}

(67)

with probability at least $1-\delta$ .

Now, we show that the list predictor $\mu_{S}$ built by Algorithm 3 is consistent with $S$ with sufficiently large probability. Precisely, by conditioning on the event given by the inequality in Equation 67, we now demonstrate that $y_{i}\in\mu_{S}(x_{i})$ for every $i\in[m]$ . Consider the function $F:{\mathcal{X}}\times{\mathcal{Y}}\to[0,1]$ as defined by Algorithm 3. Then, by Equations 66 and 67 together with the definition of $\gamma>0$ , we obtain for every $i\in[m]$ that

\sum_{\ell\in{\mathcal{Y}}}F(x_{i},\ell)\cdot w(\ell,y_{i})=\frac{1}{T}\sum_{t=1}^{T}w(h_{t}(x_{i}),y_{i})\leq z+\frac{2}{3}\gamma<z+\gamma=v_{\underline{s+1}}\;,

(68)

which in turn implies that $y_{i}\in\mu_{S}(x_{i})$ by construction of $\mu_{S}$ .

We now proceed with a deterministic characterization of the lists returned by $\mu_{S}$ , independently of any conditioning. Fix any $x\in{\mathcal{X}}$ . Let $\mathbf{p}^{x}\in\Delta_{\mathcal{Y}}$ be such that $p^{x}_{\ell}=F(x,\ell)$ for any $\ell\in{\mathcal{Y}}$ , and observe that the sum involved within the condition for $y\in{\mathcal{Y}}$ in the construction of the list $\mu_{S}(x)$ is equal to $w(\mathbf{p}^{x},y)$ . Furthermore, it must be true that $s<k$ since $\gamma>0$ . We can then show that the list $\mu_{S}(x)$ satisfies

v_{\underline{s+1}}>\max_{y\in\mu_{S}(x)}w(\mathbf{p}^{x},y)=\max_{\mathbf{q}\in\Delta_{\mu_{S}(x)}}w(\mathbf{p}^{x},\mathbf{q})\geq\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\max_{\mathbf{q}\in\Delta_{\mu_{S}(x)}}w(\mathbf{p},\mathbf{q})=\operatorname{V}_{\mu_{S}(x)}(w)\;,

(69)

where the first inequality holds by definition of $\mu_{S}(x)$ . Consequently, after observing that $\operatorname{V}_{J}(w)\leq\operatorname{V}_{J^{\prime}}(w)$ if $J\subseteq J^{\prime}$ , note that

\operatorname{V}_{\mu_{S}(x)}(w)<v_{\underline{s+1}}=\min_{J\in\binom{{\mathcal{Y}}}{s+1}}\operatorname{V}_{J}(w)=\min_{J\subseteq{\mathcal{Y}}:|J|\geq s+1}\operatorname{V}_{J}(w)\;,

(70)

which in turn implies that $|\mu_{S}(x)|\leq s$ . We can thus assume that $\mu_{S}$ outputs elements of ${\mathcal{Y}}^{s}$ without loss of generality. ∎

The following lemma proves that, in a similar way as Lemma 13 for the binary setting, the list predictor output by Algorithm 3 has a sufficiently small generalization error provided that the sample $S$ has size $m$ sufficiently large. The main idea to prove generalization is again via a sample compression scheme, but relying instead of novel results by Brukhim et al. (2023a) for multiclass classification. This generalization result, combined with Lemma 34, suffices to prove Theorem 33.

Lemma 35.

Assume the hypotheses of Lemma 34. For any $\epsilon,\delta\in(0,1)$ , if the size $m$ of the sample given to Algorithm 3 satisfies

m\geq\frac{\ln(2/\delta)}{\epsilon}+m_{0}\left(\frac{\gamma}{3},\frac{\delta}{2T}\right)\cdot T\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)\;,

then with probability at least $1-\delta$ the output $\mu_{S}$ of Algorithm 3 satisfies $L_{\mathcal{D}}(\mu_{S})\leq\epsilon$ . Therefore, Algorithm 3 is an $s$ -list PAC learner for $\mathcal{F}$ . Moreover, one can ensure that Algorithm 3 makes $O\bigl{(}\frac{\ln(m)}{\gamma^{2}}\bigr{)}$ calls to ${\mathcal{A}}$ and has sample complexity $m(\epsilon,\delta)=\widetilde{O}\left(m_{0}\left(\frac{\gamma}{3},\frac{\delta}{2T}\right)\cdot\frac{\ln(1/\delta)}{\epsilon\cdot\gamma^{2}}\right)$ .

Proof.

By analogy with the proof of Lemma 13, we first apply Lemma 34 with $\delta/2$ in place of $\delta$ in order to obtain an $s$ -list predictor $\mu_{S}$ consistent with $S$ with probability at least $1-\delta/2$ . We then apply a compression-based generalization argument. To do so, we remark once again that one can construct a compression scheme for $\mu_{S}$ of size equal to the total size of the samples on which ${\mathcal{A}}$ operates, which is equal to $\kappa=\widehat{m}\cdot T$ . The main difference with the binary case is that we rely on the generalization bound for a sample compression scheme for lists as per Theorem 6 of Brukhim et al. (2023a), with $\delta/2$ in place of $\delta$ ; we can employ this generalization bound thanks to the consistency of $\mu_{S}$ with $S$ (with sufficiently large probability). Then, this implies that

L_{\mathcal{D}}(\mu_{S})=\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\bigl{[}f(x)\notin\mu_{S}(x)\bigr{]}\leq\frac{\kappa\ln(m)+\ln(2/\delta)}{m-\kappa}

(71)

m\geq\frac{\ln(2/\delta)}{\epsilon}+m_{0}\left(\frac{\gamma}{3},\frac{\delta}{2T}\right)\cdot T\cdot\left(1+\frac{\ln(m)}{\epsilon}\right)\;.

(72)

A union bound concludes the proof for the first part of the claim, since it shows that Algorithm 3 is an $s$ -list PAC learner for $\mathcal{F}$ . The sample complexity of Algorithm 3 then immediately follows by definition of $T$ . ∎

Next, we prove a kind of converse of Theorem 33. That is, one can convert a list learner to a weak learner. This results is stated formally as follows.

Theorem 36 ( $s$ -List $\Rightarrow$ Weak Learning).

There exists an algorithm ${\mathcal{B}}$ that for every $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ satisfies what follows. Let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be a cost function, let $z\geq 0$ , and let $v_{\overline{2}}\leq\ldots\leq v_{\overline{k}}$ as defined in Equation (65). Let $s<k$ be the smallest integer for which $z<v_{\overline{s+1}}$ , or if none exists let $s=k$ . Given oracle access to a $s$ -list PAC learner $\mathcal{L}$ for $\mathcal{F}$ with sample complexity $m_{\mathcal{L}}$ , algorithm ${\mathcal{B}}$ is a $(w,z)$ -learner for $\mathcal{F}$ with sample complexity $m_{\mathcal{L}}$ that makes one oracle call to $\mathcal{L}$ .

Proof.

Fix any $f\in\mathcal{F}$ and any distribution $\mathcal{D}$ over ${\mathcal{X}}$ , and suppose ${\mathcal{B}}$ is given a sample $S$ of size $m\geq m_{\mathcal{L}}(\epsilon,\delta)$ consisting of examples drawn i.i.d. from $\mathcal{D}$ and labeled by $f$ . First, ${\mathcal{B}}$ calls $\mathcal{L}$ on $S$ . By hypothesis, then, $\mathcal{L}$ returns $\mu_{S}:{\mathcal{X}}\to{\mathcal{Y}}^{s}$ that with probability at least $1-\delta$ satisfies:

\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}\bigl{[}f(x)\notin\mu_{S}(x)\bigr{]}\leq\epsilon\;.

(73)

Conditioning on the event above, we give a randomized predictor $h_{S}$ such that $L_{\mathcal{D}}^{w}(h_{S})\leq z+\epsilon$ . First, for any nonempty $J\subseteq{\mathcal{Y}}$ let $\mathbf{p}_{J}\in\Delta_{\mathcal{Y}}$ be the minimax distribution achieving the value of the game restricted to $J$ ,

\displaystyle\mathbf{p}_{J}=\arg\min_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\left(\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p},\mathbf{q})\right)\;.

(74)

Note that $\mathbf{p}_{J}$ can be efficiently computed via a linear program. Then, simply define $h_{S}(x)\sim\mathbf{p}_{\mu_{S}(x)}$ .

Let us analyse the loss of $h_{S}$ under $\mathcal{D}$ . First, by the law of total probability, and since $\|w\|_{\infty}\leq 1$ ,

\displaystyle L_{\mathcal{D}}^{w}(h_{S})

\displaystyle\leq\operatorname{\mathbb{P}}_{x\sim D}[f(x)\notin\mu_{S}(x)]+\sum_{J}\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[\mu_{S}(x)=J\wedge f(x)\in J]\cdot L_{\mathcal{D}_{J}}^{w}(h_{S})\;,

(75)

where the summation is over all $J\subseteq{\mathcal{Y}}$ with $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[\mu_{S}(x)=J]>0$ , and $\mathcal{D}_{J}$ is the distribution obtained from $\mathcal{D}$ by conditioning on the event $\mu_{S}(x)=J\wedge f(x)\in J$ . Consider the right-hand side of Equation 75. By Equation 73, the first term is at most $\epsilon$ . For the second term, denote by $\mathbf{q}_{J}$ the marginal of $\mathcal{D}_{J}$ over ${\mathcal{Y}}$ ; note that, crucially, $\mathbf{q}_{J}\in\Delta_{J}$ . Therefore, by definition of $h_{S}$ and of $s$ :

\displaystyle L_{\mathcal{D}_{J}}^{w}(h_{S})=w(\mathbf{p}_{J},\mathbf{q}_{J})\leq\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p}_{J},\mathbf{q})=\operatorname{V}_{J}(w)\leq v_{\overline{s}}\leq z\;.

(76)

We conclude that $L_{\mathcal{D}}^{w}(h_{S})\leq z+\epsilon$ . ∎

5.4 Lower bounds

We start proving the second item of C.

Lemma 37.

Let ${\mathcal{Y}}=[k]$ and let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be any cost function. Let $0=v_{1}(w)\leq v_{2}(w)\leq\cdots\leq v_{\tau}(w)$ as defined in Equation 6, and let $n$ be the largest integer for which $v_{n}(w)\leq z$ . Then there exists a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ that has a $(w,z)$ -learner but no $(w,z^{\prime})$ -learner for any $z^{\prime}<v_{n}(w)$ .

Proof.

If $v_{n}(w)=0$ then the claim is trivial, hence we assume $v_{n}(w)>0$ . Observe that this implies that there exists some $J$ with $|J|\geq 2$ such that $v_{n}(w)=V_{J}(w)$ . Let $\mathbf{p}^{*}\in\Delta_{\mathcal{Y}}$ be the distribution achieving $\operatorname{V}_{J}(w)$ , that is:

\mathbf{p}^{*}=\mathop{\rm arg\,min}_{\mathbf{p}\in\Delta_{\mathcal{Y}}}\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p},\mathbf{q})\;.

(77)

Now let ${\mathcal{X}}$ be any infinite domain (e.g., ${\mathcal{X}}=\mathbb{N}$ ) and let $\mathcal{F}=J^{\mathcal{X}}$ . For every distribution $\mathcal{D}$ over ${\mathcal{X}}$ and every labeling $f:{\mathcal{X}}\to J$ ,

\displaystyle L_{\mathcal{D}}^{w}(\mathbf{p}^{*})

\displaystyle=w(\mathbf{p}^{*},\mathbf{q}_{\mathcal{D}})\leq\max_{\mathbf{q}\in\Delta_{J}}w(\mathbf{p}^{*},\mathbf{q})=\operatorname{V}_{J}(w)=v_{n}(w)\leq z\;,

(78)

where $\mathbf{q}_{\mathcal{D}}\in\Delta_{J}$ is the marginal of $\mathcal{D}$ over ${\mathcal{Y}}$ . Thus the learner that returns the random guess $h$ based on $\mathbf{p}^{*}$ is a $(w,z)$ -learner for $\mathcal{F}$ .

Next, we show that $\mathcal{F}$ has no $(w,z^{\prime})$ -learner with $z^{\prime}<v_{n}(w)$ . Suppose indeed towards a contradiction that there exists such a $(w,z^{\prime})$ -learner ${\mathcal{A}}$ . By Theorem 24, then, $\mathcal{F}$ admits a $(w,z^{\prime})$ -list learner $\mathcal{L}$ . Now, as $z^{\prime}<v_{n}=\operatorname{V}_{J}(w)$ , the list function $\mu$ returned by $\mathcal{L}$ ensures $J\not\subseteq\mu(x)$ for all $x\in{\mathcal{X}}$ . Moreover, as $F=J^{\mathcal{X}}$ , we can assume without loss of generality that $\mu(x)\subseteq J$ for all $x\in{\mathcal{X}}$ ; otherwise we could remove the elements of $\mu(x)\setminus J$ to obtain a list $\mu^{\prime}(x)$ such that $\operatorname{V}_{\mu^{\prime}(x)}(w)\leq\operatorname{V}_{\mu(x)}(w)$ and that $\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[f(x)\in\mu^{\prime}(x)]\geq\operatorname{\mathbb{P}}_{x\sim\mathcal{D}}[f(x)\in\mu(x)]$ . It follows that $\mu(x)\subsetneq J$ for all $x\in{\mathcal{X}}$ . Therefore, $\mathcal{L}$ is a $(|J|-1)$ -list PAC learner. However, one can verify that the $(|J|-1)$ -Daniely-Shalev-Shwartz dimension of $\mathcal{F}$ is unbounded (see Definition 6 of Charikar and Pabbaraju (2023)). It follows by Charikar and Pabbaraju (2023, Theorem 1) that $\mathcal{F}$ is not $(|J|-1)$ -list PAC learnable, yielding a contradiction. ∎

Next, we prove the second item of Theorem 33.

Lemma 38.

Let ${\mathcal{Y}}=[k]$ , let $w:{\mathcal{Y}}^{2}\rightarrow[0,1]$ be any cost function, and let $v_{\underline{2}}\leq\ldots\leq v_{\underline{k}}$ as defined in Equation (65). Let $z\geq v_{\underline{2}}$ and let $s\leq k$ be the largest integer for which $z\geq v_{\underline{s}}$ . Then, there exists a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ that has a $(w,z)$ -learner and is not $(s-1)$ -list PAC learnable.

Proof.

The proof follows closely the one of Lemma 37. Let $J=\arg\min\left\{\operatorname{V}_{J^{\prime}}(w):J^{\prime}\in{{\mathcal{Y}}\choose s}\right\}$ . Let ${\mathcal{X}}$ be any infinite domain (e.g., ${\mathcal{X}}=\mathbb{N}$ ) and let $\mathcal{F}=J^{\mathcal{X}}$ . As in the proof of Lemma 37 there is a distribution $\mathbf{p}^{*}$ yielding a $(w,z)$ -learner for $\mathcal{F}$ . Simultaneously (again from the proof of Lemma 37), the class $\mathcal{F}$ is not $(s-1)$ -list PAC learnable. ∎

Finally, we prove the second item of D.

Lemma 39.

Let ${\mathcal{Y}}=[k]$ , let $\boldsymbol{w}=(w_{1},\ldots,w_{r})$ where each $w_{i}:{\mathcal{Y}}^{2}\rightarrow[0,1]$ is a cost function, and let $\boldsymbol{z},\boldsymbol{z}^{\prime}\in[0,1]^{r}$ such that $\boldsymbol{z}\not\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ . There exists a class $\mathcal{F}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ that admits a $(\boldsymbol{w},\boldsymbol{z})$ -learner that is trivial, and therefore cannot be boosted to a $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -learner.

Proof.

By assumption that $\boldsymbol{z}\not\preceq_{\boldsymbol{w}}\boldsymbol{z}^{\prime}$ , there must be a set $J\subseteq{\mathcal{Y}}$ for which $\boldsymbol{z}\in D_{J}(\boldsymbol{w})$ and $\boldsymbol{z}^{\prime}\notin D_{J}(\boldsymbol{w})$ . Let ${\mathcal{X}}$ be any infinite domain (e.g., ${\mathcal{X}}=\mathbb{N}$ ) and let $\mathcal{F}=J^{\mathcal{X}}$ . By definition of $D_{J}(\boldsymbol{w})$ there exists a trivial learner that is a $(\boldsymbol{w},\boldsymbol{z})$ -learner for $\mathcal{F}$ . Assume towards contradiction that the trivial learner can be used to construct a $(\boldsymbol{w},\boldsymbol{z}^{\prime})$ -learner for $\mathcal{F}$ . Since $\boldsymbol{z}^{\prime}\notin D_{J}(\boldsymbol{w})$ , then by Proposition 19 there exists $\boldsymbol{\alpha}\in\Delta_{r}$ such that $\langle\boldsymbol{\alpha},\boldsymbol{z}^{\prime}\rangle<\operatorname{V}_{J}(w_{\boldsymbol{\alpha}})$ , where $w_{\boldsymbol{\alpha}}=\sum_{i=1}^{r}\alpha_{i}w_{i}$ . Then, by Theorem 24, there is a $(w_{\boldsymbol{\alpha}},z_{\boldsymbol{\alpha}}^{\prime})$ -list learner $\mathcal{L}^{\prime}$ that outputs list functions $\mu$ such that, for every $x\in{\mathcal{X}}$ it holds that:

V_{\mu(x)}(w_{\boldsymbol{\alpha}})\leq z_{\boldsymbol{\alpha}}^{\prime}<\operatorname{V}_{J}(w_{\boldsymbol{\alpha}}).

Thus $\mathcal{L}^{\prime}$ is a $(|J|-1)$ -list PAC learner for $\mathcal{F}$ . However, one can verify that the $(|J|-1)$ -Daniely-Shalev-Shwartz dimension of $\mathcal{F}$ is unbounded (see Definition 6 of Charikar and Pabbaraju (2023)). It follows by Charikar and Pabbaraju (2023, Theorem 1) that $\mathcal{F}$ is not $(|J|-1)$ -list PAC learnable, yielding a contradiction. ∎

References

Allwein et al. [2000] Erin L Allwein, Robert E Schapire, and Yoram Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of machine learning research, 1(Dec):113–141, 2000.
Ben-David et al. [2001] Shai Ben-David, Philip M Long, and Yishay Mansour. Agnostic boosting. In International Conference on Computational Learning Theory, pages 507–516. Springer, 2001.
Blackwell [1956] D Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1–8, 1956.
Brukhim et al. [2021] Nataly Brukhim, Elad Hazan, Shay Moran, and Robert E. Schapire. Multiclass boosting and the cost of weak learning. In Advances in Neural Information Processing Systems, NeurIPS, 2021.
Brukhim et al. [2022] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In Annual Symposium on Foundations of Computer Science, FOCS, 2022.
Brukhim et al. [2023a] Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: simple and intuitive weak learning criteria. In Advances in Neural Information Processing Systems, NeurIPS, 2023a.
Brukhim et al. [2023b] Nataly Brukhim, Steve Hanneke, and Shay Moran. Improper multiclass boosting. In Proceedings of the Conference on Learning Theory, COLT, 2023b.
Canonne [2020] Clément L. Canonne. A short note on learning discrete distributions, 2020. URL https://arxiv.org/abs/2002.11457.
Charikar and Pabbaraju [2023] Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the Annual Symposium on Theory of Computing, STOC, 2023.
Durgin and Juba [2019] Alexander Durgin and Brendan Juba. Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs. In Proceedings of the International Conference on Algorithmic Learning Theory, ALT, 2019.
Ehrgott [2005] Matthias Ehrgott. Multicriteria optimization, volume 491. Springer Science & Business Media, 2005.
Elkan [2001] Charles Elkan. The foundations of cost-sensitive learning. In Bernhard Nebel, editor, Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI, pages 973–978, 2001.
Fan et al. [1999] Wei Fan, Salvatore J. Stolfo, Junxin Zhang, and Philip K. Chan. Adacost: Misclassification cost-sensitive boosting. In Proceedings of the International Conference on Machine Learning, ICML, 1999.
Feldman [2009] Vitaly Feldman. Distribution-specific agnostic boosting. arXiv preprint arXiv:0909.2927, 2009.
Freund [1990] Yoav Freund. Boosting a weak learning algorithm by majority. In Proceedings of the Workshop on Computational Learning Theory, COLT, 1990. URL http://dl.acm.org/citation.cfm?id=92640.
Freund and Schapire [1997] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119–139, 1997. URL https://doi.org/10.1006/jcss.1997.1504.
Green Larsen and Ritzert [2022] Kasper Green Larsen and Martin Ritzert. Optimal weak to strong learning. Advances in Neural Information Processing Systems, 35:32830–32841, 2022.
Kalai and Servedio [2005] Adam Tauman Kalai and Rocco A. Servedio. Boosting in the presence of noise. J. Comput. Syst. Sci., 71(3):266–290, 2005. doi: 10.1016/j.jcss.2004.10.015. URL https://doi.org/10.1016/j.jcss.2004.10.015.
Kalai et al. [2008] Adam Tauman Kalai, Yishay Mansour, and Elad Verbin. On agnostic boosting and parity learning. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 629–638, 2008.
Kalai et al. [2012] Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. Journal of Computer and System Sciences, 78(5):1481–1495, 2012.
Kanade and Kalai [2009] Varun Kanade and Adam Kalai. Potential-based agnostic boosting. In Advances in neural information processing systems, NIPS, 2009.
Kanade and Thaler [2014] Varun Kanade and Justin Thaler. Distribution-independent reliable learning. In Proceedings of the Conference on Learning Theory, COLT, 2014.
Karakoulas and Shawe-Taylor [1998] Grigoris I. Karakoulas and John Shawe-Taylor. Optimizing classifers for imbalanced training sets. In Advances in Neural Information Processing Systems, NIPS, 1998.
Kearns [1988] M. Kearns. Thoughts on hypothesis boosting. Unpublished, December 1988.
Kivinen [1995] Jyrki Kivinen. Learning reliably and with one-sided error. Mathematical systems theory, 28(2):141–172, 1995.
Landesa-Vazquez and Alba-Castro [2012] Iago Landesa-Vazquez and José Luis Alba-Castro. Shedding light on the asymmetric learning capability of adaboost. Pattern Recognition Letters, 33(3):247–255, 2012. URL https://doi.org/10.1016/j.patrec.2011.10.022.
Landesa-Vazquez and Alba-Castro [2013] Iago Landesa-Vazquez and José Luis Alba-Castro. Double-base asymmetric adaboost. Neurocomputing, 118:101–114, 2013. URL https://doi.org/10.1016/j.neucom.2013.02.019.
Landesa-Vázquez and Alba-Castro [2015] Iago Landesa-Vázquez and José Luis Alba-Castro. Revisiting adaboost for cost-sensitive classification. part i: Theoretical perspective. arXiv preprint arXiv:1507.04125, 2015.
Ling and Sheng [2008] Charles X Ling and Victor S Sheng. Cost-sensitive learning and the class imbalance problem. Encyclopedia of Machine Learning, 2011:231–235, 2008.
Ling and Sheng [2017] Charles X. Ling and Victor S. Sheng. Cost-sensitive learning. In Encyclopedia of Machine Learning and Data Mining. Springer, 2017. URL https://doi.org/10.1007/978-1-4899-7687-1_181.
Long and Servedio [2008] Philip M. Long and Rocco A. Servedio. Adaptive martingale boosting. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 977–984. Curran Associates, Inc., 2008. URL http://papers.nips.cc/paper/3623-adaptive-martingale-boosting.
Masnadi-Shirazi and Vasconcelos [2011] Hamed Masnadi-Shirazi and Nuno Vasconcelos. Cost-sensitive boosting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(2):294–309, 2011. URL https://doi.org/10.1109/TPAMI.2010.71.
Møller Høgsgaard et al. [2024] Mikael Møller Høgsgaard, Kasper Green Larsen, and Markus Engelund Mathiasen. The many faces of optimal weak-to-strong learning. arXiv e-prints, pages arXiv–2408, 2024.
Mukherjee and Schapire [2011] Indraneel Mukherjee and Robert E Schapire. A theory of multiclass boosting. Journal of Machine Learning Research, 14:437–497, 2011. URL http://rob.schapire.net/papers/multiboost-journal.pdfhttp://arxiv.org/abs/1108.2989.
Nikolaou et al. [2016] Nikolaos Nikolaou, Narayanan Unny Edakunni, Meelis Kull, Peter A. Flach, and Gavin Brown. Cost-sensitive boosting algorithms: Do we really need them? Machine Learning, 104(2-3):359–384, 2016. URL https://doi.org/10.1007/s10994-016-5572-x.
Raman and Tewari [2022] Vinod Raman and Ambuj Tewari. Online agnostic multiclass boosting. Advances in Neural Information Processing Systems, 35:25908–25920, 2022.
Raman et al. [2019] Vinod Raman, Daniel T Zhang, Young Hun Jung, and Ambuj Tewari. Online boosting for multilabel ranking with top-k feedback. arXiv preprint arXiv:1910.10937, 2019.
Sabato and Tishby [2012] Sivan Sabato and Naftali Tishby. Multi-instance learning with any hypothesis class. The Journal of Machine Learning Research, 13(1):2999–3039, 2012.
Schapire [1990] Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990. URL https://doi.org/10.1007/BF00116037.
Schapire and Freund [2012] Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. Cambridge university press, 2012.
Schapire and Singer [1999] Robert E Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, 1999.
Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
Sun et al. [2007] Yanmin Sun, Mohamed S. Kamel, Andrew K. C. Wong, and Yang Wang. Cost-sensitive boosting for classification of imbalanced data. Pattern Recognition, 40(12):3358–3378, 2007. URL https://doi.org/10.1016/j.patcog.2007.04.009.
Ting [2000] Kai Ming Ting. A comparative study of cost-sensitive boosting algorithms. In Proceedings of the International Conference on Machine Learning, ICML, 2000.
Valiant [1984] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
Viola and Jones [2001] Paul A. Viola and Michael J. Jones. Fast and robust classification using asymmetric adaboost and a detector cascade. In Advances in Neural Information Processing Systems, NIPS, 2001.
von Neumann [1928] John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100(1):295–320, 1928.
Zadrozny et al. [2003] Bianca Zadrozny, John Langford, and Naoki Abe. Cost-sensitive learning by cost-proportionate example weighting. In International Conference on Data Mining, ICDM, 2003.

Appendix A Cost-Sensitive Learning

Cost sensitive learning has a long history in machine learning. The two main motivations are that, first, not all errors have the same impact, and second, that there might be a class-imbalance between the frequency of different classes. Over the years there have been many workshops on cost-sensitive learning in ICML (2000) NIPS (2008) SDM (2018), yet another indication of the impostance of cost-sensitive loss. See, e.g., Ling and Sheng [2017, 2008]. Recall the definition of the cost sensitive loss:

L_{\mathcal{D}}^{w}(h)={\mathbb E}_{x\sim\mathcal{D}}\Bigl{[}w(h(x),f(x))\Bigr{]}\,.

(79)

Given the the distribution $\mathcal{D}$ on ${\mathcal{X}}$ , the Bayes optimal prediction rule is given by:

\displaystyle\arg\min_{i\in{\mathcal{Y}}}\sum_{j\in{\mathcal{Y}}}w(i,j)\operatorname{\mathbb{P}}[f(x)=j\mid x]

(80)

for every $x\in{\mathcal{X}}$ . The early works include Elkan [2001], which characterizes the Bayes optimal predictor as a threshold, and its implication for re-balancing and decision tree learning. In fact, this resembles our binary prediction rule.

Sample complexity for cost-sensitive leaning for large margin appears in Karakoulas and Shawe-Taylor [1998]. Additional sample complexity bounds, for cost-sensitive learning, based on transformation of the learning algorithms and using rejection sampling is found in Zadrozny et al. [2003]. The idea of cost sensitive learning has a long history in statistics. For binary classification, there are many different metrics used for evaluation. Let $w=\begin{pmatrix}w_{++}&w_{+-}\\ w_{-+}&w_{--}\end{pmatrix}$ . The false-positive (FP) is $w_{+-}$ , the false-negative is $w_{-+}$ , the precision is $w_{++}/(w_{++}+w_{+-})$ , the recall is $w_{++}/(w_{++}+w_{-+})$ , and more.

A.1 Boosting cost-sensitive loss

There has been significant amount of work with the motivation of adapting AdaBoost to a cost-sensitive loss. At a high level, the different proposals either modify the way the algorithm updates its weights, taking in to account the cost-sensitive loss, or changes the final prediction rule. Nikolaou et al. [2016] give an overview on various AdaBoost variants for the cost-sensitive case. See also Landesa-Vázquez and Alba-Castro [2015]. Our modified update rule of Hedge in Algorithm 1 corresponds to CGAda of Sun et al. [2007] and related AdaBoost variants.

The theoretically sound proposal focused on deriving similar guarantees to that of AdaBoost. Cost-sensitive boosting by Masnadi-Shirazi and Vasconcelos [2011] modified the exponential updates to include the cost-sensitive loss. Cost-Generalized AdaBoost by Landesa-Vazquez and Alba-Castro [2012] modifies the initial distribution over the examples. AdaboostDB by Landesa-Vazquez and Alba-Castro [2013] modifies the base of the exponents used in the updates. All the theoretically sound proposal are aimed to guarantee convergence under the standard weak-leaning assumption. Their main objective is to derive better empirical results when faced with a cost-sensitive loss. However, they do not address the essential question, when is boosting possible? In particular, they do not study cost-sensitive variants weak learners and do not characterize the boostability of such learners. In addition to the papers above, there have been many heuristic modifications of AdaBoost which try to address the cost-sensitive loss [Karakoulas and Shawe-Taylor, 1998, Fan et al., 1999, Ting, 2000, Viola and Jones, 2001, Sun et al., 2007].

A.2 Multi-objective learning and boosting

Learning with multiple objectives is also common in machine learning. A well studied special case are variants of learning with one-sided error [Kivinen, 1995, Sabato and Tishby, 2012]. A typical goal in one-sided learning or the related positive-reliable learning [Kalai et al., 2012, Kanade and Thaler, 2014, Durgin and Juba, 2019] is to guarantee an (almost) $0$ false positive loss and simultaneously a low false negative loss. This corresponds to a $(\boldsymbol{w},\boldsymbol{z})$ -learner with $\boldsymbol{w}=(w_{+},w_{-})$ and $\boldsymbol{z}=(0,\epsilon)$ . More generally, Kalai et al. [2012] also considered tolerant reliable learning with an arbitrary $\boldsymbol{z}=(z_{+},z_{-})$ . Our results apply in this context. For example in the binary case, our results show that a $(\boldsymbol{w},\boldsymbol{z})$ -learner (i.e., a $\boldsymbol{z}$ -tolerant-reliable one) is boostable if and only if $\sqrt{z_{+}}+\sqrt{z_{-}}<1$ . Moreover, our results also imply boostability and learnability results for reliable learning in the multi-class case; a learning setting mostly over-looked so far.

Appendix B Multiclass Boosting

Boosting is a fundamental methodology in machine learning that can boost the accuracy of weak learning rules into a strong one. Boosting theory was originally designed for binary classification. The study of boosting was initiating in a line of seminal works which include the celebrated Adaboost algorithm, as well an many other algorithms with various applications, (see e.g. Kearns [1988], Schapire [1990], Freund [1990], Freund and Schapire [1997]). It was later adapted to other settings and was extensively studied in broader contexts as well [Ben-David et al., 2001, Kalai and Servedio, 2005, Long and Servedio, 2008, Kalai et al., 2008, Kanade and Kalai, 2009, Feldman, 2009, Møller Høgsgaard et al., 2024, Green Larsen and Ritzert, 2022, Raman and Tewari, 2022, Raman et al., 2019].

There are also various extension of boosting to the multiclass setting. The early extensions include AdaBoost.MH, AdaBoost.MR, and approaches based on Error-Correcting Output Codes (ECOC) [Schapire and Singer, 1999, Allwein et al., 2000]. These works often reduce the $k$ -class task into a single binary task. The binary reduction can have various problems, including increased complexity, and lack of guarantees of an optimal joint predictor.

Notably, a work by Mukherjee and Schapire [2011] established a theoretical framework for multiclass boosting, which generalizes previous learning conditions. However, this requires the assumption that the weak learner minimizes a complicated loss function, that is significantly different from simple classification error.

More recently, there have been several works on multiclass boosting. First, Brukhim et al. [2021] followed a formulation for multiclass boosting similar to that of Mukherjee and Schapire [2011]. They proved a certain hardness result showing that a broad, yet restricted, class of boosting algorithms must incur a cost which scales polynomially with $|{\mathcal{Y}}|$ . Then, Brukhim et al. [2023b] and Brukhim et al. [2023a] demonstrated efficient methods for multiclass boosting. We note that our work generalizes the results given in Brukhim et al. [2023a] to the cost sensitive setting, as detailed in Section 5.

	Binary	Multiclass
0-1 loss	$1/2$	$\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots,\frac{k-1}{k}$
cost $w$	$V(w)=\frac{w_{+}w_{-}}{w_{+}+w_{-}}$	$v_{{2}}(w)\leq\dots\leq v_{{\tau}}(w)$
multi-objective $\boldsymbol{w}=(w_{1},\dots,w_{r})$	coin-attainable boundary of $C(\boldsymbol{w})$	$J$ -dice-attainable boundaries of $D_{J}(\boldsymbol{w})$

Of Dice and Games: A Theory of Generalized Boosting

Abstract

1 Introduction

Organization of the manuscript.

2 Main Results

2.1 Binary setting

Definition 1 ((w,z)(w,z)-learner).

Definition 2 (Random guess).

Theorem A (Cost-sensitive boosting, binary case).

2.1.1 Multi-objective losses

Definition 3 ((𝒘,𝒛)(\boldsymbol{w},\boldsymbol{z})-learner).

Definition 4 (Coin attainability).

Definition 5 (Trivial learner).

Theorem B (Multi-objective boosting, binary case).

Geometric interpretation of B.

2.1.2 Cost-sensitive vs. multi-objective losses: a general equivalence

Theorem 6 (Equivalence of learners).

Theorem 7 (Equivalence of trivial guarantees).

2.2 Multiclass setting

Fact 8.

Theorem C (Cost-sensitive boosting, multiclass case).

2.2.1 Multiclass classification, multi-objective loss

Definition 9 (JJ-dice attainability).

Theorem D (Multi-objective boosting, multiclass case).

3 Binary Classification

Definition 10 (Margin, binary case).

3.1 Boosting a (w,z)(w,z)-learner

Theorem 11.

Lemma 12.

Proof.

Lemma 13.

Proof.

Remark on adaptive boosting.

Lemma 14.

Proof.

3.2 Multi-objective losses: boosting a (𝒘,𝐳)(\boldsymbol{w},\mathbf{z})-learner

3.2.1 Coin attainability

Definition 15.

3.2.2 Coin-attainability equals non-boostability

Theorem 16.

Proof.

3.3 A duality, and a geometric interpretation

Theorem 17.

3.4 Proof of B

4 Equivalence: Cost-Sensitive and Multi-Objective

Lemma 18.

Proof.

Proposition 19.

Proof of Proposition 19.

Proof of Theorem 6.

5 Multiclass Classification

5.1 Cost-sensitive boosting

Definition 20 ((w,z)(w,z)-boundedness).

Definition 21 ((w,z)(w,z)-list learner).

Theorem 22.

5.1.1 Turning a (w,z)(w,z)-learner into a (w,z)(w,z)-list learner

Definition 23 (Margin).

Theorem 24 (Weak ⇒\Rightarrow List Learning).

Lemma 25.

Proof.

Lemma 26.

Proof.

Proof of Theorem 24.

5.1.2 Turning a (w,z)(w,z)-list learner into a (w,z)(w,z)-learner

Lemma 27 (List ⇒\Rightarrow Weak Learning).

Proof.

5.2 Multi-objective losses

Theorem 28.

Proof.

Lemma 29.

Proof.

Definition 30 (av⁡(𝒘,𝒛)\operatorname{av}(\boldsymbol{w},\boldsymbol{z})-list learner).

Lemma 31.

Proof.

5.3 Multiclass boosting via ss-list PAC learning

Definition 32 (ss-List PAC Learning (Brukhim et al., 2022; Charikar and Pabbaraju, 2023)).

Theorem 33.

Lemma 34.

Proof.

Lemma 35.

Of Dice and Games:
A Theory of Generalized Boosting

Definition 1 ( $(w,z)$ -learner).

Definition 3 ( $(\boldsymbol{w},\boldsymbol{z})$ -learner).

Definition 9 ( $J$ -dice attainability).

3.1 Boosting a $(w,z)$ -learner

3.2 Multi-objective losses: boosting a $(\boldsymbol{w},\mathbf{z})$ -learner

Definition 20 ( $(w,z)$ -boundedness).

Definition 21 ( $(w,z)$ -list learner).

5.1.1 Turning a $(w,z)$ -learner into a $(w,z)$ -list learner

Theorem 24 (Weak $\Rightarrow$ List Learning).

5.1.2 Turning a $(w,z)$ -list learner into a $(w,z)$ -learner

Lemma 27 (List $\Rightarrow$ Weak Learning).

Definition 30 ( $\operatorname{av}(\boldsymbol{w},\boldsymbol{z})$ -list learner).

5.3 Multiclass boosting via $s$ -list PAC learning

Definition 32 ( $s$ -List PAC Learning (Brukhim et al., 2022; Charikar and Pabbaraju, 2023)).

Theorem 36 ( $s$ -List $\Rightarrow$ Weak Learning).