Pareto Front Identification from Stochastic Bandit Feedback

Peter Auer, Chao-Kai Chiang, Ronald Ortner, Madalina M. DruganAISTATS 2016 · OpenReview

Abstract

We consider the problem of identifying the Pareto front for multiple objectives from a finite set of operating points. Sampling an operating point gives a random vector where each coordinate corresponds to an objective. This paper introduces a robust, elimination-based algorithm that identifies all Pareto-optimal points without relying on the restrictive regularity assumptions required by previous methods.

What Problem Does This Paper Address?

In many real-world scenarios, we want to optimize multiple conflicting objectives at once—for example, maximizing a software's performance while minimizing its memory footprint. The "best" solutions are those on the Pareto front: points where you cannot improve one objective without making another one worse.

The challenge arises when we don't know the true values of our options (operating points) and can only learn about them by "sampling" them, which yields noisy, stochastic results. This is a multi-objective version of the multi-armed bandit problem. While identifying a single best arm is well-studied, identifying an entire frontier of optimal points is much more complex because:

  1. A point might be Pareto-optimal even if it isn't the "best" in any single category.
  2. Sampling one point provides information about all its objectives simultaneously, creating a combinatorial search space.
  3. Distinguishing between a point that is truly on the front and one that is just "very close" requires careful statistical management.

Methods

The authors propose two main algorithmic contributions:

  1. Algorithm 1 (Pareto Front Identification): An elimination-based algorithm. It maintains a set of "active" points and repeatedly samples them. It uses confidence bounds to prune points that are statistically guaranteed to be dominated by others. Conversely, it moves points into a permanent "Pareto" set once it is highly confident they are either on the front or sufficiently close to it (within a precision parameter $\epsilon_0$).
  2. Algorithm 3 (Asymmetric Covering): Because the Pareto front can be dense, the authors provide a way to find a "sparse cover"—a smaller subset of points that represents the whole front. They develop a novel algorithm to handle asymmetric distance, which is necessary because the concept of "dominance" in multi-objective optimization is inherently directional.

Unlike the previous state-of-the-art (the PAL algorithm), this approach does not assume the underlying data follows a Gaussian Process, making it more "distribution-free" and robust to irregular data.

Datasets

The researchers evaluated their approach using the SW-LLVM dataset, which involves 1,024 different compiler settings for the LLVM compiler infrastructure. The goal is to balance performance (speed) against memory footprint. To simulate stochasticity, they used a subset of 16 distinct operating points, using the variance in the original measurements to provide noisy feedback.

Operating points and the Pareto front for the LLVM dataset, where memory footprint is negated to transform the problem into a maximization task.

Key Insights and Ideas

  • Geometric Complexity: The "hardness" of finding the Pareto front is defined by specific geometric gaps. These gaps measure how much a point needs to "move" to either dominate another or be dominated.
  • Asymmetry is Vital: Standard distance metrics fail in multi-objective optimization. The authors show that you must use asymmetric distance functions to correctly define what it means for a set of points to "cover" the Pareto front.
  • Conservative is Reliable: By using frequentist confidence bounds rather than Bayesian priors, the algorithm is more conservative. It might take more samples, but it is far less likely to "miss" a Pareto-optimal point simply because the data didn't fit a specific curve.

Key Results

  • Theoretical Bounds: The authors proved that their algorithm's sample complexity is characterized by the natural geometric properties of the operating points. They provided both upper and lower bounds that nearly match.
  • Stability: In experiments, Algorithm 1 consistently achieved the desired precision across 1,000 runs.
  • Comparison with PAL: While the PAL algorithm was often faster (required fewer samples), it frequently failed to find the actual Pareto front or returned points far from the front when the data was irregular. Algorithm 1 was much more stable, always finding the optimal points once sufficient samples were provided.
Comparison of success rates between Algorithm 1 and PAL. Algorithm 1 maintains a 100% success rate across various precision levels (epsilon_0), whereas PAL's reliability drops as the precision requirement tightens.

Limitations and Future Work

  • Sample Efficiency: The algorithm is "conservative," meaning it samples every active point in each round. In scenarios with a massive number of points, this could be prohibitively expensive.
  • Scaling to High Dimensions: While the math holds for $D$ objectives, the "gaps" that define complexity likely become much smaller as the number of objectives increases, potentially leading to an exponential increase in required samples.
  • Future Directions: The authors suggest that their asymmetric covering algorithm is of "independent interest" and could be applied to other areas of computer science where directional relationships are more important than standard distance.

Summary updated

Abstract

We consider the problem of identifying the Pareto front for multiple objectives from a finite set of operating points. Sampling an operating point gives a random vector where each coordinate corres...
BibTeX
@inproceedings{auer2016pareto,
  author = {Peter Auer and Chao-Kai Chiang and Ronald Ortner and Madalina M. Drugan},
  title = {{Pareto Front Identification from Stochastic Bandit Feedback}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=S7heFOXO6mJ},
}
Figure