From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization
Abstract
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 𝒪(ε−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 𝒪(ε−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.
Related
- Data-driven joint optimization of maintenance and spare parts provisioning: A distributionally robust approach
- Nested Clustered Optimization Is One End of a Schur Bridge, and the Interior Is Sometimes Provably Better
- Conformal-DRO: Distributionally Robust Optimization with Conformalized Ambiguity Set
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- Calibrating Ambiguity Set via Diagnostic Transport for Distributionally Robust Optimization
BibTeX
@misc{yang2026from,
title = {{From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization}},
author = {Yufeng Yang and Fangning Zhuo and Ziyi Chen and Heng Huang and Yi Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.05660},
eprint = {2605.05660},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.05660},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization
AU - Yufeng Yang
AU - Fangning Zhuo
AU - Ziyi Chen
AU - Heng Huang
AU - Yi Zhou
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2605.05660
UR - https://arxiv.org/abs/2605.05660
AB - 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 𝒪(ε^−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 𝒪(ε^−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.
ER -