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:
- The Iterative Method: Solving a sequence of $n$ optimization problems, fixing components one by one.
- 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.
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