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