Distributionally Robust Regularization of Sparse Integer Programming Trained Learning Models

Sanjeeb Dash; Soumyadip Ghosh; Joao Goncalves; Mark S. Squillante

stat.MLNov 3, 2023

Distributionally Robust Regularization of Sparse Integer Programming Trained Learning Models

Authors: Sanjeeb Dash, Soumyadip Ghosh, Joao Goncalves, Mark S. Squillante

Organizations: IBM Research, Yorktown Heights, NY 10598

Abstract

Building explainable machine learning models is crucial for human users to be able to interpret the proposed statistical relationship obtained from the training data. Mixed-integer optimization formulations are often used to train such models with explicit sparsity constraints, aiming to strike the right trade-off between sparsity and prediction accuracy. Existing methods to find the right choice of sparsity -- e.g., via cross-validation -- are computationally expensive. For convex model training formulations, recent advances in distributionally robust optimization (DRO) provide strong generalization while sidestepping this computational burden. We describe an extension of such regularization via DRO to mixed-integer sparse programs, providing statistical guarantees as a function of an associated sparsity parameter of the formulation. We illustrate the use of this approach in the case of building explainable binary classification models using sets of feature value rules.

Figures & tables

Dataset	Test Performance (%)					Model Complexity
Name	DR	CG	CART	RF	RuleFit	DR	CG	CART
heart	81.0(4.4)	78.9(4.7)	81.6 (4.7)	82.5 (1.4)		22.0(4.2)	11.3 (3.5)	32.0(15.9)
ILPD	71.7 (2.4)	69.6 (2.4)	67.4(3.1)	69.8 (1.0)	69.1(1.5)	10.5 (0.9)	10.9 (5.3)	56.5(21.4)
FICO	71.8(0.6)	71.7(1.0)	70.9(0.6)	73.1 (0.2)	72.7 (0.6)	21.5(3.9)	13.3 (8.0)	155.0(53.9)
ionosphere	93.2 (3.5)	90.0(3.5)	87.2(3.5)	93.6 (1.4)	89.2(3.7)	26.5(3.4)	12.3 (5.9)	46.1(8.2)
liver	62.0 (2.8)	59.7 (4.7)	55.9(2.7)	60.0 (1.6)	61.5 (5.2)	29.0(1.9)	5.2 (2.4)	60.2(30.6)

Table 1: (Left) Classification Performance over Unseen Test Data by Five Competing Methods and (Right) Complexity of Models from Three Explainable Methods for Seven UCI Repository Datasets and the FICO Dataset. (Last Row:) Mean Rank of Competing Methods (exclude heart). All Results presented with Mean and

95\%

CI.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Computation Time		Relative DR
Name	DR	CG	Improvement
heart	1431.73(17.91)	6015.66(115.65)	4.2
ILPD	2136.25(25.86)	11868.06(333.90)	5.6
FICO	9548.59(98.22)	42250.38(691.78)	4.4
ionosphere	6008.45(16.12)	23168.82(093.65)	3.9
liver	1661.16(12.84)	6472.05(093.28)	3.9

Appendix

Table 2: Comparison of Computation Times Between our DR Approach and the CG Approach to Solve One Training Run for seven UCI Repository Datasets and the FICO Dataset, Averaged over ten Partition Permutations. All Results presented with a Mean and a

95\%

Confidence Interval.

Dataset	Test Performance (%)		Model Complexity
Name	DR	CG	DR	CG
heart	81.0 (4.4)	78.9(2.7)	22.0(4.2)	21.7 (4.1)
ILPD	71.7 (2.4)	70.6(2.0)	10.5 (0.9)	10.5 (0.9)
FICO	71.8 (0.6)	70.9(0.6)	21.5(3.9)	21.2 (4.2)
ionosphere	93.2 (3.5)	88.5(3.8)	26.5(3.4)	25.2 (3.5)
liver	62.0 (2.8)	57.9(5.3)	29.0(1.9)	28.8 (1.8)

Appendix

Table 3: Results for CG when Complexity Observed in DR Results are Imposed as Constraints on CG.

Dataset	Test Performance (%) of DR		Model Complexity of DR		$n$ , number of Iterates of DR
Name	${\mathfrak{C}}^{\prime}=5$	${\mathfrak{C}}^{\prime}=10$	${\mathfrak{C}}^{\prime}=5$	${\mathfrak{C}}^{\prime}=10$	${\mathfrak{C}}^{\prime}=5$	${\mathfrak{C}}^{\prime}=10$
heart	81.0 (4.4)	79.6(5.4)	22.0 (4.2)	30.0(0.0)	31.7 (4.2)	35.2(4.1)
ILPD	71.7 (2.4)	69.8(3.2)	10.5 (0.9)	26.0(3.0)	26.0 (0.0)	26.4(0.4)
FICO	71.8 (0.6)	71.3(0.9)	21.5 (3.9)	29.0(1.9)	36.2(5.3)	33.2 (4.4)
ionosphere	93.2 (3.5)	93.0(2.4)	26.5 (3.4)	30.0(0.0)	45.1(3.7)	37.1 (5.4)
liver	62.0 (2.8)	60.4(6.8)	29.0 (1.9)	30.0(0.0)	38.1(5.2)	32.9 (5.5)

Appendix

Table 4: Sparse Ensembles Constructed from Low (

{\mathfrak{C}}^{\prime}=5

) Complexity DNF Models are Compared to Ensembles Constructed from Moderate (

{\mathfrak{C}}^{\prime}=10

) Complexity DNF Models.

Dataset	Test Performance (%) of DR		Model Complexity of DR		$n$ , number of Iterates of DR
Name	cutoff $=30$	cutoff $=60$	cutoff $=30$	cutoff $=60$	cutoff $=30$	cutoff $=60$
heart	81.0 (4.4)	81.0 (4.1)	22.0 (4.2)	38.5(8.5)	31.7 (4.2)	36.7(5.1)
ILPD	71.7 (2.4)	71.7 (2.4)	10.5 (0.9)	10.5 (0.9)	26.0 (0.0)	26.0 (0.0)
FICO	71.8 (0.6)	71.8 (0.7)	21.5 (3.9)	24.5(7.1)	36.2 (5.3)	38.8(5.8)
ionosphere	93.2 (3.5)	92.9(3.7)	26.5 (3.4)	29.5(6.0)	45.1 (3.7)	47.2(2.3)
liver	62.0 (2.8)	61.7(2.9)	29.0 (1.9)	39.0(7.6)	38.1 (5.2)	39.0(4.5)

Appendix

Table 5: Aggregate Complexity of Sparse Ensemble Determined by ( 19 ) with a Cutoff at

{\mathfrak{C}}\leq 30

Compared to a Cutoff at

{\mathfrak{C}}\leq 60

Dataset	Test Performance (%) of DR		Model Complexity of DR		$n$ , number of Iterates of DR
Name	$\rho=0.05$	$\rho=0.5$	$\rho=0.05$	$\rho=0.5$	$\rho=0.05$	$\rho=0.5$
heart	81.0(4.4)	81.9 (5.3)	22.0 (4.2)	30.0(0.0)	31.7 (4.2)	38.2(3.7)
ILPD	71.7(2.4)	71.8 (2.3)	10.5 (0.9)	10.5 (0.9)	26.0 (0.0)	26.0 (0.0)
FICO	71.8 (0.6)	71.6(0.8)	21.5(3.9)	17.5 (4.4)	36.2(5.3)	31.8 (2.6)
ionosphere	93.2(3.5)	93.5 (3.9)	26.5 (3.4)	30.0(0.0)	45.1 (3.7)	45.5(5.6)
pima	76.7 (2.8)	76.7 (3.6)	22.0 (4.2)	25.5(3.5)	29.4 (2.5)	44.1(3.6)

Appendix

Table 6: DRO Radius Parameter

\rho

is varied from

0.05

0.5

Dataset	Test Performance (%) of DR			Model Complexity of DR			$t$ , number of Iterates of DR
Name	$10$	$20$	$30$	$10$	$20$	$30$	$10$	$20$	$30$
heart	80.6(3.4)	81.0 (4.4)	80.0(4.4)	23.0(4.4)	22.0 (4.2)	25.0(3.9)	20.5 (2.3)	31.7(4.2)	43.6(3.5)
ILPD	71.7 (2.4)	71.7 (2.4)	71.7 (2.4)	10.5 (0.9)	10.5 (0.9)	10.5 (0.9)	16.0 (0.0)	26.0(0.0)	36.0(0.0)
FICO	72.1 (0.7)	71.8(0.6)	72.1 (0.7)	23.0(3.7)	21.5 (3.9)	24.5(3.5)	21.8 (3.2)	36.2(5.3)	44.0(3.3)
ionosphere	92.6(3.6)	93.2(3.5)	93.5 (3.5)	22.5 (4.6)	26.5(3.4)	28.0(2.5)	22.9 (3.7)	45.1(3.7)	49.1(1.7)
liver	62.0 (3.3)	62.0 (2.8)	61.4(2.8)	28.0 (2.5)	29.0(1.9)	30.0(0.0)	24.6 (4.2)	38.1(5.2)	46.1(3.0)

Appendix

Table 7: Minimum Number of Consecutive Iterations of No-Improvement to Observe in Step 4 of Sparse Ensembling Algorithm before Stopping Outer Iterations: Test Performance, Model Complexity and number

t

of Outer Iterations

Panel of Figure 1 — Figure 1: Iterate Trajectories of Percentage Correctly Classified in Test and Training Datasets by Sparse Ensembling Algorithm over four dataset instances.

Rule-Based Classification

See all 21 papers

Probabilistic Linear Explanations
Sep 16, 2026Frederic Koriche, Jean-Marie Lagniez, Chi TranExplainable Artificial Intelligence Mixed-Integer QP
Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France
Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
Oct 14, 2026Thomas Pammer, Johannes Fürnkranz, Markus SinnlBoolean Function Learning Interpretable ML
Institute for Application-Oriented Knowledge Processing (FAW), Johannes Kepler University Linz, Austria · LIT AI Lab, Johannes Kepler University Linz, Austria · Institute of Business Analytics & Technology Transformation/JKU Business School, Johannes Kepler University Linz, Austria
Efficient Cross-Validation for Sparse Linear Regression
Jun 26, 2023Ryan Cory-Wright, Andrés GómezModel Selection Mixed-Integer Linear Programming
Department of Analytics, Marketing and Operations, Imperial Business School, London, UK · Department of Industrial and Systems Engineering, Viterbi School of Engineering, University of Southern California, CA

Sep 16, 2026J/K move · Enter open · S save

Probabilistic Linear Explanations

Frederic Koriche, Jean-Marie Lagniez, Chi Tran

Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France

Explainable Artificial Intelligence Mixed-Integer QP

Open paper AskPDF arXiv

Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget

k

. We show that minimizing the relevance error for such explanations is \ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any

k

-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.

Abstract

Rule-Based Classification

Explore similar work

Probabilistic Linear Explanations

Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming

Efficient Cross-Validation for Sparse Linear Regression