Best Subset Binary Prediction

Le‐Yu Chen, Sokbae Lee

Abstract

This paper addresses the challenge of variable selection in binary prediction by integrating Manski’s maximum score estimator with best subset selection. By reformulating this traditionally NP-hard problem as a Mixed Integer Optimization (MIO) task, the authors provide a computationally feasible and theoretically grounded framework. We establish non-asymptotic risk bounds that are minimax rate-optimal and demonstrate the method's efficacy through simulations and an empirical study on transportation mode choice, achieving significant computational speedups over existing benchmarks.

Introduction

In fields ranging from economics to medicine, researchers frequently encounter the need to predict binary outcomes—such as whether a patient will respond to a treatment or whether a commuter will choose public transit. While traditional parametric models like Logit and Probit are widely used, they rely on strict assumptions regarding the distribution of error terms. When these assumptions are violated, the resulting predictions can be biased and unreliable.

Manski’s maximum score estimator (1975, 1985) offers a powerful semiparametric alternative that avoids these distributional pitfalls. However, it has historically faced two significant hurdles: it is computationally NP-hard due to its non-smooth, piecewise constant objective function, and its theoretical properties in high-dimensional settings (where the number of potential predictors $p$ exceeds the sample size $n$) have remained under-explored. This paper introduces a framework to overcome these barriers by leveraging modern optimization techniques.

The PRESCIENCE Framework

The authors propose a procedure termed PRESCIENCE (aPpRoximate bEst S(C)ubset maxImum scorE biNary prediCtion rulE). This approach is built upon three primary pillars designed to make robust binary prediction both fast and theoretically sound.

1. Mixed Integer Optimization (MIO) Reformulation

The core innovation lies in showing that the maximum score problem can be exactly reformulated as a Mixed Integer Optimization problem. Unlike traditional gradient-based methods that might get trapped in local optima, MIO allows researchers to use state-of-the-art solvers (such as Gurobi or CPLEX) to find the global optimum for the best subset of variables. This effectively tames the NP-hard nature of the objective function.

2. The "Warm-Start" Strategy

To address the inherent complexity of MIO, the authors developed a data-driven heuristic to tighten the search space. By executing preliminary linear programs to establish refined parameter bounds, they can reduce the search space volume by over 99%. This "warm-start" significantly accelerates the solver's ability to reach a solution.

3. Non-Asymptotic Theory

The paper derives new non-asymptotic upper and lower risk bounds for the estimator. The authors prove that PRESCIENCE is minimax rate-optimal when the number of selected variables is fixed. This provides a rigorous guarantee that the estimator converges to the "truth" at the fastest possible rate allowed by the statistical nature of the problem.

Empirical Validation

Monte Carlo Simulations

The method was tested against synthetic datasets designed to mimic high-dimensional challenges (e.g., $p=200, n=100$). In scenarios where the data-generating process was nonlinear or misspecified for standard models, PRESCIENCE significantly outperformed Logit-Lasso and Probit-Lasso. This highlights the advantage of a semiparametric approach: it remains "honest" and accurate even when the underlying noise distribution is unknown.

Work-Trip Transportation Application

The authors applied their method to the classic Horowitz (1993) dataset, which tracks the transportation choices of 842 commuters in Washington, D.C. The goal was to predict mode choice based on travel times, costs, and car ownership.

  • Computational Efficiency: Previous MIO implementations required approximately 10.5 hours to find an exact solution for this dataset. Using the PRESCIENCE framework with refined parameter spaces, the same problem was solved in less than 5 minutes—a speedup of over 100x.
  • Predictive Insights: The model identified car ownership ($CARS$) as the most dominant predictor of mode choice, maintaining high predictive stability even when including complex quadratic interactions between other variables.

Discussion and Limitations

While PRESCIENCE represents a major step forward, the authors note specific areas for future refinement. The "warm-start" strategy, while highly effective for moderate dimensions, loses some efficacy when the number of variables greatly exceeds the sample size ($p \gg n$), as the initial linear constraints become less restrictive. Furthermore, while the method is generally fast, certain constraints (such as selecting a specific small subset of variables) can occasionally lead to longer solve times due to the branching logic of MIO solvers.

Conclusion

By bringing Manski’s maximum score estimator into the era of Mixed Integer Optimization, this research transforms a theoretical curiosity into a practical tool for high-dimensional binary prediction. PRESCIENCE offers a robust, sparse, and computationally efficient alternative to traditional parametric models, backed by minimax optimal theory and demonstrated empirical success.

Summary updated

Abstract

We consider a variable selection problem for the prediction of binary outcomes. We study the best subset selection procedure by which the covariates are chosen by maximizing Manski (1975, 1985)'s maximum score objective function subject to a constraint on the maximal number of selected variables. We show that this procedure can be equivalently reformulated as solving a mixed integer optimization problem, which enables computation of the exact or an approximate solution with a definite approximation error bound. In terms of theoretical results, we obtain non-asymptotic upper and lower risk bounds when the dimension of potential covariates is possibly much larger than the sample size. Our upper and lower risk bounds are minimax rate-optimal when the maximal number of selected variables is fixed and does not increase with the sample size. We illustrate usefulness of the best subset binary prediction approach via Monte Carlo simulations and an empirical application of the work-trip transportation mode choice.
BibTeX
@article{chen2018best,
  author = {Le‐Yu Chen and Sokbae Lee},
  title = {{Best Subset Binary Prediction}},
  journal = {Journal of Econometrics},
  year = {2018},
  doi = {10.1016/j.jeconom.2018.05.001},
}

Loading related content...

Figure