Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
84,457 characters · 32 sections · 42 citation commands
Binary Classification with the Maximum Score Model and Linear Programming
\address{$^1$Department of Economics, Northwestern University, Evanston, IL 60208, USA.} \email{[email removed]}
\address{$^2$Centre for Microdata Methods and Practice, Institute for Fiscal Studies, 7 Ridgmount Street, London, WC1E 7AE, UK.} \address{$^3$Department of Economics, Columbia University, New York, NY 10027, USA.} \email{[email removed]}
\onehalfspacing
This paper introduces a computationally efficient method for applying Manski's (Manski:1975, Manski:1985) maximum score model of binary response to binary classification when covariates may be discretely distributed and parameters are partially but not point identified. We establish conditions under which it is minimax optimal to allow for either non-classification or random classification and derive finite-sample and asymptotic lower bounds on the probability of correct classification.
In Manski’s model, the binary dependent variable $Y$ is related to a finite-dimensional vector of explanatory variables $X$ as follows:
where $I(\cdot)$ is the indicator function, $\beta$ is an unknown vector of constants, and $0<\tau<1$, implying that zero is the $\tau$-quantile of $U$ conditional on $X$. The distribution of $U$ is otherwise unrestricted and may depend on $X$ in an unknown way (i.e., heteroskedasticity of unknown structure). Given an independent random sample $\left\{ (Y_i, X_i): i=1, \ldots, n\right\}$, the maximum score estimator of $\beta$ is defined as:
where $\mathbf{B}$ is the parameter space.
If $\beta$ were known, an individual with covariate $X_*$ would be classified as $Y=1$ if $\beta' X_* > 0$ and $Y=0$ otherwise. However, when $X$ follows a discrete distribution, $\beta$ and $\beta' X_*$ are not point identified. Under mild conditions, $\beta' X_*$ is contained in an identified interval, denoted here by $[c_L, c_H]$. In this paper, we propose two simple classification rules. In one rule, an individual with covariate $X_*$ is classified as $Y=1$ if $c_L > 0$, as $Y=0$ if $c_H < 0$, and remains unclassified if $c_L \leq 0 \leq c_H$. We provide a decision-theoretic framework in which this classification rule is shown to be minimax optimal. This minimax optimal classification rule relies on two elements: a lower cost associated with abstention (non-classification) compared to misclassification, and the explicit availability of non-classification as an option. In the second classification rule, abstention is not possible, and decisions are made via randomization. In this case, we propose a modified decision rule: classify as $Y = 1$ if $c_L > 0$, as $Y = 0$ if $c_H < 0$, and assign $Y = 1$ or $Y = 0$ randomly with equal probability when $c_L \leq 0 \leq c_H$. We again establish conditions under which this randomized classification rule is minimax optimal.
We further present estimators for $[c_L, c_H]$ and construct both finite-sample and asymptotic confidence intervals, denoted by $[\hat{c}_L, \hat{c}_H]$. The classification rule follows the same logic: we classify an individual as $Y=1$ if $\hat{c}_L > 0$ and as $Y=0$ if $\hat{c}_H < 0$, with non-classification or random classification occurring when $\hat{c}_L \leq 0 \leq \hat{c}_H$. We say that an individual is classified correctly if (s)he would have the same classification if $c_L$ and $c_U$ were known. Theoretically, we provide upper bounds on the probability of misclassification and, thereby, lower bounds on the probability of correct classification.
Computing $\hat{\beta}$ (solving the optimization problem (ref)) is a notoriously difficult, NP-hard combinatorial optimization problem. In addition, $\hat{\beta}$ converges in probability to $\beta$ at the slow rate of $n^{-1 / 3}$ when $\beta$ is point identified. The objective of this paper, however, is estimation of the interval $\left[c_L, c_H\right]$ that contains $\beta^{\prime} X_*$, not point identification or estimation of $\beta$. We give conditions under which $\left[c_L, c_H\right]$ can be estimated by solving two linear programming problems, one for $c_L$ and one for $c_H$. Computationally efficient algorithms and software for solving linear programming problems are widely available, so we avoid the computational difficulty of solving (ref).
While the underlying model involves the parameter vector \(\beta\), our primary interest lies in conducting binary classification rather than in precisely estimating \(\beta\) itself. Although the bounds for \(\beta\) may be wide, informative classification remains possible. By focusing on the signs of linear combinations of covariates rather than on point estimates of coefficients, we leverage the structure of the identified set to assign classifications reliably. Thus, even when parameter uncertainty is substantial, the classification rule can yield meaningful and robust decisions.
Various methods exist for binary classification. Fully nonparametric methods, such as estimating $\mathbb{P}(Y=1 \mid X=X_*)$ nonparametrically and classifying based on whether this probability exceeds $\tau$, make minimal assumptions but suffer from poor extrapolation ability. If the covariates follow a discrete distribution, these methods fail to classify individuals whose $X_*$ is not observed in the sample and are imprecise if there are few observations of $X_*$. Parametric methods, including logit, probit, and discriminant analysis, allow extrapolation but rely on restrictive distributional assumptions. The method we propose balances these trade-offs: it permits extrapolation while being less restrictive than fully parametric approaches and some semiparametric models. For example, semiparametric single-index models satisfying the quantile restriction are special cases of the maximum score model.
The remainder of this paper is structured as follows. Section (ref) reviews the literature on maximum score estimation. Section (ref) formally describes the model. Section (ref) provides a decision-theoretic framework for the proposed classification rule. Section (ref) outlines our estimation procedure and discusses finite-sample and asymptotic inference with discretely distributed covariates. It also presents lower bounds on the probability of correct classification. Finite-sample inference typically yields conservative bounds in moderate-sized samples common in economics applications, as it imposes only weak constraints on the distribution of the underlying random variables and ensures validity for the worst-case scenario under those constraints. In contrast, asymptotic inference yields tighter bounds but does not guarantee validity in finite samples. Section (ref) details our computational algorithms. Section (ref) extends the framework to accommodate continuous covariates, specifically incorporating manski2002inference-type bounds when a continuous vector is treated as observed only within a hypercube. Section (ref) provides empirical illustrations: Section (ref) presents an empirical example using data from KLS; Section (ref) illustrates the extension discussed in Section (ref), again using the same data; Section (ref) presents another empirical application using data from Corno:ECMA:2020. Section (ref) reports a Monte Carlo experiment demonstrating the effectiveness of our classification rules. Section (ref) concludes with a discussion of key findings and potential directions for future research. Appendix (ref) contains the proofs of the theoretical results presented in the main text. Appendix (ref) presents Monte Carlo simulations comparing finite-sample and asymptotic inference methods. Finally, Appendix (ref) extends the framework to accommodate clustered dependence and survey sampling weights.
The literature on the maximum score model is concerned mainly with identification and estimation of $\beta$, methods for computing $\hat{\beta}$ in (1.2), and inference. The literature is large, and we cite only a limited set of papers that treat these topics.
Manski:1988 provided classical results for point identification. Subsequently, advances have been made in terms of partial identification: see, e.g., manski2002inference; komarova2013; blevins2015; chen2015; and KKN:2024 among others.
When $\beta$ is point identified, $\hat{\beta}$ converges in probability to $\beta$ at the rate $n^{-1 / 3}$, and $n^{1 / 3}(\hat{\beta}-\beta)$ has an intractable asymptotic distribution kim1990,Seo2016. For inference, subsampling and bootstrap methods are considered in e.g., delgado2001; abrevaya2005; Lee:Pun:06; Patra2015; and Cattaneo2020bootstrap among others; however, they are computationally demanding because it is required to solve (ref) repeatedly.
Horowitz:92,horowitz2002 developed smoothed maximum score estimation to mitigate the difficulties coming from the maximum score objective function. The smoothed maximum score estimator is asymptotically normal with a faster rate of convergence and enables the bootstrap to provide asymptotic refinements. Alternative approaches include: finite sample inference Rosen:Ura:2024; Bayesian methods benoit2012,Walker:2024; non-Bayesian Laplace type approaches JPW15, JPW14; and two-stage methods GXX:2022 among many others.
One major challenge in applying maximum score estimation lies in the computational complexity of the objective function. The maximum score objective is a piecewise constant function, with a finite range of discrete values. Consequently, while this function always reaches a maximum, the maximizer is not necessarily unique, making computation of the maximum score estimates NP-hard Johnson:78. Early algorithms for addressing maximum score estimation were developed by Manski:Thompson:1986 and PINKSE1993. Second-generation approaches leverage advances in mixed integer programming (MIP) solvers, along with significant increases in computing power since the development of the first-generation methods. Florios:Skouras:08 presented strong numerical evidence that an MIP-based method outperforms earlier techniques. Similarly, Kitagawa:Tetenov:2015 employed an alternative MIP formulation to solve a maximum score-type problem for treatment choice rules, where they maximized an empirical welfare criterion resembling the maximum score function. Chen:Lee:18,Chen:Lee:20 extended this approach to $\ell_0$-constrained and $\ell_0$-penalized empirical risk minimization for high-dimensional binary classification. However, the MIP approach faces intrinsic scalability limitations. To the best of our knowledge, numerical studies applying MIP to maximum score estimation typically remain confined to datasets with a modest sample size (e.g., around 1,000) and a limited number of parameters. In contrast, our approach is based on linear programming, which is considerably more scalable and capable of handling larger datasets with a greater number of parameters.
This section describes the model we treat and the parameters of interest. We begin with definitions and notation.
Let $X \in \mathbb{R}^q$ be a random or non-stochastic (fixed) vector. If $X$ is random, assume for now that it is discretely distributed with $J$ mass points $\left\{x_j: j=1, . ., J\right\}$ and probability mass function $p\left(x_j\right)>0$. The case of continuously distributed components of $X$ is treated in Section (ref). If $X$ is fixed, let it have $J$ possible values $\left\{x_j: j=1, . ., J\right\}$. In this case, we treat a design in which there are $n$ observations of $(Y,X)$ and $n_j > 0$ of these observations have $X=x_j$. Define $p\left(x_j\right)=n_j / n$, the fraction of observations in the design for which $X=x_j$. For any random event $A$, let $P\left(A \mid X=x_j\right)$ denote the probability of $A$ conditional on $X=x_j$ if $X$ is random and the probability of $A$ at $X=x_j$ if $X$ is fixed.
The model is
where $U$ is an unobserved random variable that satisfies $\mathbb{P} \left(U \leq 0 \mid X=x_j\right)=\tau$ for all $j=1, \ldots, J$, some constant $0<\tau<1$, and some unknown vector of constant parameters $\beta \in \mathbb{R}^q$. We assume that this model is correctly specified unless stated otherwise. Note that the $(1-\tau)$ quantile of $Y$ conditional on $X=x_j$ is
where $I (\cdot)$ is the usual indicator function. A scale normalization is needed for identification of $\beta$. We use $\beta_1 =1$, where $\beta_1$ is the first component of $\beta$.
For each $j=1, \ldots, J$ define
where for a real number $u$, $\text{sgn}(u) = 1$ if $u > 0$, $\text{sgn}(u) = -1$ if $u < 0$, and $\text{sgn}(u) = 0$ if $u = 0$. Let $r^{\prime} \beta$, where $r \in \mathbb{R}^q$ is a non-zero vector of constants, be a linear combination of components of $\beta$. The parameter $\beta$ is not point identified when $X$ is discretely distributed with finitely many mass points or fixed with finitely many possible values. The linear combination $r^{\prime} \beta$ is not point identified if at least one component of $\left(r_2, \ldots, r_J\right)^{\prime}$ is non-zero, but it is interval identified. Let $\left[c_L, c_U\right]$ be the identified interval.
We assume the following regularity conditions.
Under Assumption (ref), there is an $\varepsilon>0$ such that $\min_{1\leq j \leq J} \left|\beta^{\prime} x_j\right| = \varepsilon$. Under Assumption (ref), the parameter space for $\beta$ is a known compact set. Define
If $X$ is random, we include the indicator function $I( X = x_j)$ in $g_0 (x_j)$ so that it can be estimated as a sample average without a random denominator.
In model (ref), $Y=1$ if and only if $\beta'X \geq U$, where $\mathbb{P}(U \leq 0 \mid X)=\tau$. Under Assumption (ref), we have
Therefore, under Assumption (ref), the identified set for $\beta$ is $$ \left\{b \in \mathbf{B}: d_j=\operatorname{sgn}\left(b^{\prime} x_j\right) ; b_1=1,\left|b^{\prime} x_j\right| \geq \varepsilon ; j=1, \ldots, J\right\}. $$ This is equivalent to $$ d_j\left(x_{j 1}+b_2 x_{j 2}+\ldots+b_q x_{j q}\right) \geq \varepsilon \quad (j=1, \ldots, J) . $$ The identified upper and lower bounds, $c_U$ and $c_L$, on $r^{\prime} \beta$ are optimal values of the objective functions of the linear programs
subject to
for all $j=1,\ldots,J$.
Under Assumption (ref), $d_j \equiv \text{sgn}[ f(x_j) ]$ and $g_{0,j} \equiv g_0(x_j)$ have the same sign. Therefore, the linear programs (ref)-(ref) with $\varepsilon = 0$ are equivalent to
subject to
for all $j=1,\ldots,J$.
In this section, we present a decision-theoretic framework for our classification rules. We start with the case of a known, point-identified $\beta$. Let $\hat{y} \in \{0, 1\}$ denote a binary classifier. For covariate values \(x\) within the support of $X$, the function \[ f(x) = \mathbb{P}(Y=1 \mid X=x) - \tau \] is nonparametrically identified. At the population level, the optimal classification rule assigns
However, when \(x\) lies outside the support of $X$, the function \(f(x)\) is not identified, and classification based on (ref) is not feasible. Classification based on \(f(x)\), which is what we rely on when $\beta$ is unknown and only partially identified, does not extend to off-support covariate values. In contrast, if $\beta$ is known, we can replace (ref) with the equivalent linear rule
This formulation enables classification at any covariate value $x$, including those not in the support of $X$.
We now move to the case of partially identified $\beta$. Although $\beta'x$ is only interval-identified: \[ \beta' x \in [c_L(x),\,c_U(x)], \] this interval provides information about the sign of $f(x)$, which can be leveraged to extrapolate $f(x)$ and classify off-support values of $x$. To account for the partial identification of $\beta'x$, we consider two scenarios: one that includes the option of non-classification, and another that allows for random classification.
In this subsection, we extend the classification options from $\{0, 1\}$ to $\{0, 1, \emptyset\}$, where $\emptyset$ denotes “non-classification.” Consider the following loss function:
where \(0 \le C_{b} < C_{\emptyset} < C < \infty.\)
The loss function \(L(\hat{y}, y)\) reflects the relative costs associated with three possible classification actions: assigning \(1\), assigning \(0\), or abstaining (denoted by \(\emptyset\)). Correct classifications incur a baseline loss \(C_{b}\), interpreted as the cost of making a decision even with oracle knowledge of \(f(x)\); this cost need not be zero, as the realized outcome \(Y\) can differ from the classification implied by \(f(x)\). Incorrect classifications, where \(\hat{y}\) disagrees with the sign of \(f(x)\), incur a higher loss \(C\), reflecting the penalty for wrong decisions such as incorrect treatments or verdicts. Abstention incurs an intermediate loss \(C_{\emptyset}\), satisfying \(C_{b} < C_{\emptyset} < C\), and models the idea that refraining from classification is preferable to misclassification but costlier than a correct decision. Abstention seems natural when partial identification of \(f(x)\) limits prediction for off-support $x$. The exact values of \(C_{b}\), \(C_{\emptyset}\), and \(C\) are immaterial for our classification rule, provided the ordering \(0 \leq C_{b} < C_{\emptyset} < C < \infty\) holds. Overall, the structure of the loss function encourages a cautious classification strategy. The following theorem formalizes this intuition by characterizing the decision rule that minimizes the worst-case loss under this loss structure.
In words, we adopt the following classification rule: predict 1 if the entire identified region for $\beta'x$ is strictly positive; predict 0 if it is strictly negative; and abstain otherwise.
When $x$ is off-support, we determine a bounding interval $[c_L(x), c_U(x)]$ for $\beta'x$. If this interval is entirely positive, we predict 1; if entirely negative, we predict 0; otherwise, we abstain to avoid incurring the high misclassification cost $C$. The key insight is that $C_\emptyset$ is strictly smaller than $C$, making non-classification optimal in ambiguous cases.
One might argue against the option of abstention when the identification interval includes zero. If one truly faces a binary choice problem, abstention may not be possible. As an alternative, one might consider a randomized choice between the two options. Indeed, there is a precedent for randomization as a sensible approach to making binary decisions under ambiguity Manski2009.
Since abstention is not feasible in this subsection, we modify the loss function in (ref) as follows:
where \(0 \le C_{b} < C < \infty.\)
Suppose we randomly classify an observation as \(1\) with probability \(p\) and as \(0\) with probability \(1 - p\). The expected loss is then:
To minimize the expected loss, it is necessary to know the true sign of \(\beta'x\). However, since this is unknown, we instead aim to minimize the maximum regret. The regret is defined as the expected loss minus the oracle loss \(C_{b}\):
Theorem (ref), building on the framework of Manski2009, provides a robust rationale for assigning classifications randomly with equal probability when the identification interval includes zero. Although the theorem is stated in terms of minimizing maximum regret, it also characterizes the minimax-optimal rule under expected loss. This equivalence holds in our setting because the oracle loss $C_b$ remains constant regardless of the true sign of $\beta’x$.
Section (ref) describes estimation of $c_L$ and $c_U$. Sections (ref) and (ref) describe our method of inference about $\left[c_L, c_U\right]$. Section (ref) gives the lower bounds on the probability of correct classification when $c_L$ and $c_U$ are replaced by our estimates.
In applications, $g_{0, j}$ is unknown. We estimate it by one of two methods, depending on whether $X$ is fixed or random. If $X$ is fixed, estimate $g_{0, j}$ by
If $X$ is random, estimate $g_{0, j}$ by $$ \hat{g}(x_j)=n^{-1} \sum_{i=1}^n\left(Y_i-\tau\right) I\left(X_i=x_j\right). $$ Both estimators are unbiased: $$ \mathbb{E} \left[\hat{g}\left(x_j\right)\right]=g_0\left(x_j\right) ; \quad j=1, \ldots, J. $$
Now let $\mathcal{G}_\alpha$ be a confidence region for $g_0 \equiv (g_{0,1},\ldots, g_{0,J})$ satisfying
for some $0 < \alpha < 1$. Here, $\mathcal{G}_\alpha$ may be a finite-sample or asymptotic confidence region. Section (ref) explains how to construct finite-sample confidence regions based on the two versions of $\hat{g}(x_j)$. Section (ref) explains how to construct asymptotic confidence regions.
The estimators of $c_U$ and $c_L$, denoted respectively by $\hat{c}_U$ and $\hat{c}_L$, are the optimal values of the objective functions of the following optimization problems:
subject to
for all $j=1,\ldots,J$.
The following theorem, which is similar to Theorem 2.1 of JL:JBES, is the basis for our inference and classification.
Theorem (ref) shows that if (ref) holds, the estimated interval $[\hat{c}_L, \hat{c}_U]$ contains the population interval $[c_L, c_U]$ with finite-sample or asymptotic probability at least $(1-\alpha)$, depending on whether $\mathcal{G}_\alpha$ is a finite-sample or asymptotic confidence region. Theorem (ref) implies that to obtain a confidence region for $[c_L, c_U]$, it suffices to obtain the confidence region $\mathcal{G}_\alpha$. Sections (ref) and (ref) explain how to construct finite-sample and asymptotic confidence regions $\mathcal{G}_\alpha$ that satisfy (ref).
In terms of classification, Theorem (ref) establishes lower bounds on the probability of correct classification when the estimated bounds allow classification (i.e., when $\hat{c}_L > 0$ or $\hat{c}_U < 0$). However, it does not provide guarantees for cases where $\hat{c}_L \leq 0 \leq \hat{c}_U$, meaning classification is indeterminate. Sections (ref) and (ref) provide bounds that include the possibility of indeterminate classification. Nevertheless, as the sample size $n$ increases, the probability of correct classification for all cases approaches 1, since $\hat{c}_L$ and $\hat{c}_U$ consistently estimate $c_L$ and $c_U$. This result aligns with the standard intuition behind size and power comparisons in hypothesis testing.
This section obtains finite-sample confidence regions $\mathcal{G}_\alpha$ for fixed and random $X$.
Let $X$ be fixed and Assumption (ref)(a) hold. Then
because $Y = 0$ or 1. An application of Hoeffding's inequality yields $$ \mathbb{P} \left[\left|\hat{g}\left(x_j\right)-g_0\left(x_j\right)\right| \geq p\left(x_j\right) t_j \right] \leq 2 \exp \left(-2 n_j t_j^2\right) $$ for any $t_j>0$ and each $j=1, \ldots, J$. Moreover,
for all $j=1, \ldots, J$ with probability at least $1-2 \sum_{j=1}^J \exp \left(-2 n_j t_j^2\right)$. Set
and
Then $\mathbb{P}(g_0 \in \mathcal{G}_\alpha) \geq 1-\alpha$.
Let $X$ be random and Assumption (ref)(b) hold. Then $$ -\tau \leq (Y_{\ell, j} - \tau ) I\left(X_i=x\right) \leq 1-\tau. $$ Another application of Hoeffding's inequality gives $$ \mathbb{P} \left[\left|\hat{g}\left(x_j\right)-g_0\left(x_j\right)\right| \geq t\right] \leq 2 \exp \left(-2 n t^2\right) $$ for each $j=1,\ldots,J$ and any $t > 0$. Therefore, $$ \hat{g}\left(x_j\right)-t \leq g_0\left(x_j\right) \leq \hat{g}\left(x_j\right)+t $$ for all $j=1, \ldots, J$ and any $t > 0$ with probability at least $1-2 J \exp \left(-2 n t^2\right)$. Now set
and
Then $\mathbb{P}(g_0 \in \mathcal{G}_\alpha) \geq 1-\alpha$.
To compare confidence regions in (ref) and (ref), let Assumption (ref)(a) hold so that $p(x_j) = n_j/n$. Then,
which implies that $[\hat{c}_L, \hat{c}_U]$ is a longer interval under the random design than under the fixed design. This happens because of the need to account for randomness of $X$ when we apply Hoeffding's inequality to the random design.
This section gives asymptotic confidence regions $\mathcal{G}_\alpha$ for fixed and random designs. To minimize computational complexity (see Section (ref)) we focus on (hyper) rectangular regions based on the Bonferroni inequality. Ellipsoidal regions give narrower bounds $[\hat{c}_L, \hat{c}_U]$ under certain conditions but make computation much more difficult.
As in Section (ref), let $X$ be fixed and Assumption (ref)(a) hold. It follows from the Lindeberg-Lévy central limit theorem that for each $j=1,\ldots,J$, $$ \left(n / n_j^{1 / 2}\right)\left(\hat{g}_j-g_{0, j}\right) \rightarrow_d N\left(0, \sigma_j^2\right), $$ where $$ \sigma_j^2 \equiv \mathbb{P}\left(Y=1 \mid X=x_j\right)\left[1-\mathbb{P}\left(Y=1 \mid X=x_j\right)\right]. $$ Estimate $\sigma_j^2$ by
and let $z_{1-\alpha}$ denote the $(1-\alpha)$ quantile of the standard normal distribution. Set
Then the Bonferroni inequality gives $\mathbb{P}(g_0 \in \mathcal{G}_\alpha) \geq 1-\alpha$ asymptotically.
Let $X$ be random and Assumption (ref)(b) hold. Then the Lindeberg-Lévy theorem gives $$ n^{1 / 2} \left(\hat{g}_j-g_{0, j}\right) \rightarrow_d N\left(0, s_j^2\right), $$ where $$ s_j^2 \equiv \mathrm{Var} \left[ \left(Y_i-\tau\right) I\left(X_i=x_j\right) \right]. $$ Estimate $s_j^2$ by
Set
Then, the Bonferroni inequality gives $\mathbb{P}(g_0 \in \mathcal{G}_\alpha) \geq 1-\alpha$ asymptotically. $\mathcal{G}_\alpha$ is larger with a random design case than with a fixed design if and only if $ n \hat{s}_j^2 > n_j \hat{\sigma}_j^2. $
In the population, an individual with covariate \(X_*\) is classified as \(Y=1\) if \(c_L(X_*) > 0\) and as \(Y=0\) if \(c_U(X_*) < 0\), where \(c_L(X_*)\) and \(c_U(X_*)\) are the optimal values of the objective functions defined in (ref)--(ref) with \(r = X_*\). The individual is not classified if \(c_L(X_*) \leq 0 \leq c_U(X_*)\). Thus, the oracle classifier assigns: \[ \mathrm{Oracle}(X_*) =
\] The desirability of this classification rule was justified through a decision-theoretic framework in Section (ref).
Using the estimation sample, an individual is classified as \(Y=1\) if \(\hat{c}_L(X_*) > 0\) and as \(Y=0\) if \(\hat{c}_U(X_*) < 0\), where \(\hat{c}_L(X_*)\) and \(\hat{c}_U(X_*)\) are the optimal values of the objective functions in (ref)--(ref) with \(r = X_*\). The individual is not classified if \(\hat{c}_L(X_*) \leq 0 \leq \hat{c}_U(X_*)\). Thus, the maximum score classifier assigns: \[ \mathrm{MaximumScore}(X_*) =
\]
We define the misclassification indicator at \(X_*\) by \[ \mathcal{M}(X_*) =
\]
To characterize the probability of misclassification, we allow \(X_*\) to be either fixed or random.
Part (a) considers a fixed design, while part (b) addresses a random design. In part (i) under each setting, we allow \(X_*\) or its distribution to differ from that of the training sample. Part (ii) imposes margin conditions to ensure separation in both designs. The margin conditions in part (ii) are natural in our setting, as they formalize the idea that classification becomes more reliable when $c_L(X_*)$ and $c_U(X_*)$ are well-separated from zero. When these conditions hold, small estimation errors are unlikely to alter the classification outcome, making it easier to mimic the oracle classification. In contrast, if the margin conditions fail (i.e., when either $c_L(X_*)$ or $c_U(X_*)$ lies close to zero in a fixed design, or with non-negligible probability in a random design), even minor sampling variability can result in misclassification. This undermines both the stability and the interpretability of the classification rule, particularly in finite samples.
For the fixed design, the misclassification probability is bounded by two components: the coverage error \(\alpha\) and the estimation errors \(\mathbb{P}(\hat{c}_L(X_*) - c_L(X_*) \leq -\epsilon) + \mathbb{P}(\hat{c}_U(X_*) - c_U(X_*) \geq \epsilon)\). There is a trade-off between these two components: as \(\alpha\) decreases, the interval \([\hat{c}_L(X_*), \hat{c}_U(X_*)]\) widens, leading to larger estimation errors. This mirrors the familiar size-power trade-off in hypothesis testing.
For the random design, an additional component \(M_L \epsilon + M_U \epsilon\) appears, reflecting the difficulty of classification when \(c_L(X_*)\) or \(c_U(X_*)\) is close to zero.
In this section, we consider the case of random classification. Specifically, random classification by the oracle occurs when $c_L(X_*) \leq 0 \leq c_U(X_*)$ for a given covariate value $X_*$. Let $r$ be a binary random variable taking values in $\{0,1\}$ with equal probability, i.e., $\mathbb{P}(r = 1) = \mathbb{P}(r = 0) = 0.5$, and let $Y = r$ when random classification occurs.
Define the oracle classification outcome by \[ M_{\mathrm{OR}} =
\] and the classification outcome under the maximum score rule by \[ M_{\mathrm{MS}} =
\] Then the corresponding classification rules are:
where both oracle and maximum score classifiers are assumed to use the same random classification $r$. We redefine the misclassification indicator at $X_*$ as: \[ \mathcal{M}(X_*) =
\]
The bounds in Theorem (ref) differ from those in Theorem (ref) due to the role of random classification. In the setting of Theorem (ref), abstention is permitted, so it is possible for the oracle to classify $Y = 0$ or $Y = 1$, while the maximum score classifier abstains. This leads to a classification disagreement. In contrast, under random classification (as in Theorem (ref)), abstention is not an option, and both the oracle and the maximum score classifier randomly assign $Y = 0$ or $Y = 1$ with equal probability when the decision is ambiguous. Consequently, they agree with probability 0.5 in such cases, and this probabilistic agreement is reflected in the factor of 0.5 appearing in the bounds in Theorem (ref).
In this section, we describe how to solve the optimization problems given in (ref)-(ref). In all the cases we considered, $\mathcal{G}_\alpha$ has the form
for an appropriate choice of $\hat{s}(x_j, \alpha) > 0$. For example, for asymptotic inference under the random design, we have $\hat{s}(x_j, \alpha) = n^{-1/2} \hat{s}_j z_{1 - \alpha / (2J)}$ (see the form of $\mathcal{G}_\alpha$ defined in (ref)). The constraints in (ref) are bilinear and could potentially create computational difficulties; however, it turns out that it is easy to solve (ref)-(ref) with $\mathcal{G}_\alpha$ in the form of (ref). Specifically, the following theorem shows that it suffices to solve a linear programming (LP) problem, which is known to be highly scalable.
This result highlights a key computational simplification: for each $j$, only one of the two linear constraints in (ref) needs to be imposed, and only when $\hat{g}(x_j)$ deviates sufficiently from zero. If $\hat{g}(x_j)$ lies within the interval $[-\hat{s}(x_j, \alpha), \hat{s}(x_j, \alpha)]$, no constraint is imposed for that index. This selective enforcement leads to an LP problem with fewer active constraints, while still exactly solving the original bilinear formulation.
In this section, we extend our framework to manski2002inference type bounds for maximum score estimation when a continuously distributed vector is only observed or treated as only observed to be in a hypercube.
Let $X$ be a discretely distributed random vector with $\operatorname{dim}(X)=q_X$ and $V$ be a continuously distributed random vector with $\operatorname{dim}(V)=q_V$. The model is given by
where the unobserved random variable $U$ satisfies $\mathbb{P} \left(U \leq 0 \mid X, V \right)=\tau$ almost surely for some constant $0<\tau<1$. We use the scale/sign normalization $\delta_1=1$, where $\delta_1$ is the first element of $\delta$. A key assumption is that $V$ is unknown (or treated as unknown and we discretize $V$ in advance) but is in the hypercube $V_0 \leq V \leq V_1$ component-wise, where $V_0$ and $V_1$ are known, non-stochastic constants or observed discrete random variables. In this setting, $\theta \equiv (\beta', \delta')'$ is not point identified. The objective here is to estimate upper and lower bounds on the identified interval for $r^{\prime} \theta$, where $r$ is a constant vector whose components are not all zero.
Let $W \equiv (X', V_0', V_1')'$ denote the observed covariates. We make the following regularity conditions.
We now make the following generalization of MT's interval, monotonicity, and mean independence (IMMI) assumptions.
The monotonicity assumption requires the signs of the coefficients of the components of $V$ to be known, which is often the case in applications (e.g., if $V$ is a price). Given this knowledge, there is no further loss of generality in assuming that the signs are non-negative; a negative sign can be turned into a positive one by changing the sign of the relevant component of $V$.
Let $\mathcal{W} \equiv \{ w_j \equiv (x_j, v_{0 j}, v_{1 j}): j=1, \ldots, J \}$ denote mass points of $W$. The following theorem simplifies and generalizes Proposition 1 of MT.
Now define
and
We now make an analog of Assumption (ref).
Under Assumption (ref), we have that $\left|f\left( w_j \right)\right|>0$ for all $j=1, \ldots, J$. This is necessary to exclude the case of $f(w_j) = 0$ as we have explained in Remark (ref). Note that by Lemma (ref) and the fact that $\left[\mathbb{P}\left(Y=1 \mid X=x_j,V=v_{j}\right)-\tau\right] > 0 \Leftrightarrow \beta^{\prime} x_j+\delta^{\prime} v_{j} > 0 $,
and
Therefore, the identified set for $\theta$ is
The identified upper and lower bounds on $r^{\prime} \theta$ are optimal values of the objective functions of the linear program
subject to
for all $j=1,\ldots,J$. As in Remark (ref), outer bounds can be obtained by replacing $\varepsilon$ with zero.
For brevity, we focus on the random design case. It is straightforward to modify the following discussion to the fixed design case. As before, we define
where $p_{W}(\cdot)$ is the probability mass function of $W$. As $p_{W}(w_j) > 0$, we have that $\operatorname{sgn}[f(w_j)] = \operatorname{sgn}[g(w_j)]$ for all $j=1,\ldots,J$. We now modify the estimator by $$ \hat{g}(w_j)=n^{-1} \sum_{i=1}^n\left(Y_i-\tau\right) I\left(W_i=w_j\right) $$ and assume that we have the following confidence set for $g_j \equiv g(w_j)$:
for an appropriate choice of $\hat{s}(w_j, \alpha) > 0$.
Following the arguments used to prove Theorem (ref), we can show that it is possible to conduct inference by solving
subject to
When $ v_{0 j} = v_{1 j}$, the resulting optimization problem is the same as (ref).
Suppose that we want to classify a new member of the population using their covariate vector, say $W_* \equiv (X_*, V_*)$, where $W_*$ may not be an element in the support $\mathcal{W}$ of $W$. In particular, $V_*$ can be different from the realized values of $(V_{0i},V_{1i})$. Then, we solve (ref) with $r = W_*$. As before, we propose to assign $(Y=0)$ if the solution to the minimization problem is negative; $(Y=1)$ if the solution to the maximization problem is positive; and abstain from classification or apply random classification otherwise.
In Section (ref), we apply our method to classify resumes in the context of hiring decisions. In Section (ref), we demonstrate how the approach can be extended to interval-valued covariates using the resume classification example. Finally, in Section (ref), we use our method to assess the likelihood of marriage among women in developing countries.
In this section, we use data from KLS to illustrate the methodology developed in this paper. KLS introduced a new experimental paradigm, called incentivized resume rating (IRR), which invites employers to evaluate resumes known to be hypothetical (avoiding deception) and provides incentives by matching employers with real job seekers. For each resume, KLS asked two questions, both on a Likert scale from 1 to 10:
We construct the binary response variable by setting $Y_i = 1$ if the rating for the first question is higher than or equal to 5 and 0 otherwise. Among possible covariates, we include:
GPA and Top Internship are two most important predictors in the KLS regression analysis (see Table 1 in KLS). In this example, $n = 2880$ and $J = 6 \times 2 = 12$. Out of 12 covariate groups, the minimum, median, and maximum group sizes are 110, 226, and 347, respectively.
Figure (ref) displays the sample probabilities $\{ \mathbb{P}(Y = 1 | X = x_j): j =1,\ldots, J \}$ of receiving the rating of 5 or higher for hiring interest by covariate groups. Blue triangles correspond to 6 GPA groups (points of support of the covariates) with a top internship (i.e., Top Internship $= 1$) and red squares those without a top internship (i.e., Top Internship $= 0$). It can be seen that having a top internship boosts the ratings although the vertical distance between the triangle and square is not uniform across different GPA groups. The orange horizontal line represents the probability of 0.5, suggesting that it would be interesting to consider $\tau = 0.5$ in this example.
In view of Figure (ref), we consider the following simple linear specification for $\beta' x$ with $\tau = 0.5$:
where $\beta_1 \equiv 1$ by scale normalization. The main parameter of interest is $\beta_2$, which measures the effectiveness of having a top internship relative to the effect of GPA.
Table (ref) presents interval estimates for $\beta_2$ and $\beta_3$ across different methods. In column (1), a logit model based on (ref) is fitted and the misspecification-robust asymptotic 95% confidence intervals for $\beta_j/\beta_1$ for $j=2,3$ are given. In columns (2)-(4), maximum score estimation of (ref) is considered with $\tau= 0.5$ under the restriction that $- 10 \leq \beta_j \leq 10$ for $j=2,3$. In column (2), (ref)-(ref) is solved for $r'\beta = \beta_j$ with $\hat{s}(x_j, \alpha) \equiv 0$; that is, we treat the $\hat{g}_j$'s as if they were true probabilities. In columns (3) and (4), we use the asymptotic 95% confidence regions for the fixed and random designs, respectively. The sample size was too small to consider finite sample inference in this example. In Appendix (ref), we present results from small Monte Carlo experiments comparing finite and asymptotic inference methods. In summary, a substantially larger sample size is required to obtain informative bounds. It can be seen from Table (ref) that the effect of Top Internship is strictly positive in columns (1) and (2) and has relatively tight intervals. The intervals are wider in columns (3) and (4).
We now move to our main focus, namely, the classification exercise for each covariate group. Figure (ref) shows the results of classification by covariate groups. In the top left panel, we classify each covariate group by $I ( x_j' \hat{\beta}_{\text{Logit}} > \tau)$, where $\hat{\beta}_{\text{Logit}}$ is the logit estimate. That is, if the predicted probability is greater than $\tau=0.5$, we assign $1$ and if it is less than $\tau=0.5$, we assign $0$. In other panels, we use maximum score methods and classify the covariate groups as described in Section (ref). Here, $\emptyset$ refers to the case of “non-classification.” The maximum score methods used in Figure (ref) match those in columns (2)-(4) in Table (ref) with a suitable choice of $r'\beta$. The classification results using the logit model suggest that Top Internship is a game changer for the middle GPA groups of 3.4 and 3.6. The top right panel that treats sample probabilities as the truth show a similar patten, although it indicates that Top Internship is crucial for GPA groups of 3.2 and 3.4. The bottom panels are identical, implying that there is no difference in classification between the fixed and random design cases. The results are more prudent here as there are 4 incidences of non-classification. The GPA groups of 3.6 or higher with a top internship are classified as $1$, whereas the GPA groups of 3.4 or lower without a top internship are classified as $0$. Finally, we do not display classification outcomes for the abstention region $\emptyset$ under random classification, as its value will be either $0$ or $1$ depending on the outcome of the randomization device.
In this subsection, we illustrate the extension discussed in Section (ref). Recall that we have grouped GPA into six categories via $\text{\texttt{ceiling}}(\text{GPA} \times 5)/5$. In the original data, the range of GPA is $[2.90,4.00]$ and it is recorded in two decimal points. Thus, we now view GPA as an interval covariate and it takes the following interval values: $\{ (v_{0j}, v_{1j})_{j=1}^6 \} = \{[2.9, 3.0],[3.0,3.2],\ldots,,[3.8,4.0]\}$.
Table (ref) reports of the effects of treating GPA as an interval covariate. Columns (1) and (2) reproduce the estimates in Table (ref), where we treat GPA as “truly” discretely distributed; columns (3) and (4) provide new estimates. It can be seen that the resulting bounds on Top Internship become larger to reflect the nature of interval censoring.
We also revisit our classification exercise. Figure (ref) compares classification results between the baseline results in Figure (ref) and the new results treating GPA as an interval covariate. The top panel sub-figures reproduce the estimates in Figure (ref) and the bottom panel sub-figures show equivalent classification results, only changing GPA to be an interval covariate. Unsurprisingly, there are more cases of non-classification ($\emptyset$ in the $y$-axis) as the bounds are wider with interval censoring. As before, we do not display classification outcomes under random classification.
In this subsection, we provide a second empirical example using data from Corno:ECMA:2020. In particular, we use their Sub-Saharan Africa (SSA) sample, which contains more than 2 million observations with survey sampling weights. Furthermore, it is unlikely that observations are independent across each other. In the regression analysis of Corno:ECMA:2020, regression coefficients are estimated with survey sampling weights and the standard errors are clustered at the grid cell level. Our framework can be extended to account for clustered dependence and survey sampling weights. Since these details are not essential for understanding the empirical results in this section, we provide them in Appendix (ref). In particular, we focus on asymptotic inference in Section (ref), as the effective sample size was too small to apply the finite sample inference method.
In this example, the dependent variable is a binary variable for marriage, coded to 1 if a woman married at the age corresponding to the observation and 0 otherwise. Among possible covariates, we include:
They are all discrete covariates and the resulting $J$ is $J = 13 \times 2 \times 4 = 104$. Figure (ref) displays the sample probabilities $\{ \mathbb{P}(Y = 1 | X = x_j): j =1,\ldots, J \}$ of marriage by covariates: age, drought, and birth cohorts. The sample probabilities are computed using country population-adjusted survey sampling weights. The orange horizontal line in each panel represents the probability of 0.12, which is the value of $\tau$ in this example.
It can be seen from Figure (ref) that the age effects tend to be linear up to around age 18 and become more or less flat after age 18. In view of this, we consider the following specification for $\beta' x$ with $\tau = 0.12$:
where $\beta_1 \equiv 1$.
In Table (ref), we report interval estimates using our methods. The sample maximum score interval estimates are quite tight in column (1). By the discrete nature of covariates (in particular, all the regressors can take only integer values), the tightest interval will be a point as in the case of drought and the second tightest interval will be an interval of length 1, which is the case for all the other covariates. The maximum score interval estimates become wider in column (2) as we take into consideration sampling uncertainty by taking $\mathcal{G}_\alpha$ to be a 95% confidence region (note that $\mathcal{G}_\alpha$ is identical between the fixed and random designs here; see Appendix (ref) for details).
We now move to the classification exercise. Figure (ref) shows the maximum score classification results treating sample probabilities as population probabilities. One striking patten is the existence of the cohort effects, namely, “$1$” classifications kicked in the later ages as women were born later. The effect of drought is rather limited in the sense that it makes differences only for earlier ages. For example, the incidence of drought moves up the classification rating at age 14 for cohort 1950; ages 14 and 15 for cohort 1960; ages 15 and 16 for cohort 1970; and ages 16 and 17 for cohort 1980. Figure (ref) now depicts the maximum score classification results using the 95% confidence region. There are more occurrences of non-classification but the effects of drought on classification are visible in 5 instances. Overall, the classification exercises demonstrate the usefulness of our methodology. As before, we do not display classification outcomes under random classification.
To evaluate the effectiveness of our proposed classification rules, we conduct a Monte Carlo experiment. Specifically, we base our experimental design on the first empirical example reported in Section (ref). We retain the same covariate design ($X$) from Section (ref) and generate $Y$ as follows:
where \( U_i = \sigma(X_i) V_i \), with \( V_i \sim N(0,1) \), and \( (\beta_0^{(1)}, \beta_0^{(2)}, \beta_0^{(3)}) = (1, 0.4, -3.7)' \). We consider both a homoskedastic design (\(\sigma(X_i) = 0.5\)) and a heteroskedastic design (\(\sigma(X_i) = 0.2 [1 + (GPA_i/3 + \text{Top Internship}_i)^2 ]\)). The parameter values of \((\beta_0^{(1)}, \beta_0^{(2)}, \beta_0^{(3)})\) are chosen to mimic the empirical results reported earlier and to ensure that the population values of \(g_0(x_j)\) are never zero. The quantile of interest is \(\tau = 0.5\), the confidence level is \(\alpha = 0.05\), and the number of Monte Carlo repetitions is 1,000.
Table (ref) reports the Monte Carlo frequencies of misclassification. Panel A considers the setting in which abstention is permitted. At the population level, an individual with covariate $X_*$ is classified as $Y = 1$ if $c_L > 0$, as $Y = 0$ if $c_U < 0$, and remains unclassified if $c_L \leq 0 \leq c_U$. In the sample, classification follows the same rule, using the estimates $\hat{c}_L$ and $\hat{c}_U$, which are constructed based on the fixed-design asymptotic critical value. A classification error occurs whenever the sample classification differs from the population classification. This setup corresponds to the theoretical discussion of misclassification probabilities in Section (ref).
In Panel A, each row in the table corresponds to a different sample size, where increasing the sample size by a factor of \(c\) corresponds to adding \(c-1\) additional copies of \(X\), with \(c=1,2,3\). The column “Avg. (Pointwise)” reports the average misclassification error across \(J=12\) support points (six GPA values for each Top Internship status). Specifically, in each Monte Carlo repetition and for each support point, we check whether the sample classification differs from the population classification, and then average these discrepancies across both repetitions and support points. As an alternative measure, the column “All (Uniform)” reports whether, for each Monte Carlo repetition, any misclassification occurs across all support points. Since “All (Uniform)” imposes a stricter criterion, the reported misclassification errors are higher in this column.
Although the exact misclassification error levels depend on the noise structure in \(U_i\), the results show a clear trend: both measures of misclassification error decrease as the sample size increases. This illustrates that as the sample size grows, population bounds increasingly dominate sampling errors, reinforcing the reliability of the proposed classification approach.
Panel B in Table (ref) considers the scenario in which abstention is not allowed but random classification is permitted. In this case, at the population level, an individual with covariate $X_*$ is classified as $Y = 1$ if $c_L > 0$, as $Y = 0$ if $c_U < 0$, and is classified at random (with equal probability) if $c_L \leq 0 \leq c_U$. In the sample, classification follows the same rule using the same randomization device. As before, a classification error occurs whenever the sample classification deviates from the population classification. In other words, while the definition of population classification differs from that in Panel A, the definition of classification error remains unchanged. The theoretical analysis relevant to this case is presented in Section (ref). These simulation results are consistent with the findings in Section (ref), in the sense that misclassification errors are smaller in magnitude, as implied by Theorem (ref).
Panel C in Table (ref) compares the population classification rule---identical to that in Panel B, using the same randomization device---with a sample classification rule based solely on the sign of the sample frequency of $f(x) = \mathbb{P}(Y=1 \mid X=x) - \tau$. The resulting classification errors are large and exhibit little to no improvement as $n$ increases. This is because the sample frequencies of $f(x)$ are already estimated with high precision at $n = 2880$, leaving limited scope for further gains. These results underscore the value of extrapolation through the maximum score model, even when data are available in every cell. The advantages will become even more pronounced in settings with sparse or missing observations.
We have shown that scalable inference based on linear programming can be conducted for maximum score estimation. We have demonstrated the usefulness of our proposal of credible binary classification rules. In our empirical examples, the finite sample inference methods did not provide informative bounds but the asymptotic inference methods did. One natural follow-up question is whether it would be possible to improve the confidence regions constructed via the Bonferroni correction. This is an interesting topic for future research.