Combinatorial Optimization in Trustworthy Machine Learning: A Survey of Methods

A new survey (arXiv:2607.07762) on the role of combinatorial optimization in building trustworthy AI systems has been published on arXiv. The study synthesizes recent work at the intersection of combinatorial optimization (CO) and trustworthy ML, showing that CO methods provide formal guarantees of interpretability, robustness, fairness and privacy where traditional gradient-based approaches deliver only empirical quality.

Why modern AI remains a black box

Large neural networks train equally well on almost any function, but their behavior is unpredictable. Two models with the same accuracy on a test set can differ dramatically in interpretability, resistance to adversarial examples, fairness toward different user groups and resilience to privacy attacks.

Gradient optimization quickly finds a good local solution, but it does not guarantee global quality and does not explain decisions. That creates problems for critical applications such as medicine, law enforcement and finance, where provable guarantees are needed, not just good metrics.

Combinatorial optimization as a verification tool

Combinatorial optimization searches for globally optimal solutions or proves that none exist. In ML, it helps with:

• Interpretability: building decision trees and linear models with a guarantee of minimal complexity and maximal quality at the same time
• Robustness: finding all adversarial examples that break a model, or proving there are none within a given range
• Fairness auditing: detecting and measuring discrimination in AI decisions on specific data groups
• Compression: removing redundant neurons with a guarantee that quality is preserved
• Privacy protection: adding differentially private mechanisms with provable guarantees on information leakage

The key advantage: the result comes with a certificate, either a proof of optimality or a guarantee within a bounded tolerance interval.

Scalability: realistic complexity

The main challenge for CO in AI is computational cost on large datasets. The survey's authors point to two encouraging trends.

First, modern solvers (SAT solvers, Gurobi, IBM CPLEX) handle increasingly hard problems thanks to heuristics and parallelism. Second, hybrid algorithms combine CO with gradient methods: for example, CO selects the architecture while gradient descent optimizes the weights quickly.

This opens a practical path: CO is applied not to the whole training process but to verification and auditing, where guarantees are critical and data volumes are manageable.

What this means

The survey signals a shift in trustworthy AI: from empiricism to a hybrid with formal guarantees. For high-stakes applications such as medicine, finance and law enforcement, this means the possibility of provable verification and certification of models.