Pith. sign in

REVIEW 10 minor 15 references

Responsible Machine Learning via Mixed-Integer Optimization

T0 review · 0 major / 10 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This tutorial argues that mixed-integer optimization lets modelers encode interpretability, fairness, and robustness directly as constraints in the training problem, preserving accuracy while providing certified guarantees.

desk verdict A solid, clearly-written tutorial on MIO for responsible ML; no new results, but a useful map of the field with an honest treatment of scalability limits. read the letter →

arxiv 2505.05857 v3 pith:IXTXDJ65 submitted 2025-05-09 cs.LG math.OCstat.ML

Nathan Justin , Qingshi Sun , Andrés Gómez , Phebe Vayanos This is my paper · ORCID
classification cs.LGmath.OCstat.ML MSC 90C1168T05
keywords mixed-integeroptimizationinterpretablemachinelearningfairadversarialrobustnessdistributionshiftcounterfactualexplanationsriskscorescausalinference
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This tutorial argues that mixed-integer optimization (MIO) is a unified framework for responsible machine learning: instead of patching fairness, transparency, or robustness onto a trained model, the modeler writes them as hard constraints or exact penalties inside the learning problem itself. The authors survey explicit MIO formulations for sparse linear and logistic regression, risk scores, optimal decision trees, rule lists and decision sets, sparse PCA, Bayesian network learning, counterfactual explanations, outlier-robust regression, adversarial verification, fair classification and regression, and prescriptive treatment assignment. Their running demonstration is that the same binary-variable machinery carries every one of these goals, and that solving the resulting problems to optimality yields models that are accurate and responsible at once, for example lifting the share of large-Hispanic cities with below-average predicted crime from 23% to 37% while the coefficient of determination drops only from 0.63 to 0.60. The sympathetic reader should take away that MIO is a practical route to models with guaranteed properties, with scalability as the main open bottleneck.

What carries the argument

The central machinery is the binary decision variable used to encode every combinatorial aspect of responsibility: which features enter a sparse model, which node routes a data point through a tree, which points are trimmed as outliers, which ReLU neurons are active, which individuals receive a favorable outcome, and which treatment a policy assigns. The second load-bearing component is relaxation strengthening, especially the perspective reformulation that replaces big-M products with rotated-cone constraints of the form $\theta_j^2 \le z_j r_j$, plus dynamic outer approximations of the logistic loss and constraint-generation schemes for robust counterparts. These devices tighten the continuous relaxation, which the paper identifies as a better predictor of practical solvability than the number of variables or constraints, and they determine whether branch-and-bound can close the gap to optimality at scale.

What would settle it

Take the fair sparse-regression problem with $n = 50{,}000$ observations and $d = 500$ features, solve it with a modern MIO solver using the perspective reformulation, and record the optimality gap after one hour; if the gap remains above 10% while the same solver closes the unconstrained sparse-regression instance to under 1% in minutes, the tutorial's implicit premise that responsible constraints can be added without giving up practical solvability fails in exactly the regime where fairness matters most.

Watch

Extended reading notes

Core claim

On its own terms, the central claim is that most responsible-ML desiderata reduce to constrained mixed-integer optimization problems, and that modern MIO solvers can often solve these to optimality or with quality guarantees. For interpretability, the paper presents L0-sparse regression with perspective reformulations, integer-valued risk scores, flow-based formulations for optimal classification trees, and column-generation approaches for decision sets. For robustness, it shows how outlier trimming becomes a binary selection problem, how ReLU activation constraints are linearized with binary variables for network verification, and how distributional robustness is handled through delayed constraint generation when duality fails. For fairness, it encodes statistical parity, conditional statistical parity, predictive equality, equal opportunity, and equalized odds as linear constraints on binary favorable-outcome indicators, and extends them to fair prescriptive trees. The unifying discovery is that all of these combinatorial structures sit naturally inside the same MIO template, so advances in relaxation strength and branch-and-bound immediately transfer across the responsible-ML landscape.

Load-bearing premise

The load-bearing premise is that the MIO formulations surveyed in the tutorial can be solved to acceptable optimality at the dataset sizes that matter in practice; the paper itself notes that fairness constraints require at least $|I|$ binary variables, so current methods do not scale well to large numbers of observations.

Editorial extensions

If this is right

  • Interpretability need not force a large accuracy penalty: exact MIO-trained sparse models, risk scores, and decision trees achieve better interpretability-accuracy tradeoffs in sample, and with proper regularization can generalize competitively out of sample.
  • Fairness becomes a hard, auditable constraint: statistical parity, equal opportunity, predictive equality, and equalized odds can be imposed with a user-chosen tolerance, and on datasets small enough to solve, MIO methods reach fairer solutions than heuristics without sacrificing accuracy.
  • Robustness becomes certifiable: MIO verification of ReLU networks and tree ensembles either exhibits a genuine adversarial example or proves that none exists under the chosen attack model, a guarantee heuristic attacks cannot provide.
  • The same MIO core extends to causal and prescriptive settings, enabling optimal covariate-balanced matching and fair treatment-assignment trees learned from observational data under standard causal assumptions.
  • Scalability is the binding constraint: sparse regression has been solved to optimality with feature counts in the hundreds of thousands, but fairness constraints introduce at least one binary variable per data point, so exact fair models remain limited to smaller datasets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If solver and relaxation technology continue improving at the pace the tutorial documents, the per-data-point binary bottleneck for fairness may be relieved by the same perspective and cutting-plane ideas, making exact fairness constraints practical for large tabular datasets.
  • Because the adversarial-verification problem and the counterfactual-explanation problem share the same minimal-perturbation structure, branching and relaxation techniques developed for one could transfer directly to the other at scale, a cross-fertilization the paper notes but does not explore.
  • The paper's own Communities and Crime example suggests a concrete benchmark: solving fair sparse regression exactly at n in the thousands costs almost no accuracy; testing the same formulations at n in the hundreds of thousands would reveal when the fairness-vs-accuracy tradeoff actually starts to bite, which the paper leaves open.
  • Privacy appears only as future work, but the natural next step inside this framework is adding differential-privacy noise as an explicit constraint in the training MIO, yielding interpretable models with certified privacy guarantees.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 10 minor

Summary. This paper is a tutorial on mixed-integer optimization (MIO) as a modeling and solution framework for responsible machine learning. It covers interpretable supervised models (sparse linear and logistic regression, risk scores, SVMs, generalized additive models, decision trees, rule lists, decision sets), interpretable unsupervised learning (sparse PCA, Bayesian networks, clustering), counterfactual explanations, hyperparameter selection, robustness (outlier detection, adversarial verification and training, distribution shifts), prescriptive policy learning in observational settings, and fairness constraints in predictive models. The tutorial presents numerous MIO formulations, discusses relaxation strength and solution technology, and closes with limitations and future directions. Its central thesis is that MIO's modeling flexibility and optimality guarantees make it a powerful tool for embedding interpretability, robustness, and fairness into ML, while acknowledging scalability as a major bottleneck.

Significance. If the tutorial's content is accurate, it fills a useful niche: it provides an accessible, unified treatment spanning several strands of responsible ML and gives instructors and practitioners a compact starting point and reference list. Its strengths are breadth, the presence of concrete formulations, and an honest treatment of limitations: it explicitly flags the debate over whether exact MIO models outperform heuristics out-of-sample, notes that fairness constraints introduce O(|I|) binary variables and do not scale well, and lists scaling and privacy as open directions. I agree with the stress-test assessment that the paper's main vulnerability, scalability, is disclosed rather than concealed in Sections 5.1 and 6; for a tutorial whose purpose is to survey formulations and solution strategies, that disclosure is adequate. The paper is not a research-advance contribution with new algorithms or experiments, so its value is primarily pedagogical and informational; with the corrections noted below, it would be a sound tutorial.

minor comments (10)
  1. [2.3.2, Eq. (18)] Equation (18c) should read -M z_{jk} ≤ θ_{jk} ≤ M z_{jk} for all j,k; using M z_{kj} on the right does not force θ_{jk}=0 when z_{jk}=0 and incorrectly couples the bound to the reverse arc. In addition, the domain declaration in (18e) should be ζ ∈ {1,...,d}^d, not ζ ∈ {0,1}^d, to match the topological-ordering interpretation given in the text.
  2. [2.3.3, Eq. (20)] The McCormick linearization is misprinted: the lower bound should be z_i^k + z_j^k - 1 ≤ ζ_{ij}^k; the printed expression -1 + z_i^k + z_k^k contains an undefined z_k^k and does not provide the required lower bound for the product z_i^k z_j^k.
  3. [3.1, Eq. (24)] Equation (24a) is missing the summation over i ∈ I; as written, the objective contains a single loss term ℓ(f_θ(x_i), y_i - r_i) instead of the sum over the training set.
  4. [3.3, after Eq. (27)] The sentence 'the loss function may not be non-convex' should read 'may be non-convex'; the examples that follow, namely a discrete 0-1 loss and piecewise-linear classifiers, are non-convex, so the current wording contradicts the sentence's intent.
  5. [4.2, after Eq. (30)] The sentence describing constraint (30c) is backwards: the constraint ensures that no control individual c is matched to more than one treated individual, not that no treated individual is paired with two or more treated individuals.
  6. [4.3, Eqs. (33)-(34)] In the inverse-propensity score definitions, the denominator μ(x_i, a_i) is written outside the summation even though its index i is the summation index; it should be μ(x, a) or the propensity score should appear inside the summand so that s(x, a) is well-defined for each (x, a).
  7. [2.1.4, Eq. (11)] The double sum in (11) uses inconsistent indices: the summand should be θ_{jl} x_j x_l over j,l with appropriate indices, rather than θ_{ij} x_i x_j as printed.
  8. [Abstract and Section 2] The abstract's unqualified claim that MIO is useful 'while maintaining performance' is stronger than the body's discussion, which explicitly says the out-of-sample superiority of exact MIO over heuristics is debated and that the authors 'believe' it holds; consider softening the abstract or adding a qualifier.
  9. [5.1, Eq. (35)] In formulation (35), the minimization is declared over z ∈ {0,1}^n but the fairness variables appearing in constraint (35b) are ζ; the variable declaration should be ζ ∈ {0,1}^n, or the constraints should use z consistently.
  10. [2.4, after Eq. (22)] The sentence defining the cost metric says 'a larger value indicates an easier change,' but since problem (22) minimizes c(x, x̄), a larger cost should indicate a more difficult change; please clarify this wording.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the tutorial's central claim is a scoped pedagogical synthesis supported by external formulations and by explicitly disclosed limitations, not by a self-referential derivation.

full rationale

This paper is a tutorial, not a derivation: its central claim is that MIO offers a flexible modeling framework for responsible ML, and it supports this claim by surveying a broad literature of external formulations (e.g., Bertsimas and Dunn 2017, Hazimeh et al. 2022, Aghaei et al. 2024, Zubizarreta 2012, Hardt et al. 2016) rather than by fitting parameters and then predicting those same values. No step in the paper defines a modeling object in terms of the quantity it is supposed to predict, and no fitted input is relabeled as a prediction. The authors' own prior works (e.g., Gómez and Prokopyev 2021, Sun et al. 2025, Justin et al. 2023) are cited as examples of specific MIO formulations or solution techniques, but these citations are not load-bearing for the paper's survey-level thesis, and they are accompanied by many independent external references. The paper also explicitly identifies the main vulnerability of its thesis—the scalability and performance limitations of MIO models—in Section 5.1 ('require the introduction of at least |I| binary variables, leading to methods that do not scale well') and in Section 6, and it candidly describes the out-of-sample performance debate in Section 2 as an open question on which the authors state a belief rather than an established result. Because the central claim is a teaching claim about modeling flexibility and the surveyed content is externally grounded, there is no circularity to flag.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The tutorial relies on standard causal assumptions and on the practical solvability of MIO problems. The authors' own opinion about generalization is an ad hoc assumption that is explicitly flagged as a belief.

assumptions (3)
  • domain assumption Conditional exchangeability, positivity, and consistency (Assumptions 1-3 in Section 4.1)
    These are required for causal identification in the matching and policy learning sections. They cannot be verified from data and are standard background assumptions in causal inference.
  • domain assumption MIO solvers with strong relaxations can solve the presented formulations to optimality or high-quality solutions at practical scales
    The tutorial's thesis that MIO is a powerful framework depends on computational tractability. The paper itself cites scalability as a bottleneck in several sections, so this is a load-bearing premise.
  • ad hoc to paper The authors' belief that exact MIO models generalize better out-of-sample than heuristics
    Stated in Section 2.1 as a belief without proof or comprehensive evidence. It motivates the tutorial's emphasis on exact optimization and is not an established result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Responsible Machine Learning via Mixed-Integer Optimization." pith.science (2026). https://pith.science/paper/IXTXDJ65

@misc{pith2026250505857,
  author       = {Pith},
  title        = {Pith review of: Responsible Machine Learning via Mixed-Integer Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IXTXDJ65}},
  note         = {Machine review of arXiv:2505.05857}
}
read the original abstract

In the last few decades, Machine Learning (ML) has achieved significant success across domains ranging from healthcare, sustainability, and the social sciences, to criminal justice and finance. But its deployment in increasingly sophisticated, critical, and sensitive areas affecting individuals, the groups they belong to, and society as a whole raises critical concerns around fairness, transparency and robustness, among others. As the complexity and scale of ML systems and of the settings in which they are deployed grow, so does the need for responsible ML methods that address these challenges while providing guaranteed performance in deployment. Mixed-integer optimization (MIO) offers a powerful framework for embedding responsible ML considerations directly into the learning process while maintaining performance. For example, it enables learning of inherently transparent models that can conveniently incorporate fairness or other domain specific constraints. This tutorial paper provides an accessible and comprehensive introduction to this topic discussing both theoretical and practical aspects. It outlines some of the core principles of responsible ML, their importance in applications, and the practical utility of MIO for building ML models that align with these principles. Through examples and mathematical formulations, it illustrates practical strategies and available tools for efficiently solving MIO problems for responsible ML. It concludes with a discussion on current limitations and open research questions, providing suggestions for future work.

Figures

Figures reproduced from arXiv: 2505.05857 by the authors.

Figure 1
Figure 1. MIO relaxations. Black dots represent the dis￾crete feasible region of an MIO problem. Solid lines depict the convex hull, while dashed lines depict a weaker linear relaxation. where hj (z, r) : Z p × R q → R are functions encoding hard constraints and J is the set of indices of those constraints. If all functions g and hj , j ∈ J are affine, the problem is known as mixed-integer linear optimization (MILO). If g is … view at source ↗
Figure 3
Figure 3. The sigmoid function σ(yθ ⊤x) = 1 1+exp(−yθ ⊤x) , whose value represents the estimated probability that an individual with covariates x has label y. The logistic loss is −log(σ(yθ ⊤x)). Namely, we learn a linear model θ ⊤x where a larger value indicates a higher probability that the true label of x is y = 1. The loss function for logistic regression is the logistic loss, also called the cross-entropy loss, which inv… view at source ↗
Figure 4
Figure 4. A possible scoring card to assess medical risk. See Ustun and Rudin (2019) for samples of opti￾mal risk scoring cards in a variety of high-stakes domains. branch-and-bound algorithms with exponential cones, and can directly tackle (8) without requiring tailored implementations of outer approximations. Molero-R´ıo and D’Ambrosio (2024) generalize the approach to continuous data {x i}i∈I, although this generalization … view at source ↗
Figures from the paper (6 more)
Figure 5
Figure 5. Figure 5: A SVM classifier on perfectly separable data. Interestingly, while SVMs are among to most widely used models in statistics and ML, there are surprisingly limited results in the lit￾erature concerning solving their interpretable version (9) to optimality. The methods pr…
Figure 7
Figure 7. Figure 7: A visualization of the flow network used to train a decision tree of depth D = 2 in Aghaei et al. (2024). parent node as a(k). Also denote A(k) ⊂ B as the set of all ancestors of k, i.e., the set of all nodes traversed between s and k. Assuming that the covariates are …
Figure 9
Figure 9. Figure 9: 2D dataset and principal components, where lengths repre￾sent the amount of variance cap￾tured. is a classical technique for dimensionality reduc￾tion in unsupervised learning. At a high level, PCA seeks the most important axes or directions, called principal component…
Figure 10
Figure 10. Figure 10: Sample Bayesian network showing that the variables “Test Result” and “Symptoms” are conditionally independent given “Disease”. inference and knowledge discovery. They aim to describe the joint probability distribution generating the data by means of a directed acyclic…
Figure 12
Figure 12. Figure 12: Matching in obser￾vational studies: every individ￾ual in the treatment group is matched to (i.e., represented by) several similar individuals in the control group. The sizes of the subgroups matched to each individual are roughly the same across individuals, and no on…
Figure 13
Figure 13. Figure 13: By imposing fairness, cities with large Hispanic populations and low estimated crime rates increase from 23% to 37%. TotalPctDiv: per￾centage of population who are divorced, popula￾tion: population for community. police budget per population (PolicBudgPerPop), as the …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 9 canonical work pages

  1. [1]

    Engineering with Computers 1–19

    Aftabi N, Moradi N, Mahroo F (2025) Feed-forward neural networks as a mixed-integer program. Engineering with Computers 1–19. Aghaei S, Azizi MJ, Vayanos P (2019) Learning optimal and fair decision trees for non- discriminative decision-making. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 1418–1426. Aghaei S, G´ omez A, Vayano...

    work page 2025

  2. [17]

    Fair and Accurate Regression: Strong Formulations and Algorithms

    Dedieu A, Hazimeh H, Mazumder R (2021) Learning sparse classifiers: Continuous and mixed integer optimization perspectives. Journal of Machine Learning Research 22(135):1–47. Dey SS, Mazumder R, Wang G (2022) Using ℓ1-relaxation and integer programming to obtain dual bounds for sparse pca. Operations Research 70(3):1914–1932. Deza A, Atamt¨ urk A (2022) S...

    work page Pith review arXiv 2021

  3. [18]

    Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society , 177–187

    Mohammadi K, Karimi AH, Barthe G, Valera I (2021) Scaling guarantees for nearest counterfactual explanations. Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society , 177–187. Mohassel P, Zhang Y (2017) Secureml: A system for scalable privacy-preserving machine learning. 2017 IEEE Symposium on Security and Privacy (SP) , 19–38. Molero-R´ ı...

    work page 2021

  4. [29]

    Hastie T, Tibshirani R, Tibshirani RJ (2017) Extended comparisons of best subset selec- tion, forward stepwise selection, and the lasso

    Hastie T, Tibshirani R, Friedman J (2009) The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Springer), 2nd edition. Hastie T, Tibshirani R, Tibshirani RJ (2017) Extended comparisons of best subset selec- tion, forward stepwise selection, and the lasso. arXiv preprint arXiv:1707.08692 . Hazimeh H, Mazumder R (2020) Fast best sub...

    arXiv 2009

  5. [31]

    Advances in Neural Information Processing Sys- tems

    d’Aspremont A, Ghaoui L, Jordan M, Lanckriet G (2004) A direct formulation for sparse pca using semidefinite programming. Advances in Neural Information Processing Sys- tems

    work page 2004

  6. [32]

    arXiv preprint arXiv:2104.10751

    R¨ ober TE, Lumadjeng AC, Aky¨ uz MH, Birbil S ¸˙I (2021) Rule generation for classification: Scalability, interpretability, and fairness. arXiv preprint arXiv:2104.10751 . Rousseeuw PJ (1984) Least median of squares regression. Journal of the American Statis- tical Association 79(388):871–880. Rousseeuw PJ (1987) Silhouettes: a graphical aid to the inter...

    arXiv 2021

  7. [36]

    Learning Optimal Prescriptive Trees from Observational Data

    Ingold D, Soper S (2016) Amazon doesn’t consider the race of its customers. should it? URL https://www.bloomberg.com/graphics/2016-amazon-same-day/. Innovation, Science and Economic Development Canada (2023) Voluntary code of conduct on the responsible development and management of advanced generative ai systems. https://ised-isde.canada.ca/. Insolia L, K...

    work page Pith review arXiv 2016

  8. [226]

    right to explanation

    Dziugaite GK, Ben-David S, Roy DM (2020) Enforcing interpretability and its sta- tistical impacts: Trade-offs between accuracy and interpretability. arXiv preprint arXiv:2010.13764 . D’Onofrio F, Grani G, Monaci M, Palagi L (2024) Margin optimal classification trees. Computers & Operations Research 161:106441. Eberhardt F, Kaynar N, Siddiq A (2024) Discov...

    arXiv 2020

Show all 15 references
  1. [397]

    Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings 14, 94–103 (Springer)

    Verwer S, Zhang Y (2017) Learning decision trees with flexible constraints and objec- tives using integer optimization. Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings 14, 94–1...

    2017 arXiv

  2. [663]

    The AAAI-22 workshop on Adversarial Machine Learning and Beyond

    Justin N, Aghaei S, Gomez A, Vayanos P (2021) Optimal robust classification trees. The AAAI-22 workshop on Adversarial Machine Learning and Beyond . Justin N, Aghaei S, G´ omez A, Vayanos P (2023) Learning optimal classification trees robust to distribution shifts. arXiv prepr...

    2021 arXiv

  3. [734]

    Computers & Operations Research 164:106515

    Al` es Z, Hur´ e V, Lambert A (2024) New optimization models for optimal classification trees. Computers & Operations Research 164:106515. Amram M, Dunn J, Zhuo YD (2022) Optimal policy trees. Machine Learning 111(7):2741–

    2024

  4. [1000]

    arXiv preprint arXiv:2402.01797

    Cepeda V, G´ omez A, Han S (2024) Robust support vector machines via conic optimization. arXiv preprint arXiv:2402.01797 . Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math- ematical Programming 86:595–614. Chen R, Dash S, Gao T (2021) Integ...

    2024 arXiv

  5. [1996]

    Ustun B, Rudin C (2019) Learning optimized risk scores

    Public Law 104-191. Ustun B, Rudin C (2019) Learning optimized risk scores. Journal of Machine Learning Research 20(150):1–75. Ustun B, Spangher A, Liu Y (2019) Actionable recourse in linear classification.Proceedings of the conference on Fairness, Accountability, and Transpar...

    2019 arXiv

  6. [2768]

    2020 59th IEEE Conference on Decision and Control (CDC), 2190–2197 (IEEE)

    54 Justin, Sun, G´ omez, and Vayanos:Responsible Machine Learning via Mixed-Integer Optimization Anderson BG, Ma Z, Li J, Sojoudi S (2020a) Tightened convex relaxations for neural network robustness certification. 2020 59th IEEE Conference on Decision and Control (CDC), 2190–2...

    2020

  7. [3203]

    INFORMS Journal on Data Science 1(2):156–171

    Morucci M, Noor-E-Alam M, Rudin C (2022) A robust approach to quantifying uncer- tainty in matching problems of causal inference. INFORMS Journal on Data Science 1(2):156–171. Navarro-Garc´ ıa M, Guerrero V, Durban M, del Cerro A (2025) Feature and functional form selection in...

    2022 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.