Lexicographic Optimization: Algorithms and Stability

Jacob Abernethy, Robert E. Schapire, Umar Syed

Research output: Contribution to journalConference articlepeer-review

Abstract

A lexicographic maximum of a set X ⊆ Rn 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 Lc(x) = Pi exp(−cxi) converges to a lexicographic maximum of X as c → ∞, 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 log n ), all other components can converge c arbitrarily slowly.

Original languageEnglish (US)
Pages (from-to)2503-2511
Number of pages9
JournalProceedings of Machine Learning Research
Volume238
StatePublished - 2024
Event27th International Conference on Artificial Intelligence and Statistics, AISTATS 2024 - Valencia, Spain
Duration: May 2 2024May 4 2024

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Lexicographic Optimization: Algorithms and Stability'. Together they form a unique fingerprint.

Cite this