Agnostic Learning with Multiple Objectives

Corinna Cortes, Mehryar Mohri, Javier Gonzalvo, Dmitry StorcheusNeurIPS 2020 · OpenReview

Agnostic Learning with Multiple Objectives

Most machine learning models are trained to optimize a fixed, weighted sum of multiple objectives. However, this approach often leads to overfitting on some metrics while neglecting others. To address this, researchers have introduced Agnostic Learning with Multiple Objectives (ALMO), a framework that optimizes for the worst-case mixture of objectives, ensuring the resulting model is robust to any preference distribution and theoretically guaranteed to be Pareto-optimal.

The Problem with Fixed Weights

In real-world machine learning, we rarely care about just one metric. A translation model needs a high BLEU score, but it also needs to maintain correct word order and handle synonyms well. Usually, researchers combine these goals into a single scalar objective: $\sum \lambda_k \mathcal{L}_k$.

The vulnerability in this approach lies in how we choose those weights ($\lambda$). Most practitioners default to a uniform distribution (averaging the losses) or a fixed set of manual weights. This introduces three major flaws:

  1. Overfitting: A model might perform excellently on the average but fail catastrophically on one specific, critical objective.
  2. Unknown Preferences: In many industries, the "true" importance of different metrics is unknown or shifts over time.
  3. Computational Cost: Finding the "Pareto frontier" (the set of all optimal trade-offs) is computationally expensive and still leaves the user with the difficult task of picking a single point on that curve.

The ALMO Framework: A Minimax Approach

To solve this, the authors propose a minimax framework. Instead of minimizing a fixed average, the learner seeks to minimize the agnostic loss, which is defined as the maximum loss over all possible valid weight distributions.

Illustration of the minimax objective: the algorithm seeks the point that minimizes the upper envelope (maximum) of the individual loss functions.

Key Technical Components: * The Minimax Game: The optimization is treated as a two-player game. One player (the model) tries to minimize the loss, while an "adversary" chooses the weights $\lambda$ to maximize the current loss. This forces the model to improve on its weakest objectives. * Theoretical Guarantees: The authors prove that if the agnostic solution is unique, it is guaranteed to be Pareto-optimal. They also provide data-dependent generalization bounds using Rademacher complexity, which measures how complex the hypothesis space is relative to the objectives. * ALMO Algorithm: They provide a scalable stochastic gradient descent algorithm (based on Stochastic Mirror-Prox). It updates both the model parameters and the mixture weights iteratively, making it easy to implement in modern symbolic gradient frameworks like TensorFlow or PyTorch. * Regularization: The theory suggests a specific form of regularization that controls the weighted norm of the mixture weights, preventing the adversary from "cheating" by putting all weight on a single, noisy objective.

Key Insights and Ideas

  • Robustness as a Default: By optimizing for the worst-case mixture, the model becomes naturally "risk-averse." It won't sacrifice significant performance on one metric just to get a tiny gain on another.
  • Agnosticism as AutoML: ALMO effectively acts as an automated way to tune loss weights. During training, the algorithm automatically identifies which objectives are "hardest" for the current model and increases their weight.
  • Hidden Benefits: Interestingly, the authors found that ALMO models often performed better on metrics that weren't even part of the training objectives (like AUC), suggesting that the agnostic approach leads to more fundamentally robust representations.
  • Pareto Justification: While Pareto frontiers are usually hard to navigate, ALMO provides a theoretical "anchor point" on that frontier that is mathematically justified by the principle of robustness.

Experimental Results

The framework was evaluated on three standard benchmarks (MNIST, Fashion-MNIST, and ADULT) to demonstrate its versatility across different types of data. The experiments compared ALMO against a uniform weighting baseline across several loss functions (Cross-entropy, Zero-one, Hinge, and L1-norm).

  • Worst-Case Improvement: ALMO consistently improved the performance of the "worst" performing loss compared to the uniform baseline. For example, on the Adult dataset with logistic regression, the Hinge loss dropped from 0.967 (Uniform) to 0.518 (ALMO).
  • Generalization: In almost every test case, ALMO achieved a higher AUC (Area Under the Curve) than the uniform baseline, despite AUC not being explicitly optimized. On the DNN-Adult configuration, AUC jumped from 0.809 to 0.884.
  • Dynamics: The authors visualized the training dynamics, showing how the mixture weights $\lambda$ shift over time as the model masters different objectives, eventually settling into a stable, robust distribution.
Training dynamics showing how the mixture weights for different objectives automatically adjust over epochs.

Limitations and Future Work

The convergence guarantees for the algorithm currently rely on the loss functions and hypothesis space being convex. While the authors showed it works empirically on non-convex Deep Neural Networks (DNNs), the theoretical proof for the non-convex case remains an open challenge. Additionally, the current work assumes the weights $\lambda$ belong to a convex subset of the simplex. Future work could explore more complex constraints, such as hierarchical objectives or fairness-constrained weightings, as well as testing the scalability of the minimax game when there are hundreds of competing objectives in massive multi-task learning scenarios.

Summary updated

Abstract

Most machine learning tasks are inherently multi-objective. This means that the learner has to come up with a model that performs well across a number of base objectives $\cL_{1}, \ldots, \cL_{p}$, as opposed to a single one. Since optimizing with respect to multiple objectives at the same time is often computationally expensive, the base objectives are often combined in an ensemble $\sum_{k=1}^{p}\lambda_{k}\cL_{k}$, thereby reducing the problem to scalar optimization. The mixture weights $\lambda_{k}$ are set to uniform or some other fixed distribution, based on the learner's preferences. We argue that learning with a fixed distribution on the mixture weights runs the risk of overfitting to some individual objectives and significantly harming others, despite performing well on an entire ensemble. Moreover, in reality, the true preferences of a learner across multiple objectives are often unknown or hard to express as a specific distribution. Instead, we propose a new framework of \emph{Agnostic Learning with Multiple Objectives} ($\almo$), where a model is optimized for \emph{any} weights in the mixture of base objectives. We present data-dependent Rademacher complexity guarantees for learning in the $\almo$ framework, which are used to guide a scalable optimization algorithm and the corresponding regularization. We present convergence guarantees for this algorithm, assuming convexity of the loss functions and the underlying hypothesis space. We further implement the algorithm in a popular symbolic gradient computation framework and empirically demonstrate on a number of datasets the benefits of $\almo$ framework versus learning with a fixed mixture weights distribution.
BibTeX
@inproceedings{cortes2020agnostic,
  author = {Corinna Cortes and Mehryar Mohri and Javier Gonzalvo and Dmitry Storcheus},
  title = {{Agnostic Learning with Multiple Objectives}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=QtdTl9qu-8s},
}
Figure