Constrained Classification and Policy Learning

Constrained Classification and Policy Learning

Keywords: Surrogate loss, support vector machine, monotone classification, fairness in machine learning, statistical treatment choice, personalized medicine

\onehalfspacing

Introduction

Binary classification, the prediction of a binary dependent variable $Y \in \{-1, +1\}$ based upon covariate information $X \in \mathcal{X}$, is one of the most fundamental problems in statistics and econometrics. Many modern machine learning algorithms build on statistically and computationally efficient classification algorithms, and their application has had a sizeable impact on various fields of study and in society in general, e.g., pattern recognition, credit approval systems, personalized recommendation systems, to list but a few examples. Since estimation of an optimal treatment assignment policy can be cast as a weighted (cost-sensitive) classification problem (Zadrozny03), methodological advances in the study of the classification problem apply to the causal problem of designing individualized treatment assignment policies. As the allocation of resources in both business and public policy settings has become more evidence-based and dependent upon algorithms, so too has there been increasingly active debate on how to make allocation algorithms respect societal preferences for interpretability and fairness (Dwork_et_al_2012). Understanding the theoretical performance guarantee and efficient implementation of classification algorithms under interpretability or fairness constraints is a problem of fundamental importance with a strong connection to real life.

In the supervised binary classification problem, the typical objective is to learn a classification rule that minimizes the probability of false prediction. We denote the distribution of $(Y,X)$ by $P$, and a (non-randomized) classifier that predicts $Y \in \{-1, +1 \}$ based upon $\text{sign}(f(X))$ by $f: \mathcal{X} \to \mathbb{R}$, where $\text{sign}(\alpha) = 1\{\alpha \geq 0\} - 1\{ \alpha < 0\}$. We denote the 0-level set of $f$ by $G_f \equiv \{x \in \mathcal{X} : f(x) \geq 0 \} \subset \mathcal{X}$, and refer to $G_f$ as the prediction set of $f$. The goal is to learn a classifier that minimizes classification risk:

Given a training sample $\{ (Y_i,X_i) \sim_{iid} P : i=1,\dots,n \}$, the empirical risk minimization principle of Vapnik98 recommends estimating the optimal classifier by minimizing empirical classification risk,

over a class of classifiers $\mathcal{F} = \{f : \mathcal{X} \to \mathbb{R} \}$. If the complexity of $\mathcal{F}$ is properly constrained, the empirical risk minimizing (ERM) classifier $\hat{f}$ has statistically attractive properties including risk consistency and minimax rate optimality. See, for example, DGLbook96 and Lugosi02.

Despite the desirable performance guarantee of the ERM classifer, the computational complexity of solving the optimization in ((ref)) becomes a serious hurdle to practical implementation, especially when the dimension of covariates is moderate to large. To get around this issue, the existing literature has offered various alternatives to the ERM classifier, including support vector machines (Cortes_Vapnik_1995), AdaBoost (Freund_Schapire_1997), and neural networks. Focusing on optimization, each of these algorithms can be viewed as targeting the minimization of surrogate risk,

where $\phi: \mathbb{R} \to \mathbb{R}$ is called the surrogate loss function, a different specification of which corresponds to a different learning algorithm. Convex functions make for a desirable choice of surrogate loss function as, combined with some functional form specification for $f$, the minimization problem for the empirical analogue of the surrogate risk in ((ref)) is a convex optimization problem. This insight and the computational benefit that it yields has been pivotal to learning algorithms being able to handle large scale problems with high-dimensional features.

Can surrogate risk minimization lead to an optimal classifier in terms of the original classification risk? The seminal works of Zhang_2004 and Bartlett_et_al_2006 provide theoretical justification for the use of surrogate losses by clarifying the conditions under which surrogate risk minimization also minimizes the original classification risk. A crucial assumption for this important result is correct specification of the classifiers, requiring that the class of classifiers $\mathcal{F}$ over which the surrogate risk is minimized contains a classifier that globally minimizes the original classification risk, i.e., a classifier that is identical to or performs as well as the Bayes classifier $f^{\ast}_{Bayes}(x) \equiv 2 P(Y=1|X=x) -1$ in terms of its classification risk.

The credibility of the assumption of correct specification is, however, limited if the set of implementable classifiers is constrained exogenously, independently of any belief concerning the underlying data generating process. Such a situation is becoming more prevalent due to the increasing need for interpretability or fairness of classification algorithms. Given that $f$ determines the classification rule only through $G_f$, such constraints can be represented by shape restrictions on the prediction set of $f$, i.e., the class of feasible $f$ is represented by $\mathcal{F}_{\mathcal{G}} \equiv \{f \in \mathcal{F} : G_f \in \mathcal{G} \}$, where $\mathcal{G}$ is a restricted class of sets in $\mathcal{X}$ satisfying the requirements for interpretability and fairness. To the best of our knowledge, how the validity of a surrogate loss approach is affected if $\mathcal{F}_{\mathcal{G}}$ misses the first-best classifier is not known.

The main contribution of this paper is to establish conditions under which a surrogate loss approach is valid without assuming correct specification. We first characterize those conditions on surrogate loss such that minimization of the surrogate risk can lead to a second-best rule (i.e., constrained optimum) in terms of the original classification risk. Specifically, we show that hinge losses $\phi_h(\alpha) = c \max\{ 0, 1- \alpha \}$, $c>0$, are the only surrogate losses that guarantee consistency of the surrogate risk minimization for a second-best classifier. An important implication of this result is that $\ell_1$-support vector machines are the only surrogate loss-based methods that are robust to misspecification.

The computational attractiveness of a surrogate loss approach crucially depends not only upon the convexity of the surrogate loss function $\phi$ but also upon the functional form restrictions on the classifer $f$ that lead to a convex $\mathcal{F}$. We therefore investigate how additional constraints on $f$ on top of $G_f \in \mathcal{G}$ can affect the consistency of the hinge risk minimization. As a second contribution of this paper, we characterize a simple-to-check sufficient condition for consistency of the hinge risk minimization in terms of the additional functional form restrictions we can impose on $\mathcal{F}_{\mathcal{G}}$. We term a subclass of classifiers of $\mathcal{F}_{\mathcal{G}}$ satisfying the sufficient condition a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$.

Exploiting our main theoretical results, we develop novel procedures for monotone classification. In monotone classification, prediction sets are constrained to

where $x' \leq x$ is an element-wise weak inequality. Since $\mathcal{G}_M$ coincides with the class of prediction sets spanned by the class of monotonically decreasing bounded functions $\mathcal{F}_M \equiv \{ f: f \ \text{decreasing in }x, \ -1 \leq f \leq 1 \}$, hinge loss-based estimation for monotone classification can be performed by solving

We show that the class of monotone classifiers $\mathcal{F}_M$ is a constrained classification-preserving reduction of $\mathcal{F}_{\mathcal{G}_M}$, guaranteeing consistency of the hinge-risk minimizing classifier $\hat{f}_M$. Furthermore, we show that convexity of $\mathcal{F}_{M}$ reduces the optimization of ((ref)) to a finite dimensional linear programming problem and hence delivers significant computational gains relative to minimization of the original empirical classification risk. We also consider approximating $\mathcal{F}_M$ using a sieve of Bernstein polynomials and estimating a monotone classifier by solving ((ref)) over the Bernstein polynomials. Adopting either approach, the application of our main theorems guarantees

as $n \to 0$, and this convergence is valid regardless of whether $\mathcal{F}_M$ attains the first-best risk, i.e., $\inf_{f \in \mathcal{F}_M} R(f) = \inf_{f \in \bar{\mathcal{F}}}R(f)$, or not, where $\bar{\mathcal{F}}$ is the class of measurable functions $f: \mathcal{X} \to \mathbb{R}$. We also derive the uniform upper bound of the mean of $R(\hat{f}_M) - \inf_{f \in \mathcal{F}_M}R(f)$ to characterize the regret convergence rate attained by $\hat{f}_M$.

Connection and contributions to causal policy learning

For simplicity of exposition, this paper mainly focuses on the prototypical setting of binary classification. The main theoretical results can easily be extended to weighted (cost-sensitive) classification, where the canonical representation of the population risk criterion is given by

Here, $\omega$ is a non-negative random variable defining the cost of misclassifying $Y$ that typically depends on $(Y,X)$. The cost of misclassification $\omega$ may represent the decision-maker's economic cost (LieliWhite2010) or welfare weights over the individuals to be classified, as considered in Rambachan_2020 and Babii_et_al_2020. The surrogate risk for weighted classification can be defined similarly to ((ref)), as

As discussed in KT18, there are fundamental conceptual differences between the prediction problem of classification and the causal problem of treatment choice. Nevertheless, if the training sample is obtained from a randomized control trial (RCT) or an observational study satisfying unconfoundedness (selection on observables), we can view minimization of the weighted classification risk in ((ref)) as being equivalent to the maximization of the additive welfare criterion commonly specified in treatment choice problems. To see this equivalence, let $\{ (Z_i,D_i,X_i) : i=1, \dots, n \}$ be an independent and identically distributed RCT sample of $n$ experimental subjects, where $Z_i \in \mathbb{R}$ is subject $i$'s observed outcome, $D_i \in \{-1, +1\}$ is an indicator for his assigned treatment, and $X_i \in \mathcal{X}$ is a vector of pretreatment covariates, and let $(Z_i(d): d \in \{-1,+1\})$ be $i$'s potential outcomes satisfying $Z_i= Z_i(+1) \cdot 1\{D_i = +1 \} + Z_i(-1) \cdot 1\{D_i = -1 \}$. We denote the propensity score in the RCT sample by $e(x) \equiv P(D = +1|X=x)$ and assume that $e(x)$ is bounded away from 0 and 1 for all $x \in \mathcal{X}$. We denote the joint distribution of $(Z_i(+1),Z_i(-1),D_i,X_i)$ by $P$ and assume $P$ satisfies unconfoundedness, $(Z(+1), Z(-1)) \perp D | X$.

Similar to our consideration of classification, we represent a (non-randomized) treatment assignment rule by the sign of $f: \mathcal{X} \to \mathbb{R}$ --i.e., the 0-level set $G_f = \{x \in \mathcal{X} : f(x) \geq 0 \} \subset \mathcal{X}$ specifies the subgroup of the population assigned to the treatment $+1$. Following Manski2004, we consider evaluating the welfare performance of the assignment policy $f$ by the average outcomes attained under its associated assignment rule:

Relying on unconfoundedness of the experimental data and employing the inverse propensity score weighting technique, we can express this welfare in terms of the observable variables as\footnote{KL21 makes use of this transformation of the welfare objective function to develop an Adaboost algorithm for treatment choice.}

Provided that the first moment of $ \omega_p$ is finite, maximization of $W(f)$ is equivalent to minimization of the weighted classification risk $R^{\omega}(f)$ defined in ((ref)) with $\omega = \omega_p$ and $Y=\mathrm{sign}(Z)\cdot D$. As a result, optimal treatment assignment rules can be viewed as optimal classifiers for $D$ in terms of weighted classification risk. This equivalence also holds for other methods of policy learning, such as the offset-tree learning of BeygelzimerLangford09 and the doubly-robust approaches of SJ15 and AW17, which correspond to different ways of constructing or estimating the weighting term $\omega_p$.

Due to its equivalence to weighted classification, a surrogate loss approach to policy learning proceeds by minimizing the empirical analogue of ((ref)) with $\omega = \omega_p$ and $Y=\mathrm{sign}(Z)\cdot D$. Section (ref) of this paper shows that our main theoretical results established for constrained binary classification carry over to the setting of policy learning in which feasible treatment assignment policies are constrained exogenously due to fairness and legislative considerations. This paper therefore offers valuable and novel contributions to current research and public debate regarding how to make use of machine learning algorithms to design individualized policies. If treatment assignment rules are constrained to be monotone, our concrete proposals for monotone classification algorithms can be applied to policy learning, which yields significant gains in computational efficiency relative to the mixed integer programming approaches considered in KT18 and MT17.

Related literature

This paper is closely related to the literature of consistency and performance guarantees for surrogate risk minimization. Notable works in this literature include Mannor_et_al_2003, Jiang_2004, Lugosi_Vayatis_2004 , Zhang_2004, Steinwart_2005, Steinwart_2007, Bartlett_et_al_2006, Nguyen_et_al_2009, and Scott_2012. Under the assumption of correct specification, Zhang_2004 and Bartlett_et_al_2006 derive quantitative relationships between excess classification risk and excess surrogate risk, and then provide general conditions for surrogate risk minimization to achieve risk consistency. Bartlett_et_al_2006 show that the classification-calibration property of surrogate loss, defined in Section (ref) below, guarantees risk consistency. Zhang_2004 and Bartlett_et_al_2006 show that many commonly used surrogate loss functions, including hinge loss, exponential loss, and truncated quadratic loss, satisfy the conditions needed for risk consistency. In a classification problem different from ours, where a pair comprising a quantizer and a classifier is chosen, Nguyen_et_al_2009 study sufficient and necessary conditions for surrogate risk minimization to yield risk consistency. Nguyen_et_al_2009 show that only hinge loss functions satisfy the conditions required for risk consistency in their problem. Correct specification of the class of classifiers is an essential condition for consistency in all of the surrogate risk minimization approaches studied in the literature. The key contribution of our paper is to relax the assumption of correct specification and to clarify the conditions that are required for the surrogate loss function to yield a consistent surrogate risk minimization procedure.

Relaxing the assumption of correct specification connects this paper to classification problems with exogenous constraints. Such problems are studied in machine learning and statistics, and include interpretable classification (e.g., Zeng_et_al_2017, and Zhang_et_al_2018), fair classification (e.g., Dwork_et_al_2012), and monotone classification (e.g., Cano_et_al_2019). Some works in the existing literature adopt a surrogate loss approach. Donini_et_al_2018 use the $\ell_1$-support vector machine in fair classification, where the hinge risk minimization is subject to a statistical fairness constraint. Chen_Li_2014 use the $\ell_1$-support vector machine with a monotonicity constraint, which constrains the class of feasible classifiers to a class of certain monotone functions. However, neither paper shows consistency of their hinge risk minimization procedures in terms of classification risk.

Agarwal_et_al_2018 propose an approach to reduce fairness constrained classification problems to weighted classification. Their reduction can accommodate various fairness constraints proposed in the machine learning literature and the monotonicy constraint of this paper if $X$ is discrete. Our consistency results on surrogate risk minimizing classifiers can apply to an arbitrary class $\mathcal{G}$ regardless of whether their reduction applies or not.

Focusing on optimization, ERM classification and maximum score estimation (Manski1975, ManskiThompson1989) share the same objective function. Horowitz_1992 proposes smooth maximum score estimation, where kernel smoothing is performed on the 0-1 loss to obtain a differentiable objective function. However, the smoothed objective function remains non-convex and does not offer the computational gains that the surrogate risk minimization approach with convex surrogates can deliver.

This paper also contributes to a growing literature on statistical treatment rules in econometrics, including Manski2004, Dehejia2005, HiranoPorter2009, Stoye2009,Stoye2012, Chamberlain2011, BhattacharyaDupas2012, Tetenov2012, Kasy2018, KT18, KT21, Viviano_2019, AW17, MT17, Sakaguchi_2021, KW23, among others. As discussed above, the policy learning methods of KT18, AW17, and MT17 build on the similarity between empirical welfare maximizing treatment choice and ERM classification. MT17 propose penalization methods to control the complexity of treatment assignment rules, and derive relevant finite sample upper bounds on the regret of the estimated treatment rules. AW17 apply doubly-robust estimators to estimate the weight $\omega$ in ((ref)), and show that an $1/\sqrt{n}$-upper bound on regret can also be achieved in the observational study setting. These works optimize an empirical welfare objective involving an indicator loss function. As a result, the practical implementation of such methods is sometimes discouraging, especially when the sample size or number of covariates is moderate to large.

Estimation of individualized treatment rules is a topic of active research in other fields including medical statistics, machine learning, and computer science. Notable works in these fields include Zadrozny03, BeygelzimerLangford09, Qian_Murphy_2011, Zhao2012JASA, SJ15, Zhao_et_al_2015, and Kallus_2020, among others. Zhao2012JASA propose using $\ell_{1}$-support vector machines to solve the weighted classification with individualized treatment choice problem, and show risk consistency. They specify a rich class of treatment choice rules that is a reproducing kernel Hilbert space, and assume correct specification. Zhao_et_al_2015 extend this approach to estimate optimal dynamic treatment regimes.

Constrained classification with surrogate loss

Consider the binary classification problem of ascribing a binary label $Y \in \{-1,+1\}$ based upon covariates $X \in \mathcal{X}$, which are collectively distributed according to a joint distribution $P$. We let $X$ be a $d_x$-dimensional vector, $d_x< \infty$, and denote its marginal distribution by $P_{X}$. We denote the conditional probability of $Y=+1$ given $X=x$ by $\eta(x) \equiv P(Y = +1|X=x)$ and otherwise maintain the notation introduced in the Introduction. The ultimate objective is to minimize the classification risk of ((ref)).

We study constrained classification problems where an optimal classifier is searched for over a restricted class of functions. Section (ref) studies the consistency of surrogate risk minimization in the special case that the prespecified class of classifiers contains a classifier whose prediction set agrees with the prediction set of the Bayes classifier. Section (ref) introduces a classification problem that embeds a constraint on the prediction sets, which is a central problem throughout the paper.

Misspecification in constrained classification

Let $\mathcal{F}$ be a constrained class of classifiers $f: \mathcal{X} \rightarrow \mathbb{R}$. If the set of classifiers were unconstrained, it is well known that the Bayes classifier defined by

minimizes the classification risk. Due to the constraints on the class of classifiers, however, the minimized classification risk on $\mathcal{F}$ can be strictly larger than the first-best minimal risk $R(f^{\ast}_{Bayes})$. We refer to this situation as $R$-misspecification of $\mathcal{F}$, which we formally define in the following definition.

Because the 0-1 loss function is neither convex nor continuous, minimizing the empirical analog of $R(f)$ is computationally challenging and often infeasible given the scale of the problems that we encounter in practice. Commonly used classification algorithms, such as boosting and support vector machines, replace the 0-1 loss with a surrogate loss function, $\phi:\mathbb{R}\rightarrow\mathbb{R}$, and aim to minimize the surrogate risk $R_{\phi}(f) \equiv E_P[\phi(Yf(X))]$. Table (ref) below lists some commonly used surrogate loss functions including the hinge loss $\phi_h(\alpha)=c\max\{0, 1-\alpha\}$, which corresponds to $\ell_1$-support vector machines, and the exponential loss $\phi_e(\alpha)=\exp(-\alpha)$, which corresponds to AdaBoost.

We also introduce the concept of misspecification of $\mathcal{F}$ in terms of surrogate risk as follows.

The seminal theoretical results that guarantee consistency of surrogate-risk classification (Zhang_2004, Bartlett_et_al_2006, and Nguyen_et_al_2009) crucially rely on the assumption that $\mathcal{F}$ is both $R$-correctly specified and $R_{\phi}$-correctly specified in the sense of Definitions (ref) and (ref), respectively. The central question that this paper poses is how is a surrogate loss approach affected if $\mathcal{F}$ is $R$-misspecified or $R_\phi$-misspecified? This misspecification is a likely scenario, especially when the origins of the constraints have nothing to do with the assumptions on $P$, as is the case in the examples discussed in the next subsection.

Throughout the paper, we limit our analysis to the class of classification-calibrated loss functions defined in Bartlett_et_al_2006.

Noting that the surrogate risk can be expressed as

the definition of classification-calibrated loss functions implies that at every $x \in \mathcal{X}$ with $\eta(x)\neq 1/2$, every $f(x)$ that minimizes $C_{\phi}(f(x), \eta(x))$ has the same sign as the Bayes classifier, $\mathrm{sign}(2\eta(x)-1))$. Bartlett_et_al_2006 shows that many commonly used surrogate loss functions including those listed in Table (ref) are classification-calibrated.\footnote{Bartlett_et_al_2006 also show that any convex loss function $\phi$ is classification-calibrated if and only if it is differentiable at $0$ and $\phi^{\prime}(0)<0$.}

Having introduced two notions of misspecification, we now clarify the relationship between $R$-misspecification and $R_\phi$-misspecification.

Proposition (ref) (i), which rephrases Claim 3 of Theorem 1 in Bartlett_et_al_2006, implies that surrogate risk minimization on the $R_\phi$-correctly specified class $\mathcal{F}$ leads to (first-best) optimal classification in terms of the classification risk. An equivalent statement following Theorem 1 in Bartlett_et_al_2006 is that for any $P$ and every sequence of measurable functions $\{ f_{i}:\mathcal{X} \rightarrow \mathbb{R}\}$,

This result justifies the approach of surrogate risk minimization when $\mathcal{F}$ is a sufficiently rich class of classifiers (e.g., the reproducing kernel Hilbert space of functions with a large number of features as used in support vector machines), since $R_{\phi}$-correct specification, which is a credible assumption to make given a rich class of classifiers, guarantees $R$-correct specification.

Proposition (ref) (ii), in contrast, shows that $R$-correct specification of $\mathcal{F}$ does not guarantee $R_{\phi}$-correct specification.\footnote{ Given a convex classification-calibrated loss function $\phi$, our proof of Proposition (ref) (ii) in Appendix (ref) constructs a pair comprising a $R$-correctly specified class of classifiers $\mathcal{F}$ and a distribution $P$ that leads to $R_{\phi}$-misspecification. In the construction, we assume that $x_1 \neq x_2 \in \mathcal{X}$ supported by $P_X$ on which $\phi(f(x_1))<\phi(-f(x_2)))$ holds for all $f \in \mathcal{F}$ and that $f(x_1)<0 \leq f(x_2)$ holds for some $f \in \mathcal{F}$, and consider $P$ that specifies a value of $\eta(x_2)$ close to 1, and a value of $\eta(x_1)$ slightly below $1/2$. Such a construction of $P$ is not pathological or limited to the specific class of classifiers considered in the proof.} $R_{\phi}$-misspecification of $\mathcal{F}$ can lead to the selection of a suboptimal classifier in $\mathcal{F}$ in terms of the classification risk, which illustrates the pitfall of adopting a surrogate loss approach with constrained classifiers. Even when we are confident that the constrained class $\mathcal{F}$ is $R$-correctly specified, we cannot justify the use of $\mathcal{F}$ in the surrogate risk minimization.

$\mathcal{G}$-constrained classification

In this section, we consider restricting the class of classifiers by requiring that their prediction sets belong to a prespecified class of sets, $\mathcal{G}\subset2^{\mathcal{X}}$. See Examples (ref)--(ref) below for motivating examples.

We denote by

the class of classifiers whose prediction sets are constrained to $\mathcal{G}$. In this definition, we restrict $f$ to be bounded and, without loss of generality, normalize its range to $[-1,1]$. Other than on the shape of the 0-level set and on the range, $\mathcal{F}_{\mathcal{G}}$ does not impose any constraint on the functional form of $f \in \mathcal{F}_{\mathcal{G}}$. The goal of the constrained classification problem is then to find a best classifier, in the sense that it minimizes the classification risk $R\left(\cdot \right)$ over $\mathcal{F}_{\mathcal{G}}$. We refer to $\mathcal{F}_{\mathcal{G}}$ as the $\mathcal{G}$-constrained class of classifiers and to the classification problem over $\mathcal{F}_\mathcal{G}$ as $\mathcal{G}$-constrained classification.

The specification of the class of prediction sets $\mathcal{G}$ represents the fairness, interpretability, and other exogenous requirements that are desired for classification rules. Some examples follow.

In the $\mathcal{G}$-constrained classification problem, $R$-correct specification of $\mathcal{F}_{\mathcal{G}}$ is necessary and sufficient for the surrogate risk minimizer $f_{\phi}^{*}$ to achieve the first-best minimum risk.

Proposition (ref) shows that if $\phi$ is classification-calibrated, $f_{\phi}^{\ast} \in \mathcal{F}_{\mathcal{G}}$ that minimizes the surrogate risk over $\mathcal{F}_{\mathcal{G}}$ leads to a globally optimal classifier in terms of the classification risk if and only if $\mathcal{F}_{\mathcal{G}}$ is $R$-correctly specified. A comparison of Proposition (ref) (ii) and Proposition (ref) clarifies a special feature of the $\mathcal{G}$-constrained class of classifiers. Specifically, Proposition (ref) (ii) establishes that, in general, $R$-correct specification of a constrained class of classifiers $\mathcal{F}$ does not guarantee $R(f^{\ast}_{\phi}) = R(f^{\ast}_{Bayes})$. In contrast to the seminal results about surrogate risk consistency shown in Zhang_2004 and Bartlett_et_al_2006, our claim does not require $R_\phi$-correct specification of $\mathcal{F}_\mathcal{G}$.

If constraints defining $\mathcal{G}$ are motivated by some considerations that are independent of any belief on the underlying data generating process (e.g., Examples (ref)--(ref) above), $R$-correct specification of $\mathcal{F}_{\mathcal{G}}$ is hard to justify. Therefore, an important question for our analysis to consider is whether or not surrogate risk minimization procedures can yield a classifier achieving $\inf_{f \in \mathcal{F}_{\mathcal{G}}} R(f)$ without requiring $R$-correct specification of $\mathcal{F}_{\mathcal{G}}$.

Calibration of $\mathcal{G}$-constrained classification

This section investigates the risk consistency of a surrogate risk minimization approach over $\mathcal{F}_{\mathcal{G}}$, where $\mathcal{F}_{\mathcal{G}}$ is now allowed to be $R$-misspecified. Let $f^{\ast}$ be an optimal classifier that minimizes the classification risk over $\mathcal{F}_{\mathcal{G}}$:

Similarly, we denote a best classifier among $\mathcal{F}_{\mathcal{G}}$ in terms of the surrogate risk by $f_{\phi}^{\ast}$,

To begin our analysis, let us first perform a simple numerical example to assess the influence of misspecification in constrained classification.

This example illustrates that hinge loss is robust to $R$-misspecification of $\mathcal{F}_{\mathcal{G}}$, but exponential and truncated quadratic losses are not. To what extent, can we generalize this finding? What conditions do we need to guarantee that surrogate risk minimizing classifiers are consistent to the second-best (constrained optimal) classification rule in terms of the classification risk? We answer these questions below.

For any classifier $f$, we define the $\mathcal{G}$-constrained excess risk of $f$ as

which is the regret of $f$ relative to a constrained optimum $f^{*}$ in terms of the classification risk. Similarly, we define the $\mathcal{G}$-constrained excess $\phi$-risk of $f$ as

Fix $G\in\mathcal{G}$ and let

be the class of classifiers that share the prediction set $G$. Then $\{\mathcal{F}_{G}:G\in\mathcal{G}\}$ forms a partition of $\mathcal{F}_{\mathcal{G}}$ indexed by the prediction set, and satisfies $\mathcal{F}_{\mathcal{G}}=\cup_{G\in\mathcal{G}}\mathcal{F}_{G}$ and $\mathcal{F}_{G}\cap\mathcal{F}_{G'}=\emptyset$ for $G,G'\in\mathcal{G}$ with $G\neq G'$. With this definition to hand, choosing a classifier from $\mathcal{F}_{\mathcal{G}}$ can be decomposed into two steps: choosing a prediction set $G$ from $\mathcal{G}$ and, then, choosing a classifier $f$ from $\mathcal{F}_{G}$.

Denote the classification risk evaluated at a prediction set $G$ by $\mathcal{R}(G)\equiv\inf_{f\in\mathcal{F}_{G}}R(f)$. Note that any $f\in\mathcal{F}_{G}$ attains the same level of classification risk, so $\mathcal{R}(G)=R(f)$ holds for all $f\in\mathcal{F}_{G}$. $\mathcal{R}(G)$ can be written as

Similarly, we define the surrogate risk evaluated at $G$ by $\mathcal{R}_{\phi}(G)\equiv\inf_{f\in\mathcal{F}_{G}}R_{\phi}(f)$, which can be written as

where the second line follows from the fact that $f \in \mathcal{F}_{G}$ is unconstrained other than via its prediction set and that the minimization over $f\in\mathcal{F}_{G}$ can be performed pointwise at each $x$. For $f\in\mathcal{F}_{G}$ with $x\in G$, $f(x)$ is constrained to $[0,1]$, and with $x\in G^{c}$, $f(x)$ is constrained to $[-1,0)$. To simplify the notation, we define

where $C_{\phi}^{+}(\eta(x))$ and $C_{\phi}^{-}(\eta(x))$ are the minimized surrogate risks conditional on $X=x$ under the constraints $f(x)\in[0,1]$ and $f(x)\in[-1,0)$, respectively. Using these definitions, the surrogate risk at $G$ can be written as

By comparing the expressions of the risks in ((ref)) and ((ref)), we obtain the first main theorem that clarifies the condition for the surrogate risk $\mathcal{R}_{\phi}(G)$ to calibrate the global ordering of the classification risk $\mathcal{R}(G)$ over $G\in\mathcal{G}$.

Theorem (ref) does not exploit the condition that $\phi$ is classification-calibrated, but if a surrogate loss function satisfies condition ((ref)), it is automatically classification-calibrated. Another remark follows.

The well known inequality by Zhang_2004 relates the excess surrogate risk to the excess classification risk under $R$-correct specification. As a corollary of Theorem (ref), if we set $\phi = \phi_h$, we can generalize Zhang's inequality by allowing $R$-misspecification of the classifiers. To formally state this generalization, we let $G^{\ast}\in\arg\inf_{G\in\mathcal{G}}\mathcal{R}(G)$, and set $G'=G^{\ast}$ in Theorem (ref). Let $f\in\mathcal{F}_{\mathcal{G}}$ be arbitrary and $G_{f} = \{ x \in \mathcal{X}: f(x) \geq 0 \}\in\mathcal{G}$. The alignment of the risk ordering between the classification and hinge risks implies that the minimizers of $\mathcal{R}(\cdot)$ also minimize $\mathcal{R}_{\phi_h}(\cdot)$, i.e., $\inf_{f\in\mathcal{F}_{\mathcal{G}}}R_{\phi_h}(f)=\inf_{G\in\mathcal{G}}\mathcal{R}_{\phi_h}(G)=\mathcal{R}_{\phi_h}(G^{\ast})$. Theorem (ref) therefore implies that the $\mathcal{G}$-constrained excess classification risk of $f$ satisfies the following inequality:

where the second equality follows by equation ((ref)); and the third equality follows by equation ((ref)) and $\Delta C_{\phi_h}(\eta)=c(1-2\eta)$. That is, when $\phi = \phi_h$, Zhang's inequality holds without requiring the $R$-correct specification of the classifiers.

Corollary (ref) shows that if the surrogate loss $\phi$ satisfies condition ((ref)), then the classifier $f_{\phi}^{\ast}$ that minimizes the surrogate risk over $\mathcal{F}_{\mathcal{G}}$ also minimizes the classification risk over $\mathcal{F}_{\mathcal{G}}$. Importantly, this result holds without assuming the $R$-correct specification of $\mathcal{F}_{\mathcal{G}}$. It justifies the use of hinge loss in the constrained classification problem irrespective of whether or not $\mathcal{F}_{\mathcal{G}}$ is correctly $R$-specified. Note, however, that the result relies on the fact that at every $x \in \mathcal{X}$ we can choose any $f(x) \in [-1,1]$ as long as the prediction set constraint $G_{f} \in \mathcal{G}$ is satisfied. We relax this requirement in the next section.

Further analysis can show that the condition ((ref)) in Theorem (ref) is not only sufficient but also necessary. To formally show this, we adopt the concept of universal equivalence of loss functions introduced by Nguyen_et_al_2009 to the current setting.

Universally equivalent loss functions $\phi_{1}$ and $\phi_{2}$ lead to the same risk ordering over $\mathcal{G}$. Hence, if a loss function $\phi$ is universally equivalent to the 0-1 loss, the $\phi$-risk shares the same risk ordering with the classification risk.

The following theorem establishes a necessary and sufficient condition for two classification-calibrated loss functions to be universally equivalent.

The `if' part of the theorem is a generalization of Theorem (ref) in that it does not assume that either of $\phi_1$ or $\phi_2$ is the 0-1 loss function.

When we set $\phi_{2}$ to the 0-1 loss function, Theorem (ref) yields the class of loss functions that are universally equivalent to the 0-1 loss functions. This class exactly coincides with the class of loss functions that satisfy the condition ((ref)) in Theorem (ref). Hence, the following corollary holds.

In the following sections, without loss of generality, we maintain the assumption that $c=1$ in the definition of the hinge loss function where it is convenient to do so. We conclude this section with a remark to compare our constrained classification framework to that of Nguyen_et_al_2009.

Consistency of hinge risk classification with functional form constraints

The previous section considers $\mathcal{F}_{\mathcal{G}}$, the class of all functions whose prediction sets are in $\mathcal{G}$. The generalized Zhang's inequality shown in Corollary (ref) heavily relies on the richness of $\mathcal{F}_{\mathcal{G}}$. This richness, however, limits the computational attractiveness of a surrogate-loss approach, since convexity in optimization of an empirical analogue of the surrogate risk does not directly follow from $\mathcal{F}_{\mathcal{G}}$, and typically requires additional functional form restrictions for $f$.

Unfortunately, once a functional form restriction on $f$ is imposed on top of the prediction set constraint $G_f \in \mathcal{G}$, the global calibration property of the hinge risk shown in Theorem (ref) breaks down. The following example illustrates this phenomenon.

This example illustrates that even with hinge loss, consistency to the second best classifier becomes a fragile property once the functional form of $f$ is constrained in addition to the prediction set constraint $G_{f}\in\mathcal{G}$. Consequently, it is natural to ask what additional functional form restriction we can safely introduce to $\mathcal{F}_{\mathcal{G}}$ without threatening consistency, i.e., for which subclass $\widetilde{\mathcal{F}}_{\mathcal{G}} \subset \mathcal{F}_{\mathcal{G}}$ does minimizing the hinge risk $R_{\phi_h}(f)$ over $f \in \widetilde{\mathcal{F}}_{\mathcal{G}}$ lead to a classifier that minimizes the classification risk $R(f)$ over $f \in \mathcal{F}_{\mathcal{G}}$?

Formally, we introduce the following definition of classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$.

To start with the heuristic, consider a simple case where $\widetilde{\mathcal{F}}_{\mathcal{G}}$ consists of piecewise constant functions with at most $J$ jumps, $J \geq 1$, of the following form:

By construction, any function in $\widetilde{\mathcal{F}}_{\mathcal{G},J}$ is a step function bounded in $[-1, 1]$ and its sublevel sets $\{x\in\mathcal{X}:f(x) \leq t\}$ belong to $\mathcal{G}$ for any $t\in[-1,1]$.

Let

be the collection of best prediction sets in $\mathcal{G}$, and

be the optimal classification risk. For any $G \in \mathcal{G}$, we define $\tilde{f}_{G}(x) \equiv 2\cdot 1\{x \in G\}-1$, a step function over $\mathcal{X}$ that indicates $x \in G^{\ast}$ and $x \notin G^{\ast}$ with values $+1$ and $-1$, respectively. The following lemma shows that $\widetilde{\mathcal{F}}_{\mathcal{G},J}$ is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$.

Characteristic features of $\widetilde{\mathcal{F}}_{\mathcal{G},J}$ are (i) sublevel sets of any $f \in \widetilde{\mathcal{F}}_{\mathcal{G},J}$ are in $\mathcal{G}$, and (ii) $\widetilde{\mathcal{F}}_{\mathcal{G},J}$ contains $\tilde{f}_{G}$ for any $G \in \mathcal{G}$. It transpires that these two features are the key features that need to be maintained for $\widetilde{\mathcal{F}}_{\mathcal{G}}$ to generalize Lemma (ref).

The next theorem is the second main theorem of the paper that extends Lemma (ref) to a more general class of classifiers that can accommodate continuous ones.

The theorem establishes that the two conditions (ref) and (ref) are sufficient for $\widetilde{\mathcal{F}}_{\mathcal{G}}$ to be a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$. This result holds regardless of whether $\mathcal{F}_{\mathcal{G}}$ is correctly $R$-specified or not. Examples (ref) and (ref) at the end of this section give examples of classification-preserving reductions for linear classification and monotone classification.

The conditions (ref) and (ref) in Theorem (ref) are simple to interpret and guarantee the consistency of the hinge risk minimization, but they do not imply that the empirical hinge risk minimization over $\widetilde{\mathcal{F}}_{\mathcal{G}}$ can be reduced to a convex optimization. We are unaware of a general way to construct a classification-preserving reduction that makes the empirical hinge risk minimization a convex program. For monotone classification, analyzed in Section (ref), we propose two constructions of $\widetilde{\mathcal{F}}_{\mathcal{G}_M}$, one of which is exactly a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}_M}$ while the other is approximately classification-preserving. We show that for both cases, minimization of the empirical hinge risk is a linear programming problem.

Although Theorem (ref) shows the consistency of the hinge risk minimization over $\widetilde{\mathcal{F}}_{\mathcal{G}}$, it does not lead to the generalized Zhang_2004's (Zhang_2004) inequality in Corollary (ref). Instead, the following corollary gives proportional equality between the $\mathcal{G}$-constrained excess classification risk and the $\mathcal{F}_{\mathcal{G}}$-constrained excess hinge risk with an extra term added.

The extra term (the right-most term) in ((ref)) measures the difference in the hinge risks between a classifier $f$ and the step function indicating the prediction set of $f$ by the values $+1$ or $-1$. Due to the fact that some of the best classifiers are of the form $\tilde{f}^{\ast}(\cdot)=1\left\{\cdot \in G^\ast \right\} - 1\left\{\cdot \notin G^\ast \right\}$ for $G^{\ast} \in \mathcal{G}^{\ast}$ (Theorem (ref) (ii)), if $f$ closely approximates such a classifier, the extra term is close to zero. In the following section, we use equation ((ref)) to derive the statistical properties of the hinge risk minimization in terms of the $\mathcal{G}$-constrained excess classification risk. Equation ((ref)) implies that the $\mathcal{G}$-constrained excess classification risk is bounded from above by the average of the two $\mathcal{F}_{\mathcal{G}}$-constrained excess hinge risks. One is over $\widetilde{\mathcal{F}}_\mathcal{G}$ and the other is over $\mathcal{F}_{\mathcal{G}}$. We are unable to determine if the excess hinge risk over $\mathcal{F}_{\mathcal{G}}$ can be bounded from above by a term that is proportional to the excess hinge risk over $\widetilde{\mathcal{F}}_\mathcal{G}$. As such, the constrained-classification-preserving reduction $\widetilde{\mathcal{F}}_{\mathcal{G}}$ cannot replace $\mathcal{F}_{\mathcal{G}}$ in Zhang's inequality, shown in Corollary (ref).

We conclude this section by presenting examples of classes of classifiers that approximately or exactly satisfy the conditions for classification-preserving reduction.

Statistical properties

The analyses presented so far concern the consistency of a surrogate loss approach in terms of the population risk criterion. It is important to note that Theorems (ref) and (ref) do not impose any restriction on the underlying distribution of $(Y,X)$. Accordingly, equivalence of the risk orderings and risk minimizing classifiers between the classification and hinge risks remains valid even if we consider empirical analogues of the risks constructed from the empirical distribution of the sample. Theorems (ref) and (ref) hence guarantee that a classifier minimizing the empirical hinge risk over $\mathcal{F}_{\mathcal{G}}$ or over a classification-preserving reduction $\widetilde{\mathcal{F}}_{\mathcal{G}}$ also minimizes the empirical classification risk.

In this section, we assess the generalization performance of hinge risk minimizing classifiers, allowing for general misspecification of the constrained class of classifiers. Towards that goal, let $\mathcal{G}$ be fixed and consider $\Check{\mathcal{F}}$, a class of classifiers whose members satisfy $-1 \leq f \leq 1$. $\Check{\mathcal{F}}$ may or may not be a subclass of $\mathcal{F}_{\mathcal{G}}$, while in our analysis of monotone classification below, $\Check{\mathcal{F}}$ corresponds to an approximation of a classification-preserving reduction $\widetilde{\mathcal{F}}_{\mathcal{G}}$. Let $\{\left(Y_{i},X_{i}\right):i=1,\ldots,n\}$ be a sample of observations that are independent and identically distributed (i.i.d.) as $(Y,X)$. We denote the joint distribution of a sample of $n$ observations by $P^{n}$ and the expectation with respect to $P^{n}$ by $E_{P^{n}}[\cdot]$. We define the empirical classification risk and empirical hinge risk, respectively, as

where the max operator in the hinge loss is redundant if we constrain $f(\cdot)$ to $[-1, 1]$. Let $\hat{f}$ be a classifier that minimizes $\hat{R}_{\phi_{h}}(\cdot)$ over $\Check{\mathcal{F}}$. We evaluate the statistical properties of $\hat{f}$ in terms of the excess classification risk relative to the minimal risk over $\mathcal{F}_{\mathcal{G}}$, $R(\hat{f})-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f)$. In particular, we later derive a distribution-free upper bound on the mean of the excess classification risk.

Let $\widetilde{\mathcal{F}}_\mathcal{G}$ be a subclass of $\mathcal{F}_{\mathcal{G}}$ that satisfies conditions (ref) and (ref) in Theorem (ref). $\widetilde{\mathcal{F}}_\mathcal{G}$ is a classification-preserving reduction of $\mathcal{F}_\mathcal{G}$ (Definition (ref)). Following Corollary (ref), we have

When $\Check{\mathcal{F}}=\widetilde{\mathcal{F}}_\mathcal{G}$, evaluating each term on the right hand side of ((ref)) gives an upper bound on the mean of the $\mathcal{G}$-constrained excess classification risk of $\hat{f}$.

Let $H_{1}^{B}\left(\epsilon,\mathcal{F},P_{X}\right)$ be the $L_{1}\left(P_X\right)$-bracketing entropy of a class of functions ${\mathcal{F}}$ and $H_{1}^{B}\left(\epsilon,\mathcal{G},P_{X}\right)$ be that of a class of prediction sets $\mathcal{G}$.\footnote{With a slight abuse of notation, we denote by $H_{1}^{B}\left(\epsilon,\mathcal{G},P_{X}\right)$ the bracketing entropy number of the class of indicator functions, $H_{1}^{B}\left(\epsilon,\mathcal{H}_\mathcal{G},P_{X}\right)$, where $\mathcal{H}_{\mathcal{G}}\equiv \{1\{\cdot \in G\}: G \in \mathcal{G}\}$.} For definitions of these two terms, see Definition (ref) in Appendix (ref). When $\Check{\mathcal{F}}$ coincides with $\widetilde{\mathcal{F}}_\mathcal{G}$, the following theorem gives a non-asymptotic distribution-free upper bound on the mean of the $\mathcal{G}$-constrained excess classification risk in terms of the bracketing entropy.

The upper bound on the mean of the $\mathcal{G}$-constrained excess classification risk converges to zero at the rate of $\tau_n$, which depends on $r$ in the bracketing entropy conditions ((ref)) and ((ref)). Dudley1999 shows many examples that satisfy these bracketing entropy conditions. In particular, the class $\mathcal{G}_\precsim \subseteq 2^{\mathcal{X}}$ that is compatible with monotone classification and introduced in Example (ref) satisfies condition ((ref)) with $r$ equal to $d_x-1$ (see Theorem 8.3.2 in Dudley1999).

We next consider the case when $\Check{\mathcal{F}}$ does not coincide with $\widetilde{\mathcal{F}}_{\mathcal{G}}$. This case corresponds to a scenario where minimizing the empirical hinge risk over $\widetilde{\mathcal{F}}_{\mathcal{G}}$ is difficult but minimizing over $\Check{\mathcal{F}}$, a class approximating $\widetilde{\mathcal{F}}_{\mathcal{G}}$, is feasible.

A further decomposition of $R_{\phi_h}(\hat{f})-\inf_{f\in\widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi_h}(f)$ in ((ref)) leads to

Hence the $\mathcal{G}$-constrained excess classification risk is decomposed into three terms. We call the first term estimation error, the second term approximation error to a best classifier, and the third term approximation error to a step classifier. Evaluating each error gives an upper bound on the $\mathcal{G}$-constrained excess classification risk.

The following theorem evaluates the estimation error in terms of bracketing entropy.

Applications to monotone classification

This section applies the general theoretical results shown in Sections (ref)--(ref) to the monotone classification problem (Example (ref)). By Theorem (ref), we limit our analysis to hinge loss. We assume that $\mathcal{X}$ is compact in $\mathbb{R}^{d_x}$, $d_x < \infty$, and without loss of generality, we represent $\mathcal{X}$ as the $d_x$-dimensional unit hypercube (i.e., $\mathcal{X}=\left[0,1\right]^{d_x}$). To be specific, we consider the class of monotone prediction sets $\mathcal{G}_{M}$ such that, for any $G\in\mathcal{G}_{M}$ and $x,\tilde{x}\in\mathcal{X}$, $x\in G$ and $x\leq\tilde{x}$ implies $\tilde{x}\in G$ holds\footnote{We define the partial order $\leq$ on $\mathcal{X}$ as follows. For any $x=\left(x_{1},\ldots,x_{d}\right)^{T}$ and $\tilde{x}=\left(\tilde{x}_{1},\ldots,\tilde{x}_{d}\right)^{T}$, we say $x\leq\tilde{x}$ if $x_{j}\leq\tilde{x}_{j}$ for every $j=1,\ldots,d$. We further say $x<\tilde{x}$ if $x\leq\tilde{x}$ holds and for some $j\in\left\{ 1,\ldots,d\right\} $, $x_{j}<\tilde{x}_{j}$ holds.} (i.e., $\mathcal{G}_{M}$ respects the partial order $\leq$ on $\mathcal{X}$). Accordingly, the class of monotonically increasing classifiers can be represented as

In this section, we first study the monotone classification problem on $\mathcal{F}_M$. Note that $\mathcal{F}_M$ is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}_M}$ (see Example (ref)). As an alternative to $\mathcal{F}_{M}$, we next consider using a sieve of Bernstein polynomials to approximate a hinge risk minimizing classifier on $\mathcal{F}_{M}$. The Bernstein polynomial is known for its capability to accommodate bound constraints and various shape constraints on functions (e.g., monotonicity or convexity). The class of Bernstein polynomials becomes a classification-preserving reduction only at the limit with a growing order of polynomials.

Nonparametric monotone classification

We first consider hinge risk minimization given the class of monotonically increasing classifiers $\mathcal{F}_{M}$. Let $\hat{f}_{M}$ be a minimizer of $\hat{R}_{\phi_h}(\cdot)$ over $\mathcal{F}_{M}$. Since the hinge risk for classifiers constrained to $-1 \leq f(x) \leq 1$ gives the linear loss $\phi_h(yf(x)) = 1-yf(x)$, minimization of the empirical hinge risk can be formulated as the following linear programming:

where the first inequality constraints correspond to the monotononicity constraint on $\mathcal{F}_M$, and the second inequality constraints correspond to the range constraint for $f \in \mathcal{F}_M$. Solving this linear program yields the values of $\hat{f}_{M}$ at the values of $x$ observed in the training sample. Let $\left(\hat{f}_{M}\left(X_{1}\right),\ldots,\hat{f}_{M}\left(X_{n}\right)\right)$ be the solution of ((ref)). Then any function in $\mathcal{F}_{M}$ that passes the points $\left(\left(X_{1},\hat{f}_{M}\left(X_{1}\right)\right),\ldots,\left(X_{n},\hat{f}_{M}\left(X_{n}\right)\right)\right)$ minimizes the empirical hinge risk over $\mathcal{F}_M$.\footnote{All classifiers obtained from this procedure predict a unique label at each point $x$ observed in the training sample, whereas they may not give a unique prediction at a point $x$ not observed in the training sample. One possible way to predict a label at an unobserved point $x$ without violating the monotonicity constraint is to predict its label by the largest label among those predicted by all classifiers in $\arg\inf_{f \in \mathcal{F}_M}\hat{R}_{\phi_h}(f)$. Let $\widetilde{\mathcal{X}}$ be a set of $x$ observed in the training sample. Given any $\hat{f}_M \in \arg\inf_{f \in \mathcal{F}_M}\hat{R}_{\phi_h}(f)$, this way of predicting a label is equivalent to predicting the label of $x \in \mathcal{X} \backslash \widetilde{\mathcal{X}}$ as the sign of $\min\{\hat{f}_{M}(\tilde{x}):\tilde{x}\in \widetilde{\mathcal{X}}, \tilde{x} \geq x\}$ if there exists $\tilde{x}\in \widetilde{\mathcal{X}}$ such that $\tilde{x} \geq x$, and as 1 otherwise.} Since $\mathcal{F}_{M}$ is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}_M}$, Theorem (ref) with $P$ replaced by $P^n$ shows that any solution to ((ref)) exactly minimizes $\hat{R}_{\phi_h}(\cdot)$ over $\mathcal{F}_{\mathcal{G}_M}$.

We investigate the statistical properties of this procedure. Since $\mathcal{F}_M$ is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}_M}$, we can apply Theorem (ref). Towards this goal, we first characterize an upper bound on the bracketing entropy number of the class of monotone prediction sets $\mathcal{G}_M$. The next lemma, which we borrow from Theorem 8.3.2 in Dudley1999, gives an upper bound on the $L_{1}\left(P_X\right)$-bracketing entropy of $\mathcal{G}_{M}$. Here, we assume that $X$ is continuously distributed with bounded density.

With this lemma to hand, setting $r= 1 - d_x$ in Theorem (ref) yields a finite sample uniform upper bound on the $\mathcal{G}_M$-constrained excess classification risk of $\hat{f}_{M}$. The following theorem shows that the excess risk of $\hat{f}_M$ obtained from the linear program in ((ref)) attains the same convergence rate as the welfare regret of monotone treatment rules shown by MT17.

This theorem guarantees the consistency of monotone classification using hinge loss and the class of monotone classifiers $\mathcal{F}_{M}$. The rate of convergence corresponds to $\tau_n$.

Monotone classification with Bernstein polynomials

To illustrate our theoretical results for monotone classification, the second approach we consider is to use multivariate Bernstein polynomials to approximate a best classifier in $\mathcal{F}_{M}$. Let $b_{kj}(x)=\left(

\right)x^{j}\left(1-x\right)^{k-j}$ be the Bernstein basis. The Bernstein polynomial for a $d_x$-dimensional function takes the following form:

where $\mathbf{k}=\left(k_{1},\ldots,k_{d_x}\right)^{T}$ is a vector collecting the orders of the Bernstein polynomial bases specified by the analyst, $\theta\equiv \left\{ \theta_{j_{1}\ldots j_{d_x}}\right\} _{j_{1}=0,\ldots,k_{1};\cdots;j_{d_x}=0,\ldots,k_{d_x}}$ is a $(k_{1}+1)\times\cdots\times(k_{d_x}+1)$-dimensional vector of the parameters to be estimated, and $x_j$ denotes the $j$-th element of the $d_x$-dimensional vector $x$. If $-1\leq\theta_{j_{1}\ldots j_{d_x}}\leq1$ for all $\left(j_{1},\ldots,j_{d_x}\right)$, the range of the function $B_{\mathbf{k}}\left(\theta,\cdot\right)$ is bounded in $\left[-1,1\right]$. Moreover, if $\theta_{j_{1}\ldots j_{d_x}}\geq\theta_{\tilde{j}_{1}\ldots\tilde{j}_{d_x}}$ for all $\left(j_{1},\ldots,j_{d_x}\right)\geq\left(\tilde{j}_{1},\ldots,\tilde{j}_{d_x}\right)$, $B_{\mathbf{k}}\left(\theta,\cdot\right)$ is non-decreasing in $x$.\footnote{See, e.g., Wang_Ghosh_2012 for the bound and shape preserving properties of the multivariate Bernstein polynomials.} Hence, to preserve the bound and non-decreasing constraints on $\mathcal{F}_M$, we constrain the class of Bernstein polynomials to

where $\widetilde{\Theta}$ is the set of $\theta$ such that $\theta_{j_{1}\ldots j_{d_x}}\in\left[-1,1\right]$ for all $\left(j_{1},\ldots,j_{d_x}\right)$ and $\theta_{j_{1}\ldots j_{d_x}}\geq\theta_{\tilde{j}_{1}\ldots\tilde{j}_{d_x}}$ for all $\left(j_{1},\ldots,j_{d_x}\right)\geq\left(\tilde{j}_{1},\ldots,\tilde{j}_{d_x}\right)$. An appropriate choice of $\mathbf{k}$ is discussed later.

Noting that some hinge risk minimizing classifiers on $\mathcal{F}_M$ have the form of step functions taking only the values $-1$ and $1$ (Theorem (ref)), we propose approximating such a step function using the sieve of Bernstein polynomials. To this end, we propose the following two steps:

Our proposal is to use $\hat{f}_{B}^{\dagger}$ rather than $\hat{f}_B$. Lemma (ref) in Appendix (ref) shows that $\hat{f}_{B}^{\dagger}$ also minimizes $R_{\phi_h}(f)$ over $f \in \mathcal{B}_{\mathbf{k}}$. With respect to the first step, since the hinge loss of a classifier $f$ constrained on $[-1,1]$ has the linear form $\phi_h(yf(x))=1-yf(x)$, any function in $\mathcal{B}_{\mathbf{k}}$ is linear in the parameters $\theta$, and the parameter space $\widetilde{\Theta}$ is a polyhedron, minimization of $\hat{R}_{\phi_h}(\cdot)$ over $\mathcal{B}_{\mathbf{k}}$ can be formulated as the following linear program:

where $X_{ij}$ denotes the $j$-th element of $X_i$.\footnote{The linear program in ((ref)) for the nonparametric monotone classification problem has $n$-decision variables, whereas the linear program in ((ref)) has $(k_1+1)\times \cdots \times (k_{d_x}+1)$-decision variables. Hence when the dimension of $X$ is small to moderate relative to the sample size $n$, the linear programming for the Bernstein polynomials would be easier to compute. The reverse is also true.} The first inequality constraints restrict the feasible classifiers to a class of non-decreasing functions. The second inequality constraints bound the feasible classifiers to $[-1,1]$.

We then consider applying the general result for the excess risk bound in Theorem (ref) with $\Check{F} = \mathcal{B}_{\mathbf{k}}$. Lemma (ref) in Appendix (ref) gives finite upper bounds on two approximation errors:

in ((ref)) upon setting $(\Check{\mathcal{F}},\widetilde{\mathcal{F}},\hat{f})=(\mathcal{B}_{\mathbf{k}},\mathcal{F}_M,\hat{f}_{B}^{\dagger})$. The binarized coefficients in $\hat{f}_{B}^\dagger$ help us to make the second approximation error shrink to zero. Moreover, Lemma (ref) in Appendix (ref) gives a finite upper bound on the bracketing entropy of $\mathcal{B}_{\mathbf{k}}$. Combining these results, the following theorem gives a finite sample upper bound on the mean of the $\mathcal{G}_M$-constrained excess classification risk of $\hat{f}_B^{\dagger}$.

The upper bound in ((ref)) converges to zero as the sample size $n$ and the order of the Bernstein polynomials $k_j$ ($j=1,\ldots,d_x$) increase. Note that the rate of convergence for the estimation error in this theorem, $\tilde{\tau}_n$, is slower than that in Theorem (ref), $\tau_n$. The difference in the rates of convergence is due to the different orders of the upper bounds on $H_{1}^{B}(\epsilon,\mathcal{G}_M,P_X)$ and $H_{1}^{B}(\epsilon,\mathcal{F}_M,P_X)$ in Lemmas (ref) and (ref). To achieve the convergence rate of $\tilde{\tau}_n$ for the mean of the excess risk of $\hat{f}_{B}^{\dagger}$, Theorem (ref) suggests the tuning parameters $k_{j}$, for $j=1,\ldots,d_x$, should be set sufficiently large so that $\sqrt{\log k_{j}/k_{j}}=O\left(\tilde{\tau}_n\right)$.

In practice, one may want to select the complexity of the Bernstein polynomials by minimizing penalized empirical surrogate risk. The classification and treatment choice literature (Koltchinskii_2006, MT17, and references therein) analyze the regret properties and oracle inequalities for penalized risk minimizing classifiers. We leave theoretical investigation of the applicability of penalization methods to the current hinge risk minimization using Bernstein polynomials for future research.

Extension to individualized treatment rules

This section extends the primary results obtained in Sections (ref) and (ref) for binary classification to the weighted classification introduced in Section (ref), and to causal policy learning. Extensions of the results in Sections (ref) and (ref) to weighted classification are presented in Appendix (ref). We use the same notation and definitions as those introduced in Section (ref). We term $R^{\omega}$ and $R_{\phi}^{\omega}$, defined in ((ref)) and ((ref)), weighted classification risk and weighted $\phi$-risk, respectively. Throughout this section, with some abuse of notation, we denote by $P$ a distribution on $\mathbb{R}_{+} \times \{-1,1\} \times \mathcal{X}$ and suppose that $(\omega,Y,D) \sim P$.

Consistency of weighted classification with hinge loss

We first show consistency of weighted classification with hinge risk by adapting the analyses in Sections (ref) and (ref). Given a prespecified $\mathcal{G}$, let $\mathcal{F}_\mathcal{G}$ be as in Section (ref). Analogous to $\mathcal{R}(G)$ and $\mathcal{R}_\phi(G)$, we define $\mathcal{R}^{\omega}(G) \equiv \inf_{f \in \mathcal{F}_G}R^{\omega}(f)$, the weighted-classification risk evaluated at $G$, and $\mathcal{R}_{\phi}^{\omega}(G) \equiv \inf_{f \in \mathcal{F}_G}R_{\phi}^{\omega}(f)$, the weighted $\phi$-risk evaluated at $G$. Note that $\mathcal{R}^{\omega}(G) = R^{\omega}(f)$ for all $f \in \mathcal{F}_G$. Let $\mathcal{R}^{w\ast} \equiv \inf_{G\in \mathcal{G}}\mathcal{R}^{\omega}(G) = \inf_{f \in \mathcal{F}_{\mathcal{G}}}R^{\omega}(f)$ be the optimal weighted risk, and $\mathcal{G}^{\ast} \equiv \arg\inf_{G\in \mathcal{G}}\mathcal{R}^{\omega}(G)$ be the collection of best prediction sets.

For the non-negative weight variable $\omega$, we define

Let $C_{\phi}\left(a,b,c,d\right)\equiv a\phi\left(c\right)d+b\phi\left(-c\right)\left(1-d\right)$, and

which are analogous to $C_{\phi}^{+}$, $C_{\phi}^{-}$ and $\Delta C_{\phi}$ defined in Section (ref).

The next theorem generalizes Theorems (ref), (ref), and Corollary (ref) to weighted classification, giving a necessary and sufficient condition for equivalence of the risk ordering among surrogate loss functions. In particular, we show that hinge loss functions share a common risk ordering with the 0-1 loss function.

Theorem (ref) and inequalities similar to ((ref)) lead to a generalized Zhang_2004's Zhang_2004 inequality for weighted classification, as shown in the next corollary.

Similar to the analysis in Section (ref), we consider adding functional form restrictions to the class of classifiers $\mathcal{F}_{\mathcal{G}}$. Let $\widetilde{\mathcal{F}}_{\mathcal{G}}$ be a subclass of $\mathcal{F}_\mathcal{G}$. We suppose that the non-negative weight variable $\omega$ is bounded from above.

In causal policy learning, Condition (ref) holds if the outcome variable $Z$ has bounded support and the propensity score $e(x)$ satisfies a strict overlap condition. For example, if the support of $Z$ is contained in $[-\tilde{M},\tilde{M}]$ for some $\tilde{M} <\infty$, and the propensity score satisfies $\kappa < e(x) < 1-\kappa$ for some $\kappa \in (0,1/2)$ and all $x\in \mathcal{X}$, then the weight variable for the causal policy learning $\omega_{p}$ defined in ((ref)) is bounded from above by $\tilde{M}/\kappa$ a.s.

The following theorem, which is analogous to Theorem (ref), shows that the two conditions (ref) and (ref) in Theorem (ref) remain sufficient for $\widetilde{\mathcal{F}}_\mathcal{G}$ to guarantee the consistency of the hinge risk minimization approach to weighted classification.

Empirical illustration

To illustrate the hinge risk minimizing approach in a causal policy learning setting, we apply our weighted classification methods with a monotone constraint to experimental data from karlan_et_al_2019. karlan_et_al_2019 conducted three experiments in India and the Philippines in which they paid off the high-interest moneylender debt of market vendors and gave them brief financial training. Though the main focus of karlan_et_al_2019 is to understand why a debt-trap occurs (i.e., why some individuals repeatedly take on high-interest rate loans), we regard their treatment of paying off debt as policy intervention and study effective treatment allocation maximizing the value of household business in the population.

We use the data of karlan_et_al_2019, collected from an RCT experiment conducted in Cagayan de Oro, the Philippines, in 2010. The observations are divided into two groups: a treatment group (debt paid off and received financial training) and a control group. The data was collected over 5 periods, comprising a baseline period before the policy intervention and 4 follow-up periods after the policy intervention was implemented. The follow-up periods correspond to the 1st, 4th, 8th, and 18-19th months after the policy intervention was implemented. We label these follow-up periods as periods 1 through 4, respectively. After dropping observations with missing values, our main sample consists of 411 observations, of which 289 (122) observations belong to the treatment (control) group.

We focus on the effect of treatment on the present value (PV) of business at the time of the policy intervention. To define the PV of business, we introduce some notation. Let $D \in \{-1,1\}$ denote a treatment indicator, with $1$ indicating treatment and $-1$ indicating control. Let $C$ be the amount of moneylender debt paid off, which we assume to be a cost of treatment. Let $P_t$ denote monthly take-home profit in month $t$ after the policy intervention. For $s \in \{1,2,3,4\}$, let $P_{(s)}$ denote an average of the monthly take-home profit observed in the follow-up period $s$. Since the data was collected only for 4 follow-up periods, we assume that $P_{t}=P_{(1)}$ for $t\leq 2$, $P_{t}=P_{(2)}$ for $3\leq t\leq 6$, $P_{t}=P_{(3)}$ for $7\leq t\leq 11$, and $P_{t}=P_{(4)}$ for $t\geq 12$. Let $WC_{19}$ denote the total working capital of business in the 19th month after the policy intervention (at the end of the follow-up survey), which corresponds to the total working capital of business observed in the final follow-up period.\footnote{The total working capital of a business, as defined in karlan_et_al_2019, is the worth of current business assets plus the amount spent on an average restocking trip minus any current or daily loans owed.} All variables $P_t$, $WC_{19}$, and $C$ are measured in USD, using the average exchange rate during September and October, 2010. For $T \geq 1$, we define the outcome variable $Z$ as the PV of business minus the cost of the treatment as follows:

where $r$ is the monthly discount rate of the business value, to 0.037/12, the average of the annual real interest rate in force in the Philippines between 2010 and 2019 divided by 12. In our analysis, we set $T=19$ (the duration of the follow-up survey), $60$, $120$, and $240$.

The covariates that we use for treatment assignment are the amount of moneylender debt in the baseline period, financial literacy index, and food expenditure ratio. Specifically, we consider the following three sets of covariates\footnote{Aside from these three covariates, karlan_et_al_2019 use vendors' time inconsistent preferences, possession of savings at a bank, math skills index, and predicted probability of household income shock for estimation of the conditional causal effects.}:

All of the covariates are observed in the baseline period. The food expenditure ratio is the proportion of expenditure on food and drink to total expenditure, and is used to gauge living standards, i.e., the higher the ratio, the poorer the household is considered to be. The amount of moneylender debt in the baseline period is measured in USD, using the same average exchange rate used to define $Z$. For each set of covariates, we constrain the class of feasible treatment rules to the class of monotonically increasing treatment rules, i.e.,

where $x \geq \tilde{x}$ is an element-wise weak inequality. Any treatment rule in $\mathcal{F}_{M}$ is more likely to award treatment to individuals with more baseline debt, higher financial literacy and a higher food expenditure ratio. This class of monotone rules is intended to represent the planner's (hypothetical) objective of prioritizing those households that are more financially-strained and debt-trapped, and those that have a lower standard of living. At the same time, the monotonicity of assignment in financial literacy disciplines the allocation of the policy by prioritizing those who are more likely to escape a debt-trap, assuming that financial literacy is a good predictor for this.

Let $\hat{e}$ be the empirical probability of treatment, which we use as an estimated propensity score. Setting $\omega = |Z|/(D\hat{e} + (1-D)/2)$ and $Y=\mathrm{sign}(Z)\cdot D$ in the definitions of the weighted classification and surrogate risks (((ref)) and ((ref))), let $\hat{f}_{M}$ be a classifier that minimizes the empirical weighted hinge risk over $\mathcal{F}_{M}$ (see Appendix (ref) for details of this procedure). Denote $f_{-1}$ and $f_{+1}$ the never-treating and always-treating rules (i.e., $f_{-1}(x)=-1$ and $f_{+1}(x)=1$ for all $x$).

Table (ref) shows the estimated welfare gains of $\hat{f}_{M}$ relative to the never-treating rule (i.e., $W(\hat{f}_M) - W(f_{-1})$). Figure (ref) illustrates the resulting treatment allocation $G_{\hat{f}_M}$ for the covariate sets $X_1$ and $X_2$, for each $T$. The welfare gains in Table (ref) are estimated using the same sample as is used to estimate $\hat{f}_{M}$; hence, the estimated welfare gains of $\hat{f}_{M}$ in Table (ref) are positively biased.\footnote{To our knowledge, there is no bias-free estimation method available for the welfare gain of the policy that maximizes the full-sample objective function over the large class of monotone assignment rules. Out-of-sample methods based upon sample-splitting is a simple approach for inferring welfare gain, but the policy estimated from a subsample can sacrifice welfare performance. We leave development of bias-free estimation applicable to the current context for future research.} Using $X_2$ rather than $X_{1}$ leads to higher estimates of the welfare gain from using $\hat{f}_M$. Figure (ref) shows the estimated treatment allocation rules under the monotonicity constraint. When we use $X_{1}$, we obtain an optimal treatment rule that is identical for all $T\in \{19,60,120,240\}$. In contrast, the estimated treatment rules differ between $T=19$ and $T \in \{60,120,240\}$ when we use $X_2$.

Conclusion

This paper studies the consistency of surrogate risk minimization approaches to classification and weighted classification given a constrained set of classifiers, where weighted classification subsumes policy learning for individualized treatment assignment rules. Our focus is on how surrogate risk minimizing classifiers behave if the constrained class of classifiers violates the assumption of correct specification. Our first main result shows that when the constraint restricts classifiers' prediction sets only, hinge losses are the only loss functions that secure consistency of the surrogate-risk minimizing classifier without the assumption of correct specification. When the constraint additionally restricts the functional form of the classifiers, the surrogate risk minimizing classifier is not generally consistent even with hinge loss. Our second main result is to show that, in this case, the set of conditions (ref) and (ref) in Theorem (ref) becomes a sufficient condition for the consistency of the hinge risk minimizing classifier.

This paper also investigates the statistical properties of hinge risk minimizing classifiers in terms of uniform upper bounds on the excess regret. Exploiting hinge loss and the class of monotone classifiers in the monotone classification problem, we show that the empirical surrogate-risk minimizing classifier can be computed using linear programming. All of the results obtained in the standard classification setting are naturally extended to the weighted classification problem, so that our contributions carry over to causal policy learning and related applications.