Overview
This survey examines the role of combinatorial optimization (CO) in developing trustworthy machine learning (ML) systems. It highlights how optimization- and certification-oriented reasoning, enabled by CO formulations, can differentiate between ML models with similar empirical performance but varying properties like transparency, interpretability, robustness, fairness, privacy, and certifiability. The review synthesizes recent advancements where CO intersects with trustworthy ML, covering tasks from model training and selection to auditing and certification.
Research Context
Modern machine learning increasingly utilizes complex models. These models' behaviors are often difficult to characterize beyond their empirical performance metrics. Consequently, models performing similarly empirically can exhibit marked differences in other crucial attributes, including transparency, interpretability, robustness, fairness, privacy, and certifiability. The research context emphasizes that addressing these attributes is vital for advancing the trustworthiness of ML systems.
Approach
The survey adopts an approach centered on reviewing and synthesizing recent advances at the intersection of combinatorial optimization (CO) and trustworthy ML. It categorizes these applications into both training and post-training tasks. The methodology involves exploring how CO formulations provide capabilities beyond purely heuristic methods, such as gradient-based approaches, specifically in achieving global guarantees, formal certificates, and explicit trade-off treatments within trustworthy ML contexts.
Findings
- Combinatorial optimization provides a framework for reasoning about differences in ML model properties beyond empirical performance, including transparency, interpretability, robustness, fairness, privacy, and certifiability.
- CO is applicable to a range of tasks in trustworthy ML, spanning both model training and post-training activities.
- Specific tasks where CO is applied include interpretable model learning, explanation generation, robustness analysis, fairness auditing, model compression, and privacy attacks and protections.
- CO formulations offer distinct advantages over heuristic approaches, such as gradient-based methods, by enabling global guarantees, formal certificates, and explicit treatment of trade-offs.
- While scalability presents an ongoing challenge for CO applications in this domain, continuous improvements in solvers and hybrid algorithms suggest an expanding role for CO in the design and deployment of trustworthy ML systems.
Why This Matters
The ability to characterize ML model behavior beyond empirical performance — encompassing attributes like transparency, interpretability, robustness, fairness, privacy, and certifiability — is crucial for deploying reliable and responsible ML systems. This survey indicates that combinatorial optimization provides tools to gain deeper insights into these critical properties, supporting tasks from model selection to auditing. This matters for developing ML systems whose behavior can be better understood and certified, aligning with growing demands for trustworthiness in AI applications.