Constrained Classification and Policy Learning

The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.

133,995 characters

Constrained Classification and Policy Learning


\title{{Constrained Classification and Policy Learning}{\Large \thanks{
We thank Ashesh Rambachan, J\"{o}rg Stoye, and Max Tabord-Meehan for valuable discussions and comments. We also thank participants at the 2021 Cowles Foundation Econometrics Conference, 2021 NASMES, 2021 SEA conference, and seminar participants at Bristol, CEMFI, Chicago, Cornell, CUHK, Glasgow, Northwestern, NYU, Penn State, SciencesPo, Syracuse, UBC, UC-Berkeley, UC-Irvine, UC-Riverside, UPenn, UW Madison, and Z\"{u}rich for beneficial comments. The authors gratefully acknowledge financial support from ERC grant 715940,
the ESRC Centre for Microdata Methods and Practice (CeMMAP) (RES-589-28-0001),
Swiss NSF grant 192580,
and JSPS KAKENHI grant 22K20155.}}}
\author{Toru Kitagawa\thanks{ Department of Economics, Brown University, and Department of Economics, University College London. Email: toru\[email removed]}, Shosei Sakaguchi\thanks{Faculty of Economics, University of Tokyo. Email: [email removed]}, and Aleksey Tetenov\thanks{Geneva School of Economics and Management, University of Geneva. Email: [email removed]}}
\date{\today}
\maketitle
\begin{abstract}
Modern machine learning approaches to classification, including AdaBoost, support vector machines, and deep neural networks, utilize surrogate loss techniques to circumvent the computational complexity of minimizing empirical classification risk.
These techniques are also useful for causal policy learning problems, since estimation of individualized treatment rules can be cast as a weighted (cost-sensitive) classification problem.
Consistency of the surrogate loss approaches studied in \citet{Zhang_2004} and \citet{Bartlett_et_al_2006} relies on the assumption of \textit{correct specification}, which means that the specified set of classifiers is rich enough to contain a first-best classifier.
This assumption is, however, less credible when the set of classifiers is constrained by interpretability or fairness, leaving the applicability of surrogate loss-based algorithms unknown in such second-best scenarios.
This paper studies consistency of surrogate loss procedures under a constrained set of classifiers without assuming correct specification.
We show that in settings where the constraint restricts the classifier's prediction set only, hinge losses (i.e., $\ell_1$-support vector machines) are the only surrogate losses that preserve consistency in second-best scenarios.
If the constraint additionally restricts the functional form of the classifier, consistency of a surrogate loss approach is not guaranteed, even with hinge loss.
We therefore characterize conditions on the constrained set of classifiers that can guarantee consistency of hinge risk minimizing classifiers.
Exploiting our theoretical results, we develop robust and computationally attractive hinge loss-based procedures for a monotone classification problem.
\end{abstract}

\textbf{Keywords:} Surrogate loss, support vector machine, monotone classification, fairness in machine learning, statistical treatment choice, personalized medicine
\newpage{}

\onehalfspacing

\section{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 (\citet{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 (\citet{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 \textit{prediction set} of $f$. The goal is to learn a classifier that minimizes \textit{classification risk}:
\begin{equation} \label{eq:classification_risk}
R(f) \equiv P(\text{sign}(f(X)) \neq Y) = E_P[ 1 \{ Y \cdot \text{sign}( f(X) ) \leq 0 \} ].
\end{equation}
Given a training sample $\{ (Y_i,X_i) \sim_{iid} P : i=1,\dots,n \}$, the empirical risk minimization principle of \citet{Vapnik98} recommends estimating the optimal classifier by minimizing empirical classification risk,
\begin{align}
&\hat{f} \in \arg \inf_{f \in \mathcal{F}} \widehat{R}(f), \label{eq:ERM_optimization} \\
& \widehat{R}(f) \equiv \frac{1}{n} \sum_{i=1}^{n} 1\{ Y_i \cdot \mbox{sign}(f(X_i)) \leq 0 \},  \tag*{}
\end{align}
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, \citet{DGLbook96} and \citet{Lugosi02}.

Despite the desirable performance guarantee of the ERM classifer, the computational complexity of solving the optimization in (\ref{eq:ERM_optimization}) 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 (\citet{Cortes_Vapnik_1995}), AdaBoost (\citet{Freund_Schapire_1997}), and neural networks. Focusing on optimization, each of these algorithms can be viewed as targeting the minimization of \textit{surrogate risk},
\begin{equation} \label{eq:surrogate_risk}
    R_{\phi}(f) \equiv E_P [\phi (Y f(X))],
\end{equation}
where $\phi: \mathbb{R} \to \mathbb{R}$ is called the \textit{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{eq:surrogate_risk}) 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 \citet{Zhang_2004} and \citet{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 \textit{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 \textit{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
\begin{equation}
\mathcal{G}_M \equiv \{G \subset \mathcal{X} : x \in G  \Rightarrow x' \in G \ \forall x' \leq x \}, \notag
\end{equation}
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
\begin{align}
& \hat{f}_M \in \arg \inf_{f \in \mathcal{F}_M} \widehat{R}_{\phi_h} (f), \label{eq:monotone_empriical_surrogate_risk} \\
& \widehat{R}_{\phi_h} (f) \equiv \frac{1}{n} \sum_{i=1}^n \phi_h (y_i f(x_i)). \notag
\end{align}
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{eq:monotone_empriical_surrogate_risk}) 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{eq:monotone_empriical_surrogate_risk}) over the Bernstein polynomials. Adopting either approach, the application of our main theorems guarantees
\begin{equation}
    R(\hat{f}_M) - \inf_{f \in \mathcal{F}_M}R(f) \xrightarrow[p]{} 0, \notag
\end{equation}
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$.

\subsection{Connection and contributions to causal policy learning} \label{sec: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
\begin{equation}
R^{\omega}(f) \equiv E_P[\omega \cdot 1 \{ Y \cdot \text{sign}( f(X) ) \leq 0 \} ]. \label{eq:weighted_classification_risk}
\end{equation}
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 (\citet{LieliWhite2010}) or welfare weights over the individuals to be classified, as considered in \citet{Rambachan_2020} and \citet{Babii_et_al_2020}. The surrogate risk for weighted classification can be defined similarly to (\ref{eq:surrogate_risk}), as
\begin{equation}
    R_{\phi}^{\omega}(f) = E_P[\omega \cdot \phi(Y f(X)) ]. \label{eq:weighted_surrogate_risk}
\end{equation}

As discussed in \citet{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{eq:weighted_classification_risk}) 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 \citet{Manski2004}, we consider evaluating the welfare performance of the assignment policy $f$ by the average outcomes attained under its associated assignment rule:
\begin{equation}
    W(f) \equiv E_P \left[ Z(+1) \cdot 1\{ X \in G_f \} + Z(-1) \cdot 1\{ X \notin G_f \} \right] \nonumber
\end{equation}
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{\citet{KL21} makes use of this transformation of the welfare objective function to develop an Adaboost algorithm for treatment choice.}
\begin{align}
W(f) &= E_P \left[ \frac{Z}{D e(X) + (1- D)/2 } \cdot 1\{ D = \text{sign}(f(X)) \} \right] \notag \\
     & = E_P \left[ \max \left\{0,\frac{Z}{D e(X) + (1- D)/2 } \right\} \right]  - E_P \left[ \omega_p \cdot 1\{\mathrm{sign}(Z) \cdot D \cdot \text{sign}(f(X)) \leq 0 \} \right], \mspace{15mu}  \label{eq:policy_learning_welfare}
     \intertext{where}
     \omega_p & \equiv \frac{|Z|}{D e(X) + (1- D)/2 } \geq 0. \notag
\end{align}
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{eq:weighted_classification_risk}) 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 \citet{BeygelzimerLangford09} and the doubly-robust approaches of \citet{SJ15} and \citet{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{eq:weighted_surrogate_risk}) with $\omega = \omega_p$ and $Y=\mathrm{sign}(Z)\cdot D$.
Section \ref{sec:Extension to individualized treatment rules} 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 \citet{KT18} and \citet{MT17}.




\subsection{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 \cite{Mannor_et_al_2003}, \cite{Jiang_2004}, \cite{Lugosi_Vayatis_2004} , \cite{Zhang_2004}, \citet{Steinwart_2005, Steinwart_2007}, \cite{Bartlett_et_al_2006}, \cite{Nguyen_et_al_2009}, and \cite{Scott_2012}.
Under the assumption of correct specification, \cite{Zhang_2004} and \cite{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. \cite{Bartlett_et_al_2006} show that the classification-calibration property of surrogate loss, defined in Section \ref{sec:calibration of MG-constrained classification} below, guarantees risk consistency.
\cite{Zhang_2004} and \cite{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, \cite{Nguyen_et_al_2009} study sufficient and necessary conditions for surrogate risk minimization to yield risk consistency.
\cite{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., \cite{Zeng_et_al_2017}, and \cite{Zhang_et_al_2018}), fair classification (e.g., \cite{Dwork_et_al_2012}), and monotone classification (e.g., \cite{Cano_et_al_2019}). Some works in the existing literature adopt a surrogate loss approach. \cite{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. \cite{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.

\cite{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 (\cite{Manski1975}, \cite{ManskiThompson1989}) share the same objective function.
\cite{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 \cite{Manski2004}, \cite{Dehejia2005}, \cite{HiranoPorter2009}, \citet{Stoye2009,Stoye2012}, \cite{Chamberlain2011}, \cite{BhattacharyaDupas2012}, \cite{Tetenov2012}, \cite{Kasy2018}, \cite{KT18, KT21}, \cite{Viviano_2019}, \cite{AW17}, \cite{MT17}, \cite{Sakaguchi_2021}, \cite{KW23}, among others. As discussed above, the policy learning methods of \cite{KT18}, \cite{AW17}, and \cite{MT17} build on the similarity between empirical welfare maximizing treatment choice and ERM classification.
\cite{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.
\cite{AW17} apply doubly-robust estimators to estimate the weight $\omega$ in (\ref{eq:weighted_surrogate_risk}), 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 \cite{Zadrozny03}, \cite{BeygelzimerLangford09}, \cite{Qian_Murphy_2011}, \cite{Zhao2012JASA}, \cite{SJ15}, \cite{Zhao_et_al_2015}, and \cite{Kallus_2020}, among others. \cite{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. \cite{Zhao_et_al_2015} extend this approach to estimate optimal dynamic treatment regimes.





\section{Constrained classification with surrogate loss}
\label{sec:constrained classification and surrogate loss approach}

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{eq:classification_risk}).

We study constrained classification problems where an optimal classifier is searched for over a restricted class of functions. Section \ref{sec:misspecification in constrained classification} 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{sec:MG-constrained classification} introduces a classification problem that embeds a constraint on the prediction sets, which is a central problem throughout the paper.

\subsection{Misspecification in constrained classification} \label{sec: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
\begin{equation}
    f^{\ast}_{Bayes} = 2 \eta(x) - 1 \notag
\end{equation}
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.

\bigskip{}

\begin{definition}[$R$-misspecification] \label{def:misspecification}
$\mathcal{F}$ is $R$-misspecified if
\begin{equation} \notag
\inf_{f \in \mathcal{F}} R(f) > R(f^{\ast}_{Bayes}).
\end{equation}
If the inequality instead holds with equality, we say that $\mathcal{F}$ is $R$-correctly specified.
\end{definition}

\bigskip{}

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{tb:surrogate loss functions and their forms of H} below lists some commonly used surrogate loss functions including
the \textit{hinge loss} $\phi_h(\alpha)=c\max\{0, 1-\alpha\}$, which corresponds to $\ell_1$-support vector machines, and the \textit{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.
\bigskip{}

\begin{definition}[$R_\phi$-misspecification]
\label{def:surrogate risk misspecification}
Let $f_{\phi,FB}^{\ast}$ be a minimizer of $R_{\phi}$ over the unconstrained class of classifiers, i.e., the class of all measurable functions $f: \mathcal{X} \to \mathbb{R}$.  A constrained class $\mathcal{F}$ is $R_\phi$-misspecified if
\begin{align*}
    \inf_{f \in \mathcal{F}} R_{\phi}(f) > R_{\phi}(f_{\phi,FB}^{\ast}).
\end{align*}
If the inequality instead holds with equality, we say that $\mathcal{F}$ is $R_{\phi}$-correctly specified.
\end{definition}
\bigskip{}

The seminal theoretical results that guarantee consistency of surrogate-risk classification (\citet{Zhang_2004}, \citet{Bartlett_et_al_2006}, and
\citet{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{def:misspecification} and \ref{def:surrogate risk misspecification}, respectively. The central question that this paper poses is \textit{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 \citet{Bartlett_et_al_2006}.

\bigskip{}

\begin{definition}[Classification-calibrated loss functions]\label{def:classification-calibrated loss functions} For $a \in \mathbb{R}$ and $0 \leq b \leq 1$, define $C_{\phi}(a, b) \equiv \phi ( a ) b+\phi(-a )(1-b)$.
A loss function $\phi$ is classification-calibrated if for any $b \in [0,1]\backslash\{1/2\} $,
\begin{equation*}
\inf_{\left\{ a\in\mathbb{R}\, :\, a \left(2b-1\right)<0\right\} }C_{\phi}(a,b) >  \inf_{\left\{ a\in\mathbb{R} \,:\, a \left(2b-1\right) \geq 0\right\} }C_{\phi}(a,b).
\end{equation*}
\end{definition}

\bigskip{}

Noting that the surrogate risk can be expressed as
\begin{equation}
    E_P[\phi(Yf(X))]=E_{P_X}[C_{\phi}(f(X), \eta(X))], \label{eq:surrogate rick expression}
\end{equation}
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))$.
\citet{Bartlett_et_al_2006} shows that many commonly used surrogate loss functions including those listed in Table \ref{tb:surrogate loss functions and their forms of H} are classification-calibrated.\footnote{\citet{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.
\bigskip{}

\begin{proposition}\label{prop:misspecification relation}
Let $\mathcal{F}$ be a constrained class of classifiers and $f_{\phi}^{\ast} \in \mathcal{F}$ be a minimizer of $R_{\phi}$ over $\mathcal{F}$. Suppose $\phi$ is a classification-calibrated loss function.
\\
(i) For any distribution $P$ on $\{-1,1\}\times \mathcal{X}$, if $\mathcal{F}$ is $R_{\phi}$-correctly specified, then $\mathcal{F}$ is $R$-correctly specified and $R(f_{\phi}^{\ast})=R(f_{Bayes}^{\ast})$ holds;\\
(ii) If $\phi$ is, in addition, convex, there exist a distribution $P$ on $\{-1,1\}\times \mathcal{X}$ and a class of classifiers $\mathcal{F}$ under which $\mathcal{F}$ is $R$-correctly specified but $R_{\phi}$-misspecified, and $R (f_{\phi}^{\ast}) > R(f_{Bayes}^{\ast})$ holds.
\end{proposition}
\begin{proof}
See Appendix \ref{appx:proof 1}.
\end{proof}

\bigskip

Proposition \ref{prop:misspecification relation} (i), which rephrases Claim 3 of Theorem 1 in \cite{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 \cite{Bartlett_et_al_2006} is that for any $P$ and every sequence of measurable functions $\{ f_{i}:\mathcal{X} \rightarrow \mathbb{R}\}$,
\begin{align}
    R_{\phi}(f_{i}) \rightarrow \inf_{f\in \mathcal{F}}R_{\phi}(f) \mbox{ implies that } R(f_{i}) \rightarrow \inf_{f\in \mathcal{F}}R(f). \nonumber
\end{align}
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{prop:misspecification relation} (ii), in contrast, shows that $R$-correct specification of $\mathcal{F}$ does \textit{not} guarantee $R_{\phi}$-correct specification.\footnote{
Given a convex classification-calibrated loss function $\phi$, our proof of Proposition \ref{prop:misspecification relation} (ii) in Appendix \ref{appx:proof 1} 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.


\subsection{$\mathcal{G}$-constrained classification}
\label{sec:MG-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{exm:interpretable classification}--\ref{exm:fair classification} below for motivating examples.

We denote by
\begin{equation}
\mathcal{F}_{\mathcal{G}}\equiv\left\{ f:G_{f}\in\mathcal{G},\ f(\cdot)\in[-1,1]\right\} \label{eq:g_restriction} \notag
\end{equation}
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 \textit{$\mathcal{G}$-constrained class of classifiers} and to the classification problem over $\mathcal{F}_\mathcal{G}$ as \textit{$\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.

\bigskip{}

\begin{example}[Interpretable classification]
\label{exm:interpretable classification}
Decision-makers may prefer simple decision or classification rules that are easily understood or explained even at the cost of harming prediction accuracy. This concept, often referred to as \textit{interpretable machine learning}, has been pursued, for instance, in the prediction analysis of recidivism (\citet{Zeng_et_al_2017}) and the decision on medical intervention protocol (\citet{Zhang_et_al_2018}). An example is a linear classification rule, in which
$\mathcal{G}$ is a class of half-spaces with linear boundaries in $\mathcal{X}$,
\begin{equation}
    \mathcal{G}=\{x\in\mathbb{R}^{d_x}:x^{T}\beta\geq0,\beta\in\mathbb{R}^{d_x}\}. \notag
\end{equation}
Note that $f \in \mathcal{F}_{\mathcal{G}}$ is not restricted to be a linear function. Any function $f$, including nonlinear functions, is included in $\mathcal{F}_{\mathcal{G}}$ as long as its prediction set $G_{f}$ is a hyperplane in $\mathcal{X}$. A classification tree is another type of classification rule that is interpretable. See, e.g., \citet{Breiman84book}.
\end{example}

\bigskip{}

\begin{example}[Monotone classification]
\label{exm:monotone classification} The framework we study can accommodate monotonicity constraints on classification.
Formally, a monotonicity constraint corresponds to a partial order $\precsim$ on $\mathcal{X}$, and any prediction set $G_{f}$ has to respect this partial order in the sense that if $x_{1} \precsim x_{2}$ and $x_{1} \in G_{f}$, then $x_{2}\in G_{f}$. Monotonicity constraints have been utilized in the classification of credit rating (\citet{Chen_Li_2014}), and in the assignment of job training in the context of policy learning (\citet{MT17}).
\end{example}

\bigskip{}

\begin{example}[Fair classification]
\label{exm:fair classification}  Specification of $\mathcal{G}$ can accommodate some fairness constraints introduced
in the literature on \textit{fair classification}.
Let $A=\left\{ 0,1\right\} $ be an element of $X$ indicating a binary protected group variable (e.g., race, gender). The decision-maker wants to ensure fairness of classification by, for instance, equalizing the raw positive classification rate (known as statistical parity): $P_{X}\left(f(x)\geq0\mid A=1\right)=P_{X}\left(f(x)\geq0\mid A=0\right)$.
The classification problem embedding this constraint is equivalent to $\mathcal{G}$-constrained classification with
\begin{align*}
{\cal G} & =\left\{ G\in2^{{\cal X}}:P_{X}\left(X\in G\mid A=1\right)=P_{X}\left(X\in G\mid A=0\right)\right\} ,
\end{align*}
where $\mathcal{G}$ depends on $P_{X}$ in this case. This fairness constraint is studied by \citet{Calders_Verwer_2010},
\citet{Kamishima_et_al_2011}, \citet{Dwork_et_al_2012}, \citet{Feldman_et_al_2015},
among others.
Some other forms of
fairness constraint, such as equalized odds and equalized positive
predictive value as reviewed by \citet{Chouldechova_et_al_2018},
can be accommodated in our framework as well via an appropriate construction of $\mathcal{G}$.
\end{example}

\bigskip

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.


\bigskip{}

\begin{proposition}\label{prop:MG-constrained misspecification relation}
Suppose $\phi$ is a classification-calibrated loss function. Let $\mathcal{G} \subseteq 2^{\mathcal{X}}$ be a class of measurable subsets of $\mathcal{X}$ and $f_{\phi}^{\ast} \in \mathcal{F}_{\mathcal{G}}$ be a minimizer of $R_{\phi}$ over $\mathcal{F}_{\mathcal{G}}$. Then, for any distribution $P$ on $\{-1,1\}\times \mathcal{X}$, $R(f_{\phi}^{\ast}) = R(f_{Bayes}^{\ast})$ holds if and only if $\mathcal{F}_{\mathcal{G}}$ is $R$-correctly specified.
\end{proposition}

\begin{proof}
See Appendix \ref{appx:proof 1}.
\end{proof}

\bigskip

Proposition \ref{prop:MG-constrained misspecification relation} 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{prop:misspecification relation} (ii) and Proposition \ref{prop:MG-constrained misspecification relation} clarifies a special feature of the $\mathcal{G}$-constrained class of classifiers. Specifically, Proposition \ref{prop:misspecification relation} (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 \cite{Zhang_2004} and \cite{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{exm:interpretable classification}--\ref{exm:fair classification} 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)$ \textit{without} requiring $R$-correct specification of $\mathcal{F}_{\mathcal{G}}$.




\section{Calibration of $\mathcal{G}$-constrained classification}
\label{sec:calibration of MG-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}}$:
\begin{align}
f^{*} & \in\arg\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f).\notag
\end{align}
Similarly, we denote a best classifier among $\mathcal{F}_{\mathcal{G}}$ in terms of
the surrogate risk by $f_{\phi}^{\ast}$,
\begin{align}
f_{\phi}^{*} & \in\arg\inf_{f\in\mathcal{F}_{\mathcal{G}}}R_{\phi}(f),\label{eqsurr_problem}. \notag
\end{align}

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

\bigskip{}

\begin{example}[Numerical example 1]
\label{ex:numerical example 1} Let $\mathcal{X}=\{0,1,2\}$ and $\mathcal{G}=\{\emptyset,\{2\},\{2,1\},\{2,1,0\}\}$. Here, $\mathcal{G}$ imposes monotonicity of the prediction sets in a way that is compatible with Example \ref{exm:monotone classification}.
We specify $P_X$ to be uniform on $\mathcal{X}$ and $P(Y=+1\mid X=0)=0.9$, $P(Y=+1\mid X=1)=0.3$, and $P(Y=+1\mid X=2)=0.2$. The Bayes classifier therefore predicts $Y= +1$ at $x=0$ and $Y= -1$ at $x=1$ and $2$, but such a prediction set is excluded from $\mathcal{G}$. That is, $\mathcal{F}_{\mathcal{G}}$ is R-misspecified.
Under this specification, the second-best (constrained optimum) classifier
$f^{*}$ has a prediction set equal to $\emptyset$, and attains the classification risk $R(f^{\ast}) = 0.47$.

For each of hinge loss $\phi_h$ with $c=1$, exponential loss $\phi_e$, and truncated quadratic loss $\phi_q$, we compute the classifier minimizing the surrogate risk $f_{\phi}^{*}$ and the classification risk at the surrogate optimal classifier $R(f_{\phi}^{*})$.
Figure \ref{fig:monotone classification} illustrates each computed classifier with each loss function.
We obtain
\begin{align*}
& R(f_{\phi_{h}}^{*}) = 0.47 = R(f^{*}), \mspace{15mu} R(f_{\phi_{e}}^{*})=R(f_{\phi_{q}}^{*}) = 0.53, \\
& G_{f_{\phi_{h}}^{*}}=\emptyset = G_{f^{*}}, \mspace{15mu} G_{f_{\phi_{e}}^{*}}=G_{f_{\phi_{q}}^{*}}=\{2,1,0\}.
\end{align*}
In this specification, the hinge risk optimal classifier agrees with the second best optimal classifier, whereas this is not the case for the exponential or truncated quadratic loss.

\bigskip
\begin{figure}[ht]
\caption{Monotone classifiers minimizing classification and surrogate risks}
\begin{center}
\begin{tabular}{c}
\includegraphics[scale=0.45]{figures/figure_monotone_classification.png}
\label{fig:monotone classification}
\end{tabular}
\begin{tablenotes}
\item[] {\footnotesize Notes: The square points correspond to the values of $f^{\ast}(x)$ at $x=0,1$, and $2$. The circular points correspond to the values of each of $f_{\phi_h}^{\ast}(x)$, $f_{\phi_e}^{\ast}(x)$, and $f_{\phi_q}^{\ast}(x)$ at $x=0,1$, and $2$.}
\end{tablenotes}
\end{center}
\end{figure}
\end{example}

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 \textit{$\mathcal{G}$-constrained excess risk} of $f$ as \begin{equation}
R(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f), \notag
\end{equation}
which is the \textit{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
\begin{align*}
    R_{\phi}(f) - \inf_{f \in \mathcal{F}_{\mathcal{G}}}R_{\phi}(f).
\end{align*}
Fix $G\in\mathcal{G}$ and let
\begin{align*}
\mathcal{F}_{G}\equiv\{f:G_{f}=G,f(\cdot)\in[-1,1]\}
\end{align*}
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
\begin{align}
\mathcal{R}(G) & =\int_{\mathcal{X}}\left[\eta(x)1\{x\notin G\}+(1-\eta(x))1\{x\in G\}\right]dP_{X}(x),\nonumber \\
 & =\int_{\mathcal{X}}(1-2\eta(x))\cdot1\{x\in G\}dP_{X}(x)+P(Y=1).\label{eq:classification risk at G}
\end{align}
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
\begin{align}
\mathcal{R}_{\phi}(G) & =\inf_{f\in\mathcal{F}_{G}}\int_{\mathcal{X}}\left[\eta(x)\phi(f(x))+(1-\eta(x))\phi(-f(x))\right]dP_{X}(x)\nonumber \\
 & =\int_{G}\inf_{0 \leq f(x)\leq1}C_{\phi}(f(x),\eta(x))dP_{X}(x)+\int_{G^{c}}\inf_{-1\leq f(x) < 0}C_{\phi}(f(x),\eta(x))dP_{X}(x),\nonumber
\end{align}
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
\begin{align*}
C_{\phi}^{+}(\eta(x)) & \equiv\inf_{0 \leq f(x)\leq1}C_{\phi}(f(x),\eta(x)),\\
C_{\phi}^{-}(\eta(x)) & \equiv\inf_{-1\leq f(x) < 0}C_{\phi}(f(x),\eta(x)),\\
\Delta C_{\phi}(\eta(x)) & \equiv C_{\phi}^{+}(\eta(x))-C_{\phi}^{-}(\eta(x)),
\end{align*}
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
\begin{align}
\mathcal{R}_{\phi}(G) & =\int_{\mathcal{X}}\left[C_{\phi}^{+}(\eta(x))\cdot1\{x\in G\}+C_{\phi}^{-}(\eta(x))\cdot1\{x\notin G\}\right]dP_{X}(x)\nonumber \\
 & =\int_{\mathcal{X}}\Delta C_{\phi}(\eta(x))\cdot1\{x\in G\}dP_{X}(x)+\int_{\mathcal{X}}C_{\phi}^{-}(\eta(x))dP_{X}(x).\label{eq:simplified surrogate risk}
\end{align}
By comparing the expressions of the risks in (\ref{eq:classification risk at G}) and (\ref{eq:simplified surrogate risk}), 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}$.

\bigskip{}

\begin{theorem}[Global calibration of the $\mathcal{G}$-constrained excess risk] \label{thm:risk equivalence}
Let $P$ be an arbitrary distribution on $\{-1,1\}\times \mathcal{X}$ and $\mathcal{G} \subseteq 2^{\mathcal{X}}$ be a class of measurable subsets of $\mathcal{X}$. For $G,G'\in\mathcal{G}$, the risk ordering $\mathcal{R}(G)\geq\mathcal{R}(G')$ in terms of the classification risk
is equivalent to
\begin{equation}
\int_{G\setminus G'}(1-2\eta(x))dP_{X}(x)\geq\int_{G'\setminus G}(1-2\eta(x))dP_{X}(x),\label{eq:thm eq1}
\end{equation}
while the risk ordering $\mathcal{R}_{\phi}(G)\geq\mathcal{R}_{\phi}(G')$ in terms of the surrogate risk
is equivalent to
\begin{equation}
\int_{G\setminus G'}\Delta C_{\phi}(\eta(x))dP_{X}(x)\geq\int_{G'\setminus G}\Delta C_{\phi}(\eta(x))dP_{X}(x).\label{eq:thm eq2}
\end{equation}
Hence, if $\Delta C_{\phi}(\eta(x))$ is proportional to $1-2\eta(x)$ up
to a positive constant, i.e.,
\begin{align}
\Delta C_{\phi}(\eta(x))=c(1-2\eta(x))\mbox{ for some }c>0,\label{eq:conditon_risk equivalence}
\end{align}
the risk ordering over $\mathcal{G}$ in terms of the surrogate risk
$\mathcal{R}_{\phi}(G)$ agrees with the risk ordering over $\mathcal{G}$
in terms of the classification risk $\mathcal{R}(G)$ for any distribution $P$ on $\{-1,1\}\times \mathcal{X}$.

In particular, when $\phi$ is the hinge loss $\phi_h(\alpha) = c \max \{0, 1-\alpha \}$, $c>0$,
\begin{equation}
\Delta C_{\phi}(\eta(x))=c(1-2\eta(x))\label{eq:H difference for hinge} \notag
\end{equation}
holds, establishing that hinge risk preserves the risk ordering of the classification
risk. \end{theorem}
\begin{proof}
By equation (\ref{eq:classification risk at G}),
\begin{align*}
 \mathcal{R}(G)-\mathcal{R}(G')
= & \int_{\mathcal{X}}(1-2\eta(x))\cdot[1\{x\in G\}-1\{x\in G'\}]dP_{X}(x)\\
= & \int_{\mathcal{X}}(1-2\eta(x))\cdot[1\{x\in G\setminus G'\}-1\{x\in G'\setminus G\}]dP_{X}(x)\\
= & \int_{G\setminus G'}(1-2\eta(x))dP_{X}(x)-\int_{G'\setminus G}(1-2\eta(x))dP_{X}(x).
\end{align*}
This proves (\ref{eq:thm eq1}), the first claim of the theorem.

Given the representation of the surrogate risk shown in (\ref{eq:simplified surrogate risk}),
a similar argument yields (\ref{eq:thm eq2}), the second claim of
the theorem.

For the hinge loss $\phi_h(\alpha)=c\max\{0,1-\alpha\}$ and $f\in\mathcal{F}_{G}$,
we have
\begin{align*}
C_{\phi_h}(f(x),\eta(x))=c(1-2\eta(x))f(x)+c.
\end{align*}
Hence, we obtain
\begin{align}
C_{\phi_h}^{+}(\eta) & =\begin{cases}
c(1-2\eta)+c & \text{for \ensuremath{\eta>1/2},}\\
c & \text{for \ensuremath{\eta\leq1/2},}
\end{cases}\nonumber \\
C_{\phi_h}^{-}(\eta) & =\begin{cases}
c & \text{for \ensuremath{\eta>1/2},}\\
2c\eta & \text{for \ensuremath{\eta\leq1/2}.}\notag
\end{cases}
\end{align}
Hence, $\Delta C_{\phi_h}(\eta)=c(1-2\eta)$ holds for all $\eta\in[0,1]$.
\end{proof}
\bigskip{}

Theorem \ref{thm:risk equivalence} does not exploit the condition that $\phi$ is classification-calibrated, but if a surrogate loss function satisfies condition (\ref{eq:conditon_risk equivalence}), it is automatically classification-calibrated. Another remark
follows.

\bigskip{}

\begin{remark} Many commonly used surrogate loss functions do
not satisfy condition (\ref{eq:conditon_risk equivalence}) in
Theorem \ref{thm:risk equivalence}. Table \ref{tb:surrogate loss functions and their forms of H}
shows the forms of $\Delta C_{\phi}(\eta)$ for the hinge loss, exponential loss, logistic
loss, quadratic loss, and truncated quadratic loss functions. With the exception of the hinge loss function, none of these functions satisfy condition (\ref{eq:conditon_risk equivalence}).
That is, among the surrogate loss-based algorithms that are commonly used in practice, the $\ell_1$-support vector machine corresponding to hinge loss is the only algorithm whose surrogate risk preserves the classification risk.

\begin{table}[h]
\centering \caption{Surrogate loss functions and their associated forms for $\Delta C_{\phi}$}
\label{tb:surrogate loss functions and their forms of H}
\begin{threeparttable}
\scalebox{0.9}{
\begin{tabular}{c:c:c}
\hline
Loss function  & $\phi(\alpha)$  & $\Delta C_{\phi}\left(\eta\right)$\tabularnewline
\hline
0-1 loss  & $1\{\alpha\leq0\}$  & $1-2\eta$\tabularnewline
\hdashline
Hinge loss  & $c \max\{0,1-\alpha\}$  & $c(1-2\eta)$\tabularnewline
\hdashline
Exponential loss  & $e^{-\alpha}$  & $\begin{cases}
\begin{array}{c}
-2\sqrt{\eta(1-\eta)}+1\\
2\sqrt{\eta(1-\eta)}-1
\end{array} & \begin{array}{l}
\mbox{if }0\leq\eta<1/2\\
\mbox{if }1/2\leq\eta \leq 1
\end{array}\end{cases}$\tabularnewline
\hdashline
Logistic loss  & $\log(1+e^{-\alpha})$  & $\begin{cases}
\begin{array}{c}
\log(2\eta^{\eta}(1-\eta)^{1-\eta})\\
-\log(2\eta^{\eta}(1-\eta)^{1-\eta})\\
\end{array} & \begin{array}{l}
\mbox{if }0\leq\eta < 1/2\\
\mbox{if }1/2\leq\eta\leq 1\\
\end{array}\end{cases}$\tabularnewline
\hdashline
Quadratic loss  & $(1-\alpha)^{2}$  & $\begin{cases}
\begin{array}{c}
(1-2\eta)^{2}\\
-(1-2\eta)^{2}
\end{array} & \begin{array}{l}
\mbox{if }0\leq\eta <1/2\\
\mbox{if }1/2\leq\eta\leq 1
\end{array}\end{cases}$\tabularnewline
\hdashline
Truncated quadratic loss  & $(\max\{0,1-\alpha\})^{2}$  & $\begin{cases}
\begin{array}{c}
(1-2\eta)^{2}\\
-(1-2\eta)^{2}
\end{array} & \begin{array}{l}
\mbox{if }0\leq\eta <1/2\\
\mbox{if }1/2\leq\eta\leq 1
\end{array}\end{cases}$\tabularnewline
\hline
\end{tabular}}
\end{threeparttable}
\end{table}

\end{remark}

\bigskip{}


The well known inequality by \citet{Zhang_2004} relates the excess surrogate risk to the excess classification risk under $R$-correct specification.
As a corollary of Theorem \ref{thm:risk equivalence}, 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{thm:risk equivalence}. 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{thm:risk equivalence} therefore implies that the $\mathcal{G}$-constrained excess classification risk of $f$ satisfies the following inequality:
\begin{align}
R(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f)=&\ \mathcal{R}(G_f)-\mathcal{R}(G^{\ast}) \notag \\
=&\ \int_{G_f\setminus G^{\ast}}(1-2\eta(x))dP_{X}(x)-\int_{G^{\ast}\setminus G_f}(1-2\eta(x))dP_{X}(x)
\notag \\
=&\ c^{-1} \left[ \mathcal{R}_{\phi_h}(G_f)-\mathcal{R}_{\phi_h}(G^{\ast}) \right] \notag \\
=&\ c^{-1} \left[ \inf_{f^{\prime}\in\mathcal{F}_{G_f}}R_{\phi_h}(f^{\prime})-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R_{\phi_h}(f) \right] \notag \\
\leq&\ c^{-1} \left[ R_{\phi_h}(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R_{\phi_h}(f) \right], \label{eq:generalized zhang's ineq}
\end{align}
where the second equality follows by equation (\ref{eq:classification risk at G}); and
the third equality follows by equation (\ref{eq:simplified surrogate risk})
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.

\bigskip{}

\begin{corollary}\label{corr:zhang's inequality}
For any distribution $P$ on $\{-1,1\}\times \mathcal{X}$ and class of measurable subsets $\mathcal{G} \subseteq 2^{\mathcal{X}}$, if $\Delta C_{\phi}(\eta(x))$ is proportional to $1-2\eta(x)$ with a proportionality
constant $c>0$, i.e., $\Delta C_{\phi}(\eta(x))=c(1-2\eta(x))$, then the
following inequality holds
\begin{align}
c(R(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f))\leq R_{\phi}(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R_{\phi}(f)\label{eq:zhangs inequality} \notag
\end{align}
for any $f\in\mathcal{F}_{\mathcal{G}}$.
\end{corollary}
\begin{proof} See equation (\ref{eq:generalized zhang's ineq}).
\end{proof}
\bigskip{}

Corollary \ref{corr:zhang's inequality} shows that if the surrogate
loss $\phi$ satisfies condition (\ref{eq:conditon_risk equivalence}),
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{eq:conditon_risk equivalence})
in Theorem \ref{thm:risk equivalence} is not only sufficient but
also necessary. To formally show this, we adopt the concept of universal equivalence of loss functions introduced by \citet{Nguyen_et_al_2009} to the current setting.

\bigskip{}

\begin{definition}[Universal equivalence] Loss functions $\phi_{1}$
and $\phi_{2}$ are universally equivalent, denoted by $\phi_{1}\overset{u}{\sim}\phi_{2}$,
if for any distribution $P$ on $\{-1,1\}\times\mathcal{X}$ and class of measurable subsets $\mathcal{G}\subseteq2^{\mathcal{X}}$,
\begin{align*}
{\cal R}_{\phi_{1}}\left(G_{1}\right)\leq{\cal R}_{\phi_{1}}\left(G_{2}\right)  \Leftrightarrow{\cal R}_{\phi_{2}}\left(G_{1}\right)\leq{\cal R}_{\phi_{2}}\left(G_{2}\right)
\end{align*}
holds for any $G_{1},G_{2}\in\mathcal{G}$. \end{definition}

\bigskip{}

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.

\bigskip{}

\begin{theorem} \label{thm:univesal equivalence} Let $\phi_{1}$
and $\phi_{2}$ be classification-calibrated loss functions. Then
$\phi_{1}\overset{u}{\sim}\phi_{2}$ if and only if $\Delta C_{\phi_{2}}\left(\eta\right)=c\Delta C_{\phi_{1}}\left(\eta\right)$
for some $c>0$ and any $\eta\in\left[0,1\right]$, i.e., $\Delta C_{\phi_{2}}$
is proportional to $\Delta C_{\phi_{1}}$ up to a positive constant. \end{theorem}

\begin{proof}
See Appendix \ref{appx:proof 1}.
\end{proof}

\bigskip{}

The `if' part of the theorem is a generalization of Theorem \ref{thm:risk equivalence} 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{thm:univesal equivalence} 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{eq:conditon_risk equivalence}) in Theorem
\ref{thm:risk equivalence}. Hence, the following corollary holds.

\bigskip{}

\begin{corollary} \label{corr:universally equivalence} A classification-calibrated
loss function $\phi$ is universally equivalent to the 0-1 loss function
if and only if $\phi$ satisfies condition (\ref{eq:conditon_risk equivalence})
for any $\eta(x)\in[0,1]$. That is, the class of hinge loss functions $\{\phi (\alpha) = a \max\{0, 1- \alpha \} + b: a>0, b\geq 0 \}$ agrees with the class of loss functions that are universally equivalent to the 0-1 loss function.
\end{corollary}

\bigskip{}

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 \citet{Nguyen_et_al_2009}.

\bigskip{}

\begin{remark} \label{remark:Nguyen_et_al_2009} \citet{Nguyen_et_al_2009} show that, for the classification problem in which an optimal pair comprising a quantizer and a classifier is to be chosen,
the hinge loss function is also the only surrogate loss function that preserves the consistency of surrogate loss classification. In their framework, the quantizer is a stochastic mapping $Q\in\mathcal{Q}:{\cal X}\mapsto{\cal Z}$,
where ${\cal Z}$ is a discrete space and ${\cal Q}$ is a possibly
constrained class of conditional distributions of $Z$ given $X$,
$Q\left(Z\mid X\right)$. The classifier is a function $\gamma\in\Gamma:{\cal Z}\mapsto\mathbb{R}$,
where $\Gamma$ is the set of all measurable functions on ${\cal Z}$. The motivation for using $Z$ as an input, instead of $X$, is to reduce the dimension of $X$, which might be a high-dimensional vector. \citet{Nguyen_et_al_2009} propose estimating the pair $\left(Q,\gamma\right)\in\mathcal{Q}\times\Gamma$ that minimizes the risk $R\left(\gamma,Q\right){\equiv}P\left(Y\neq\mbox{sign}\left(\gamma\left(Z\right)\right)\right)$, by solving the surrogate loss classification problem: $\inf_{(Q,\gamma)\in\mathcal{Q}\times\Gamma}R_{\phi}(Q,\gamma)$, where $R_{\phi}(Q,\gamma)=E\phi(Y\gamma(Z))$. They show that, among the commonly used surrogate loss functions, only hinge loss classification leads to the optimal pair of $(Q,\gamma)$.

The framework we study is different from that of \citet{Nguyen_et_al_2009}, and neither nests the other. The framework \citet{Nguyen_et_al_2009}
study constrains the mapping $Q:{\cal X}\mapsto{\cal Z}$, whereas the framework we study constrains prediction sets $G_{f}$ for all classifiers $f$. Furthermore, the class of classifiers $\Gamma$ considered in \citet{Nguyen_et_al_2009} contains the Bayes classifier, whereas the class of classifiers $\mathcal{F}_{\mathcal{G}}$ we consider may not contain the Bayes classifier.
\end{remark}


\section{Consistency of hinge risk classification with functional form constraints}
\label{sec:classification preserving reduction}

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{corr:zhang's inequality} 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{thm:risk equivalence} breaks down. The following example illustrates this phenomenon.

\bigskip{}

\begin{example}[Numerical example 2]\label{ex:numerical example 2}
Maintain $\mathcal{X}=\{0,1,2\}$ and $\mathcal{G}=\{\emptyset,\{2\},\{2,1\},\{2,1,0\}\}$ as in Example \ref{ex:numerical example 1}. We here consider choosing a classifier from the following
class of non-decreasing linear functions:
\begin{align*}
\mathcal{F}_{L}=\{f(x)=c_{0}+c_{1}x:c_{0}\in\mathbb{R},\ c_{1}\in\mathbb{R}_{+},\ f(x)\in[-1,1]\mbox{ for all }x\in\mathcal{X}\}.
\end{align*}
Note that the class of prediction sets $\{G_{f}:f\in\mathcal{F}_{L}\}$ agrees with $\mathcal{G}$; hence, $\mathcal{F}_{L}$ is a subclass of $\mathcal{F}_{\mathcal{G}}$. We set $X$ to be uniformly distributed on $\mathcal{X}$, and $Y$ to have conditional probabilities $P(Y=1\mid X=0)=0.6$, $P(Y=1\mid X=1)=0.2$, and $P(Y=1\mid X=2)=0.8$.

The Bayes classifier predicts positive $Y$ at
$x=0$ and $2$. Hence, no classifier in $\mathcal{F}_{L}$ shares the prediction set with the Bayes classifier, and $\mathcal{F}_L$ is $R$-misspecified.

Figure \ref{fig:linear classification} illustrates the computed classifiers, $f^{*}$ and $f_{\phi_h}^{*}$, that minimize the classification and hinge risks, respectively, over $\mathcal{F}_L$.
The optimal classification risk $R(f^{\ast})$ over $\mathcal{F}_{L}$ (equivalently, over $\mathcal{F}_{\mathcal{G}}$ since $\{G_{f}:f\in\mathcal{F}_{L}\}$ agrees with $\mathcal{G}$) is $R(f^{\ast}) = 0.33$ with $G_{f^{\ast}}=\{2\}$, while the classification risk at $f_{\phi_h}^{*}$ is $R(f_{\phi_h}^{\ast}) = 0.54$ with $G_{f_{\phi_h}^{\ast}}=\{2,1\}$. Thus, in contrast to Example \ref{ex:numerical example 1} where $f$ is unconstrained other than via the constraint $G_f \in \mathcal{G}$, adding the linear functional form constraint to $\mathcal{F}_{\mathcal{G}}$ invalidates the calibration property of the hinge risk, and the hinge risk minimization is no longer consistent to the second-best (constrained optimal) classifier in terms of the classification risk.

\bigskip
\begin{figure}[ht]
\caption{Linear monotone classifiers minimizing classification and hinge risks}
\begin{center}
\includegraphics[scale=0.45]{figures/figure_linear_classification.png}
\label{fig:linear classification}
\begin{tablenotes}
\item[] {\footnotesize Note: The orange and blue lines are the graphs of the computed classifiers, $f^{\ast}$ and $f_{\phi_h}^{\ast}$, respectively.}
\end{tablenotes}
\end{center}
\end{figure}

\end{example}



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 \textit{classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$}.

\bigskip{}

\begin{definition}[Classification-preserving reduction]
\label{def:Constrained classification preserving reduction}
Let $\tilde{f}^{\ast} \in \arg\inf_{f \in \widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi_{h}}(f)$. A subclass of classifiers $\widetilde{\mathcal{F}}_{\mathcal{G}}$ $(\subseteq \mathcal{F}_{\mathcal{G}})$ is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$ if
\begin{align*}
    R(\tilde{f}^{\ast}) = \inf_{f \in \mathcal{F}_{\mathcal{G}}}R(f)
\end{align*}
holds for any $P$, distribution on $\{-1,1\}\times \mathcal{X}$.
\end{definition}
\bigskip{}

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:
\begin{equation}
\label{eq:class of step functioins}
\begin{split}
\widetilde{\mathcal{F}}_{\mathcal{G},J}= & \left\{ f(\cdot)=2\sum_{j=1}^{J}c_{j}1\{\cdot\in G_{j}\} -1:
G_{j}\in \mathcal{G}\mbox{ and }c_{j}\geq0\mbox{ for }j=1,\ldots,J; \right.\\
& \quad G_{J}\subseteq\cdots\subseteq G_{1};\ \left. \sum_{j=1}^{J}c_{j}=1 \right\}.
\end{split}
\end{equation}
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
\begin{equation*}
\mathcal{G}^{*}\equiv\arg\inf_{G\in\mathcal{G}}\mathcal{R}(G)
\end{equation*}
be the collection of best prediction sets in $\mathcal{G}$, and
\begin{equation*}
\mathcal{R}^{\ast}\equiv\inf_{G\in\mathcal{G}}\mathcal{R}(G)
\end{equation*}
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}}$.

\bigskip{}

\begin{lemma}\label{lem:step functions}
Let $\mathcal{G} \subseteq 2^{\mathcal{X}}$ be a class of measurable subsets of $\mathcal{X}$. The following two claims hold:
\\
(i) $\widetilde{\mathcal{F}}_{\mathcal{G},J}$  is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$.
\\
(ii) For any distribution $P$ on $\{-1,1\} \times \mathcal{X}$ and $G^{*}\in{\cal G}^{\ast}$,  $\tilde{f}_{G^{\ast}}$ is a minimizer of $R_{\phi_h}(\cdot)$ over $\widetilde{\mathcal{F}}_{\mathcal{G},J}$, and $\inf_{f \in \widetilde{\mathcal{F}}_{\mathcal{G},J}}R_{\phi_h}(f) = 2\mathcal{R}^{\ast}$ holds. \end{lemma}

\begin{proof}
See Appendix \ref{appx:proof 1}.
\end{proof}

\bigskip{}

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{lem:step functions}.

The next theorem is the second main theorem of the paper that extends Lemma \ref{lem:step functions} to a more general class of classifiers that can accommodate continuous ones.
\bigskip{}

\begin{theorem}[Consistency under classification-preserving reduction] \label{thm:continuous functions}
Given a class of measurable subsets $\mathcal{G} \subseteq 2^{\mathcal{X}}$ and $\mathcal{F}_{\mathcal{G}}=\left\{ f:G_{f}\in\mathcal{G},\ f(\cdot)\in[-1,1]\right\}$, suppose $\widetilde{\mathcal{F}}_{\mathcal{G}} \subset \mathcal{F}_{\mathcal{G}}$ satisfies the following two conditions:
\begin{enumerate}[label=(A\arabic*)]
    \item \label{asm:sublevel set condition} For every $f\in\widetilde{\mathcal{F}}_{\mathcal{G}}$, $\{x\in\mathcal{X}:f(x)\leq t\}\in\mathcal{G}$ for all $t\in[-1,1]$;
    \item \label{asm:optimizer condition} For any $G \in \mathcal{G}$, $\tilde{f}_{G}\in\widetilde{\mathcal{F}}_{\mathcal{G}}$.
\end{enumerate}
Then the following claims hold:\\
(i) $\widetilde{\mathcal{F}}_{\mathcal{G}}$ is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}}$;
\\
(ii) For any distribution $P$ on $\{-1,1\}\times \mathcal{X}$ and $G^{*}\in{\cal G}^{\ast}$,  $\tilde{f}_{G^{\ast}}$ is a minimizer of $R_{\phi_h}(\cdot)$ over $\widetilde{\mathcal{F}}_{\mathcal{G}}$, and $\inf_{f \in \widetilde{\mathcal{F}}_{\mathcal{G}} }R_{\phi_h}(f) = 2 \mathcal{R}^{\ast}$ holds.
\end{theorem}

\begin{proof}
See Appendix \ref{appx:proof 1}.
\end{proof}
\bigskip{}


The theorem establishes that the two conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} 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{ex:Linear classification with a class of transformed logistic functions} and \ref{example:Monotonic classification with a class of monotonic functions} at the end of this section give examples of classification-preserving reductions for linear classification and monotone classification.

The conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions}  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{sec:Applications to monotone classification}, 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{thm:continuous functions} shows the consistency of the hinge risk minimization over $\widetilde{\mathcal{F}}_{\mathcal{G}}$, it does not lead to the generalized \citeauthor{Zhang_2004}'s (\citeyear{Zhang_2004}) inequality in Corollary \ref{corr:zhang's inequality}. 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.

\bigskip{}

\begin{corollary}\label{cor:zhang's ineuality for admissible refinement}
Assume $\widetilde{\mathcal{F}}_{\mathcal{G}}$ is a subclass of $\mathcal{F}_{\mathcal{G}}$ satisfying conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions}. If $\Delta C_{\phi}(\eta) = c(1- 2 \eta)$ holds for some $c>0$ and any $\eta \in [0,1]$,
\begin{align}
c(R(f)-\inf_{f\in \mathcal{F}_{\mathcal{G}}} R(f)) = \frac{1}{2}\left(R_{\phi}(f)-\inf_{f\in\widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi}(f)\right)
+ \frac{1}{2}\left(R_{\phi}(\tilde{f}_{G_f}) - R_{\phi}(f) \right)
\label{eq:zhang's inequality}
\end{align}
for any classifier $f:\mathcal{X} \mapsto [-1,1]$. Moreover, the following holds:
\begin{align}
c(R(f)-\inf_{f\in \mathcal{F}_{\mathcal{G}}} R(f)) \leq  \frac{1}{2}\left(R_{\phi}(f)-\inf_{f\in\widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi}(f)\right)
+ \frac{1}{2}\left(R_{\phi}(f)-\inf_{f\in \mathcal{F}_\mathcal{G} }R_{\phi}(f)\right) \label{eq:zhang's inequality_average excess risks}
\end{align}
for any $f \in \mathcal{F}_\mathcal{G}$.
\end{corollary}

\begin{proof}
See Appendix \ref{appx:proof 1}.
\end{proof}
\bigskip{}


The extra term (the right-most term) in (\ref{eq:zhang's inequality}) 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{thm:continuous functions} (ii)), if $f$ closely approximates such a classifier, the extra term is close to zero.
In the following section, we use equation (\ref{eq:zhang's inequality}) to derive the statistical properties of the hinge risk minimization in terms of the $\mathcal{G}$-constrained excess classification risk. Equation (\ref{eq:zhang's inequality_average excess risks}) 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{corr:zhang's inequality}.

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

\bigskip{}

\begin{example}[Linear classification with a class of transformed logistic functions]
\label{ex:Linear classification with a class of transformed logistic functions}
Suppose that the prediction sets are subject to the linear index rules:
\begin{equation*}
    \mathcal{G}_L=\{x\in\mathbb{R}^{d_x}:x^{T}\beta\geq0:\beta\in\mathbb{R}^{d_{x}}\},
\end{equation*}
where $\mathcal{X}=\mathbb{R}^{d_x}$. Let $\pi(\alpha,k)\equiv(1-e^{-k\alpha})/(1+e^{-k\alpha})=2/(1+e^{-k\alpha})-1$
be a transformed logistic function and define a class of classifiers
\begin{align}
\mathcal{F}_{Logit}=\{\pi(x^{T}\beta,k):\beta\in\mathbb{R}^{d_x}\mbox{ and }k\in\mathbb{R}_{+}\},\nonumber
\end{align}
where $k$ is a tuning parameter that determines the steepness of the logistic curve. $\mathcal{F}_{Logit}$ satisfies the condition (\hyperlink{sublevel set condition}{A1}) in Theorem \ref{thm:continuous functions}.\footnote{Fix $\beta\in\mathbb{R}^{d_x}$ and $k\in\mathbb{R}_{+}$. The condition
\ref{asm:sublevel set condition} is satisfied as, for any $t\in[-1,1]$,
$\{x:\pi(x^{T}\beta,k)\leq t\}=\{x:x^{T}\beta\leq\pi^{-1}(t,k)\}\in\mathcal{G}$,
where $\pi^{-1}(\cdot,k)$ is an inverse function of $\pi(\cdot,k)$
with fixed $k$.} Since $\mathcal{F}_{Logit}$ for fixed $k < \infty$ rules out any step functions, the condition \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions} is not exactly met. Fix $G \in \mathcal{G}$, and let $\tilde{\beta}$ be such that $\{x\in\mathcal{X}:x^{T}\tilde{\beta}\geq0\}=G$.
Then, as $k\rightarrow\infty$, $\pi(x^{T}\tilde{\beta},k)$ approximates
$\mathrm{sign}(x^{T}\tilde{\beta})$, so the condition \ref{asm:optimizer condition} is approximately met for large $k$. Every function in $\mathcal{F}_{Logit}$ is smooth and depends on a finite number of parameters. Hence, the empirical hinge risk  becomes a smooth and continuous function with a finite number of parameters, although it is not generally convex.
\end{example}

\bigskip{}

\begin{example}[Monotonic
classification with a class of monotone functions]
\label{example:Monotonic classification with a class of monotonic functions} Hinge risk
minimization embedding a monotonicity restriction remains consistent when we use a class of monotone functions. Let $\precsim$ be a partial order on $\mathcal{X}$, and let $\mathcal{G}_{\precsim}$ be the collection of all $G\in2^{\mathcal{X}}$ that respect monotonicty (i.e., if $x_{1}\precsim x_{2}$ and $x_{1}\in G$, then $x_{2}\in G$).
Define $\widetilde{\mathcal{F}}_{\mathcal{G}_{\precsim}}$ as a class of functions $f:\mathcal{X}\rightarrow[-1,1]$ that are weakly monotonic
in $\precsim$ (i.e., satisfying $f(x_{1})\leq f(x_{2})$ if $x_{1}\precsim x_{2}$). Then the prediction set of any $f\in\widetilde{\mathcal{F}}_{\mathcal{G}_{\precsim}}$ respects the partial order $\precsim$ (i.e., if $x_{1}\precsim x_{2}$ and $x_{1}\in G_{f}$, then $x_{2}\in G_{f}$).
For any $t\in[-1,1]$ and $f\in\widetilde{\mathcal{F}}_{\precsim}$, $\{x:f(x)\leq t\}=\{x:x\precsim\tilde{x}\mbox{ for any }\tilde{x}\mbox{ such that }f(\tilde{x})=t\}\in\mathcal{G}_{\precsim}$ holds,
satisfying condition \ref{asm:sublevel set condition} in Theorem \ref{thm:continuous functions}.
In addition, for any $G\in\mathcal{G}_{\precsim}$, since $\tilde{f}_{G}(x)=2\cdot1\{x\in G\}$
is weakly monotonic in $\precsim$, $\tilde{f}_{G} \in\mathcal{G}_{\precsim}$
holds, satisfying condition \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions}. Hence $\widetilde{\mathcal{F}}_{\mathcal{G}_{\precsim}}$
is a classification-preserving reduction of $\mathcal{F}_{\mathcal{G}_{\precsim}}$. Therefore, according to Theorem \ref{thm:continuous functions},
hinge risk minimization over $\widetilde{\mathcal{F}}_{\precsim}$ yields the optimal classifier in terms of the classification risk. Section \ref{sec:Applications to monotone classification} focuses on monotone classification and investigates its statistical and computational properties.
\end{example}



\section{Statistical properties}
\label{sec:statistical property}

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{thm:risk equivalence} and \ref{thm:continuous functions} 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{thm:risk equivalence} and \ref{thm:continuous functions} 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
\begin{align*}
\hat{R}(f)&\equiv  \frac{1}{n}\sum_{i=1}^{n}1\left\{ Y_{i} \cdot \text{sign} (f\left(X_{i}\right) ) \leq0\right\} ,\\
\hat{R}_{\phi_{h}}(f)&\equiv \frac{1}{n}\sum_{i=1}^{n}\max\{0,1-Y_{i}f\left(X_{i}\right)\} = \frac{1}{n}\sum_{i=1}^{n}\left(1-Y_{i}f\left(X_{i}\right) \right),
\end{align*}
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{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions}. $\widetilde{\mathcal{F}}_\mathcal{G}$ is a
classification-preserving reduction of $\mathcal{F}_\mathcal{G}$ (Definition \ref{def:Constrained classification preserving reduction}). Following  Corollary \ref{cor:zhang's ineuality for admissible refinement}, we have
\begin{align}
R(\hat{f})-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f)= \frac{1}{2}\left(R_{\phi_h}(\hat{f})-\inf_{f\in\widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi_h}(f)\right)
+\frac{1}{2}\left(R_{\phi_h} \left( \tilde{f}_{G_{\hat{f}}} \right) -R_{\phi_h}(\hat{f})\right).
\label{eq:excess risk decomposition}
\end{align}
When $\Check{\mathcal{F}}=\widetilde{\mathcal{F}}_\mathcal{G}$, evaluating each term on the right hand side of (\ref{eq:excess risk decomposition}) 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{def:bracketing entropy} in Appendix \ref{appx:proof 2}. 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.

\bigskip

\begin{theorem}\label{thm:statistical propery for excess classification risk}
Let $\widetilde{\mathcal{F}}_\mathcal{G}$ be a subclass of $\mathcal{F}_{\mathcal{G}}$ that satisfies conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions}.
Suppose that $\mathcal{P}$ is a class of distributions on $\{-1,1\}\times \mathcal{X}$ such that there exist positive constants $C$ and $r$ for which
\begin{align}
H_{1}^{B}\left(\epsilon,\mathcal{G},P_{X}\right) \leq C\epsilon^{-r} \label{eq:bracketing entoropy conditoin_G}
\end{align}
holds for any $P \in \mathcal{P}$ and $\epsilon>0$, or
\begin{align}
H_{1}^{B}\left(\epsilon,\widetilde{\mathcal{F}}_{\mathcal{G}},P_{X}\right) \leq C\epsilon^{-r} \label{eq:bracketing entoropy conditoin_tildeF}
\end{align}
holds for any $P \in \mathcal{P}$ and $\epsilon>0$.
Define $\tau_{n}=n^{-1/2}$ if $r<1$, $\tau_{n}=\log\left(n\right)/\sqrt{n}$ if $r=1$, and
$\tau_{n}=n^{-1/\left(r+1\right)}$ if $r\geq2$. Let $q_{n}=\sqrt{n}\tau_{n}$.
Then, for $\hat{f} \in \arg\inf_{f \in \widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi_h}(f)$, the following holds:
\begin{align}
\sup_{P\in\mathcal{P}}E_{P^{n}}\left[R(\hat{f})-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f)\right]\leq  L_{C}(r,n), \label{eq:upper bound_statistical property_admissible refinement}
\end{align}
where
\begin{align}
    L_{C}(r,n)	=\begin{cases}
\begin{array}{c}
2D_{1}\tau_{n}+4D_{2}\exp\left(-D_{1}^{2}q_{n}^{2}\right)\\
2D_{3}\tau_{n}+2n^{-1}D_{4}
\end{array} & \begin{array}{l}
\mbox{if }r\geq1\\
\mbox{if }r<1
\end{array}\end{cases}
\nonumber
\end{align}
for some positive constants $D_{1}, D_{2}, D_{3}, D_{4}$, which depend only on $C$ and $r$.
\end{theorem}

\begin{proof}
See Appendix \ref{appx:proof 2}.
\end{proof}

\bigskip

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{eq:bracketing entoropy conditoin_G}) and (\ref{eq:bracketing entoropy conditoin_tildeF}).
\cite{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{example:Monotonic classification with a class of monotonic functions} satisfies condition (\ref{eq:bracketing entoropy conditoin_G}) with $r$ equal to $d_x-1$ (see Theorem 8.3.2 in \cite{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{eq:excess risk decomposition})
leads to
\begin{align}
R(\hat{f})-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f) & =  \frac{1}{2}\left(R_{\phi_{h}}(\hat{f})-\inf_{f\in \Check{\mathcal{F}}}R_{\phi_h}(f)\right)+\frac{1}{2}\left(\inf_{f\in \Check{\mathcal{F}}}R_{\phi_h}(f)-\inf_{f\in\widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi_h}(f)\right) \notag \\
 & +\frac{1}{2}\left(R_{\phi_h} (\tilde{f}_{G_{\hat{f}}})-R_{\phi_h}(\hat{f})\right).
\label{eq:decomposition}
\end{align}
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.

\bigskip{}

\begin{theorem}\label{thm:statistical propery for excess classification risk_2}
Let $\widetilde{\mathcal{F}}_\mathcal{G}$ be a subclass of $\mathcal{F}_{\mathcal{G}}$ that satisfies conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions}.
Suppose that $\mathcal{P}$ is a class of distributions on $\{-1,1\} \times \mathcal{X}$ such that there exist positive constants $C^{\prime}$ and $r^{\prime}$ for which
\begin{align}
H_{1}^{B}\left(\epsilon,\Check{\mathcal{F}},P_{X}\right) \leq C^{\prime}\epsilon^{-r^{\prime}} \label{eq:bracketing entoropy conditoin}
\end{align}
holds for any $P \in \mathcal{P}$ and $\epsilon>0$.
Let $\hat{f} \in \arg \inf_{f \in \Check{\mathcal{F}}}R_{\phi_h}(f)$.
Then
\begin{align}
\sup_{P\in\mathcal{P}}E_{P^{n}}\left[R(\hat{f})-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R(f)\right] & \leq
L_{C^{\prime}}(r^{\prime},n) + \frac{1}{2}\left(\inf_{f\in \Check{\mathcal{F}}}R_{\phi_{h}}(f)-\inf_{f\in\widetilde{\mathcal{F}}_{\mathcal{G}}}R_{\phi_{h}}(f)\right) \nonumber \\
 & + \frac{1}{2} \left( R_{\phi_{h}} ( \tilde{f}_{G_{\hat{f}}})-R_{\phi_{h}}(\hat{f})\right), \label{eq:upper bound_statistical propery}
\end{align}
where $L_{C^\prime}(r^\prime,n)$ is as defined in Theorem \ref{thm:statistical propery for excess classification risk}.
\end{theorem}

\begin{proof}
See Appendix \ref{appx:proof 2}.
\end{proof}

\bigskip{}

\begin{remark}[Approximation errors]\label{rem:approximation error}
Evaluating each approximation error (the final two terms on the right-hand side) in (\ref{eq:upper bound_statistical propery}) depends on the functional form restriction placed on $f \in \Check{\mathcal{F}}$.
If $\Check{\mathcal{F}}$ grows and approaches $\widetilde{\mathcal{F}}_\mathcal{G}$ as $n \to \infty$,
each approximation error converges to zero.
In Section \ref{sec:Monotone classification with Bernstein polynomial} below, where we consider the monotone classification problem and set $\Check{\mathcal{F}}$ being a sieve of Bernstein polynomials, we characterize convergence of these two approximation errors. We then apply Theorem \ref{thm:statistical propery for excess classification risk_2} to obtain the regret convergence rate of the estimated monotone classifier.
\end{remark}





\section{Applications to monotone classification}
\label{sec:Applications to monotone classification}

This section applies the general theoretical results shown in Sections \ref{sec:calibration of MG-constrained classification}--\ref{sec:statistical property} to the monotone classification problem (Example \ref{exm:monotone classification}). By Theorem \ref{thm:risk equivalence}, 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
\begin{align*}
\mathcal{F}_{M} \equiv & \left\{ f:f(x)\leq f\left(\tilde{x}\right)\mbox{ for any \ensuremath{x,\tilde{x}\in\mathcal{X}} with \ensuremath{x\leq\tilde{x}} }; f(\cdot) \in [-1,1]\right\}.
\end{align*}

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{example:Monotonic classification with a class of monotonic functions}).
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.


\subsection{Nonparametric monotone classification}

\label{sec: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:
\begin{align}
&\max_{f_{1},\ldots,f_{n}}	\sum_{i=1}^{n}Y_{i}f_{i} \label{eq:LP_monotone classification}\\
\mbox{s.t.}& \quad	f_{i}\geq f_{j}\mbox{ for any }X_{i}\neq X_{j}\mbox{ with }X_{i}\geq X_{j}\mbox{ for }1\leq i\leq j\leq n; \notag \\
& \quad	-1\leq f_{i}\leq1\mbox{ for }1\leq i\leq n, \notag
\end{align}
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{eq:LP_monotone classification}).
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{thm:continuous functions} with $P$ replaced by $P^n$ shows that any solution to (\ref{eq:LP_monotone classification}) 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{thm:statistical propery for excess classification risk}.
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 \cite{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.

\bigskip{}

\begin{lemma} \label{lemma:bracketing entropy_monotone G}
Suppose that $P_{X}$ is absolutely continuous with respect to the Lebesgue measure on $\mathcal{X}$ and has a density that is bounded from above by a finite constant $A>0$. Then there exists a constant $C$, which depends only on $A$, such that
\begin{align*}
H_{1}^{B}\left(\epsilon,\mathcal{G}_{M},P_{X}\right) \leq C\epsilon^{1-d_x}.
\end{align*}
holds for all $\epsilon>0$.
\end{lemma}

\begin{proof}
See Appendix \ref{appx:proof 3}.
\end{proof}

\bigskip{}



With this lemma to hand, setting $r= 1 - d_x$ in Theorem \ref{thm:statistical propery for excess classification risk} 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{eq:LP_monotone classification}) attains the same convergence rate as the welfare regret of monotone treatment rules shown by \cite{MT17}.

\bigskip{}

\begin{theorem} \label{thm:nonparametric monotone classifiation}
Let $\mathcal{P}$ be a class of distributions on $\{-1,1\}\times\mathcal{X}$
such that the marginal distribution $P_{X}$ is absolutely continuous
with respect to the Lebesgue measure on $\mathcal{X}$ and has a density that
is bounded from above by some finite constant $A>0$. Define $\tau_n=n^{-1/2}$ if $d_x=1$,
$\tau_{n}=\log\left(n\right)/\sqrt{n}$ if $d_x=2$, and $\tau_{n}=n^{-1/d_x}$ if $d_x\geq3$. Let $q_n=\sqrt{n}\tau_n$. Then, for $\hat{f}_{M} \in \arg\inf_{f\in \mathcal{F}_M}\hat{R}_{\phi_{h}}(f)$,
\begin{align}
\sup_{P\in\mathcal{P}}E_{P^{n}}\left[R(\hat{f}_{M})-\inf_{f\in\mathcal{F}_{\mathcal{G}_{M}}}R(f)\right]  \leq \begin{cases}
\begin{array}{c}
2D_{1}\tau_{n}+4D_{2}\exp\left(-D_{1}^{2}q_{n}^{2}\right)\\
2D_{3}\tau_{n}+2n^{-1}D_{4}
\end{array}  \begin{array}{l}
\mbox{if }d_x \geq 2\\
\mbox{if }d_x = 1
\end{array}\end{cases}\label{eq:regret bound_nonparametric monotone classification} \notag
\end{align}
for some positive constants $D_1, D_2, D_3 ,D_4$, which depend only on $d_x$ and $A$.
\end{theorem}

\begin{proof}
Since $\mathcal{F}_M$ satisfies conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions} with $\mathcal{G}$ equal to $\mathcal{G}_M$ (Example \ref{example:Monotonic classification with a class of monotonic functions}), the result follows from Theorem \ref{thm:statistical propery for excess classification risk} and Lemma \ref{lemma:bracketing entropy_monotone G}.
\end{proof}

\bigskip{}

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$.


\subsection{Monotone classification with Bernstein polynomials}
\label{sec:Monotone classification with Bernstein polynomial}

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(\begin{array}{c}
k\\
j
\end{array}\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:
\begin{align*}
B_{\mathbf{k}}\left(\theta,x\right)= & \sum_{j_{1}=0}^{k_{1}}\cdots\sum_{j_{d_x}=0}^{k_{d_x}}\theta_{j_{1}\ldots j_{d}}\cdot \left(b_{k_{1}j_{1}}\left(x_1\right) \times \cdots \times b_{k_{d_{x}}j_{d_{x}}}\left(x_{d_x}\right) \right),
\end{align*}
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., \citet{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
\begin{align*}
\mathcal{B}_{\mathbf{k}}= & \left\{ B_{\mathbf{k}}\left(\theta,\cdot\right):\theta \in\widetilde{\Theta}\right\} ,
\end{align*}
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{thm:continuous functions}), we propose approximating such a step function using the sieve of Bernstein polynomials. To this end, we propose the following two steps:
\begin{enumerate}
    \item Minimize the empirical hinge risk $\hat{R}_{\phi_h}(f)$ over $f \in \mathcal{B}_{\mathbf{k}}$ and obtain $\hat{f}_B \in \arg\inf_{f \in \mathcal{B}_{\mathbf{k}}}\hat{R}_{\phi_h}(f)$.
    \item Let $\{\hat{\theta}_{j_1\ldots j_{d_{x}}}\}_{j_1=0,\ldots,k_1;\cdots;j_{d_x}=0,\ldots,k_{d_x}}$ be the vector of coefficients in $\hat{f}_B$. Compute a modified classifier
\begin{align*}
    \hat{f}_{B}^{\dagger}(x)\equiv \sum_{j_{1}=1}^{k_{1}}\cdots\sum_{j_{d_{x}=1}}^{k_{d_{x}}}\mathrm{sign}\left(\hat{\theta}_{j_{1}\ldots j_{d_{x}}}\right)\cdot\left(b_{k_{1}j_{1}}\left(x_{1}\right)\times\cdots\times b_{k_{d_{x}}j_{d_{x}}}\left(x_{d_x}\right)\right),
\end{align*}
which converts each estimated coefficient $\hat{\theta}_{j_1\ldots j_{d_x}}$ to either $-1$ or $1$ depending on its sign.
\end{enumerate}

Our proposal is to use $\hat{f}_{B}^{\dagger}$ rather than $\hat{f}_B$. Lemma \ref{lem:step function approximation optimality_Bernstein polynomial} in Appendix \ref{appx:proof 3} 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:
\begin{equation}
\label{eq:LP_bernstein polynomial}
\begin{split}
    & \max_{\theta}	\sum_{i=1}^{n}Y_{i}\cdot \left(\sum_{j_{1}=0}^{k_{1}}\cdots\sum_{j_{1}=d_{x}}^{k_{d_{x}}}\theta_{j_{1}\ldots j_{d_{x}}}\cdot\left(b_{k_{1}j_{1}}\left(X_{i1}\right)\times\cdots\times b_{k_{d_{x}}j_{d_{x}}}\left(X_{id_{x}}\right)\right)\right) \\
\mbox{s.t.}& \quad	\theta_{j_{1}\ldots j_{d_{x}}}\geq\theta_{\tilde{j}_{1}\ldots\tilde{j}_{d_{x}}}\mbox{ for any }\left(j_{1},\ldots,j_{d_{x}}\right)\geq\left(\tilde{j}_{1},\ldots,\tilde{j}_{d_{x}}\right); \\
&\quad	-1\leq\theta_{j_{1}\ldots j_{d_{x}}}\leq1\mbox{ for all }\left(j_{1},\ldots,j_{d_{x}}\right),
\end{split}
\end{equation}
where $X_{ij}$ denotes the $j$-th element of $X_i$.\footnote{The linear program in (\ref{eq:LP_monotone classification}) for the nonparametric monotone classification problem has $n$-decision variables, whereas the linear program in (\ref{eq:LP_bernstein polynomial}) 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{thm:statistical propery for excess classification risk_2} with $\Check{F} = \mathcal{B}_{\mathbf{k}}$.
Lemma \ref{lem:berstein approximation error} in Appendix \ref{appx:proof 3} gives finite upper bounds on two approximation errors:
\begin{align*}
    \inf_{f \in \mathcal{B}_{\mathbf{k}}}R_{\phi_h}(f) - \inf_{f \in \mathcal{F}_M}R_{\phi_h}(f) \mbox{ and } R_{\phi_h}(1\{\cdot \in G_{\hat{f}_{B}^{\dagger}}\} - 1\{\cdot \notin G_{\hat{f}_{B}^{\dagger}}\})
    - R_{\phi_h}(\hat{f}_{B}^{\dagger})
\end{align*}
in (\ref{eq:upper bound_statistical propery}) 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{lemma:bracketing entropy_monotone function} in Appendix \ref{appx:proof 3} 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}$.



\bigskip{}

\begin{theorem} \label{thm:berstein polynomial approximation}
Let $\mathcal{P}$ be a class of distributions on $\{-1,1\}\times\mathcal{X}$ that satisfy the same conditions as in Theorem \ref{thm:nonparametric monotone classifiation}.
Let $\tilde{\tau}_{n}=\log\left(n\right)/\sqrt{n}$ if $d_x=1$ and $\tilde{\tau}_{n}=n^{-1/d_x}$ if $d_x\geq2$. Define $\tilde{q}_n=\sqrt{n}\tilde{\tau}_n$. Then the following holds:
\begin{align}
\sup_{P\in \mathcal{P}}E_{P^{n}}\left[R(\hat{f}_{B}^{\dagger})-\inf_{f\in\mathcal{F}_{\mathcal{G}_{M}}}R(f)\right] & \leq   2D_{1}\tilde{\tau}_{n}+4D_{2}\exp\left(-D_{1}^{2}\tilde{q}_{n}^{2}\right) \notag \\
 & + 4A\sum_{j=1}^{d_x}\sqrt{\frac{\log k_{j}}{k_{j}}}+\sum_{j=1}^{d_x}\frac{8}{\sqrt{k_{j}}},  \label{eq:regret bound_berstein monotone classification}
\end{align}
where $D_{1}$ and $D_{2}$ are some positive constants, which depend only on $d_x$ and $A$.
\end{theorem}

\begin{proof}
From the fact that $\mathcal{B}_\mathbf{k} \subseteq \mathcal{F}_M$ and Lemma \ref{lemma:bracketing entropy_monotone function} in Appendix \ref{appx:proof 3}, we have $H_{1}^{B}(\epsilon, \mathcal{B}_{\mathbf{k}},P_X) \leq C \epsilon^{-d_x}$ for some positive constant $C$, which depends only on $A$, and all $\epsilon>0$ .
Then the result follows by combining Theorem \ref{thm:statistical propery for excess classification risk_2} and Lemma \ref{lem:berstein approximation error}.
\end{proof}

\bigskip{}

The upper bound in (\ref{eq:regret bound_berstein monotone classification}) 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{thm:nonparametric monotone classifiation}, $\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{lemma:bracketing entropy_monotone G} and \ref{lemma:bracketing entropy_monotone function}.
To achieve the convergence rate of $\tilde{\tau}_n$ for the mean of the excess risk of $\hat{f}_{B}^{\dagger}$, Theorem  \ref{thm:berstein polynomial approximation}  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 (\citet{Koltchinskii_2006}, \citet{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.



\section{Extension to individualized treatment rules}
\label{sec:Extension to individualized treatment rules}

This section extends the primary results obtained in Sections \ref{sec:calibration of MG-constrained classification} and \ref{sec:classification preserving reduction} for binary classification to the weighted classification introduced in Section \ref{sec:Connection and contributions to causal policy learning}, and to causal policy learning. Extensions of the results in Sections \ref{sec:statistical property} and \ref{sec:Applications to monotone classification} to weighted classification are presented in Appendix \ref{appx:weighted classification}.
We use the same notation and definitions as those introduced in Section \ref{sec:Connection and contributions to causal policy learning}. We term $R^{\omega}$ and $R_{\phi}^{\omega}$, defined in (\ref{eq:weighted_classification_risk}) and (\ref{eq:weighted_surrogate_risk}), 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$.



\subsection{Consistency of weighted classification with hinge loss}
\label{sec:Consistency of the weighted classification with hinge loss}

We first show consistency of weighted classification with hinge risk by adapting the analyses in Sections \ref{sec:calibration of MG-constrained classification} and \ref{sec:classification preserving reduction}. Given a prespecified $\mathcal{G}$, let $\mathcal{F}_\mathcal{G}$ be as in Section \ref{sec:constrained classification and surrogate loss approach}. 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
\begin{align*}
    \omega_{+}(x) & \equiv E_{P}\left[\omega\mid X=x,Y=+1\right] \\
    \omega_{-}(x) & \equiv E_{P}\left[\omega\mid X=x,Y=-1\right].
\end{align*}
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
\begin{align*}
C_{\phi}^{w+}\left(\omega_{+},\omega_{-},\eta\right)&\equiv  \underset{0\leq f\leq1}{\inf}C_{\phi}\left(\omega_{+},\omega_{-},f,\eta\right),\\
C_{\phi}^{w-}\left(\omega_{+},\omega_{-},\eta\right)&\equiv  \underset{-1\leq f<0}{\inf}C_{\phi}\left(\omega_{+},\omega_{-},f,\eta\right),\\
\Delta C_{\phi}^{\omega}\left(\omega_{+},\omega_{-},\eta\right)&\equiv  C_{\phi}^{w+}\left(\omega_{+},\omega_{-},\eta\right)
  -C_{\phi}^{w-}\left(\omega_{+},\omega_{-},\eta\right),
\end{align*}
which are analogous to $C_{\phi}^{+}$, $C_{\phi}^{-}$ and $\Delta C_{\phi}$
defined in Section \ref{sec:calibration of MG-constrained classification}.

The next theorem generalizes Theorems \ref{thm:risk equivalence}, \ref{thm:univesal equivalence}, and Corollary \ref{corr:universally equivalence} 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.

\bigskip{}

\begin{theorem}\label{thm:risk equivalence_WC}
Let $\phi_{1}$ and $\phi_{2}$ be classification-calibrated loss functions in the sense of Definition \ref{def:classification-calibrated loss functions}. Then
\begin{align}
\mathcal{R}^{\omega}_{\phi_{1}}\left(G_{1}\right)\leq \mathcal{R}^{\omega}_{\phi_{1}}\left(G_{2}\right) & \Leftrightarrow \mathcal{R}^{\omega}_{\phi_{2}}\left(G_{1}\right)\leq \mathcal{R}^{\omega}_{\phi_{2}}\left(G_{2}\right)
\nonumber
\end{align}
holds for any distribution $P$ on $\mathbb{R}_{+}\times \{-1,1\} \times \mathcal{X}$, any class of measurable subsets $\mathcal{G} \subseteq 2^{\mathcal{X}}$, and any $G_1,G_2 \in \mathcal{G}$ if and only if there exists $c>0$ such that $\Delta C_{\phi_{2}}^{\omega}\left(\omega_{+},\omega_{-},\eta\right)=c\Delta C_{\phi_{1}}^{\omega}\left(\omega_{+},\omega_{-},\eta\right)$ holds
for any $(\omega_{+},\omega_{-},\eta)\in \mathbb{R}_{+} \times \mathbb{R}_{+} \times \left[0,1\right]$. In particular, the 0-1 loss function, $\phi_{01}(\alpha) = 1\{\alpha \leq 0\}$, satisfies
\begin{align}
    \Delta C_{\phi_{01}}^{\omega}\left(\omega_{+},\omega_{-},\eta\right)=-\omega_{+}\eta+\omega_{-}\left(1-\eta\right), \label{eq:conditon_risk equivalence_WC}
\end{align}
and the hinge loss function $\phi_{h}(\alpha) = c \max\{0,1-\alpha\}$ satisfies
\begin{equation}
    \Delta C_{\phi_{h}}^{\omega}\left(\omega_{+},\omega_{-},\eta\right)=c\left(-\omega_{+}\eta+\omega_{-}\left(1-\eta\right) \right) = c \Delta C_{\phi_{01}}^{\omega}\left(\omega_{+},\omega_{-},\eta\right).\notag
\end{equation}

\end{theorem}

\begin{proof}
See Appendix \ref{appx:proof 4}.
\end{proof}

\bigskip{}




Theorem \ref{thm:risk equivalence_WC} and inequalities similar to (\ref{eq:generalized zhang's ineq}) lead to a generalized \citeauthor{Zhang_2004}'s \citeyearpar{Zhang_2004} inequality for weighted classification, as shown in the next corollary.

\bigskip{}

\begin{corollary}\label{cor:zhang's inequality_WC}
For any distribution $P$ on $\mathbb{R}_{+}\times \{-1,1\} \times \mathcal{X}$ and any surrogate loss function $\phi$ satisfying $\Delta C_{\phi}^{\omega}\left(\omega_{+},\omega_{-},\eta\right)=c\left(-\omega_{+}\eta+\omega_{-}\left(1-\eta\right) \right)$,
\begin{align}
c(R^{\omega}(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R^{\omega}(f))\leq R_{\phi}^{\omega}(f)-\inf_{f\in\mathcal{F}_{\mathcal{G}}}R_{\phi}^{\omega}(f) \label{eq:zhangs inequality_WC}
\end{align}
holds for any $f\in\mathcal{F}_{\mathcal{G}}$.
\end{corollary}

\begin{proof}
See Appendix \ref{appx:proof 4}.
\end{proof}

\bigskip{}

\begin{remark} Table \ref{tb:surrogate loss functions and their forms of H_WC}
shows the forms of $\Delta C_{\phi}^{\omega}(\omega_+,\omega_-,\eta)$ for the hinge loss, exponential loss, logistic
loss, quadratic loss, and truncated quadratic loss functions, where $\mu_+ \equiv \omega_+ \eta$ and $\mu_- \equiv \omega_- (1-\eta)$. With the exception of the hinge loss function, none of these functions satisfy $\Delta C_{\phi}^{\omega}(\omega_+,\omega_-,\eta) = c(-\mu_{+} + \mu_{-})$ for some positive constant $c>0$.
That is, similar to the standard binary classification, hinge losses also have a special status in weighted classification, since they are the only surrogate losses that preserve classification risk.


\begin{table}[h]
\centering \caption{Surrogate loss functions and their associated forms for $\Delta C_{\phi}^w$}
\label{tb:surrogate loss functions and their forms of H_WC}
\begin{threeparttable}[h]
\scalebox{0.9}{
\begin{tabular}{c:c:c}
\hline
Loss function  & $\phi(\alpha)$  & $\Delta C_{\phi}^{\omega}\left(\omega_+,\omega_-,\eta\right)$
\tabularnewline
\hline
0-1 loss  & $1\{\alpha\leq0\}$  & $-\mu_+ + \mu_-$\tabularnewline
\hdashline
Hinge loss  & $c \max\{0,1-\alpha\}$  & $c\left(-\mu_+ + \mu_-\right)$\tabularnewline
\hdashline
Exponential loss  & $e^{-\alpha}$  & $\begin{cases}
\begin{array}{c}
 (\sqrt{\mu_+} - \sqrt{\mu_-})^2\\
-(\sqrt{\mu_+} - \sqrt{\mu_-})^2
\end{array} & \begin{array}{l}
\mbox{if } \mu_+ \leq \mu_-\\
\mbox{if }\mu_+ > \mu_-
\end{array}\end{cases}$\tabularnewline
\hdashline
Logistic loss  & $\log(1+e^{-\alpha})$  & $\begin{cases}
\begin{array}{c}
-\mu_+ \log\left(\frac{2\mu_+}{\mu_+ + \mu_-}\right)
- \mu_- \log\left(\frac{2\mu_-}{\mu_+ + \mu_-}\right) \\
\mu_+ \log\left(\frac{2\mu_+}{\mu_+ + \mu_-}\right)
+ \mu_- \log\left(\frac{2\mu_-}{\mu_+ + \mu_-}\right)
\end{array} &
\begin{array}{l}
\mbox{if } \mu_+ \leq \mu_-\\
\mbox{if }\mu_+ > \mu_-
\end{array}\end{cases}$\tabularnewline
\hdashline
Quadratic loss  & $(1-\alpha)^{2}$  & $\begin{cases}
\begin{array}{c}
\frac{(\mu_+ - \mu_-)^{2}}{\mu_+ + \mu_-}\\
-\frac{(\mu_+ - \mu_-)^{2}}{\mu_+ + \mu_-}
\end{array} & \begin{array}{l}
\mbox{if } \mu_+ \leq \mu_-\\
\mbox{if } \mu_+ > \mu_-
\end{array}\end{cases}$\tabularnewline
\hdashline
Truncated quadratic loss  & $(\max\{0,1-\alpha\})^{2}$  & $\begin{cases}
\begin{array}{c}
\frac{(\mu_+ - \mu_-)^{2}}{\mu_+ + \mu_-}\\
-\frac{(\mu_+ - \mu_-)^{2}}{\mu_+ + \mu_-}
\end{array} & \begin{array}{l}
\mbox{if } \mu_+ \leq \mu_-\\
\mbox{if } \mu_+ > \mu_-
\end{array}\end{cases}$\tabularnewline
\hline
\end{tabular}
}
\begin{tablenotes}\footnotesize
\item[]Note: $\mu_+ = \omega_+ \eta$ and $\mu_- = \omega_- (1-\eta)$.
\end{tablenotes}
\end{threeparttable}
\end{table}

\end{remark}

\bigskip{}

Similar to the analysis in Section \ref{sec:classification preserving reduction}, 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.

\bigskip{}
\begin{condition}[Bounded weight variable]\label{con:bounded weight variable}
There exists $M<\infty$ such that $0 \leq \omega \leq M$ a.s.
\end{condition}
\bigskip{}

In causal policy learning, Condition \ref{con:bounded weight variable} 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{eq:policy_learning_welfare}) is bounded from above by $\tilde{M}/\kappa$ a.s.

The following theorem, which is analogous to Theorem \ref{thm:continuous functions}, shows that
the two conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions} remain sufficient for $\widetilde{\mathcal{F}}_\mathcal{G}$ to guarantee the consistency of the hinge risk minimization approach to weighted classification.

\bigskip{}

\begin{theorem}\label{thm:continuous functions_WC} Given a distribution $P$ on $\mathbb{R}_{+}\times \{-1,1\} \times \mathcal{X}$ and a class of measurable subsets $\mathcal{G} \subseteq 2^{\mathcal{X}}$, suppose that $\widetilde{\mathcal{F}}_{\mathcal{G}} \subset \mathcal{F}_{\mathcal{G}}$ satisfy the conditions \ref{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions} and that the weight variable $\omega$ satisfies Condition \ref{con:bounded weight variable}. Then the following claims hold:\\
(i)  $\tilde{f}^{\ast} \in \arg \inf_{f \in \widetilde{\mathcal{F}}_{\mathcal{G}}} R_{\phi_h}^{\omega}(f)$ minimizes the weighted-classification risk $R^{\omega}(\cdot)$ over $\mathcal{F}_{\mathcal{G}}$. \\
(ii) For $G^{*}\in{\cal G}^{\ast}$,  $\tilde{f}_{G^{*}}$ is a minimizer of $R_{\phi_h}^{\omega}(\cdot)$ over $\widetilde{\mathcal{F}}_{\mathcal{G}}$.
\end{theorem}

\begin{proof}
See Appendix \ref{appx:proof 4}.
\end{proof}









\section{Empirical illustration}\label{sec:empirical application}

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 \cite{karlan_et_al_2019}.
\cite{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 \cite{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 \cite{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 \cite{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:
\begin{align*}
    Z = \sum_{t=1}^{T}\frac{1}{(1+r)^{t}}P_{t} + \frac{1}{(1+r)^{19}}WC_{19} - D\cdot C,
\end{align*}
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, \cite{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.}:
\begin{align*}
    X_{1} =& \{\mbox{amount of moneylender debt in the baseline period, financial literacy index}\},\\
    X_{2} =& \{\mbox{amount of moneylender debt in the baseline period, food expenditure ratio}\},\\
    X_{3} =& \{\mbox{amount of moneylender debt in the baseline period, financial literacy index},\\
    & \mbox{ food expenditure ratio}\}.
\end{align*}
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.,
\begin{align*}
    \mathcal{F}_{M} = \{f:f(x)\geq f(\tilde{x}) \mbox{ for any $x,\tilde{x} \in \mathcal{X}$ with $x \geq \tilde{x}$ and $f(\cdot) \in [-1,1]$}\},
\end{align*}
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{eq:weighted_classification_risk}) and (\ref{eq:weighted_surrogate_risk})),
let $\hat{f}_{M}$ be a classifier that minimizes the empirical weighted hinge risk over $\mathcal{F}_{M}$ (see Appendix \ref{appx:Monotone weighted classification} 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{tab:welfare gain_exc} 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{fig:treatment rule_exc} 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{tab:welfare gain_exc} 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{tab:welfare gain_exc} 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{fig:treatment rule_exc} 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$.


\begin{table}[h]
\caption{Estimates of welfare gains, probability of treatment, and $E[Z(1)]$ and $E[Z(0)]$}
\label{tab:welfare gain_exc}
\begin{center}
\begin{tabular}{cccccccc}
\hline
\multirow{2}{*}{$X$}     & \multirow{2}{*}{$T$} & \multirow{2}{*}{Sample size} & \multicolumn{2}{l}{Welfare gain of} & Probability of & \multirow{2}{*}{$E[Z(1)]$} & \multirow{2}{*}{$E[Z(0)]$} \\ \cline{4-5}
&   & & $\hat{f}_M$ & $f_{+1}$ & treatment\\ \hline
\multirow{4}{*}{$X_{1}$} & 19 & \multirow{4}{*}{411}  & 627.0 & 495.6 & 0.43 &4406.8& 3911.2\\
& 60 & & 1724.0 & 1223.4 & 0.43 & 12516.6 & 11293.2 \\
& 120 & & 3093.8 & 2132.2 & 0.43 & 22642.3 & 20510.1 \\
& 240 & & 5164.4 & 3506.1 & 0.43 & 37949.7 & 34443.6 \\ \hdashline
\multirow{4}{*}{$X_{2}$} & 19 & \multirow{4}{*}{337}  & 839.5 & 518.6 & 0.43 &4483.7& 3965.1\\
& 60 & & 2214.2 & 1031.1 & 0.40 & 12513.3 & 11482.2 \\
& 120 & & 3991.9 & 1670.9 & 0.40 & 22538.8 & 20867.9\\
& 240 & & 6679.5 & 2638.3 & 0.40 & 37694.7 & 35056.5\\ \hdashline
\multirow{4}{*}{$X_{3}$} & 19 & \multirow{4}{*}{337}  & 1226.9 & 518.6 & 0.42 &4483.7& 3965.1\\
& 60 & & 3182.7 & 1031.1 & 0.44 & 12513.3 & 11482.2 \\
& 120 & & 5631.2 & 1670.9 & 0.45 & 22538.8 & 20867.9 \\
& 240 & & 9333.5 & 2638.3 & 0.45 & 37694.7 & 35056.5 \\
\hline
\end{tabular}
\end{center}
\end{table}


\bigskip
\begin{figure}[h!]
\caption{Monotone treatment rules obtained from empirical hinge risk minimization}
\label{fig:treatment rule_exc}
\bigskip
\begin{tabular}{cc}
\begin{minipage}{0.5\hsize}
\begin{center}
{\small (a) $X_1$ is used and $T \in \{19,60,120,240\}$}
\includegraphics[scale=0.39]{figures/monotone_X1_T=19_cost.png}
\end{center}
\end{minipage}
\bigskip
\\
\begin{minipage}{0.5\hsize}
\begin{center}
{\small (b) $X_2$ is used and $T=19$}
\includegraphics[scale=0.39]{figures/monotone_X2_T=19_cost.png}
\end{center}
\end{minipage}
\begin{minipage}[c]{0.5\hsize}
\begin{center}
{\small (c) $X_2$ is used and $T \in \{60,120,240\}$}
\includegraphics[scale=0.39]{figures/monotone_X2_T=60_cost.png}
\end{center}
\end{minipage}
\end{tabular}
\begin{tablenotes}\footnotesize
\item[] Notes: In each figure, every circle represents the sample density at a given observation.
\end{tablenotes}
\end{figure}
\bigskip{}





\section{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{asm:sublevel set condition} and \ref{asm:optimizer condition} in Theorem \ref{thm:continuous functions} 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.


\bigskip