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

Julien Ferry; Thibaut Vidal

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

T0 review · 0 major / 5 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read Combinatorial optimization gives trustworthy ML global guarantees, formal certificates, and explicit trade-offs that pure heuristics cannot match.

desk verdict Solid, broad survey that actually unifies training and post-training CO work for trustworthiness; worth reading and citing as a map, not as a new result. read the letter →

arxiv 2607.07762 v1 pith:XFDPCK5R submitted 2026-07-08 cs.LG math.OC

Thibaut Vidal , Julien Ferry This is my paper

classification cs.LGmath.OC

keywords trustworthymachinelearningcombinatorialoptimizationexplainabilityandinterpretabilityrobustnessfairnessprivacycertificationauditingmixed-integerprogramming

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

Machine learning models with nearly identical accuracy can still differ sharply in how transparent, fair, robust, private, or certifiable they are. This survey argues that many of those trustworthiness questions—learning sparse interpretable models, generating explanations, auditing fairness, verifying robustness, compressing models, and probing privacy leakage—can be cast as combinatorial optimization or feasibility problems. Formulated that way, modern solvers and hybrid algorithms can deliver global optimality, formal certificates, and explicit multi-criteria trade-offs that gradient-based and purely heuristic methods rarely provide. The paper synthesizes work across training and post-training tasks using mixed-integer programming, SAT, SMT, constraint programming, MaxSAT, and specialized branch-and-bound hybrids. Scalability remains a real limit because most of these problems are NP-hard, yet the authors contend that continued solver progress is expanding what can be certified in practice, so combinatorial optimization should play a growing role in how trustworthy systems are designed, selected, audited, and deployed.

What carries the argument

Casting trustworthiness tasks as optimization or feasibility problems over discrete structured spaces (via MILP, SAT, SMT, CP, MaxSAT, and hybrid branch-and-bound), so solvers can return global guarantees and certificates rather than local heuristic answers.

What would settle it

If, over several years of further solver progress, exact or hybrid combinatorial trainers and verifiers remain limited to models far smaller than those used in high-stakes practice, while systems continue to ship without usable formal certificates, the claim of a growing deployment role for combinatorial optimization would fail.

Watch

Extended reading notes

Core claim

Across transparency, explainability, fairness, robustness, model compression, and privacy, combinatorial-optimization formulations offer capabilities that are hard to get from purely heuristic or gradient-based methods: global optimality, formal certificates, explicit treatment of trade-offs, and the ability to enforce rich structural and domain constraints.

Load-bearing premise

That progress in solvers and hybrid algorithms will keep expanding the practical scale of exact combinatorial methods fast enough for them to matter in real deployment, despite NP-hardness and the size of modern deep models.

Editorial extensions

If this is right

When many models achieve similar accuracy, combinatorial search over Rashomon sets can select sparser, fairer, or more verifiable alternatives without sacrificing performance.
Post-training audits can produce formal certificates of robustness, fairness, or functional equivalence instead of only empirical checks.
Explanation methods can return subset-minimal or cardinality-minimal counterfactuals and abductive reasons while enforcing actionability and plausibility constraints.
Privacy leakage can be audited as inverse combinatorial reconstruction, turning abstract risk into concrete recovery rates and attack surfaces.
Design can shift toward verifiability by construction—sparser, more stable, or hybrid models—when certification is required.

Reading between the lines

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

High-stakes regulation that demands formal certificates may effectively prefer model classes that admit combinatorial analysis, even when large black-box models score slightly higher on accuracy.
The same optimization machinery that certifies models can also attack them (dataset reconstruction, model extraction), so richer released structure or explanations can increase privacy exposure.
When predictors sit inside larger decision pipelines, trustworthiness will need to be measured on actions, costs, and group outcomes, not only on prediction error.
Without sustained hybrid-algorithm gains, combinatorial methods may stay confined to tabular and small structured models while the largest deep systems remain outside formal reach.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

This is a careful survey, not a primary result. What is new is the organizing frame: it pulls training (sparse models, ODTs, scoring systems, pruning) and post-training tasks (explanations, fairness/robustness audits, privacy reconstruction, compression) under one CO lens, across MILP, SAT/MaxSAT, CP, SMT, and hybrids, with more weight on verification and privacy than the earlier tutorials it cites.

It does that job well. The highlights give self-contained formulations that are usable as entry points; the literature coverage is dense but representative rather than padded; and the authors are honest about NP-hardness and scale. The central claim—that CO gives global guarantees, certificates, and explicit trade-offs that pure heuristics do not—is supported by the concrete models and citations in Sections 3–7, not by hand-waving. Circularity is essentially zero; self-citations look like ordinary pointers to their own prior work in the area.

Soft spots are real but secondary. The forward-looking line about solvers and hybrids expanding CO’s role is optimistic and sits in the abstract and §8; it is not load-bearing for the synthesis. The paper never pretends exact CO already scales to modern deep nets, so if that projection fails the survey still stands. As with any survey of this breadth, some sub-areas are thinner than others (privacy is thinner than trees/robustness), and there is no new theorem or experiment to stress-test. That is fine for the genre.

Who it is for: people who already work at the OR–ML boundary, or who need a single map of which CO tools have been used for which trustworthiness tasks. Not for someone hunting a new algorithm. Math and citation pattern look solid. I would bring it to reading group as a shared reference, cite it when I need a survey pointer, and send it to peer review without hesitation—it is the kind of synthesis that earns referee time.

Referee Report

0 major / 5 minor

Summary. This survey organizes trustworthy machine learning through the lens of combinatorial optimization. It argues that CO formulations (MILP, CP, SAT/MaxSAT, SMT, DP+B&B hybrids) supply capabilities that purely heuristic or gradient-based methods do not: global optimality, formal certificates, explicit trade-offs, and the ability to encode structural and domain constraints. After background on trustworthiness dimensions and CO, Sections 3–7 systematically cover transparency (sparse models, ODTs, pruning, Rashomon sets), explainability (counterfactuals, AXps, prototypes, surrogates), fairness (in-processing, preprocessing, auditing), robustness (robust training, verification, selective classification), and privacy (reconstruction attacks, extraction, disclosure control). Representative formulations are given as self-contained Highlights; Section 8 discusses open challenges and research perspectives.

Significance. The manuscript fills a genuine gap. Prior surveys either treat CO mainly for classical training (Gambella et al.), reverse the direction (ML for CO; Bengio et al.), or focus narrowly on MIP for responsible learning (Justin et al.). By spanning training and post-training tasks, multiple CO paradigms, and the full suite of trustworthiness desiderata, the paper provides a unifying map that is useful to both the OR and ML communities. Strengths include the curated mathematical Highlights, the careful treatment of scalability limits, and the explicit discussion of trade-offs and certifiability-by-design. The central claim is organizational rather than empirical and is well supported by the literature synthesis.

minor comments (5)

The abstract and §8 project that continued solver progress will expand CO’s practical role. This is a reasonable forward-looking remark, but a short, more cautious sentence acknowledging that modern deep models remain largely out of reach for exact methods would better match the careful tone of the body.
Highlight 6 (MaxSAT decision lists) is dense; a one-sentence high-level reading of the soft/hard clause structure before the full encoding would help non-SAT readers.
Table 1 (notation) is referenced but not visible in the provided text; ensure it appears in the final version and is complete for all Highlights.
A few recent adjacent works on hybrid verification and decision-focused learning could be added in §6–8 for completeness, without changing the survey’s scope.
Minor typographical inconsistencies appear in author names with diacritics (e.g., Ljubi´c, G´omez) and in a few arXiv-style citations; a final copy-edit pass would clean these.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: pure survey synthesis with no fitted predictions or self-referential derivations

full rationale

This manuscript is an integrative survey of combinatorial-optimization techniques applied to trustworthy machine learning. It organizes external literature into sections on transparency, explainability, fairness, robustness and privacy, and supplies representative mathematical formulations drawn from the cited works. The central claim—that CO formulations supply global optimality, formal certificates and explicit trade-offs that pure heuristics do not—is supported by the collected formulations and citations rather than by any new theorem, fitted parameter, or self-referential definition. Self-citations appear only as ordinary literature pointers to the authors’ prior contributions; none is load-bearing for a uniqueness claim or for a quantitative prediction. The forward-looking remark on solver progress is acknowledged as a research perspective, not a premise required by the synthesis. Consequently the derivation chain contains no circular step.

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

As a literature survey the paper introduces no free parameters, no new physical or mathematical entities, and relies only on standard background assumptions of combinatorial optimization and machine learning. The load-bearing premises are the correctness of the cited primary works and the continued improvement of solvers.

assumptions (3)

domain assumption Many trustworthiness questions (robustness verification, fairness auditing, minimal explanations, sparse training) can be cast as NP-hard combinatorial optimization or feasibility problems.
Stated throughout Sections 2–7; standard complexity results for the cited formulations.
domain assumption Modern CO solvers (MILP, SAT, SMT, CP, MaxSAT) have improved by orders of magnitude and can solve instances of practical size for moderate-scale models.
Cited via Koch et al. 2022 and Clautiaux & Ljubić 2025 in Section 2; used to justify the growing role of CO.
domain assumption Global optimality certificates and formal feasibility proofs are valuable for high-stakes deployment even when heuristic methods achieve similar empirical accuracy.
Core framing of the survey (abstract and Section 1).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives." pith.science (2026). https://pith.science/paper/XFDPCK5R

@misc{pith2026260707762,
  author       = {Pith},
  title        = {Pith review of: Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XFDPCK5R}},
  note         = {Machine review of arXiv:2607.07762}
}

read the original abstract

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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

4655–4665. Dasu, V. A., ur Rashid, M. R., Gupta, V., Tizpaz-Niari, S., Tan, G. 2026. Attention Pruning: Automated Fairness Repair of Language Models via Surrogate Simulated Annealing.Proceedings of the International Conference on Software Engineering 2026. 1–13. Dathathri, S., Dvijotham, K., Kurakin, A., Raghunathan, A., Uesato, J., Bunel, R., Shankar, S....

work page 2026
[2]

Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection

MurTree: Optimal decision trees via dynamic programming and search.Journal of Machine Learning Research231–47. Deng, X., Papadimitriou, C. H. 1994. On the Complexity of Cooperative Solution Concepts.Mathematics of Operations Research19257–266. 53 Denis, C., Elie, R., Hebiri, M., Hu, F. 2024. Fairness Guarantees in Multi-class Classification with Demograph...

work page Pith review arXiv 1994
[3]

Distilling the Knowledge in a Neural Network

3323–3331. Hassibi, B., Stork, D. 1992. Second order derivatives for network pruning: Optimal Brain Surgeon.Proceedings of NIPS 1992. 164–171. Hay, M., Rastogi, V., Miklau, G., Suciu, D. 2010. Boosting the accuracy of differentially private histograms through consistency.Proceedings of the VLDB Endowment31021–1032. Hazimeh, H., Mazumder, R., Saab, A. 2022...

work page Pith review arXiv 1992
[4]

Learning Optimal Classification Trees Robust to Distribution Shifts

1782–1795. Jiang, J., Lan, J., Leofante, F., Rago, A., Toni, F. 2024a. Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation.Proceedings of the ACML 2024. 582–597. Jiang, J., Leofante, F., Rago, A., Toni, F. 2024b. Interval abstractions for robust counterfactual explanations. Artificial Intelligence336104218...

work page Pith review arXiv 2024
[5]

Ma, J., Wang, J., Xuan, Q., Wang, Z

4766–4775. Ma, J., Wang, J., Xuan, Q., Wang, Z. 2025. Provable Fairness Repair for Deep Neural Networks.Proceedings of the International Conference on Automated Software Engineering 2025. 508–520. Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A. 2018. Towards deep learning models resistant to adversarial attacks.Proceedings of ICLR 2018. 1–28. ...

work page 2025
[6]

McDonald, T., Tsay, C., Schweidtmann, A

6765–6774. McDonald, T., Tsay, C., Schweidtmann, A. M., Yorke-Smith, N. 2024. Mixed-integer optimisation of graph neural networks for computer-aided molecular design.Computers and Chemical Engineering185. Meng, X., Chen, W., Benbaki, R., Mazumder, R. 2024a. FALCON: FLOP-Aware Combinatorial Optimization for Neural Network Pruning.Proceedings of AISTATS 202...

work page arXiv 2024
[7]

Parmentier, A., Vidal, T

2444–2454. Parmentier, A., Vidal, T. 2021. Optimal counterfactual explanations in tree ensembles.Proceedings of ICML

work page 2021
[8]

Why should I trust you?

8422–8431. Patel, K. K., Desaulniers, G., Lodi, A. 2024. An improved column-generation-based matheuristic for learning classification trees.Computers & Operations Research165106579. Petersen, F., Borgelt, C., Kuehne, H., Deussen, O. 2022. Deep differentiable logic gate networks.Proceedings of NeurIPS 2022. 2006–2018. Petersen, F., Kuehne, H., Borgelt, C.,...

work page 2024

Show all 15 references

[9]

Ruoss, A., Balunovic, M., Fischer, M., Vechev, M

42783–42795. Ruoss, A., Balunovic, M., Fischer, M., Vechev, M. 2020. Learning certified individually fair representations. Proceedings of NeurIPS 2020. 7584–7596. R¨ atsch, G., Warmuth, M. K., Glocer, K. A. 2007. Boosting Algorithms for Maximizing the Soft Margin. Proceedings ...

2020
[10]

Sun, Q., Justin, N., G´ omez, A., Vayanos, P

21–30. Sun, Q., Justin, N., G´ omez, A., Vayanos, P. 2025. Mixed-feature Logistic Regression Robust to Distribution Shifts.Proceedings of AISTATS 2025. 4906–4914. Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., Fergus, R. 2013. Intriguing propert...

2025
[11]

van der Linden, J

10–19. van der Linden, J. G. M., Vos, D., de Weerdt, M. M., Verwer, S., Demirovi´ c, E. 2024. Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance. Tech. rep., arXiv:2409.12788. van der Linden, J. G., de Weerdt, M. M., Demirovi´ c, E. 2022. Fa...

2024 arXiv
[12]

Vos, D., Verwer, S

203–218. Vos, D., Verwer, S. 2022b. Robust Optimal Classification Trees against Adversarial Examples.Proceedings of AAAI 2022. 8520–8528. Wachter, S., Mittelstadt, B., Russell, C. 2018. Counterfactual explanations without opening the black box: Automated decisions and the GDPR...

2022
[13]

Marabou 2.0: A Versatile Formal Analyzer of Neural Networks.Proceedings of the International Conference on Computer Aided Verification 2024. 249–264. Xian, R., Yin, L., Zhao, H. 2023. Fair and Optimal Classification via Post-Processing.Proceedings of ICML

2024
[14]

Xian, R., Zhao, H

37977–38012. Xian, R., Zhao, H. 2024. A Unified Post-Processing Framework for Group Fairness in Classification. Tech. rep., arXiv:2405.04025. Xiao, K. Y., Tjeng, V., Shafiullah, N. M., Madry, A. 2019. Training for faster adversarial robustness verification via inducing ReLU st...

2024 arXiv
[15]

Xu, K., Zhang, H., Wang, S., Wang, Y., Jana, S., Lin, X., Hsieh, C

1129–1141. Xu, K., Zhang, H., Wang, S., Wang, Y., Jana, S., Lin, X., Hsieh, C. J. 2021. Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers. Proceedings of ICLR 2021. 1–15. Yajima, H., Matsui, Y. 2026. PINE: P...

2021 arXiv

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.

[1] [1]

4655–4665. Dasu, V. A., ur Rashid, M. R., Gupta, V., Tizpaz-Niari, S., Tan, G. 2026. Attention Pruning: Automated Fairness Repair of Language Models via Surrogate Simulated Annealing.Proceedings of the International Conference on Software Engineering 2026. 1–13. Dathathri, S., Dvijotham, K., Kurakin, A., Raghunathan, A., Uesato, J., Bunel, R., Shankar, S....

work page 2026

[2] [2]

Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection

MurTree: Optimal decision trees via dynamic programming and search.Journal of Machine Learning Research231–47. Deng, X., Papadimitriou, C. H. 1994. On the Complexity of Cooperative Solution Concepts.Mathematics of Operations Research19257–266. 53 Denis, C., Elie, R., Hebiri, M., Hu, F. 2024. Fairness Guarantees in Multi-class Classification with Demograph...

work page Pith review arXiv 1994

[3] [3]

Distilling the Knowledge in a Neural Network

3323–3331. Hassibi, B., Stork, D. 1992. Second order derivatives for network pruning: Optimal Brain Surgeon.Proceedings of NIPS 1992. 164–171. Hay, M., Rastogi, V., Miklau, G., Suciu, D. 2010. Boosting the accuracy of differentially private histograms through consistency.Proceedings of the VLDB Endowment31021–1032. Hazimeh, H., Mazumder, R., Saab, A. 2022...

work page Pith review arXiv 1992

[4] [4]

Learning Optimal Classification Trees Robust to Distribution Shifts

1782–1795. Jiang, J., Lan, J., Leofante, F., Rago, A., Toni, F. 2024a. Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation.Proceedings of the ACML 2024. 582–597. Jiang, J., Leofante, F., Rago, A., Toni, F. 2024b. Interval abstractions for robust counterfactual explanations. Artificial Intelligence336104218...

work page Pith review arXiv 2024

[5] [5]

Ma, J., Wang, J., Xuan, Q., Wang, Z

4766–4775. Ma, J., Wang, J., Xuan, Q., Wang, Z. 2025. Provable Fairness Repair for Deep Neural Networks.Proceedings of the International Conference on Automated Software Engineering 2025. 508–520. Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A. 2018. Towards deep learning models resistant to adversarial attacks.Proceedings of ICLR 2018. 1–28. ...

work page 2025

[6] [6]

McDonald, T., Tsay, C., Schweidtmann, A

6765–6774. McDonald, T., Tsay, C., Schweidtmann, A. M., Yorke-Smith, N. 2024. Mixed-integer optimisation of graph neural networks for computer-aided molecular design.Computers and Chemical Engineering185. Meng, X., Chen, W., Benbaki, R., Mazumder, R. 2024a. FALCON: FLOP-Aware Combinatorial Optimization for Neural Network Pruning.Proceedings of AISTATS 202...

work page arXiv 2024

[7] [7]

Parmentier, A., Vidal, T

2444–2454. Parmentier, A., Vidal, T. 2021. Optimal counterfactual explanations in tree ensembles.Proceedings of ICML

work page 2021

[8] [8]

Why should I trust you?

8422–8431. Patel, K. K., Desaulniers, G., Lodi, A. 2024. An improved column-generation-based matheuristic for learning classification trees.Computers & Operations Research165106579. Petersen, F., Borgelt, C., Kuehne, H., Deussen, O. 2022. Deep differentiable logic gate networks.Proceedings of NeurIPS 2022. 2006–2018. Petersen, F., Kuehne, H., Borgelt, C.,...

work page 2024