# MGDA Converges under Generalized Smoothness, Provably arXiv: https://arxiv.org/abs/2405.19440 · HTML: https://mlsanity.com/paper/2405.19440/ ## Key facts - Cited by 7 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 40 references that are in the map. - First posted on arXiv 29 May 2024. ## Builds on (most cited first, 30 of 32) - [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016) - [SegNet: A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation](https://mlsanity.com/paper/1511.00561/) (2015) - [Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics](https://mlsanity.com/paper/1705.07115/) (2017) - [Gradient Surgery for Multi-Task Learning](https://mlsanity.com/paper/2001.06782/) (2020) - [GradNorm: Gradient Normalization for Adaptive Loss Balancing in Deep Multitask Networks](https://mlsanity.com/paper/1711.02257/) (2017) - [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) - [End-to-End Multi-Task Learning with Attention](https://mlsanity.com/paper/1803.10704/) (2018) - [Conflict-Averse Gradient Descent for Multi-task Learning](https://mlsanity.com/paper/2110.14048/) (2021) - [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019) - [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (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) - [The ApolloScape Open Dataset for Autonomous Driving and its Application](https://mlsanity.com/paper/1803.06184/) (2018) - [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023) - [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013) - [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017) - [Reasonable Effectiveness of Random Weighting: A Litmus Test for Multi-Task Learning](https://mlsanity.com/paper/2111.10603/) (2021) - [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023) - [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022) - [FAMO: Fast Adaptive Multitask Optimization](https://mlsanity.com/paper/2306.03792/) (2023) - [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) - [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023) - [Fair Resource Allocation in Multi-Task Learning](https://mlsanity.com/paper/2402.15638/) (2024) - [Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms](https://mlsanity.com/paper/2305.18409/) (2023) - [Multi-Objective SPIBB: Seldonian Offline Policy Improvement with Safety Constraints in Finite MDPs](https://mlsanity.com/paper/2106.00099/) (2021) - [Variance-reduced Clipping for Non-convex Optimization](https://mlsanity.com/paper/2303.00883/) (2023) ## Built on by (most cited first, 7 of 7) - [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025) - [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025) - [Are Large Vision-Language Models Ready to Guide Blind and Low-Vision Individuals?](https://mlsanity.com/paper/2510.00766/) (2025) - [Step-level Denoising-time Diffusion Alignment with Multiple Objectives](https://mlsanity.com/paper/2604.14379/) (2026) - [From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization](https://mlsanity.com/paper/2605.05660/) (2026) - [A Unified Framework for Gradient Aggregation in Multi-Objective Optimization](https://mlsanity.com/paper/2605.30452/) (2026) - [Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates](https://mlsanity.com/paper/2610.13773/) (2026) ## Abstract (arXiv) Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning. Recent works provide some effective algorithms with theoretical analysis but they are limited by the standard L-smooth or bounded-gradient assumptions, which typically do not hold for neural networks, such as Long short-term memory (LSTM) models and Transformers. In this paper, we study a more general and realistic class of generalized ℓ-smooth loss functions, where ℓ is a general non-decreasing function of gradient norm. We revisit and analyze the fundamental multiple gradient descent algorithm (MGDA) and its stochastic version with double sampling for solving the generalized ℓ-smooth MOO problems, which approximate the conflict-avoidant (CA) direction that maximizes the minimum improvement among objectives. We provide a comprehensive convergence analysis of these algorithms and show that they converge to an ε-accurate Pareto stationary point with a guaranteed ε-level average CA distance (i.e., the gap between the updating direction and the CA direction) over all iterations, where totally O(ε-2) and O(ε-4) samples are needed for deterministic and stochastic settings, respectively. We prove that they can also guarantee a tighter ε-level CA distance in each iteration using more samples. Moreover, we analyze an efficient variant of MGDA named MGDA-FA using only O(1) time and space, while achieving the same performance guarantee as MGDA.