# Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization

arXiv: https://arxiv.org/abs/2504.02833 · HTML: https://mlsanity.com/paper/2504.02833/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 16 Mar 2025.

## Builds on (most cited first, 16 of 16)

- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [Pareto Multi-Task Learning](https://mlsanity.com/paper/1912.12854/) (2019)
- [Smooth Tchebycheff Scalarization for Multi-Objective Optimization](https://mlsanity.com/paper/2402.19078/) (2024)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [A Very Brief Introduction to Machine Learning With Applications to Communication Systems](https://mlsanity.com/paper/1808.02342/) (2018)
- [Linear Convergence of Primal-Dual Gradient Methods and their Performance in Distributed Optimization](https://mlsanity.com/paper/1904.01196/) (2019)
- [Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions](https://mlsanity.com/paper/2010.11450/) (2020)
- [Networked Signal and Information Processing](https://mlsanity.com/paper/2210.13767/) (2022)
- [A Survey of Multi-Objective Optimization in Wireless Sensor Networks: Metrics, Algorithms and Open Problems](https://mlsanity.com/paper/1609.04069/) (2016)
- [Exact Pareto Optimal Search for Multi-Task Learning and Multi-Criteria Decision-Making](https://mlsanity.com/paper/2108.00597/) (2021)
- [Stability and Performance Limits of Adaptive Primal-Dual Networks](https://mlsanity.com/paper/1408.3693/) (2014)
- [Over-the-Air Fair Federated Learning via Multi-Objective Optimization](https://mlsanity.com/paper/2501.03392/) (2025)
- [Accelerating Min-Max Optimization with Application to Minimal Bounding Sphere](https://mlsanity.com/paper/1905.12733/) (2019)
- [Identification of Active Subfunctions in Finite-Max Minimisation via a Smooth Reformulation](https://mlsanity.com/paper/2404.10326/) (2024)
- [Hybrid Precoding With Low-Resolution PSs for Wideband Terahertz Communication Systems in The Face of Beam Squint](https://mlsanity.com/paper/2406.16303/) (2024)

## Abstract (arXiv)

In multi-objective optimization, minimizing the worst objective can be preferable to minimizing the average objective, as this ensures improved fairness across objectives. Due to the non-smooth nature of the resultant min-max optimization problem, classical subgradient-based approaches typically exhibit slow convergence. Motivated by primal-dual consensus techniques in multi-agent optimization and learning, we formulate a smooth variant of the min-max problem based on the augmented Lagrangian. The resultant Exact Pareto Optimization via Augmented Lagrangian (EPO-AL) algorithm scales better with the number of objectives than subgradient-based strategies, while exhibiting lower per-iteration complexity than recent smoothing-based counterparts. We establish that every fixed-point of the proposed algorithm is both Pareto and min-max optimal under mild assumptions and demonstrate its effectiveness in numerical simulations.