# Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives

arXiv: https://arxiv.org/abs/2607.07762 · HTML: https://mlsanity.com/paper/2607.07762/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 381 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [The Fifth International Verification of Neural Networks Competition (VNN-COMP 2024): Summary and Results](https://mlsanity.com/paper/2412.19985/) (2024)
- [The 6th International Verification of Neural Networks Competition (VNN-COMP 2025): Summary and Results](https://mlsanity.com/paper/2512.19007/) (2025)
- [A DPLL(T) Framework for Verifying Deep Neural Networks](https://mlsanity.com/paper/2307.10266/) (2023)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [A Unified Post-Processing Framework for Group Fairness in Classification](https://mlsanity.com/paper/2405.04025/) (2024)
- [Symbolic Regression using Mixed-Integer Nonlinear Optimization](https://mlsanity.com/paper/2006.06813/) (2020)
- [Learning Fair Rule Lists](https://mlsanity.com/paper/1909.03977/) (2019)
- [Fairness-guided SMT-based Rectification of Decision Trees and Random Forests](https://mlsanity.com/paper/2011.11001/) (2020)
- [Learning Optimal Classification Trees Robust to Distribution Shifts](https://mlsanity.com/paper/2310.17772/) (2023)
- [One-for-many Counterfactual Explanations by Column Generation](https://mlsanity.com/paper/2402.09473/) (2024)
- [A GPU-accelerated Nonlinear Branch-and-Bound Framework for Sparse Linear Models](https://mlsanity.com/paper/2602.04551/) (2026)
- [Counterfactual Maps: What They Are and How to Find Them](https://mlsanity.com/paper/2602.09128/) (2026)
- [Linear Model Extraction via Factual and Counterfactual Queries](https://mlsanity.com/paper/2602.09748/) (2026)
- [Integrating Fairness and Model Pruning Through Bi-level Optimization](https://mlsanity.com/paper/2312.10181/) (2023)
- [Intersectional Fairness via Mixed-Integer Optimization](https://mlsanity.com/paper/2601.19595/) (2026)
- [PACE: Prune-And-Compress Ensemble Models](https://mlsanity.com/paper/2605.06278/) (2026)
- [Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms](https://mlsanity.com/paper/2605.06561/) (2026)
- [Optimal Recourse Summaries via Bi-Objective Decision Tree Learning](https://mlsanity.com/paper/2605.07598/) (2026)

## Abstract (arXiv)

Modern machine learning (ML) increasingly relies on complex models whose behavior is difficult to characterize beyond empirical performance metrics. Across a wide range of tasks, including prediction, generation, and decision-making, models with similar empirical performance can exhibit markedly different properties in terms of their transparency, interpretability, robustness, fairness, privacy, and certifiability. This survey highlights how optimization- and certification-oriented reasoning can provide a useful framework for reasoning about such differences, supporting tasks ranging from model training and selection to auditing and certification. We review and synthesize recent advances at the intersection of combinatorial optimization (CO) and trustworthy ML, covering both training and post-training tasks, including interpretable model learning, explanation generation, robustness analysis, fairness auditing, model compression, and privacy attacks and protections. Across these domains, CO formulations offer additional capabilities over purely heuristic approaches, e.g., gradient-based ones, notably global guarantees, formal certificates, and explicit treatment of trade-offs. While scalability remains an important challenge, continued progress in solvers and hybrid algorithms suggests a growing role for CO in the design and deployment of trustworthy ML systems.