Generalization In Multi-Objective Machine Learning
This work addresses a foundational gap in statistical learning theory for multi-objective ML, which is crucial for tasks involving multiple goals like efficiency, robustness, or fairness, though it is incremental as it provides initial theoretical steps.
The paper tackles the lack of theoretical understanding of generalization in multi-objective machine learning, establishing foundational generalization bounds and analyzing the relationship between true and empirical Pareto-optimal sets, revealing an asymmetry where all true Pareto-optimal solutions can be approximated by empirical ones but not vice versa.
Modern machine learning tasks often require considering not just one but multiple objectives. For example, besides the prediction quality, this could be the efficiency, robustness or fairness of the learned models, or any of their combinations. Multi-objective learning offers a natural framework for handling such problems without having to commit to early trade-offs. Surprisingly, statistical learning theory so far offers almost no insight into the generalization properties of multi-objective learning. In this work, we make first steps to fill this gap: we establish foundational generalization bounds for the multi-objective setting as well as generalization and excess bounds for learning with scalarizations. We also provide the first theoretical analysis of the relation between the Pareto-optimal sets of the true objectives and the Pareto-optimal sets of their empirical approximations from training data. In particular, we show a surprising asymmetry: all Pareto-optimal solutions can be approximated by empirically Pareto-optimal ones, but not vice versa.