Lexicographic Optimization: Algorithms and Stability

Jacob D. Abernethy, Robert E. Schapire, Umar Syed

Abstract

Lexicographic optimization seeks vectors that maximize their smallest components in a prioritized order, a task central to fair resource allocation and game theory. This paper bridges the gap between iterative optimization and exponential loss minimization. We introduce the concept of lexicographic stability to characterize sets where these methods converge. Our analysis reveals a convergence dichotomy: while the first two components converge at a rate of $O(1/c)$, higher-order components can be arbitrarily slow. Furthermore, we show that the Multiplicative Weights algorithm, previously thought unsuitable for this task, can be rehabilitated with a $1/t$ learning rate decay.

Introduction

In fields such as fair resource allocation, game theory, and machine learning, the "lexicographic maximum" (lexmax) is a gold standard for fairness. A lexmax solution ensures that the least-advantaged participant receives as much as possible; once that is maximized, the second-least-advantaged is prioritized, and so on.

Traditionally, two methods have been used to find these solutions:

  1. The Iterative Method: Solving a sequence of $n$ optimization problems, fixing components one by one.
  2. The Exponential Loss Method: Minimizing a "soft" objective function $L_c(\mathbf{x}) = \sum \exp(-cx_i)$, where $c \to \infty$.

Despite their use, several theoretical gaps remained. It was unclear if the exponential loss method worked for general sets beyond simple polytopes, how fast it converged, and whether the iterative method was stable under small perturbations.

Lexicographic Stability and Methods

The authors introduce lexicographic stability as the key property determining whether an algorithm can reliably find the lexmax. Stability implies that small errors in the intermediate steps of an iterative algorithm do not compound into a final result far from the true maximum.

The study employs a mix of geometric analysis and convergence proofs:

  • Geometric Analysis: The authors prove that all convex polytopes are stable. However, they provide a counterexample of a smooth, compact convex set that lacks stability, showing that the success of lexmax optimization depends heavily on the set's geometry.
  • Convergence Analysis: For stable sets, the exponential loss minimizer is guaranteed to converge to the lexmax.
  • Algorithm Rehabilitation: The paper revisits the Multiplicative Weights (MW) algorithm. While prior work suggested MW could not find a lexmax, this paper demonstrates that a simple modification—decaying the learning rate at a rate of $1/t$—enables convergence.

The Convergence Dichotomy

A primary contribution of this work is the discovery of a "convergence dichotomy." The authors found that the first and second smallest components of the vector converge to their optimal values relatively quickly (at a rate of roughly $\log n / c$).

In contrast, components from the third to the $n$-th can converge arbitrarily slowly. This explains the numerical difficulties often encountered when solving high-dimensional lexicographic problems: unless the parameter $c$ is exponentially large relative to the desired precision, higher-order components may remain far from their optimal values.

Results and Algorithmic Implications

The theoretical findings translate into concrete algorithmic results:

  • Polytopes: Every convex polytope is lexicographically stable.
  • Convergence Rates: For the first two components, the error is bounded by $O(1/c)$. Specifically, $d_{\{1,2\}}(\mathbf{x}^* | \mathbf{x}_{c,\gamma}) \leq \frac{1}{c} \log \frac{n-k+1}{1-\gamma}$.
  • MW Fix: By setting the learning rate $\eta_t = c/t$, the Multiplicative Weights algorithm achieves a convergence rate of $O(c \log T / T)$ for the smooth loss function.
Algorithm 1: Modified Multiplicative Weights for Lexicographic Optimization.

Conclusion and Future Work

This research provides the first formal link between iterative "progressive filling" and "soft" exponential loss approaches. While it confirms that polytopes are "safe" for these methods, the discovery of the convergence dichotomy highlights significant practical hurdles for high-dimensional problems.

Future research may explore alternative loss functions that avoid lopsided convergence or extend the characterization of stability to non-convex regions. Additionally, these results offer a potential framework for understanding implicit regularization in algorithms like AdaBoost, where the choice of loss function might implicitly favor "fair" or "max-margin" solutions.

Summary updated

Abstract

A lexicographic maximum of a set $X \subseteq \mathbb{R}^n$ is a vector in $X$ whose smallest component is as large as possible, and subject to that requirement, whose second smallest component is as large as possible, and so on for the third smallest component, etc. Lexicographic maximization has numerous practical and theoretical applications, including fair resource allocation, analyzing the implicit regularization of learning algorithms, and characterizing refinements of game-theoretic equilibria. We prove that a minimizer in $X$ of the exponential loss function $L_c(\mathbf{x}) = \sum_i \exp(-c x_i)$ converges to a lexicographic maximum of $X$ as $c \rightarrow \infty$, provided that $X$ is stable in the sense that a well-known iterative method for finding a lexicographic maximum of $X$ cannot be made to fail simply by reducing the required quality of each iterate by an arbitrarily tiny degree. Our result holds for both near and exact minimizers of the exponential loss, while earlier convergence results made much stronger assumptions about the set $X$ and only held for the exact minimizer. We are aware of no previous results showing a connection between the iterative method for computing a lexicographic maximum and exponential loss minimization. We show that every convex polytope is stable, but that there exist compact, convex sets that are not stable. We also provide the first analysis of the convergence rate of an exponential loss minimizer (near or exact) and discover a curious dichotomy: While the two smallest components of the vector converge to the lexicographically maximum values very quickly (at roughly the rate $\frac{\log n}{c}$), all other components can converge arbitrarily slowly.
BibTeX
@inproceedings{abernethy2024lexicographic,
  author = {Jacob D. Abernethy and Robert E. Schapire and Umar Syed},
  title = {{Lexicographic Optimization: Algorithms and Stability}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=mfyYIg2aFC},
}

Loading related content...

Figure