Navigating Non-Convex Pareto Fronts Beyond Linear Scalarization

584 concepts349 papers3 proposals

When optimizing systems with multiple conflicting goals—such as maximizing a robot's speed while minimizing its energy consumption—we rarely find a single "perfect" solution. Instead, we look for the Pareto front: the set of all optimal trade-offs where you cannot improve one objective without degrading another.

The most common reflex in machine learning is to smash these objectives together into a single score using a weighted sum (e.g., $F = w_1 \cdot \text{Reward} + w_2 \cdot \text{Safety}$). This technique, known as linear scalarization, is simple and computationally efficient. However, it suffers from a fundamental geometric flaw: in complex, non-convex optimization landscapes, linear scalarization is mathematically blind to large portions of the optimal trade-off space.

The Linear Scalarization Trap

To understand why linear scalarization fails, we must look at its geometry. A linear weighted sum defines a flat hyperplane in the objective space. When an optimizer maximizes this sum, it effectively pushes this hyperplane outward until it tangentially touches the boundary of the feasible objective space.

If the Pareto front is perfectly convex (curving outward), this works beautifully. By smoothly changing the weights, you tilt the slope of the hyperplane, allowing it to touch every single point along the front.

Convex Front (Linear sum works)      Non-Convex Front (Linear sum fails)
       Objective 2                          Objective 2
          |                                    |
          |  * *                               |  *
          | *    *  <-- Hyperplane             |   \   <-- Hyperplane bridges
          |*       *   touches here            |    \      over the concave dip
          +------------ Objective 1            |     * * * 
                                               +------------ Objective 1

However, real-world optimization landscapes are rarely purely convex. When the Pareto front contains concave regions—dents or valleys where the frontier curves inward—linear scalarization fails completely. As a straight line resting on the edges of a valley bridges right over the gap, a linear hyperplane will always snap to the outer edges (the convex hull) and skip the interior dip entirely.

As Tianye Shu et al. observe in Learning Pareto Set for Multi-Objective Continuous Robot Control, linear weighting is mathematically incapable of identifying optimal solutions located on these concave portions. No combination of positive weights can ever make a point inside the dip the unique optimum, leaving critical trade-offs completely unreachable.

Why Non-Convexity is Everywhere

While classical optimization often assumes convexity for mathematical convenience, modern deep learning, reinforcement learning (RL), and multi-task learning operate in highly non-linear, non-convex spaces.

Sharp Contours: The Power of Chebyshev Scalarization

To reach into the concave "dents" of a non-convex Pareto front, we must replace flat linear hyperplanes with non-linear scalarization functions that possess sharp, angular level sets. The most prominent of these is Chebyshev (or Tchebycheff) scalarization.

Instead of calculating a weighted average, Chebyshev scalarization minimizes the maximum weighted distance between the system's current performance and an unachievable "utopian" reference point ($z^*$):

$$F(x) = \max_{i} \left( w_i \cdot |f_i(x) - z^*_i| \right)$$

Geometrically, the level curves of a Chebyshev function are not straight lines; they are sharp, L-shaped angles.

Linear Level Curves (Flat)           Chebyshev Level Curves (L-Shaped)
          |                                    |
          | \                                  | |___
          |  \                                 | |   |
          |   \                                | |___|
          +------------                        +------------

As Qiuyi Zhang explains in Optimal Scalarizations for Sublinear Hypervolume Regret, these L-shaped level curves allow optimization algorithms to precisely target and nestle into concave regions of a Pareto frontier. The vertex of the "L" can slide directly into a dip, anchoring onto optimal trade-offs that a flat linear plane would skip over.

By minimizing the maximum weighted loss among tasks rather than summing them, the optimizer can safely explore the entire frontier. Biswajit Paria leverages this property in A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations, demonstrating that drawing random weights within a Chebyshev framework guarantees full coverage of the trade-off space, regardless of whether the underlying geometry is convex or non-convex.

Continuous Manifolds and Hypervolume Maximization

Rather than running separate optimization passes with different Chebyshev weights to find individual points, modern frameworks often aim to learn the entire Pareto front simultaneously as a continuous manifold.

One approach is to train a single neural network—a hypernetwork—to output the optimal model parameters for any given preference vector. To force this network to map non-convex regions accurately, researchers change the global training objective from scalarized losses to Hypervolume Maximization.

Xi Lin establishes the geometric foundations of this approach in Hypervolume Maximization: A Geometric View of Pareto Set Learning. Hypervolume measures the total multi-dimensional space dominated by a given Pareto front relative to a reference point. Because hypervolume treats the frontier as a cohesive geometric boundary, maximizing it naturally forces the learned manifold to expand outward into every available pocket—including concave regions—bypassing the limitations of point-wise linear weights.

Alternatively, agents can bypass scalarization entirely by conditioning policies directly on target goals. In Pareto Conditioned Networks, Mathieu Reymond et al. show that conditioning an RL agent on explicit target return vectors allows it to discover optimal policies in concave regions. By learning to navigate directly to vector targets rather than maximizing a collapsed scalar reward, the agent preserves the full dimensionality of the trade-off space.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 323 papers
  2. Version 1 · 2026-10-04 · 326 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_linear_scalarization_limitations_95162382,
  title = {linear scalarization limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-scalarization-limitations/rdr_95162382a4a74749bd4d7d550bfc9a30},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_linear_scalarization_limitations_95162382_v2,
  title = {linear scalarization limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-scalarization-limitations/rdr_95162382a4a74749bd4d7d550bfc9a30/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake