# From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 67 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 30 of 38)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Gradient Surgery for Multi-Task Learning](https://mlsanity.com/paper/2001.06782/) (2020)
- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Conflict-Averse Gradient Descent for Multi-task Learning](https://mlsanity.com/paper/2110.14048/) (2021)
- [Multi-Task Learning with Deep Neural Networks: A Survey](https://mlsanity.com/paper/2009.09796/) (2020)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Pareto Multi-Task Learning](https://mlsanity.com/paper/1912.12854/) (2019)
- [Multi-Task Learning as a Bargaining Game](https://mlsanity.com/paper/2202.01017/) (2022)
- [Just Pick a Sign: Optimizing Deep Multitask Models with Gradient Sign Dropout](https://mlsanity.com/paper/2010.06808/) (2020)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [RotoGrad: Gradient Homogenization in Multitask Learning](https://mlsanity.com/paper/2103.02631/) (2021)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [FAMO: Fast Adaptive Multitask Optimization](https://mlsanity.com/paper/2306.03792/) (2023)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning](https://mlsanity.com/paper/1907.04472/) (2019)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms](https://mlsanity.com/paper/2305.18409/) (2023)
- [Recovering Best Statistical Guarantees via the Empirical Divergence-based Distributionally Robust Optimization](https://mlsanity.com/paper/1605.09349/) (2016)
- [Computer-Aided Multi-Objective Optimization in Small Molecule Discovery](https://mlsanity.com/paper/2210.07209/) (2022)
- [Robust Multi-Task Learning with Excess Risks](https://mlsanity.com/paper/2402.02009/) (2024)
- [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025)

## Abstract (arXiv)

Multi-objective optimization (MOO) has received growing attention in applications that require learning under multiple criteria. However, most existing MOO formulations do not explicitly account for distributional shifts in the data. We introduce distributionally robust multi-objective optimization (DR-MOO), which minimizes multiple objectives under their respective worst-case distributions. We propose Pareto-type solution concepts for DR-MOO and develop multi-gradient descent algorithms (MGDA) with provable guarantees. Leveraging a Lagrangian dual reformulation, we first design a double-loop MGDA that uses an inner loop to estimate dual variables and achieves a total sample complexity O(ε-8) for reaching an ε-Pareto-stationary point. To further improve convergence, we combine large-batch sampling with gradient clipping to accommodate generalized smoothness and control bias in stochastic preference updates, eliminating the need for double sampling. This yields a single-loop double-clip MGDA with substantially improved sample complexity O(ε-4). Our theory applies to nonconvex problems without requiring uniformly bounded gradients of the dual objectives. Experiments demonstrate that our methods are competitive with state-of-the-art MGDA baselines.