TL;DR
This paper introduces a robust framework for binary prediction that combines "best subset" variable selection with Manski’s classic maximum score estimation. By reformulating this NP-hard problem as a Mixed Integer Optimization (MIO), the authors achieve minimax rate-optimal performance in high-dimensional settings and demonstrate a 100x computational speedup over previous methods.
What Problem Does This Paper Address?
In fields like economics and medicine, researchers often need to predict binary outcomes (e.g., "Will a commuter take the bus or drive?") using a large pool of potential variables. Traditional methods like Logit or Probit are popular but rely on strict assumptions about the distribution of "noise" in the data. Manski’s maximum score estimator is a powerful semiparametric alternative that avoids these assumptions, but it has historically faced two massive hurdles:
- Computational Complexity: The objective function is non-smooth and piecewise constant, making it "NP-hard" to solve. Finding the best subset of variables (the $\ell_0$ constraint) only adds to the difficulty.
- High-Dimensionality: Proving that a model will perform well when the number of potential predictors ($p$) is much larger than the sample size ($n$) is theoretically challenging for non-smooth estimators.
Methods
The authors propose a procedure they call PRESCIENCE (aPpRoximate bEst S(C)ubset maxImum scorE biNary prediCtion rulE). Their approach relies on three key pillars:
- MIO Reformulation: They show that the maximum score problem can be exactly mapped to a Mixed Integer Optimization problem. This allows researchers to use state-of-the-art solvers (like Gurobi or CPLEX) to find global optima rather than getting stuck in local ones.
- The "Warm-Start" Strategy: To solve the MIO faster, the authors use a data-driven heuristic to tighten the search space. By running simple linear programs first to establish refined parameter bounds, they reduce the "volume" of the search space by over 99%, leading to dramatic speedups.
- Non-Asymptotic Theory: They derive new upper and lower risk bounds, proving that their method is minimax rate-optimal. This means that in a specific statistical sense, no other estimator can converge to the "truth" faster than this one when the number of selected variables is fixed.
Datasets
The paper validates the method using two primary sources:
- Monte Carlo Simulations: Synthetic datasets designed to test high-dimensional performance (e.g., $p=200$ potential variables with only $n=100$ observations).
- Work-Trip Transportation Dataset: A real-world dataset from Horowitz (1993) containing 842 observations of commuters in Washington, D.C. Variables include travel time differences, transit fares, and car ownership ($CARS$).
Key Insights and Ideas
- Hardware + Algorithms = Relevance: The authors argue that the maximum score approach, once considered a "theoretical curiosity" due to its slow computation, is now empirically relevant thanks to modern MIO solvers and faster CPUs.
- Robustness to Misspecification: In simulations where the true data-generating process was nonlinear, PRESCIENCE significantly outperformed Logit-Lasso and Probit-Lasso. Because it doesn't assume a specific error distribution, it is far more "honest" when the model is slightly wrong.
- The Power of Sparsity: The "best subset" approach (choosing exactly $q$ variables) often yields more interpretable and stable models than "shrinkage" methods like Lasso, which can sometimes include many irrelevant "noise" variables.
Key Results
- Massive Speedup: On the Horowitz dataset, previous MIO implementations took 10.5 hours to find an exact solution. Using the authors' refined parameter space and modern solvers, the same problem was solved in less than 5 minutes—a factor of over 100x improvement.
- Predictive Accuracy: In high-dimensional simulations ($p > n$), the method maintained high "Oracle" selection rates (identifying the true relevant variables) while keeping the out-of-sample risk low.
- Empirical Finding: In the transportation application, the model revealed that car ownership is the single most dominant predictor of mode choice, even when allowing for complex quadratic interactions between travel times and costs.
Limitations and Future Work
- The $p > n$ Warm-Start Gap: The authors acknowledge that their "warm-start" strategy (tightening the parameter space) doesn't work well when the number of variables exceeds the sample size, as the initial linear constraints become ineffective.
- Scaling Sparsity: The current minimax optimality proof assumes the number of selected variables ($s$) is fixed. Extending this theory to cases where the number of selected variables grows alongside the sample size remains an open research question.
- Computational Spikes: While generally fast, certain "middle-ground" constraints (e.g., selecting exactly 3 variables out of 10) can occasionally trigger much longer solve times due to the branching logic of MIO solvers.
Summary updated