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

Overview

Modern machine learning (ML) often prioritizes predictive accuracy, frequently ignoring critical dimensions of trustworthiness such as interpretability, robustness, fairness, and privacy. This paper argues that these shortcomings are not merely technical bugs but fundamental design challenges. The authors propose that combinatorial optimization (CO) offers a superior framework for addressing these issues compared to traditional gradient-based heuristics, as CO allows for the explicit modeling of constraints and the attainment of global optimality.

The Shift to Optimization

The authors highlight the 'Rashomon effect,' where multiple models achieve similar predictive performance but differ significantly in their internal structure and trustworthiness. Rather than relying on black-box models, the authors advocate for using CO to navigate this set of accurate models to select those that satisfy specific transparency or fairness requirements. By framing trustworthiness as a feasibility or optimization problem, researchers can use tools like Mixed-Integer Linear Programming (MILP), Constraint Programming (CP), and Satisfiability Modulo Theories (SMT) to enforce formal guarantees.

Applications in Trustworthy ML

The survey categorizes the intersection of CO and ML into several key domains:

• Transparency and Interpretability: Using CO to learn sparse models (e.g., optimal decision trees or sparse linear regression) that are inherently understandable.
• Robustness: Formulating adversarial attacks and defenses as optimization problems to provide formal certificates of robustness against input perturbations.
• Fairness: Incorporating fairness constraints directly into the training process to ensure equitable outcomes across sensitive groups.
• Privacy: Auditing models for data leakage through reconstruction attacks and designing privacy-preserving mechanisms.