Learning Optimized Risk Scores

1. Introduction

• Risk scores let users make quick predictions and choose among operating points, but constraints on model properties have made development largely heuristic.Such approaches may violate requirements or perform poorly, and without a formal guarantee it can be difficult to tell whether poor performance reflects the heuristics or restrictive constraints.Source: §1 · p. 2
• An optimality certificate can show whether a score is best among those meeting its constraints, helping distinguish poor performance from requirements that are too restrictive.Comparing certified scores under different constraint sets supports informed choices between models.Source: §1 · p. 3
• RiskSLIM optimizes feature selection and small integer coefficients while handling application-specific constraints and providing an optimality certificate.The proposed lattice cutting plane algorithm is designed for non-convex problems and scales linearly with the number of samples; specialized techniques target feasible solutions, optimality gaps, and data-related computation.Source: §1 · pp. 3–4
• Experiments report best-in-class risk-score performance in minutes, and the paper applies the approach to customized ICU seizure prediction with Massachusetts General Hospital.The authors also present heuristic methods intended to address pitfalls in common approaches.Source: §1 · p. 4

1.1 Related Work

• RiskSLIM targets calibrated risk assessment, unlike SLIM scoring systems designed for decision-making; the paper also positions its algorithm for constrained learning beyond risk scores.The related-work discussion describes a predecessor that cannot prove optimality and emphasizes certified solutions or small optimality gaps as a distinctive feature of this work.Source: §1.1 · pp. 5–6

2. Risk Score Problem

• Risk scores represent predictions through a linear score whose feature coefficients are points, then convert that score to estimated risk using a logistic link.The input consists of n training examples with feature vectors and binary class labels.Source: §2 · p. 7

Model Desiderata

• Calibration is the primary performance objective, while AUC is reported as an auxiliary metric because class imbalance can make trivial scores appear to have low calibration error.Calibration is assessed with reliability diagrams and summarized by expected calibration error; rank accuracy is assessed using AUC.Source: Model Desiderata · p. 7
• RiskSlimMINLP minimizes logistic loss plus an ℓ0 penalty over user-provided feasible coefficient vectors, with C0 controlling the fit–sparsity trade-off.The constraints can restrict coefficients to small integers and encode application-specific requirements.Source: Model Desiderata · p. 8
• RiskSLIM is an optimal feasible solution to RiskSlimMINLP and, for sufficiently small C0, has the lowest training logistic loss among feasible models.It is therefore a maximum-likelihood logit model satisfying the required constraints.Source: Model Desiderata · p. 8
• The trade-off parameter can be set small when model size is imposed as a constraint, allowing optimization of logistic loss subject to that size limit.For data-driven model size selection, solving constrained instances across size limits yields models over the full ℓ0-regularization path.Source: Model Desiderata · p. 9
• Although optimizing RiskSlimMINLP is NP-hard, the paper reports that many real-world datasets can be solved to optimality in minutes with runtime scaling linearly in sample size.The authors note that this favorable behavior is empirical, despite worst-case intractability for high-dimensional data.Source: Model Desiderata · p. 9

3.1 Cutting Plane Algorithms

• CPA repeatedly solves a MIP minimizing a cutting-plane approximation of the loss, then adds a cut at the resulting solution to improve the approximation.For convex loss, the approximation improves monotonically and CPA converges in a finite number of iterations.Source: §3.1 · pp. 10, 12
• For fixed dimension, CPA and LCPA scale linearly with sample size because data are used to compute cut parameters, not while solving the surrogate MIP.Computing cut parameters takes O(nd) time per iteration, and users can customize this isolated computation to reduce data-related work.Source: §3.1 · p. 12, Figure 6 · p. 18
• Standard CPA can stall when non-convex surrogate problems become increasingly difficult to solve to optimality, risking poor solutions and invalid bounds if solved only approximately.On the illustrated d = 20 instance, CPA stalls at iteration 86 after six hours with a large optimality gap.Source: §3.1 · pp. 13–14, Figure 4 · p. 13

3.2 The Lattice Cutting Plane Algorithm

• LCPA avoids stalling by adding cuts and computing lower bounds without optimizing a non-convex surrogate.Its branch-and-bound search solves surrogate LPs over regions, splitting fractional solutions and pruning infeasible or provably suboptimal regions.Source: §3.2 · pp. 14, 16
• LCPA terminates after finitely many iterations and returns an optimal solution; for finite coefficient set L, it uses at most |L| cuts and processes at most 2|L| − 1 nodes.The finite-search guarantee applies for any training dataset and positive trade-off parameter.Source: §3.2 · p. 17

3.3 Performance Comparison with MINLP Algorithms

• LCPA finds an optimal or near-optimal solution with a small optimality gap on almost all tested instances, while CPA stalls for d ≥15 and MINLP solvers struggle on larger instances.The commercial solver fails to converge within six hours on larger instances; Figure 6 compares the algorithms on difficult synthetic cases.Source: §3.3 · p. 18, Figure 6 · p. 18

4. Algorithmic Improvements

• The algorithmic improvements also include DCD polishing of solver-found integer solutions and ChainedUpdates calls when LCPA changes either bound.Appendix techniques add initialization and reductions in data-related computation.Source: §4 · p. 19

4.1 Discrete Coordinate Descent

• DCD polishes integer solutions by changing one coefficient at a time to improve the objective, terminating at a 1-opt solution.Golden section search reduces the coordinate step-size search from nd|L_j| to nd log_2 |L_j| flops per iteration.Source: §4.1 · p. 19

4.2 Sequential Rounding

• SequentialRounding repeatedly chooses the best up-or-down rounding for a remaining coefficient, then DCD polishes the resulting integer solution.In the LCPA experiment, this combination can reduce the time to find a high-quality risk score and attain a lower optimality gap than the basic implementation.Source: §4.2 · pp. 20–21, Figure 8 · p. 22

4.3 Chained Updates

• ChainedUpdates repeatedly tightens bounds on the objective, loss, and number of nonzero coefficients, restricting the search region without discarding the optimum.It applies dependent bound updates until none can be improved, regardless of which bound was updated first.Source: §4.3 · pp. 21, 23, 24
• On synthetic data with d = 30 and n = 50,000, ChainedUpdates can considerably improve LCPA’s lower bound and optimality gap.Figure 10 shows the performance profile for the basic implementation and the version with ChainedUpdates.Source: §4.3 · p. 24, Figure 10 · p. 24

5.1 Setup

• The benchmark used six public datasets and compared RiskSLIM with six post-processing baselines for integer coefficients and model-size limits Rmax from 2 to 10.The baselines began with penalized logistic regression models built using Lasso, Ridge, or Elastic Net.Source: §5.1 · pp. 25–26, Table 2 · p. 25

5.2 Discussion

• Lower-loss models typically have better calibration and AUC, and the authors report this pattern generalizing to test data for the simple model class.RiskSLIM optimizes loss over exact model-form constraints, attaining minimal or near-minimal loss.Source: §5.2 · p. 27
• RiskSLIM had the best 5-CV mean test CAL on 5/6 datasets and best 5-CV mean test AUC on 5/6; no method beat it on both (Table 3; Figures 11–12).Source: §5.2 · p. 27, Figure 11 · p. 28, Figure 12 · p. 29
• A trivial model can have misleadingly low CAL, so the experiments select free parameters by 5-CV mean test AUC rather than minimizing CAL.The cited example has training CAL of 0.7% and training AUC of 0.500.Source: §5.2 · p. 30
• Reliability diagrams reveal monotonicity violations and irregular or limited risk coverage; Platt scaling spreads predictions but cannot repair heuristic-induced problems such as low AUC.Source: §5.2 · pp. 31–32, Figure 14 · p. 32
• Rounding can lower AUC by zeroing features, rescaled rounding can hurt calibration, and unit weighting can produce poor calibration and unpredictable performance.These approaches may have less noticeable effects on AUC than on calibration.Source: §5.2 · p. 32
• Pooled approaches improve calibration and rank accuracy over traditional approaches by selecting among post-processed models and using loss-sensitive heuristics such as SequentialRounding and DCD.Pooling adds robustness to heuristic failures, while loss-sensitive heuristics can produce lower-loss scores.Source: §5.2 · p. 33
• RiskSLIM was certifiably optimal or had small optimality gaps on every dataset in under 20 minutes; cutting-plane computation took under 1% of runtime.LCPA scales linearly with sample size, and the authors expect similar results on larger datasets.Source: §5.2 · p. 33

6.1 Problem Description

• The seizure-prediction task used 5,427 recordings from 41 hospitals, with 87 input variables and a seizure outcome prevalence of 12.5%.Inputs included medical history, neurological symptoms, and five standard cEEG patterns.Source: §6.1 · pp. 36–37
• The collaborators required calibrated risk estimates, a model size of at most four variables, monotonicity for known risk factors, and restrictions on feature composition and encoding.These operational requirements were intended to support validation and usability by physicians.Source: §6.1 · pp. 37–38

6.2 Discussion

• Only RiskSLIM and pooled methods found feasible scores under the full constraints; traditional methods could violate constraints after rounding and had weaker performance even under simpler constraints.With only model-size and monotonicity constraints, traditional methods had test AUC at most 0.761 or test CAL at least 7.0%.Source: §6.2 · p. 38
• RiskSLIM’s risk predictions were monotonic and stayed within the fold-model prediction boundaries, unlike other models that could violate monotonicity or vary substantially across folds.Such violations could erode trust; for example, the PooledSeqRd model could imply higher seizure risk at score 3.5 than at score 4.0.Source: §6.2 · p. 38
• RiskSLIM achieved 5-CV mean test CAL/AUC of 2.5%/0.801, versus 2.8%/0.745 for the best heuristic risk score.The comparison is reported in Table 4.Source: §6.2 · p. 38, Table 4 · p. 39
• RiskSLIM required checking one cEEG pattern, while other scores could require checking three patterns, and PooledSeqRd* also required estimating LPD frequency.The collaborators considered whether a five-feature model’s slight AUC improvement justified the additional evaluation time for doctors.Source: §6.2 · pp. 39–40
• Pooled methods selected feasible models from a large pool, requiring nested cross-validation and 33,000 fits; only 12% of their instances met all constraints.Parameter-tuning approaches also offered no guarantee that the final model would satisfy every constraint.Source: §6.2 · p. 40
• Small integer coefficients can make operating points easier to choose and, with binary inputs, allow decision rules to be written as Boolean rules.The paper contrasts this with real-valued coefficients and inputs, for which extracting a Boolean function is difficult.Source: §6.2 · pp. 40–41

7. Concluding Remarks

• Ad hoc risk-score development can violate important requirements, lack performance guarantees, and incur hidden costs such as specialized training pipelines.Such development may lead to manual adjustments or models built without data.Source: §7 · p. 44
• The approach formulates risk-score learning as empirical risk minimization with exact feature selection, small integer coefficients, and application-specific constraints, solved using the new LCPA cutting plane algorithm.LCPA is described as scaling linearly with the number of samples and as applicable to other empirical risk minimization problems with non-convex regularizers or constraints.Source: §7 · p. 44
• LCPA trained certifiably optimal risk scores for real-world datasets in minutes, and these models often achieved best-in-class calibration and rank accuracy.The models also avoid pitfalls of heuristics used in practice.Source: §7 · p. 44
• Optimality certificates can help practitioners understand how application-specific constraints affect predictive performance.The approach also lets practitioners customize risk scores without post-processing.Source: §7 · p. 44

Appendix A. Omitted Proofs

• LCPA searches the feasible region and discards a node only when its surrogate is infeasible or its objective bound rules out an optimal integer-feasible solution.This is the stated basis for the claim that LCPA encounters the optimal solution.Source: Appendix A · p. 53
• The proof bounds the number of cuts by the number of integer-feasible solutions and bounds processed nodes using the depth of the branch-and-bound tree.The split rule partitions regions using integer-valued bounds on a coefficient.Source: Appendix A · p. 53
• The loss is bounded because the coefficient set is bounded, the data are discrete, and the normalized logistic loss is continuous.The proof then establishes lower and upper bounds on the loss over the feasible coefficient set.Source: Appendix A · p. 54

Appendix B. Small Regularization Parameters do not Influence Accuracy

• For sufficiently small C0, the regularized objective selects a smallest model among the most accurate feasible models; the paper uses C0 = 10^-8 to avoid numerical issues with the MIP solver.The required smallness threshold is not known in advance because it depends on quantities as difficult to compute as solving the risk-score problem.Source: Appendix B · p. 56

Appendix C. Background on Risk Scores

• Risk scores are used across domains partly because they are easy to use, understand, and validate.The appendix supports this claim with quotations from authors in medicine, criminal justice, and finance.Source: Appendix C · p. 59, Table 6 · p. 59

Importance of Operational Constraints

• Operational requirements can include explicit clinical rules and harder-to-formalize qualities such as sensibility, usability, and face validity.The cited clinical example requires emergent presentations to be directed to coronary care rather than telemetry admission.Source: Importance of Operational Constraints · pp. 59–60

Approaches to Model Development

• Common risk-score construction heuristics include feature selection, coefficient rounding, expert judgment, and unit weighting.Some approaches combine statistical techniques with expert choices about scaling or converting variables to categories.Source: Approaches to Model Development · p. 60

Critical Analysis of a Real-World Training Pipeline

• The TIMI pipeline illustrates concerns with sequential development: steps can optimize conflicting objectives, fail to find global optima, use unvalidated parameters, or leave data unused for final fitting.Its final coefficients are set to unit weights rather than optimized.Source: Critical Analysis of a Real-World… · p. 61

• The appendix supplies additional computational-experiment details for Sections 3.3 and 4.Source: Appendix D · p. 62

D.1 Simulation Procedure for Synthetic Datasets

• The synthetic datasets derive from the breastcancer dataset, selected for solvable RiskSlimMINLP instances, prior study, and public availability.The original data contain 683 samples and 9 features.Source: §D.1 · p. 62
• The procedure builds a largest dataset by replicating original features and samples with normally distributed noise, then forms smaller datasets as nested subsets.The largest dataset has n = 5×10^6 and d = 30; nested sets preserve shared samples and features.Source: §D.1 · p. 62
• Replicated, highly correlated features make instances with d > 9 difficult because feature selection yields exponentially many slightly suboptimal solutions.Source: §D.1 · p. 62
• A solved smaller dataset can bound the optimum for an unsolved larger-feature dataset because the latter contains all the former’s features.For example, the optimum at (d, n) = (20, 10^6) is no greater than at (10, 10^6).Source: §D.1 · p. 62

D.2 Setup on the Performance Comparison in Section 3.3

• The benchmark instance uses C0 = 10^-8, λ0 ∈ {−100, 100}, and λj ∈ {−10, …, 10}, with up to six hours on a 3.33 GHz Intel Xeon CPU.The machine had 16GB of RAM.Source: §D.2 · p. 64
• The comparison includes CPA, LCPA, ActiveSetMINLP, InteriorMINLP, and InteriorCGMINLP.Source: §D.2 · p. 64
• If an algorithm fails to return a certifiably optimal solution within six hours, the reported result is its best feasible solution; MINLP algorithms use Knitro and CPA/LCPA use CPLEX.The formulation represents the cutting-plane approximation with cut constraints and auxiliary variables for objective, loss, and ℓ0 norm.Source: §D.2 · p. 64

D.3 Results for MINLP Algorithms

• All benchmarked MINLP algorithms perform similarly on difficult synthetic instances, while ActiveSetMINLP solved the most instances to optimality.Source: Figure 27 · p. 65, §D.3 · p. 65

E.1 Initialization Procedure

• The LCPA initialization procedure improves the lower bound and optimality gap over the course of the algorithm.It combines CPA cuts and a lower bound, rounded and polished integer solutions for an upper bound, and chained updates to tighten bounds.Source: §E.1 · p. 66

E.2.1 Fast Loss Evaluation via a Lookup Table

• When features and coefficients are bounded, discrete, and regularly spaced, their scores can be represented as bounded integers and logistic-loss values precomputed in a lookup table.Source: §E.2.1 · p. 68

E.2 Reducing Data-Related Computation

• The lookup table replaces repeated loss calculations with fast lookups, can fit in cache, and can be reduced as Rmax changes at an O(n) update cost.Source: §E.2.1 · p. 68

E.2.2 Faster Rounding Heuristics via Subsampling

• Subsampling targets rounding heuristics that require multiple loss evaluations, which can otherwise waste computation when runs fail to improve the incumbent.SequentialRounding is one example; validating an incumbent update still requires evaluating the full training dataset.Source: §E.2.2 · pp. 68–69
• Theorem 11 bounds the difference between full-data and sampled-data loss, with a tighter guarantee as the sample size approaches the dataset size.Its normalization term is the maximum loss range over the finite coefficient set.Source: §E.2.2 · pp. 69–70
• The bound can guide the sample size so an incumbent update on the subsample is likely to yield an update on the full dataset.It can also assess the probability that a proposed update on sampled data becomes an actual update.Source: §E.2.2 · pp. 70–71
• The normalization term can be recomputed during LCPA for each real-valued solution or when the solver restricts the feasible coefficient set.Source: §E.2.2 · p. 70

Appendix F. Additional Experimental Results

• Table 7 summarizes calibration and AUC statistics for risk scores with coefficients from −5 to 5 and model size at most 5.The caption defines test statistics as five-fold cross-validation means and training statistics for the final full-dataset fit.Source: Table 7 · p. 72

Appendix G. Supporting Material for Seizure Prediction

• The seizure-prediction appendix provides supporting material, including a list of training-dataset input variables.Table 8 lists variable names, values, and sign constraints.Source: Appendix G · p. 73, §G.1 · p. 73, Table 8 · p. 73

No Redundant Categorical Variables

• For sex and selected cEEG pattern groups, the requirements allow either an aggregate variable or specified component variables.Source: No Redundant Categorical Variables · p. 74

Frequency in Continuous Encoding or Thresholded Encoding

• For six frequency variables, the requirements allow continuous encoding or thresholded encoding.Source: Frequency in Continuous Encoding or… · p. 74

Limited # of Thresholds for Thresholded Variables

• Thresholded frequency variables are limited to at most two selected thresholds for each listed frequency measure.Source: Limited # of Thresholds for… · pp. 74–75

Any cEEG Pattern or Specific cEEG Patterns

• The requirements allow aggregate or pattern-specific stimulus-induced and superimposed variables, and alternatives for frequency variables, including using none.Source: Any cEEG Pattern or Specific cEEG… · p. 75

G.3 Additional Experimental Results

• 33K models are required for the other methods because they use nested cross-validation to select a final risk score and pair it with an unbiased performance estimate.Source: Table 9 · p. 75