Combinatorial Optimization in Robust Machine Learning: A Survey of Methods

A new review has been published on arXiv (arXiv:2607.07762) on the role of combinatorial optimization in developing reliable AI systems. The research synthesizes recent advances at the intersection of combinatorial optimization (CO) and trustworthy ML, demonstrating 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-scale neural networks learn equally well on any function, yet their behavior is unpredictable. Two models with identical accuracy on a test set can differ dramatically in interpretability, resistance to adversarial examples, fairness across different user groups, and resilience against privacy attacks.

Gradient optimization allows rapid discovery of a good local solution but does not guarantee global quality and does not explain the solution. This creates problems for critical applications—medicine, law enforcement, finance—where provable guarantees are needed, not just strong metrics.

Combinatorial Optimization as a Verification Tool

Combinatorial optimization seeks globally optimal solutions or proves their nonexistence. In ML, it helps:

• Interpretability: construct decision trees and linear models with guarantees of minimal complexity and maximum quality simultaneously
• Robustness: find all adversarial examples that disrupt model operation or prove their absence within a certain range
• Fairness auditing: detect and measure discrimination in AI decisions on specific data groups
• Compression: remove redundant neurons while guaranteeing quality preservation
• Privacy protection: add differentially-private mechanisms with provable guarantees on information leakage

The key advantage: results are accompanied by a certificate—proof of optimality or a guaranteed permissible deviation interval.

Scalability: Realistic Complexity

The main challenge for CO in AI is computational cost on large datasets. However, the review authors point to two positive trends.

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

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

What This Means

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