Multi-Objective Optimization in Machine Learning

Introduction

Most real-world machine learning problems involve optimizing multiple competing objectives simultaneously. A recommendation system must balance relevance, diversity, and serendipity. A medical classifier must balance sensitivity and specificity. An autoML system must balance accuracy, latency, and memory footprint.

Multi-objective optimization (MOO) provides the mathematical framework to reason about these trade-offs rigorously, producing a set of optimal solutions — the Pareto front — rather than a single point, and enabling informed decision-making about trade-offs.

Core Concepts

Multi-Objective Problem Formulation

A multi-objective optimization problem is defined as:

$$\min_{\theta \in \Theta} \mathbf{F}(\theta) = (f_1(\theta), f_2(\theta), \ldots, f_m(\theta))$$

Where $\theta$ are the decision variables (e.g., model parameters, hyperparameters) and $f_1, \ldots, f_m$ are the $m$ objective functions (e.g., loss, latency, fairness violation).

Pareto Dominance

A solution $\theta^A$ dominates $\theta^B$ (written $\theta^A \prec \theta^B$) if and only if:

$$\forall i: f_i(\theta^A) \leq f_i(\theta^B) \quad \text{and} \quad \exists j: f_j(\theta^A) < f_j(\theta^B)$$

$\theta^A$ is at least as good as $\theta^B$ on all objectives and strictly better on at least one.

Pareto Front

The Pareto front is the set of all non-dominated solutions:

$$\mathcal{P}^* = {\theta \in \Theta : \nexists, \theta’ \in \Theta \text{ such that } \theta’ \prec \theta}$$

No solution in $\mathcal{P}^*$ can improve on one objective without degrading another. The Pareto front represents the complete picture of achievable trade-offs.

Hypervolume Indicator

The quality of an approximated Pareto front is measured by the hypervolume indicator $\text{HV}$:

$$\text{HV}(\mathcal{A}, r) = \lambda\left(\bigcup_{\theta \in \mathcal{A}} [\mathbf{F}(\theta), r]\right)$$

Where $r$ is a reference point dominated by all solutions and $\lambda$ is the Lebesgue measure. Higher hypervolume means a better Pareto front approximation.

Scalarization Methods

The simplest approach converts the multi-objective problem into a single-objective one by combining objectives.

Weighted Sum Scalarization

$$\min_\theta \sum_{i=1}^m w_i f_i(\theta) \quad \text{with} \quad \sum_i w_i = 1, w_i \geq 0$$

By varying the weight vector $\mathbf{w}$, different points on the Pareto front can be recovered. However, weighted sum only recovers convex parts of the Pareto front — non-convex regions are inaccessible regardless of the weights chosen.

Chebyshev (Minimax) Scalarization

$$\min_\theta \max_{i} w_i (f_i(\theta) - z_i^*)$$

Where $z_i^* = \min_\theta f_i(\theta)$ is the ideal point for objective $i$. The Chebyshev scalarization can recover non-convex Pareto front regions and is widely used in multi-objective Bayesian optimization.

Epsilon-Constraint Method

Fix all but one objective as constraints:

$$\min_\theta f_1(\theta) \quad \text{s.t.} \quad f_i(\theta) \leq \epsilon_i, ; i = 2, \ldots, m$$

By systematically varying $\epsilon$, the entire Pareto front can be recovered. Well-suited for problems where constraint satisfaction is natural (e.g., latency budget).

Reference Point Methods (MOEA/D)

Decompose the multi-objective problem into a set of subproblems, each with a different reference direction $\lambda^{(k)}$. Each subproblem is solved using a scalar aggregation function, and neighboring subproblems share information. Enables parallel exploration of the Pareto front.

Evolutionary Multi-Objective Algorithms

Evolutionary algorithms are naturally suited to MOO because they maintain a population of solutions, enabling direct Pareto front approximation.

NSGA-II (Non-Dominated Sorting Genetic Algorithm II)

The most widely used multi-objective evolutionary algorithm. Key mechanisms:

Non-dominated sorting: Sort the population into fronts $F_1 \prec F_2 \prec \ldots$. Front $F_1$ contains all non-dominated solutions.
Crowding distance: Within each front, prefer solutions with larger crowding distance (more isolated in objective space) to maintain diversity.
Selection: Combine parent and offspring populations, then select the best $N$ individuals using non-dominated rank and crowding distance.

Time complexity: $O(mN^2)$ per generation, where $N$ is population size.

NSGA-III

Extends NSGA-II to many-objective problems ($m > 3$) by replacing crowding distance with reference point-based diversity preservation. A set of reference directions is distributed uniformly on the unit hyperplane, and solutions are associated with the nearest reference direction.

MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition)

Decomposes the MOO problem into $N$ scalar subproblems and solves them simultaneously using a genetic algorithm. Neighboring subproblems (similar weight vectors) share solutions, enabling efficient parallel optimization. Particularly effective when the Pareto front is convex or known to have specific structure.

Gradient-Based Multi-Objective Optimization

For differentiable objectives (common in neural network training), gradient-based methods are more efficient than evolutionary algorithms.

Multiple Gradient Descent Algorithm (MGDA)

Finds a descent direction that reduces all objectives simultaneously. At each step, solve the quadratic program:

$$\min_{\alpha_1, \ldots, \alpha_m} \left| \sum_{i=1}^m \alpha_i \nabla_\theta f_i(\theta) \right|^2 \quad \text{s.t.} \quad \alpha_i \geq 0, \sum_i \alpha_i = 1$$

The solution $\alpha^*$ gives the optimal convex combination of gradients. If the minimum is 0, the current point is Pareto-stationary.

import torch
from scipy.optimize import minimize
import numpy as np

def mgda_step(gradients):
    """Find MGDA update direction given list of per-objective gradients."""
    m = len(gradients)
    G = torch.stack([g.flatten() for g in gradients])  # (m, d)
    G_np = G.detach().cpu().numpy()

    # Solve QP: min ||G^T alpha||^2 s.t. sum(alpha)=1, alpha>=0
    M = G_np @ G_np.T  # (m, m)

    def objective(alpha):
        return 0.5 * alpha @ M @ alpha

    def grad_objective(alpha):
        return M @ alpha

    constraints = [{'type': 'eq', 'fun': lambda a: np.sum(a) - 1}]
    bounds = [(0, None)] * m
    alpha0 = np.ones(m) / m

    result = minimize(objective, alpha0, jac=grad_objective,
                      bounds=bounds, constraints=constraints,
                      method='SLSQP')
    alpha = torch.tensor(result.x, dtype=G.dtype)

    # Compute combined gradient
    combined_grad = (alpha.unsqueeze(1) * G).sum(0)
    return combined_grad.reshape(gradients[0].shape)

Pareto MTL (Multi-Task Learning)

Applies MOO to multi-task learning: each task’s loss is an objective, and MGDA finds a shared parameter update that does not harm any task. This avoids the negative transfer problem where optimizing a single weighted loss harms some tasks.

Conflicting Gradient Methods

When gradients from different objectives conflict, methods like GradDrop (selectively drop conflicting gradient components) or PCGrad (project conflicting gradients onto each other’s normal planes) reduce inter-task interference.

Multi-Objective Bayesian Optimization

For expensive black-box objectives (e.g., training a model to measure accuracy and latency), Bayesian optimization extends naturally to MOO.

EHVI (Expected Hypervolume Improvement)

The acquisition function measures the expected increase in hypervolume from a candidate point:

$$\text{EHVI}(\theta) = \mathbb{E}[\text{HV}(\mathcal{A} \cup {\theta}, r) - \text{HV}(\mathcal{A}, r)]$$

Maximizing EHVI selects the candidate most likely to extend the Pareto front. Efficient analytical formulas exist for Gaussian process posteriors.

qNEHVI (Noisy Batch EHVI)

Extends EHVI to noisy evaluations and batch selection (selecting multiple candidates per iteration). Uses Monte Carlo integration for the expectation, enabling parallel multi-objective Bayesian optimization.

Applications in Machine Learning

Hyperparameter Optimization (AutoML)

Multi-objective hyperparameter optimization jointly optimizes:

Accuracy vs. training time: Avoid over-spending compute for marginal gains.
Accuracy vs. model size: Find the smallest model achieving target accuracy.
Accuracy vs. inference latency: Critical for edge deployment.

Tools like Ax (Meta), SMAC3, and Ray Tune support multi-objective optimization with Pareto front output.

Neural Architecture Search (NAS)

NSGA-II and NSGA-III are widely applied in hardware-aware NAS to find architectures on the Pareto front of:

Test accuracy (maximize)
FLOPs (minimize)
Parameter count (minimize)
Latency on target hardware (minimize)

NSGA-Net, CARS, and Once-for-All are NAS methods explicitly built around multi-objective evolutionary search.

Fairness-Accuracy Trade-offs

Fairness constraints create natural trade-offs:

Accuracy vs. demographic parity: Equalizing positive prediction rates across groups often reduces overall accuracy.
Accuracy vs. equalized odds: Equalizing TPR/FPR across groups may require sacrificing accuracy.

Multi-objective optimization finds the complete Pareto front of fairness-accuracy trade-offs, enabling stakeholders to choose operating points based on policy rather than optimization defaults.

Multi-Task Learning

In multi-task settings, each task’s loss is an objective. MOO methods find model parameters that are Pareto-optimal across all tasks, avoiding the arbitrary task weighting required by weighted sum approaches.

LLM Alignment (RLHF)

RLHF involves trade-offs between:

Helpfulness (high reward)
Harmlessness (low policy violation)
KL divergence from the base model (stay close to pretrained behavior)

Multi-objective RL methods find policies on the Pareto front of these objectives, enabling alignment researchers to make explicit trade-off decisions.

Diversity Metrics for Pareto Fronts

Generational Distance (GD)

Measures how close the approximated front $\mathcal{A}$ is to the true front $\mathcal{P}^*$:

$$\text{GD}(\mathcal{A}, \mathcal{P}^) = \frac{1}{|\mathcal{A}|} \sum_{\theta \in \mathcal{A}} \min_{\theta^ \in \mathcal{P}^} d(\theta, \theta^)$$

Lower is better. GD measures convergence but not diversity.

Inverted Generational Distance (IGD)

$$\text{IGD}(\mathcal{A}, \mathcal{P}^) = \frac{1}{|\mathcal{P}^|} \sum_{\theta^* \in \mathcal{P}^} \min_{\theta \in \mathcal{A}} d(\theta^, \theta)$$

IGD measures both convergence and coverage — a low IGD means every part of the Pareto front is well-approximated.

Challenges and Open Problems

Scalability to many objectives: With $m > 5$ objectives, Pareto dominance becomes uninformative (almost all solutions are non-dominated), requiring alternative aggregation strategies.
Expensive-to-evaluate objectives: Each objective evaluation may require training a model from scratch; Bayesian optimization helps but scales poorly to large $m$.
Non-differentiable objectives: Latency, memory, and fairness metrics may not be differentiable, requiring surrogate models or evolutionary methods.
Preference elicitation: The Pareto front contains infinitely many solutions; helping decision-makers select their preferred operating point requires interactive or preference-based methods.

Summary

Multi-objective optimization provides principled tools for navigating the inherent trade-offs in machine learning system design. By framing model training, architecture search, and alignment as MOO problems, practitioners can expose the full range of achievable trade-offs rather than making implicit choices via scalar weights. Methods range from simple scalarization (fast but limited) to evolutionary algorithms (broadly applicable) to gradient-based approaches (efficient for differentiable objectives) and Bayesian optimization (sample-efficient for expensive objectives). As ML systems become more tightly constrained by efficiency, fairness, and safety requirements, multi-objective optimization becomes an essential component of responsible model development.