Model Selection in Utility-Maximizing Binary Prediction

Model Selection in Utility-Maximizing Binary Prediction

\thispagestyle{empty}

\fontsize{12}{18pt}\selectfont \setcounter{page}{1}

Introduction

Making a binary decision based on an uncertain binary outcome is common in modern economic activities. For instance, an investor who considers buying a financial instrument may tend to predict its price change in the future and decide to buy the instrument if the price is predicted to rise. As suggested by GrangerMachina2006, decision-making based on the prediction of a binary outcome should be driven by the preference of the decision maker. On the one hand, the utility arising from a mismatch between the binary decision and outcome may differ in the realized outcome; on the other hand, the utility may be affected by observable covariates. In making financial investment decisions, the disutility for the investor who buys the instrument but suffers from a decrease in the price may be greater than that for the investor who does not buy the instrument but finds an increase in the price. In addition, features of the instrument, for example measures of its price volatility, may affect not only the likelihood of price change but also the investor's utility.\footnote{BarberisXiong2012 propose a model to explain the individual investor preference for volatile stocks. } Further examples illustrating the importance of the decision maker's preference in economic forecasting are provided in ElliottTimmermann2016.

Although the subjective preference would be important for the decision-making based on binary prediction, traditional methods of pattern classification rarely take the decision maker's utility into consideration. Recently, ElliottLieli2013 propose a maximum utility approach to incorporate the decision maker's utility into prediction of a binary outcome $Y\in\{-1,1\}$ given a vector $X$ of observed covariates. Instead of globally estimating the conditional probability $p^{*}(x)\equiv\mathbb{P}(Y=1\mid X=x)$, they show the utility-maximizing binary classification problem can be solved by only estimating the sign of $p^{*}(x)-c(x)$, where $c$ is the cutoff function determined by the decision maker's utility function. Compared with maximum likelihood estimation, their maximum utility estimation is, however, prone to in-sample overfitting.

In this paper, we show that the maximum utility estimation can be viewed as cost-sensitive binary classification; thus, its in-sample overfitting issue is similar to that of perceptron learning in the machine learning literature. To alleviate the tendency of fitting the in-sample noise by sophisticated models, we follow the structural risk minimization approach proposed by Vapnik1982. More precisely, we pre-specify a hierarchy of classes of (finite-dimensional) functions and consider a utility-maximizing prediction rule (UMPR), which is a maximum utility estimator that maximizes a complexity-penalized empirical utility. To construct the UMPR, we consider a VC-type distribution-free complexity penalty and four data-dependent complexity penalties: maximal discrepancy (BartlettBoucheronEtAl2002), simulated maximal discrepancy, Rademacher complexity (Koltchinskii2001 and BartlettBoucheronEtAl2002 among others), and bootstrap complexity (Fromont2007). We evaluate the performance of a prediction rule by the generalized expected utility, that is, the expected utility achieved by the decision maker applying this prediction rule, which could be constructed based on in-sample observations, to the classification of an out-of-sample observation. We emphasize generalization because the expected utility averages over not only the out-of-sample observation but the ex ante in-sample observations as well. We prove that the difference between the maximal expected utility and the generalized expected utility of the UMPR can be bounded by an almost optimal trade-off between the expected complexity penalty and the approximation error, that is, an error due to the approximation of functions in a hierarchy of classes to an optimal decision rule. Hence, whenever the approximation error is equal to zero for some class of functions, the expected utility of the UMPR increases in the sample size and will asymptotically attain the maximal expected utility. In other words, the proposed UMPR is universally utility consistent.\footnote{ Universal utility consistency has a counterpart in the literature on empirical risk minimization, in which different names are used, for example universal consistency in DevroyeGyoerfiEtAl1996, persistence in GreenshteinRitov2004 and Greenshtein2006, and risk consistency in HomrighausenMcDonald2013. Another conceptually different but common term is consistency, and in this paper, it refers to the property that a selection method asymptotically picks a model with the lowest Kullback-Leibler divergence, as in SinWhite1996. }

The idea of complexity penalization has been applied to selection methods in econometrics. Instead of penalized empirical utility criteria, penalized likelihood criteria are the main concerns in early literature. One strand of literature adopts the information-theoretic approach. Classical examples include Akaike1973's (Akaike1973) information criterion (AIC), Schwarz1978's (Schwarz1978) information criterion (BIC), and their cousins (TIC and GIC among others).\footnote{ Schwarz's information criterion is also called BIC, as it is usually analyzed from a Bayesian angle. TIC and GIC are abbreviations for Takeuchi's information criterion and generalized information criterion, respectively.} Additionally, motivated by different spirits, the leave-one-out cross-validation in the likelihood framework is asymptotically equivalent to the AIC, whereas the minimum description length can be approximated by the BIC. These early selection methods are well documented in KonishiKitagawa2008 and ClaeskensHjort2008. With the purpose of achieving shrinkage and variable selection simultaneously, Tibshirani1996's (Tibshirani1996) least absolute shrinkage and selection operator (LASSO) adopts an $\ell_{1}$ penalty. All of these selection methods can be applied to the binary prediction in maximum likelihood estimation with the logit specification. As an alternative to penalized maximum likelihood estimation, penalized maximum score estimation is recently applied to the variable selection in binary prediction by ChenLee2018b, in which an $\ell_{0}$ penalty is used.\footnote{ Similarly, by setting a bound on the $\ell_{0}$-norm of covariates, ChenLee2018 consider the constrained maximum score estimation to select covariates in binary prediction. } Furthermore, replacing the zero-one loss with the hinge loss, the $\ell_{1}$-norm support vector machine (SVM), developed by ZhuRossetEtAl2004 and FungMangasarian2004 among others in the machine learning community, can effectively select variables in the traditional binary classification, namely binary classification with a symmetric loss independent of covariates. However, none of these penalty-based selection methods above takes the decision maker's utility into account.

Despite the prevalence of penalty-based selection methods, pretesting and cross-validation are two alternatives in literature. Both alternatives can be adapted for the selection in maximum utility estimation. ElliottLieli2013 propose a general-to-specific pretest to select MU estimators but do not investigate theoretical properties of their post-model-selection MU estimator. However, as suggested by LeebPoetscher2005 (LeebPoetscher2005, LeebPoetscher2008a), a post-model-selection estimator would have complicated distributional properties. The complicated distributional properties are partly attributable to using the same data for both estimation and validation. In contrast, data splitting makes it convenient to evaluate the out-of-sample performance of a prediction rule so that cross-validation can be used to select models in almost any framework. As argued by ArlotCelisse2010, the wide applicability of cross-validation however makes its predictive performance less satisfactory than that of selection methods tailored in a specific framework. The lack of theoretical analysis of the pretest and cross-validatory estimators motivates the evaluation by Monte Carlo experiments in this paper. According to the simulation results, the UMPR with an appropriate data-dependent penalty outperforms the pretest and cross-validatory estimators. The UMPR with an appropriate data-dependent penalty also outweighs the AIC, BIC, and LASSO if the conditional probability of the binary outcome is misspecified, and the $\ell_{1}$-norm SVM if the cutoff function considerably deviates from $1/2$.

The proposed method in this paper can be viewed as an essential complement to the literature concerned with model selection in binary classification. Although cost-sensitive binary classification is important for decision-making, previous studies on binary classification focus on performance evaluated by the cost-insensitive rate of misclassification. By applying McDiarmid1989's (McDiarmid1989) inequality and Massart2000's (Massart2000) lemma, we extend the aforementioned complexity penalties to the maximum utility estimation, in which the cost of misclassification may depend on the binary outcome and covariates. Following the structural risk minimization approach, we establish non-asymptotic upper bounds on the difference between the maximal expected utility and the generalized expected utility of the UMPR. These bounds, similar to those in Koltchinskii2001 and BartlettBoucheronEtAl2002 for the traditional binary classification, strike a balance between the approximation error and the expected complexity penalty. In addition, we establish a non-asymptotic upper bound, which shrinks to zero as the in-sample size tends to infinity, on the expected value of these data-dependent complexity penalties. We also extend properties of the Bayes decision rule to the maximum utility estimation. This extension not only confirms ElliottLieli2013's (ElliottLieli2013) insight that the knowledge of sign of $p^{*}(x)-c(x)$ suffices to achieve the maximal expected utility, but also implies that the approximation error is bounded by the uniform distance between the conditional probability $p^{*}$ and the underlying class of functions. Consequently, given pre-specified classes of functions, we can examine the universal utility consistency of UMPR, which is a property (corresponding to the risk consistency in loss minimization) rarely investigated in the previous studies on model selection in binary classification.

Throughout this paper, all random variables are defined on the probability space $(\Omega, \mathcal{A}, \mathbb{P})$. Data are assumed to be i.i.d.\ (independent and identically distributed). We write $\mathbb{N}$ for the collection of positive integers and $\mathbb{R}$ for the collection of real numbers. We denote the indicator function by $\mathbbm{1}_{[E]}$, which equals one if event $E$ occurs and equals zero otherwise. We also denote the sign function by $\text{sign}(z)$, which is equal to $2\mathbbm{1}_{[z\geq 0]}-1$ for any $z\in\mathbb{R}$.

The structure of the remaining paper is as follows. Section (ref) describes the maximum utility estimation in ElliottLieli2013's (ElliottLieli2013) model and the issue of its in-sample overfitting. Section (ref) presents the construction of a utility-maximizing prediction rule based on different complexity penalties, and non-asymptotic upper bounds on the difference between the generalized expected utility of the prediction rule and the maximal expected utility. In Section (ref), Monte Carlo experiments are carried out to evaluate the finite-sample performance of the proposed utility-maximizing prediction rule and the aforementioned estimators. Section (ref) concludes. Technical proofs and steps of implementing pretest and cross-validation in the maximum utility estimation are collected in the Appendix.

Maximum Utility Estimation

Model

We start by describing ElliottLieli2013's (ElliottLieli2013) model of binary decision-making based on binary prediction: Before the realization of a binary outcome $Y\in\{-1,1\}$, a decision maker aims to choose a binary decision $a\in\{-1,1\}$ to maximize his or her expected utility conditional on a $d$-dimensional vector of observed covariates $X=x\in\mathcal{X}$. Concretely, the decision maker solves the optimization problem

We abbreviate by writing $u_{a,y}(x)=U(a,y,x)$ for notational simplicity.

Elliott and Lieli show that under some regularity assumptions, we can obtain an optimal decision rule (after observing $X=x$)

where

is a cutoff function derived from the utility function, which is known in principle to the decision maker. Thus, knowledge of the correct conditional probability $p^{*}(x)$ yields the maximal expected utility of the decision.

ElliottLieli2013's (ElliottLieli2013) insight is that the correct specification of sign$(p^{*}(x)-c(x))$ rather than that of $p^{*}(x)$ is enough to achieve maximal expected utility in ((ref)); namely, the knowledge of crossing points between the conditional probability $p^{*}(x)$ and the cutoff $c(x)$ is sufficient. Moreover, they point out that the decision-making problem in ((ref)) can be equivalently written as

where

is the denominator of $c(x)$ and the maximum is taken over all measurable functions from $\mathcal{X}$ to $\mathbb{R}$. Since $u_{a,y}(x)=0.25b(x)[y+1-2c(x)]a+0.25b(x)[y+1-2c(x)]+u_{-1,y}(x)$, we normalize the utility function by setting $u_{-1,y}(x)=-0.25b(x)[y+1-2c(x)]$ for all $x\in\mathcal{X}$ and call $S(f)$ the expected utility of $f$.

The insight motivates ElliottLieli2013 to propose the maximum utility (MU) estimation. To be specific, given observations $\{(Y_{i},X_{i})\}_{i=1}^{n}$ with the sample size $n$ and a pre-specified class $\mathcal{F}$ of functions indexed by a finite-dimensional parameter, we can choose a measurable maximum utility estimator $\hat{f}\in\mathcal{F}$ that satisfies

where “$\arg$” stands for the set of estimators in $\mathcal{F}$ that achieve the optimum.\footnote{ Since multiplicity of the maximum utility estimator could be present, the analysis in this paper emphasizes the properties of optimand functions. See ElliottLieli2013 for the discussion about the lack of identification of optimizers. }

The Monte Carlo simulation in ElliottLieli2013 shows that the maximum utility estimation, compared with traditional maximum likelihood approaches, achieves a large improvement in utility especially when the conditional probability $p^{*}$ is misspecified. However, the in-sample performance of the maximum utility estimation may be attributed to the overfitting. \citeauthor*{ElliottLieli2013} further make the following comment:

Nature of the Overfitting in MU Estimation

The in-sample overfitting of maximum utility estimation is similar to that of perceptron learning in the machine learning literature. The simple perceptron learning is a method of binary pattern recognition that establishes classification based on a threshold function $f(x)=\text{sign}(\theta_{1}^{\top}x-\theta_{0})$, where $\theta_{1}\in\mathbb{R}^{d}$ and $\theta_{0}\in\mathbb{R}$. More variants of perceptron are well documented in Vapnik2000 and AnthonyBartlett1999. Since it can be shown that for any $(y,x)\in\{-1,1\}\times \mathcal{X}$,

the optimization problem in ((ref)) can be viewed as the simple perceptron learning in which the cost of misclassification for each observation $(Y_{i},X_{i})$ may be different. To be specific, the maximum utility estimator satisfies

where $b(X_{i})[Y_{i}(1-2c(X_{i}))+1]$ is the cost of misclassification for the observation $(Y_{i},X_{i})$, and the cost of misclassification is nonnegative under some mild assumptions. The simple perceptron learning is a special case of the maximum utility estimation because the cost of misclassification is identical for each observation whenever there is a constant $\bar{u}\in\mathbb{R}_{+}$ such that $u_{1,1}(x)-u_{-1,1}(x)=u_{-1,-1}(x)-u_{1,-1}(x)=\bar{u}$ for all $x\in\mathcal{X}$. In this case, if $\mathcal{F}$ is further parameterized as $\{x\mapsto\theta_{0}+\theta_{1}^{\top}x: (\theta_{0},\theta_{1})^{\top}\in \mathbb{R}^{(d+1)}\}$, the maximum utility estimation reduces to Manski1975's (Manski1975, Manski1985) maximum score estimation. Moreover, even though the cost of misclassification may be different for each observation $(Y_{i},X_{i})$, when the in-sample observations (training data set) can be perfectly separated by $\mathcal{F}$ (i.e., classification without error), the maximum utility estimation boils down to the simple perceptron learning. This is because in this case, the cost of misclassification $b(X_{i})[Y_{i}(1-2c(X_{i}))+1]$ has no effect:

Although perfect separation of the in-sample observations could be accomplished by a sufficiently large class of functions, such sophisticated models will also fit the in-sample noise and thus worsen the out-of-sample performance.

Model Selection

Motivated by possible in-sample overfitting, we adopt the structural risk minimization approach (also known as complexity regularization) in machine learning to investigate model selection in cost-sensitive binary classification. More precisely, our goal is to alleviate the overfitting by selecting a maximum utility estimator from some specific class of functions such that this selected maximum utility estimator, compared with maximum utility estimators from other classes of functions, has the largest complexity-penalized empirical utility.

To explain the idea, we first introduce notation. Let

be the utility of the prediction rule $f$ evaluated at the observation $(y,x)$.\footnote{ More precisely, $s(y,x,f)$ is the double extra gain (loss) in utility arising from a match (mismatch) between the decision $\text{sign}(f(x)-c(x))$ and outcome $y$ given the covariate $x$, because

} A sample of i.i.d.\ observations with sample size $n$ is denoted by $\mathscr{D}_{n}\equiv\{(Y_{i},X_{i})\}_{i=1}^{n}$. Given a prediction rule $\hat{f}$ constructed based on $\mathscr{D}_{n}$, let $S(\hat{f})=\operatorname*{\mathbb{E}}[s(Y,X,\hat{f})\mid \mathscr{D}_{n}]$ and $S_{n}(\hat{f})=\frac{1}{n}\sum_{i=1}^{n}s(Y_{i},X_{i},\hat{f})$ be the expected utility and the empirical utility of the prediction rule $\hat{f}$, respectively. The expectation involved in the definition of $S(\hat{f})$ is taken with respect to an observation $(Y,X)$, which is independent of $\mathscr{D}_{n}$ and distributed as $(Y_{1},X_{1})$. Said differently, $S(\hat{f})$ measures the decision maker's expected utility if he or she uses the prediction rule $\hat{f}$, estimated based on $\mathscr{D}_{n}$, to classify one additional observation $(Y,X)$ drawn independently of $\mathscr{D}_{n}$. Note that $S(\hat{f})$ could be random because of the random sample $\mathscr{D}_{n}$. We suppress the possible dependence of $S(\hat{f})$ on $\mathscr{D}_{n}$ for convenience of exposition.

The structural risk minimization approach consists of the following steps. First we consider a nondecreasing sieve $\{\mathcal{F}_{k}\}_{k=1}^{\infty}$,\footnote{ In the literature on sieve estimation, a metric space $(\mathcal{F}^{*},\rho)$ is usually pre-specified such that $\mathcal{F}\equiv\bigcup_{k=1}^{\infty}\mathcal{F}_{k}$ is dense in $\mathcal{F}^{*}$ with respect to $\rho$. See for example GemanHwang1982. In this paper, the denseness is however not assumed and $\mathcal{F}^{*}$ can be treated as the collection of all measurable real-valued functions. } that is, a hierarchy of classes of functions

For example, $\mathcal{F}_{k}=\mathcal{P}_{k}$ is the class of polynomial transformations on $\mathcal{X}$ of order at most $k$,\footnote{ A polynomial transformation on $\mathcal{X}\subseteq \mathbb{R}^{d}$ of degree at most $k$ is a function of the form $f(x)=c_{0}+\sum_{j=1}^{q}c_{j}\varrho_{j}(x)$, where $(c_{0},c_{1},\ldots,c_{q})\in\mathbb{R}^{(q+1)}$ and $\varrho_{j}(x)=\prod_{\ell=1}^{d}x_{\ell}^{p_{j\ell}}$ with $\sum_{\ell=1}^{d}p_{j\ell}\leq k$ and $p_{j\ell}\in\mathbb{N}\cup\{0\}$ for each $j$ and $q\in\mathbb{N}$. } or it can be further transformed by the logistic function as $\mathcal{F}_{k}=\Lambda(\mathcal{P}_{k})\equiv \left\{x\mapsto \Lambda(f(x)):f\in\mathcal{P}_{k}\right\}$, where $\Lambda(v)=(1+\exp{\{-v\}})^{-1}$ for all $v\in\mathbb{R}$. We refer the reader to Chen2007 for more examples of sieves. For each $\mathcal{F}_{k}$, we select a maximum utility estimator

In addition, we construct a complexity penalty $C_{n}(k;\alpha)$ for $\mathcal{F}_{k}$, where $\alpha>0$ is a tuning parameter for a technical reason. This technical reason and the issue of choosing $\alpha$ will be discussed later. Let

be the associated complexity-penalized empirical utility of a prediction rule $f\in\mathcal{F}_{k}$. Finally, we define a utility-maximizing prediction rule (UMPR) as a maximum utility estimator $\hat{f}_{k}$ in ((ref)) that maximizes $\tilde{S}_{n}(\hat{f}_{k};k,\alpha)$;\footnote{ Precisely, the UMPR should be referred to as $\text{sign}(\tilde{f}_{n}(\cdot\;;\alpha)-c(\cdot))$. Since it will be clear from the context in this paper, we still reserve the UMPR for the estimator $\tilde{f}_{n}(\cdot\;;\alpha)$. } that is,

For ease of presentation, we suppress the dependence of $(\tilde{S}_{n}(f;k,\alpha),\hat{k}_{n}(\alpha),\tilde{f}_{n}(\cdot\;;\alpha))$ on $\alpha$ and write $\tilde{S}_{n}(\tilde{f}_{n})=\tilde{S}_{n}(\hat{f}_{\hat{k}_{n}};\hat{k}_{n})$ for the complexity-penalized empirical utility of the UMPR.

The idea of complexity penalization has been used in the selection methods based on information criteria in econometrics. These methods aim to maximize the complexity-penalized empirical log-likelihood evaluated at the maximum likelihood estimator. Specifically, let $\mathcal{L}$ be the log-likelihood function of a single observation $(Y,X)$ and $\hat{f}^{\text{ML}}_k$ be the maximum likelihood estimator in $\mathcal{F}_{k}$. Given a complexity measure $C^{\text{IC}}_{n}(k)$ for $\mathcal{F}_{k}$, we can construct an estimator

Leading examples include the AIC by setting $C^{\text{IC}}_{n}(k)$ to be the number of free parameters in $\mathcal{F}_{k}$ divided by $n$, and the BIC by setting $C^{\text{IC}}_{n}(k)$ to be the number of free parameters in $\mathcal{F}_{k}$ multiplied by $\log{\{n\}}/(2n)$. Although the AIC and BIC only differ in the choice of complexity penalty in the selection procedure, their asymptotic behaviors are different. Details on these differences can be found in KonishiKitagawa2008, ClaeskensHjort2008, and references given there.

The UMPR shares a similar motivation with the AIC. Just as the AIC adjusts the empirical log-likelihood to approximate the expected log-likelihood, the UMPR adjusts the empirical utility to approximate the expected utility. Both adjustments are fulfilled by subtracting specific complexity penalties. However, the AIC attempts to recover $p^{*}$, while the UMPR aims to select a model in which the decision maker only focuses on the local fitting at the crossing points between $p^{*}$ and $c$.

As in the penalized likelihood criteria, the choice of complexity penalty $C_{n}(k;\alpha)$ is essential in the proposed penalized empirical utility criteria. First, the complexity penalty should be constructed without assuming any knowledge of the conditional probability $p^{*}$ so that the UMPR, like the maximum utility estimator, can perform well when $p^{*}$ is misspecified. More importantly, the complexity penalty should be an appropriate estimate of the magnitude of overfitting $S_{n}(\hat{f}_{k})-S(\hat{f}_{k})$. In this case, the expected utility $S(\hat{f}_{k})$ can be recovered by the penalized empirical utility $\tilde{S}_{n}(\hat{f}_{k};k)$ and thus the UMPR $\tilde{f}_{n}$ will have the largest expected utility $S(\tilde{f}_{n})$ among the maximum utility estimators $\{\hat{f}_{k}\}_{k=1}^{\infty}$. Taking these two requirements into account, we will construct complexity penalties, without assuming the knowledge of $p^{*}$, to non-asymptotically bound the in-sample overfitting. This non-asymptotic complexity-regularized approach is in marked contrast to the information-theoretic approach, for example AIC and GIC, where penalties are obtained by an asymptotic approximation of the Kullback-Leibler divergence but may not effectively control the in-sample overfitting. As will be shown later, the non-asymptotic complexity penalties may differ from the information-theoretic complexity penalties in the order of the in-sample size. We discuss both distribution-free and data-dependent penalty terms constructed by the non-asymptotic complexity-regularized approach, and study the theoretical properties of their associated utility-maximizing prediction rules in the following subsections.

UMPR with a Distribution-Free Penalty

Since the seminal work by VapnikChervonenkis1971, there have been many improvements in the VC-type upper bound on the uniform deviation of empirical means from their expectations. LugosiZeger1996 further applied the VC-type upper bound to finding a complexity penalty in the traditional binary classification. Motivated by this idea, we aim to construct a VC complexity penalty for the maximum utility estimation.

We start by making the following assumptions.\\[0.3cm] Assumptions

The first three assumptions are imposed in ElliottLieli2013, and the last assumption is imposed to avoid measurability complications. Assumption (ref) excludes the possibility of feedback from the binary action to the binary outcome. Take the financial investment in Section (ref) as an example. Under Assumption (ref), investors are price takers whose decisions on buying an instrument do not affect the possibility of price change. Assumption (ref) implies that the decision maker obtains higher utility when the decision matches the outcome; in particular, there should be a best response $a$ to a realized outcome $Y$ if this realization were observed by the decision maker before making a decision. This assumption seems plausible in many situations, for example the aforementioned financial investment. The uniform boundedness imposed by Assumption (ref) implies some shape constraint on the utility functions, especially when the support $\mathcal{X}$ is unbounded. However, this assumption could be compatible with some models of the financial investment. An example is the exponential utility (also known as constant absolute risk aversion preference) used by ChristensenLarsenEtAl2012 in an asset pricing model when the decision maker is risk averse. Assumption (ref) is inconsequential in practice because there are only countably many computable real numbers evaluated for the parameters of $\mathcal{F}_{k}$ by a computer program. The use of computable real numbers and functions could also be interpreted as a decision maker's computability-bounded rationality, as in RichterWong1999.

These assumptions allow us to establish a VC-type upper bound on the uniform deviation of $S_{n}(f)$ from $S(f)$.

The maximal inequality in Proposition (ref) suggests that large empirical utility arising from sophisticated models does not guarantee large expected utility. To see this, note that for any $n,k\in\mathbb{N}$ and $\delta\in(0,1)$, with probability at least $1-\delta$,

Thus, given the sample size $n$, an increase in $k$ tends to increase empirical utility $S_{n}$, but it may meanwhile increase $\Pi_{k,c}(n)$. The growth function $\Pi_{k,c}$ measures the complexity of $\mathcal{F}_{k,c}$ to fit in-sample observations. Clearly, $\Pi_{k,c}(\ell)\leq 2^{\ell}$ for each $\ell\in\mathbb{N}$. If $\Pi_{k,c}(\ell)<2^{\ell}$ for some $\ell$, the complexity of $\mathcal{F}_{k,c}$ is restricted because some specific $\ell$ observations $\{(Y_{i},X_{i})\}_{i=1}^{\ell}$ cannot be separated by $\mathcal{F}_{k,c}$ without any classification error.\footnote{ There are $2^{\ell}-\Pi_{k,c}(\ell)$ possible realizations of $(Y_{1},\cdots,Y_{\ell})^{\top}$ such that for all $(x_{1},\cdots,x_{\ell})^{\top}$ and $f\in\mathcal{F}_{k}$,

}

Proposition (ref) also implies the asymptotic behavior of $\sup_{f\in\mathcal{F}_{k}}|S_{n}(f)-S(f)|$ as follows.

This corollary immediately guarantees that given i.i.d.\ observations, $|S_{n}(\hat{f}_{k})-S(\hat{f}_{k})|$ converges almost surely to zero whenever $\Pi_{k,c}$ is of polynomial order. Hence, the technical conditions imposed by Proposition 2 of ElliottLieli2013 such as compactness of parameter space and lipschitz continuity of functions with respect to the parameter can be relaxed.

More importantly, the maximal inequality in Proposition (ref) is non-asymptotic; thus, it can be used to estimate the upper bound on $S_{n}(\hat{f}_{k})-S(\hat{f}_{k})$ for every finite sample size $n$ when the growth function $\Pi_{k,c}$ is known. The calculation of $\Pi_{k,c}(n)$ is, however, not easy in practice. Thus, $\Pi_{k,c}(n)$ is usually replaced with an upper bound

where $V_{k,c}$ is the VC dimension of the class $\mathcal{F}_{k,c}$, which is the largest integer $\ell$ such that $\Pi_{k,c}(\ell)=2^{\ell}$ by definition. By Proposition (ref), the replacement of $\Pi_{k,c}(n)$ with $\psi_{c}(k,n)$ shows that for any $n, k\in\mathbb{N}$ and $\varepsilon>0$,

The upper bound $\psi_{c}(k,n)$ follows from a combinatorial result, which is known as Sauer's lemma and can be found in Theorems 3.6 and 3.7 of AnthonyBartlett1999. As a parameter involved in $\psi_{c}(k,n)$, the VC dimension $V_{k,c}$, like the growth function, also restricts the complexity of $\mathcal{F}_{k,c}$. Note that $\Pi_{k,c}(V_{k,c}+1)<2^{(V_{k,c}+1)}$ if $V_{k,c}<\infty$. Thus, the classification error of using $\mathcal{F}_{k,c}$ to classify some realization of $\{(Y_{i},X_{i})\}_{i=1}^{n}$ is impossibly eliminated whenever the in-sample size $n$ is greater than $V_{k,c}$. As shown in Theorem 3.5 of AnthonyBartlett1999, the VC dimension $V_{k,c}$ is equal to the dimension of $\mathcal{F}_{k}$ if this class $\mathcal{F}_{k}$ is specified as a vector space of real-valued functions. For example, the VC dimension $V_{k,c}$ is ${d+k \choose k}$ if $\mathcal{F}_{k}$ is the class $\mathcal{P}_{k}$ of polynomial transformations on $\mathcal{X}$ of order at most $k$ in the absence of dummy covariates. Even if we consider the logit specification, say $\mathcal{F}_{k,c}=\left\{x\mapsto \text{sign}(f(x)-c(x)):f\in\Lambda(\mathcal{P}_{k})\right\}$, then its VC dimension $V_{k,c}$ can be bounded by ${d+k \choose k}+1$.\footnote{ To see this, note that for a class of Boolean functions, the VC dimension is equal to the VC index minus one by definition. Since both functions $\text{sign}(\cdot)$ and $\Lambda(\cdot)$ are monotone, the VC index of $\mathcal{F}_{k,c}$ is less than or equal to that of $\mathcal{P}_{k}$ by Lemma 9.9 (v) and (viii) of Kosorok2008. Applying Lemma 9.6 of Kosorok2008 yields the result. } More generally, if $\mathcal{F}_{k}$ is a VC-subgraph class,\footnote{ Let $\mathcal{C}$ be a collection of subsets of $\mathcal{Z}$. The collection $\mathcal{C}$ is said to shatter a subset $\mathcal{Z}_{\ell}=\{z_{1},\ldots,z_{\ell}\}\subseteq \mathcal{Z}$ if the cardinality of $\left\{\{\mathcal{Z}_{\ell}\cap C\}:C\in\mathcal{C}\right\}$ is equal to $2^{\ell}$. The collection $\mathcal{C}$ is called a Vapnik-Cervonekis (VC) class if for some $\ell\in\mathbb{N}$, no subset of cardinality $\ell$ is shattered by $\mathcal{C}$. A collection $\mathcal{F}$ is a VC-subgraph class if the collection $\big\{\{(x,t)\in \mathcal{X}\times \mathbb{R}:t<f(x)\}:f\in\mathcal{F}\big\}$ of all subgraphs is a VC class of sets in $\mathcal{X}\times \mathbb{R}$. } then the VC dimension $V_{k,c}$ equals the VC index of $\mathcal{F}_{k}$ minus one by Lemma 9.9 of Kosorok2008. We refer the reader to Section 2.6 of VaartWellner1996 and Section 9.1 of Kosorok2008 for properties of a VC-subgraph class.

The easily computable VC-type upper bound permits the construction of a distribution-free complexity penalty. For each $k$, we consider an estimate of expected utility $S(\hat{f}_{k})$ to be

It follows that for each $k$, we obtain a non-asymptotic upper bound on the tail probability for $R^{\text{VC}}_{n,k}-S(\hat{f}_{k})$. To be specific, we have for any $n,k\in\mathbb{N}$ and $\varepsilon >0$,

Following the suggestion in BartlettBoucheronEtAl2002, we consider the VC complexity penalty

where

The VC complexity penalty is the sum of the estimate $S_{n}(\hat{f}_{k})-R_{n,k}$ of the magnitude of overfitting and a technical term $8M\chi_{n}(k;\alpha)$. Treating $S_{n}(\hat{f}_{k})-R_{n,k}$ as a component of the VC complexity penalty, the non-asymptotic complexity-regularized approach explicitly accounts for the in-sample overfitting. The VC complexity penalty differs from the penalties for the information-theoretic approach in the order of $n$. For example, the VC complexity penalty (without the technical term) is $8M\sqrt{2(k+1)\log\{en/(k+1)\}/n}$ if we consider the specification $\mathcal{F}_{k}=\mathcal{P}_{k}$ of univariate polynomial functions for the UMPR. Given the logistic transformation of the same specification $\mathcal{F}_{k}=\mathcal{P}_{k}$ in the empirical log-likelihood, the AIC and BIC have the penalties $(k+1)/n$ and $(k+1)\log\{n\}/(2n)$, respectively. In this example, the VC complexity penalty would be greater than the penalties used in AIC and BIC when a large sample is available. The different convergence rates should be attributed to the difference in the underlying objective function: the AIC and BIC are both associated with the empirical log-likelihood function, whereas the UMPR is associated with the empirical utility function.\footnote{ The derivation of penalties for AIC and BIC relies on twice differentiability of the empirical log-likelihood function. See for example Sections 3.4 and 9.1 of KonishiKitagawa2008. The empirical utility function is, however, not differentiable. Despite the non-differentiability, a minimax lower bound on $\operatorname*{\mathbb{E}}[S_{n}(\hat{f}_{k})]-\operatorname*{\mathbb{E}}[S(\hat{f}_{k})]$ could still be established. Let $\mathcal{P}(\mathcal{F}_{k})$ be the set of all distributions of $(Y,X)$ such that $p^{*}\in\mathcal{F}_{k}$. In the special case that $b(x)=b>0$ and $c(x)=1/2$ for all $x\in\mathcal{X}$, if $\mathcal{F}_{k}$ has a finite VC index greater than 2, then Inequality (38) of MassartNedelec2006 implies $\sup_{\mathbb{P}\in\mathcal{P}(\mathcal{F}_{k})}\operatorname*{\mathbb{E}}[S_{n}(\hat{f}_{k})]-\operatorname*{\mathbb{E}}[S(\hat{f}_{k})]\geq \operatorname{\Omega}\left(1/\sqrt{n}\right)$, where the notation $\operatorname{\Omega}\left(1/\sqrt{n}\right)$ indicates that there exist positive constants $\kappa_{0}$ and $n_{0}$ such that this lower bound is grater than $\kappa_{0}/\sqrt{n}$ for all $n\geq n_{0}$. Thus, the VC complexity penalty is near optimal in the minimax sense. This lower bound can be improved under a margin restriction on $p^{*}$. Details about the margin restriction can be found in MassartNedelec2006. } The technical term $\chi_{n}(k;\alpha)$ is included in the penalty to guarantee the summability of $\zeta(\alpha)\equiv \sum_{k=1}^{\infty}V_{k,c}^{-(1+\alpha)}$ for some $\alpha_{0}$ such that the union bound holds nontrivially in the proof of the following theorem.

Theorem (ref) implies a probabilistic lower bound on the expected utility $S(\tilde{f}_{n})$; that is, for any $n\in\mathbb{N}$ and $\delta\in(0,1)$,

with probability at least $1-\delta$. Theorem (ref) also shows an upper bound on the difference between the maximal expected utility $S^{*}$ and the generalized expected utility $\operatorname*{\mathbb{E}}[S(\tilde{f}_{n})]$. This upper bound takes into account the trade-off between the complexity penalty $C^{\text{VC}}_{n}(k;\alpha_{0})$ and the approximation error $S^{*}-S^{*}_{k}$. Furthermore, if the approximation error is equal to zero for some $k$, then $\operatorname*{\mathbb{E}}[S(\tilde{f}_{n})]$ converges to $S^{*}$ because the upper bound on this difference shrinks to zero as the sample size tends to infinity. In this case, the convergence of $\operatorname*{\mathbb{E}}[S(\tilde{f}_{n})]$ to $S^{*}$ is equivalent to the convergence of $S(\tilde{f}_{n})$ to $S^{*}$ in probability because $\sup_{f\in\mathcal{F}}|S(f)|\leq 4M$ under Assumption (ref). In fact, we can establish the almost sure convergence of $S(\tilde{f}_{n})$ as follows.

Corollary (ref) shows that the UMPR $\tilde{f}_{n}$ with the VC penalty is universally utility consistent because the almost sure convergence holds for every distribution of $(Y,X)$ satisfying $\lim_{k\to \infty}S_{k}^{*}=S^{*}$. To check this convergence of approximation error for some function classes $\{\mathcal{F}_{k}\}_{k=1}^{\infty}$, we prove the following proposition.

This proposition implies that for each $k\in\mathbb{N}$,

If we specify $\mathcal{F}_{k}$ as the class of polynomial transformations on $\mathcal{X}$ of order at most $k$, then the Stone-Weierstrass approximation theorem ensures that $\inf_{f\in\mathcal{F}_{k}}\sup_{x\in\mathcal{X}}|f(x)-p^{*}(x)|$ converges to zero as $k$ tends to infinity whenever $p^{*}$ is continuous on the support $\mathcal{X}$ that is a compact subset of $\mathbb{R}^{d}$. Moreover, if each $r$-th order partial derivative of $f:\mathcal{X}\to\mathbb{R}$ exists and is continuous on $\mathcal{X}$ for all $r\leq s\in\mathbb{N}$, and $\mathcal{X}$ is compact, then the multivariate Jackson theorem of BagbyBosEtAl2002 implies that $\inf_{f\in\mathcal{F}_{k}}\sup_{x\in\mathcal{X}}|f(x)-p^{*}(x)|=\operatorname{O}\left(k^{-s}\right)$. Rather than evaluating the global approximation to $p^{*}$, ElliottLieli2013 illustrate some preferences and data generating processes of $(Y,X)$ in which finite order polynomial functions in $X$ can completely replicate the crossing points between $p^{*}(x)$ and $c(x)$; more precisely, there is some polynomial function $f_{0}$ with sufficient order such that $\text{sign}(f_{0}(x)-c(x))=\text{sign}(p^{*}(x)-c(x))$ and thus $S^{*}_{k}\equiv\sup_{f\in\mathcal{P}_{k}}S(f)=S^{*}$ for some $k\in\mathbb{N}$ by Proposition (ref).

By explicitly expressing $S^{*}-S(f)$ for any nonrandom function $f$, Proposition (ref) also confirms ElliottLieli2013's insight that the correct specification of sign$(p^{*}(x)-c(x))$ is sufficient to achieve the maximal expected utility. Furthermore, Proposition (ref) extends the properties of the Bayes decision rule to the cost-sensitive case. In this case, the maximal expected utility $S^{*}$ depends on not only the distribution of $(Y,X)$ via the conditional probability $p^{*}$ but also the decision maker's preference via the weight function $b$ and cutoff function $c$. Corresponding results in the traditional binary classification can be found in Sections 2.4 and 2.5 of DevroyeGyoerfiEtAl1996.

The upper bound in Proposition (ref) is distribution-free in the sense that it is valid for any distribution of $(Y,X)$. Since the distributional properties are ignored, this VC-type upper bound is generally loose. The looseness is even exacerbated by the replacement of the growth function with an upper bound via Sauer's lemma. Although the distribution of $(Y,X)$ is unknown, its distributional information could be inferred from the sample. As shown in Lozano2000's (Lozano2000) simulation results for the interval model selection problem, the data driven penalization can track the magnitude of overfitting better than the VC-type penalization. Thus, we expect that using data-dependent complexity penalties, instead of the distribution-free complexity penalty $C^{\text{VC}}_{n}(k;\alpha_{0})$, will improve the predictive performance of the UMPR.

UMPR with a Data-Dependent Penalty

Heuristically, the magnitude of overfitting is bounded by $\max_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S'_{n}(f)\right)$,\footnote{ It can be shown that $\operatorname*{\mathbb{E}}[\sup_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S(f)\right)]\leq \operatorname*{\mathbb{E}}[\max_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S'_{n}(f)\right)]$ by the common symmetrization argument. By McDiarmid1989's (McDiarmid1989) inequality, there is a constant $c_{0}>0$ such that for any $\delta\in(0,1)$, $\sup_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S(f)\right) -\max_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S'_{n}(f)\right)\leq\sqrt{\ln\{1/\delta\}/c_{0}n}$ with probability at least $1-\delta$. } where $S'_{n}(f)$ is the empirical utility of $f$ based on the ghost sample $\mathscr{D}'_{n}$, in which the observations $(Y'_{1},X'_{1}),\ldots,(Y'_{n},X'_{n})$ are distributed as $(Y_{1},X_{1}),\ldots,(Y_{n},X_{n})$ and independent of them. Although the lack of the ghost sample $\mathscr{D}'_{n}$ invalidates the direct estimation of $\max_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S'_{n}(f)\right)$, this idea allows us to develop data-dependent complexity penalties. Each of them, similar to the VC counterpart, is the sum of a technical term with $\chi_{n}(k;\alpha)$ and an estimate of $\max_{f\in\mathcal{F}_{k}}\left(S_{n}(f)-S'_{n}(f)\right)$. Different estimates generate different complexity penalties as follows.

To study the performance of the UMPR $\tilde{f}_{n}$ with each of these data-dependent complexity penalties, we evaluate the difference between the generalized expected utility $\operatorname*{\mathbb{E}}[S(\tilde{f}_{n})]$ and the maximal expected utility $S^{*}$. The upper bounds on $S^{*}-\operatorname*{\mathbb{E}}[S(\tilde{f}_{n})]$ in Theorem (ref), resembling the VC counterpart in Theorem (ref), have a similar trade-off between the associated expected complexity penalty and the approximation error. Note that the data-dependent complexity penalties are all random, whereas the VC complexity penalty is deterministic.

We can show that if the ratio $m/n$ is bounded away from zero, then the expected value of each data-dependent complexity penalty in this section shrinks to zero at the rate $\operatorname{O}\left(n^{-1/2}\right)$, which is slightly faster than the convergence rate of the VC complexity penalty. Hence, if the approximation error $S^{*}-S^{*}_{k}$ is equal to zero for some $k$, then $S^{*}-\operatorname*{\mathbb{E}}[S(\tilde{f}_{n})]=\operatorname{O}\left(n^{-1/2}\right)$. Under the same assumptions, we can also demonstrate the universal utility consistency of the UMPR $\tilde{f}_{n}$ with any data-dependent complexity penalty above. These results are summarized in Corollary (ref).

Simulation

To study the finite-sample performance of the UMPR with any complexity penalty in the previous section, we carried out Monte Carlo experiments. The simulation designs are those in ElliottLieli2013. Specifically, we consider two data generating processes:

In addition, we consider four preferences:

The first two preferences are associated with (ref), whereas the last two preferences are associated with (ref). For (ref) together with either preference 1 or 2, not only the cubic ML but also the cubic MU are correctly specified because there are three crossing points between the conditional probability $p^{*}$ and the cutoff function $c$ in the support of $X$.\footnote{ By the cubic MU, we mean that the MU optimization is taken over the class $\mathcal{P}_{3}$ of polynomial transformations of order at most 3. Similarly, we refer to the cubic ML as the maximum likelihood estimation with optimization taken over the class $\Lambda(\mathcal{P}_{3})$. } Although any logit model is misspecified for (ref), ElliottLieli2013 demonstrate that the cubic MU is correctly specified in the sense that for all $x\in\mathcal{X}$, $\text{sign}(f(x))=\text{sign}(p^{*}(x)-c(x))$ for some $f\in\mathcal{P}_{3}$.

We evaluate different selection methods for the cost-sensitive binary classification. In addition to the proposed UMPR with different complexity penalties, we study the pretest estimator adopted by ElliottLieli2013 and a tenfold cross-validatory estimator in the maximum utility estimation. For the MU, UMPR, pretest and cross-validatory estimators, we specify the hierarchy $\{\mathcal{F}_{k}\}_{k=1}^{\infty}$ of classes as $\mathcal{F}_{k}=\mathcal{P}_{k}$ for $k\in\{1,2\}$ and $\mathcal{F}_{k}=\mathcal{P}_{3}$ for all $k\geq 3$. Moreover, we compare prediction rules based on penalized empirical utility criteria with those based on penalized likelihood criteria. We consider the UMPR for the former criteria, but the AIC and BIC for the latter criteria. For the ML, AIC and BIC, we specify the hierarchy $\{\mathcal{F}_{k}\}_{k=1}^{\infty}$ of classes as $\mathcal{F}_{k}=\Lambda(\mathcal{P}_{k})$ for $k\in\{1,2\}$ and $\mathcal{F}_{k}=\Lambda(\mathcal{P}_{3})$ for all $k\geq 3$. We also compute the tenfold cross-validatory LASSO (i.e., logistic loss with an $\ell_{1}$ penalty) with optimization taken over the class $\Lambda(\mathcal{P}_{3})$ and $\ell_{1}$-norm SVM (i.e., hinge loss with an $\ell_{1}$ penalty) with optimization taken over the class $\mathcal{P}_{3}$. The steps of pretesting and cross-validation in maximum utility estimation are described in Appendix (ref), whereas the implementation of LASSO and $\ell_{1}$-norm SVM can be found in EfronHastie2016 and FungMangasarian2004, respectively.\footnote{ As suggested for the $\ell_{2}$-norm SVM in Shawe-TaylorCristianini2004, we construct the $\ell_{1}$-norm SVM estimator $\hat{f}_{\text{SVM}}$ based on standardized covariates in the following Monte Carlo experiments. Additionally, we use the logistic transformation $\tilde{f}_{\text{SVM}}\equiv \Lambda(\hat{f}_{\text{SVM}})$ to evaluate its predictive performance. This transformation not only makes $\tilde{f}_{\text{SVM}}$ comparable with other competing estimators in binary classification but also maintains the classification rule of $\hat{f}_{\text{SVM}}$ because $\text{sign}(\hat{f}_{\text{SVM}}(x))=\text{sign}(\tilde{f}_{\text{SVM}}(x)-c(x))$ provided $c(x)=1/2$ for all $x\in\mathcal{X}$.} To evaluate the performance of a prediction rule $f^{\dag}_{n}$, we compute its relative generalized expected utility

which can be approximated via simulation because

where $S_{\ell,j}(f^{\dag}_{n}|\mathscr{D}_{n,j})$ is the $j$-th out-of-sample empirical utility with size $\ell$ of $f^{\dag}_{n}$, constructed by the $j$-th training data $\mathscr{D}_{n,j}$ with size $n$, $S_{\ell,j}(p^{*})$ is the $j$-th out-of-sample empirical utility with size $\ell$ of $p^{*}$, and $\mathcal{S}$ is the number of simulation replications. In the following experiments, we set $n\in\{500,1000\}$, $\ell=5000$, and $\mathcal{S}=500$; additionally, we take $m=10$ for the SMD, RC, and BC penalties.

Table (ref) presents the relative generalized expected utility of ML, MU, and UMPR with VC and MD complexity penalties under different designs when $n=500$ and $n=1000$. As expected, a correctly specified ML achieves the largest relative generalized expected utility among these estimators for (ref). However, a misspecified ML, compared with MU and UMPR, usually has the worst performance. In addition, for each tuning parameter $\alpha\in\{1,0.5,0.1,0.05\}$, the UMPR with MD penalty outperforms its VC counterpart for (ref), but the dominance is not clear for (ref). As $\alpha$ decreases (i.e., the technical term is smaller), the UMPR with MD penalty might have slightly larger relative generalized expected utility. However, the UMPR with VC penalty has the same relative generalized expected utility as the linear MU for (ref). This is a caveat that the correctly specified cubic MU is never selected out of 500 simulation replications by the UMPR with VC penalty. This phenomenon arises probably because the distribution-free complexity penalty used to construct the UMPR is too conservative. Using tenfold cross-validated $\hat{\alpha}$ selected from $\{1,0.5,0.1,0.05\}$ does not improve the performance of the UMPR with VC and MD penalties; however, excluding the technical term ($8M\chi_{n}(k;\alpha)$ and $24M\chi_{n}(k;\alpha)$ for VC and MD penalty, respectively) would yield an increase in relative generalized expected utility. These results imply that the UMPR with MD penalty is more adept at selecting the MU estimator with the largest utility than its VC counterpart. Thus, we focus on the UMPR with data-dependent complexity penalties exclusive of the technical term hereafter.

In addition to the comparison between MU and ML, we compare prediction rules based on penalized empirical utility criteria with those based on penalized likelihood criteria. Table (ref) reports the relative generalized expected utility of UMPR, AIC, BIC, LASSO, and $\ell_{1}$-norm SVM under different designs when $n=500$ and $n=1000$. We see that the performance of the UMPR relies on the choice of data-dependent complexity penalties. Among these penalties, SMD, RC, and BC might be better than MD in terms of relative generalized expected utility. We also see that the AIC and BIC outweigh the UMPR for (ref), and this reflects the consistent selection of the cubic ML by the AIC and BIC, a property shown in SinWhite1996. However, the AIC and BIC, selecting a mispecified logit model by the penalized likelihood, are dominated by the UMPR for (ref). Furthermore, compared with the AIC and BIC, the LASSO has poorer performance for (ref), but almost the same performance for (ref). Outweighing the LASSO for (ref), the SVM has the worst performance for (ref). Such bad performance could be attributed to the fact that the SVM aims to recover $\text{sign}(p^{*}(x)-1/2)$ rather than $\text{sign}(p^{*}(x)-c(x))$, but the cutoff function $c(x)$ is markedly different from $1/2$ for (ref). More importantly, when the number of in-sample observations increases from $n=500$ to $n=1000$, the relative generalized expected utility of UMPR increases for all designs. This phenomenon is guaranteed by Theorem (ref) and Corollary (ref) because the approximation error $S^{*}-S^{*}_{3}$ is equal to zero. In contrast, for (ref) in which any ML is misspecified, a larger sample size does not improve the relative generalized expected utility of AIC, BIC, LASSO, and SVM. These results demonstrate that the UMPR inherits the robustness of MU estimation, a feature that selection methods based on penalized likelihood criteria do not possess in general.

Finally, we compare the proposed UMPR with two pretest estimators, including a specific-to-general approach and a general-to-specific approach, and the tenfold cross-validatory estimator in maximum utility estimation. Table (ref) provides the relative generalized expected utility and the percentage of models selected out of 500 simulation replications when $n=500$ and $n=1000$. Differences in the selection frequencies for the pretesting are shown across the left and right panels because ElliottLieli2013's (ElliottLieli2013) test statistic depends on the preference specifications. In terms of selecting the correctly specified cubic MU, the UMPR with VC penalty, either inclusive or exclusive of a technical term, performs worst under all designs. As can be seen, the cross-validatory estimator, in comparison with the UMPR, attains higher percentages of selecting the cubic MU under all designs. Thus, the cross validation might be preferable if we attempt to select the model correctly specified in the maximum utility estimation. However, if the goal is to capture the largest expected utility, we prefer the UMPR with data-dependent penalties to the pretest and cross-validatory estimators because the proposed penalty-based prediction rules perform better than the other estimators in terms of the relative generalized expected utility, as suggested by the experimental evidence.

Conclusion

The maximum utility estimation can be viewed as the binary classification with a decision-based utility function. Despite its possible improvement in utility over traditional maximum likelihood methods, the maximum utility estimation has inherited the in-sample overfitting from the perceptron learning.

To alleviate the in-sample overfitting, we adopt the structural risk minimization approach to construct a utility-maximizing prediction rule. For complexity penalization, we consider the distribution-free VC penalty and four data-dependent penalties (MD, SMD, RC, and BC). For each penalty, we show that the difference between the maximal expected utility and the generalized expected utility of the utility-maximizing prediction rule is bounded. The upper bounds are close to zero for a large sample if the approximation error is equal to zero for some pre-specified classes of functions. In general, we prefer the simulated complexity penalties in terms of predictive performance, as suggested by the simulation results. These simulation results also show that the utility-maximizing prediction rule with an appropriate data-dependent complexity penalty has better predictive performance than the pretest and cross-validatory estimators; more importantly, it outperforms the AIC, BIC, and LASSO if the conditional probability of the binary outcome is misspecified, and the $\ell_{1}$-norm SVM if the cutoff function considerably deviates from $1/2$. The utility-maximizing prediction rule is thus important for the decision-making based on binary prediction.